Concurrent and Parallel Algorithms
Question 1
A doughnut shop has to provide a steady stream of doughnuts for customers. The doughnuts are made by a chef in the kitchen and placed on a conveyor belt. The conveyor belt carries the doughnuts 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 a circular array called conveyor, where each space in the array can hold one doughnut. There are two shared general semaphores, empty and full. In this scenario, there is only one chef and one customer. The pseudo-code for the chef is as follows. The chef makes use of an integer variable in for noting the next available space on the conveyor belt. while(true){ doughnut = makeDoughnut(); // Create a doughnut. wait(empty); conveyor[in] = doughnut; // Put the doughnut on the conveyor belt. in = (in + 1) mod n; signal(full); } The pseudo-code for the customer is as follows. The customer makes use of an integer variable out for noting the next location on the conveyor belt that contains a doughnut. while(true){ wait(full); doughnut = conveyor[out]; // Get a doughnut from the conveyor belt. conveyor[out] = null; out = (out + 1) mod n; signal(empty); eat(doughnut); // Eat the doughnut. } This code should be familiar to you as it is an example of the Producer-Consumer problem. (a) Explain, in words, the purposes of the empty and full semaphores.
Explain what would happen if the empty semaphore was not there, and for what kind of scenario this would apply to. You may wish to include simple examples.
#Explain #happen #empty #semaphore
