Re: GSoC ticket #1069 (thread scheduler) application

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

That was exactly what I wrote, except that I left out the details, no?
"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."

> I think you misunderstand how this process is working - I will try to
> explain it below :-)

Hmm..

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

Ok... I didn't know that everything gets abstracted by semaphores even
at the kernel level. I believed there could be some mechanism to tell
the kernel what susbsystem a semaphore belongs to, and that we could
use such knowledge.

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

Holy cow. That's embarassingly easier than what I had imagined. Still,
I can see how THIS operation is currently implemented O(n) ***where n
is the number of threads waiting on a given semaphore***. And, that,
too, is something I believe I can turn into O(1).

> The threads are in a hash table,

Thought so, intuitively. That's what makes most sense.

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

I didn't say anything about the name... Did I? If so, ignore that. I
warned you I'd probably say a handful of outrageous stupidities before
attaining enlightenment. ;)

> Who on earth would need that many threads on a desktop system?

Someone willing to play massive-scale The Sims, where every character
is controlled by an independent thread? ;D

Now, really. I'm only getting my bases covered. At least people won't
accuse us of repeating that famous 640kb mistake. ;D

(Note to Sun engineers and the Terascale team at Intel: I'm currently
unemployed. :D :D :D)

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

Okay... Just FWIW, whenever we need to transpass this limit, we may, with ease.

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

I don't think so. I said the prototype scheduler with a demented
bottleneck became TWICE as fast as the O(n) one with as few as 20
threads; *NOT* that 20 threads was the threshold where one starts to
reap the benefits of the O(1) algorithm I designed. Especially now
that I've identified and fixed the bottleneck, it's not even close.

Still, that's indeed a benchmark I'm yet to run. Are you willing to
bet a sixpack that I'll be able to outperform the current scheduler
EVERY time the number of ready threads is larger than 2? ;)

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

So it's in a greater shape than I originally imagined. Anyway, I just
thought it would be better to target a very large value that's easily
downscaled than assume small values and have a hard time upscaling
them when the need arises.

> 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