Author Description

The Dining Philosophers problem is a classic case study in the synchronization of concurrent processes. The five philosophers sit at a circular table with a large bowl of spaghetti in the center. A fork is placed in between each pair of adjacent philosophers, and as such, each philosopher has one fork to his left and one fork to his right. As spaghetti is difficult to serve and eat with a single fork, it is assumed that a philosopher must eat with two forks. Each philosopher can only use the forks on his immediate left and immediate right. The philosophers never speak to each other, which creates a dangerous possibility of deadlock when every philosopher holds a left fork and waits perpetually for a right fork (or vice versa). The problem is even more difficult with multiprocessor systems. There are implementations of a variety of priority inversion control algorithms in the uniprocessor systems, but there has been less work done on the multiprocessor implementations of these algorithms. Herein, we will present such an evaluation of the Multiprocessor Priority Ceiling Protocol (MPCP) and the Multiprocessor Stack Resource Policy (MSRP). We will show that the results differ from the previous simulation-based studies and that both policies are more or less equally effective. The main difference is the MSRP's expense. We will discuss the efficacy of the Ada language and the methods that we have attempted to overcome Ada's weakness in mapping tasks to processors.