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

"André Braga" <[email protected]> wrote:
> 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...

Please have a look at the current scheduler to see how it's supposed to 
work: whenever a thread is scheduled to run, a timer interrupt is 
started that defines the quantum of the thread (currently fixed 3 ms).
But this quantum can get cut if the thread decides to block; in that 
case, the scheduler is invoked directly, and the quantum timer is 
aborted.

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

I think you misunderstand how this process is working - I will try to 
explain it below :-)
But anyway, you cannot know why a thread is waiting or what it is 
waiting for - the kernel only knows threads that wait on a semaphore or 
not (neglecting suspended threads here).

[...]
> 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.

You never need to search for them; whenever a blocked thread gets 
ready, the semaphore code will actively put this thread into the run 
queue; you don't have to care, you just have to write the code that 
actually puts it in there.

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

The threads are in a hash table, and they are quickly found by ID - the 
name doesn't matter; there can even be any number of threads with the 
same name, you wouldn't even know which one you're killing.

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

Who on earth would need that many threads on a desktop system?
Count two threads per window, one for each application. All in all, 
there should rarely be more than 1000 threads active at some point; 
BeOS even has a hard 4096 thread limit (Haiku currently limits the 
number of threads to the same amount).

> 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,
[...]

I would guess our current scheduler will be faster with the normal 
desktop load - at least until a certain number of active threads is 
reached.
Currently, there are usually less than 5 threads in the run queue; but 
you can easily test that with a small application. Only inserting 
threads into the run queue is currently O(n), the rest of the scheduler 
already is O(1).

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