Algoritmos asociados con la Exclusión mutua

Vista previa del material en texto

Algoritmos asociados con la exclusión mutua
Algoritmo de Dekker
El algoritmo de Dekker es un algoritmo clásico diseñado para proporcionar exclusión mutua en un entorno de concurrencia. Fue propuesto por Edsger W. Dijkstra en 1965 y es uno de los primeros algoritmos para garantizar la sección crítica en sistemas multiprocesador.
El objetivo principal del algoritmo de Dekker es permitir que dos procesos o hilos compartan un recurso de forma segura, evitando condiciones de carrera y garantizando que solo un proceso pueda acceder al recurso a la vez.
El algoritmo se basa en el uso de variables compartidas y banderas (flags) para lograr la exclusión mutua. A continuación se presenta una descripción básica del algoritmo de Dekker:
1. Cada proceso tiene una variable booleana (flag) que indica su intención de entrar en la sección crítica. Inicialmente, ambas banderas se establecen en falso.
2. Cada proceso ejecuta un bucle infinito que contiene tres fases: preprotocolo, protocolo y postprotocolo.
3. En la fase de preprotocolo, un proceso establece su bandera en verdadero para indicar su intención de entrar en la sección crítica. Luego, comprueba si el otro proceso también tiene la intención de entrar en la sección crítica. Si es así, pasa a la siguiente fase (protocolo) y espera a que la bandera del otro proceso se establezca en falso.
4. En la fase de protocolo, solo un proceso a la vez puede entrar en la sección crítica. La decisión se toma en base a la bandera del otro proceso y al propio turno del proceso. Si el otro proceso no tiene la intención de entrar en la sección crítica o si es el turno del proceso actual, se le permite entrar en la sección crítica. De lo contrario, el proceso debe esperar en esta fase hasta que se cumpla la condición.
5. En la fase de postprotocolo, el proceso sale de la sección crítica y restablece su bandera a falso para indicar que ha completado su trabajo en la sección crítica.
El algoritmo de Dekker se basa en la alternancia controlada de la entrada en la sección crítica entre los dos procesos. Sin embargo, también sufre de varios problemas, como el interbloqueo (deadlock) y la violación de la propiedad de la exclusión mutua en ciertos escenarios. Estos problemas llevaron a la formulación de otros algoritmos más sofisticados, como el algoritmo de Peterson y el algoritmo de Lamport, que abordan las limitaciones del algoritmo de Dekker.
A pesar de sus limitaciones, el algoritmo de Dekker fue un hito importante en la historia de la concurrencia y sentó las bases para el desarrollo posterior de algoritmos de exclusión mutua más eficientes y seguros.
Cabe destacar que en la actualidad existen otros enfoques más avanzados para garantizar la exclusión mutua, como los semáforos, los monitores y los mecanismos de sincronización proporcionados por los sistemas operativos y los lenguajes de programación modernos. Estos enfoques ofrecen soluciones más robustas y menos propensas a errores que el algoritmo de Dekker.
Este algoritmo también cuenta con cinco versiones del algoritmo de Dekker, teniendo ciertos fallos los primeros cuatro. De estas versiones la versión 5 es la mas eficiente combinando la 1 y 4. Estos son:
· 1er Algoritmo
Garantiza la exclusión mutua, pero su desventaja es que acopla los procesos fuertemente, esto significa que los procesos lentos atrasan a los procesos rápidos.
· 2do Algoritmo
Problema interbloqueo. No existe la alternancia, aunque ambos procesos caen a un mismo estado y nunca salen de ahí.
· 3er Algoritmo
Colisión región critica no garantiza la exclusión mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la región critica.
· 4to Algoritmo
Postergación indefinida. Aunque los procesos no están en interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda.
· 5to Algoritmo
El quinto algoritmo de Dekker es la versión optimizada y que no presenta problemas como las cuatro versiones anteriores, para su estructuración se hace combinación de dos algoritmos de acuerdo al orden de prioridad de desempeño y funcionamiento de las cuatro versiones conocidas.
Algoritmo de Peterson
El algoritmo de Peterson, también conocido como solución de Peterson, ​ es un algoritmo de programación concurrente para exclusión mutua, que permite a dos o más procesos o hilos de ejecución compartir un recurso sin conflictos, utilizando sólo memoria compartida para la comunicación.
Gary L. Peterson desarrolló en 1981 el algoritmo básico para dos procesos, como una simplificación del algoritmo de Dekker. El algoritmo básico puede generalizarse fácilmente a un número arbitrario de procesos. 
Algoritmo para dos procesos
Los procesos p0 y p1 no pueden estar en la sección crítica al mismo tiempo: si p0 está en la sección crítica, entonces bandera[0] = true, y ocurre que bandera[1] = false, con lo que p1 ha terminado la sección crítica, o que la variable compartida turno = 0, con lo que p1 está esperando para entrar a la sección crítica. En ambos casos, p1 no puede estar en la sección crítica.
Algoritmo para N procesos
Algoritmo de Szymanski 
El algoritmo de exclusión mutua de Szymański es un algoritmo de exclusión mutua ideado por el científico informático Dr. Bolesław Szymański , que tiene muchas propiedades favorables, incluida la espera lineal, y cuya extensión resolvió el problema abierto publicado por Leslie Lamport. 
El algoritmo se basa en una sala de espera con una puerta de entrada y salida. Inicialmente, la puerta de entrada está abierta y la puerta de salida está cerrada. Todos los procesos que solicitan el ingreso a la sección crítica aproximadamente al mismo tiempo ingresan a la sala de espera; el último de ellos cierra la puerta de entrada y abre la puerta de salida. Luego, los procesos ingresan a la sección crítica uno por uno (o en grupos más grandes si la sección crítica lo permite). El último proceso en salir de la sección crítica cierra la puerta de salida y vuelve a abrir la puerta de entrada, por lo que puede entrar el siguiente lote de procesos. 
El algoritmo de Hunt-Szymanski es una modificación de una solución básica para el problema de la subsecuencia común más larga que tiene una complejidad O ( n 2 ) . La solución se modifica para que haya menores requisitos de tiempo y espacio para el algoritmo cuando trabaja con entradas típicas. Sea P ij la longitud de la subsecuencia común más larga para los primeros i elementos de A y los primeros j elementos de B .
 El algoritmo es el siguiente: 
