Re: GSoC ticket #1069 (thread scheduler) application

On 2007-04-11 at 01:40:50 [+0200], André Braga <[email protected]> wrote:
> On 4/10/07, Axel Dörfler <[email protected]> wrote:
[...]
> > 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).

Please note that: (1) There are usually not that many threads waiting for a 
single semaphore anyway. (2) The most likely semaphore release operation is 
with count 1, i.e. only the frontmost thread in the semaphore's queue will be 
woken up. (3) Even in cases were all waiting threads are woken up (e.g. 
delete_sem()) some info for each one needs to be updated, so the operation is 
"O(n)" anyway.

CU, Ingo

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