Southern Methodist University
Bobby B. Lyle School of Engineering
Department of Computer Science
CS 5343/7343
• CS 5343 students must do exactly 2 projects
• CS 7343 students must do all projects
For each project, please submit
1. The source code of the project
2. Brief description of how to test your program
3. A sample Output (snapshot or a video of program running)
All of the above should be place on folder (called Project1 & Project2). These two
folders should be placed in a folder bearing your name (e.g., Mike Smith). The
folder "Mike Smith" should be zipped and uploaded to Canvas. 1. Project 2―The Sleeping Teaching Assistant (Chapter 7, P-38)
Project 2―The Sleeping Teaching Assistant
A university computer science department has a teaching assistant (TA) who
helps undergraduate students with their programming assignments during
regular office hours. The TA's office is rather small and has room for only one
desk with a chair and computer. There are three chairs in the hallway outside
the office where students can sit and wait if the TA is currently helping another
student. When there are no students who need help during office hours, the
TA sits at the desk and takes a nap. If a student arrives during office hours
and finds the TA sleeping, the student must awaken the TA to ask for help. If a
student arrives and finds the TA currently helping another student, the student
sits on one of the chairs in the hallway and waits. If no chairs are available, the
student will come back at a later time.
Using POSIX threads, mutex locks, and semaphores, implement a solu-
tion that coordinates the activities of the TA and the students. Details for this
assignment are provided below.
The Students and the TA
Using Pthreads (Section 4.4.1), begin by creating n students where each student
will run as a separate thread. The TA will run as a separate thread as well.
Student threads will alternate between programming for a period of time and
seeking help from the TA. If the TA is available, they will obtain help. Otherwise,
they will either sit in a chair in the hallway or, if no chairs are available, will
resume programming and will seek help at a later time. If a student arrives
and notices that the TA is sleeping, the student must notify the TA using a
semaphore. When the TA finishes helping a student, the TA must check to see
if there are students waiting for help in the hallway. If so, the TA must help
each of these students in turn. If no students are present, the TA may return to
napping.
Perhaps the best option for simulating students programming—as well as
the TA providing help to a student-is to have the appropriate threads sleep
for a random period of time.
Coverage of POSIX mutex locks and semaphores is provided in Section 7.3.
Consult that section for details. 2. Project 3-The Dining-Philosophers Problem (Chapter 7, P-39)
Project 3―The Dining-Philosophers Problem
In Section 7.1.3, we provide an outline of a solution to the dining-philosophers
problem using monitors. This project involves implementing a solution to
this problem using either POSIX mutex locks and condition variables or Java
condition variables. Solutions will be based on the algorithm illustrated in
Figure 7.7.
Both implementations will require creating five philosophers, each identi-
fied by a number 0..4. Each philosopher will run as a separate thread. Philoso-
phers alternate between thinking and eating. To simulate both activities, have
each thread sleep for a random period between one and three seconds.
I. POSIX
Thread creation using Pthreads is covered in Section 4.4.1. When a philosopher
wishes to eat, she invokes the function
pickup forks (int philosopher number)
where philosopher_number identifies the number of the philosopher wishing
to eat. When a philosopher finishes eating, she invokes
return forks (int philosopher number)
Your implementation will require the use of POSIX condition variables, which
are covered in Section 7.3.
II. Java
When a philosopher wishes to eat, she invokes the method take-
Forks (philosopherNumber), where philosopherNumber identifies the
number of the philosopher wishing to eat. When a philosopher finishes eating,
she invokes returnForks (philosopherNumber).
Your solution will implement the following interface:
public interface DiningServer
public
}
/Called by a philosopher when it wishes to eat */
public void take Forks (int philosopherNumber);
Called by a philosopher when it is finished eating */
public void returnForks (int philosopherNumber);
It will require the use of Java condition variables, which are covered in Section
7.4.4. 3. Project 4—The Producer – Consumer Problem (Chapter 7, P-40)
Project 4―The Producer-Consumer Problem
In Section 7.1.1, we presented a semaphore-based solution to the producer-
consumer problem using a bounded buffer. In this project, you will design a
programming solution to the bounded-buffer problem using the producer and
consumer processes shown in Figures 5.9 and 5.10. The solution presented in
Section 7.1.1 uses three semaphores: empty and full, which count the number
of empty and full slots in the buffer, and mutex, which is a binary (or mutual-
exclusion) semaphore that protects the actual insertion or removal of items
in the buffer. For this project, you will use standard counting semaphores
for empty and full and a mutex lock, rather than a binary semaphore, to
represent mutex. The producer and consumer-running as separate threads
--will move items to and from a buffer that is synchronized with the empty,
full, and mutex structures. You can solve this problem using either Pthreads
or the Windows API.
The Buffer
Internally, the buffer will consist of a fixed-size array of type buffer_item
(which will be defined using a typedef). The array of buffer_item objects
will be manipulated as a circular queue. The definition of buffer_item, along
with the size of the buffer, can be stored in a header file such as the following:
/* buffer.h */
typedef int buffer_item;
#define BUFFER_SIZE 5
The buffer will be manipulated with two functions, insert_item() and
remove_item(), which are called by the producer and consumer threads,
respectively. A skeleton outlining these functions appears in Figure 7.14.
The insert_item() and remove_item() functions will synchronize the
producer and consumer using the algorithms outlined in Figure 7.1 and Figure
7.2. The buffer will also require an initialization function that initializes the
mutual-exclusion object mutex along with the empty and full semaphores.
The main() function will initialize the buffer and create the separate pro-
ducer and consumer threads. Once it has created the producer and consumer
threads, the main() function will sleep for a period of time and, upon awaken-
ing, will terminate the application. The main() function will be passed three
parameters on the command line:
1. How long to sleep before terminating
2. The number of producer threads
3. The number of consumer threads
A skeleton for this function appears in Figure 7.15. #include "buffer.h"
/* the buffer */
buffer item buffer [BUFFER_SIZE];
int insert item (buffer_item item) {
}
/* insert item into buffer
return 0 if successful, otherwise
return -1 indicating an error condition */
int remove_item(buffer_item *item) {
}
/* remove an object from buffer
placing it in item
return 0 if successful, otherwise
return -1 indicating an error condition */
Figure 7.14 Outline of buffer operations.
The Producer and Consumer Threads
The producer thread will alternate between sleeping for a random period of
time and inserting a random integer into the buffer. Random numbers will
be produced using the rand() function, which produces random integers
between 0 and RAND-MAX. The consumer will also sleep for a random period
of time and, upon awakening, will attempt to remove an item from the buffer.
An outline of the producer and consumer threads appears in Figure 7.16.
#include "buffer.h"
int main(int argc, char *argv[]) {
}
/* 1. Get command line arguments argv[1], argv[2], argv[3] */
/* 2. Initialize buffer */
/* 3. Create producer thread(s) */
/* 4. Create consumer thread(s) */
/* 5. Sleep */
/* 6. Exit */
Figure 7.15 Outline of skeleton program.
