P/V using SysV semop(2)

[Daniel R. Levy]

[Dennis L. Mumagh:]
< In article <1001 at uwbull.uwbln.UUCP> ckl at 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 at 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-----|