Concurrent Systems examination 25.3.2003 ########################################################################## 1. 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) What is the essential idea in the "banker's algorithm"? What happens to the client, if the banker cannot grant the request? (You are not expected to write the algorithm!) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 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) The banker checks whether, after granting the resource, there still exists at least one way to finish all the tasks - even if all of them would request their maximum resources (some of them may have to wait for others finish). If the client does not get the required resource it starts to wait (eventually it will get the resource!) ########################################################################## 2. The museum offers only guided tours to the visitors. The arriving visitors wait in the entrance hall until the guide comes and starts a new tour. Assume that the guide and the visitors are processes and write the corresponding routines. Waiting is implemented using semaphores. Hint: a visitor's routine is essentially a loop the body of which looks in principle more or less like {do something somewhere};{wait for the guide};{take_the_tour} and for the guide correspondingly {wake the visitor group}; {guide_the_tour} Notice that while the group is leaving the hall new customers may arrive - they must be allowed to join the group. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ # a visitor while (true) { walk_around; P(mutex); if (no_guide){ # is the guide present? waiting = waiting + 1; # no => join the waiting group V(mutex); P(entrance_hall); # wait for the guide } else V(mutex); # pass those already waiting take_the_tour; } # the guide while (true) { P(mutex); no_guide = false; # after this no visitor updates "waiting" if (waiting == 0) { no_guide = true; V(mutex); drink_coffee_until_next_tour; } else { # there is at least one visitor V(mutex); # additional visitors can join # (but they pass the queue) for (i = 1 to waiting) # release those already waiting V(entrance_hall); no_guide = true; # an indivisible operation # => new visitors have to wait guide_the_tour; } } Notice: the test for a condition and the corresponding action must be indivisible ########################################################################## 3. The components of a distributed application are located far away from each other, and the connections between the nodes are slow and may sometimes break down. The application needs a "reliable multicast" operation: the message is "accepted" by everybody or by nobody. Write the routine for this reliable multicast using send and receive operations and global channels (the sender's code is enough, you need not write the receiver's code). In your solution, exploit concurrency in communication as much as possible. (Specify the synchronization semantics of your send and receive: "blocking" or "nonblocking".) +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ # global declarations int N # group size int G[N] # receiver names of group members # global communication channels for messages and acknowledgements chan G_chan[N](int sender, messageType message), # for messages chan G_ack[N](int sender); # for ack's chan G_comm[N](commT); # type commT = {commit, abort} # send is nonblocking, receive is blocking procedure multicast(int sender, messageT message) { int ack_count; # number of received ack's boolean ack_info[N]; # ack received? for [j = 1 to N, such that i != j] send G_chan[j](i, message); # multicast to G ack_count = 1; # "ack from G[i]" for [j = 1 to N, such that i != j] ack_info[j] = false; while(ack_count < N and waiting_time_left) { select receive G_ack[i](j); # ack from G[j] ack_info[j] = true; ack_count = ack_count + 1; or delay (max_waiting_time); # one way to time_out waiting_time_left == false; end; } # end of collecting ack's if (ack_count = N) commit_mess = commit else commit_mess= abort; for [j = 1 to N, such that (ack_info[j] == true)] send G_comm[j](commit_mess); # see (*) } # end of multicast # (*) A problem: did everybody receive the commit message? ########################################################################## 4. In a network, to get information about the utilizations of the nodes you can use a "probe-echo" algorithm. The general idea is simple. The net is treated as a binary tree, where the root asks its both subtree roots for the utilization information of their corresponding subtrees; these continue in a similar way and ask their children, and so it goes on. After having received the required information from both children the node sends the complete subtree information to its own caller. Write the algorithm used by each node. Use remote procedure calls for communication. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ the information about the tree structure is in the variables "left_child" and "right_child", which are local for each node; the utilization information is returned as a vector of type "utilType" module UtilizationInquiry # module located in each node op inquiry (result utilType); # declaration of the procedure proc inquiry(reply) { # body of the remote procedure /* remote calls are activated in parallel */ co if (left_child != NIL) call node[left_child].inquiry(reply_L); else reply_L = NIL; // if (right_child != NIL) call node[right_child].inquiry(reply_R); else reply_R = NIL; oc; reply = combine (reply_L, reply_R, local_info); } process initiator { /* the initiating proces, located in the root node */ call inquiry(reply); # calls the local inquiry } ##########################################################################