Monitores

Es un tipo de procedimientos, variables y estructuras de datos que se agrupan en un tipo de modulo especial. Tienen una propiedad importante: solo un proceso puede estar activo en un monitor en un instante de tiempo.

Los monitores proveen un nuevo tipo de variables de condición con dos operaciones que operan sobre el (solo se usan dentro del procedimiento de el monitor).

Wait -> wait(a) : produce que el proceso que ejecuta la instrucción sea interrumpido y removido de la cola de ready hasta que otro proceso lo habilite ejecutando la instrucción signal( )con la misma variable de condición.

Signal -> signal(a) : Habilita la ejecución de algún proceso en espera por la ejecución de la instrucción wait con la misma variable de condición.

Semáforos

Son una herramienta de sincronización. Es una variable protegida que solo puede ser modificada por la rutina de inicialización y por otras dos operaciones atómicas:

P( ) <- wait

V( ) <- signal

Las operaciones a las cuales se puede acceder son:

Inicialización: Crea un nuevo semáforo asignándole un valor inicial

P(s): while (s=0) do no_op ATÓMICA

s:=s-1

V(s): s:=s+1 ATÓMICA

Existen básicamente dos tipos de semáforos:

* Semáforos contadores: Toman valores positivos mayores o iguales a 0. Se utilizan para sincronización de procesos.

* Semáforos binarios: Toman los valores 0 ó 1 y se utilizan para exclusión mutua.

A continuación se presenta una solución mediante semáforos del problema productor/consumidor.

#define N 100

semaphore mutex = 1;

semaphore empty = N;

semaphore full = 0;

void productor(void)

{int item;

while(1){

produce_item(item);

down(empty);

down(mutex);

enter_item(item);

up(mutex);

up(full);}

}

void consumidor(void)

{ int item;

while(1){

down(full);

down(mutex);

remove_item(&item);

up(mutex);

up(empty);

consume_item(item);}

}

En este caso tenemos la utilización de 3 semáforos, uno destinado al control de la exclusión mutua y los otros dos destinados a la sincronización de los procesos para el control de buffer lleno y vacío.

Podríamos utilizar semáforos para un algoritmo de espera ocupada con n procesos, pero los n procesos que están ejecutando el while de la función P(s) van a la cola de ready en un instante de tiempo reduciendo la performance general del equipo.

Para evitar la espera ocupada se crea un semáforo que sea un registro de un nuevo tipo:

Semáforo = Record

Valor:Integer

L:Lista_de_Procesos

End

P(s) {

s.Valor:= s.valor - 1

if s.Valor <>

bloquear;

end}

V(s){

s.Valor:=s.Valor + 1

if s.Valor £ 0 then quitar un proceso y a s.L

Despertar (y) }

Algoritmo de Peterson

El algoritmo de Peterson, también conocido como solución de Peterson, es un algoritmo de programación concurrente para exclusión mutua, que permite a dos o más procesos o hilos de ejecución compartir un recurso sin conflictos, utilizando sólo memoria compartida para la comunicación.

Algoritmos de Dekker

El algoritmo de Dekker es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado por Edsger Dijkstra.

Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.

Existen cinco versiones del algoritmo Dekker, teniendo ciertos fallos los primeros cuatro. La versión 5 es la que trabaja más eficientemente, siendo una combinación de la 1 y la 4.

* Versión 1: Alternancia estricta. Garantiza la exclusión mutua, pero su desventaja es que acopla los procesos fuertemente, esto significa que los procesos lentos atrasan a los procesos rápidos.

* Versión 2: Problema interbloqueo. No existe la alternancia, aunque ambos procesos caen a un mismo estado y nunca salen de ahí.

* Versión 3: Colisión región crítica no garantiza la exclusión mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la región crítica.

* Versión 4: Postergación indefinida. Aunque los procesos no están en interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda.

Más Sobre Sincronización de Procesos

