OS system's help

[dee m.]

I've been trying to seek help regarding this OS
problem that involves threads.  For some reason I am
not really sure whether it can be determined as being
safe or not given the criteria of the protocol being
asked.  Can you help?


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[i]=0 
1: while k != i do {c[i]=1; if b[k]=1 then k=i} 
c[i]=0 
for j=1..N do {if j != i & c[j]=0 then goto 1} 
CRITICAL SECTION 
c[i]=1 
b[i]=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[i] and c[i] are 1, and
k=1. 
The interpretations of the shared variables are as
follows. The bit b[i]=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[i]=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? 
· (d) What is the relation of this protocol to
Dijkstra's protocol as discussed in the "Mutex" slides
in Art of Operating Systems? 


__________________________________________________
Do You Yahoo!?
Try FREE Yahoo! Mail - the world's greatest free email!
http://mail.yahoo.com/