Exclusión mutua

1. Introducción.

En un sistema multiprogramado con un único procesador, losprocesos se intercalan en el tiempo (i.e. Round Robin) para darapariencia de ejecución simultánea. Aunque no se consigue unprocesado en paralelo real, y aunque se produce un sobrecargadoen la cpu por el hecho de tener que cambiar de tareaconstantemente, las ventajas de todo esto son muy elevadas. Ejemplo: avion-torre, chat’s, etc.
Uno de los grandes problemas que nos podemos encontrar es queel hecho de compartir recursos está lleno de riesgos. Por ejemplo,si dos procesos hacen uso al mismo tiempo de una variable globaly ambos llevan a cabo tanto operaciones de lectura como deescritura sobre dicha variable, el orden en que se ejecuten estaslecturas y escrituras es crítico, puesto que se verá afectado elvalor de la variable.

Concepto de condiciones de carrera:

• Situaciones en las que dos o más procesos leen o escriben en un área de memoria compartida y el resultado final depende de los instantes de ejecución de cada uno.
• Esto se soluciona impidiendo que más de un proceso acceda simultáneamente a las
• variables compartidas. Se soluciona garantizando la exclusión mutua.

Concepto de exclusión mutua.

• Consiste en que un solo proceso excluye temporalmente a todos los demás para usar un recurso compartido de forma que garantice la integridad del sistema.

Concepto de sección crítica.

• Es la parte del programa con un comienzo y un final claramente marcados que generalmente contiene la actualización de una o más variables compartidas.
• Para que una solución al problema de la exclusión mutua sea válida, se tienen que cumplir una serie de condiciones:
  • Hay que garantizar la exclusión mutua entre los diferentes procesos a la hora de acceder al recurso compartido. No puede haber en ningún momento dos procesos dentro de sus respectivas secciones críticas.
  • No se deben hacer suposiciones en cuanto a la velocidad relativa de los procesos en conflicto.
  • Ningún proceso que esté fuera de su sección crítica debe interrumpir a otro para el acceso a la sección crítica.
  • Cuando más de un proceso desee entrar en su sección crítica, se le debe conceder la entrada en un tiempo finito, es decir, que nunca se le tendrá esperando en un bucle que no tenga final.

Para solucionar el problema de la exclusión mutua vamos a tener tres tipos de soluciones:

• Soluciones software.
• Soluciones hardware.
• Soluciones aportadas por el Sistema Operativo.

2. Soluciones hardware.
Las soluciones hardware se dividen en dos tipos:

• Optimistas.
• Consideran que lo mas probable es que no haya conflictos, y si los hay sea en número reducido, por lo que permiten cualquier acceso a la variable compartida. En caso de conflicto, mantienen la integridad del sistema descartando las actualizaciones.
• Pesimistas.
  • Bloquean todo aquello que pueda interferir.
  • Actualizan la variable.
  • Desbloquean lo bloqueado al principio.

• Deshabilitar interrupciones y habilitar interrupciones (pesimista).
• Test and Set (Compartir y Fijar) (pesimista).
• Comparar e intercambiar (optimista).

3. Soluciones del Sistema Operativo.
3.1. Semáforos.
3.1.1. Semáforos binarios.
   Dijkstra dio en 1968 una solución elegante y sencilla al problema de la exclusión mutua con la introducción del concepto de semáforo binario. Esta técnica permite resolver la mayoría de los problemas de sincronización entre procesos y forma parte del diseño de muchos sistemas operativos y de lenguajes de programación concurrentes.
   Un semáforo binario es un indicador de condición (S) que registra si un recurso está disponible o no. Un semáforo binario sólo puede tomar dos valores: O y 1. Si, para un semáforo binario. S=1 entonces el recurso está disponible y la tarea lo puede utilizar; si S=0 el recurso no está disponible y el proceso debe esperar.
   Los semáforos sólo permiten tres operaciones sobre ellos:
      Espera.
      Señal.
      Inicializar.

El wait y el signal son indivisibles y no se pueden interrumpir, es decir, no se pueden ejecutar ambas a la vez.
Los semáforos binarios los utilizaremos para recursos de una sola instancia, y para sincronización binaria.

3.1.2. Semáforos generales.

• El semáforo binario resulta adecuado cuando hay que proteger un recurso que pueden compartir varios procesos, pero cuando lo que hay que proteger es un conjunto de recursos similares, se puede usar una versión más general del concepto de semáforo que lleve la cuenta del numero de recursos disponibles. En este caso el semáforo se inicializa con el numero total de recursos disponibles (n) y las operaciones de espera y señal se diseñan de modo que se impida el acceso al recurso protegido por el semáforo cuando el valor de éste es menor o igual que cero.
• Cada vez que se solicita y obtiene un recurso, el semáforo se decrementa y se incrementa cuando se libera uno de ellos. Si la operación de espera se
• ejecuta cuando el semáforo tiene un valor menor que uno, el proceso debe quedar en espera de que la ejecución de una operación señal libere alguno de
• los recursos.
• Al igual que en los semáforos binarios, la ejecución de las operaciones son indivisibles, esto es, una vez que se ha empezado la ejecución de uno de estos
• procedimientos se continuará hasta que la operación se haya completado.

Conclusión: Son un tipo de semáforos utilizados cuando tenemos varias instancias de un mismo recurso. Este tipo de semáforos se inicializa al número de instancias que tengamos.

3.2. Monitores.
Un monitor es una estructura formada por una cabecera que los identifica, un conjunto de variables globales a todos los procedimientos del monitor, un conjunto de procedimientos y un bloque de inicialización, el cual se ejecuta una única vez, cuando se crea el monitor.

El recurso que queremos compartir (S.C.) se declara como monitor y en él se incluyen todas las operaciones que afecten a dicho recurso. Los procesos que usan el monitor se sitúan de forma independiente y cuando deseen usar el recurso, llamarán al procedimiento del monitor que implemente la operación que desea ejecutar. Para resolver la sincronización se utilizan dos instrucciones, wait (bloquea siempre) y signal, y actúan sobre variables condición que son colas y además no tienen valor.

• cwait (c): suspende la ejecución del proceso que llama bajo la condición c. El monitor está ahora disponible para ser usado por otros procesos.
• csignal(c): reanuda la ejecución de algún proceso suspendido después de un cwait bajo la misma condición. Si hay varios procesos, se elige uno de ellos; si no hay ninguno, no hace nada.

Las colas son un tipo de variables que son el lugar donde almacenaremos los procesos que hayan quedado suspendidos bajo un .wait. y estén a la espera de ser “despertados”.
En el caso de que dentro de un monitor un proceso se quede bloqueado con un wait por lo cual se bloquea y no dejaría ejecutarse a otro proceso, el SO despierta a otro proceso cuya última instrucción haya sido un signal y además vale la condición que hace que se bloqueen los procesos.
Habrá algunos casos en los que nos apoyemos en una variable booleana para garantizar la exclusión mutua sobre una variable con una sola instancia. También habrá casos en los que utilicemos un contador.

3.3. Mensajes.

Son una solución del sistema operativo que nos permitirán la sincronización de procesos y la comunicación entre ambos.

Es una cadena de texto transmitida de un proceso que envía el mensaje a un receptor (proceso receptor). Un mensaje puede tener código, texto, datos, …

Suelen tener dos partes:
   – Cabecera (obligatoria): IdProcesoEmisor, IdProcesoReceptor, Tipo, Longitud
   – Cuerpo (optativo): Información adicional

Tenemos dos tipos de órdenes para gestionar mensajes (para enviar y recibir):
   – Enviar: send (destino, mensaje)
   – Recibir: receive (origen, mensaje)

*Direccionamiento.
a) Directo. Se especifican emisor y receptor de forma explícita.

   P envía a Q:
      – P: send (Q, mensaje)
      – Q: receive (Q, mensaje)

b) Implícito: El emisor especifica quien es el receptor, pero el receptor no especifica quién es el emisor.

c) Indirecto. En este direccionamiento los mensajes no se envían directamente al receptor, sino que se envían a una estructura de datos denominada buzón o mailbox. Una gran ventaja de esto es que podemos enviar a cualquier buzón cualquier mensaje. Los mensajes no tienen que ir dirigidos específicamente a un proceso.

En este tercer caso la relación puede ser (1-1) (un proceso envía a un solo buzón). También puede haber (n-1) donde varios procesos envían mensajes a un solo buzón o (1-n) donde un proceso envía mensajes a muchos buzones. Este último caso vale para cuando quiero comunicar una información a muchos procesos.

* Propiedad de los buzones.
   Tenemos dos casos:
      – El proceso es el propietario. El buzón existe mientras existe el proceso y sólo el propietario puede leer datos del buzón   
      – El propietario del buzón es el SO. La propiedad del buzón puede transmitirse entre procesos, lo que permite que varios procesos puedan leer.

* Sincronización de los mensajes.
   a) Cuando enviamos:
      – El proceso se bloquea hasta que el receptor reciba el mensaje (envío bloqueante)
      – No se bloquea y continua haciendo operaciones (envío no bloqueante)
   b) Al recibir el mensaje:
      – Al mirar a ver si está el mensaje, si ya ha llegado, lo cojo y continúo.
      – Cuando voy a buscar el mensaje, si no ha llegado todavía:
      – Bloqueo el proceso, hasta que llegue el mensaje (recepción bloqueante).
      – No se bloquea el proceso (recepción no bloqueante).
      – El proceso se bloquea durante un intervalo de tiempo. Si transcurrido ese tiempo, el mensaje no ha llegado, el proceso continúa sin el mensaje.

*Casos habituales:
   – Envío bloqueante- Recepción bloqueante.
      Se usa cuando la sincronización ha de ser muy estricta.
   – Envío no bloqueante – recepción bloqueante.
      Se usa para cuando el proceso emisor no necesita que el receptor haya recibido el mensaje para continuar. Ej: Servidor de correo.
   – Envío no bloqueante – recepción no bloqueante.