Requisito previo: exclusión mutua en sistemas distribuidos
El algoritmo basado en árbol de Raymond es un algoritmo basado en bloqueo para la exclusión mutua en un sistema distribuido en el que un sitio puede ingresar a la sección crítica si tiene el token. En este algoritmo, todos los sitios se organizan como un árbol dirigido, de modo que los bordes del árbol se asignan en dirección al sitio que contiene el token. El sitio que contiene el token también se denomina raíz del árbol.
Estructura de datos y notaciones:
- Cada sitio Si mantiene una cola FIFO, llamada request_q.
Esta cola almacena las requests de todos los sitios vecinos que han enviado una solicitud de token al sitio Si pero aún no se les ha enviado el token. Un request_q no vacío en cualquier sitio indica que el sitio ha enviado un mensaje de SOLICITUD al Node raíz.
Cada sitio Si tiene una variable local, llamada titular.
Esta variable apunta a un Node vecino inmediato en una ruta dirigida al Node raíz.
Algoritmo:
Para ingresar a la sección Crítica:
Cuando un sitio Si desea ingresar a la sección crítica, envía un mensaje de SOLICITUD al Node a lo largo de la ruta dirigida a la raíz, siempre que no tenga el token y su solicitud_q esté vacía. Después de enviar el mensaje de SOLICITUD, agrega su solicitud a su request_q.
cuando un sitio Sj en la ruta a la raíz recibe el mensaje SOLICITUD del sitio Si, coloca la SOLICITUD en su solicitud_q y envía el mensaje SOLICITUD a lo largo de la ruta dirigida a la raíz, si no ha enviado ningún mensaje SOLICITUD para la SOLICITUD recibida previamente mensaje.
Cuando el sitio raíz Sr (que tiene el token) recibe el mensaje SOLICITUD, envía el token al sitio solicitante y establece su variable de soporte para que apunte a ese sitio.
Al recibir el token, Site Sj elimina la entrada superior de su request_q y envía el token al sitio indicado por la entrada eliminada. la variable titular del Sitio Sj está configurada para apuntar a ese sitio.
Después de eliminar la entrada superior de request_q, si aún no está vacío, el sitio Sj envía un mensaje de SOLICITUD al sitio indicado por la variable del titular para recuperar el token.
Para ejecutar la sección crítica:
El sitio Si ejecuta la sección crítica si ha recibido el token y su propia entrada está en la parte superior de su request_q.
Para liberar la sección crítica:
Después de terminar la ejecución de la sección crítica, el sitio Si hace lo siguiente:
Si su request_q no está vacío, entonces elimina la entrada superior de su <request_q y luego envía el token a ese sitio indicado por la entrada eliminada y también su variable de titular se configura para apuntar a ese sitio.
Después de realizar la acción anterior, si request_q aún no está vacío, entonces el sitio Si envía un mensaje de SOLICITUD al sitio señalado por la variable del titular para recuperar el token.
Complejidad del mensaje:
en el peor de los casos, el algoritmo requiere 2 * (longitud de ruta más larga del árbol) invocación de mensaje por entrada de sección crítica. Si todos los Nodes están dispuestos en línea recta, la longitud de la ruta más larga será N – 1 y, por lo tanto, el algoritmo requerirá 2 * (N -1) invocaciones de mensajes para la entrada a la sección crítica. Sin embargo, si todos los Nodes generan la misma cantidad de mensajes SOLICITUD para el privilegio, el algoritmo requerirá aproximadamente 2*N/3 mensajes por entrada de sección crítica.
Inconvenientes del algoritmo basado en árboles de Raymond:
puede causar inanición: el algoritmo de Raymond utiliza una estrategia codiciosa ya que un sitio puede ejecutar la sección crítica al recibir el token incluso cuando su solicitud no está en la parte superior de la cola de requests. Esto afecta la equidad del algoritmo y, por lo tanto, puede causar inanición.
Actuación:
El retraso de sincronización es (T * log N )/ 2, porque la distancia promedio entre dos sitios para ejecutar sucesivamente la sección crítica es (Log N)/2. Aquí T es el tiempo máximo de transmisión del mensaje.
En condiciones de carga pesada, el retraso de sincronización se convierte en T porque un sitio ejecuta la sección crítica cada vez que se transfiere el token.
La complejidad del mensaje de este algoritmo es O (log N) ya que la distancia promedio entre dos Nodes en un árbol con N Nodes es log N
Interbloqueo es imposible
El código para visualizar el algoritmo basado en el árbol de Raymond se proporciona a continuación:
C++
//Contributed by Anuj Kumar Sahu
#include <stdio.h>
#include <stdlib.h>
// Define Structure for Node
struct node {
int id;
int holderval;
struct node* l;
struct node* r;
int require[20];
};
typedef struct node node;
//Function for inorder Traversal
void TraversalInorder(node* roonodeT)
{
if (roonodeT == NULL) {
return;
}
TraversalInorder(roonodeT->l);
printf("%d %d\n", roonodeT->id, roonodeT->holderval);
TraversalInorder(roonodeT->r);
}
void token(node* roonodeT, int NodeCS)
{
if (NodeCS == roonodeT->id) {
printf("%d\n", roonodeT->id);
roonodeT->holderval = roonodeT->id;
return;
}
else if (NodeCS < roonodeT->id) {
roonodeT->holderval = (roonodeT->l)->id;
printf("%d->", roonodeT->id);
roonodeT = roonodeT->l;
token(roonodeT, NodeCS);
}
else if (NodeCS > roonodeT->id) {
roonodeT->holderval = (roonodeT->r)->id;
printf("%d->", roonodeT->id);
roonodeT = roonodeT->r;
token(roonodeT, NodeCS);
}
}
// Function to Insert Node
void NodeTinsert(node* nodeNew, node* roonodeT)
{
if (nodeNew->id > roonodeT->id) {
if (roonodeT->r == NULL) {
roonodeT->r = nodeNew;
nodeNew->holderval = roonodeT->id;
}
else
NodeTinsert(nodeNew, roonodeT->r);
}
if (nodeNew->id < roonodeT->id) {
if (roonodeT->l == NULL) {
roonodeT->l = nodeNew;
nodeNew->holderval = roonodeT->id;
}
else
NodeTinsert(nodeNew, roonodeT->l);
}
}
// Driver Function
int main()
{
node *roonodeT = NULL, *nodeNew = NULL, *node1;
int i;
// Value to be given below
int n = 5;
int nodeT = 3;
int idValue;
int arr[5] = { 1, 2, 3, 4, 5 };
int NodeCS, option;
roonodeT = (struct node*)malloc(sizeof(node));
node1 = (struct node*)malloc(sizeof(node));
roonodeT->id = nodeT;
roonodeT->r = roonodeT->l = NULL;
roonodeT->holderval = roonodeT->id;
for (i = 0; i < n; i++) {
idValue = arr[i];
nodeNew = (struct node*)malloc(sizeof(node));
nodeNew->l = nodeNew->r = NULL;
if (i == nodeT)
i++;
nodeNew->id = idValue;
NodeTinsert(nodeNew, roonodeT);
}
TraversalInorder(roonodeT);
NodeCS = 2;
token(roonodeT, NodeCS);
return -1;
}
1 3 2 1 3 3 4 3 3->1->2