Ahora analizaremos brevemente las definiciones de una sincronización de procesos , la sección critica y las concurrencia y paralelismo en un sistema operativo.
Sincronización de procesos
en primer lugar se empezara definiendo algunos conceptos de la comunicación entre procesos:
La comunicación entre procesos: necesaria si se desea que varios procesos puedan colaborar para realizar una misma tarea. Sincronización ,funcionamiento coordinado en la resolución de una tarea encomendada.
El SO ofrece mecanismos básicos de comunicación, que permiten transferir cadenas de bytes. Deben ser los procesos que se comunican quienes interpreten el significado de las cadenas transferidas para su labor coordinada.
Los mecanismos de comunicación y sincronización son dinámicos. Es decir, cuando se necesita un mecanismo de este estilo, se crea, usa y destruye, de forma que no se establezca de forma definitiva ningún mecanismo de comunicación, ya que ellos podrían producir efectos indeseados. Es decir, la comunicación es algo puntual.
Los servicios básicos de comunicación son:
a. crear: el proceso solicita la creación del mecanismo
b. enviar o escribir: el proceso emisor envía información al proceso receptor
c. recibir o leer: el proceso receptor recibe información
d. destruir: el proceso solicita la destrucción del mecanismo de comunicación
La comunicación puede ser sincrona y asíncrona:
a. síncrona: los dos procesos han de ejecutar servicios de forma simultánea. El emisor ha de ejecutar el servicio enviar mientras el receptor ejecuta recibir.
b. asíncrona: el emisor hace el envío y prosigue su ejecución. El SO ofrece un almacenamiento intermedio para guardar la información enviada, hasta que el receptor la solicite.
c. En un sistema operativo multiprogramado los procesos compiten por el acceso a los recursos compartidos o cooperan dentro de una misma aplicación para comunicar información. Ambas situaciones son tratadas por el sistema operativo mediante mecanismos de sincronización que permiten el acceso exclusivo de forma coordinada a los recursos y a los elementos de comunicación compartidos. Según el modelo de sistema operativo descrito anteriormente, basado en colas de procesos y transiciones de estados, los procesos abandonan la CPU para pasar a estado bloqueado cuando requieren el acceso a algún dispositivo, generalmente en una operación de E/S, pasando a estado preparado cuando la operación ha concluido y eventualmente volver a ejecución. La gestión de estos cambios de estado, es decir, los cambios de contexto, es un ejemplo de sección crítica de código dentro del sistema operativo que debe ser ejecutada por éste en exclusión mutua. Otros ejemplos de código que debe protegerse como sección crítica incluyen la programación de los dispositivos de E/S y el acceso a estructuras de datos y buffers compartidos.
d. Dentro del dentro del núcleo del sistema operativo, el espacio de direcciones es único, por lo que la comunicación se resuelve mediante el uso de variables de memoria compartida. Como contrapartida a la agilidad de este esquema, es necesario utilizar mecanismos explícitos de sincronización para garantizar acceso exclusivo a las variables compartidas. Si se definen buffers o colas compartidas a las que se proporciona acceso exclusivo, se pueden utilizar esquemas de comunicación más elaborados, como es el caso del productor-consumidor. El esquema cliente-servidor es un caso particular del productor-consumidor donde los clientes producen peticiones que son consumidas por el servidor de un determinado recurso. Un sistema operativo con estructura cliente-servidor resulta atractivo por la claridad de su diseño. Cuando los procesos que se comunican mediante estos esquemas no comparten el espacio de direcciones, lo que sucede en particular en sistemas basados en micro núcleo, se requieren primitivas de comunicación por paso de mensajes, que, al gestionar implícitamente la sincronización, simplifican la programación de la comunicación.
e. En los apartados siguientes vamos a tratar el problema de la sección crítica y sus soluciones. La sección crítica no es el único problema a resolver en un sistema operativo. Aunque se utilicen esquemas de comunicación elaborados, las interacciones en el uso de los recursos pueden conducir a interbloqueos, problema que se tratará más adelante.




