Unisex Bathroom Problem

This project attempts to solve the problems outlined The Unisex Bathroom: Fairness versus Performance [1], using a strategy which is 100% fair.

Assumptions

  • Males and females cannot use the bathroom at the same time
  • An individual will spend some time doing other things, other than using the bathroom
  • An individual will spend some time using the bathroom
  • An individual cannot do other things while waiting to use the bathroom
  • An individual does not like to wait to use the bathroom
  • Each individual may spend different amounts of time in the bathroom

The ideal solution to the ‘Unisex Bathroom Problem’ is one that is 100% fair, and also has a minimal waiting time for each person.

However, a strategy with good performance may not be 100% fair to all individuals, and vice-versa.

Performance & Fairness

I chose to implement a solution which is 100% fair to every individual. A single queue for the bathroom is used on a FIFO (First-In First-Out) basis. If someone of the opposite sex is currently using the bathroom, then the individual must wait for the bathroom to empty.

“Strategy 2” of “The Unisex Bathroom: Fairness versus Performance” [1] suggests a strategy which is almost 100% fair, and yields very good performance. However, it is my opinion that in this context, fairness is more important than performance.

Deadlock & Denial

By making correct use of synchronisation in Java, the solution completely avoids any occurrence of deadlock or denial.

Implementation

The ‘Bathroom’ class is a shareable resource that can be represented by shared memory. It has 5 ‘stalls’. It holds a single list representing the queue of people.

It is responsible for choosing when to next let a person in.

Each ‘Person’ is a separate thread based on the following logic[1]:

Person[i:1..k] :: while (true)
do_something; // random delay
get_stall; // wait here if stall is not available
use_stall; // random delay
release_stall;
end of while loop;

The ‘random delay’ is used to represent time fluctuation from iteration to iteration. This reflects how a real process might behave.

Each person can be male or female. The order of adding people to the queue is random.

Grouping people by gender would provide better performance, but decrease the realism of how processes generally behave.

Measurements are displayed on a basic GUI. It is possible to see how fairness is satisfied, since both total female and male waiting times are never far apart. Also, it is seen that the number of males/females who have used the bathroom are closely related.

More information on how the program fits together can be found in the source code, which is commented well.

Requirements

  • Java 1.5 or later.

Files & Running

Download All

To execute, simply compile all three classes and run RunBathroom.

References

[1] The Unisex Bathroom: Fairness versus Performance, 12-April-2006, Assistant Professor David J. Powers.