Begin by creating n philosophers, each identified by a number 0...(n-1). Each philosopher will run as a separate thread. Philosophers alternate between thinking and eating. To simulate both activities, have the thread sleep for a random period between one and five seconds. 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)

Pthreads Condition Variables Condition variables in Pthreads behave similarly to those described in Slides (Process Management PartK, Slides 8-12). However, in that part, condition variables are used within the context of a monitor, which provides a locking mechanism to ensure data integrity. Since Pthreads is typically used in C programsand since C does not have a monitorwe accomplish locking by associating a condition variable with a mutex lock. Pthreads mutex locks are covered in the slides (Process Management PartH). We cover Pthreads condition variables here. Condition variables in Pthreads use the pthread_cond_t data type and are initialized using the pthread_cond_init() function. The following code creates and initializes a condition variable as well as its associated mutex lock:

pthread_mutex_t mutex; pthread_cond_t cond_var; pthread_mutex_init(&mutex,NULL); pthread_cond_init(&cond_var,NULL);

The pthread_cond_wait() function is used for waiting on a condition variable. The following code illustrates how a thread can wait for the condition a == b to become true using a Pthread condition variable:

pthread_mutex_lock(&mutex); while (a != b) pthread_cond_wait(&mutex, &cond_var); pthread_mutex_unlock(&mutex);

The mutex lock associated with the condition variable must be locked before the pthread_cond_wait() function is called, since it is used to protect the data in the conditional clause from a possible race condition. Once this lock is acquired, the thread can check the condition. If the condition is not true, the thread then invokes pthread_cond_wait(), passing the mutex lock and the condition variable as parameters. Calling pthread_cond_wait() releases the mutex lock, thereby allowing another thread to access the shared data and possibly update its value so that the condition clause evaluates to true. (To protect against program errors, it is important to place the conditional clause within a loop so that the condition is rechecked after being signaled.)

A thread that modifies the shared data can invoke the pthread_cond_signal() function, thereby signaling one thread waiting on the condition variable. This is illustrated below: Pthread_mutex_lock(&mutex); a = b; pthread_cond_signal(&cond_var); pthread_mutex_unlock(&mutex); It is important to note that the call to pthread_cond_signal() does not release the mutex lock. It is the subsequent call to pthread_mutex_unlock()that releases the mutex. Once the mutex lock is released, the signaled thread becomes the owner of the mutex lock and returns control from the call to pthread_cond_wait().

Part I Assignment Design and implement a solution for the dining-philosophers problem using the Pthreads library. Your solution must be deadlock-free. Following are some sample ? outputs expected from your solution: ...... Philosopher 2 is eating: eating for 1 seconds Philosopher 4 is eating: eating for 4 seconds Philosopher 2 is thinking: thinking for 5 seconds Philosopher 1 is eating: eating for 3 seconds Philosopher 4 is thinking: thinking for 4 seconds Philosopher 3 is eating: eating for 2 seconds Philosopher 1 is thinking: thinking for 1 seconds Philosopher 0 is eating: eating for 3 seconds Philosopher 3 is thinking: thinking for 4 seconds Philosopher 2 is eating: eating for 2 seconds Philosopher 0 is thinking: thinking for 5 seconds Philosopher 4 is eating: eating for 1 seconds Philosopher 2 is thinking: thinking for 2 seconds Philosopher 1 is eating: eating for 5 seconds Philosopher 4 is thinking: thinking for 5 seconds Philosopher 3 is eating: eating for 1 seconds Philosopher 3 is thinking: thinking for 1 seconds Philosopher 3 is eating: eating for 2 seconds Philosopher 1 is thinking: thinking for 5 seconds Philosopher 0 is eating: eating for 4 seconds ...... Note that in your writing report, you should provide details on how you design your solution and how your solution can achieve deadlock-free. In addition, you should also discuss whether your solution can avoid starvation. If yes, explain why; and if not, explain why and discuss how your solution can be changed to avoid starvation. Part IIBankers Algorithm (Mandatory for graduate students) For this part of the project, you will write a multithreaded program that implements the bankers algorithm discussed in the Slides (Deadlocks and CPU Scheduling PartB). Several customers request and release resources from the bank. The banker will grant a request only if it leaves the system in a safe state. A request that leaves the system in an unsafe state will be denied. This part of the project combines three separate topics: (1) multithreading, (2) preventing race conditions, and (3) deadlock avoidance. The Banker The banker will consider requests from n customers for m resources types, as outlined in the Slides (Deadlocks and CPU Scheduling PartB and PartC). The banker will keep track of the resources using the following data structures: ? ? /* these may be any values >= 0 */ #define NUMBER_OF_CUSTOMERS 5 #define NUMBER_OF_RESOURCES 3 /* the available amount of each resource */ int available[NUMBER_OF_RESOURCES]; /*the maximum demand of each customer */ int maximum[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES]; /* the amount currently allocated to each customer */ int allocation[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES]; /* the remaining need of each customer */ int need[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES];

The Customers Create n customer threads that request and release resources from the bank. The customers will continually loop, requesting and then releasing random numbers of resources. The customers requests for resources will be bounded by their respective values in the need array. The banker will grant a request if it satisfies the safety algorithm outlined in the Slides (Deadlocks and CPU Scheduling PartB). If a request does not leave the system in a safe state, the banker will deny it. Function prototypes for requesting and releasing resources are as follows: int request_resources(int customer_num, int request[]); int release_resources(int customer_num, int release[]); These two functions should return 0 if successful (the request has been granted) and 1 if unsuccessful. Multiple threads (customers) will concurrently access shared data through these two functions. Therefore, access must be controlled through mutex locks to prevent race conditions by using the Pthreads APIs.

Implementation You should invoke your program by passing the number of resources of each type on the command line. For example, if there were three resource types, with ten instances of the first type, five of the second type, and seven of the third type, you would invoke your program follows: ./a.out 10 5 7 The available array would be initialized to these values. You may initialize the maximum array (which holds the maximum demand of each customer) using any method you find convenient. ? ? Part II Assignment Implement the Bankers Algorithm using the Pthreads library. Following are some sample outputs expected from your solution: ...... Available [5 2 4] Customer 0 Allocation/Max [0 1 0]/[7 5 3] Customer 1 Allocation/Max [3 0 2]/[3 2 2] ...... Customer 0 is requesting [3 2 1] Request granted ...... Available [2 0 3] Customer 0 Allocation/Max [3 3 1]/[7 5 3] Customer 1 Allocation/Max [3 0 2]/[3 2 2] ...... Customer 1 is requesting [2 0 2] Request denied ...... Customer 0 releases [1 1 1] Available [3 1 4] Customer 0 Allocation/Max [2 2 0]/[7 5 3] Customer 1 Allocation/Max [3 0 2]/[3 2 2] ......