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

    Messages:
    1
    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.
    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?
    ·

    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