Assignment Task: Data Structure & Algorithms Question
Some researchers are working in a lab. Due to safety regulations, only five people are allowed in the lab at the same time. The code for each researcher is given below. It uses a semaphore lab, to represent whether there is space left in the lab for more people. S1, S2 and S3 are labels identifying the line code.
Researcher code:
S1: wait(lab);
S2: work();
S3: signal(lab);
Part A: There are eight researchers, A, B, C, D, E, F, G and H, working in the lab. Each researcher 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 five researches in the lab and one or more of them leave.
- The trace should show what happens when there are five researchers in the lab and another researcher or several researchers want to enter.
The trace must start with an empty lab and show all the steps of each of the researchers as they enter/leave.
You must show the value of lab after each wait or signal step. Ensure that you state the initial value of lab.
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 Researcher process (e.g., M.S1 means that the researcher named M executed statement S1); the value of the lab semaphore (e.g., lab=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; lab=2; wait succeeded.
Part B: The code has now been modified. Each time a researcher enters the lab, an integer totalEntered is incremented. The variable is initially 0. The new code is given below:
Researcher code:
S1: wait(lab);
S2: totalEntered = totalEntered + 1;
S3: work();
S4: signal(lab);
The code given has a problem. The researchers have found that sometimes the totalEntered value does not reflect the actual number of researchers who have entered the lab.
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.