We assume that there are 2 atomic instructions cr1 and cr2 in the critical secti

Question

We assume that there are 2 atomic instructions cr1 and cr2 in the critical section, and 2 atomic instructions nc1 and nc2 in the non-critical section. Also note there are P (occupied) and V (occupied) acting on the semaphore occupied, with the value set to 1. For simplicity, we will just write P and V to stand for P(occupied) and V(occupied).

Valid sequence of instructions. We know the instruction sequence cr1, cr2, V, nc1, nc2 is valid; cr2, cr1 is invalid in any case; cr1, cr2, V, P, cr1, cr2 is invalid for one thread (since we need to have nc1 and ncc2 after V); it is valid for two threads with semaphore count occupied = 1 (occupied(1)) denoted as we have cr1 (0), cr2(0), V(0), P(1), cr1(1), cr2(1) (cr1(0) means we are running cr1 in thread 0, V(0) means we are running V(occupied) in thread 0, and P(1) means we now switch to thread 1 and run P(occupied), cr1 (1) means we run cr1 in thread 1.

(a) Assume that there are 2 threads and semaphore count is 1, is it possible to have an instruction sequence cr1, cr2, cr1, cr2? Explain! You can assume P(0) and P(1) had been executed in thread 0 and thread 1. Denote cr1 by cr1 (0), cr1 (1) as necessary to explain. OS is assumed to be preemptive, meaning it can switch from one thread to another thread any time (but you have to complete atomic instructions).

(b) Assume that there are 2 threads and semaphore count can be more than 1, is it possible to have an instruction sequence cr1, cr2, cr1, cr2? Explain!

(c) Is it possible to have a sequence of cr1, cr2, cr2? Explain! Assume you can have any number of threads and also the semaphore count can be more than 1.

(d) Is it possible to have a sequence of cr1, cr1, cr1 assuming two threads only but semaphore count is 10? Explain!

(e) Is it possible to have a sequence of cr1, cr1, cr1 assuming three threads but semaphore count is 1? Explain!

1 System 3 create sema pho re and nitial i value 1 4 Semaphore occupied new Semaphore C1 start Threads CD ini ti a I ize and launch both threads Thread I ILO void main C 11 while done L3 PC occupied wait 14 critical Section code 16 VC occupied signal 18 19 Code outside critica l section end while 22 Thread TX

Explanation / Answer

a) The instruction sequence cr1,cr2,cr1,cr2 is not valid. The thread 1 enters the critical section and executes cr1 and cr2. However since the semaphore count is 1 (as thread 1 will have executed P(0)) it will need to execute V(0) before any other thread can enter into the critical section. Hence, the correct instruction sequence can be cr1,cr2,V,cr1,cr2.

b) Yes. In this case the instruction sequence is valid. Since semaphore count is more than 1, thread 1 can execute cr1 and cr2, then without waiting thread 2 can also execute cr1 and cr2. Since the semaphore count is more than 1, thread 2 need not have to wait for the V operation of thread 1. Since the OS is preemptive, after executing cr1 and cr2 of thread 1 it can immediately switch to thread 2 and execute cr1 and cr2.

c) Yes this sequence is also possible. If we have more than one thread, say thread 1 executes cr1(0). Now, since semaphore count is more than 1 and the OS is pre-emptive, it can switch to another thread and execute cr2(1) assuming cr1(1) was executed earlier at some point of time. The OS can then swich back to thread 1 and execute cr2(0) and hence this instruction sequence is valid

d) No, this sequence is not valid if there are only 2 threads. Say, thread 1 and thread 2 both executes cr1. Before the 3rd execution of cr1, either of them has to execute cr2. It is not possible for either of the threads to skip cr2 and execute cr1 again.

e) No, this sequence is not valid. Since semaphore 1, only 1 thread can execute in the critical section. If thread 1 is executing in the critical section, it has to execute cr1, cr2 and V before any other thread can enter into the critical section and execute cr1.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.