Q4. (a) You need to share one resource X between three threads P, Q and R. Write
ID: 3704286 • Letter: Q
Question
Q4. (a) You need to share one resource X between three threads P, Q and R. Write the critical section code for each of the threads and use semaphores to guarantee exclusive access by just one of the threads at a time to the resource X (which can be accessed by just calling “X()”).
(b) Rewrite the critical section code of part (a) to allow at most two of the three threads to access the resource at the same time. (5 pts)
(c) Is your implementation in the previous two parts of this question susceptible to (i) deadlock, (ii) starvation and/or (iii) priority inversion. Explain. (15 pts)
(Please explain as thoroughly as possible)
Explanation / Answer
a) Initialize semaphore to 1 to allow only one thread to enter into critical section. A thread can enter into CS only if s=1 otherwise wait. When thread enters into CS, decrement semaphore and while exiting CS increment semaphore.
Example: thread P tries to acess X(enter into CS) and initially s=1 then P(s) will decrement s to 0 and P will enter into CS. Now if Q/R tries to access resource X and executes P(s) then will stuck into while loop as s is equal to 0. Now when P finishes, it will execute V(s) and will increment sempahore back to 1. Now one of the thread among Q & R will exit waiting loop and enter into CS. This process will ensure only one thread is allowed in critical section at a time.
s = 1;
void employee(){
while(true){
P(s);
X(); // CS
V(s);
}
}
P(semaphore s){
while(s == 0);
s--;
}
V(semaphore s){
s++;
}
b) Modify above implementation by initializing s=2.
s = 2;
void employee(){
while(true){
P(s);
X(); // CS
V(s);
}
}
P(semaphore s){
while(s == 0);
s--;
}
V(semaphore s){
s++;
}
c)
Deadlock: Yes, if two threads are in CS for resources X & some other resource Y and require access to Y & X respectively then both will not leave CS and will wait indefinitely.
Starvation: Yes, if a thread take really long time then it may starve a waiting thread since there is no preemption of thread from CS
Priority inversion: Yes, if a lower priority thread enters into CS first then there is a possibility that a higher priority thread will enter into wait cycle to wait for lower priority thread.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.