Apuntes sobre sistemas operativos Apuntes con lo más importante sobre sistemas operativos.

Programación concurrente

• concurrencia <--> paralelismo → mismos problemas

• tipos de concurrencia

  – procesos independientes

• aplicaciones diferentes, no necesitan coordinarse entre sí

  – aplicaciones concurrentes


• aplicación formada por varios hilos/procesos (ej: base de datos)

• objetivo: mejorar las prestaciones

  – varios procesadores: paralelismo

  – un único procesador: se aprovechan los tiempos de espera

• cooperación:

  – datos compartidos (memoria compartida, ficheros...)

  – mecanismos de comunicación entre hilos/procesos (semáforos, mutex/variables condición, mensajes, pipes, señales...)

  – concurrencia en el núcleo del S.O.

• peticiones de múltiples procesos (competencia)

• interrupciones de dispositivos

El problema de la sección crítica

• varios hilos comparten datos entre sí

• cada uno ejecuta un algoritmo correcto(si no se compartiesen los datos)

• al ejecutarlos concurrentemente: resultado incorrecto

• sección crítica: acceso exclusivo a datos compartidos

• requisitos básicos

  – exclusión mutua: un hilo cada vez

  – progreso: fuera de la sección crítica no se debe estorbar

  – espera acotada: cota máxima a la espera

• además; no se deben hacer suposiciones sobre:

  – velocidad relativa de ejecución

  – cambios de hilo

• modelo:

  – antes de la sección crítica

  – entrada a la sección crítica

  – sección crítica

  – salida de la sección crítica

  – después de la sección crítica

Deshabilitación de interrupciones

• Mecanismo:

  – antes de la sección crítica

  – deshabilitar interrupciones

  – sección crítica

  – habilitar interrupciones

  – después de la sección crítica

• Ventaja:

  – eficiencia (entrar y salir: una instrucción máquina)

• Inconvenientes:

  – durante la S.C. no se atienden interrupciones

  – durante la S.C. se impide la ejecución de todos los hilos

  – un error de programación paralizaría el sistema

  – no se pueden entrelazar SS.CC.

  – no funciona en multiprocesadores

Comprobar y establecer (TS)

• TS memoria

  – compara operando con 0

  – modifica el registro de indicadores (flags) indicando el resultado de

la comparación

  – hace que operando pase a 1

• Forma de utilizarla:

• Ventajas

  – aplicable a cualquier número de hilos

  – aplicable en multiprocesadores

  – sencilla de utilizar (aunque no garantiza espera acotada)

  – admite varias secciones críticas independientes

• Inconvenientes

  – utiliza espera activa

  – puede producir inanición

  – pueden producirse interbloqueos

Otros problemas clásicos

Productores y Consumidores

• Separación de preparación y procesamiento

  – mayor rendimiento (permite solapar ambas actividades)

  – algoritmos sencillos para productores y consumidores

• Todos comparten un buffer con capacidad para N elementos

• Productores

  – preparan nuevos elementos (los producen)

  – los depositan en el buffer

  – deben esperar cuando el buffer se llena

• Consumidores

  – retiran elementos del buffer (los consumen)

  – deben esperar cuando el buffer se vacía

  – los procesan

Lectores y escritores

• Acceso concurrente a una base de datos

  – mayor rendimiento (permite solapar múltiples consultas)

  – algoritmos sencillos para lectores y escritores

• Lectores

  – no modifican la base de datos

  – se debe permitir el acceso concurrente de los lectores

• Escritores

  – modifican la base de datos

  – necesitan acceso exclusivo

• ¿Quién tiene preferencia?

  – primer problema: prioridad a los lectores

  – segundo problema: prioridad a los escritores

Semáforos

• objeto que:

  – contiene un contador inicializable a un valor no negativo

  – ofrece la siguiente interfaz

Semáforos:
problema de la sección crítica

Semáforos:
productores y consumidores

Análisis de los semáforos

• Las operaciones sem_wait y sem_signal deben ser
indivisibles

• Ventajas:

  – no utilizan espera ocupada

  – son muy versátiles (se pueden utilizar para resolver problemas
generales de coordinación)

• Inconvenientes:

  – es fácil cometer errores al utilizarlos

• Alternativas:

  – mutex y variables condición (hilos POSIX)

  – monitores

  – objetos protegidos de ADA

  – clases sincronizadas de Java

  – ...

Mutex y variables condición

Sincronización. Mutex.

• Protección de secciones críticas

• Debe liberar el mutex el hilo que lo haya cerrado

• Inicialización y destrucción

  – int pthread_mutex_init(pthread_mutex_t *mutex,

pthread_mutexattr_t *attr)

  – int pthread_mutex_destroy(pthread_mutex_t *mutex)

