Concurrent Systems examination 13.12.2002 ############################################################################### 1. Give a short answer to each of the following questions: a) What is "barrier synchronization"? How does it differ from the customary "PV-synchronization"? b) What is the use of having a buffer between a producer and a consumer? How does the length of the buffer affect the performance of the system? c) An implementation (of b) can be based on 1) semaphores, 2) a monitor, 3) a buffer manager using message passing, 4) remote procedures. How does each of these implement customer waiting? Who (what) waits? Where? What does it wait for? (In your explanation, use the concepts of the method, the operating system is of no concern here.) (a: 3, b: 2, c: 8) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a) The customary "PV-synchronization" is not symmetric: a process B checks before continueing that a process A has passed a certain point (but B's execution has no effect whatsever on A's execution). In barrier synchro- nization *all* involved processes must arrive at "the barrier" before anybody is allowed to continue. b) Without a buffer the producer and the consumer must get synchronized to allow a data transfer to take place. A longer buffer is beneficial in cases where the execution rates of the producer and consumer vary: larger variability => longer buffer. If either one is continuosly faster then using a longer buffer becomes counterproductive (why?). c) Semaphores the consumer process waits in a semphore for a V-operation performed by the producer Monitors the consumer process waits in a condition ... Managers the consumer process waits in a "receive" statement (there is a semaphore somewhere inside); the operation waits in a channel that the manager reads the message (using a "receive") RPC the consumer process waits for the procedure call to be completed (more specifically: the process is executing the stub code and waits there in a semaphore for the return message from the server's stub); the processes which execute the (remotely called) procedures wait in their corresponding semaphores (see the traditional solution). ############################################################################### 2. a) The operating system supports only binary semaphores (the counter of the semaphore can only take values 1 and 0). Write the code for the procedures P_general(count,sema) and V_general(count,sema). These are application- level procedures, which implement PV operations on general semaphores. The parameter "count" is an integer, to be used as the counter of the general semaphore; the parameter "sema" is a binary semaphore, which is used to implement the semaphore functionality of the general semaphore (P_general and V-general behave in the same way as the P and V of the textbook; it is the responsibility of the programmer to declare and initialize the necessary counters and binary semaphores, and to use in the procedure calls counters and binary semaphores which belong together). Notice that for delaying and releasing processes you have to use the existing PV operations (and not any internal functions of the operating system). b) Justify the correctness of your solution (level of explanation: how you should tell it to a fellow student - but in a rather concise way). (a: 9p, b: 4p) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ procedure P_general(count,sem) { P(mutexPV); count = count - 1; if (count < 0) { V(mutexPV); P(sem); } V(mutexPV); } procedure V_general(count,sem) { P(mutexPV); count = count + 1; if (count <= 0) V(sem); else V(mutexPV); } ############################################################################# 3. "Merry-go-round". Suppose there are n customer processes and one vehicle process. The customers repeatedly wait to take rides in the vehicle, which can hold C customers (C < n). However, the vehicle is started for a ride only when it is full. After each ride all customers continue with other activities. The control of the vehicle is implemented using the monitor MGR_cntrl. The customer routine is "while (true) {various_activities; call MGR_cntrl.enter;}"; the vehicle routine "while (true) call MGR_cntrl.load; make_the_tour; call MGR_cntrl.unload". Develop code for the monitor routines (use the signal-and-continue discipline). (13p) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Solution 1: The main control is in "enter" monitor MGR_cntrl { # the routines for merry_go_round int sitting = 0; # number of passengers # waiting places ... cond driving_time, # ... for the MGR process filling_time, # ... for waiting customers exit; # ... for driving customers procedure enter() { # used by customers while (sitting = C) # if the vehicle is full, wait wait(filling_time); # after wakeup: recheck! sitting = sitting + 1; if (sitting = C) # the last customer ... signal(driving_time); # ... wakes the driver up wait(exit); # wait until the ride has finished } # end of enter procedure load() { # used only by the merry_go_round if (sitting < C) # (no need for a "while"! why?) wait(driving_time); # wait until the system is full } # end of load procedure unload() { # used only by the merry_go_round signal_all(exit); # release the customers sitting = 0; signal_all(filling_time); # waiting customers may enter } # end of unload } # end of monitor ++++ Solution 2: The main control is in "load" monitor MGR_cntrl { int sitting = 0; cond customer, entrance, exit; procedure enter() { signal(customer); wait(entrance); wait(exit); } procedure load() { while (sitting < C) { if (!empty(entrance)) { signal(entrance); sitting = sitting + 1; } else wait(customer); } } procedure unload() { signal_all(exit); sitting = 0; } Check that this solution is correct! Notice that a customer may arrive when the M-G-R process is waiting, executing "load", or executing "unload", and notice that a customer may see an entrance queue which is empty, short or "long" (longer than C). +++ Solution 3: signal_all is not available: monitor MGR_cntrl { # the routines for merry_go_round int sitting = 0; # number of passengers # waiting places ... cond driving_time, # ... for the MGR process filling_time, # ... for waiting customers exit; # ... for driving customers procedure enter() { # used by customers while (sitting = C) # wait if the vehicle is full wait(filling_time); # after wakeup: recheck! if (!empty(filling_time) # there is still somebody waiting ... signal(filling_time); # ... wake him/her up! sitting = sitting + 1; if (sitting = C) # the last customer ... signal(driving_time); # ... wakes the driver up wait(exit); # wait until the ride has finished if (sitting > 0) { # somebody still sitting, release ... signal(exit); # ...just one - everybody must not ... # ...release everybody sitting = sitting - 1; # signal & update indivisible ! # check: consistent with unload? } else signal(filling_time); # waiting customers may enter } # end of enter procedure load() { # used only by the merry_go_round if (sitting < C) # (no need for a "while"! why?) wait(driving_time); # wait until the system is full } # end of load procedure unload() { # used only by the merry_go_round signal(exit); # release the first customer # (NOT all customers! why?) sitting = sitting - 1; # the counter is decreased before .. # .. the customer resumes its mobility # check: consistent with enter? } # end of unload } # end of monitor ############################################################################# 4. The application consists of a group of rather independent processes S[*], which run in separate nodes of the network. The processes share a data store, but only one process at a time is allowed to use it. The control is organized along the following principle: - the processes form a ring along which a token travels - after having received the token the process can use the data store; after having finished its task the process forwards the token to its successor. The technical implementation of the system is as follows. Each node "i" has two processes: Allocator[i] takes care of the token (receives it, forwards it), Worker[i] does the actual computing. When Worker[i] wants to use the data store it sends a request to Allocator[i], then it waits until Allocator gives a permission to continue. All communication between the processes is based on message passing (send and receive follow the syntax and semantics of the textbook). Develop the code for the essential parts of Worker[i] and Allocator[i], channel declarations included. Make a picture which clarifies the architecture of the system. (13p) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ chan S_in[M](type_token) # a global channel module Node[i] { chan request(), release(), reply(); # local channels within a node process Allocator[i] { while (true) { select { # concurrent waiting receive S_in[i](token); if (wanting) { send reply(); wanting = false; receive release(); } send S_in[i+1](token); or receive request() wanting = true; } } } process Worker[i] { ... send request(); receive reply(); ... send release(); ... } # select-or-end can be replaced by in - [] - ni ###############################################################################