2
$\begingroup$

A semaphore is a variable that, apart from initialization is accessed through only two standard atomic operations wait(s) and signal(s).

wait(S){
    while S <= 0
    ; //no-op
    s--;
}

signal(S){
    s++;
}

The function $wait()$ is an atomic operation which means that either it is executed in its entirety or it is not executed. Let us suppose that we call $wait(a)$ upon a semaphore variable $a$. And let us assume the initial value is $0$. This means the criterion for the while loop is satisfied and it goes into a while loop. It can only come out of the while loop if the value of the semaphore $a$ is $\gt$ 0. This can occur, if some process sets the value of $a$ to $1$ by calling $signal(a)$. But since $wait()$ and $signal()$ are atomic operations and since we have already entered into the busy waiting while loop in $wait()$ when the value of $a$ was $0$, isn't this loop supposed to run indefinitely since its atomic? How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?

$\endgroup$

3 Answers 3

2
$\begingroup$

Your assertion that wait() and signal() are atomic is incorrect. The increment/decrement to s within the functions (s++, s--), are what's atomic.

That being said, what you have given here is only one possible implementation of a semaphore. An OS may or may not implement semaphores in this way, and they probably will choose a more efficient implementation. What's more important is to grasp the semantics of a semaphore, which you seem to understand correctly.

$\endgroup$
1
$\begingroup$

Semaphore do not work the way you have described. They are more like shared variables. So even inside the loop S can get modifies and the first process will come out of the loop. Note it is not same as while(1){}; .

$\endgroup$
0
$\begingroup$

The definition of wait() as given by you is very simplest. The checking of value of S (S<=0) and its possible modification (S--) must be performed without interruption. If you write wait() function as you have written here then, when a process has found that S>0 and it is going to modify S (S--) then it can stop between checking value of S (S<=0) and its possible modification (S--). If this happens mutual exclusion will not be satisfied. Also, if a process finds that S<=0, it has to simply busy wait and other process should be allowed to enter signal() and increment S. You will need to add few lines in your code to handle such situations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.