ckl@uwbln.UUCP (Christoph Kuenkel) (08/24/88)
I just tried to implement Disjkstra's P/V semaphore operations using
system V's semops. what i found on three different SysV R.2 ports was
that mutual exclusion was ok but the order of entrance into the critical
section enclosed into P/V was ``by random'' (probably by order of kernel
process slot, which is roughly equivalent to ``by random'').
I implemented it using an array of 1 semaphore and a value of -1 for
sem_op.
As far as i understand, the documentations does not specify anything at all.
i cant believe it. is it impossible to implement P/V without starvation?
--
Christoph Kuenkel/UniWare GmbH Kantstr. 152, 1000 Berlin 12, West Germany
ck@tub.BITNET ckl@uwbln {unido,tmpmbx,tub}!uwbln!cklchris@mimsy.UUCP (Chris Torek) (08/25/88)
In article <1001@uwbull.uwbln.UUCP> ckl@uwbln.UUCP (Christoph Kuenkel) writes: >... is it impossible to implement P/V without starvation? Yes. At least one SysV implementation (probably two; I doubt yours is the same as the other I heard of) will, when asked to switch among three processes A,B,C, run in the order A,B,A,B,A,B,A,B.... This problem does not occur when using 4.3BSD's file locking primitive to implement semaphores. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
hutch@lzaz.ATT.COM (R.HUTCHISON) (08/25/88)
From article <1001@uwbull.uwbln.UUCP>, by ckl@uwbln.UUCP (Christoph Kuenkel):
] I just tried to implement Disjkstra's P/V semaphore operations using
] system V's semops. what i found on three different SysV R.2 ports was
] that mutual exclusion was ok but the order of entrance into the critical
] section enclosed into P/V was ``by random'' (probably by order of kernel
] process slot, which is roughly equivalent to ``by random'').
]
The order is predictable - it is Last-In-First-Out. This is because
processes waiting for semaphores move back and forth between the run
queue and sleep queues each time there is a possibility that a process
can be awakened. The only problem is that these sleep queues are
actually stacks (add to the front, remove from the front) and not
queues at all. All processes blocked on a semaphore sleep at the same
priority and are all reawakened at the same time. So, the order of
the list is reversed when it passes through the (sleep) stack.
*** WARNING: KLUDGE FOLLOWING ***
Kludge to get it to work: When requesting a resource, subtract 2 from
its value (the value of the semaphore will be between 0 and 2); when
releasing a resource add 1 twice. This will toss the processes from
the sleep queue to the run queue (at the end of the first system
call), cause all of them to go back to the sleep queue (they all
wanted 2 - there was only 1) and then finally back onto the run queue
after the second call effectively maintaining the original order.
I know this will be very slow but as they say, "Bad breath is better
than no breath."
A better way to fix this is to make the sleep queue hash table a table
of structures each with pointers to the first and last
proc table entries of the sleep "queue" instead of just one entry
pointing to the start of the list. Always add to one end, take off of the
other end. Simple, huh? Another solution would be to always traverse
the hash list and add to its end - this would save memory (about 1K) but
waste time.
By the way, I reported this problem back with SVR0 using "trenter."
It looks like the problem is still there.
] I implemented it using an array of 1 semaphore and a value of -1 for
] sem_op.
]
] As far as i understand, the documentations does not specify anything at all.
] i cant believe it. is it impossible to implement P/V without starvation?
] --
] Christoph Kuenkel/UniWare GmbH Kantstr. 152, 1000 Berlin 12, West Germany
] ck@tub.BITNET ckl@uwbln {unido,tmpmbx,tub}!uwbln!ckl
Hope this helps;
Bob Hutchison att!lzaz!hutchvandys@hpisoa1.HP.COM (Andrew Valencia) (08/25/88)
/ hpisoa1:comp.unix.wizards / ckl@uwbln.UUCP (Christoph Kuenkel) / 6:45 am Aug 24, 1988 / >As far as i understand, the documentations does not specify anything at all. >i cant believe it. is it impossible to implement P/V without starvation? On many UNICES, the sleep queue isn't FIFO, unlike the run queue. This can result in real oddities of performance when just depending on sleep/wakeup for fairness (which the Sys V semaphore code I saw did). I believe that 4.3 has changed the sleep queues to FIFO, as have I for HP-UX. Surprisingly, nothing broke for either of us. Lacking this, an obvious and simple technique is to use a semaphore server process, accessed via messages. This process can then implement whatever policies he sees fit. Of course, if his policies include attributes like priority, he might have fun trying to figure out the true priorities of his client processes when faced with message forgeries. It goes. Andy
vandys@hpisoa1.HP.COM (Andrew Valencia) (08/27/88)
/ hpisoa1:comp.unix.wizards / hutch@lzaz.ATT.COM (R.HUTCHISON) / 5:45 am Aug 25, 1988 / >The order is predictable - it is Last-In-First-Out. This is because >processes waiting for semaphores move back and forth between the run >queue and sleep queues each time there is a possibility that a process >can be awakened. I don't know about your implementation, but on ours user processes change priority as they consume (and over-consume :->) CPU and then fall idle. So when a batch of processes move from the sleep queue to the run queue, there's no simple way (from a user's perspective) to say who's going to run. An area to be careful in is real-time scheduling (if your kernel has it). Our system design philosophy says that real-time priority processes *should* be able to starve lower priority processes when competing for these semaphores. A simple FIFO queue for the semaphore would violate this; multiple queues (one for each priority level) is a bit much. Using priorities and FIFO sleep & run queues makes it work out pretty well. Andy
hutch@lzaz.ATT.COM (R.HUTCHISON) (08/29/88)
From article <2200029@hpisoa1.HP.COM>, by vandys@hpisoa1.HP.COM (Andrew Valencia): ] / hpisoa1:comp.unix.wizards / hutch@lzaz.ATT.COM (R.HUTCHISON) / 5:45 am Aug 25, 1988 / ]>The order is predictable - it is Last-In-First-Out. This is because ]>processes waiting for semaphores move back and forth between the run ]>queue and sleep queues each time there is a possibility that a process ]>can be awakened. ] ] I don't know about your implementation, but on ours user processes change ] priority as they consume (and over-consume :->) CPU and then fall idle. So ] when a batch of processes move from the sleep queue to the run queue, there's ] no simple way (from a user's perspective) to say who's going to run. ] ... ] Andy Ah, but all processes sleeping awaiting a semaphore "unblock" sleep with the same priority (PSEMN)- the CPU consumption factor (p_cpu) is not taken into consideration when assigning priorities to sleeping processes. Processes are removed from the run queue using the following rules: 1) select the process with the highest priority 2) if there is a tie, select the one nearest the end of the queue All processes sleeping on a semaphore sleep at priority PSEMN. WHen they are put on the run queue, they will have the same priority. In this case, their ordering is important. Bob Hutchison att!lzaz!hutch
vandys@hpisoa1.HP.COM (Andrew Valencia) (08/30/88)
>Ah, but all processes sleeping awaiting a semaphore "unblock" sleep with the >same priority (PSEMN)- the CPU consumption factor (p_cpu) is not taken into >consideration when assigning priorities to sleeping processes. Processes >are removed from the run queue using the following rules: You're right; p->p_pri is used to choose the run queue (unless the process is real-time, but that's another story). Since it's set in sleep(), the priority used to select a run queue is unchanging. However, our VM system (both paging and swapping sections) takes a bigger picture of the process's behaviour. If it isn't involved (for instance, on an empty system), then you're quite likely to see something approaching FIFO. Once it gets involved, all bets are off, and the more starved processes are likely to start catching up. Andy
dlm@cuuxb.ATT.COM (Dennis L. Mumaugh) (09/01/88)
In article <1001@uwbull.uwbln.UUCP> ckl@uwbln.UUCP (Christoph Kuenkel) writes:
I just tried to implement Disjkstra's P/V semaphore
operations using system V's semops. what i found on three
different SysV R.2 ports was that mutual exclusion was ok
but the order of entrance into the critical section
enclosed into P/V was ``by random'' (probably by order of
kernel process slot, which is roughly equivalent to ``by
random'').
I implemented it using an array of 1 semaphore and a
value of -1 for sem_op.
As far as i understand, the documentations does not
specify anything at all. i cant believe it. is it
impossible to implement P/V without starvation?
And Chris Torek in <13204@mimsy.UUCP> comments:
Yes. At least one SysV implementation (probably two; I
doubt yours is the same as the other I heard of) will,
when asked to switch among three processes A,B,C, run in
the order A,B,A,B,A,B,A,B....
This problem does not occur when using 4.3BSD's file
locking primitive to implement semaphores.
And Bob Hutchison (att!lzaz!hutch) comments:
By the way, I reported this problem back with SVR0 using
"trenter." It looks like the problem is still there.
As the Tier Support person last involved with System V Semaphores
I have a couple of comments:
1). I doubt there is a really safe way to implement P/V with
System V Semaphores. Our semphores are more general than P/V but
suffer from the lack of consistency in their behavior. This
happens as other explained because the unblocking of a semaphore
results in processes waiting for the semaphore to be placed on
the run queue and then become subject to the vagaries of the UNIX
scheduler. As Chris Torek alluded to (above) it is possible for
the scheduler to thrash between two processes because the run
queue is a FIFO and not a LIFO. Many years ago I changed our PWB
system to add runable processes to the end of the queue. (Cost
one extra trip through the run queue or an extra pointer plus
updating code).
2). Kluges might work but the "random ness" of the scheduler and
the possibility of other non-related processes getting involved
still leave a window of vulnerability. One customer used two
semaphores to get good behavior and another use semaphores and
shared memory.
3). This problem has been MR'd to the developers with a
high-priority and is planned to be "fixed" in the next release.
I have no information on whether they will make semaphores FIFO
instead of quasi-LIFO or not. One could argue that the current
behavior (counter intutitive as it is) should be maintained
because applications programs may rely on it.
Thus we'll have to wait for the next release to see. Really,
solving the problem is rather difficult as one must either have a
private queue for each semaphore or change the scheduler or
something else and the developers get nervous when you talk about
all the changes and they start muttering about "side effects".
--
=Dennis L. Mumaugh
Tier 4 UNIX Support
Lisle, IL ...!{att,lll-crg}!cuuxb!dlm OR cuuxb!dlm@arpa.att.comlevy@ttrdc.UUCP (Daniel R. Levy) (09/04/88)
[Dennis L. Mumagh:] < In article <1001@uwbull.uwbln.UUCP> ckl@uwbln.UUCP (Christoph Kuenkel) writes: < I just tried to implement Disjkstra's P/V semaphore < operations using system V's semops. what i found on three < different SysV R.2 ports was that mutual exclusion was ok < but the order of entrance into the critical section < enclosed into P/V was ``by random'' (probably by order of < kernel process slot, which is roughly equivalent to ``by < random''). < I implemented it using an array of 1 semaphore and a < value of -1 for sem_op. < As far as i understand, the documentations does not < specify anything at all. i cant believe it. is it < impossible to implement P/V without starvation? < And Chris Torek in <13204@mimsy.UUCP> comments: < Yes. At least one SysV implementation (probably two; I < doubt yours is the same as the other I heard of) will, < when asked to switch among three processes A,B,C, run in < the order A,B,A,B,A,B,A,B.... < This problem does not occur when using 4.3BSD's file < locking primitive to implement semaphores. < And Bob Hutchison (att!lzaz!hutch) comments: < By the way, I reported this problem back with SVR0 using < "trenter." It looks like the problem is still there. According to my understanding of process coordination (from a senior/graduate level O.S. class at Northwestern, using the text _Operating_Systems_Advanced_ _Concepts_, by Maekawa, Oldehoeft, and Oldehoeft, published by Benjamin/Cummings in Menlo Park, California and elsewhere) naked P/V never did guarantee anything more than mutual exclusion; there is no guarantee of freedom from starvation. Thus, it can be argued that semctl(2) DOES allow a definitionally (is that a word? :-) correct implementation of P/V, though it has starvation problems in naive usage. There exist more elaborate process coordination algorithms, based on P/V or other mechanisms which in turn can be implemented with P/V, which can enforce both mutual exclusion and some defined measure of precedence. Maekawa et. al. give examples for many of these. Since the original poster didn't say what he was trying to do with his coordinated processes, I wouldn't know what algorithm to suggest. (How can I get to system "uwbln"? The original article has disappeared from this system, so I don't have a path.) -- |------------Dan Levy------------| THE OPINIONS EXPRESSED HEREIN ARE MINE ONLY | Bell Labs Area 61 (R.I.P., TTY)| AND ARE NOT TO BE IMPUTED TO AT&T. | Skokie, Illinois | |-----Path: att!ttbcad!levy-----|