Concurrencia en los sistemas operativos

Los temas principales en el diseño de un sistema operativo tienen que ver con la gestión de hilos y de procesos. Definimos tres conceptos fundamentales, multiprogramación, multiprocesamiento y procesamiento distribuido.

Multiprogramación: consiste en la gestión de varios procesos dentro de un sistema monoprocesador.

Multiprocesamiento: gestiona de varios procesos en un sistema con múltiples procesadores.

Procesamiento distribuido: consiste en la gestión de varios procesos ejecutándose en sistemas de computadores múltiples y distribuidos.

La multiprogramación se creo para permitir que el tiempo de procesador de la maquina fuese compartido dinámicamente entre varias aplicaciones.

Un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo para dar la idea de ejecución simultánea.

Dificultades de los sistemas multiprogramados:

1. Compartir recursos globales esta lleno de riesgos. Por ejemplo si dos procesos hacen uso de la misma variable local y ambos llevan acabo operaciones de lectura y escritura, el orden en que se realicen estas operaciones puede ser critico.
2. Resulta difícil gestionar la asignación óptima de recursos. Ejemplo: si un proceso A puede solicitar el uso de una canal de E/S y suspenderse antes de hacer uso del mismo. No seria conveniente que el sistema bloqueara e impidiera el uso del mismo, ya que daría lugar a un ínter bloqueo.
3. Resulta difícil localizar un error de programación porque los resultados no son ni deterministas reproducibles.

Requisitos para la exclusión mutua:

1. Debe cumplirse la exclusión mutua: solo un proceso de entre todos los que tienen sección critica por el mismo recurso, debe tener permiso para entrar en ella en un instante dado.
2. Un proceso que se interrumpe en la sección no crítica debe hacerlo sin interferir  con los otros procesos.
3. Un proceso no debe solicitar acceso a una sección crítica para después ser demorado indefinidamente. No pude permitirse el interbloqueo o la inanición.
4. Cuando ningún proceso esta en la sección critica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin dilación.
5. Un proceso permanece en su sección crítica solo por un tiempo.

Exclusión mutua: Soluciones por software.

En las soluciones por software, antes de llegar a la solución mas apropiada se expresaran cuatro intentos antes de llegar a la solución correcta.

Primera solución:

Se utiliza a una variable llamada turno, si  los procesos P0 y P1 desean acceder a su sección critica, primero observan el valor de la misma, si esta contiene el nuecero que pertenece al número de proceso, entonces pueden ingresar a la sección critica. De lo contrario el proceso se queda en espera activa (ya que queda leyendo la variable continuamente hasta que contienen su valor de proceso).

Este método tiene dos inconvenientes:

• 1. El ritmo de un proceso depende del otro.
• 2. Si un proceso falla, el otro se bloque permanentemente, ya que nunca se cambia el valor de la variable turno.

/* Proceso 0 */.. while(turno != 0)     /*no hacer nada*/; /*seccion critica*/; turno = 1; .

/* Proceso 1 */.. while(turno != 1)     /*no hacer nada*/; /*seccion critica*/; turno = 0; .

Segundo intento:

Lo que se hace es asignar una llave o variable para cada proceso con vector booleano, entonces el otro proceso se encarga de verificar el estado del otro. Entonces si  un proceso falla fuera de su sección critica, el otro proceso funciona normalmente.

           

/* Proceso 0 */.. while(señal[1]) /*no hacer nada*/; Señal[0] = cierto; /*seccion critica*/; Señal[0]=falso; .

/* Proceso 1 */.. while(señal[0]) /*no hacer nada*/; Señal[1] = cierto; /*seccion critica*/; Señal[1]=falso; .

Problema: El inconveniente en este caso es si el proceso falla en su sección crítica, e incluso es peor al caso anterior ya que no se cumple la exclusión mutua.

Tercer intento:

El tercer intento es similar al anterior, pero ahora la variable de estado del propio proceso se cambia antes comprobar el estado del otro proceso.

/* Proceso 0 */.. Señal[0] = cierto; while(señal[1]) /*no hacer nada*/; /*sección critica*/; Señal[0]=falso; .