• Sincronización

  – int pthread_mutex_lock(pthread_mutex_t *mutex)

  – int pthread_mutex_unlock(pthread_mutex_t *mutex)

  – int pthread_mutex_trylock(pthread_mutex_t *mutex)

• Sección crítica:

Ejemplo de sincronización. Mutex.

Sincronización. Variables Condición.

• Esperar a que se cumpla una determinada condición

• Esperas potencialmente largas

• Inicialización y destrucción

  – int pthread_cond_init(pthread_cond_t *cond,
pthread_condattr_t *attr)

  – int pthread_cond_destroy(pthread_cond_t *cond)

• Sincronización

  – int pthread_cond_wait(pthread_cond_t *cond
pthread_mutex_t *mutex)

  – int pthread_cond_signal(pthread_cond_t *cond)

  – int pthread_cond_broadcast(pthread_cond_t *cond)

Ejemplo de sincronización.
Variables Condición.

• Importante: comprobar la condición al salir de cond_wait()

  – otros hilos pueden haber accedido a la sección crítica

  – cond_wait puede terminar debido a una señal

  – protege contra avisos innecesarios

Mutex y variables condición:
productores y consumidores

Mutex y variables condición:
lectores y escritores

• Acceso concurrente a una base de datos

  – mayor rendimiento (permite solapar múltiples consultas)

  – algoritmos sencillos para lectores y escritores

• Lectores

  – no modifican la base de datos

  – se debe permitir el acceso concurrente de los lectores

• Escritores

  – modifican la base de datos

  – necesitan acceso exclusivo

• ¿Quién tiene preferencia?

  – primer problema: prioridad a los lectores

  – segundo problema: prioridad a los escritores

Paso de mensajes

Comunicación entre procesos

• Memoria compartida

  – acceso a almacenamiento común (memoria, ficheros...)

  – servicios de sincronización para exclusión mutua y esperas

  – el programador es responsable de los algoritmos de comunicación

  – ventajas: flexibilidad, eficiencia

• Paso de mensajes

  – el sistema operativo proporciona servicios para enviar y recibir

mensajes

    • enviar(destino, mensaje)

    • recibir(origen, mensaje)

  – ventajas: sencillez, puede ser utilizado a través de la red

• Tiene sentido proporcionar ambos mecanismos

Comunicación directa e indirecta

• Comunicación directa

  – origen y destino: procesos

  – ventaja: más fácil de implementar por el sistema operativo

• Comunicación indirecta

  – origen y destino: buzones, puertos (buzón asociado a un proceso)

    • enviar(buzón/puerto, mensaje)

    • recibir(buzón/puerto, mensaje)

  – ventajas:

    • buzones/puertos: un proceso puede recibir mensajes de
diferentes tipos en diferentes buzones/puertos

    • buzones: varios procesos pueden recibir mensajes del mismo
buzón

  – la comunicación directa equivale a que cada proceso tenga un único buzón del que sólo él recibe mensajes

Sincronización

• Envío y recepción bloqueantes

  – el emisor espera hasta que el mensaje ha sido entregado

  – el receptor espera hasta que le llegue el primer mensaje

• Envío no bloqueante/recepción bloqueante

  – el emisor no resulta bloqueado en ningún caso

(aunque el receptor no esté esperando)

    • es responsabilidad del programador (si es necesario) comprobar
si el mensaje ha sido recibido

  – el receptor espera hasta que le llegue el primer mensaje

• Envío y recepción no bloqueantes

  – el emisor no resulta bloqueado en ningún caso

  – el receptor tampoco

    • la función recibir devuelve error si no hay mensajes disponibles

Capacidad de
almacenamiento intermedio

• Sin almacenamiento intermedio (cita, rendezvous)

  – el S.O. no encola mensajes: emisor y receptor deben coincidir

  – requiere enviar bloqueante o que genere un error cuando no hay
receptor

  – utilizado habitualmente en la comunicación directa

• Con capacidad para N mensajes

  – el destino tiene capacidad para almacenar N mensajes pendientes

  – enviar puede ser no-bloqueante mientras haya espacio

  – cuando no queda espacio: enviar bloqueante o que genere un error

• Con capacidad infinita

  – se utiliza memoria dinámica para almacenar los mensajes

  – peligro: un emisor demasiado prolífico puede agotar la memoria del
sistema

Tamaño de los mensajes

• Mensajes de tamaño fijo

  – fácil de implementar

  – incómodo de utilizar (es necesario dividir los mensajes largos)

• Mensajes de tamaño variable

  – facilitan la programación

  – exigen gestión dinámica de memoria en el núcleo

    • más complejo

    • menos eficiente

