## 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:
• Prove that this satisfies safety but not starvation-freedom.

• Provide a counter-example for starvation-freedom.

### 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:
• Does this work? Prove or disprove.