Concurrent Systems examination 7.10.2003 ########################################################################## 1. a) What does it mean that a sequence of actions must be executed "atomically"? Use the sequence < x = x+1; y = y+1; > as an example. b) In a specification language you can see the expression < await(B); S > . Explain its meaning. Give an example of its use; the example should be related with the producer/consumer problem. c) Explain the execution rules for the following guarded communication statement { ... if B1; C1 -> S1; [] B2; C2 -> S2; fi ... } (a: 3, b: 5; c: 7 points) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ See Andrews, Ch. 2.1, 2.4, 2.5, and 7.6.2 ########################################################################## 2. There are M honeybees and a hungry bear. They share a pot of honey. The pot is initially empty; its capacity is H portions of honey. The bear sleeps until the pot is full; then eats all the honey and goes back to sleep. Each bee repeatedly gathers one portion of honey and puts it in the pot; the bee who fills the pot awakens the bear. Represent the bear and honeybees as processes and develop code that simulates their actions. Use semaphores for synchronization. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - semaphore lunch_time, initial value 0 (sleeping place for the bear) - semaphore filling_time, initial value 1 (exclusive use for the bee: other bees are excluded and the bear is excluded) - counter portions, initial value 0 - the semaphores also guarantee mutual exclusion: if the pot is full then only the bear can enter the critical phase, if the pot is not full then only a bee (but only one) can enter - notice that - after the V-operation has been executed it may last long (in real time) before the bear really starts eat - when the pot has become full, no further bees are allowed to enter process bear { while (true) { P(lunch_time); #sleep while waiting ... #eat (no bees allowed) portions = 0; V(filling_time); #the bees are allowed to fill the pot } } process bee[i=1 to n] while (true) { fly_from_flower_to_flower; P(filling_time); /* wait until neither the bear nor other bees are using the pot */ ... # put one portion into the pot portions = portions + 1; if ( portions == H ) #the pot is full => wake the bear V(lunch_time); /* filling_time remains down: this excludes other bees from entering, and the bear is always ready */ else V(filling_time); # the pot is free for the next bee } } ########################################################################## 3. An enterprise tries to balance the printer loads. The clients send the print files to the printer service, who maintains queues for all printers. The printer service selects the shortest queue for the incoming print file, then it informs the client about the chosen printer. Develop code for the essential parts of the client and of the printer service. Communication is based on message passing through global channels. (For each printer there is a printer process, which retrieves the print file from the queue and prints it; however, the code of this process falls outside of this assignment, and you need not worry about it.) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ An outline for some parts of the client and server codes: chan request (int client_id, file output_file); chan reply[max_clients] (string printer_id); process client[i] { ... send request(i, my_output); receive reply[i] (printer_info); ... } process printer_service { file queue[maxprinter; * ]; # the printer queues (simplified) int q_length[maxprinter]; # the queue lengths int cumulative_load[maxprinter]; # cumulative number of prints ... int chosen; ... while (true) { receive request(client, job); chosen = select(q_length) /* select the shortest queue; if there are several candidates, choose the one with the lowest load this far */ insert (job, queue[chosen]); # mutual exclusion needed ! # qlength increased send reply[i](printer_info[chosen]); } } ########################################################################## 4. Each node in a computer network maintains information about the network load: everybody informs its neighbors about all essential changes in the load. When a node receives from its neighbor new load information, it updates its local data and then forwards the received information to its other neighbors. In this application the network configuration is a chain ( x - x - ... - x ). Develop the code for a typical node (in the middle of the chain). The communication is based on remote procedure calls. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ An outline for some parts of the code in node[i]: module LB[i] op load_update(id informer, changed; load_info new_load) /*the types id, load_info have to be declared; informer: the node which informed the node[i] changed: the node where the load has been changed new_load: the new load information */ body ... load_info load_info_table[max_node]; ... procedure load_update(informer, changed, new_load) { /* this is a shared procedure => mutual exclusion is needed; here: for the sake of simplicity we assume that this procedure is implemented as a monitor routine */ ... # local update load_info[changed] = new_load; /* propagate the information to the ignorant neighbor(s)*/ for [j = i-1, i+1 such that j!=informer] call LB[j].load_update(i, changed, new_load); /* in the node where the change took place we could benefit from a concurrent execution of these calls; in all other nodes a for statement is essentially more efficient - hence, we use a for statement */ } process check_load { # a process in the node i ... while (true) { read local load information; if (load has changed in an essential way){ new_load = {new load information}; load_update(i, i, new_load); } delay(interval between two check-operations); } } end LB A comment about the execution of the procedure "load_update": - if "load_update" is called by the local "monitor_load" then the caller process executes "load_update" - if "load_update" is called using RPC (the monitor_load of a neighbor) then a new process is invoked to execute the procedure "load_update". This solution assumes that "load_update" can be called both locally and remotely. If the system does not allow this, then the process "monitor_load" can be made to include the essential contents of "load_update", and the procedure "load_update" is only used by the neighbors. The process "monitor_load" could be replaced by a similar procedure, which is called by the operating system routines (when important changes take place). ##########################################################################