The Senate Bus Problem

Recently I did a assignment in my MSc in Concurrent programming. The problem was taken from Little Book of Semaphores and the name of the problem was given as "Senate Bus Problem".

The problem in interest is described in the book as follows.

This problem was originally based on the Senate bus at Wellesley College. Riderscome to a bus stop and wait for a bus. When the bus arrives, all the waitingriders invoke boardBus, but anyone who arrives while the bus is boarding hasto wait for the next bus. The capacity of the bus is 50 people; if there are morethan 50 people waiting, some will have to wait for the next bus.When all the waiting riders have boarded, the bus can invoke depart. If thebus arrives when there are no riders, it should depart immediately.Puzzle: Write synchronization code that enforces all of these constraints.

One solution given in book can be implemented in java

1:  public class BusImpl implements Bus {  
2:    private int waiting = 0;  
3:    private Semaphore mutex = new Semaphore(1);  
4:    private Semaphore bus = new Semaphore(0);  
5:    private Semaphore boarded = new Semaphore(0);  
6:    @Override  
7:    public void takeRide() throws InterruptedException {  
8:      mutex.acquire();  
9:      waiting++;  
10:      mutex.release();  
11:      bus.acquire();  
12:      board();  
13:      boarded.release();  
14:    }  
15:    public void board() {  
16:      System.out.println("Rider boarded");  
17:    }  
18:    @Override  
19:    public void arrive() throws InterruptedException {  
20:      mutex.acquire();  
21:      int n = Math.min(waiting, 50);  
22:      for(int i = 0; i < n; i++) {  
23:        bus.release();  
24:        boarded.acquire();  
25:      }  
26:      waiting = Math.max((waiting - 50), 0);  
27:      mutex.release();  
28:      depart();  
29:    }  
30:    public void depart() {  
31:      System.out.println("Bus departed.");  
32:    }  
33:  }  

Both solutions in book of coarse optimized for minimum usage of variables. When considering performance it is obvious that we can do better. One thing noticed was in the line bus.release() it is almost sequential.  For example if number of riders are 3 the minimum context switches needed will be 7 (starting with bus arrival).


I came up this solution :- 

1:  public class MultiDoorBusImpl implements Bus {  
2:    private int waitingRiderCount = 0;  
3:    private int noOfRidersAllowed = 0;  
4:    private int boardedRidersCount = 0;  
5:    private Semaphore mutex1 = new Semaphore(1);  
6:    private Semaphore mutex2 = new Semaphore(1);  
7:    private Semaphore bus = new Semaphore(0);  
8:    private Semaphore allBoarded = new Semaphore(0);  
9:    @Override  
10:    public void takeRide() throws InterruptedException {  
11:      mutex1.acquire();  
12:      waitingRiderCount++;  
13:      mutex1.release();  
14:      bus.acquire();  
15:      board();  
16:      mutex2.acquire();  
17:      boardedRidersCount++;  
18:      if (boardedRidersCount == noOfRidersAllowed) {  
19:        allBoarded.release();  
20:      }  
21:      mutex2.release();  
22:    }  
23:    @Override  
24:    public void board() {  
25:    }  
26:    @Override  
27:    public void arrive() throws InterruptedException {  
28:      mutex1.acquire();  
29:      noOfRidersAllowed = Math.min(50, waitingRiderCount);  
30:      if (noOfRidersAllowed > 0) {  
31:        bus.release(noOfRidersAllowed);  
32:        allBoarded.acquire();  
33:      }  
34:      mutex1.release();  
35:      depart();  
36:    }  
37:    @Override  
38:    public void depart() {  
39:    }  
40:  }  

Where in this case minimum number of context switches needed for 3 riders will be 5 (starting with bus arrival). Of cause it uses more semaphores/variables.



Have to say that in my nearly 5 years of  work I have faced little bit of concurrent issues, but this book is total in different level.