The end goal of this project is to write a preemptive user-level threads library with mutex exclusion. Along the way, you will become familiar with the pthreads library and solve the classic mutual exclusion puzzle of “The Dining Philosophers”.
Gain access to a well-maintained linux machine. If you do not have this already, then it is recommended that you follow the instructions for downloading and installing VirtualBox and the AOS Virtual Image.
Download gtthreads.tar.gz, which contains the starter code for the project.
You can confirm that you have pthreads installed on your linux platform with the command
ldconfig -p | grep libpthread
For this and all projects, students must work on their own.
To familiarize yourself with the pthreads library, you will debug a simple test program named producer_consumer.c. You may read about the pthread api or consult the man pages on your virtual platform. For example, to learn about pthread_join, type
in a terminal.
There are five bugs in total (you may consult the videos for the project to help you find them.) After finding these bugs, provide answers to the questions given in the QA_producter_consumer.txt in that file.
A good exercise for understanding the perils of deadlock and how to avoid them is the classic “Dining Philosophers” problem originally posed by Dijtkstra:
There are five philosophers sitting around a table. Being philosophers, they like to think, but they also have to eat every now and again. Each philosopher gets his own rice bowl, but there only five chopsticks, one laid between each pair of neighboring philosophers. When wishing to eat, a philosopher needs to pick up the two chopsticks on either side of him. When wishing to think, he places the chopsticks back in their places for his neighbors to use.
The file dining.c contains starter code for the problem. Your task is to complete the given program by filling in the code where indicated. The output should read like directions for a play, where the action involves philosophers thinking, picking up chopsticks, eating, and putting them down.
The directions for the play must be valid. That is, a philosopher can only pick up a chopstick if it is available and only put one down if he has it. Equally important is that no philosopher should be starved. A particularly bad situation is deadlock, where all five philosophers pick up the chopstick to their left and wait for the one to their right to be set down. Of course, this chopstick will never be set down because it is in the left hand of another philosopher. In this deadlocked situation, the philosophers starve. Take care that your program avoids this problem.
There is no requirement to implement fairness among the philosophers, as long as everyone gets to eat when chopsticks are available. For instance, one way to avoid deadlock would be just to prevent one philosopher from ever picking up chopsticks. Another is to use a single global mutex that only allows one philosopher to eat at time. Neither of these are good solutions.
The main part of the project is to implement a user-level thread library with an api similar to POSIX threads or pthreads. The specifications for implementing this api are found in the two files gtthread_sched.c and gtthread_mutex.c.
The following strategies are highly recommended:
It is also suggested that you work incrementally. For instance, you might the task into the following pieces: