backwards scheduler?

[Brian Chapman]

bernie at DIALix.UUCP (Bernd Felsche) writes:

>The pipe reader was then started and returned the results in reverse
>order, but in sequence.
>
>Try it:
>	$ /etc/mknod fifo p
>	$ for i in 1 2 3 4 5 6 7 8 9 0 ; do
>	> echo "value $i" >fifo &
>	> done
>	$ # wait a little while for the echo's to stall
>	$ tail -f fifo
>	9
>	8
>	7
>	6
>	5
>	4
>	3
>	2
>	1
>	0
>You'll have to interrupt tail to stop it.
>
>So, without divulging anything about "internals" :-), can somebody
>explain why it happens this way?
>
>bernie

Ya, this happens on my V.3 386 3.2 kernel also.

Here is how it works:

1) Writes to a pipe that no one has open for reading will
   sleep in the open().

So they all go to sleep, probably in order.

2) When process are put to sleep then are linked onto the _front_ of
   the sleep queue.  [there are several hash buckets but the hashing
   is done on the sleep address and all these processes are going
   to have the same sleep address, and thus the same bucket]

So now they are in reverse order.....

3) When the tail (or cat or anything...) opens the pipe (aka fifo) 
   for reading all the processes are wakeup()'ed.	:-)
   More exactly, a wakeup() for that sleep address is issued and
   the wakeup routine goes through the sleep queue and _in_the_order_
   _it_finds_them_ links them onto the front of the run queue.

And now they are in forward order again....

4) Then when it somes time to run someone a routine called disp() [BTW
   why is it called disp()?] is called that finds the highest priority
   process to run.  Is it goes through the list if it finds two processes
   with the same priority it will choose the one that is _later_ on
   the list.

Thus the processes execute in backward order, most of the time.
Assuming that they reached the open() and went to sleep() in order
and assuming that the clock didn't tick (the top of the second)
while they were going to sleep and give the first batch a higher
priority for being asleep a second longer that the others.

I don't think you want to fix this, becasue in more normal situations
I think you would want the priority tie in the run queue to go to the
later (thus possibly older) processes.

I'm sure other people will have comments.	:-)
-- 
Brian Chapman		uunet!sco!chapman
Pay no attention to the man behind the curtain!