need help solving a problem here

Discussion in 'Computer Science & Culture' started by marc1d3, Mar 6, 2002.

Thread Status:
Not open for further replies.
  1. marc1d3 Registered Member

    I need some help solving this Operating Systems Hwk ...Im about to give up

    Please Register or Log in to view the hidden image!

    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.
    1: while k != i do {c=1; if b[k]=1 then k=i}
    for j=1..N do {if j != i & c[j]=0 then goto 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?

    Please Register or Log in to view the hidden image!

    Please Register or Log in to view the hidden image!

    Last edited: Mar 8, 2002
Thread Status:
Not open for further replies.

Share This Page