Sea Ai el i-ésimo elemento de la primera sucesión.
Sea Bj el j-ésimo elemento de la segunda sucesión.
Sea Pij la longitud de la subsecuencia común más larga para los primeros i elementos de A y los primeros j elementos de B.
Por ejemplo, considere las sucesiones A y B; A contiene tres elementos:
B contiene tres elementos:
Los pasos que realizaría el algoritmo anterior para determinar la longitud de la subsecuencia común más larga para ambas secuencias se muestran en el diagrama. El algoritmo informa correctamente que la subsecuencia común más larga de las dos secuencias tiene una longitud de dos elementos.
Algoritmo de panadería blanco y negro 
El algoritmo de panadería blanco y negro es una mejora del algoritmo de panadería de Lamport que satisface todas las condiciones de un algoritmo exclusivo mutuo. Este algoritmo conserva el algoritmo original de Lamport mientras usa un número finito de registros atómicos de tamaño acotado y satisface la equidad FIFO. El algoritmo de panadería blanco y negro está diseñado para proporcionar una solución basada en software para la exclusión mutua. 
El algoritmo de panadería blanco y negro limita principalmente la naturaleza ilimitada del algoritmo de panadería Lamport al agregar un bit adicional, que tendrá un valor de blanco o negro. Funciona según el mismo principio al satisfacer el procedimiento FIFO, pero limita los registros atómicos a través de una serie de pasos diferentes. Cada proceso debe esperar para ingresar a la sección crítica hasta que su númerode ticket de color sea el más bajo de su grupo. Si el color y el número de ticket de dos procesos son iguales, el proceso con el identificador más pequeño entrará en estado crítico.
Algoritmo de Maekawa
El algoritmo de Maekawa es un algoritmo que se emplea para crear exclusión mutua en un sistema distribuido. Para una red de N nodos, el algoritmo utilizará únicamente un total de c*√N mensajes para crear esta exclusión mutua, siendo 'c' una constante que puede variar entre los valores 3 y 5. En esta red supuesta, también se supone que todos los nodos se comunican solamente mediante mensajes y no tienen memoria compartida, así como que los mensajes se reciben en el mismo orden que han sido enviados.
Algoritmo
· Cuando un proceso recibe una petición (request) de un nodo i, la almacena en una cola ordenada por prioridad. 
· Si no ha concedido la exclusión a otro, envía un mensaje para conceder(locked) la exclusión mutua. 
· Si ya la ha concedido, comprueba si i tiene menos prioridad que el proceso al que se la ha concedido, si es así, contesta a i con un mensaje de fallo (failed).
· Si i tiene más prioridad, se envía un mensaje al proceso al que se le dio permiso preguntando (inquire) si ha obtenido permiso del resto de los procesos.
· Cuando un proceso recibe un mensaje preguntando contesta con un mensaje liberar (relinquish),si ha recibido algún mensaje de fallo.
· Cuando un proceso recibe un mensaje liberar (relinquish), almacena en la cola la petición a la que había concedido la exclusión mutua y se la concede al proceso de mayor prioridad de la cola (envía un mensaje conceder).Algoritmo de Maekawa 1
Algoritmo de Maekawa 2
¿Como funciona?
No necesitamos que todos los procesos nos permitan el acceso 
Basta con obtener el permiso de un subconjunto de K procesos, siempre que los subconjuntos usados por cualquier par de procesos se solapen con unos determinados criterios 
Elección de los subconjuntos de voto Vi para cada proceso pi: 
Para todo i, j = 1, 2, …, N 
 pi debe pertenecer a Vi 
 Vi∩Vj ≠ ∅ 
 |Vi| = K 
 pj está contenido en M de los subconjuntos de voto 
