CODEWITHSUNDEEP
processsynchronizationoperating-system
Akashdeep Saluja
Akashdeep Saluja

Reputation: 3089

Semaphore wait() and signal()

I am going through process synchronization, and facing difficulty in understanding semaphore. So here is my doubt:

the source says that

" Semaphore S is an integer variable that is accessed through standard atomic operations i.e. wait() and signal().

It also provided basic definition of wait() 

wait(Semaphore S)
{
   while S<=0
     ; //no operation
   S--;
}

Definition of signal()

signal(S)
{
   S++;
}

Let the initial value of a semaphore be 1, and say there are two concurrent processes P0 and P1 which are not supposed to perform operations of their critical section simultaneously.

Now say P0 is in its critical section, so the Semaphore S must have value 0, now say P1 wants to enter its critical section so it executes wait(), and in wait() it continuously loops, now to exit from the loop the semaphore value must be incremented, but it may not be possible because according the source, wait() is an atomic operation and can't be interrupted and thus the process P0 can't call signal() in a single processor system.

I want to know, is the understanding i have so far is correct or not. and if correct then how come process P0 call signal() when process P1 is strucked in while loop?

Upvotes: 10

Views: 97900

Answers (6)

G_kuldeep
G_kuldeep

Reputation: 617

I think the top-voted answer is inaccurate!

Operation wait() and signal() must be completely atomic; no two processes can execute wait() or signal() operation simultaneously because they are implemented in kernel and processes in kernel mode can not be preempted.

If several processes attempt a P(S) simultaneously, only one process will be allowed to proceed(non-preemptive kernel that is free of race condition).

for the above implementation to work preemption is necessary (preemptive kernel)

read about the atomicity of semaphore operations http://personal.kent.edu/~rmuhamma/OpSystems/Myos/semaphore.htm https://en.wikibooks.org/wiki/Operating_System_Design/Processes/Semaphores

Upvotes: 7

Itz Me Shefi
Itz Me Shefi

Reputation: 1

i think , when process P1 is strucked in while loop it will be in the wait state.processor will switch over among the process p0 & p1 (context switching) so the priority goes to p0 and it call signal() and then s will be incremented by 1 and p0 exit from the section so process P1 can enter into critical section and can avoid the mutual exclusion

Upvotes: 0

wiio_12
wiio_12

Reputation: 96

I think what the book means for the atomic operation is testing S<=0 to be true as well as S--. Just like testAndset() it mention before.

if both separate operations S<=0 and S-- are atomic but can be interrupt by other process, this method won't work.

imagine two process p0 and p1, if p0 want to enter the critical section and tested S<=0 to be true. and it was interrupted by p1 and tested S<=0 also be true. then both of the process will enter the critical section. And that's wrong.

the actual not atomic operation is inside the while loop, even if the while loop is empty, other process can still interrupt current one when S<=0 tested to be false, which enable other process can continue their work in critical section and release the lock.

however, I think the code from the book can not actually use in OS since I don't know how to make operations S<=0 to be true and S-- together atomic. more possible way to do that is put the S-- inside the while loop like SomeWittyUsername said.

Upvotes: 1

Mert &#199;elikok
Mert &#199;elikok

Reputation: 149

I don't think, keeping an infinite while loop inside the wait() operation is wise. I would go for Stallings' example;

void semWait(semaphore s){
    s.count--;
    if(s.count<0)
        *place this process in s.queue and block this process
}

Upvotes: 2

laksbv
laksbv

Reputation: 689

When a task attempts to acquire a semaphore that is unavailable, the semaphore places the task onto a wait queue and puts the task to sleep.The processor is then free to execute other code.When the semaphore becomes available, one of the tasks on the wait queue is awakened so that it can then acquire the semaphore.

while S<=0 ; //no operation This doesn't mean that the processor running this code. The process/task is blocked until it gets the semaphore.

Upvotes: 0

SomeWittyUsername
SomeWittyUsername

Reputation: 18338

I think it's an inaccuracy in your source. Atomic for the wait() operation means each iteration of it is atomic, meaning S-- is performed without interruption, but the whole operation is interruptible after each completion of S-- inside the while loop.

Upvotes: 5

Related Questions