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.

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?