Reference no: EM13120877

To deal with deadlocks, we can either use prevention, or avoidance, or detection followed by recovery. But which is a better choice in a particular setting where deadlocks could occur from time to time? Let do some "research" to find out the answer. Let's use the classical Dining Philosophers Problem (there are N of them, N ≥ 2) as the case. We will use the naïve, deadlock-prone method (each philosopher first tries to grab the left fork and then the right chopstick) as the base. Thus we should compare:

The naïve method with deadlock avoidance
The naïve method with deadlock detection and recovery
A good method that prevents deadlocks (such as those we mentioned in class)

Since (i) (avoidance) is very similar to (ii) in logic given that the resources (chopsticks) are all single-instance, you are required to implement and compare just (ii) (detection/recovery) and (iii) (prevention). (Well, if you do also (i), we will reward you with some bonus points (≤ 5%).) (iii) should be easy. To implement (ii), you need to figure out WHEN to detect, and the actual detection action; and then of course to resolve the deadlock if indeed one is detected. You might need to add an auxiliary thread to be responsible for all this. For resolving a detected deadlock, you may relax the "no preemption" rule, and ask a philosopher (or more) to release a chopstick that he is holding.

To carry out the comparison using experiments, you need to simulate the thinking/eating cycle of the philosophers, where eating will take E amount of time, and thinking will take T amount of time. E and T should be generated from a statistical distribution (I recommend Gaussian) so that you get some kind of randomness resembling real life. Gaussian distribution is easy to build in C (a few lines will do), and you should be able to find its code from the Internet if you don't want to write it; alternatively, you can use the GSL library where Gaussian is one of a long list of callable random statistical functions. To make a philosopher (represented by a thread) think or eat for T or E amount of time, you can use the sleep() or the finer usleep() function of Linux. If you don't want to bother with using a distribution, you should at least try to generate your Ts and Es using some mean value + a standard deviation (i.e., to draw a random number).

The experiments are to be done on Linux (or Solaris). Please write your code in C or C++, use Pthread to create the threads (one for each philosopher), and use POSIX semaphores (for uniformity) to implement thread synchronization or any critical section that maybe needed. There is a lot of info on using POSIX semaphores in Linux in the Internet, such as this one. If you use C++, the Gaussian distribution is available as part of its random number generation facilities. To repeat running an experiment, you might want to use a shell script. "Make", as always, is also a useful utility, for managing and compiling your source code. If you have to plot any graphs, Matlab is probably the best tool; there are also many open-source graph plotting packages which you can try.

So what will you measure and compare in order to determine the winner or which is better than which (which might depend on the situation)? The CPU Scheduling chapter should give us some insight on this. Throughput (how many philosophers can finish their think/eat cycle within a certain time duration) is definitely an important measure. Perhaps wait time also (you don't want any one to starve or grow grumpy). And maybe fairness. You can use the Linux command "time" to measure the execution time of any of your programs. If you need finer control of the measurements, you could use such functions as clock() inside your code.

You will write an essay to report your experiments and their results, and to present and discuss your findings. More details on the format etc. will be announced subsequently. Other than to answer the question (which is the best method?) for the Dining Philosophers Problem which is a specific case, you may want also to use the results to shed light on how to handle the possibility of deadlock in general when given any situation that might come under the harassment of deadlocks.