Task Synchronisation

Synchronisation in distributed systems can reveal itself as a severe problem. With a centralised approach it is the presence of a single point of failure. In an approach aiming at a distributed solution, it is the problem of finding an algorithm that guarantees atomicity and consistency of the operation as well as good performance[Lam79,JNW96]. In the special case of an application control system, we can exploit the local knowledge about the tasks on the cluster nodes for achieving these goals.

We chose to separate getting exclusive access to the task capsules and performing operations on them safely in critical sections. This allows us to bypass getting permission, if the operation does not interfere with other ones, thus gaining the potential of increasing efficiency. Furthermore the problem of finding a suitable distributed mutual exclusion algorithm can be decoupled from other issues. The prototype application control system offers two primitives through the execution environment interface to perform synchronisation operations on tasks: getToken and releaseToken. Calling getToken for a specific task capsule is used to acquire the right to perform operations exclusively on this task. Requests for a token that is associated with a task capsule can be sent to any node in the cluster that hosts a copy of this task. The token will not be granted to any other requester until it is released. It is however still possible for other operators to access this task. The application programmer has to insure proper usage of synchronisation. The getToken operation takes a task identifier as a parameter and has to be issued on a node that hosts a clone of the task (see figure 58). As the list of nodes on which the application has been created is replicated on all these nodes, a primary token home site can be identified. This is the first one in the list. The request for the token is forwarded to this node. Even if getToken requests from several sites are issued concurrently to different nodes they will all be put into sequential order on the token home site. One requester will be granted the token, the others are put into a list of pending requests. As soon as the token is returned the next pending node is notified and is granted the token.

The algorithm is fault tolerant in case there is at least one functional operational node that hosts a clone of the running task for which exclusive access is required. If the first node in the list is not reachable due to software or hardware errors, the next node in the list is elected as the token home (see figure 59). This is done by issuing a getToken operation to the next node in the list. The node recognises that it is not the first one in the list. This indicates that some communication problems have been encountered with the sites that are earlier in the list. The addressed node sets itself to be the new home of the token. It moves itself to the head of the list and notifies the requester. This one can also remove the faulty node from its list. In any case it moves the responding node to the head of the list. As such it becomes the new token home also at the requester site. This will work also with concurrent accesses as the list of nodes is available on all sites hosting a clone of the task capsule. Nodes that are reset and rejoin the system do not pose a problem. They will not have knowledge of the tasks for which they are requested to grant a lock and thus will not affect the algorithm. Other strategies, such as cloning an existing task to this node again, have to be implemented in order to completely reintegrate such a node. A node has however to ensure that it recognises if it is not accessible from other systems and reset itself so that no inconsistent state is introduced due to temporary unavailabilities.

When a node receives a request for a token and it recognizes that it is not the head of the list, it cannot tell immediately if it is safe to grant the token or not. The token for this task could have been requested by somebody before the original token home became unavailable (see figure 60). Therefore granting the token would produce an inconsistent state. Requesters in our algorithm however keep a connection to the token holder open until they return the token. So they can recognize if the holder fails while they own the token. If this happens they notify the next node in the list of this event. This node will therefore wait for a configurable amount of time if somebody requests a token. If the notification from the actual token holder arrives in time, it can put the waiting request into a pending queue. Otherwise, we assume that there the token has not been held while the original token home node failed. The token is granted in this case. In the case of an existing token holder of which we have knowledge, the token will eventually be returned to the new home. Complete fault tolerance cannot be achieved with this scheme, as a node could leave the cluster while a requester is waiting for the token to be granted. Furthermore the timeout between a request to a subsequent node in the list and the node waiting for a message from a potential token holder has to be long enough, so that no inconsistencies occur. C++ like pseudocode for the decentralised algorithm is shown in figures 61 and 62.