The Scheduling Algorithm

In this section the pseudo-code of the scheduling algorithm is presented. Each replica has an associated scheduler thread as explained above. All the replicas of the server will execute this algorithm that will ensure replica consistency. When the control is transferred to the scheduler, it executes the following algorithm:
1.
If there is one or more server threads that can be executed, that is, if the queue of ready threads is not empty, the first one is dequeued. If there is not any awaited messages on an entry level queue of the server thread, the scheduler will move messages from the transaction level queue to the corresponding entry level queues until an awaited message is moved (it is sure that an awaited message will be found because otherwise the server thread woud not be in the queue). Finally, the control is transferred to server thread.
2.
If the queue of ready threads is empty, then the scheduler takes a message from the communication level queue and depending on its contents takes one of the following actions:
(a)
If it is the first request from a client transaction, the scheduler registers the transaction, creates the associated server thread and inserts the message on the corresponding entry queue transferring the control to the server thread.
(b)
If the message comes from a client transaction already registered, then the message is moved to the transaction level queue:
i.
If the server thread unblocks with this message, then the control is transferred to it.
ii.
Otherwise, extracts a new message from the communication queue and processes it.
(c)
If the message corresponds to a transaction commitment or abort, the scheduler processes it. As a consequence locks can be released and some server threads can be unblocked, so the scheduler will queue them in the queue of ready server threads. Control will be transferred to the first server thread of the queue.
(d)
If the message reports that the client has finished then:
i.
If the server thread finished, no action must be taken and the scheduler processes the next message.  
ii.
If the server thread is blocked waiting for a message, it means that the client has not finished the protocol. As a consequence the server thread is aborted.  
iii.
If the server thread is ready, it will eventually finish or block. If it blocks the scheduler will apply items 2(d)i and 2(d)ii.
(e)
If the message is aimed to a server thread that has ended, then the scheduler will report to the client transaction that the protocol has been violated and that the transaction must abort. If a server thread finishes its execution and its queues are not empty it will also abort.



1999-11-17