Re: GSoC ticket #1069 (thread scheduler) application

Hi,

On 4/10/07, Axel Dörfler <[email protected]> wrote:
> 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 :-)).

I assume the scheduler still runs at regular intervals, and it will
just allow the current RT thread to run unless blocked or a
higher-priority one becomes ready. Right? If so, that's almost trivial
to implement, unless there are any weird catches I'm not aware of...

> > Should we use separate structures, one to reference blocked threads
> > and other to reference ready threads?
>
> What do you call a blocked thread?

Poor choice of words, sorry. I meant any thread not in a ready state.

> Why should waiting threads be put into the ready list?

Simplicity?

> Usually, the
> number of waiting threads exceeds the number of ready threads by a huge
> amount.

By "waiting" you mean "waiting on a semaphore" or "blocked by I/O", I
assume. My impression happened to be the opposite, that ready threads
are the more prevalent ones and they just wait for the opportunity to
run. But it doesn't matter, really.

> But I'm not sure what you're targeting at.

Just wrapping these things around my head; don't worry. I'll
eventually ask outright retarded questions, and then obviousness will
strike me so had I'll be enlighted. Kind of zen, no? ;)

> Having separate queues for ready threads and those that are waiting
> doesn't cost anything, at least in the current implementation.

Won't cost anything in either implementations; it's just a matter of
deciding what to do. But, as I mentioned below...

> > OTOH, actual O(1) scheduling could be attained by separating those
> > structures, so it is definitely desirable. [...] 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

1st thing to notice is that walking a list is inherently O(n). You
either "know" what to do and then do it in constant time, or you don't
and must have some feedback from the external world to decide how
you'll do it. The latter generally means walking a list and comparing
values between all items, i.e., some incarnation of min/max. The
former means organizing your data in such a way that you'll always
have your answer at hand.

Let's not forget that order of complexity is not literal. O(1) doesn't
mean "instantaneous", and O(n) doesn't mean "godawful slow"; they only
mean that, in the O(1) case, there's a constant overhead to find the
answer independently of how large the data set is, and in the O(n)
case, the overhead is proportional to the size of the data set. For
certain sizes of n, O(n) can be faster than O(1), depending on the
overhead of the latter.

Still, my prototype for the scheduler becomes twice as fast at context
switching as a regular O(n) implementation with as few as 20 threads,
so I suppose the overhead for my implementation was pretty low
already, and then I identified a horrific bottleneck and already have
a good solution for it... So expect even lower overhead. :D

> You don't know anything about I/O.

Hmm....

> You can just assume that a thread with a higher priority wants to run
> earlier than the other.

OK, but can't we change this assumption? I'd REALLY like to tag the
reason for unscheduling (e.g., I/O request), so that we can easily
find that very unscheduled thread later when (using that example) the
request is completed.

> The I/O > scheduler (once it's there) will probably inherit thread priority as I/
> O priority.

I believe those requirements are orthogonal. I'm not trying to mix I/O
priority with scheduling priority; what I do want is a quick way to
transfer formerly non-ready threads from the "non-ready" structure to
the "ready" structure, and the quicker way is to NOT search for
became-ready threads among god-knows-how-many unrealated not-ready
threads, but KNOW where they are supposed to be given the completion
of some event.

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

You mean the large, unstructured list, or the more structured one? I
hope the I explained a little better where I was trying to get to in
the last paragraph.

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

They're not THAT unrelated when you consider signal/message delivery.
Picture a runaway, high-priority thread stuck in an infinite loop. Now
consider your desire to kill it, lower its priority, whatever. Should
we just walk the whole list of threads? Wouldn't a hashtable that
points to the same threads as the list be more efficient when you want
or need to find one quickly?

That's definitely something not to touch until the scheduler coding is
done, but I'd like to lay down some tasks to tackle next ;)

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

Ah, the nostalgia ;)

But that was because I was considering millions of threads, not
thousands. Billions, even, on 64-bit systems with a lot of RAM to
spare. The beauty of O(1) is that it does scale that well when data is
not interdependant.

> 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 :-)

Sure. Don't worry, I'm not losing focus. "That's definitely something
not to touch until the scheduler coding is done, but I'd like to lay
down some tasks to tackle next ;)"

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

Hoh, cool!

> Bye,
>    Axel.

Cheers,
A.

-------------------------------------------------------------------------
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