University Assignment: Concurrent and Parallel Algorithms - CTEC2910

This document presents a completed assignment for the CTEC2910 module on Concurrent and Parallel Algorithms. The solution addresses two key questions. Question 1 explores the producer-consumer problem using semaphores, focusing on the roles of full and empty semaphores in managing a conveyor belt as a buffer, and analyzing potential deadlock scenarios. Question 2 delves into a swimming pool problem, illustrating the use of counting semaphores to control access to a shared resource (the pool) and implement mutual exclusion. The solution provides detailed code analysis, examples, and explanations of the semaphore operations (wait and signal). Finally, it identifies an error in the provided code snippet related to variable initialization. The assignment concludes with a list of relevant references.

Running head: COMPUTER SCIENCE
COMPUTER SCIENCE
Name of the Student:
Name of the University:
Author Note:

1COMPUTER SCIENCE
Table of Contents
Question 1........................................................................................................................................2
Question 2........................................................................................................................................2
References........................................................................................................................................4

2COMPUTER SCIENCE
Question 1
a) The purpose of the full and empty semaphores is to make sure that the consumer does not
consume a donut as soon as the producer creates a donut and places it in the conveyor
belt. Here the conveyor belt acts as a buffer and is a critical section. The full semaphore
is used to track the number of donuts in the conveyor at any given time. The empty
semaphore tracks the number of empty slots in the conveyor. Therefore, if the empty
semaphore is removed, the process will not be able to signal the producer that a new
donut needs to be put on the conveyor belt. This would create a deadlock as no donuts
will be produced or consumed.
b) The buffer or the conveyor belt is of a fixed size. For example, take it as one. Therefore, a
producer can only produce one donut at a time for one consumer to consume. If there are
more than one consumer, then it means that more than one process (consumer) is trying
to access (eat) a single resource (1 donut). This may result in the consumers going in an
infinite loop trying to eat the donuts. To solve this, a locking mechanism can be
implemented using semaphores to put the consumers to sleep and wake them up one by
one every time the producer releases a new donut.
Question 2
a) In this problem, the swimming pool has space for four swimmers at a time and there are
six people. Here poolSpace is a counting semaphore, which holds the capacity of the pool
that is four. In line S1:wait(poolSpace), the process holds the other swimmers and lets
one swimmer enter for each iteration of the process. The semaphore value also decreases
by one each time.

3COMPUTER SCIENCE
Example: In A.S1 poolSpace value gets -1 =4-1=3.
In B.S1 poolSpace value gets -1=3-1=2
In C.S1 poolSpace value gets -1=2-1-1
In D.S1 poolSpace value gets -1=1-1=0
Once the poolSpace value reaches 0, the wait(poolSpace) functions tells the S2.swim()
function that pool is full now. The rest of the processes (swimmers E and F) are put on
sleep. Once the function completes, the line S3.signal(poolSpace) is executed for each
swimmer in the pool who exits the pool. This increases the poolSpace value by 1 each
time.
Example: In A.S3 poolSpace value gets +1=0+1=1
In B.S3 poolSpace value gets +1=1+1=2
As soon as the first swimmer get out the S3.signal(poolSpace) signals the wait function to
wake up one of the last two processes (E and F) as a new slot have become vacant. This
happens for the last process (F) too. This is how the program is executed using mutual
exclusion concept in semaphores.
b) In the code given in the problem, the fastest variable has no initial value assigned to it.
Thus when if(fastest>myTime) is executed the value returned is always false as without
initialization the value of fastest is assigned zero. For example, assume myTime as
10secs. Then in the line if(fastest>myTime), the result comes false as 0>10 is false (here
fastest=0,myTime=10). This is the only error found in this code.

4COMPUTER SCIENCE
References
Downey, A., 2016. The little book of semaphores.
Hao, X., Ming, C., Shen, Y.C. and Long, X.Y., 2017. Preliminary Analysis of Synchronization
and Mutual Exclusion of Process in Operating System. Int J Signal Process Anal, 2(003).
Khandelwal, M.K., Chandnani, M. and Sharma, M., 2016, October. CSMA/CA channel
synchronization using semaphore. In 2016 2nd International Conference on Next Generation
Computing Technologies (NGCT) (pp. 13-20). IEEE.
Marmorstein, R., 2015. Teaching semaphores using... semaphores. Journal of Computing
Sciences in Colleges, 30(3), pp.117-125.