Concurrent Systems examination 23.8.2002 ############################################################################### 1. Give a precise description for the following concepts related with the control of concurrent processes: a) a critical section b) synchronization c) rendezvous. Illustrate each concept by examples based on the following case: one process writes into a (multislot) buffer, and two processes read from it. (You need not write the algorithm - but you may, if it helps your explaining.) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ The essential points: a) Only one process at a time allowed b) A process is allowed to pass a synchronization point only after some specified event has taken place (in a basic two-process synchronization one process "signals", the other "waits"; the concept is also used as a rather high-level "umbrella" concept covering various more specific coordination needs) c) Two (or more) active processes wait until (all) the other(s) have reached the "synchronization point" (e.g., barrier synchronization, "the sleeping barber") For a more detailed treatment: see the textbook ################################################################################ 2. Present a solution for the "sleeping barber" problem. Use the monitor concept with the following specifications: - the signaling discipline is of the type Signal and Continue - the scheduler assumes that a signaled process has a higher priority than a "new" process, which is first trying to activate a monitor operation (hence, in the "entry" queue all the signaled processes precede the "new" processes). The solution should be as simple as possible: there will be only one barber, no unnecessary condition checking is done neither any unnecessary wait - signal synchronizations. Explain briefly why your solution works correctly. (The solution presented in the textbook is too complicated, repeating it as it is will give you about 8 (out of 15) points.) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Original version: see Andrews Chapter 5.2.5 A short version, based on - signal and continue -mode - one server (without any idea to hire more of them) The monitor procedures are as follows: procedure get_haircut() { while (barber==0) wait(barber_available); barber = barber - 1; signal(chair_occupied); wait(door_open) signal(customer_left); } procedure get_next_customer() { barber = barber + 1; signal(barber_available); wait(chair_occupied); } procedure finished_cut() { signal(door_open); wait(customer_left); } Usage: see the textbook. Essential: check that you understand why it works! Note: if the clients must wait outdoors then the solution is essentially simpler (but this is *against* the specification of the problem) Notice: signal is "memoryless" (if the cond queue is empty => no operation) ################################################################################ 3. A narrow bridge leads over a river. Cars coming from the same direction can cross the bridge at the same time, but cars heading in opposite direction cannot. Model the cars as processes and the traffic-light controller as a multithreaded process. Write a solution for the problem using remote procedure calls (a remote procedure is executed by a thread, invoked by the procedure call). The solution need not be fair (cars are allowed to wait even for very long times). +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Process traffic-light_controller { sem mutexE = 1, mutexW = 1, waiting_cars = 1; int nE = 0, nW = 0; op enter_east(), exit_east, enter_west, exit_west; procedure enter_east() { /* a request invokes a thread to execute this code */ P(mutexE); nE = nE + 1; if (nE == 1) P(waiting_cars); /* if the bridge was empty - the semaphore was open - now it is closed: - eastbound don't check - westbound cars stop: - 1st: light_westbound - next: mutexW if the bridge was not empty - there were westbound cars on it (nE was 0) - the first eastbound car stops here - the following ones will wait in mutexE */ V(mutexE); } procedure exit_east() { P(mutexE); nE = nE - 1; if (nE == 0) V(waiting_cars); # work out the different cases V(mutexE); } ... } process car[*] { ... drive to the bridge; # this car goes to east call traffic-light_controller.enter_east(); cross the bridge; call traffic-light_controller.exit_east(); proceed to east; } Notice: - each call is executed by a separate thread in the controller => - mutual exclusion is needed - this serving thread is the one who waits in a semaphore (the car waits for a "reply" from the procedure) - the last x-bound car must wake up the whole y-bound queue; this solution starts the first one ane the others follow "automatically"; this could be done more explicitly (the code is perhaps more readable) ############################################################################### 4. For the deadlock avoidance you can use the "banker's algorithm": before a resource unit is allocated the resource manager first checks that the allo- cation cannot result into a deadlock situation. a) Explain, at a functional level, the working of this algorithm. b) Simulate the working of the algorithm in the following case. The system contains three different types of resources: A, B, and C. There are 9 units of A, 3 units of B, and 6 units of C. The system is in the following state: process allocated maximum demand for processes of processes A B C A B C P1 1 0 0 3 2 2 P2 5 1 1 6 1 3 P3 2 1 1 3 1 4 P4 0 0 2 4 2 2 The process P2 requests for one additional unit of A and one of C. Can they be allocated? What if the request had been made by P1? ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a) See the textbook Essential: before allocating the requested resources the algorithm verifies that (after the allocation) there exists at least *some* execution path (order of resource allocations to the processes) even in the "worst case" (before finishing each process wants to have its maximal resources). The requirement, that the process under consideration should be the first one to finish, is too strict. A denial of allocation does not mean that the process would have any serious troubles - it just has to wait until the allocation can be done (the original state was safe -> the process will eventually receive the requested resources). Allocating the resources against the will of the banker does not necessarily lead to a deadlock (other processes may finish without requesting any more resources, for example). ###############################################################################