La sección crítica
El problema de la seción crítica consiste en diseñar un protocolo que los procesos puedan usar para cooperar de esta forma.
Cualquier solución al problema de la sección crítica deberá satisfacer los tres requisitos siguiente:
•Exclusión mutua.- Si el proceso Pi está ejecutándose en su sección crítica, los demás procesos no pueden estar ejecutando sus secciones críticas.
•Progreso.- Si ningún proceso está ejecutando su sección crítica, y algunos procesos desean entrar en sus correspondientes secciones críticas, sólo aquellos procesos que no estén ejecutando sus secciones restantes pueden participar en la decisión de cuál será el siguiente que entre en su sección crítica, y esta selección no se puede posponer indefinidamente.
•Espera limitada.- Existe un límite en el número de veces que se permite que otros procesos entren en sus secciones críticas después de que un proceso haya hecho una solicitud para entrar en su sección crítica y antes de que la misma haya sido concedida.
Se usan dos métodos generales para gestionar las secciones críticas en los sistemas operativos:
1. Kernels apropiativos.- Permite que un proceso sea desalojado mientras se está ejecutando en modo kernel.
2. Kernels no apropiativos.- No apropiativo no permite que un proceso que se esté ejecutando en modo kernel sea desalojado.

HARDWARE DE SINCRONIZACIÓN
En sistemas de un procesador, el problema de las secciones críticas podría ser resuelto simplemente si pudiéramos deshabilitar las interrupciones mientras una variable compartida está siendo actualizada.
Esta solución no es factible para un sistema con varios procesadores debido a la demora que implica el pasaje de mensajes.
En muchos sistemas existen instrucciones de hardware que pueden ser usadas para resolver el problema de las secciones críticas.
Estas instrucciones permiten ejecutar atómicamente las operaciones de:
– chequear y modificar el contenido de una palabra, o
– intercambiar el contenido de dos palabras
SEMÁFOROS
Las soluciones por hardware presentadas no son fáciles de generalizar a problemas más complejos.
Esta dificultad se puede superar usando una herramienta de sincronización llamada semáforo.
Un semáforo S es una variable entera que solo es accedida a través de dos operaciones atómicas: wait y signal.
wait(S): while S <= 0 do no-op
S := S - 1;
signal(S): S := S +1;
PROBLEMAS CLÁSICOS DE SINCRONIZACIÓN
Buffer finito
Lectores y escritores
Filósofos comensales
Buffer finito
Buffer de tamaño N
Semáforo mutex inicializado en 1
Semáforo full inicializado en 0
Semáforo empty inicializado en N
Lectores Y Escritores
Una zona de memoria es compartida por varios procesos concurrentes
Lectores – sólo lee datos; no efectúan actualizaciones de datos
Escritores – puede leer y escribir
Problema – permitir a múltiples lectores leer simultáneamente; sólo un escritor puede acceder a los datos en forma simultánea.
Recursos Compartidos
Datos
Semáforo mutex inicializado en 1.
Semáforo wrt inicializado en 1.
Entero readcount inicializado en 0.
Problema de los Lectores
3 variantes:
(1) Los lectores tienen prioridad
Muerte por inanición de los escritores
(2) Los escritores tienen prioridad
Muerte por inanición de los lectores
(3) Lectores y Escritores tienen la misma Prioridad
No hay problemas de inanición






EL PROBLEMA DE LOS FILÓSOFOS COMENSALES
Recursos compartidos
Fuente de arroz (datos)
Semáforos chopstick [5] inicializados en 1


MONITORES
Son mecanismos de sicronización de nivel más alto que semáforos. La construcción se realiza a nivel de lenguaje de programación que controla el acceso a datos compartidos.
Un tipo monitor tiene un conjunto de operaciones definidas por el programador que gozan de la característica de exclusión
mutua dentro del monitor.










Concurrencia y paralelismo
• Hay concurrencia entre varios procesos cuando existen al mismo tiempo.
PROCESOS CONCURRENTES
• Hay paralelismo entre varios procesos cuando se ejecutan al mismo tiempo

PROCESOS PARALELOS
• El paralelismo requiere un soporte físico: varios procesadores.
• La concurrencia es el caso general y el paralelismo un caso particular.
• La concurrencia (y el paralelismo) se refiere a la ejecución de código:
Hay procesos concurrentes y flujos concurrentes.
• Hablaremos en general de flujos concurrentes:
Pueden ser del mismo proceso o diferentes procesos.
Pueden correr en un único procesador o varios.


Solución al problema de la sección crítica
Condiciones para la solución:
‰ Exclusión mutua
‰ Progresión: que ordenadamente todos los procesos puedan ejecutarse y entrar en la SC.
‰ Espera limitada: una vez que requirió entrar a la SC, que pueda hacerlo después de un
tiempo determinado.