Conservative Timestamp Ordering Algorithm

by Lúcio Cunha Tinoco

System Components:

A timestamp ordering scheme for every site (i.e, a transaction manager, TM) in the system.
A scheduler process that keeps track of all the transaction requests arriving at a certain data manager (DM). This scheduler also maintains two internal queue data structures for each TM, namely a READ and a WRITE queue. These queues, as the name suggests, hold READ and WRITE requests for a TM and are ordered by using the timestamp ordering scheme previously mentioned.

Description of the algorithm:

When a TM wants to perform a READ or a WRITE operation to a certain DM, it sends a request to the scheduler responsible for that DM. A request consists of a READ/WRITE command, a variable-value pair to be read/written (value is NIL in case of a READ-op), and timestamp (TS). The scheduler is then responsible for either allowing the request execution or for buffering the request in case of a potential conflict (we will define "potential" later, don't worry). The scheduler is also responsible for making sure that each request is processed by the algorithm when it comes in, and for testing if any of the buffered requests can be executed.

The Algorithm:

Every READ or WRITE request goes throught the following routines:

If it's a READ request:

int READ_REQ (TM_ID, DM_ID, variable/object, TS) 
{
   int i;
   int SUCCESS=TRUE;


/* Checks to see if another WRITE is scheduled to happen earlier in time. In that
 case, it buffers the request to avoid the potential conflict */    
   for (i=1; i<=N; i++) {
      if (NonEmpty(*Write_Queue[i]) && ( Head(Write_Queue[i]->TS) ) > TS) ;
      else {

/* If test fails, procedure enqueues the request in a read queue. */
         Enqueue(Read_Queue(TM_ID, TS));
         SUCCESS=FALSE;
         return(0);
      }
   } /* End for */

/* If succeeds, request is executed */
   if (SUCCESS) {
     READ(variable/object, DM_ID);
     return(SUCCESS);
   }   
} /* End READ_REQ */

If it's a WRITE request:

WRITE_REQ (TM_ID, DM_ID, variable/object, value, TS)
{
    int i;
    int SUCCESS=TRUE;

    for (i=1, i<=N; i++) {

/* Checks to see if any read requests are scheduled to happen earlier in time. In that case, it buffers the
request to avoid potential conflicts */
    if (NonEmpty(*Read_Queue[i]) && NonEmpty(*Write_Queue[i]) && (Head(Read_Queue)->TS > TS) );
      else {
        Enqueue(Write_queue(TM_ID, TS));
        SUCCESS=FALSE;
        return(0);
      }
      if (SUCCESS) {
         WRITE(variable/object, value, DM_ID);
         return (SUCCESS);
      }
} /* End WRITE_REQ */

Whenever a read or write request is buffered or executed, buffered requests are tested to see if any of them can be executed, by running the algorithm for each one of them.

How it works:

The algorithm guarantees serialization simply by ordering every action, be it conflictant or not. That's why it's called conservative ordering algorithm, by the way. As an example, assume the following ordering of requests arriving to a DM-scheduler:

1st to arrive, w/ TS=1 : REQ_READ (TM_1, DM_1, x, 1); 
2nd to arrive, w/ TS=2 : REQ_READ (TM_2, DM_1, x, 2); 
3rd to arrive, w/ TS=3 : REQ_READ (TM_2, DM_1, y, 3);
4th to arrive, w/ TS=4 : REQ_WRITE(TM_1, DM_1, y, 4);

These operations are clearly serializable, for it represents the execution of transaction 2 before transaction 1. One can see, however, that all the requests are buffered because of empty queues in the system, and because the final write request has a timestamp greater than the ones in the system. This example also illustrates a very undesirable situation that may occur when using CTO algorithms: the system can be blocked , even though it has no conflicting actions.

It should be clear also from the simple example above, that with only two transactions and one write request, every possible ordering of actions is valid and serializable, and there is no reason for blocking. The write request of transaction 1 could, for example, be executed in any order.

However, in the case of large number of requests arriving from a large number of transactions, or when the possibility of conflict among requests is big, the conservative algorithm does its job fairly well. By making sure that all the requests are processed in timestamp order, it guarantees a consistant and serializable execution of events.

To handle those blocking situations, where termination is not guaranteed, it is recommended that "dummy" requests be sent regularly to the scheduler.

References:

1. Bernstein, P. and N. Goodman, "Timestamp Based Algorithms for Concurrency Control in Distributed Database Systems," Proceedings of 6th Int Conf. on Very Large Databases, Oct. 1980
2. Singhal, M. and N. Shivaratri, "Advanced Concepts in Operating Systems,"McGraw-Hill, Inc. 1994

Back to the OS Homepage