Maekawa demuestra que la solución óptima es K = M ~ √N
Creación Subconjuntos de Voto
Para construir los subconjuntos de voto, el algoritmo de Maekawa utiliza la idea de "triángulos". Un triángulo es un subconjunto de tres nodos en el que cada par de nodos tiene un camino directo entre ellos. En un sistema distribuido, cada nodo puede ver los nodos que están directamente conectados a él, y los nodos que están a una distancia de dos saltos (es decir, los nodos que están conectados a los nodos que están conectados directamente al nodo). Utilizando esta información, cada nodo puede construir una lista de triángulos a los que pertenece.
Algoritmo de Maekawa: ejemplo
Pseudocódigo
En la inicialización
estado = LIBERADA;
 votado = FALSO; 
Cuando pi quiere entrar en la SC
 estado = BUSCADA; 
Multidifusión de la petición de entrada en SC a los procesos en Vi - {pi}; 
Espera hasta que (nº de respuestas = (K-1)); 
estado = TOMADA; 
Al salir de la SC 
estado = LIBERADA;
 Multidifunde liberar a los procesos en Vi - {pi};
Cuando pi recibe una petición de pj (i≠j) 
si (estado = TOMADA o votado = CIERTO o
 (estado = BUSCADA y (T, pi ) < (Tj , pj )*))
 pon en la cola la petición, por parte de pj 
si no
 responde inmediatamente a pj 
 votado = CIERTO; 
Al recibir en pj liberar de parte de pi (i≠j) 
si (la cola de peticiones no está vacía) 
 quita la cabeza de la cola (p. ej. pk ); 
 envía respuesta a pk ;
 votado = CIERTO; 
si no 
 votado = FALSO;
