Concurrent Systems
examination 3.6.2003

1.  Assume that you are preparing teaching material and you are supposed
    to illustrate concurrency. 
    a) Give examples related with a study registration database (such as
       oodi) about the following issues:
      - what can be implemented as concurrent activities (and how),
      - what cannot be implemented as concurrent activities
      and in these examples:
      - what benefits can be gained from using concurrency
      - what are the disadvantages related with concurrency.

    b) The following process uses guarded communication commands:
         process C {
           char c1, c2;
	   West?c1;
	   do West?c2 -> East!c1; c1 = c2;
	   [] East!c1 -> West?c1;
	   od
         }
      Describe how this process behaves in different situations 
      (essential: communication!)
      
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   
   a) assuming a nonreplicated database:
      concurrent: reading the database, writing different records
      nonconcurrent: while writing a record, any access to the intermediate
      state of the record
      
      benefits: performance (compared to what baseline?)
      disadvantages: overhead due to mutual exclusion
      
      (additional examples: assume a replicated database)

   b) see Andrews, 7.6.1
      essential: 
      - the role of guards,
      - the role of communication commands
      - concurrency

##########################################################################

2. Give a solution for the "sleeping barbers" problem using semaphores.
   There is exactly one barber, but the waiting room is big (there is
   always place for still one client). During the haircut the client
   sleeps; on the other hand, the barber must know the identity of the
   client (the client processes are client[i = 1 to N]; the "haircut"
   involves using data which belongs to the client).
   The solution must be as simple as possible.

   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   
   The original problem: see Andrews 5.2.5.
   Notice that this is an essentially simplified case, resulting into
   a straighforward producer-consumer problem:
   the clients "produce" waiting tasks, the barber "consumes" them.

    /* the solution uses an explicit queue of an "unlimited" size;
       another possibility is to use only the semaphore queues and
       let the customer identify itself to the barber (using a 
       global variable - requires one additional synchronization)*/
    /* notice: P/V operations that cause rescheduling of processes
       are really expensive - it is worth while to minimize the
       number of P/V operations on frequently used execution paths*/

    int front = 0, rear = 0 ; int queue [*];

    sem wait_for_customer = 0, wait_for_ready = 0, mutex = 1;

    process client[i = 1 to N] {
       while(true) {
       ...
       P(mutex);			#several clients => mutex
         queue[rear] = i;
         rear = rear + 1 ;		#actually: end_around add
       V(mutex);
       V(wait_for_customer);		#wakeup the barber
       P(wait_for_ready);
       /*waiting in the queue and waiting for the end of haircut
         have been combined: from the client's point of view
	 these two waiting states are typically identical*/
       }
     }

     process barber {
       while(true) {			#no mutex needed - why?
         P(wait_for_customer);
         do_some_haircut(queue[front]);
         front = front + 1 ;
         V(wait_for_ready);
       }
     }

##########################################################################

3. 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. The visitor's algorithm is essentially:
   {do something somewhere}; {enter the waiting room}; {walk in the museum}
   and for the guide correspondingly:
   {let the group into the museum}; {walk in the museum}.
   There are some administrative rules:
   - while the group is entering the museum the outer door of the waiting 
     room must be closed
   - if the group size is less than 10 the guide has to wait for further
     visitors.
   Assume that the guide and the visitors are processes. Synchronization
   is implemented using a monitor with the procedures "enter the waiting
   room" and "let the group into the museum". 
   Write the code for the monitor. The signal operation is of the type
   signal_and_continue. How would your program behave, if the type of
   the signal would be signal_and_wait?
   
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   
   /* This is an example of barrier synchronization.  
      Notice that the "door condition" is fulfilled automatically through
      the monitor infrastructure: only one procedure at a time can be
      active. */

   # The monitor (global for the processes):
   
     monitor museum {
       cond customers, guide;
       int count = 0;
       procedure enter() {
         count = count + 1;
         if (count==10) signal(customers);
         wait(guide);			#wait for a signal from the guide
       }

       procedure take_a_group() {
         if (count < 10) {
           wait(customers);		#waiting: "outside of monitor"
         }				#after signal: recheck condition
         while (count > 0) {
           signal (guide);		#signal all members of the group
	   count = count - 1;		#no check of door is needed
         }				#OR: while {} => signal_all(guide)

   # The processes:

       process visitor {
         while (true) {
           walk_around;
           museum.enter();
           walk_in_the_museum;
         }
       }

       process guide {
         while (museum_is_open) {
           museum.take_a_group();
	   walk_in_the_museum;
         }

   signal_and_wait:
   The outer door will essentially be open while the group is entering
   (the guide lets one client enter, the door is opened, the door is 
   closed, the client enters, the door is opened, the door is closed,
   the guide lets one client enter, etc);
   except this break of a rule the program works correctly.
   However, in this solution you could have used signal_all, but
   signal_all is not specified in a signal_and_wait environment.

##########################################################################

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.
   Communication is based on message passing through global channels.
   Write the algorithm used by each node (process structure, usage of
   channels). For performance reasons, exploit concurrency as much as
   possible.
   
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   
   The information about the tree structure is in the variables
   "parent", "left_child", "right_child", which are local for each node.

   The utilization information is returned as a vector of type "utilType".

   The communication channels are declared as global variables.
   Notice that somebody (i.e. the root) has to initiate the computation.

   chan inq[0:N](), reply[0:N](utilType result);   
   # "channel"[i] is for the node[i]
   # "channel"[0] is for the process "initiator"

   process UtilizationInquiry[i=1 to N] {          
   # "process"[i] executes in the node[i]
   # the root of the tree is in the node[1], its parent is the initiator

     utilType reply_L, reply_R, reply_subtree, local_info;
     int parent, ....
     ...

     while(true) {
       receive inq[i]();

       /* remote calls are activated in parallel */
       co if (left_child != NIL) {
            send inq[left_child]();
	    receive reply[i](reply_L);
	  }
          else reply_L = NIL;
       // if (right_child != NIL) {
            send inq[right_child]();
	    receive reply[i](reply_R);
	  }
	  else reply_R = NIL;
       oc;
       <collect local_info>
       reply_subtree = combine (reply_L, reply_R, local_info);
       send reply[parent](reply_subtree);
     }
   }

   process initiator {
   /* the initiating proces, located in any node */
      utilType tree_utilization;
      send inq[1]();
      receive reply[0](tree_utilization)
      ...
   }

##########################################################################