/* Proceso 1 */.. Señal[1] = cierto; while(señal[0]) /*no hacer nada*/; /*sección critica*/; Señal[1]=falso; .

Problema: Si ambos procesos ponen la señal a cierto antes de que ejecuten la sentencia while, cada proceso pensara que el otro esta en la sección critica y se provocara u interbloqueo.

Cuarto Intento:

En este intento lo que se hace es que cuando se verifica el estado del otro proceso, si el otro se encuentra en la sección critica, entonces la señal propia del proceso se pone en falso, para luego esperar un tiempo y volverla a poner en cierto, para así verificar nuevamente el estado.

/* Proceso 0 */.. Señal[0] = cierto; while(señal[1]) { Señal[0]=falso; /*Esperar*/; Señal[0] = cierto; } /*sección critica*/; Señal[0]=falso; .

/* Proceso 1 */.. Señal[1] = cierto; while(señal[0]) { Señal[1]=falso; /*Esperar*/; Señal[1] = cierto; } /*sección critica*/; Señal[1]=falso; .

Problema: puede darse que la sección del while de ambos procesos se repitan simultáneamente indefinidamente y así provocar lo que se denomina bloqueo vital.

Solucion correcta:

Lo que se hace es utilizar las variables de estado para los procesos y la variable de turno para evitar el problema de cortesía mutua expuesto en el cuarto intento.

Para ello exponemos el algoritmo de Peterson:

Bolean seña[2]; Int turno ; 

Void P0(){ While(cierto)  {    Señal[0]=cierto; Turno = 1;  While (señal[1])&& turno = = 1)     /*no hacer nada ya que el otro proceso esta en la sección critica */      /* sección critica */      Señal[0] = falso;       /* resto */ } }

Void P1(){    While(cierto)     {       Señal[1]=cierto; Turno = 0;  While (señal[0])&& turno = = 0)         /*no hacer nada ya que el otro proceso esta en la sección critica */           /* sección critica */         Señal[1] = falso;         /* resto */ } }

Void main (){

Señal[0]=falso;

Señal[1]=falso;

}

Soluciones por Hardware.

Inhabilitación de Interrupciones.

Cuando un proceso se encuentra en su sección critica, este no puede ser interrumpido, y para garantizar la exclusión mutua puede bastar con deshabilitar las interrupciones.

While (cierto)

{

/*inhabilitar interrupciones */;

/* Sección critica*/;

/* Habilitar interrupciones */;

/* Resto */;

}

El precio de esta solución puede ser muy alto, la eficiencia de ejecución puede ser notablemente degradada, debido a la imposibilidad de intercalar programas. Y es sistemas multiprocesadores no funciona.

Instrucciones especiales de máquina.

Esta solución consiste en que algunos procesadores pueden traer algunas instrucciones que se ejecutan en un solo ciclo de reloj, esto hace que no se exponga a las ingerencias de otras instrucciones. Se parte de la base de que al leerse una posición de memoria, esta se bloquea para cualquier otro acceso.

La instrucción comparar y fijar (Test and set):

Boleando TS (int i)

{

If (i = = 0)

{

I = 1;

Return cierto;

}

Else

{

Return falso;

}

}

Esta instrucción se ejecuta atómicamente.

Instrucción Intercambiar:

            Consiste en intercambiar el contenido de un registro con el de una posición de memoria. Durante la ejecución se bloquea el acceso a la posición de memoria de cualquier otra instrucción que haga referencia a la misma posición.

Problema de las soluciones por instrucciones de procesador:

1. Se emplea espera activa.
2. Puede producirse inanición. (Cuando un proceso sale de su sección critica, la selección es arbitraria, así pues, se podría negar el acceso a algún proceso indefinidamente.)
3. Puede producirse interbloqueo.

Espero que sirva para comprender un poco los problemas con los que se enfrentaron los programadores al momento de comenzar con la multiprogramación. Hoy en día estos problemas ya se encuentra solucionados de diferentes formas, ya sea aplicando semáforos, monitores, etc. Pero conocer un poco el consepto nos puede ayudar a encontrar soluciones al momento de programar nuestros sistemas.
La bibliografía consultada es:
Stallings, William; “Sistemas Operativos”; 4ta Edición; Prentice-Hall; 2001.