COMP3151/9154 Homework 3

Submission: Please put all your answers in one PDF file. Use of LaTeX is encouraged but not required. Please make your answers as concise  as possible. This homework should not be more than a few pages.  See the course Moodle page for the submission location. Late submissions will not be accepted. Solu- tions to this homework will be discussed in the tutorial immediately following the due date, and your participation mark will depend on your ability to present your answer if called upon in the tutorial.

1. In the Promela code for mutual exclusion protocols under Week 4 on Moo- dle, you will find Szymanski’s algorithm for three processes, broken down to satisfy LCR, with a particular choice of test order for the various await statements. This choice happens to satisfy mutual exclusion and eventual entry (as you may check in Spin), but as mentioned in the lectures, not all choices do.

The task here is to twiddle with the test orders and figure out which orderings break the algorithm and which don’t. You don’t need to test all permutations, but do answer these questions:

Can you find any reorderings that break mutual exclusion and/or eventual entry?  (You should be able to find at least one).  Are there any awaits that don’t seem sensitive to reordering at all?  What if you reorder the tests for all the awaits in the exact same way? And finally, based on any error trails you obtain, can you form an educated guess about *why* the test order matters?

Explain your findings, informally and in your own words.

2.  Download the Homework4 code.  To avoid name conflicts,  signal  is here called V () and wait is called P().

Cigarette  Smokers  Problem:   Three  smokers  are  rolling  their  own cigarettes and smoking them.  In order to do so, they need three resources: paper, tobacco, and matches. Each smoker has their own limitless supply of one of the three ingredients.  For the other two ingredients, they must acquire them from anemphAgent. They can ask for an Agent to distribute resources to them by signalling on the agent semaphore.  One of the Agent threads will then awaken, and produce two of the three different resources by signalling on two of the three semaphores tobacco, paper  and  match. Note that the smoker has no control over which Agent  thread awakens and which resources are produced.

The existing code where smokers get resources directly from the agents is highly vulnerable to a deadlock scenario.  In this exercise, we will im- plement a solution to this problem that ensures progress by introducing a ”middle-man” between the agents and smokers.

.  Step One ::  Introduce a dedicated semaphore for each smoker, and the smoker will just wait on that semaphore, smoke a cigarette, and signal an agent forever.

.  Step  Two  ::   Add  a  thread  called  a  pusher  for  each  of  the  three resources. The pusher will perpetually:

(a) Wait for its resource to become available.

(b)  Update some shared state  (shared with the other pushers) re- garding what resources are available.

(c) If two of the three resources are available, update the shared state to remove those resources, and signal the smoker that re- quires those two resources, to indicate that they may smoke the cigarette.

Caution :: You must make the loop body of the pusher a critical section - mutual exclusion is required when accessing the shared state. You can accomplish this by adding another semaphore for the pushers to use.

3.  Semaphores with Monitors

In  the  ProducerConsumer  module  you  will  find  an  implementation  of the  Producer-Consumer  problem we  analysed  in  class.   This  (and  the Cigarette  Smokers  example  from  earlier)  use  a  semaphore  class  called JavaSemaphore  that wraps around Java’s built-in semaphores.  We have two other classes, Busy WaitSemaphore and WeakSemaphore, without im- plementations added.

.  Step One :: Using only Java’s built-in concurrency primitives, specif- ically synchronized blocks/methods and Thread.yield(), implement a busy-wait semaphore in Busy WaitSemaphore.  You can test it using ProducerConsumer or CigaretteSmokers.

.  Step Two ::  Using  only  Java’s built-in concurrency primitives  and  monitor-like constructs, specifically synchronized blocks, Object.wait() and Object.notify(), implement a weak semaphore in WeakSemaphore.  You can test it using the same examples.