From: Kevin S. Van Horn (kevin.vanhorn_at_[hidden])
Date: 2001-10-22 15:19:40
On Mon, 22 Oct 2001, Alexander Terekhov wrote:
> > BTW, the claim that putting a maximum count for a semaphore leads to race
> > conditions is, I believe, only true for "weak" semaphores. For strong
> > semaphores with a maximum count value, the increment/up/signal/V and
> > decrement/down/wait/P operations are symmetric.
> well, you could certainly check whether sem_cnt + sem_signaled <= MAX.
> but what is the purpose of such checking? e.g. it does not count
> threads already unblocked (not counted by sem_waiting/sem_signaled)
> but still on the way out of lock/wait/dec/down/P() call.
Worry about the semantics and logical values first, and the implementation
later. If you bury yourself in the implementation before you have the
semantics straight, you just get yourself confused. The semantics of
a semaphore with a max count is fairly straightforward. In what follows, S is
always the *logical* value of the samphore, which may not be precisely the
same as any single variable (such as sem_cnt) in the implementation:
- P(S): If S == 0, causes the thread to block; if S > 0 and no thread is
blocked on S, decrements S; otherwise, unblocks a thread blocked on S.
(In the last case the blocked threads must have blocked on a V(S) operation,
since S > 0).
- V(S): If S == MAX, causes the thread to block; if S < MAX and no thread is
blocked on S, increments S; otherwise, unblocks a thread blocked on S.
(In the last case the blocked threads must have blocked on a P(S) operation,
since S < MAX.)
- P(S) and V(S) are atomic actions. That is, the external behavior is
as if they happened instantaneously.
The above describes the *logical* behavior. A thread that is on its way out
of its P(S) or V(S) operation (no future P(S) or V(S), or lack thereof, can
prevent it from completing the operation) may, from a logical standpoint, be
considered to be already unblocked. The delay in wending its way out of the
P(S) or V(S) is the same as if a delay got inserted (e.g., due to a context
switch) between between the end of the operation and the execution of the next
statement in the program.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk