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.

Dynamic dependency injection with Lift framework

Recently I have been working with scala and Lift.

Among many other features lift provide a convenient way to fordependency injection. Although cake pattern is the way to do dependency injection for scala users, it lakes in certain areas. Specially when working with multiple modules where abstraction and concrete implementation are in separate modules.

Lift Injector comes in handy in this context.

For example think of you have two module project core-logic and repository. core-logic is the place you want to keep all the business logic without infrastructure level details. core-logic will have some abstract  interfaces for repositories. e.g:-

trait UserRepository {

def createUserAccount(ua: UserAccount): Either[ErrorContext, UserAccount]

def findUserAccountByUsername(username: String): Either[ErrorContext, UserAccount]

}

repository is the place you want to keep the infrastructure (e.g:- db layer) level details.

class UserRepositoryImpl extends UserRepository {

      override def createUserAccount(ua: UserAccount): Either[ErrorContext, UserAccount] = {

      …

     }

}

Using static injection method it is difficult to inject this kind of dependency injection

object UserManagementDepInjector extends SimpleInjector {

}

With lift SimpleInjector you can register injections dynamically. This can be done at boot (if you are using life web framework)

class Boot {

   def boot {

      UserManagementDepInjector.registerInjection(() => {new UserRepositoryImpl()})(Manifest.classType(classOf[UserRepository]))

      …

   }

}

As in above we can register injections and Injector itself will handle injecting the correct concrete implementation.

class UserService {

   val userRepository: UserRepository = UserManagementDepInjector.inject[UserRepository].openTheBox

}

Need to mention that using of Box.openTheBox method may not be the recommended way. But I think in most practical cases application is not useful if that dependency is not available, so why bother !!!