• Mensajes dispersos

  – permiten incluir rangos de memoria separados en un sólo mensaje

  – permiten al recibir distribuir los datos de un mensaje entre varios

rangos de memoria

  – facilitan la programación

  – mejoran la eficiencia

  – más difíciles de implementar

Sincronización con paso de mensajes:
equivalencia buzón-semáforo

• Requisitos

  – eenominación indirecta mediante buzones

  – capacidad de almacenamiento intermedio infinita

  – enviar no-bloqueante

  – recibir bloqueante

• Equivalencia buzón- semáforo

  – valor positivo del semáforo ↔ nº de mensajes en la cola del buzón

  – valor negativo del semáforo ↔ nº de procesos esperando mensaje

  – operación signal ↔ enviar mensaje (el contenido no importa)

  – operación wait ↔ recibir mensaje (el contenido no importa)

Sincronización con paso de mensajes:
el problema de la sección crítica

Interbloqueos

Principios básicos de interbloqueos

• Interbloqueo: situación en la que todos los procesos de un
conjunto esperan a que se libere un recurso asignado a otro
proceso de ese conjunto

Modelo de trabajo

• Sistema formado por un número finito de recursos,
que deben ser distribuidos entre los procesos que lo soliciten

• Recursos agrupados en clases

  – clase: conjunto de recursos idénticos

  – cuando un proceso solicita un recurso de una clase
no importa qué miembro de la clase se le asigne

• Utilización de recursos:

  – solicitar recurso

  – utilización del recurso

  – liberación del recurso

Condiciones necesarias
(pero no suficientes)

• Exclusión mutua

  – los procesos necesitan acceso exclusivo a los recursos

• Retención y espera

  – los procesos retienen los recursos ya obtenidos mientras esperan
para obtener más recursos

• Sin expropiación

  – los procesos deben liberar los recursos voluntariamente

• Espera circular

  – consecuencia potencial de las tres primeras

  – existe una cadena circular de procesos en la que cada proceso
espera obtener un recurso asignado al siguiente proceso de la
cadena

Grafo de asignación de recursos

Métodos de tratamiento de interbloqueos

• Ignorar el problema (algoritmo del avestruz)

  – en función de la probabilidad de que ocurran

  – y del daño que puedan causar

• Garantizar que no ocurrirán

  – prevenir los interbloqueos: se elimina alguna condición necesaria

  – evitar el interbloqueo cuando va a producirse

• Detectarlo una vez ha ocurrido y recuperar al sistema

  – algoritmo de detección: comprueba si ha ocurrido

  – algoritmo de recuperación: deshace el interbloqueo

Prevención de interbloqueos

• Estrategia: eliminar al menos una condición necesaria →

es imposible que se produzcan interbloqueos

• Eliminar la exclusión mutua

  – sólo es posible con recursos que puedan ser compartidos

(ej: datos que puedan convertirse en de sólo lectura)

• Eliminar la retención y espera

  – los procesos deben liberar todos los recursos antes de solicitar más

  – inconvenientes:

    • procesos bloqueados hasta obtener todo lo solicitado

    • recursos asignados más tiempo del estrictamente necesario

• Eliminar la no expropiación:

  – aplicable cuando el estado puede ser guardado y restaurado

(ej: CPU, memoria principal...)

  – solución 1: cuando un proceso se bloquea en espera de recursos

    • se le expropian los que tenía

    • se añaden a la lista de recursos solicitados

  – solución 2: cuando un proceso solicita recursos

    • se le asignan los que están libres

    • se expropian los asignados a procesos esperando más recursos

    • se añaden a la lista de recursos pendientes de su anterior dueño

    • se le asignan al solicitante

    • si le falta algún recurso, espera

• Eliminar la espera circular

  – numerar todas las clases de recursos siguiendo un orden sensato

  – exigir que se soliciten los recursos por orden ó
exigir que se liberen los de orden inferior antes de cada solicitud

  – ejemplo:

    • R = {discos, cintas, impresoras}

    • f(discos) = 1, f(cintas) = 2, f(impresoras) = 8

    • P solicita 1 disco, 1 cinta, 1 disco

  – demostración (por reducción al absurdo):

    • se sigue una de las estrategias anteriores

    • tenemos a {P0, P1, .., PN} en espera circular:

      P0 → R1 → P1 → R2 → ... → PN → R0 → P0

      (Pi tiene asignado Ri y espera por Ri+1)

    • por tanto: f(R0) < f(R1) < ... < f(RN) < f(R0)

    • f(R0) < f(R0), luego no es posible

Evitación de interbloqueos

