IET110 Sistemas Operativos P04: Exclusión Mutua Prof. Jonathan MakucSlide: 1

IET110Sistemas Operativos

P04: Exclusión Mutua

Prof. Jonathan MakucSlide: 1

Sistemas Operativos – ICC243 [ 2 ] Prof. Jonathan Makuc

Temario ://

• Comunicación entre procesos

• Conflicto de recursos entre procesos

• Conceptos de Exclusión mutua (race condicion, atomicidad, etc)

• Implementación de Exclusión mutua (testAndSet, semaforos, etc)

• Soluciones Por Hardware

• Soluciones Por Software

Sistemas Operativos: Exclusión Mutua


Comunicación entre procesos (IPC) ://

- Comunicación entre procesos sin la necesidad de compartir variables.

- Operaciones: Envío de mensajes, recepción de mensajes

- Permite la separación completa, reduciendo los errores, permitiendo que

procesos que no pueden confiar uno del otro, cooperen


Directo:- Send(Q, mensaje)

- Recieve(P, mensaje)

Indirecto:- Send(A, mensaje)

- Recieve(A, mensaje)

IPCP Q IPC (A)

P

R

Q


Conflicto de Recursos entre procesos ://

Problemas comunes:

- Productor no termina de escribir mensaje y consumidor asume un

largo incorrecto de mensajes

- Dos o más productores envían mensajes simultáneamente

intercalándose la información

- Dos o más consumidores revisan la cola al mismo tiempo

produciéndose una duplicación del proceso del mensaje



Conceptos ://

Race Condition (Condición de competencia): falla en un sistema donde el

resultado depende críticamente del orden relativo de los eventos.

Atomicidad: operación que se realiza por completo o no tiene efecto alguno.

Región (Sección) Crítica: porción de código que no puede ser ejecutada

concurrentemente, de lo contrario el resultado es incierto.

Algoritmos de Exclusión Mutua (MUTEX): usados para evitar el uso concurrente

de un recurso que no se puede compartir.

Deadlock: condición en la cual dos o más procesos se encuentran en un estado

donde ninguno puede avanzar dado que otro proceso posee un recurso requerido y

viceversa.



Conceptos ://

Condiciones de una buena solución Mutex:

1. No puede haber más procesos de los establecidos, ejecutando una

sección crítica

2. No se puede hacer suposiciones sobre la velocidad o cantidad de CPU

3. Ningún proceso fuera de su sección crítica puede bloquear otros

procesos

4. Ningún proceso debería esperar por siempre para entrar a su región

crítica

“Si algo puede salir mal, SALDRA.” -- Ley de Murphay


Proc B

Inicio


Race Conditon ://


Suponga que la salida de B depende del resultado de A

Se requiere del resultado de A

A no alcanza a terminar a tiempo

Proc A

Inicio



Región Critica y Atomocidad ://

global contador;

char a;

while(1) {

a = getChar();

if(char != ‘ ‘) {

contador++;char = ‘ ’

}else {

contador--;}

}

Reg

ión

Cri

tica Debe ser

atómica


Implementación de Exclusión Mutua ://

Interrupciones

Las Interrupciones son señales electricas que llegan de dispositivos de hardware, que provoca

que el sistema operativo pase a modo kernel y atienda el evento. Esta acción suele provocar

cambio de contexto.


CPU1

Proc1

DiscoDuro

Tarjeta de Red

Señal I/O(Interrupcion)

Time Slice

Proc6

Proc7

Proc8



Apagado de Interrupciones

Se deshabilitan las interrupciones de la CPU permitiendo que complete su tarea atómicamente

al impedir que se produzca cambio de contexto.


Útil para permitir al Sistema Operativo realizar operaciones atómicas

CPU1

Proc2

Proc1

Proc3

Proc4

Int off

DiscoDuro

Tarjeta de Red

Señal I/O(Interrupcion)

Time Slice



Apagado de Interrupciones

Se deshabilitan las interrupciones de la CPU permitiendo que complete su tarea atómicamente

