Concurrent Systems examination 24.9.2002 Comments ############################################################################### 1. a) Assume that you are preparing teaching material and you are supposed to illustrate concurrency. Give examples related with a file server about the following issues: - what can be implemented as concurrent activities (and how), - what cannot be implemented as concurrent activities - what benefits can be gained from using concurrency (in your examples) - what are the disadvantages related with concurrency (in your examples). The file server is running in a single computer. b) What does it mean that a sequence of actions must be executed atomically? How does this affect other processes? c) What is a "guarded communication statement"? Give an example where this concept is applied (write the essential parts of the code; if you use some atypical notation, explain carefully the intended meaning). (a: 8p, b: 3p, c: 4p) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a) concurrent reading a file the file is open for several users (for details, see textbooks); one process/thread for each user writing a file mutual exclusion must be provided at file level or at record level (using locks, semaphores, monitors, e.g.) not concurrent any changes in the file system or individual files if consistency is needed but not provided benefits performance (access time): several users can work in parallel disadvantages overhead due to mutual exclusion management, vulnerability of the system (problems due to misbehaving programs), deadlocks b) see Andrews, Ch 2.4.2 (exclusive usage of resources is only one way of implementation) c) see Andrews, Ch 7.6.2 ################################################################################ 2. A group of workers get their dinners from a large pot, shared by all members of the community. When somebody wants to eat, he takes a serving from the pot. If the pot is empty, the customer wakes up the cook and then waits until the cook has refilled the pot (with M servings). The behavior of the workers and cook is specified by the following processes: process customer[1:n] { while (true) {get serving from the pot; eat; } } process cook { while (true) {sleep; put M servings in the pot; } } Develop code for the actions of the workers and cook. Use semaphores and P/V-operations for synchronization. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ int M = ; #amount of servings in a full pot int servings = 0; #amount of available servings sem empty = 1; #waiting place for the cook sem mutex = 0; #the pot is closed until the cook opens it procedure get_serving() { P(mutex); #if mutex is open then there is food servings = servings - 1; if servings == 0 V(empty); #wakeup the cook, mutex remains closed #waiting for food will be in mutex else V(mutex); } procedure eat() { #one serving is available for the customer, not further specified } procedure sleep() { P(empty); #the cook sleeps } #the cook wakes up, mutex is closed procedure put_servings() { #prepares food, not further specified servings = M; V(mutex); #the next clients are free to enter } ############################################################################## 3. Give a solution for the "sleeping barbers" problem using message passing. Assume that there are several barbers working in the barbershop. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ This is a very simple solution (there could be more cooperation) type kind = enum(haircut, shaving, ... ); chan service_queue(int id, kind op), #one queue for all customers goodbye[M](); #one "reply"-channel for each customer process client C[i = 0 to M-1] { ... op = "haircut"; #specify the operation send service_queue(i,op); #inform the barber and ... receive goodbye[i]; #... wait for a reply #(operation has been executed) ... } process barber[j = 0 to N-1] { while(true) { receive service_queue(client, operation); #wait for the next customer execute(client, operation); #service execution send goodbye[client](); #confirm } } ############################################################################## 4. a) Which are the three conditions which must be present for a deadlock to be possible? How is each of these conditions fulfilled in the "dining philosophers problem"? b) In the "dining philosophers problem", how can you prevent a deadlock by changing the "eating rules" such that one of these conditions is not fulfilled? Discuss each condition. c) Use the "banker's algorithm" to solve the following resource allocation problem. The system contains three different types of resources: A, B, and C. There are 6 units of A, 4 units of B, and 4 units of C. The system is in the following state: process allocated maximum demands for processes of processes A B C A B C P1 2 2 2 2 3 2 P2 4 1 0 5 1 1 P3 0 0 1 2 2 2 The process P2 requests for one additional unit of C. Can it be granted? Give your reasons. What if it would have been P3 requiring one additional A unit? Obviously the request cannot be granted, but what happens then? (a: 6p, b: 3p, c: 6p) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ a), b) See Stallings, Ch 6.1; forks are resources (of different types), philosophers are processes. 1. mutual exclusion two philosophers do not use the same fork at the same time; it is not wise to remove this requirement 2. hold and wait if the philosopher has to wait for the second fork he still keeps the first one; change of protocol: both forks have to be acquired "atomically" (two or none) 3. no preemption a philosopher is not allowed to take the neighbor's fork by force; change of protocol possible: a waiting philosopher must release a fork on a demand of the neighbor; or it may also be possible to stop a philosopher after a long enough eating period; in real life the feasibility of these solutions depends on the application. Notice that "circular wait" does not belong to the necessary preconditions which "make a deadlock possible" - with a circular wait you already have one! c) Banker's considerations: after C has been given to P2 it is still possible to finish P1 (even if it would require its maximum amount of resources); after P1 has released its resources both P2 and P3 can be finished (even if .. etc). P3 case: P3 has to wait until more resources become available, as the starting situation is safe (bankers algorithm has been applied all the time), P3 will eventually get its resources. ############################################################################### 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 pseudolanguage used by Andrews (at least you must specify accurately enough the meaning of you expressions).