Question 1 (40 marks) A cake shop provides a stream of cakes for customers. Cakes are made by a chef in the kitchen and

[answerhappygod]

Question 1 (40 marks) A cake shop provides a stream of cakes for
customers. Cakes are made by a chef in the kitchen and placed on a
conveyor belt. The conveyor belt carries the cakes 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 infinite
size, where each space in the array can hold one cake. In this
scenario, there are multiple chefs.
The pseudo-code for the chef is as follows.
1. while(true){
2. cake = makeCake(); // Create a cake
3. wait(empty);
4. conveyor[in] = cake; // Put the cake on the conveyor belt
5. in = (in + 1) mod n;
6. }
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) (20 marks) The pseudo-code for the chef has an error(s).
Propose the solution by giving the correct code.
(b) (20 marks) Now assume that there is a single chef and a
single customer, with a conveyor belt of finite size. Give the
pseudo-code for this scenario, both for the chef and customer.
CTEC2910 Concurrent and Parallel Algorithms Sheet 5 of 7
Question 2 (60 marks) There is a self-service passport control
that has three scanning devices, so only three passengers can scan
their passport at the same time. The code for each passenger is
given below. It uses a semaphore passport, to represent whether
there is space left in the passport control for more passengers.
S1, S2, and S3 are labels identifying the line code.
Passenger code:
S1: wait(passport);
S2: scan();
S3: signal(passport);
(a) (40 marks) There are five passengers, A, B, C, D, and E that
want to scan their passport. Each passenger 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
three passengers in the passport control and one or more of them
leave.
• The trace should show what happens when there are three
passengers in the passport control and another passenger, or
several passengers want to scan their passport.
The trace must start with an empty passport control and show all
the steps of each of the passengers as they enter/leave.
You must show the value of passport after each wait or signal
step. Ensure that you state the initial value of passport.
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 Passenger process (e.g., M.S1
means that the passenger named M executed statement S1); the value
of the passport semaphore (e.g., passport=2); whether the wait
succeeded or was placed in the queue/ whether the signal changed
the semaphore value or a sleeping process woke up.
For example: M.S1; passport=2; wait succeeded.
(b) (20 marks) The code has now been modified. Each time a
passenger uses a scanning device, an integer totalScanned is
incremented. The variable is initially 0. The new code is given
below:
Passenger code:
S1: wait(passport);
S2: totalScanned = totalScanned + 1;
S3: scan();
S4: signal(passport);
The code given has a problem. The passengers have found that
sometimes the totalScanned value does not reflect the actual number
of passengers who have entered the passport control.
• 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.