I need some help solving this Operating Systems Hwk ...Im about to give up
I need some help from the smarter bunch of programming experts on a problem Ive been boggled over...
A system has N processes operating concurrently at unknown and uncontrolled relative speeds. Occasionally each one wants to update a shared file. The update procedure is a critical section of code. A programmer has proposed the protocol shown below.
b=0
1: while k != i do {c=1; if b[k]=1 then k=i}
c=0
for j=1..N do {if j != i & c[j]=0 then goto 1}
CRITICAL SECTION
c=1
b=1
In this protocol the bit vectors b and c and integer k are shared. Index i is the process identifier of the process executing the code. Initially all processes are outside the protocol, all b and c are 1, and k=1.
The interpretations of the shared variables are as follows. The bit b=0 indicates that process i is somewhere inside the protocol. The integer k points to one of the processes that are looping while trying to get into the critical section. The bit c=0 indicates that process i got k to point to itself and will enter the critical section as long as no other looping process changes k.
· (a) Is this protocol safe? (That is, only one process can be inside the critical section at once.)
· (b) Is this protocol starvation-free? (That is, no process may wind up waiting forever to enter the critical section.)
· (c) This protocol assumes that memory accesses to the shared variables are indivisible -- that is, the memory prevents two processes from attempting to read or write the same location in the same memory cycle. What might go wrong if this is not so?
·
I need some help from the smarter bunch of programming experts on a problem Ive been boggled over...A system has N processes operating concurrently at unknown and uncontrolled relative speeds. Occasionally each one wants to update a shared file. The update procedure is a critical section of code. A programmer has proposed the protocol shown below.
b=0
1: while k != i do {c=1; if b[k]=1 then k=i}
c=0
for j=1..N do {if j != i & c[j]=0 then goto 1}
CRITICAL SECTION
c=1
b=1
In this protocol the bit vectors b and c and integer k are shared. Index i is the process identifier of the process executing the code. Initially all processes are outside the protocol, all b and c are 1, and k=1.
The interpretations of the shared variables are as follows. The bit b=0 indicates that process i is somewhere inside the protocol. The integer k points to one of the processes that are looping while trying to get into the critical section. The bit c=0 indicates that process i got k to point to itself and will enter the critical section as long as no other looping process changes k.
· (a) Is this protocol safe? (That is, only one process can be inside the critical section at once.)
· (b) Is this protocol starvation-free? (That is, no process may wind up waiting forever to enter the critical section.)
· (c) This protocol assumes that memory accesses to the shared variables are indivisible -- that is, the memory prevents two processes from attempting to read or write the same location in the same memory cycle. What might go wrong if this is not so?
·
Last edited: