Design and Use of Concurrent Algorithms

Sushi Shop Scenario

This assignment has TWO (2) parts with a total 100 marks, which will constitute 60% of your final mark for the module. Answer both parts.

The objective of this assessment is for you to demonstrate your understanding of issues related to the design and use of concurrent algorithms.

Submit your work as a single Word document or pdf document through the portal available on Blackboard. Write your answers to the questions in the Word or pdf document.

DO NOT submit any code, either as separate files or within your document. Any code submitted will not be marked.

Please refer to the marking grid provided.

The assignment will be marked anonymously. You will compromise this anonymity if you put your name on the work. Please include your p-number on your assignment.

A sushi shop provides a stream of sushi for customers. The sushi are made by a chef in the kitchen and placed on a conveyor belt. The conveyor belt carries the sushi to where the customers are waiting to buy them.

This scenario has been simulated using two processes: the chef and the customer, and a shared conveyor belt implemented as an array called conveyor with finite size, where each space in the array can hold one sushi. In this scenario, there is only a single chef and a single customer.

This code should be familiar to you as it is similar to the example of the Producer-Consumer problem. Only a few sentences are required for each of the questions below.

(a) The pseudo-code for the chef has an error. Propose the solution by giving the correct code and explain the reason in few sentences.

(b) Give the pseudo-code for the customer.

(c) Now assume that there is a single chef and a single customer, with a conveyor belt of infinite size. Give the pseudo-code for this scenario, both for the chef and customer.

Question 2 (60 marks)

There is a self-service car wash that has four washing places, so only four drivers can wash their car at the same time. The code for each driver is given below. It uses a semaphore carwash, to represent whether there is space left in the car wash for more drivers. S1, S2, and S3 are labels identifying the line code.

Driver code:

S1: wait(carwash);

S2: wash();

S3: signal(carwash);

There are six drivers, A, B, C, D, E, and F that want to wash their car. Each driver operates according to the above code. Your task is to give an execution trace that contains both of the following:

• The trace should show what happens when there are less than four drivers in the car wash and one or more of them leave.

• The trace should show what happens when there are four drivers in the carwash and another driver, or several drivers want to enter.

The trace must start with an empty car wash and show all the steps of each of the drivers as they enter/leave.

You must show the value of carwash after each wait or signal step. Ensure that you state the initial value of carwash.

If a wait operation executes, indicate whether the process succeeds or is placed in the queue. If a signal operation executes, indicate whether the value is changed, or a sleeping process is woken up.

Each line of your trace should have the following format:

Statement executed including which Driver process (e.g., M.S1 means that the driver named M executed statement S1); the value of the carwash semaphore (e.g., carwash=2); whether the wait succeeded or was placed in the queue/ whether the signal changed the semaphore value or a sleeping process woke up.

The code has now been modified. Each time a driver enters the car wash, an integer totalEntered is incremented. The variable is initially 0. The new code is given below: Driver code:

S1: wait(carwash);

S2: totalEntered = totalEntered + 1;

S3: wash();

S4: signal(carwash);

The code given has a problem. The drivers have found that sometimes the totalEntered value does not reflect the actual number of drivers who have entered the car wash.

• Explain, in words, how this situation could occur.

• Show a trace that demonstrates the problem occurring. Note that you are not being asked to solve the problem.