OS: Lab 2: Threads and Semaphores


Getting Started

The Assignment

For this assignment and all subsequent ones, you may work in groups of max 5 students. Be sure that you read carefully how the lab should be handed in. Make sure the group has all the required material, and each of you hand in what is required individually.

  1. Thread Scheduling
    This question is based on Section 6.7 of the text book. The text provides sample code for implementing a round-robin scheduler for Java threads. Using this code as a starting point, implement a scheduler that has three queues with different priorities, each with priority 2, 3 and 4. Have the scheduler select a thread from the highest-priority non-empty queue, set that thread's priority to 5 and allow the thread to run for the time slice for that queue. Assume that the times slice for each priority level is 3* DEFAULT_TIME_SLICE, 2* DEFAULT_TIME_SLICE and DEFAULT_TIME_SLICE, respectively. When this time slice expires, select the next highest priority thread and repeat the process. Assume that round-robin scheduling is used at each priority level, and that a higher priority thread that wakes up does not preempt a currently executing thread. Unlike multi-level feedback queue scheduling, assume that your simple scheduler does not move threads from one priority-level to another.

    Test your scheduler with three threads, one at each priority level. Have each thread run in a loop incrementing a counter. After every 10,000 loops, have each thread print out its id and the current value of its counter and then sleep for 5 seconds, allowing a lower priority thread to run.

  2. Threads and Semaphores
    Using Java semaphores described in Section 7.8.6, implement reader/writer communication.
    A data object is to be shared among several concurrent threads. Some of the threads, the Readers, want only to read the content of the shared object. When a reader, reads the content of the shared object (assume a single character), it should produce the following output on the screen:
      Reader <id> reading <character>

    where <id> is the unique identifier of the Reader.

    The Writer threads want to update (i.e. overwrite) the shared object with a single character which they read, in a sequential order from a text file, a file called writer_input.txt (best is to use a text file where neighboring characters are different). When a writer updates the shared object, it should produce the following output on the screen:

      Writer <id> writing <character>

    where <id> is the unique identifier of the writer, and <character> is the character just written on to the shared object. Every character read from the text file is written only by one of the Writer threads, i.e., access to the file must be synchronized and the file pointer is incremented after each access. Synchronization thus must be provided for both accessing the shared object and reading the text file.

    Test your solution with multiple readers and writers. Of course, with multiple readers and writers, the output will illustrate the concurrency provided by threads. As multiple Readers can access the shared object concurrently before an update occurs, you may see several Readers reading the same character from the shared object.

    Your code should prompt for the number of readers and the number of writers, in that order. You can assume that a valid integer is provided by the user for each of these. You should be sure that your code works for different input files as we may test it with files other than what you provide (i.e., to check that the synchronization you provide works).

How to Turn in Lab 2

All of the following files and hard copies must be turned in to get full credit for a question.

  1. Hand in a hard copy of all the files that you modified.
  2. Hand in a hard copy of a README file identifying your lab partners (if you have one) and containing an outline of the group did for the assignment. It should also explain and motivate your design choices. Keep it short and to the point. 
    If your implementation does not work, you should also document the problems in the README, preferably with your explanation of why it does not work and how you would solve it if you had more time.
  3. Hand in a hard copy showing sample output from your programs.
  4. Create jars with your files, use javadoc to document your codes.
  5. Individual Group Assessment (for students working in groups only)

    What you need to turn in (each person individually):

    Turn in a hard copy of your assessment of the division of labor in the group in the format shown below.  If you give yourself a 50% and your partner gives you a 50%, you will get the whole credit.  If you give your partner a 40% and your partner gives himself or herself a 40%, he or she will get 80% points.  And so on...

  6. Note: We will strictly enforce policies on cheating. Remember that we routinely run similarity checking programs on your solutions to detect cheating. Please make sure you turn in your own work.