CS322 Project 3: Message Passing

Due: Wednesday, April 5, 2000 at the start of class
Purpose: To give you experience with inter-process coordination using messages

Introduction

For your last project, you wrote a program in which concurrent processes coordinated their work by means of semaphores and shared variables. As you know, this mode of inter-process coordination is only usable when the different processes reside on the same CPU, or on tightly-coupled CPU's sharing some physical memory in common. It is not usable on distributed systems, and it is even unusable on some uni-processor operating systems that do not support sharing of physical memory between processes (e.g. standard Unix.) For situations where the use of shared memory is impossible or undesirable, the alternative is to coordinate processes by means of messages. This is the approach we will use for this project.

The problem you will be solving for this project is the dining philosophers problem. You should note right away that there are two possible architectures for a message-based solution to this problem:

  1. A total of 6 processes might be used: 5 for philosophers, and one to serve as a central coordinator. (This might well be the parent process, which could go into this mode after spawning five child processes for the philosophers.)

    1. A philosopher wishing to eat would need to obtain permission to use each chopstick from the coordinator, and could not proceed to eat until an authorization reply is received for each.

    2. Likewise, a philosopher finishing eating would notify the coordinator that it is releasing each chopstick (and might wait for a reply for symmetry, though this is not strictly necessary.)

  2. Only five processes might be used, with philosophers communicating directly with their neighbors to request and release chopsticks.

    Of these two, the second is by far the hardest to implement, since a philosopher must always be ready to exchange messages with a hungry neighbor, even when deep in thought or waiting for an OK from a neighbor.

Requirements

  1. For full credit, implement a deadlock and starvation free solution to the dining philosophers problem using the central coordinator architecture. You will need to do message passing using sockets.

  2. For significant extra credit, implement two deadlock and starvation free solutions to the dining philosophers problem, one using each of the above architectures. (If you decide to attempt this, you would do well to have a conference with the professor) Note: This is a hard project!

Implementation Notes

  1. To help you in doing project 2, you were given an example of a solution to the dining philosophers problem using semaphores.

    1. One key idea in this solution was deadlock prevention by having odd-numbered philosophers pick up their chopsticks in the opposite order from that used by even-numbered philosophers.

    2. This solution can be used quite straight-forwardly as the basis of a "central coordinator" type solution to the problem, by having the coordinator manage the chopsticks.

      • A hungry philosopher sends a "request chopstick" message to the coordinator for one chopstick and awaits an "OK" reply from the coordinator, then repeats this process for the second chopstick.

        The order in which the messages are sent reflects the deadlock prevention rule.

        When the coordinator receives a request, it replies immediately if the chopstick is not in use; otherwise, it notes that the philosopher is waiting for this particular chopstick and sends its reply later when the chopstick becomes available.

      • A philosopher that is sated sends a "put down chopsticks" message to the coordinator (or two separate messages - one for each chopstick - if you prefer). No reply is needed in this case, but you may choose to have the philosopher wait for one for symmetry.

  2. The directory /usr/gc/cs322/p3 on the SGI machines contains two files you will need to use in preparing your project. You can either refer to them by path names, or copy them into your own directory. Alternatively, you can download them from Netscape by holding down the shift key while left-clicking on the file names:

  3. There are two example programs to help you work with sockets: