4. CONCURRENCIA: EXCLUSIÓN MUTUA Y SINCRONIZACIÓN.
Es aparente que las nociones de procesos y recursos están estrechamente vinculadas. Un proceso es una tarea, identificada como una secuencia de instrucciones ejecutándose, o una colección de instrucciones formando un programa. Un recurso, por otra parte, es un término incluido en el sistema operativo, como también impresoras, discos, cintas de discos, procesos y repartos de la capacidad de memoria. Sin embargo, los recursos no son tratados en forma igualitaria por el S.O. y dependiendo de su cinta, tratará los procesos en forma diferente.
Los recursos no expropiables (No Preemption) son usados por los procesos que requieren una utilización de recursos ininterrumpidos. Los recursos expropiables (Preemption) requieren un control del S.O. para cambiar correctamente la utilización de los recursos.
EXCLUSIÓN MUTUA: SOLUCIONES POR SOFTWARE.
ALGORITMOS DE SINCRONIZACIÓN CON ESPERA ACTIVA (BUSY WAITING)
Se utiliza una variable global que indica el estado de la región crítica, la cual es consultada cuando se requiere entrar. Esta solución no funciona si se produce una interrupción inmediatamente antes de que la variable antes mencionada se active. (Similar al Segundo Intento de Dekker)
Espera ocupada por turnos (alternancia)
Utiliza una variable global, la cual si posee valor i indica que le proceso Pi puede entrar. Asegura que haya sólo un proceso en la región crítica. Exige alternancia estricta. Si la variable está en 0 y P1 está listo para entrar entonces debe esperar, aunque P0 no esté en la región crítica. (Similar al Primer Intento de Dekker)
Utilizaremos para su descripción el “protocolo del iglú”. Un proceso (P0 o P1) que desee ejecutar su sección crítica entra primero en el iglú y examina la pizarra. Si su número está escrito en ella, el proceso puede abandonar el iglú y continuar con su sección crítica. En caso contrario, abandona el iglú y se ve obligado a esperar, ingresando de vez en cuando para mirar la pizarra hasta que se le permita entrar a su sección crítica. Un proceso frustrado no puede hacer nada productivo hasta que obtiene permiso para entrar a su sección crítica (por ello, el nombre de espera activa), debiendo persistir y comprobar periódicamente el iglú, consumiendo tiempo del procesador mientras espera su oportunidad.
Después de que un proceso haya obtenido acceso a su sección crítica y tras terminar con ella, debe volver al iglú y escribir el número del otro proceso en la pizarra.
PROCESO 0 PROCESO 1
....... .......
while (turno ¹ 0) do (nada); while (turno ¹ 1) do (nada);
<sección crítica>; <sección crítica>;
turno:=1; turno:=0;
....... .......
- Ventaja: garantiza el cumplimiento de la exclusión mutua.
- Inconveniente 1: los procesos deben alternarse en forma estricta en el uso de sus secciones críticas; así pues, el ritmo de ejecución viene dado por el más lento.
- Inconveniente 2: si un proceso falla (tanto dentro como fuera de su sección crítica), el otro proceso se bloquea permanentemente.
Segundo intento
En el primer intento se almacenaba el nombre del proceso que podía entrar en su sección crítica cuando, en realidad, lo que hacía falta era tener información del estado de ambos procesos. En realidad, cada proceso debería tener su propia llave de la sección crítica para que si en uno se produce un error, el otro pueda seguir accediendo a su sección crítica. Cada proceso tiene ahora su propio iglú y puede mirar la pizarra del otro, pero no modificarla. Cuando un proceso desea entrar en su sección crítica, comprueba periódicamente la pizarra del otro hasta que encuentra escrito en ella ”Falso”, lo que indica que el otro proceso no está en su sección crítica. Entonces, se dirige rápidamente hacia su propio iglú, entra y escribe “Cierto” en la pizarra, continuando ahora con su sección crítica.
PROCESO 0 PROCESO 1
...... ......
while (señal_b) do (nada); while (señal_a) do (nada);
señal_a = True; señal_b = True;
< sección crítica >; < sección crítica >;
señal_a = False; señal_b = False;
...... ......
- Ventaja: si uno de los procesos falla fuera de la sección crítica, el otro proceso no queda bloqueado.
- Inconveniente 1: si uno de los procesos falla dentro de su sección crítica, el otro proceso quedará bloqueado permanentemente.
- Inconveniente 2: no soluciona el problema de la exclusión mutua. Consideremos la siguiente secuencia:
. P0 ejecuta la sentencia while y encuentra señal_b a falso
. P1 ejecuta la sentencia while y encuentra señal_a a falso
. P0 pone señal_a a true y entra en su sección crítica
. P1 pone señal_b a true y entra en su sección crítica
Puesto que ambos procesos están en sus secciones críticas, el programa Es incorrecto. Este intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado, pero antes de que pueda entrar en su sección crítica.
Tercer intento
PROCESO 0 PROCESO 1
...... ......
señal_a = True; señal_b = True;
while (señal_b) do (nada); while (señal_a) do (nada);
< sección crítica >; < sección crítica >;
señal_a = False; señal_b = False;
...... ......
Como antes, si un proceso falla dentro de la sección crítica, incluyendo el código para dar valor a las señales que controlan el acceso a la sección crítica, el otro proceso se bloquea y si un proceso falla fuera de su sección crítica, el otro proceso no se bloquea.
- Ventaja: garantiza la exclusión mutua
- Inconveniente: si ambos procesos ponen sus señales a “true” antes de que ambos hayan ejecutado la sentencia while, cada uno pensará que el otro ha entrado en su sección crítica. El resultado es un interbloqueo.
Cuarto intento
El inconveniente en el tercer intento era que un proceso fijaba su estado sin conocer el estado del otro. Se puede intentar arreglar esto haciendo que los procesos sean más educados: deben activar su señal para indicar que desean entrar en la sección crítica, pero deben estar listos para desactivar la señal y ceder la preferencia al otro proceso.
PROCESO 0 PROCESO 1
...... ......
señal_a = True; señal_b = True;
while (señal_b) do while (señal_a)
begin begin
señal_a = Falso; señal_b = Falso;
< espera cierto tiempo > < espera cierto tiempo >;
señal_a = True; señal_b = True;
end; end;
< sección crítica >; < sección crítica >;
señal_a = Falso; señal_b = Falso;
...... ......
- Ventaja: la exclusión mutua está garantizada
- Inconveniente: se produce un problema ante un “exceso de cortesía” por parte de ambos procesos. Veamos la siguiente secuencia:
. P0 pone señal_a a cierto
. P1 pone señal_b a cierto
. P0 comprueba señal_b
. P1 comprueba señal_a
. P0 pone señal_a a falso
. P1 pone señal_b a falso
. P0 pone señal_a a cierto
. P1 pone señal_b a cierto
Esta secuencia podría prolongarse indefinidamente y ningún proceso podría entrar en su sección crítica. Estrictamente hablando, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los dos procesos rompería este ciclo y permitiría a uno entrar en la sección crítica. Aunque no es probable que esta situación se mantenga por mucho tiempo, es una situación posible. Así entonces, se rechaza el cuarto intento.
Una solución correcta
Hay que poder observar el estado de ambos procesos, que viene dado por la variable señal. Y de algún modo, se hace necesario imponer algún orden en la actividad de los dos procesos para evitar el problema de “cortesía mutua” que se observó en el cuarto intento. La variable turno del primer intento puede usarse en esta labor; en este caso, la variable indica qué proceso tiene prioridad para exigir la entrada a la sección crítica. Ahora hay un iglú “árbitro” con una pizarra llamada “turno”. Cuando P0 quiere entrar en su sección crítica, pone su señal a cierto. A continuación, va y mira la señal de P1. Si ésta está puesta a falso, P0 puede entrar inmediatamente en su sección crítica. En otro caso, P0 va a consultar al árbitro. Si encuentra turno = 0, sabe que es momento de insistir y comprueba periódicamente el iglú de P1. Este otro se percatará en algún momento de que es momento de ceder y escribirá “falso” en su pizarra, permitiendo continuar a P0. Después de que P0 haya ejecutado su sección crítica, pone su señal a “falso” para liberar la sección crítica y pone turno = 1 para traspasar el derecho de insistir a P1.
PROCESO 0 PROCESO 1
begin begin
repeat repeat
señal_a = True; señal_b = True;
while (señal_b) do while (señal_a) do
if (turno) then if (!turno) then
begin begin
señal_a = Falso; señal_b = Falso;
while (turno) do (nada); while (!turno) do (nada);
señal_a = True; señal_b = True;
end; end;
< sección crítica >; < sección crítica >
turno = 1; turno = 0;
señal_a = Falso; señal_b = Falso;
< resto >; < resto >;
forever; forever;
end; end;
El algoritmo de Dekker resuelve el problema de la exclusión mutua, pero con un programa complejo. Entonces, Peterson desarrolló una solución más simple: la variable global señal indica la posición de cada proceso con respecto a la exclusión mutua y la variable global turno resuelve los conflictos de simultaneidad. Este algoritmo puede generalizarse para el caso de n procesos.
PROCESO 0 PROCESO 1
begin begin
repeat repeat
señal_a = True; señal_b = True;
turno = 1; turno = 0;
while (señal_b and turno) do (nada); while (señal_a and !turno) do (nada);
< sección crítica >; < sección crítica >;
señal_a = Falso; señal_b = Falso;
< resto >; < resto >;
forever; forever;
end; end;