panzer@tomato.ucsb.edu (Panzer, John Robert) (11/29/89)
I'm trying to implement a low-overhead shared (read) lock using signal semaphores, and I've come up with a way that will work if several tasks can effectively share ownership of a semaphore. So, my question is: What happens if a task ReleaseSemaphore()'s a semaphore which another task had previously ObtainSemaphore()'d? The semaphore structure has a field for the owner of the semaphore; would changing this field prior to the release be necessary or desirable? Thanks in advance, ========================================================================== | John Panzer | University of California, Santa Barbara | | panzer@cornu.ucsb.edu | SCHOOL OF COMPUTER VIOLENCE | ==========================================================================
valentin@cbmvax.UUCP (Valentin Pepelea) (11/30/89)
In article <3156@hub.UUCP> panzer@cornu.ucsb.edu (Panzer) writes: > >What happens if a task ReleaseSemaphore()'s a semaphore which another >task had previously ObtainSemaphore()'d? The semaphore structure >has a field for the owner of the semaphore; would changing this field >prior to the release be necessary or desirable? These comments are non Amiga specific; the principles of computer science simply don't allow you to release something you don't own. This is true for memory, file handles, locks and certainly semaphores. Tranfer of ownership is tricky and in some cases illegal. What you seem to need is "private semaphores". These semaphores are basically owned by one task which can modify the count, but other tasks can only read the count. You are better off implementing your mutual-exclusion/synchronising mechanism using the Signal() and Wait() functions rather than changing the internal fields in the SignalSemaphore structure while it is being used. Needless to say, if you hack the internal structure, your code will fail on future versions of the operating system. Valentin -- The Goddess of democracy? "The tyrants Name: Valentin Pepelea may distroy a statue, but they cannot Phone: (215) 431-9327 kill a god." UseNet: cbmvax!valentin@uunet.uu.net - Ancient Chinese Proverb Claimer: I not Commodore spokesman be
doug@xdos.UUCP (Doug Merritt) (12/01/89)
In article <8763@cbmvax.UUCP> valentin@cbmvax.UUCP (Valentin Pepelea) writes: >In article <3156@hub.UUCP> panzer@cornu.ucsb.edu (Panzer) writes: >> >>What happens if a task ReleaseSemaphore()'s a semaphore which another >>task had previously ObtainSemaphore()'d? > >These comments are non Amiga specific; the principles of computer science >simply don't allow you to release something you don't own. The "principles of computer science" are not so inflexible; you're making a thinly veiled "appeal to authority" -- a logical fallacy. In point of fact, Panzer is simply trying to redefine "ownership", he is *not* trying to redefine "semaphores". There is absolutely nothing wrong, in theory, with wanting to set up two tasks as a single conceptual entity, and have them share ownership of everything, including semaphores. Naturally such shared semaphores could not then be used to synchronize those two tasks, but in terms of his question, that's irrelevent. After all, there's nothing in the definition of a semaphor that says that ownership is based on tasks. They are frequently used for shared memory parallel processor synchronization, for instance, and in that case the ownership is based on which *cpu* grabbed it. Other non-Amiga-specific examples are a single thread of control which has different sets of subroutines using semaphores to mediate resource access. Or same thing with coroutines. So the question is simply "what defines the owner of a semaphore, and can I muck around with it", and this *is* Amiga specific. >You are better off implementing your mutual-exclusion/synchronising mechanism >using the Signal() and Wait() functions rather than changing the internal >fields in the SignalSemaphore structure while it is being used. >Needless to say, if you hack the internal structure, your code will fail on >future versions of the operating system. This sounds like pretty good advice, specific to the Amiga. Doug -- Doug Merritt {pyramid,apple}!xdos!doug Member, Crusaders for a Better Tomorrow Professional Wildeyed Visionary
jimm@amiga.UUCP (Jim Mackraz) (12/01/89)
In article <3156@hub.UUCP> panzer@cornu.ucsb.edu (Panzer) writes:
)
)I'm trying to implement a low-overhead shared (read) lock using
)signal semaphores, and I've come up with a way that will work
)if several tasks can effectively share ownership of a semaphore.
We have found a way to implement shared-read/exclusive-write style
semaphores using the existing semaphore structure, where existing
callers of ObtainSemaphore magically become "exclusive" in this
extended scheme.
I recommend that you write your own obtainexc/obtainshare/release
routines around an existing signal semaphore structure that is
not used by anybody making the Exec calls.
)So, my question is:
)
)What happens if a task ReleaseSemaphore()'s a semaphore which another
)task had previously ObtainSemaphore()'d?
For one thing, it's not a semaphore anymore if you deny a task the
opportunity to decide when it's good and ready to release it.
)The semaphore structure
)has a field for the owner of the semaphore; would changing this field
)prior to the release be necessary or desirable?
Sounds most unwise. Perhaps it would no longer work in V1.4 when
ObtainSemaphoreShared() does its stuff, since the concept of
"owner" needs to be extended, to -1 or something.
-----------
By the way, there's a standard little puzzle with shared/exclusive
locks which is more convenient to hear from someone than to learn
by experience: When a shared guy holds the lock, and an exclusive
guy is waiting, what do you do when another shared guy bids for
the semaphore?
A) Let him past the exclusive guy and share the lock with the
current guy.
B) Make him wait for the exclusive guy who was there first, after all.
If A), then the exclusive guy could conceivably never get any
time with the semaphore. It's tempting to reject this one, but
don't.
If B), then the presence of a queued exclusive guy voids the concept
of sharing between the guys who want to share. Perhaps there are
situations where this is OK, maybe if you only wanted shared access
for a performance reason.
But if you are sharing semaphores to avoid deadlocks (two tasks
grabbing two semaphores in an arbitrary order works only if the
semaphores (one of them, anyway) is truly shared) B) will not work.
You shall be hanged by the bits until you are dead.
jimm
--
-------------------------------------------------- - opinions by me
"This voice console is a *must*. I press Execute.
`Hello, I know that you've been feeling tired.
I bring you love and deeper understanding.' " -lyrics by Kate Bushpanzer@grape.ucsb.edu (Panzer, John Robert) (12/02/89)
In article <4955@amiga.UUCP> jimm@batgirl.UUCP (Jim Mackraz) writes: >In article <3156@hub.UUCP> panzer@cornu.ucsb.edu (Panzer) writes: >) >)I'm trying to implement a low-overhead shared (read) lock using >)signal semaphores, and I've come up with a way that will work >)if several tasks can effectively share ownership of a semaphore. > >We have found a way to implement shared-read/exclusive-write style >semaphores using the existing semaphore structure, where existing >callers of ObtainSemaphore magically become "exclusive" in this >extended scheme. Great! So when will 1.4 be out? :^) >I recommend that you write your own obtainexc/obtainshare/release >routines around an existing signal semaphore structure that is >not used by anybody making the Exec calls. I was hoping that I wouldn't have to move down to signals. It seems necessary, though. >)What happens if a task ReleaseSemaphore()'s a semaphore which another >)task had previously ObtainSemaphore()'d? > >For one thing, it's not a semaphore anymore if you deny a task the >opportunity to decide when it's good and ready to release it. Well, naturally you'd make sure nobody owned the shared semaphore before it was released to the system. (A usecount would work.) My manuals are unclear about one point: When allocating a signal bit, can I rely on getting whatever bit I want (within the 16 task-reserved bits, of course)? Or do system functions or compiler libraries ever use these task bits? ========================================================================== | John Panzer | University of California, Santa Barbara | | panzer@cornu.ucsb.edu | School of Computer Violence | ==========================================================================