CSCI.6500/CSCI.4500 Distributed Computing over the Internet

Spring, 2017

Programming Assignment 1.

This project is to be done individually or in pairs. Do not show your code to any other student/group and do not look at any other student/group's code. Do not put your code in a public directory or otherwise make it public. You are encouraged to use the LMS Discussions page to post problems so that other students can also answer and see the answers.

The goal of this assignment is to practice concurrent and distributed programming using the Pict programming language.

Consider the following experimental aviators setting: A hangar holds 2n engines, 2n fuselages, and 2n propellers (for n>=1 in Z.) There are 3n aviators that want to build and fly airplanes. An experimental aviator picks up an engine, a fuselage, and a propeller, builds an airplane, flies it, and then takes it apart into each of its components putting them back in the hangar, and starts all over again.

Part 0 - Experimental Aviators Problem

You are to create a program in Pict that will demonstrate that deadlock may occur.  That is, you are to create a program in which aviators will eventually be waiting for ever after all pick up some components of their airplanes, with none being able to make progress.

Algorithm for each aviator:

Loop forever {
       
  Pick up an engine if available.
  Pick up a fuselage if available.
  Pick up a propeller if available.
  If you are missing a component, pick it up when released.
  If you have the three components, build the plane, and fly it.
  Land, take the plane apart, and release the components back on the hangar. }
The main problem is that without some kind of coordination the aviators could make no progress when each has two of the three plane components and is waiting for the third component to be released by the other aviators.

Part 1 - Experimental Aviators Solution

A solution (described by Hoare in the context of dining philosophers and adapted to the experimental aviators problem) adds the requirement that at most 3n-1 aviators are allowed to enter the hangar at once.  This ensures that at all times, at least two aviators can fly, so there are no deadlocks. This solution assumes there is a bouncer that does not allow an aviator to enter the hangar if there are already 3n-1 aviators inside.  You are to write a program simulating this solution.  Your program should generate verbose output explaining what is happening.

Part 2 - Avoiding Deadlock and Reasoning about Fairness

Submission:

The due date for this project is March 22, 2017, 6pm EST. You should use the assignments drop-off box located at the course's LMS page. Upload a ZIP file containing all the relevant documented Pict files, along with a README file describing the project and its usage.