al impedir que se produzca cambio de contexto.

Inconvenientes:

- De permitir su uso por un proceso de usuario, este podría apagarlas y no reanudarlas,

bloqueando completamente la CPU.

- En sistemas multiprocesador, este método solo apaga las interrupciones del CPU que corría el

proceso en cuestión. Otros procesos podrán acceder a la memoria compartida.


Útil para permitir al Sistema Operativo realizar operaciones atómicas

CPU2 CPU1

Proc2

Proc1

Proc3

Proc4

Proc5

Proc6

Proc7

Proc8

MemoriaCompartida

Int off


TestAndSet

El hardware proporciona un método que permite setear una variable

atómicamente retornando el valor anterior de la misma. Si el valor difiere

del seteado, entonces se ha logrado ingresar nuestro dato, de lo contrario

esta la información de otro proceso.




TestAndSet

Ejemplo Básico: un programa que permita que solo 1 proceso ingrese a la región

crítica simultáneamente, sin importar si provoca starvation.



global int c = 0;

A

while(1) { while(testAndSet(c, 1));

RegionCritica();

c = 0;}

B


RegionCritica();

c = 0;}


TestAndSet

Ejemplo: escriba 2 programas que se alternen una Región crítica utilizando test and

set.



global p = 1;global c = 0;

A

while(1) { while(testAndSet(c, 1)); while(testAndSet(p, 1));

RegionCritica();

p = 1; c = 0;}

B

while(1) { while(testAndSet(p, 0)); while(testAndSet(c, 1));

RegionCritica();

c = 0; p = 1;}


TestAndSet

Ejemplo: escriba 2 programas que se alternen una Región crítica utilizando test and

set.



global p = 1;global c = 0;

A


RegionCritica();

p = 0;

}

B

while(1) { while(testAndSet(p, 1));

RegionCritica();

c = 0;

}



Variables Lock (Bloqueo)

Se consulta una variable antes de entrar a la región crítica cambiando su valor para impedir que otro proceso entre.

Inconveniente:

- Se produce una condición de competencia entre el paso de verificación y

seteo de la variable, antes de la región crítica.


while(1) {

if(lock == 1) {

lock = 0; regionCritica(); lock = 1; }}



Alternación estricta

Se proporciona un método vía programación del usuario donde 2 o más procesos se turnan secuencialmente para entrar a sus regiones críticas.

Inconveniente: poco recomendable cuando uno de los procesos es mucho mas lento que los otros, ya que este podría bloquear al resto estando fuera de su sección crítica. Sucede cuando el proceso lento da acceso al rápido a la RC, la ejecuta junto con su región no critica y espera a que el proceso lento termine con su región no critica.


while(1) { while(turno != 0); regionCritica(); turno = 1 regionNoCritica();}

while(1) { while(turno != 1); regionCritica(); turno = 0; RegionNoCritica();}

Espera innecesaria producto de que el otro proceso es mucho mas lento


Solución de Peterson - enter_region, leave_region



Inconveniente: solución solo para 2 procesos

La doble condición permite considerar el caso inicial cuando los 2 procesos entras simultáneamente y el segundo cambia “turn”, como el caso alternante donde se utiliza la variable de interés


Dormir y despertar

El proceso verifica si puede ingresar a la región critica, si no puede duerme y luego verifica nuevamente.

Problema:

- Si un proceso tiene clara preferencia de scheduling sobre otro,

ocurrirá que aquel rezagado no pueda salir nunca de su sección

crítica provocando una inversión de prioridad




SemáforosSolución propuesta por Dijkstra en 1965 que sugiere el uso de un contador para las llamadas de

liberación (ej: wakeup) y así guardarlas para un futuro. Un usuario no debe modificar este

contador directamente y solo tiene acceso a los siguientes métodos atómicos:

-P() o down(): verifica si el valor del contador. Si es mayor que cero, decrementa el valor y

continua la ejecución. Si es cero se bloquea, no terminando la llamada P().

