Raymond's algorithm

Last updated

Raymond's Algorithm is a lock based algorithm for mutual exclusion on a distributed system. It imposes a logical structure (a K-ary tree) on distributed resources. As defined, each node has only a single parent, to which all requests to attain the token are made.

Contents

Algorithm

Nodal properties

  1. Each node has only one parent to whom received requests are forwarded
  2. Each node maintains a FIFO queue of requests each time that it sees the token;
  3. If any node is forwarding privilege to other node and has non-empty queue then it forwards a request message along

Algorithm

  1. If a node i (not holding the token) wishes to receive the token in order to enter into its critical section, it sends a request to its parent, node j.
    • If node j FIFO is empty, node j shifts i into its FIFO queue; j then issues a request to its parent, k, that it desires the token
    • If node j FIFO queue is not empty, it simply shifts i into the queue
  2. When node k has token and receives the request from j it sends token to j and sets j as its parent
  3. When node j receives the token from k, it forwards the token to i and i is removed from the queue of j
    • If the queue of j is not empty after forwarding the token to i, j must issue a request to i in order to get the token back

Note: If j wishes to request a token, and its queue is not empty, then it places itself into its own queue. Node j will utilize the token to enter into its critical section if it is at the head of the queue when the token is received.

Complexity

Raymond's algorithm is guaranteed to be O(log n) per critical section entry if the processors are organized into a K-ary tree. Additionally, each processor needs to store at most O(log n) bits because it must track O(1) neighbors. [1]

Related Research Articles

FIFO (computing and electronics) scheduling algorithm

FIFO is an acronym for first in, first out, a method for organising and manipulating a data buffer, where the oldest (first) entry, or 'head' of the queue, is processed first. It is analogous to processing a queue with first-come, first-served (FCFS) behaviour: where the people leave the queue in the order in which they arrive.

Huffman coding entropy encoding algorithm used for lossless data compression

In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

Heap (data structure) tree-based data structure in computer science

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap is called the root node.

Mutual exclusion property of concurrency control, which is instituted for the purpose of preventing race conditions

In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters its critical section at the same time that another concurrent thread of execution enters its own critical section, which refers to an interval of time during which a thread of execution accesses a shared resource, such as shared memory.

In telecommunication, a distributed-queue dual-bus network (DQDB) is a distributed multi-access network that (a) supports integrated communications using a dual bus and distributed queuing, (b) provides access to local or metropolitan area networks, and (c) supports connectionless data transfer, connection-oriented data transfer, and isochronous communications, such as voice communications.

Dijkstras algorithm graph search algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Binary heap heap data structure that takes the form of a binary tree

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system such as a multitasking operating system. A semaphore is simply a variable. This variable is used to solve critical section problems and to achieve process synchronization in the multi processing environment. A trivial semaphore is a plain variable that is changed depending on programmer-defined conditions.

In computing, scheduling is the method by which work is assigned to resources that complete the work. The work may be virtual computation elements such as threads, processes or data flows, which are in turn scheduled onto hardware resources such as processors, network links or expansion cards.

The Chandy–Lamport algorithm is a snapshot algorithm that is used in distributed systems for recording a consistent global state of an asynchronous system. It was developed by and named after Leslie Lamport and K. Mani Chandy.

Petersons algorithm concurrent programming algorithm for mutual exclusion

Peterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary L. Peterson in 1981. While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.

<i>m</i>-ary tree Tree data structure in which each node has at most K children. From a graph theoretical perspective, k-ary trees are actually arborescences.

In graph theory, an m-ary tree is a rooted tree in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three.

Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion.

The Ricart-Agrawala algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport's Distributed Mutual Exclusion Algorithm, by removing the need for messages. It was developed by Glenn Ricart and Ashok Agrawala.

Maekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum like approach where any one site needs only to seek permissions from a subset of other sites.

In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task is begun, all network nodes are either unaware which node will serve as the "leader" of the task, or unable to communicate with the current coordinator. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader.

The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., d-ary heaps were invented by Donald B. Johnson in 1975.

Lamport's Distributed Mutual Exclusion Algorithm is a contention-based algorithm for mutual exclusion on a distributed system.

The Suzuki–Kasami algorithm is a token-based algorithm for achieving mutual exclusion in distributed systems. The process holding the token is the only process able to enter its critical section.

References

  1. R. Chow, T. Johnson; Distributed Operating Systems & Algorithms; Addison-Wesley, 1997.

See also