CSE 330 – Operating Systems – Fall 2016
HW2 Solution
Q1]
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, semaphores
which utilize busy waiting.
B] Implement blocking semaphores using the shift instructions.
Q2]
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; also Pi determines whether x is to be printed, and this decision is not made
by P0.
Q3]
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.
Let the Resource be a Semaphore initialized to 1
So Enq(r) = P(r) and DEQ(r) = V(r)
Q4]
Do the reverse of Q3, that is implement Semaphores using ENQ/DEQ.