-V() o up(): aumenta el valor del contador en 1. Si existen procesos bloqueados, se escoge uno

al azar y se le permite terminar la operación down().

Los semáforos deben ser implementados a nivel de sistema operativo, pues requieren del

control de este para bloquear y desbloquear un proceso. Un caso especial es el de la JVM (Java

Virtual Machine), la cual maneja las llamadas a semáforos que esta misma implementa;

comportándose de esta forma como el SO de las aplicaciones java que corren sobre ella.




Semáforos – Ejemplo BásicoUtilice semáforos para proveer exclusión mutua a la llamada regionCritica().

Solución:

mutex = new Semaforo(1);



while(1) {

mutex.p();

regionCritica();

mutex.v();

}


Semáforos - EjemploConstruya 3 programas A, B y C que generen la siguiente salida:

> CBACBACBACBACBACBA…

Solución:

Semáforos a utilizar:

a = new Semaforo(0);

b = new Semaforo(0);

c = new Semaforo(1);



A

while(1) {

a.p(); print(“A”); c.v();

}

B

while(1) {

b.p(); print(“B”); a.v();

}

C

while(1) {

c.p(); print(“C”); b.v();

}


Semáforos v/s Variables CondiciónLas variables tienen un comportamiento idéntico a los semáforos, con la salvedad que estas

NO acumulan ni cuentan llamadas de liberación.



Semáforos

P() o down()

V() o up()

Acumulación de liberaciones para su uso posterior

Variables Condición

wait()

signal()

Si no existen procesos que hayan hecho wait(), el signal() se pierde irremediablemente


MonitoresSolución implementada por un lenguaje de programación. Mediante la inclusión de palabras

clave en el código, al momento de compilar el lenguaje incorpora las primitivas que considere

adecuadas para proporcionar exclusión mutua.

Ejemplo: Java – synchronized

class Ejemplo {

public void synchronized funcion1() { …. }

public void synchronized funcion2() { …. }

}

En este ejemplo ambos métodos son excluyentes.

Solo uno puede ser llamado simultáneamente




Transferencia de Mensajes

Este método de comunicación entre procesos utiliza 2 primitivas:

Estilo C Estilo Java

send(destino, &mensaje) send(destino, mensaje)

recieve(origen, &mensaje) mensaje = recieve(origen)

Las llamadas send y recieve bloquean (o retornan un mensaje de error) cuando no existe

disponibilidad de envió o mensaje que leer.

ítems importantes en un sistema de mensaje:

- ACK (Acknowledge): acuse de recibe permite al emisor verificar la correcta recepción

del mensaje.

- Número de secuencia de mensaje: permite al receptor detectar mensajes repetidos.




Transferencia de Mensajes: Modus operandi

1. El consumidor envía N mensajes vacío al producto.

2. El productor cada vez que necesita enviar un mensaje toma uno de los mensajes

vacíos y lo devuelve lleno.

3. El consumidor recibe y procesa el mensaje, reenviando al productor el mensaje vacío

para obtener mas información.

Variantes:

- Sistema de buzón: espacio de memoria compartida que utilizan ambos procesos. Cuando el

buzón detecta que esta vació, la llamada recieve bloquea. De la misma forma cuando el buzón

esta lleno, send bloquea.

- No buffers: si no se utilizan buffers, buzones o paso de mensajes vacíos, entonces se tiene una

comunicación completamente sincrónica. Aquí si se ejecuta send antes que recieve, el productor

bloquea hasta que el consumidor recibe correctamente, y viceversa.




Barreras

Primitiva pensada para grupos de procesos. Bloquea la ejecución de un conjunto,

hasta que un número determinado esté esperando para liberarlos simultáneamente.



Barrera BarreraBarrera

IET110Sistemas Operativos

P04: Exclusión Mutua

Prof. Jonathan MakucSlide: 28

Documents

IET110 Sistemas Operativos P04: Exclusión Mutua Prof. Jonathan MakucSlide: 1