Concurrent Systems
examination 22.1.2002

Comments

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

1. a) What are the advantages of using concurrency? Give examples.
   b) What are the disadvantages of using concurrency? Give examples.
   c) Describe in detail what happens when the monitor operation signal 
      is executed. Treat both cases:
      1) "Signal and Wait" 
      2) "Signal and Continue".

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    See: Andrews textbook  

    c) level of detail: usage of the different queues 
       (notice: the process scheduler plays no role whatsever in the story)
   
##############################################################################

2. Merry-go-round". Suppose there are n customer processes and one vehicle
   process (vehicle = merry-go-round, carousel, roller coaster, for example). 
   The customers repeatedly wait to take rides in the vehicle, which can hold
   C customers (C < n). However, the vehicle is started for a ride only when
   it is full. After each ride all customers continue with some other 
   activities before returning to get a new ride. 
   
   Develop code for the actions of the customer and vehicle processes.
   Use semaphores for synchronization. 
   (Notice: for the customer, sitting in the vehicle is just waiting.)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

  
   - semaphore driving_time, initial value 0 
     (the sleeping place for the roller_coaster)
   - semaphore filling_time, initial value 1 
     (entering the train is exclusive; a customer must until 
         - the previous customer has entered
	 - the train is on place)
   - semaphore exit, initial value 0
     (the customers wait here for the end of the ride)
   - counter sitting, initial value 0 

   - the semaphores also guarantee mutual exclusion: if the train is full
     then only the roller_coaster can enter the critical phase, 
     if the train is not full then only a customer (but only one) can enter
   - the customers wait until released by the roller_coaster (V(exit))

   Use baton passing technics to implement indivisible "signal and go".

   The roller_coaster kicks the first customer out, and each customer kicks
   the next one.


    process roller_coaster { 
      while (true) {
        P(driving_time);	 	# sleep while waiting
	make_the_tour;
	V(exit);			# the first customer is released	
      }					# the gate remains closed
    }

    process customer[i=1 to n] {
      while (true) {
        various_activities;
	P(filling_time);	      # wait: entering customer / a ride is on 
	sitting = sitting + 1;
	if ( sitting == C)		
          V(driving_time);	     /* the train is full: wake up the driver 
	      			        notice: filling_time remains closed, 
					new customers stay in filling_time */
	else V(filling_time);         # the next customer is allowed to enter
	P(exit);		      # wait for a ride, enjoy the ride
				      # filling_time is closed
	sitting = sitting - 1;
	if (sitting > 0) V(exit);     # wakeup the next customer 
	else V(filling_time);	      # the system is empty => go on
      }
    }
	  
 
  severe faults: 
    no waiting of customers 
    no wakeups of customers
    busy wait
    a customer can enter a moving train
  
  other major faults:
    mutual exclusion errors
    severe performance problems (other than busy wait)
    initial values not specified: if this omission creates confusion

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

3. Suppose a computer center has two printers, A and B, that are similar but 
   not identical. Three kinds of processes use the printers: those that must 
   use A, those that must use B, and those that can use either A or B. 
   The manager process LPmngr allocates printers to users; the communication
   between LPmngr and the user processes is based on message passing. 
   
   Develop code for the request and release actions (LPmngr, user process).
   (Notice: you can assume that the user processes consist of a fixed group
   P[1:n].)		

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

 process LPmngr {
   
   type op_kind = enum(req,rel);
   
   chan request(int client; op_kind op; int pr_type); # A=1, B=2, any=0
   chan reply[n] (int pr_type);

   boolean pr_free[1:2] = (true, true);
   type queuetype = (int client, int req);
   
      
   while (true) {
     ...
     receive request(client, op, pr_type);
 
     if op == req {

       if pr_type == 0 {
         if     (pr_free[1]) 	pr_type = 1;
	 elseif (pr_free[2]) 	pr_type = 2;
	 else 			insert(queue, client, pr_type);
       }
         
       if (pr_free[pr_type]) {
         pr_free[pr_type] = false; 
         send reply[client](pr_type);
       else insert (queue, client, pr_type);		
       }
     } # end of request

     if op == rel {
       if (queue empty) 
         pr_free[pr_type] = true;
       else {
         (client, pr_type) = search(first item where req == pr_type);
	 if (search succesfull) 
           send reply[client](pr_type);
	 else 
	   pr_free[pr_type] = true;
 	}
	   
     }  # end of release
    }    # end of process

 
    process client_[i] {
        ...
	pr_type = ...
        send request(i, req, pr_type);
        receive reply[i](pr_type);
	...
	send request(i, rel, pr_type);

     }

  major faults related with communication
    use of shared memory
    receive req/ receive rel executed serially
    clients share a return channel

  major faults related with the program logic
    no queueing
    no release of printers
    LPmngr is stopped
    (treatment of empty queues forgotten)


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

4. Which are the necessary conditions for a deadlock? Explain for each
   condition what possibilities there are to prevent the condition and thus
   avoid the deadlock.
   Use as an example a booking system where the user can book seat tickets 
   for a theater play and - if he is interested - also a hotel room in the
   local hotel. 
  

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

  See the textbook.
  
##############################################################################

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). 
The expected level of detail: everything which is related with concurrency 
control and communication is important, but all other operations can be 
described using the common language ("insert X into R-queue", for example).