OPERATING
SYSTEM: CSET209
Semaphores
OUTLINE Classical synchronization problem
Producer consumer problem
SEMAPHORES
A semaphore S – integer
variable which is used by
various processes in a mutual
exclusive manner to achieve
synchronization.
The improper usage of
semaphore will also give the
improper results.
SEMAPHORES
Can only be accessed via two indivisible (atomic) operations
wait() and signal()
Originally called P() and V(). Wait
Definition of the wait() operation The wait operation decrements
wait(S) { the value of its argument S, if
while (S <= 0) it is positive. If S is negative or
; // busy wait zero, then no operation is
S--;
performed.
}
Definition of the signal() operation Signal
signal(S) { The signal operation
S++; increments the value of its
} argument S.
SEMAPHORES
COUNTING SEMAPHORES
BINARY SEMAPHORES
S
S
PRACTICE PROBLEMS BASED ON COUNTING SEMAPHORES IN OS-
A counting semaphore S is initialized to 6. How many successful down operations can be
performed?
Solution-
Six
5, 4, 3, 2, 1, 0
S
PRACTICE PROBLEMS BASED ON COUNTING SEMAPHORES IN OS-
A counting semaphore S is initialized to 10. Then, 6 P operations and 4 V operations are
performed on S. What is the final value of S?
Solution-
We know-
•P operation also called as wait operation decrements the value of semaphore variable by 1.
•V operation also called as signal operation increments the value of semaphore variable by 1.
Thus,
Final value of semaphore variable S
= 10 – (6 x 1) + (4 x 1)
= 10 – 6 + 4
=8
S
PRACTICE PROBLEMS BASED ON COUNTING SEMAPHORES IN OS-
A counting semaphore S is initialized to 7. Then, 20 P operations and 15 V operations are performed on S.
What is the final value of S?
Solution-
We know-
•P operation also called as wait operation decrements the value of semaphore variable by 1.
•V operation also called as signal operation increments the value of semaphore variable by 1.
Thus,
Final value of semaphore variable S
= 7 – (20 x 1) + (15 x 1)
= 7 – 20 + 15
=2
S
PRACTICE PROBLEMS BASED ON COUNTING SEMAPHORES IN OS-
A counting semaphore S is initialized to 10. Then, 12 P operations and ‘X’ V operations are performed on S.
if the final value of S is 7, ‘X’ will be?
Solution-
We know-
•P operation also called as wait operation decrements the value of semaphore variable by 1.
•V operation also called as signal operation increments the value of semaphore variable by 1.
Thus,
7 = 10 – 12 + X
7=-2+X
X=9
S
PRACTICE PROBLEMS BASED ON BINARY SEMAPHORES IN OS-
SOLUTION
Suppose We start with process P1, means P1 enters Critical section by performing
a DOWN on semaphore mutex. At this point MUTUX=0, Now P10 executes and
performs an UP on mutex and enters Critical section. At this point MUTUX=1,
Now, Any one process out of p2….p9 enters critical section by performing a
DOWN on binary semaphore [Link], mutux=0 and there is no way we
could perform an UP on binary semaphore without allowing any process to leave
Critical Section.
So, Maximum number of processes which are allowed to enter critical section =3
(two out of P1…P9 and P10).
WHAT IS THE OUTPUT??
S
PRACTICE PROBLEMS BASED ON BINARY SEMAPHORES IN OS-
PRODUCER – CONSUMER PROBLEM
1. Producer produces and stores in buffer, Consumer consumes from buffer.
2. Required synchronization when:
1. Producer produces, but buffer is full.
2. Consumer consumes, but buffer is empty.
3. Also known as bounded buffer problem.
PRODUCER – CONSUMER WITH SEMAPHORES
1. Two Semaphores, full and empty are used.
PRODUCER – CONSUMER WITH SEMAPHORES
N=6
full = 4
empty = 2
PRODUCER – CONSUMER WITH SEMAPHORES
N=6
full = 4
empty = 1
PRODUCER – CONSUMER WITH SEMAPHORES
N=6
full = 5
empty = 1
PRODUCER – CONSUMER WITH SEMAPHORES
N=6
full = 5
empty = 1
PRODUCER – CONSUMER WITH SEMAPHORES
N=6
full = 4
empty = 1
PRODUCER – CONSUMER WITH SEMAPHORES
N=6
full = 4
empty = 1
PRODUCER – CONSUMER WITH SEMAPHORES
N=6
full = 4
empty = 2
PRODUCER – CONSUMER WITH SEMAPHORES
PRODUCER – CONSUMER WITH SEMAPHORES
PRODUCER – CONSUMER WITH SEMAPHORES
PRODUCER – CONSUMER WITH SEMAPHORES
PRODUCER – CONSUMER WITH SEMAPHORES
PRODUCER – CONSUMER WITH SEMAPHORES
down(mutex)
down(mutex)
up(mutex)
up(mutex)
Question: What happens if we interchange wait(empty) and wait(mutex) in the producer
code?
do{
//produce an item HINT: check when buffer is full.
wait(empty); wait(mutex);
wait(mutex); wait(empty);
//place in buffer
signal(mutex);
signal(full);
}while(true)
Question: What happens if we interchange signal(full) and signal(mutex) in the producer
code?
do{
//produce an item HINT: check when buffer is empty and
full.
wait(empty);
wait(mutex);
//place in buffer
signal(mutex); Signal (full);
signal(full); signal(mutex);
}while(true)
THANK YOU
?