CSE 430  – Operating Systems – Spring 2009
Assignment: #3

Q1]

The following code fragment is a 2-process "solution" to the critical section problem.

try[i] = 1;
while (incs[j]==1) no-op;
while (turn==j and try[j]==1) no-op;
incs[i] = 1;

critical section

try[i] = 0;
incs[i] = 0;
turn = j;

Does the above "solution" meet all 3 conditions of critical sections? Please explain your answer.

No mutual exclusion.

Example:

[Initial values] turn=0, flag[0]=false, flag[1]=false;
[Running]
P1: if (turn=1) then flag[1]=true;
P1: while (flag[0]) waiting...; // no need to wait.
CONTEXT SWITCH
P0: if (turn==0) then flag[0]=true
P0: while (flag[1]) waiting...// no need to wait.
P0: flag[0]=true;
P0: ENTERING CRITICAL SECTION
CONTEXT SWITCH
P1: flag[1]=true;
P1: ENTERING CRITICAL SECTION

Q2]

Suppose a system has an atomic hardware instruction SHIFT, that does the follows:

SHIFT ( int *A, *B ) {
*B =*A; // ATOMICALLY
 *A = 0
}

A] Implement Dijkstra style semaphores with the shift instruction, that is the semaphores utilize busy waiting (defined in section 6.5 in the 8^th edition of textbook).

int lock;

// Lock is initially set to 1;

// Semphores are defined as integers.

typedef int semaphore;

// Define 2 functions called GetCS and ReleaseCS

GetCS()

{ int temp;

temp = 0;

while (temp = 0) shift (lock, temp); // busy loop

}

ReleaseCS()

{ lock = 1; }

// Now define the semaphore routines.

wait(semaphore S) // or P(S)

{

GetCS()

while (S==0) {

ReleaseCS()

GetCS();

S = S - 1;

ReleaseCS();

}

signal(semaphore S) // or V(S)

{

GetCS();

S = S + 1;

ReleaseCS()

}

B] Implement blocking semaphores using the shift instructions. (defined in section 6..5.2 in 8^th edition of book).

To use the blocking routines... use the GetCS and ReleaseCS defined in A.
 
//define a semaphore as
typedef struct {
 int count;
 PCBQueue Q
} semaphore;
 
wait(semaphore S) { // or P(S)
 GetCS()
 S.count--;
 if (S.count<0) {
 move current PCB to S.Q;
 ReleaseCS();
 block();
 }
}
 
signal(semaphore S) // or V(S)
{
 GetCS();
 S.count++;
 if (S.Count<=0) {
 move a PCB from S.Q to ready Q; //wakeup
 }
 ReleaseCS();
}

Q3]

There are 4 processes, executing concurrently. Process P0 is in an infinite loop, incrementing the value of the variable x (x is initialized to 0). P0 is the only process that changes the value of x.

The rest of the processes Pi (1<= i <=3) monitor the value of x. Whenever x reaches a value such that it is divisible by i, Pi prints the value of x. For example, P3 will print the sequence 3 6 9 12 ….. as the value of x reaches 3, 6, 9, 12 and so on.

Write the code for all the 4 processes using semaphores. Note that P1 - P3 should be identical.

 // no answer provided, figure this one out, it is straightforward

Q4]

A synchronization mechanism consists of 2 atomic routines, ENQ(r) and DEQ(r). "r" is a resource variable that has two fields, inuse (boolean) and queue (a queue) which is a queue of processes waiting to acquire the resource. The definitions of ENQ and DEQ are:

 ENQ(r) : if (r.inuse==1) then begin
                insert current process in r.queue
                block
              end
           else  r.inuse = 1;

 DEQ(r) : if r.queue == nil then inuse = false
           else delete a process from r.queue and activate it.

Construct an implementation of ENQ/DEQ using semaphores. You can use other variables, etc that you need, but no other atomic code or synchronization constructs other than P or V can be used.

The resource is a Semaphore initialized to 1

P(r) = Enq(r)

V(r) = DEQ(r)

Q5]

Do the reverse of Q3, that is implement Semaphores using ENQ/DEQ.

Semaphore is a structure containing a count and two queues mutex and block.

InitSem(s, val) { //important routine
s.count = val;
ENQ(s.block) // lock the block resource
}

P(Sem) {
ENQ(sem.mutex); // get critical section
sem.count--;
if (sem.count < 0) {
DEQ(sem.mutex);
ENQ(sem.block);} // block the caller
else DEQ(sem.mutex);
}

V(sem) {
ENQ(sem.mutex);
sem.count ++;
if (sem.count<=0) DEQ(sem.block); // unblock a waiting process
DEQ(Sem.mutex);
}