Re: GSoC ticket #1069 (t hread scheduler) application

Hi André,

"André Braga" <[email protected]> wrote:
> Should we follow the letter of the "Thread Priorities" entry on the
> BeBook (Kernel Kit, Thread Concepts) and allow RT threads run
> uninterrupted until some event leads to unscheduling? Wouldn't it be
> better to set some threshold as to how long a RT thread would be
> allowed to run? I remember Axel has pointed towards the latter.

RT threads should only be interrupted by threads with higher priority.
However, if an RT thread consumes too much CPU time, it should be 
stopped from doing so - if easily possible, that is (it would be nice, 
but it doesn't have to be there, ie. BeOS doesn't have such mechanism, 
and you only rarely suffer from it :-)).

> Should we use separate structures, one to reference blocked threads
> and other to reference ready threads?

What do you call a blocked thread?

> My initial impression is that
> it's really not necessary and that the overhead to transfer threads
> from one structure to the other is probably higher than skipping
> candidate threads that can't be run until a suitable one is found. If
> for example the number of blocked threads is 66%, on average it takes
> 3 comparisons to find a ready thread, and O(n) on the degenerate 
> case.
[...]

Why should waiting threads be put into the ready list? Usually, the 
number of waiting threads exceeds the number of ready threads by a huge 
amount.
But I'm not sure what you're targeting at.
Having separate queues for ready threads and those that are waiting 
doesn't cost anything, at least in the current implementation.

> OTOH, actual O(1) scheduling could be attained by separating those
> structures, so it is definitely desirable. So, if no one objects, and
> despite my own previous reasoning and gut feelings, this is probably
> how I'll proceed. I believe the blocked threads structure should take
> into account the reason why a thread was unscheduled. Should the
> structure be actually organized according to unscheduling reason (the
> categories would be, for example, "blocked by slow I/O", "blocked by
> fast I/O", "slept for x (m,n,µ)s", "waiting on semaphore" etc) and

You don't know anything about I/O. You can just assume that a thread 
with a higher priority wants to run earlier than the other. The I/O 
scheduler (once it's there) will probably inherit thread priority as I/
O priority.

> threads would be kept partially ordered according to wakeup 
> expectance
> inside each category, or shall we just use a big clock structure with
> cues to every y (appropriate submultiple of 'second')s and order
> threads according to said wakeup expectance, and then just walk this
> whole structure every time the scheduler runs? I tend to prefer the
> finer grain, but it might just not pay off.

I don't see the advantage in such a mechanism, but I'm no scheduler 
expert either.

> Is O(1) a concern for scheduling only, or is it desirable to happen
> for every thread operation, like find_thread? This is just classic
> time-space tradeoff, and we either just search linearly for a thread,
> or use separate, more efficient structure to list their locations,
> like a hashtable.

For now, please focus on scheduling :-)
Other optimizations may come later as the need arises, but they are 
completely unrelated.

> Finally (for now; you'll surely hear lots of further questioning as I
> move along): the previous question brought up another one I'd like to
> generalize here: how big a concern is memory usage? I'm talking about
> bit brushing here. I could, for example, use some pointer math with 8
> -
> and 16-bit offsets instead of saving full pointers on a 32- or 64-bit
> word, and then use the saved bits to store extra information; or it
> might not be worth the trouble. I could choose not use extra pointers

Please don't do such magic, the C64 is over :-)

> and use single-linked lists and walk the list to perform removal
> operations, or I could use double-linked lists and make removal
> operations take constant time. I'm pretty much sold on the idea that 
> a
> custom memory allocator tailored to thread creation and access
> patterns is VERY desirable, so thread structures will be allocated
> close together according to their base priority classes and other
> relevant information that would lead to better exploiting spatial and
> temporal locality. I'm also not ruling out using memory prefetch
> instructions straight in the scheduler code. w00t.

Don't spend much thought on that one either; it's another topic and 
will eventually be covered by a smart slab allocator implementation. If 
you want to work on that as well, fine, but the scheduler should be 
independent, and comes first :-)

> I'm always suggesting alternatives ranging from naïve to 
> sophisticated
> because some implementations may demand considerable kernel code
> surgery to accommodate all the changes required to support them. It
> will probably mean the code won't resemble it's NewOS heritage, 
> making
> syncing with the NewOS codebase difficult, if not impossible. [...]

Don't mind, at least Travis intends to work on Haiku as time permits.

Bye,
   Axel.


-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV