Path: utzoo!attcan!uunet!oddjob!gargoyle!att!lzaz!hutch
From: hutch@lzaz.ATT.COM (R.HUTCHISON)
Newsgroups: comp.unix.wizards
Subject: Re: P/V using SysV semop(2)
Message-ID: <213@lzaz.ATT.COM>
Date: 25 Aug 88 12:45:52 GMT
References: <1001@uwbull.uwbln.UUCP>
Distribution: comp
Organization: AT&T ISL Lincroft NJ USA
Lines: 52

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!hutch