Assignment 1

Programming Assignment 1

This assignment has two parts. In the first part, you will use the JAVA monitor to implement a semaphore. In the second part, you will solve a given synchronization problem and implement its solution using the semaphores created in the first part. This assignment must be done in groups of two. Assignments submitted with more or less than two group members will not be accepted. This assignment will be done in JAVA.

What to do?

Part I:

In this part of the assignment, you will use JAVA monitor to implement semaphores. More specifically, you will define a class called Semaphore. This class will have the following interface.

A constructor Semaphore (int init), where init specifies the initial integer value for the semaphore; for example, to create a semaphore for mutual exclusion, we set init to 1 for that semaphore.

A method void Enter (), which will perform the wait operation of the semaphore.

A method void Exit (), which will perform the signal operation of the semaphore.

You may need to use the synchronized primitive, as well as wait (), notify (), and notifyAll () methods of JAVA. For a tutorial on how to use these, see online java tutorial .

Part II:

In this part of the assignment, you will present a semaphore-based solution to the following synchronization problem and then implement it using the Semaphore class built in part I.

The newly built Duffield Hall has washrooms in the basement for people to take showers. However, due to lack of funds, only one washroom with 3 showers for use by both men and women could be completed. But etiquette prevents men and women from using the washroom simultaneously. Consequently, when a man is using a shower, any woman must wait outside, even if two other showers are free (and vice versa). However, a man can use the second shower even if another man is using the first one. Let us assume that there is a sign outside the washroom indicating whether the occupants are men or women and whether the washroom is empty or full, and that each shower can be used by at most one person at a time.

The problem is to write an algorithmic representation for the activities of a man and a woman as they arrive to use the washroom. Use semaphores to enforce synchronization and mutual exclusion. Assume that the arriving men and women stand in a queue outside the washroom and that they always enter the washroom in the order of arrival. Thus, if a woman is waiting outside the washroom because it is being occupied by a man, any man behind her cannot enter the washroom before she does even if a shower is currently free. The above condition enforces fairness. Assume that at each unit of time either a man or a woman arrives and stands at the tail of the queue to use the washroom.

Note that each arriving man or woman executes parallel code. There need not be an explicit queue data structure for waiting. People waiting to enter a semaphore can be thought of as waiting in a queue. Note that there are 3 showers in the washroom and hence a man does not have to wait if a shower is free and there are no women inside the washroom. For your convenience, a skeleton program is being provided with appropriate places for your code marked in it. Please download the file Solution.java and use only that file to implement the solution. The code for generating men and women has already been incorporated in the skeleton program. The method to be called to indicate that a man or woman is using the shower is also indicated in the skeleton program.

Each team may present a text solution (algorithmic, not in java code) to the problem in class by Wednesday, June 6. This solution will be corrected and returned on the following day. This provision is to give you an opportunity to come up with a correct solution before having to implement it. However, only the final solution will be considered for grading.

What to submit?

You should submit the following things as a part of this assignment. Instructions for submission can be found here.

1. A file called Semaphore.java containing the definition of the class Semaphore as specified.

2. A file called Solution.java containing the implementation of the synchronization problem.

3. A file called README.txt where you give a tutorial on how to compile and run your programs. This file should also contain the names, net ids and Cornell ids of all the individuals in the group.

4. A file called Solution.txt containing a text version of the solution proposed for the synchronization problem.

5. Since we would be using our test programs to interface with your java programs, please make sure that you implement the interfaces precisely as stated.

How will you be graded?

The following will play a crucial role in your grades for this assignment.

Part I:

1. Correctness of the JAVA program written to implement semaphores.

2. Robustness of the JAVA program written.

3. Clarity of the JAVA program (comments!!!).

4. Ease of using the README to test your programs and results.

5. We would use our own test program to test the correctness of your implementation.

Part II:

1. Correctness of the text solution presented to the synchronization problem. Correctness includes the following:

· Mutual exclusion and appropriate synchronization.

· Fairness and no starvation.

· No Deadlocks.

2. Correct implementation of the solution presented to the synchronization problem.

When to submit?

Final submission (one per team) of all files must be made electronically by Sunday, 10.00 p.m., 06/10/01. The instructions for electronic submission will be posted on the web. A provisional text solution (one per team) may be submitted in class on 06/06/01 for corrections. The corrected solution will be returned the next day in class. The above deadlines are strict.