Concurrent Systems examination 21.1.2003 ########################################################################## 1. a) An information system update includes write operations on several files. The update is required to be "atomic". What does this mean from the application's point of view? What does this mean from the other users' point of view? How can atomicity be implemented (the idea is enough, no code is needed here)? What new problems can this solution generate? b) What is a "guarded communication statement"? Give an example where this concept is used (write only the essential parts of the code, if you use some nontypical notation explain carefully the intended semantics). (a: 8p, b: 7p) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a) - application: either all writes will be done or none of them - other users see - either the situation which existed before the update started - or the situation which exists after the update ended - implementation - lock all variables as soon as they are used (reading or writing) (isolation) - a write operation: - make a copy of the entity - update the copy - when the whole update is ready, make all entities "visible" (or delete them, if the update could not finish orderly) (all or nothing) - problem: locking => deadlock (several users try to use the same entities) (see Andrews, Ch 2.4.2) a 2p b) see Andrews, Ch 7.6.2 - guard & communication (3p) - example (4p) ########################################################################## 2. How can you implement the monitor operations "wait" and "signal" ("signal and continue") using semaphores? Write the needed code. For the case of simplicity you can assume that - there is only one monitor in the system - the condition variables of the monitor are declared as a vector c[n] where the type of the element is "queue" - the type "queue" has two operations: "insert" and "remove". A hint: the process executing a "wait" should delay in a private semaphore. Why? ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ See: Andrews, Fig. 6.7 ########################################################################## 3. A weather forecast system has been implemented as a concurrent appli- cation: 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 informs its neighbors about the new estimated weather conditions - 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). All communication is based on message passing (using global channels). 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). Include in your solution the channel declarations, and specify the synchronization semantics of the operations send and receive ("blocking" or "nonblocking"). ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3. global declarations typedef weather_type ...; # weather-data record chan mailbox[N,N](weather_type value) # the mailbox[i,j] is for messages from P[i] to P[j] process P[ i = 0 to N-1 ] { int maxphase; # number of phases weather_type value[N]; /* initialiazations .... */ for [phase = 1 to maxphase ] { /* compute this phase input: value[ * ] # previous results output: value[ i ] # new local result */ for [ all j: P[j] is a neighbor of P[i] ] send mailbox[i,j](value[i]); # nonblocking send for [ all j: P[j] is a neighbor of P[i] ] { receive mailbox[j,i](value[j]); # blocking receive } # start the next phase } } For the sake of simplicity, this solution wastes quite a lot of space: - one mailbox per process would be enough, but then you must carefully synchronize the phases: while collecting the interim results of one phase the process may receive from some colleague results belonging to the next phase - only interim values of the neighbors are used => the array "value" should contain about six entries (and not N); in order to do this you should just map the "global names" P[i] to local index names used in the "value". ########################################################################## 4. The producer and the consumer execute in different computers, asynchro- nously. For communication they can use only remote procedure calls. The realization of asynchrony is based on the use of a separate buffer ser- ver (a process which contains the buffer area; the buffer can contain several data items). Write the code needed for communication (between the producer, the consumer, and the buffer server). You can assume that there exists only one producer and only one consumer. Expected level of detail: the main parts of the remote procedures, the calling of a remote procedure (the form of the call), managing of the buffer area. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4. the general outlook: see the procedures in Fig. 5.4 the contents: see Fig. 4.4 procedure call: see Chapter 8 Buffering //variables: // not visible outside final int N = 100; // buffer size item [ N-1 ] buffer; // buffer, type of content .. // ... item, N entries int next_item=0, nextfree=0; // buffer indexes semaphore entries = N, space = 0; // counting semaphores // remote procedures: // visible outside remote_procedure item GET() { // returns data of type.. // ... item P(entries); // semaphore for synchr... x = buffer[next_item]; next_item = (next_item + 1); // "end_around" + V(space) // semaphore for synchr... return x; } remote procedure PUT(item x) { P(space); buffer[next_free] = x; next_free = (next_free + 1); // "end_around" + V(entries) } end; Producer ... data_item = ... ; buffering.PUT(data_item); ... consumer ... data_item = buffering.GET; ... ##########################################################################