CMSC 412

NOTE 15

March 17, 1999

East-West Bridge Problem

1. Problem statement

An east-west bridge is shared between east cars and west cars. Each car is a process. We want the following to hold:
  1. Multiple cars: More than one car can on the bridge as long as they are all going in the same direction (east or west).

  2. No starvation: A car that attempts to cross the bridge eventually does so provided no car stays forever in the bridge.

  3. No busy waiting.
This problem is like the readers-writers problem except that multiple writes can be ongoing at the same time.

1. Solution attempt 1

Proceeding along the lines of our attempt to solve the readers-writers problem, we have the following: 
Semaphore bFree initially 1;   // 1 if no car is on the bridge
Semaphore waitE initially 1;   // 0 if east-car waiting on dir
Semaphore waitW initially 1;   // 0 if west-car waiting on dir

integer numE initially 0;   // number of east-cars waiting or in bridge
integer numW initially 0;   // number of west-cars waiting or in bridge


StartE( ) {  // executed by a east-car to enter bridge
  P( waitE );
  nEast := nEast + 1;
  if nEast = 1 then { P( bFree ) };
  V( waitE );
}

EndE( ) {
  P( waitE );
  nEast := nEast - 1;
  if nEast = 0 then { V( bFree ) };
  V( waitE );
}

StartW( ) {  // executed by a west-car to enter bridge
  P( waitW );
  numW := numW + 1;
  if numW = 1 then { P( bFree ) };
  V( waitE );
}

EndW( ) {
  P( waitW );
  numW := numW - 1;
  if numW = 0 then { V( bFree ) };
  V( waitW );
}
NOTE:

3. Attempted solution 2

integer numInE initially 0;    // number of east-cars in bridge
integer numWaitE initially 0;  // number of east-cars waiting
Semaphore gateE initially 0;   // east-cars wait here

integer numInW initially 0;    // number of west-cars in bridge
integer numWaitW initially 0;  // number of west-cars waiting
Semaphore gateW initially 0;   // west-cars wait here

Semaphore mutex initially 1;  // protects counters

StartE() {
  P(mutex) ;
  if ( numInW > 0 or numWaitW > 0 )
    then { numWaitE := numWaitE + 1;
           V(mutex);
           P(gateE)
    }
    else { numInE := numInE + 1;
           V(mutex)
    }
}


EndE() {
  P(mutex);
  numInE := numInE - 1;
  if ( numInE = 0 and numWaitW > 0 )
    then { for i = 1 to numWaitW do { V(gateW) };
           numInW := numWaitW;
           numWaitW := 0;
    };
  V(mutex);
}

StartW() {
  P(mutex);
  if ( numInE > 0 or numWaitE > 0 )
    then { numWaitW := numWaitW + 1;
           V(mutex);
           P(gateW)
    }
    else { numInW := numInW + 1;
           V(mutex);
    }
}

EndW() {
  P(mutex);
  numInW := numInW - 1;
  if ( numInW = 0 and numWaitE > 0 )
    then { for i = 1 to numWaitE do { V(gateE) };
           numInE := numWaitE;
           numWaitE := 0;
    };
  V(mutex);
}
NOTE: