C2910 Concurrent and Parallel Algorithms: Homework Assignment

This document presents a comprehensive solution to a Concurrent and Parallel Algorithms assignment (C2910). The solution addresses key concepts such as the use of the mod n statement for calculating available space in a conveyor, and the role of mutexes in handling critical sections and preventing collisions between bakers and customers. It analyzes the importance of semaphore order in customer processes, discussing the implications of changing the order of wait and signal operations. The solution further explores the impact of an infinite buffer size on the baker-customer scenario. Furthermore, the document provides an execution trace of researcher code, detailing the behavior of researchers entering and exiting a lab, and analyzes a modified code version that calculates the total number of researchers, highlighting potential issues related to the accuracy of this count. The assignment includes a bibliography of relevant sources.

Running Head: CONCURRENT AND PARALLEL ALGORITHMS C2910
CONCURRENT AND PARALLEL ALGORITHMS C2910
Name of the Student
Name of the University

1CONCURRENT AND PARALLEL ALGORITHMS C2910
Question 1
(a) The main purpose of the mod n statement is to calculate available space in the
conveyor. In this statement n is the divisor. In the above example, mod n is used to modulo
division a variable with n where n is the total number of buffer or the size of the buffer. In
general, the mod is used to perform modulo operation which helps to find the reminder.
The main purpose of mutex buffer_mutex is to handle a critical section by identifying
only one baker or customer can access the critical section. Mutex is the object of mutual
exclusion which helps to synchronise the use of resources and also helps to manage the flow of
the process. According to the scenario, buffere_mutex solve the problem of a collision between
baker and customer. Buffer_mutex always take cares of only one baker or customer can access
the critical section, for example, if the baker is producing muffins at that time customer not able
to buy any muffins and similarly if the customer buying muffins at that time bakers are not
allowed to produce. Buffer_mutex solve the problem of a collision that means the baker and
customer never collapsed between each other and the both of them perform their task without
any problem
(b) If the order of semaphores in the customer process changed then the customer never
get any muffins or the customer never get the access of critical section. The order of semaphore
is very important because it helps process, or threads to complete its execution without any
problem. As per the above scenario, the customer waits until the baker produces muffins then the
customer able to buy muffins. Customer buys muffins from the conveyor and when the conveyor
gets empty, it sends a signal to the baker that the conveyor is empty. Then again the baker
appends muffins to the conveyor. If the order of wait (full) and signal (empty) changed then

2CONCURRENT AND PARALLEL ALGORITHMS C2910
customer always sends a signal to the baker that the conveyor is empty and the customer never
gets any process and the baker send a signal that the conveyor is empty and the process is in a
deadlock situation.
According to the scenario, there is a bounded buffer available for the critical section but
if the available buffer is set to infinite with a single baker and single customer, then the given
solution of baker and customer have to modify to fulfil all the requests. In this scenario of a
single producer and single customer with an infinite buffer then the baker can make an infinite
number of muffins and place to conveyor but the customer has to wait to buy muffins until the
new item is not placed into conveyor and baker can make muffins always because the size of the
buffer is infinite. The customer has to wait in the initial time of execution until the baker makes
muffins. In this scenario baker sends a signal to the customer that there is a muffin available then
the customer can buy muffins.
Question 2
a) The execution trace of the given researcher code:
Initial value of Lab=0; initially lab is empty and waiting for the researchers to enter the
lab
A.S1; Lab=1; Lab<=5 wait statement succeeded
A.S2; A started work;
B.S1; Lab=Lab+1; Lab<=5 wait statement succeeded
C.S1; Lab=Lab+1; wait succeeded, and the number of researchers increases to 1

3CONCURRENT AND PARALLEL ALGORITHMS C2910
C.S2; B.S2; B and C started their work
Lab=3 Lab is empty for 2 researchers
D.S1; E.S1; Lab=Lab+2; wait succeeded because Lab<=5
D.S2; E.S2; Started work; Lab=5 Lab is full
F.S1; Lab=5; wait not succeed and F sends to queue for waiting
B.S3; Lab=Lab-1; Signal succeeded
F.S1; Lab=Lab+1; wait succeeded because of Lab<=5
F.S2; F started working
C.S3; D.S3; Lab=Lab-2 Both C and D exits at the same time; Signal succeeded;
G.S1; Lab=Lab+1; wait succeeded
Lab=4
H.S1; Lab=Lab+1; wait succeed because Lab<=5
Lab=5; Lab full
b) The modified code has a new line which calculates the total number of the researchers
in the lab and the initial value is set to 0. Every time a researcher enters the lab the
totalEntered value is increased by 1. But in this code, there is some problem which is
noticed by the researches that sometimes the value of totalEntered is not reflected.
This problem occurs due to every time a researcher enters the lab the value of

4CONCURRENT AND PARALLEL ALGORITHMS C2910
totalEntered is increased by one, but whenever a researcher exits from the lab, the
value of totalEntered remains the same. Such problems occur in the modified code.
Execution Trace of modified code:
Initial value of Lab=0; initially lab is empty and waiting for the researchers to enter the
lab
A.S1; Lab=1; Lab<=5 wait statement succeeded
totalEntered= totalEntered + 1
A.S2; A started work;
B.S1; Lab=2; Lab<=5 wait statement succeeded
totalEntered= totalEntered + 1
C.S1; Lab=3; wait succeeded
totalEntered= totalEntered + 1
C.S2; B.S2; B and C started their work
Lab=3; totalEntered=3; Lab is empty for 2 researchers
D.S1; E.S1; Lab=5; wait succeeded because Lab<=5
totalEntered= totalEntered + 2
D.S2; E.S2; Started work; Lab=5 Lab is full
F.S1; Lab=5; wait not succeed and F sends to queue for waiting

5CONCURRENT AND PARALLEL ALGORITHMS C2910
A.S3; Lab=Lab-1; Signal succeeded
totalEntered= 5

6CONCURRENT AND PARALLEL ALGORITHMS C2910
Bibliography
Capel, M. I., Tomeu, A. J., & Salguero, A. G. (2017). Teaching concurrent and parallel
programming by patterns: An interactive ICT approach. Journal of Parallel and
Distributed Computing, 105, 42-52.
Lamport, L., 2019. The mutual exclusion problem: Part II---Statement and solutions.
In Concurrency: the Works of Leslie Lamport (pp. 247-276).
Wang, K.C., 2015. Process Synchronization. In Design and Implementation of the MTX
Operating System (pp. 175-214). Springer, Cham.
Sun, Y., & Blelloch, G. (2019, February). Implementing parallel and concurrent tree structures.
In Proceedings of the 24th Symposium on Principles and Practice of Parallel
Programming (pp. 447-450).