Concurrent Systems examination 26.3.2002 Comments A general comment: it is worth while to read all areas belonging to the course. There are four main "methods" (semaphores, monitors, message passing, remote procedure calls), and in every examination at least three out of them are supposed to be used. In this examination there were 38 participants; out of these 28 had no idea whatever about monitors, and 27 had no idea about remote procedure calls. Some 20 knew neither of them. ############################################################################### 1.a) Explain the meaning of the concept "thread of control". How is this concept related with the windows on your screen? b) Using a seat reservation system give an example of each of the four basic problems related with the concurrent systems (mutual exclusion, synchonization, deadlock, starvation). c) Assume that the mutual exclusion of a data structure is solved using a semaphore. How can a compiler check that the data structure is used only in a critical section closed by P/V-operations on this semaphore? How can the compiler check that each P-operation on a semaphore is followed by a corresponding V-operation (i.e., the programmer has not forgotten to open the critical section)? d) What is "barrier synchronization"? e) Is it of any use to have concurrent processes/threads, if the computer has only one processor? ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a) Thread of control: a sequence of subsequent actions specified by a program, may be executed by several operating system processes in different nodes (but at any time there is only on active operation belonging to this thread of control); typically: one application / window, the execution of the application may be based on one or more threads of control (IO control threads, DC control, the main computation, which again may be based on a sequential or parallel algorithm). See: Andrews, p 2. b) Mutual exclusion: two clients trying to reserve the same seat. Synchronization: the client waits until the server replies Deadlock: Two seats are left, and two clients start to reserve two seats one by one, both get the first seat and stop to wait for the second one. c) In no way: the compiler cannot know the the inteded purpose of any semaphore neither can the compiler konw anything about the execution paths of the program (the problem: conditional branching). d) All participants must first reach the synchronization point, and then all are released (in "normal" synchronization a "signalling" process need not wait for a partner to arrive). e) A process may wait for some external event (IO, data communication message etc); while one process is waiting, some others may continue. ############################################################################## 2. A parking hall has several entrances. At each entrance there is a sensor, which detects the arrivals and departures of cars, and an electric information table, which tells whether there are vacant places in the hall. The system is controlled by a computer with - one process for each sensor - one process to control the information tables. The communication between a process and a sensor is based on message passing (contents of a message: arrival/departure). The communication between a process and the information tables is based on message passing. The communication between the processes is based on shared memory. Write the essential parts of the codes the processes use (the data structures needed for the control, communication). (You need not care about the device drivers of the sensor and information tables). ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ module parking_hall int count, max_count; boolean change; type direction ("in", "out"); chan sensor_message[N](direction), info(string); process sensor[i] { type direction ("in", "out"); while (true) { receive sensor_message[i](event); P(mutex); if (event == "in") { count = count + 1; if (count == maxcount) change = true; } else { if (count == max_count) change = true; count = count - 1; } V(mutex); } if (change) { change = false; V(update); } } process info { while (true) { P(update); P(mutex); if (count == max_count) send info("full") else send info("vacant"); V(mutex); } } /* The process info can be made more straightforward: ... while (true) { send info("vacant"); P(full); send info("full""); P(vacant); } sensor[i] must be changed correspondingly, for example ... if (event == "in") { count = count + 1; if (count == maxcount) V(full); ... ############################################################################## 3. The producer and the consumer communicate using a buffer, which can contain several data elements. The buffer has been implemented using a monitor, which is based on the signal-and-continue principle. a) Write the essential parts of the codes for the producer, for the consumer and for the buffer monitor. b) Assume that the producer and the consumer are started at the same time, and that the consumer process has a higher priority. Describe the behavior of the procesesses to the point where the producer has written the second entry into the buffer. The level of detail: when active, when waiting, the queue in which the process is waiting, which event changes the state of the process. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a) See Andrews, Figure 5.4 b) Producer Consumer ... call fetch wait in "not-empty" (cond queue) ... call deposit write into buffer signal(non_empty) return wait in "ready" queue read from buffer signal(not_full) # has no effect return call fetch wait in "not-empty" call deposit write into buffer signal(non_empty) return wait in "ready" queue ############################################################################### 4.A weather forecast system has been implemented as a concurrent application: the air space is divided into cubes, and for each cube one computer calculates the forecast. The computation advances in phases: - starting with the initial values each computer computes the first forecast (weather conditions after one hour, for example) - when the forecast is ready the computer emits the estimated weather conditions to its neighbors - after having received the corresponding results from all its neighbors the computer computes the next forecast (weather conditions after the next hour, for example). The computaton continues until the forecast for the desired period is ready (for a week, for example). Write the essential parts of the program for one computer. You can restrict to the "normal" phases of the algorithm (you need not care about the starting and stopping phases). Try to maximize the amount of concurrency in your solution (explain how you use processes or threads). All communication is based on remote procedure calls. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Node S[i] process forecast { int neighbors; /* number of neighbors of S[i] ... typically 6 */ int maxphase; # number of phases typedef weather_type ...; # weather-data record sem nextphase = 0; # phase synchronization weather_type value[phase, neighbors]; /* interim values for the whole forecast */ # local node: 0 weather_type result; int count[maxphase] = [ [maxphase] 0]; # ready-to-continue counters procedure exchange (source, phase, xchvalue) { value[source, phase] = xchvalue; # store the value locally # mapping source->index not shown count[phase] = count[phase] + 1; if ( count[phase] == neighbors ) V(nextphase); /* notice that phase i+1 cannot become ready before phase i */ } initiate value[0, neighbors] ... for [phase = 1 to maxphase ] { /* compute this phase input: value[phase-1, * ]# all results from the previous phase output: result */ value[phase, 0] = result; # the local result saved for [ all j: S[j] is a neighbor of S[i] ] call S[j].exchange(i, phase, result); # the neighbor stores the data P(nextphase); # wait until all neighbors have sent their results } ... } The procedure exchange is executed by a separate thread. This thread serves all remote callers (if all callers aare served by an own thread then updating of count must be implemented as a critical section). ############################################################################## NOTICE, that in each assignment you must use the required control/communication structure (semaphore, monitor, message passing, remote procedure call); this is a prerequisite for any credits. The language of the algorithms must resemble the pseudolanguage used by Andrews (at least you must specify accurately enough the meaning of you expressions).