Concurrent Systems examination 22.8.2003 ########################################################################## 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: 4, b: 3, c: 8) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a) Tavanomainen perusongelma on luonteeltaan epäsymmetrinen: prosessi B varmistaa ennen suorituksensa jatkamista, että prosessi A on ohittanut tietyn pisteen (mutta prosessin B eteneminen ei vaikuta millään tavalla prosessin A etenemiseen). Puomisynkronoinnissa on oleellista, että kaikki prosessit saavuttavat tarkoitetun "tahdistuspisteen" ennen kuin yksikään saa jatkaa. b) Ilman puskuria tuottajan ja kuluttajan on täytyisi synkronoitua tiedon välitystä varten. Puskuri poistaa tämän rajoituksen. Puskurin pituudesta on hyötyä, jos tuottaja ja kuluttaja toimivat vaihtelevilla nopeuksilla: mitä enemmän vaihtelua sitä suurempi puskuri. Jos toinen on jatkuvasti nopeampi kuin toinen, niin puskurin pituudesta on vain haittaa (miksi?) c) Semafori kuluttajaprosessi odottaa semaforissa, että tuottaja tekee V-operaation Monitori kuluttajaprosessi odottaa ehtomuuttujassa, että ... Manageri kuluttajaprosessi odottaa receive-käskyssä (receiven toteuttavassa koodissa semafori tms), toimenpide odottaa kanavassa, että managerin receive lukee sanoman Etäproseduuri kuluttajaprosessi odottaa proseduurikutsusta paluuta (itse asiassa prosessi on suorittamassa tynkäkoodia ja odottaa siellä semaforissa sanoman palautusta), etäproseduurin suorittajaprosessi odottaa paikallisessa semaforissa että tuottajan kutsuma paikallinen suorittajaprosessi tekee V-operaation. ########################################################################## 2. a) What are the four necessary and sufficient conditions for deadlock? Explain what they mean when resource allocation is considered. b) Group communication can lead to a deaclock: everybody waits for a message from some other member of the group (in a receive operation). How do the conditions materialize in this situation? +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a) see the textbook b) resource unit ~ message mutual exclusion ~ a process waits for a message hold and wait the waiting process witholds its next message until the message it waits for has arrived no preemption the process cannot be forced to send a message (using a timer, for example) circular wait circular wait ########################################################################## 3. Memory management can be implemented using a monitor with two operations: REQUEST(AMOUNT) and RELEASE(AMOUNT), where AMOUNT is an integer. When a process calls REQUEST, it delays until AMOUNT pages can be allocated to it. A process returns AMOUNT pages to the free pool by calling RELEASE. The memory allocation is based on the "smallesta request first" policy (the delayed processes are served in the order defined by the size of the memory request). Write the code for the operations REQUEST and RELEASE, which implement the memory management. However, only the parts related with delaying the processes and decision making are required, other administration of the memory allocation management need not be considered in detail. The signal operation is of the type "signal and wait". ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ SEE: Ch 5.2.3, and ex. 5.14 SIGNAL AND WAIT: a process woken up by the signal always finds the released memory (no other process can steal it) monitor MEMORYMANAGEMENT; int free = M; # number of free pages, initially M cond req_queue; /* queue for waiting processes, clients ordered by the request size */ procedure REQUEST(int req) { if (free < req) wait(req_queue, req); /* the process may have passed the (possibly nonempty) queue or it may have been woken up from it - in both cases: free < req */ free = free - req; } procedure RELEASE(int amount) { free = free + req; while (!empty(req_queue) && minrank(req_queue) <= free) signal(req_queue); /* the released memory may satisfy the needs of several waiting processes */ /* notice that immediately after the signal the signalled process gets control; this (signalling) process continues first when it gets the processor back - during this time interval NO OTHER PROCESS CAN ENTER THIS MONITOR, hence, the state variables free and cond have been updated only by the signalled process */ } ########################################################################## 4. The structure of the software in a router (of a data-communication network) could be as follows: - there are m threads waiting for messages, each from its own channel - there are m threads for writing messages, each into its own channel - each writing thread has a buffer for one message - when a reading thread has received a message, it inserts the message into a writer's buffer (determined by a routing table); if the buffer is full, the reader waits. Write the code which implements this functionality. Your solution need not contain details related with address specification. You need not care how the message is moved from one channel (seen by the send operation) to another channel (seen by the receive operation). You can assume that there is never more than one message in transfer and that the transfer never fails. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ type message = .... ; chan in_chan[1:m](message), out_chan[i:m](message); message buffer_pool[1:m]; sem empty[1:m] = 1, full[i:m] = 0; thread reader [i = 1 to m]; { message packet; int dest; # output channel while (true) { receive in_chan[i](packet); # blocking receive dest = resolve_address(packet); /* determine the output channel */ P(empty[dest]); # see Fig. 4.3 message_buffer[dest] = packet]; V(full[dest]; } } thread writer [i = i to m]; { # see Fig. 4.3 while (true) { P(full[i]; synch_send out_chan[i](buffer[i]); /* blocks until the message has been received - otherwise the receiver may overflow */ V(empty[i]); } } ########################################################################## NOTICE, that in each assignment you must use the required control/communi- cation structure (semaphore, monitor, message passing, remote procedure call); this is a prerequisite for any credits. The language of the algorithms must resemble the algorithmic language used by Andrews.