De esta manera, cada nodo tiene múltiples subconjuntos de voto que se superponen con los de otros nodos, lo que garantiza que solo un nodo a la vez pueda obtener el recurso compartido
Algoritmo de Maekawa: análisis
· Requisitos 
· Cumple con la seguridad 
· No cumple con la pervivencia, pues puede producir interbloqueos 
· Solución mejorada por Sanders [1987] mediante el uso de una ordenación “antes que” → cumple con pervivencia y ordenación 
· Rendimiento 
· Retraso de entrada: 
· Petición de entrada en SC: √N 
· Concesión de entrada en SC: √N 
· Retraso en el relevo: √N 
· Ancho de banda: 3√N 
· Mejora Ricart y Agrawala si N>4
Exclusión mutua distribuida
Comparativa
Algoritmo de panadería de Lamport
El algoritmo de panadería de Lamport es un algoritmo informático que garantiza el uso eficiente de los recursos compartidos en un entorno multiproceso. Este algoritmo fue concebido por Leslie Lamport y se inspiró en la metodología operativa de una panadería por orden de llegada, o por orden de llegada (FIFO). El algoritmo de panadería de Lamport es un algoritmo de exclusión mutua que restringe el acceso simultáneo de un recurso a dos o más procesos.
Los principios operativos detrás del algoritmo de panadería de Lamport son muy simples. Todos los subprocesos del proceso deben tomar un número y esperar su turno para usar un recurso informático compartido o para ingresar a su sección crítica. El número puede ser cualquiera de las variables globales, y los procesos con el número más bajo se procesarán primero. Si hay un empate o un número similar compartido por ambos procesos, se administra a través de su ID de proceso. Si un proceso finaliza antes de su turno, debe comenzar de nuevo en la cola del proceso.
Funcionamiento
Lamport imaginó una panadería con una máquina de numeración en su entrada para que cada cliente reciba un número único. Los números aumentan en uno a medida que los clientes ingresan a la tienda. Un contador global muestra el número del cliente al que se atiende actualmente. Todos los demás clientes deben esperar en una cola hasta que el panadero termine de atender al cliente actual y se muestre el siguiente número. Cuando el cliente termina de comprar y se deshace de su número, el empleado aumenta el número, lo que permite atender al siguiente cliente. Ese cliente debe sacar otro número de la máquina de numeración para poder comprar nuevamente.
Según la analogía, los "clientes" son hilos, identificados por la letra i , obtenidos a partir de una variable global.
Debido a las limitaciones de la arquitectura de la computadora, algunas partes de la analogía de Lamport necesitan una ligera modificación. Es posible que más de un hilo obtenga el mismo número n cuando lo soliciten; esto no se puede evitar. Por lo tanto, se supone que el identificador de hilo i también es una prioridad. Un valor más bajo de i significa una prioridad más alta y los subprocesos con una prioridad más alta ingresarán primero a la sección crítica.
Sección crítica
La sección crítica es aquella parte del código que requiere acceso exclusivo a los recursos y solo puede ser ejecutada por un hilo a la vez. En la analogía de la panadería, es cuando el cliente negocia con el panadero que los demás deben esperar.
Cuando un hilo quiere entrar en la sección crítica, tiene que comprobar si ahora es su turno para hacerlo. Debería comprobar el número n de todos los demás subprocesos para asegurarse de que tenga el más pequeño. En caso de que otro hilo tenga el mismo número, el hilo con la i más pequeña entrará primero en la sección crítica.
En pseudocódigo esta comparación entre los hilos una y b se puede escribir en la forma:
(n a , i a ) <(n b , i b ) // n a - el número de cliente para el hilo a , i a - el número de hilo para el hilo a
que es equivalente a:
(n a b ) o ((n a == n b ) y (i a b ))
Una vez que el hilo finaliza su trabajo crítico, se deshace de su número y entra en la sección no crítica .
Sección no crítica
La sección no crítica es la parte del código que no necesita acceso exclusivo. Representa un cálculo específico de subprocesos que no interfiere con los recursos y la ejecución de otros subprocesos.
Esta parte es análoga a las acciones que ocurren después de comprar, como devolver el cambio a la billetera.
Implementación del algoritmo
Definiciones
En el artículo original de Lamport, la variable de entrada se conoce como elección y se aplican las siguientescondiciones:
Las palabras que eligen [i] y el número [i] están en la memoria del proceso i, y son inicialmente cero.
El rango de valores del número [i] es ilimitado.
Un proceso puede fallar en cualquier momento. Suponemos que cuando falla, inmediatamente pasa a su sección no crítica y se detiene. Entonces puede haber un período en el que la lectura de su memoria dé valores arbitrarios. Eventualmente, cualquier lectura de su memoria debe dar un valor de cero.
Ejemplos de código
Pseudocódigo
En este ejemplo, todos los subprocesos ejecutan la misma función "principal", Thread. En aplicaciones reales, diferentes subprocesos a menudo tienen diferentes funciones "principales".
Tenga en cuenta que, como en el papel original, el hilo se comprueba antes de entrar en la sección crítica. Dado que las condiciones del bucle se evaluarán como falsas, esto no causa mucho retraso.
 // declaración y valores iniciales de variables globales Ingresando: matriz [ 1 .. NUM_THREADS] de bool = { falso }; Número : matriz [ 1 .. NUM_THREADS ] de entero = { 0 }; bloquear ( entero i ) { Ingresando [ i ] = verdadero ; Número [ i ] = 1 + máx. ( Número [ 1 ], ..., Número [ NUM_THREADS ]); Ingresando [ i ] = falso ; para ( entero j = 1 ; j <= NUM_THREADS ; j ++ ) { // Espere hasta que el hilo j reciba su número: while ( Ingresando [ j ]) { / * nada * / } // Espere hasta que todos los hilos con números más pequeños o con el mismo // número, pero con mayor prioridad, terminan su trabajo: while (( Número [ j ] ! = 0 ) && (( Número [ j ], j ) < ( Número [ i ], i ))) { / * nada * / } } } desbloquear ( entero i ) { Número [ i ] = 0 ; } Subproceso ( entero i ) { while ( verdadero ) { bloqueo ( i ); // La sección crítica va aquí ... desbloquear ( i ); // sección no crítica ... } }
