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