PCD: PROGRAMAS CONCURRENTES
En un programa concurrente no sabemos cual es el orden de ejecucion de las instrucciones (si un programa tiene dos procesos P1, P2 con 2 instrucciones cada uno, el orden puede ser el usual, alternados, inversos...) con lo cual hay que considerar todas las posibilidades.
Supongamos los siguientes procesos:
Y de forma interna, cada proceso hace, de forma secuencial, lo siguiente:
Bien, si el proceso uno se ejecuta primero y luego el proceso dos, no pasaría nada (o al revés) pero si ejecutamos simultaneamente ambas instrucciones. Veríamos lo siguiente:
Con lo cual la ejecución resulta fallida, y nosotros tenemos que garantizar que esto jamás ocurra. Para eso tenemos que hacer que se ejecute la operacion de incremento de forma ininterrumpida (cuando la haga uno el otro se espere) y es lo que llamamos ejecución atómica.
CARACTERISTICAS DE LOS SISTEMAS CONCURRENTES
Si tenemos dos conjuntos L(Sk) = {a1, a2,..., ak} que representa las variables que son accedidas en modo lectura y E(Sk) = {b1,b2,...,bk}, dos instrucciones Sm y Sn se pueden ejecutar concurrentemente si y solo si:
Dicho de otro modo, o leemos-escribimos cosas diferentes, o escribimos cosas diferentes. Lo unico que no importa es la lectura-lectura que siempre puede hacerse, en cualquier otro caso hay que poner dicha sentencia en ejecución atómica.
SINCRONIZACIÓN: EXCLUSIÓN MUTUA
Dado un recurso no compartible (un recurso que varios procesos utilizan pero no simultaneamente, como la pantalla, el disco duro, memoria...) se conoce como exclusión mutua a una sincronización necesaria para que los procesos utilicen el recurso pero no simultaneamente.
La zona de código donde se lleva a cavo la exclusión mutua es la 'seccion crítica'. Si un proceso está en la sección crítica ningún otro proceso debe de estar en la suya.
Segun la siguiente imagen, podemos ver que hay varias secciones críticas donde aparecen problemas por el indeterminismo:
Writeln(n) <-> Writeln(i)
Writeln(n) <-> Writeln("ok")
PROTECCION DE LA SECCIÓN CRÍTICA
La sección crítica (SC) estará protegida por una serie de instrucciones que, previamente, formaran el protocolo de entrada (PE)para permitir que un proceso accceda cuando deba a la seccion crítica (y bloquee a los demas) y unas instrucciones posteriores que permitiran que otros recursos sean notificados de que la sección crítica ya está libre llamado protocolo de salida (PS).
Siempre, siempre, han de garantizarse tres fases:
Exclusión mutua: Un solo proceso accede al mismo tiempo al recurso (R). Mientras un proceso está en su sección critica relativa a R ningun otro puede estar ejecutando dicha seccion critica (no simultaneidad). Cuando R está siendo utilizado por un proceso, los demas se quedan bloqueados a la espera de que R quede libre.
Progreso de la ejecución: Si R está libre, cualquier proceso podrá entrar a su sección critica relativa a R.
Limitación en la espera: Ningun proceso esperará ilimitadamente por acceder a R.
CONDICIONES DE SINCRONIZACION
La condicion de sincronización es una propiedad de que un proceso NO realice un evento hasta que otro proceso haya realizado una accion determinada. Suponiendo el siguiente esquema de impresora, podemos ver que hay una serie de condiciones de sincronización:
El lector ha de parar cuando el buffer esté lleno.
El gestor ha de evitar tomar la imagen del buffer si el buffer está vacío.
El gestor ha de evitar meter imagenes a la cola de impresión si está llena.
El impresor no ha de imprimir si no hay nada en la cola de impresion.
TIPOS DE SINCRONIZACIÓN: INHIBICION DE INTERRUPCIONES
La mas antigua de las soluciones (además es via hardware) consiste en bloquear todas las interrupciones (lo que incluye la señal de reloj del procesador que hace el cambio de contexto) asi se obliga a que la instruccion se realice sí o si, por lo que la seccion crítica quedaría tal que así:
Pero esto está mal, primero porque los usuarios controlan la habilitacion/deshabilitacion de interrupciones y si se olvidaran de activarlos el SO muere. Además no es valido para los multiprocesadores. Asi que hay que hacer otras técnicas via software.
ESPERA OCUPADA: ALGORITMO DE PETERSON
Los procesos esperan para entrar en la seccion crítica mediante una comprobacion continua del valor de algunas variables, ocupando el tiempo de la CPU (estan en un bucle infinito hasta que les dicen que pueden pasar a la seccion critica), no obstante aunque es funcional se añaden tantas lineas que no es rentable. Lo idoneo sería un sistema de turnos (para saber a que proceso le toca) y además una inicialización de la comprobación para que se garantice que algun proceso entra en la Sección Crítica por primera vez.
El siguiente programa se espera que, como resultado de su ejecución se imprima 110 o 50. ¿Es correcto el algoritmo?
En efecto, no. Como podemos ver está la operacion x:=x+10 y la comprobacion x>100. Asi que puede pasar algo como esto que haría que no saliera ni 110, ni 50.
Supongamos la instruccion atomica TAS donde x es una variable local y c una variable global que simbolica si la Seccion Crítica está libre (0) o si está ocupada (1).
Utilizando la instruccion anterior, construir los protocolos de entrada, de salida y la inicializacion de las variables para dar una solución al problema de la exclusión mútua de las secciones criticas siguientes:
PE: do TAS(x) until x==0 //asi sabre que c=0
EJERCICIO 1: Supongamos que tengo un proceso que cuando recibe una señal, hace 'n=n+1' y que otro proceso, cuando pasa una hora, escribe y resetea dicho contador 'write(n)-n=0' y que trabajan en armonía. ¿Que puede pasar?
n:=n+1 -> write(n) -> n:=0
write(n) -> n:=n+1 -> n:=0
write(n) -> n:=0 -> n:=n+1
El primer caso es el correcto, pues escribimos el numero de señales recibidas. El segundo está mal pues se pierde una señal y el tercero aunque podría parecer que está bien si suponemos que las operaciones tendrian que realizarse de forma secuencial, primero se añade y luego se escribe, no al reves (aunque no se pierde la seal sino que se añade al siguiente ciclo).
EJERCICIO 2: Supongamos que tenemos que leer en la posicion de memoria 20 y en la posicion de memoria 88 escribir, suponiendo que no son instrucciones atomicas y que se componen de saltar(direccion) y leer/escribir. ¿Qué puede pasar?
Saltar(20) -> Leer -> Saltar(88) -> Escribir
Saltar(20) -> Saltar(88) -> Leer -> Escribir
Saltar(20) -> Saltar(88) -> Escribir -> Leer
Saltar(88) -> Escribir -> Saltar(20) -> Leer
Saltar(88) -> Saltar(20) -> Escribir -> Leer
Saltar(88) -> Saltar(20) -> Leer -> Escribir
La primera y la cuarta estan bien pues sería la ejecución secuencial de ambos procesos en un orden u otro, el resto son erroneas.