Cada hilo solo escribe su propio almacenamiento, solo se comparten las lecturas. Es notable que este algoritmo no se construya sobre alguna operación "atómica" de nivel inferior, por ejemplo, comparar e intercambiar. La prueba original muestra que, para lecturas y escrituras superpuestas en la misma celda de almacenamiento, solo la escritura debe ser correcta. [ aclaración necesaria] La operación de lectura puede devolver un número arbitrario. Por lo tanto, este algoritmo se puede utilizar para implementar la exclusión mutua en la memoria que carece de primitivas de sincronización, por ejemplo, un disco SCSI simple compartido entre dos computadoras.
Es posible que la necesidad de la variable Entering no sea obvia, ya que no hay un "bloqueo" entre las líneas 7 a 13. Sin embargo, suponga que la variable se eliminó y dos procesos calcularon lo mismo Number[i]. Si el proceso de mayor prioridad se adelantó antes de la configuración Number[i], el proceso de baja prioridad verá que el otro proceso tiene un número cero y entra en la sección crítica; más tarde, el proceso de alta prioridad ignorará igual Number[i]para los procesos de menor prioridad y también ingresará a la sección crítica. Como resultado, dos procesos pueden ingresar a la sección crítica al mismo tiempo. El algoritmo de panadería usa la variable Entering para hacer que la asignación en la línea 6 parezca atómica; procesar i nunca se verá un número igual a cero para un proceso j que se va a recoger el mismo número que i.
Al implementar el pseudocódigo en un sistema de proceso único o bajo multitarea cooperativa, es mejor reemplazar las secciones de "no hacer nada" con un código que notifique al sistema operativo que cambie inmediatamente al siguiente hilo. Este primitivo a menudo se conoce como yield.
El algoritmo de panadería de Lamport asume un modelo de memoria de consistencia secuencial. Pocos idiomas o procesadores multinúcleo, si es que hay alguno, implementan un modelo de memoria de este tipo. Por lo tanto, la implementación correcta del algoritmo generalmente requiere la inserción de vallas para inhibir el reordenamiento. 
Algoritmo de la panadería
/* Variables globales */
Número: vector [1..N] de enteros = ftodos a 0);
Eligiendo: vector [1..N] de booleanos = ftodos a falso);
1* Código del hilo ¡ */
Hilo(i) £
loop £
/* Calcula el número de turno */
Eligiendo([i) = cierto;
Númerofi] + max(Número[1),..., Número[N]);
Eligiendo[i] = falso;
/* Compara con todos los hilos +/
[A
/* Si el hilo ¡ está calculando su número, espera a
que termine */
while ( Eligiendo(j)) (/* nada */ )
/* Si el hilo j tiene más prioridad, espera a que
ponga su número a cero */
/* ¡tiene más prioridad si su número de tuno es
más bajo que el de |, */
/* o bien si es el mismo número y además | es
menor que | 7
while ( (Número[) != 0) 82 (Número), |) <
(Númerofi). )) ) (/* nada */)
ra Fin de sección crítica */
Número(i] = 0;
/* Código restante */
)
Referencias
Hmong. (s.f.). Algoritmo de Hunt-Szymanski. Obtenido de https://hmong.es/wiki/Szyma%C5%84ski%27s_algorithm
Infor Uva Es. (24 de Mayo de 2023). Obtenido de https://www.infor.uva.es/~cllamas/concurr/pract98/sisos4/index.html
R, S. (24 de Mayo de 2023). Obtenido de Usal Es: http://vis.usal.es/rodrigo/documentos/sisdis/teoria/5-coordinacion.pdf
Theastrologypage. (s.f.). Obtenido de https://es.theastrologypage.com/black-white-bakery-algorithm#menu-3
Wikipedia. (s.f.). Obtenido de Wikipedia contributors. (n.d.). Algoritmo de Maekawa. Wikipedia, The Free Encyclopedia. https://es.wikipedia.org/w/index.php?title=Algoritmo_de_Maekawa&oldid=151071162
Wikipedia. (24 de Mayo de 2023). Obtenido de https://es.wikipedia.org/wiki/Algoritmo_de_Peterson#:~:text=El%20algoritmo%20de%20Peterson%2C%20tambi%C3%A9n,memoria%20compartida%20para%20la%20comunicaci%C3%B3n
Wikipedia. (24 de Mayo de 2023). Wikipedia - Hunt–Szymanski algorithm. Obtenido de https://en.wikipedia.org/wiki/Hunt%E2%80%93Szymanski_algorithm
Wikiwand. (24 de Mayo de 2023). Obtenido de Wikiwand: https://www.wikiwand.com/es/Algoritmo_de_Maekawa