Finding issues in concurrent implementation of carpark overflow control

Question

Firstly, I am revising for my Concurrent Programming exam and have come across the following question from a previous exam paper. I have attempted to answer it, and will try and convey this effort; I'm very stuck with this question and not sure how to further progress.

Question

This question is from a 2011 Past Paper from my University created by the Examining Body that year. Examiners: Professor E K Burke Dr P Sage and the internal examiners

A car park has 100 parking spaces. Because of building work max cars must be accommodated in an overflow area which is accessed via the main car park. Entrance to the main and overflow areas is controlled by two automatic barriers as follows.

• When the car park is empty both barriers are closed.

• Normally, the main barrier is raised as a car approaches and is lowered immediately the car has entered.

• An exception occurs immediately after the main car park is full i.e. when it has 100-max cars in it. As the next car approaches the overflow barrier is raised first, then the main barrier is raised. Once the car has entered the main car park the overflow barrier remains raised and the main barrier is lowered. The normal main barrier action described above then resumes.

Consider the following program which is intended to control the two barriers.

All instructions, o1, o2, o3, m1, m2, m3 and m4, are atomic. You may assume that $0 < \max \leq 100$.

int #cars=0;

process Main {
while (true)
 {
 m1: <#cars++>;
 m2: <openMainBarrier>;
 m3: <closeMainBarrier>;
 m4: <if (#cars==100)
     break>;
 }
}

process Overflow {
int max; 
o1: <input(max)>;
 while (true) 
 {
   o2: <if (#cars==100-max+1)  break>; 
   o3: <openOverflowBarrier>; 
 }
}

1. The program terminates only if both processes terminate. Explain why the program may not terminate.

2. Explain why, even if the program does terminate, it may not operate as specified.

3. By introducing the use of semaphores, ensure that program does terminate and operates as specified. You must only use atomic instructions. You may introduce new additional non-semaphore variables but you must not alter the scope of #cars and max.

My attempt

Most semaphore exercises I have looked at so far often have the main process in a while(true){...} infinite loop, thus, termination has never been an issue before - it is normally not addressed in these short exercises.

It is because of this I am having difficulty trying to produce an answer for 2) and 3). The question does not even appear to address cars leaving the car park, which leads me to understand this isn't an infinite ongoing cycle type process, but will terminate when both car parks reach maximum capacity?

In this instance, the only thing I can think of is that the process will not terminate in the event the main carpark or overflow carpark does not reach capacity, however I feel this answer is not 'clever' enough and I'm worried I may be missing something.

I have attempted 3) as follows but I am worried this is incorrect as I'm not sure if I am supposed to handle cars leaving the car park, or if I am supposed to ignore that in order to force it to terminate.

OverflowCarPark{
int max;
<input (max)>
while(true){
 down(maxFull)
 if(#cars <= 100 + max){
    down(openMainBarrier)
    up(openOverflowBarrier)
 }
  else { break; }
}

MainCarPark{
<cars++;>
while(true){
 if(#cars <= 100){
    up(openMainBarrier)
  } else if (#cars > 100 + max) { break; 
  } else { 
    up(maxFull);
    down(openOverflowBarrier);
 }
}

What is the recommended approach to dealing with termination here?

Answer 1

For the first task think about what might happen, if the loop in Overflow is not run for each car.

For the second task, look at the following things:

• How is the opening and closing of bars linked to arriving cars?
• Does the overflow bar really open at the $100-\max$-th car?
• The specification requests a specific order of opening and closing the bars. Is this enforced?

In the third task you should address the problems identified in the first two tasks by adding semaphores and possibly additional variables and atomic operations to the code.

Concerning your attempt and the questions therein:

• The setting as described assumes that no car leaves the car park.
• You may assume that eventually 100 cars will have arrived. (Otherwise you could not ensure termination.)
• You should mostly keep the operations m1-m4 and o1-o3 (depending on your approach you might change one or two of them). Just add additional code around and inbetween them, in order to address the problems.
• You use $100+\max$ twice, where you probably intended to use $100-\max$.
• Using max in Process Main is changing its scope, since in the original code it is a variable local to Process Overflow.
• Also your code does not solve most of the problems I hinted at for task 2. (This is no surprise, given that you had not identified them, when writing the code.)