CIS307: Homework 2: More from Pradeep Pappachan

1. Agenda: It is a priority queue that holds the events corresponding to the completion of requests (READs/UPDATEs) requested by RAND_PROC1 and RAND_PROC2. Each node in the Agenda is a record containing the following information:
   • a) TABLE_ID of the entry in the TABLE on which the operation is to be performed.
   • b) Operation code for type of operation to be performed (READ/UPDATE).
   • c) The operands needed for the operation.
   • d) The time (t) when the operation is scheduled to be completed.
   The nodes in the Agenda will be maintained in ascending order of their time (t) fields.

   Before a node is inserted into the Agenda the values of fields (a), (b), and (c) are known from the message received by the store manager from the processes RAND_PROC1 and 2. But the value of the time field has to be calculated before the node can be inserted into the Agenda using PQinsert(). The t field value is calculated as follows:

   Let the node to be inserted be called N. Let the first node in the Agenda be called F.

   Case 1: If there are no nodes in the Agenda whose TABLE_ID field matches that of N then N.t = Time remaining for the request of F to be satisfied + 1 (Details are given below in the steps of the program segment)

   Case 2: If there are k nodes N1, N2, ..., Nk having the same TABLE_ID as N and if Nk is the last of these nodes in the Agenda at that instant N.t = Nk.t + 1

   After calculating N.t as above you can use PQinsert() to insert node N into the Agenda.

2. Program segment for the TABLE_MANAGER:

      loop
        wait for a request on the pipe C_BOX;
        log message;
        start the operation; (details below)
      forever
      termination;
   

   Starting the operation for node N: (fields (a), (b), (c) of N from above are assumed to be filled.)

        n = alarm(0); /* Turn off the alarm before accessing the Agenda
                         so that the signal handler cannot access it till
                         we are done. n is the time left before the alarm
                         goes off for the first node (F) in the Agenda. */
        
        Starting from the rear of the Agenda search for first node Nk
        such that Nk.TABLE_ID = N.TABLE_ID;     
         
        if such a node Nk is found
        	N.t = Nk.t + 1;
        else
           if Agenda is empty
              N.t = 1;
              n = N.t;
           else /* No node Nk could be found */
              N.t = (F.t - n) + 1; /* (F.t - n) is the time remaining for the
                                      request corresponding to node F to be 
                                      satisfied */
        PQinsert(Agenda, N);
        alarm(n); /* Retrigger the alarm */
   

3. Program segment for the signal handler for SIGALRM:

      N = PQdelete(Agenda);
      t1 = N.t;
      Complete operation on N; (call READ/UPDATE operation)
      Send response to sender;
      log response;
      t2 = Agenda.F.t; /* Agenda.F is the first node in the Agenda */    
      alarm(t2 - t1);
   

Pradeep Pappachan