Two concurrent processes P1 and P2 use four shared resources R1, R2, R3 and…
2005
Two concurrent processes P1 and P2 use four shared resources R1, R2, R3 and R4, as shown below.
Both processes are started at the same time, and each resource can be accessed by only one process at a time The following scheduling constraints exist between the access of resources by the processes:
P2 must complete use of R1 before P1 gets access to R1
P1 must complete use of R2 before P2 gets access to R2.
P2 must complete use of R3 before P1 gets access to R3.
P1 must complete use of R4 before P2 gets access to R4.
There are no other scheduling constraints between the processes. If only binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed?
Answer: B. 2 — Answer: 2 Reason: The four constraints fall into two independent directions: P2 must precede P1 for resources R1 and R3. P1 must precede P2 for resources R2…
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 13 students.
Show answer & explanation
Correct answer: B
Answer: 2
Reason: The four constraints fall into two independent directions:
P2 must precede P1 for resources R1 and R3.
P1 must precede P2 for resources R2 and R4.
A single binary semaphore can be reused to enforce multiple constraints that have the same direction by placing wait and signal calls at each relevant point. Therefore two semaphores (one per direction) are sufficient and minimal.
Construction (one correct implementation):
Create semaphore S_p2_before_p1 initialized to 0. Before P1 uses R1 and before P1 uses R3, P1 performs wait(S_p2_before_p1). After P2 finishes using R1 and after P2 finishes using R3, P2 performs signal(S_p2_before_p1).
Create semaphore S_p1_before_p2 initialized to 0. Before P2 uses R2 and before P2 uses R4, P2 performs wait(S_p1_before_p2). After P1 finishes using R2 and after P1 finishes using R4, P1 performs signal(S_p1_before_p2).
Notes: Each semaphore is binary but can be signaled multiple times and waited on multiple times at different points in the execution. This groups same-direction constraints onto one semaphore each, yielding the minimum of two binary semaphores.
A video solution is available for this question — log in and enroll to watch it.