Sample Synchronization ProblemsCS 414/415, Spring 2001Emin Gün Sirer1. You have been hired to coordinate people trying to cross a river. There is only a single boat, capable ofholding at most three people. The boat will sink if more than three people board it at a time. Each personis modeled as a separate thread, executing the function below:Person(int location)// location is either 0 or 1;// 0 = left bank, 1 = right bank of the river { ArriveAtBoat(location); BoardBoatAndCrossRiver(location); GetOffOfBoat(location); } Synchronization is to be done using monitors and condition variables in the two proceduresArriveAtBoat and GetOffOfBoat. Provide the code for ArriveAtBoat and GetOffOfBoat.The BoardBoatAndCrossRiver() procedure is not of interest in this problem since it has no role insynchronization. ArriveAtBoat must not return until it safe for the person to cross the river in thegiven direction (it must guarantee that the boat will not sink, and that no one will step off the pier into theriver when the boat is on the opposite bank). GetOffOfBoat is called to indicate that the caller hasfinished crossing the river; it can take steps to let other people cross the river. Boatlocation = 0; // 0 for left bank, 1 for rightBoatcount = 0;ConditionVariable Boatarrived, boatfull;Monitor ArriveAtBoat(int location){ while(true) {if(boatlocation == location && boatcount < 3) {boatcount++;if(boatcount < 3) Condition.wait(boatfull);ElseCondition.broadcast(boatfull);return;} else {Condition.wait(boatarrived);}} } Monitor GetOffOfBoat(int location){ --boatcount;if(boatcount == 0) {// we arrived on the other side, update boat directionboatlocation = not location;Condition.broadcast(boatarrived);}} 1Note that this solution may lead to starvation. The readers is encouraged to develop a starvation-free solution. 2. Ping and pong are two separate threads executing their respective procedures. The code below isintended to cause them to forever take turns, alternately printing “ping” and “pong” to the screen. Theminithread_stop() and minithread_start () routines operate as they do in your projectimplementations: minithread_stop() blocks the calling thread, and minithread_start ()makes a specific thread runnable if that thread has previously been stopped, otherwise its behavior isunpredictable. void ping() { while(true) { minithread_stop(); Printf(“ping is here\n”); minithread_start(pongthread); } } void pong() { while(true) { Printf(“pong is here\n”);minithread_start(pingthread);minithread_stop(); } } a. The code shown above exhibits a wellknown synchronization flaw. Briefly outline a scenario in whichthis code would fail, and the outcome of that scenario. b. Show how to fix the problem by replacing the minithread_stop and start calls withsemaphore P and V operations. c. Implement ping and pong correctly using a mutex and condition variables.Sema sping, spong = sema_init(0);void ping() { while(true) { P(sping); Printf(“ping is here\n”); V(spong); } } void pong() { while(true) { Printf(“pong is here\n”);V(sping);P(spong); } 2} Mutex m;bool turn;ConditionVariable cond;void ping() { mutex.lock(m);while(true) { if(turn == true) {Printf(“ping is here\n”);turn = false;}Condition.signal(cond);Condition.wait(cond, m);} } void pong() { mutex.lock(m);while(true) { if(turn == false) {Printf(“pong is here\n”);turn = true;}Condition.signal(cond);Condition.wait(cond, m);} } 3. You are designing a data structure for efficient dictionary lookup in a multithreaded application. Thedesign uses a hash table that consists of an array of pointers each corresponding to a hash bin. The arrayhas 1001 elements, and a hash function takes an item to be searched and computes an entry between 0 and1000. The pointer at the computed entry is either null, in which case the item is not found, or it points to adoubly linked list of items that you would search sequentially to see if any of them matches the item youare searching for. There are three functions defined on the hash table: Insertion (if an item is not therealready), Lookup (to see if an item is there), and deletion (to remove an item from the table). Consideringthe need for synchronization, would you: 1.Use a mutex over the entire table? 2.Use a mutex over each hash bin? 3.Use a mutex over each hash bin and a mutex over each element in the doubly linked list? Justify your answer. Answer: A mutex over the entire table is undesirable since it would unnecessarily restrict concurrency.Such a design would only permit a single insert, lookup or delete operation to be outstanding at any giventime, even if they are to different hash bins. A mutex over each element in the doubly linked list wouldpermit the greatest concurrency, but a correct, deadlock-free implementation has to ensure that allelements involved in a delete or insert operation, namely, up to three elements for an delete, or twoelements and the hash bin for inserts/some deletes, are acquired in a well-defined order. A mutex overeach hash bin is a compromise between these two solutions – it permits more concurrency than solution 1,and is easier to implement correctly than solution 2.34. A car is manufactured at each stop on a conveyor belt in a car factory. A car is constructed from thefollowing parts - chassis, tires, seats, engine (assume this includes everything under the hood and thesteering wheel), the top cover, and painting. Thus there are 6 tasks in manufacturing a car. However, tires,seats or the engine cannot be added until the chassis is placed on the belt. The car top cannot be addeduntil tires, seats and the engine are put in. Finally, the car cannot be painted until the top is put on.A stop on the conveyor belt in your car company has four technicians assigned to it - Abe, Bob, Charlie,and Dave. Abe is skilled at adding tires and painting, Bob can only put the chassis on the belt, Charlieonly knows how to attach the seats, and Dave knows how to add the engine as well as how to add the top.Write pseudocode for Abe, Bob, Charlie and Dave to be able to work on the car, without violating the taskorder outlined above. You can use semaphores, mutexes or monitors in your solution.5. Write a simulator for Dragon Day, where each architect and engineer is modeled as a separate threadexecuting their respective functions.void initsimulator() {// TODO:
View Full Document
Unlocking...