Procesos Concurrentes Asíncronos

Definición

Concurrente: Compiten por la CPU y recursos a la vez.

Asíncrono: No ocurren en intervalos predecibles. No se puede asumir el tiempo que tarda en ejecutarse.

Exclusión Mutua

Ocurre cuando dos o más procesos intentan compartir un recurso no compartible (ej: impresora). Puede ser:

• Simple: Solo un proceso interviene en un momento dado (no lo controla el SO).
• Generalizada: Máximo de n procesos (n > 1), ejemplo: conectar a una base de datos. Hasta cierto punto, lo controla el SO.

Sección Crítica

Cuando un proceso accede a datos compartidos modificables, se encuentra en su sección crítica. Cuando un proceso está en su sección crítica, se debe garantizar que ningún otro proceso se encuentre en su sección crítica propia. La sección crítica evita que un proceso se pueda bloquear dentro de ella y mantiene un control sobre las terminaciones anormales de un proceso que se encuentra dentro de ella.

Primitivas de Exclusión Mutua

Garantía de la Sección Crítica

• Sección residual
• Protocolo de entrada a la sección crítica
• Sección crítica (parte del código que necesita garantizar la exclusión mutua)
• Protocolo de salida de la sección crítica

Sección Residual: Fragmento del proceso que no necesita acceso exclusivo. Para garantizar la exclusión mutua, se implementan instrucciones conocidas como primitivas de exclusión mutua, que son operaciones que actúan evitando que haya más de un proceso en su sección crítica.

Las 4 Reglas de Dijkstra

• No hacer suposiciones acerca de las instrucciones o del número de procesos soportados por la máquina. Es exclusivamente software. En caso de que dos operaciones se realicen a la vez, el resultado es no determinista. Los accesos son en orden aleatorio.
• No hacer suposiciones acerca de las velocidades relativas de ejecución de los procesos, salvo que no son cero.
• Un proceso que no está en su sección crítica no debe impedir que otro proceso progrese a la suya.
• Equidad: No se debe postergar indefinidamente la entrada de un proceso a su sección crítica.

Soluciones que cumplen estos requisitos: Algoritmo de Dekker y Peterson para la exclusión mutua de 2 procesos y el de Lamport para N procesos.

Espera Activa

También llamada espera improductiva. El proceso está ejecutando código mientras espera la ocurrencia del evento (espera sin hacer nada, ocurre en el protocolo de entrada). Se considera aceptable en los casos en los que el evento ocurrirá con seguridad y en un tiempo limitado.

Exclusión Mutua para 2 Procesos

Primer Intento

Se controla la exclusión mutua mediante dos variables lógicas globales (ej: p1Dentro, p2Dentro) que indican si un proceso ha entrado o no en su sección crítica. Si los dos procesos están fuera de la sección crítica y las dos variables son FALSE (el recurso está libre), no garantiza la exclusión mutua. Ambos procesos pueden estar en la sección crítica al mismo tiempo. Se da la espera activa.

while (true); while (p1Dentro); // Espera activa

Segundo Intento

Garantiza la exclusión mutua si las dos variables globales (ej: p1QuiereEntrar, p2QuiereEntrar) van precedidas por la activación de un indicador propio. Primero la asignación y después el while. Se soluciona la exclusión mutua, pero se da el interbloqueo (espera circular), también conocido como abrazo mortal o deadlock.

while(true); p1QuiereEntrar = true; while(p2QuiereEntrar);

Algoritmo de Dekker

Crea otra variable (ej: TurnoProceso) que indica el turno de prioridad. Se soluciona el interbloqueo, pero aunque los procesos no están en interbloqueo y soluciona la exclusión mutua en determinadas circunstancias, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda. Se da la espera activa.

Algoritmo de Peterson

También utiliza las tres variables, pero cambia el orden de ejecución, evitando también el interbloqueo, pero se da la inanición (no justa = equidad). Agotamiento de recursos y no acaba nunca. No se da el abrazo mortal.

Exclusión Mutua para N Procesos

Algoritmo de Lamport (Algoritmo de la Panadería)

Un proceso que desee entrar recibe un número de orden cuyo valor es mayor que el resto de los procesos. Luego, se queda esperando hasta que sea el menor valor de los que no han sido atendidos. No funciona.

Maneras de Resolver la Exclusión Mutua

La Instrucción TSL

Test and Set Lock (comprobación y asignación a cerrojo), TSL: Lee en un registro el contenido de una dirección de memoria y carga en esta un valor distinto de cero. El hardware garantiza que ningún otro procesador puede acceder a la palabra hasta que la instrucción haya terminado. Para coordinar el acceso a memoria compartida, se utiliza una variable indicador que, si vale cero, cualquier proceso la pone a 1 por medio de la instrucción TSL y accede al área de memoria compartida (cerrojo echado).

Semáforos

Para generalizar estas soluciones, Dijkstra ideó el concepto de semáforo. Es una variable entera con dos operaciones:

• Wait (protocolo de entrada): Comprueba el valor del contador. Si es > 0, resta 1 al contador. Si es = 0, bloquea el proceso y lo retiene en la cola de procesos.
• Signal: Comprueba la cola de procesos para saber si hay procesos bloqueados. Si está vacía, suma 1 al contador. Si no está vacía, desbloquea un proceso.

Init_sem: Inicialización de semáforos. Valor inicial = número de procesos. Si es binario, a cero.

Existen dos tipos de semáforos: binarios y generales. Para saber qué tipo de semáforo debemos usar, miramos el valor máximo que tomará el contador del semáforo. Si es > 1, general; si es = 1, binario. El contador nunca es negativo.

Con el mínimo de semáforos posibles, se maximiza la concurrencia.

Contadores de Eventos

• Advance(E): Señala que ha ocurrido un evento. Suma 1 a E.
• Read(E): Devuelve el contador actual E. Si devuelve algún n, es que han ocurrido n operaciones Advance.
• Await(E, v): Espera hasta que E supere a v, que ocurrirá cuando esté desbloqueado.