bernie@DIALix.UUCP (Bernd Felsche) (09/27/90)
I observed some strange behaviour with the scheduler on our System V/68 (version V.3<something>) today: A named pipe was created and 10 processes kicked off to write to the pipe. 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. The exact start point of the sequence varies, depending on which waiting echo gets unblocked first. However, the sequence is reversed from the order in which the processes were started. (You can add a sleep after each echo if you like) So, without divulging anything about "internals" :-), can somebody explain why it happens this way? bernie
chapman (Brian Chapman) (10/10/90)
bernie@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!
npl@cbnewsi.att.com (nickolas.landsberg) (10/11/90)
In article <8108@scolex.sco.COM>, chapman (Brian Chapman) writes: > 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 I believe that disp() was originally called the dispatcher, but that portion of memory is so old, it's stale. Nick Landsberg