P/V using SysV semop(2)

[Dennis L. Mumaugh]

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.

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 at arpa.att.com