Having studied the Nachos operating system structure in the previous project, now it is time to demonstrate your knowledge of Nachos. In this project, you will work in teams of two, with the same partner that you worked for Projects I and II.

In this project, you will use semaphores to solve some the synchronization problems. For  a brief overview of the semaphore synchronization primitive and its implementation in Nachos, visit   Salsa's overview of Synchronization .

The first problem you will solve is the producer -consumer problem.

1.Producer-Consumer Problem: The producer places characters from a text file into the buffer one character at a time; it must wait if the buffer is full. The consumer pulls characters out of the buffer one at a time and prints them to the screen; it must wait if the buffer is empty. Test your solution with a multi-character buffer and with multiple producers and consumers. Of course, with multiple producers or consumers, the output will illustrate the concurrency provided by threads.

The second problem will be ONE out of the following three. I will randomly assign the problems to the various teams in class.  Your solutions to the following problems should be deadlock free and starvation free.

A. (Sleeping Barber Problem) A barbershop consists of a waiting room with n chairs, and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.

B. (Narrow Bridge Synchonization) Suppose a two way (two-lane) east-west road contains a narrow bridge with only one lane. An eastbound (or westbound) car can only pass over the bridge if, when it arrives at the bridge, there are no oncoming cars on the bridge. Write a program to achieve the synchronization necessary to coordinate the cars passing the bridge.  In particular, write the code of a procedure called car that knows whether it is driving east or west (i.e. a value passed in as a parameter), that calls the critical section to cross the bridge. (Note that two cars can be crossing the bridge at the same time, if they are both going in the same direction.)

C. (The Cigarette Smoker's Problem): Consider a system with three smoker processes and one agent process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper and matches. One of the smoker processes has paper, another has tobacco and the third has matches. The agent has an infinite supply of all the three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient than makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a program to synchronize the agent and the smokers.

Guidelines and Hints: For this assignment, you will only need to modify files in the threads directory. In particular, the files you are most concerned with are threadtest.cc, synch.cc, and synch.h. For  implementing the  synchronization primitives, you should modify only synch.h and synch.cc;  The semaphores are defined in synch.cc. You need to complete writing the functions.

To develop solution to the two problems, you need to modify threadtest.cc. Your first step is to make a copy of this file and keep it under some other name for reference (e.g. threadtest.cc.orig), and then modify threadtest.cc as needed .  Once you have implementated  a solution to a problem, say the Sleeping Barber problem in threadtest.cc, then copy the threadtest.cc into  barber.cc.  If you wish, you could have a a file named barber.h. In addition, you should surround your changes with the ifdef CHANGED directive. The variable CHANGED is defined by default in Makefile.common in the code directory.

Think about what you need to do to synchronize your threads before you start writing code. Have the strategy clear in your head or on paper before you write code. This strategy is always the best way.

I highly recommend that you write and thorougly test your code in small increments to make debugging and trouble shooting as easy as possible. It is easier to get rid of compile time and runtime errors for one routine at a time, than it is for all the code that you write at once. In the same vein, use small easy test cases first and more rigorous tests once the easy cases work.

It is expected that code is readable and is well documented. This should have been taught to you in lower level classes that teach programming.
 

Submission Instructions:  Note that there will be two  programs submitted by each team. These will be solutions for two synchronization problems. In addition, you will also submit several sample runs to demonstrate that your solution works.

Email Submission: Each team should send tar files. For example, a team that is assigned Sleeping Barber problem would mail the files: prod_cons.tar and  barber.tar.

Each tar file should contain ANY files that are modified from the orginal Nachos files and must contain a README file containing instructions on how to run your program for someone that has the original Nachos files.

The email should be sent to "skanchi@kettering.edu"

Hard-Copy Submission: In addition to the email submission there should be hard-copy submission of the following items.

1. A short  report describing the solutions that you implemented and any comments that you want to make about your solution.

2. The hard-copies of all the files that you modified.  (These would be what you would email me)

3. The copy of several sample runs for each of the  solution.  You must submit at least six  sample runs. The first two sample runs should be obtained by using the "-rs" flag, and the last  four  sample runs should be obtained by adding "currentThread -> Yield()" randomly to your  code.  To obtain the last four sample runs, add the line "currentThread-> Yield()" every  2nd, 3rd, 4th and 5th line of your code respectively.  For the last four sample runs do not use the "-rs" flag. Use the script command to capture the terminal interaction into a file and then print the file.
 
Here is an example of sample output using the "-rs" flag.
 
 %prod_cons  -rs   23232

Please enter the buffer size:  5
Please enter the number of producers:  2
Please enter the number of consumers:  4
producer 0 producing a
producer 0 producing b
producer 0 producing c
producer 1 producing d
consumer 0 consuming a
consumer 0 consuming b
producer 0 producing e
producer 0 producing f
producer 1 producing g
consumer 0 consuming c
consumer 0 consuming d
consumer 1 consuming e
consumer 1 consuming f
consumer 1 consuming g
producer 0 producing h
producer 1 producing i
producer 1 producing j
consumer 0 consuming h
consumer 0 consuming i
consumer 1 consuming j
producer 0 producing k
producer 1 producing l
producer 1 producing m
producer 1 producing n
consumer 0 consuming k
consumer 0 consuming l
producer 0 producing o
producer 0 producing p
consumer 0 consuming m
consumer 0 consuming n
consumer 0 consuming o
consumer 1 consuming p
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!

Ticks: total 1695, idle 35, system 1660, user 0
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

Cleaning up...

---------------------------------------------------------
 

> barber -rs  3
Please enter the number of customer chairs:  5
Please enter the total number of customers:  10
Barber going to sleep.
customer 2 is waking up the barber
customer 3 is waiting for the barber
customer 4 is waiting for the barber
customer 5 is waiting for the barber
customer 7 is waiting for the barber
customer 8 is waiting for the barber
customer 9 is leaving without a haircut
customer 10 is leaving without a haircut
customer 1 is leaving without a haircut
Barber cutting hair.
Barber cutting hair.
Barber cutting hair.
Barber cutting hair.
Barber cutting hair.
Barber cutting hair.
Barber going to sleep.
customer 6 is waking up the barber
Barber cutting hair.
Barber going to sleep.
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!

Ticks: total 954, idle 104, system 850, user 0
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

Cleaning up...