• La prevención de interbloqueos

  – no requiere información sobre el uso de recursos

  – genera una pobre utilización de recursos

• Evitación de interbloqueos

  – no se elimina ninguna condición necesaria

  – se solicita información adicional sobre el uso de recursos

     • qué recursos va a pedir cada proceso y en qué momento

      – permite una optimización del uso

      – información difícil (¿imposible?) de conseguir

    • numéro máximo de recursos de cada clase que puede necesitar
cada proceso

      – más fácil de conseguir

      – mejor utilización de recursos que con la prevención

Conceptos básicos

• Estado de asignación de recursos

  – nº máx. de recursos de cada tipo que cada proceso puede solicitar

  – nº de recursos de cada tipo asignados a cada proceso

  – nº de recursos de cada tipo disponibles

• Secuencia segura

  – secuencia de procesos <P1, P2, ..., PN> que,

  – en el estado actual de asignación de recursos, cumple que:

  – ∀i ∈ [1, N], Pi puede terminar con:

    • sus recursos

    • los asignados a los Pj con j<i

• Estado seguro: estado de asignación de recursos para el
que existe al menos una secuencia segura

• Estado inseguro: estado para el que no existe ninguna
secuencia segura

Ejemplo de estado seguro

Sea un sistema con: 12 impresoras (R0), 3 scanners (R1) y 4 procesos que las utilizan

Secuencia segura: <P1, P0, P2>

P1 puede terminar con lo disponible

P0 puede terminar con los disponible más lo de P1

P2 puede terminar con lo disponible más lo de P1 y P0

Ejemplo de estado inseguro

Sea un sistema con: 12 impresoras (R0), 3 scanners (R1) y 4 procesos que las utilizan

Secuencia segura: no existe

P0 no puede terminar con lo disponible (puede pedir 1 de R1)

P1 no puede terminar con lo disponible (puede pedir 2 de R0)

P2 no puede terminar con lo disponible (puede pedir 3 de R0 y 1 de R1)

 

Evitación de interbloqueos

• Mecanismo general:

  – el sistema comienza en un estado seguro

  – no se permiten transiciones a estados inseguros

    • aunque haya suficientes recursos disponibles

    • si se pasaría a un estado inseguro

    • se deniega la petición

• Aspectos importantes:

  – estado seguro implica que no existe interbloqueo

  – estado seguro no implica que exista interbloqueo

Múltiples recursos por clase: “Algoritmo del Banquero”

Ejemplo de ejecución del
algoritmo del banquero

Análisis del algoritmo del banquero

• Ventajas

  – no es necesario expropiar recursos ni hacer retroceder a los

procesos (ej: detección)

  – permite aprovechar mejor los recursos que con la prevención

  – coste elevado (MxN2 en el peor caso)

• Inconvenientes

  – el nº máximo de recursos de cada clase que cada proceso puede

necesitar necesita ser conocido a priori

  – los procesos deben ser independientes respecto a la sincronización

  – debe haber un nº fijo de recursos que gestionar

  – los procesos deben devolver los recursos antes de terminar

Detección y recuperación

Detección con
múltiples recursos por clase

Ejemplo de ejec. del alg. de detección
(sin interbloqueo)

Ejemplo de ejec. del alg. de detección
(con interbloqueo)

Utilización del algoritmo de detecccción

• La ejecución del algoritmo tiene un coste importante

  – memoria: estructuras de datos

  – procesador: coste O(MxN2)

• Factores que influyen en la decisión

  – ¿con qué frecuencia se esperan interbloqueos?

  – ¿a cuántos procesos se espera que pueda afectar?

  – a mayor intervalo entre ejecuciones,

mayor será el nº de procesos involucrados cuando se produzca

  – a menor intervalo, mayor sobrecoste

• Extremos

  – invocarlo cada vez que un proceso tiene que esperar

  – invocarlos sólo cuando el uso de CPU cae por debajo de un mínimo

Recuperación del sistema
tras un interbloqueo

• Informar al usuario o al administrador

  – de que hay interbloqueo

  – de los procesos involucrados

• Recuperación automática

  – finalización de todos los procesos involucrados

    • supone un gran coste

  – finalización de procesos uno a uno

    • evita tener que finalizar tantos procesos (o no)

    • requiere ejecutar el algoritmo de detección cada vez

  – vuelta atrás en vez de finalización

    • no se pierde todo el trabajo

    • es necesario haber guardado el estado previamente

  – expropiar recursos

    • elección de víctimas: en función del coste, evitar repetir
demasiado

    • es necesario finalizar/volver atrás a los procesos

Estrategia combinada

• Dividir los recursos en categorías

• Aplicar una estrategia para cada categoría
(la más apropiada para el tipo de recursos)