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

Ficheros: concepto y estructura interna

• Fichero: datos + atributos

  –usuario: colección de datos relacionados entre sí

  –S.O.: unidad lógica de almacenamiento

• Datos:

  – posible estructura interna

    • secuencia de bytes


    • secuencia de registros, ficheros indexados, de acceso directo...


    • estructuras específicas (ejecutables, presentación, gráficos...)

  – manejada en el S.O.

    • facilita la programación de aplicaciones


    • poca flexibilidad (tipos no soportados)


    • interfaz e implementación del S.O. más complejas

  – manejada por las aplicaciones

    • ventajas e inconvenientes a la inversa que en S.O.

Ficheros: atributos y métodos de acceso

• Atributos de ficheros

  – Nombre


  – Identificador único (para el S.O.)


  – Localización


  – Tamaño


  – Protección


  – Información temporal

• Métodos de acceso


  – secuencial


    Mediante el acceso secuencial, los registros de un fichero son recorridos en el sentido que aparecen en el fichero. No es posible comenzar en un registro particular dentro del fichero sin haber leído los anteriores registros de forma secuencial.

  – directo o aleatorio


    Mediante el acceso directo, los registros son seleccionados por un número de registro. Usando esta identificación, los registros podrán ser leídos y escritos en cualquier orden. Si usamos el acceso directo tenemos las siguientes reglas:

    – Todos los registros deben tener la misma longitud.
    – No es posible borrar un registro.
    – No se puede acceder a un fichero interno.

  – proyectado en memoria (más adelante)

Ficheros: operaciones

• crear (nombre, atributos)

   asignar espacio: todo, parte, nada

  
añadir entrada con nombre que apunte al fichero

  
establecer valor inicial de los atributos

•
borrar (nombre)

  
eliminar entrada del SF

  
liberar todo el espacio: cuando se cierre, inmediatamente

•
abrir (nombre, operaciones) -> identificador

  
buscar en el SF la información del fichero

  
comprobar que el proceso está autorizado a realizar las operaciones

  
crear entrada en la tabla de ficheros abiertos -> identificador

  
establecer posición inicial

  
devolver identificador

•
cerrar (id)

  
guardar información de la tabla de ficheros abiertos en disco

  
liberar memoria y entrada en la tabla de ficheros abiertos

• leer (id, destino, cantidad)

   comprobar que el fichero está abierto para lectura

  
localizar los datos en el disco

  
transferir los datos del disco a la memoria principal


escribir (id, origen, cantidad)

  
comprobar que el fichero está abierto para escritura

  
localizar los datos en el disco

  
transferir los datos de la memoria principal al disco


establecer posición (id, nueva posición)


consultar los atributos (id. o nombre) -> atributos


modificar los atributos (id. o nombre, atributos)

Directorios

Directorio: nombre -> atributos, datos


Operaciones:

  –
crear (directorio)

  –
eliminar (directorio)

  –
añadir (directorio, elemento)

  –
eliminar (directorio, elemento)

  –
buscar (directorio, elemento)

  –
listar (directorio, patrón)


Estructuras de directorios:

  – árbol: ficheros y directorios

  –
grafo: ficheros, directorios y enlaces (alias y ficheros indirectos)

Estructura de directorio de árbol

Referencias:

  –
absolutas: /home/carlos/so/pr1.sxw

  –
directorio actual (o directorio de trabajo): pr1.sxw

  –
lista de directorios de ejecutables (por ejemplo: PATH=/bin:/usr/bin): pine

Alias
(enlaces físicos, links, hard links)

Ficheros indirectos
(enlace simbólico, symbolic link, soft link)

ln un comando de Unix para vincular archivos o directorios entre sí. Básicamente, crea nuevos archivos con los nombres que usted especifique, y referencian a archivos ya existentes o directorios. Al ejecutar cualquier comando de Unix contra un enlace simbólico, se resuelve primero y el comando de Unix trabaja con ese archivo para producir los resultados deseados.



   Dos formas de vincular los archivos y directorios



Hay dos métodos comunes para vincular un archivo o directorio en Unix: enlaces simbólicos o soft linking y alias o hard linking .

   ¿Qué es un enlace simbólico?



Enlace simbólico es un tipo especial de archivo de Unix, que hace referencia a otro fichero o directorio. Enlace simbólico contiene el nombre de otro archivo y no contiene los datos reales. Para la mayoría de comandos, los enlaces simbólicos parecen un archivo normal, pero todas las operaciones (como la lectura de un archivo) hacen referencia al fichero o directorio al que apunta.



Cuando se elimina un enlace simbólico, sólo se quita uno de los punteros a los archivos reales. Cuando se quita el archivo original de un enlace simbólico, sus datos se pierden. A pesar de que el enlace simbólico seguirá existiendo, apuntará a un archivo que no existe y por lo tanto será inútil (es probable que tenga que ser borrado también).

   ¿Qué es un alias?



Alias es un puntero a los datos físicos. En efecto, todos los archivos estándar son alias, porque en última instancia, crean una asociación entre un nombre de archivo y los datos físicos, que corresponden a cada archivo.



En Unix, puedes crear tantos alias a un archivo como desees, e incluso hay un contador especial para tales referencias. Cuando estás utilizando el formato largo de un comando ls, puedes ver este contador.



Cuando se quita un alias, se resta del contador de punteros a los datos almacenados. Si eliminas el archivo original, los datos no se perderán, siempre que haya al menos un alias apuntando hacia él.

Estructura de directorio de grafo
(con alias y ficheros indirectos)

Borrado

  –
alias: contador con el número de alias

  –
ficheros indirectos: no plantea problemas

Recorrido de la estructura de directorio

  –
¿cómo recorrer cada nodo sólo una vez?

     árboles: recorrido en anchura o en profundidad

     ficheros indirectos: visitarlos; pero no seguirlos

     alias: no permitir alias de directorios (salvo . y ..)

  –
¿cómo detectar ciclos?

     árboles: no hay

     ficheros indirectos: número máximo de indirecciones

     alias: no permitir alias de directorios (salvo . y ..)

Protección

Protección: ¿quién puede hacer qué con qué objeto?

  – ¿quién? usuarios, grupos

  – ¿qué? tipos de acceso

  – ¿con qué? fichero, directorio, alias, fichero indirecto...

Funcionamiento habitual:

  – abrir el objeto (incluye conjunto de operaciones a realizar):

     se comprueba que el usuario tiene derecho a realizarlas todas


     se añade una entrada a la tabla de ficheros abiertos asociada al BCP del proceso


  – operaciones posteriores (lecturas escrituras)


     se comprueba que la operación pertenece al conjunto declarado


     no requiere accesos a disco (sólo el acceso a la tabla de ficheros
abiertos)


  – consecuencia: la revocación de derechos no es inmediata

Tipos de acceso: alias y ficheros indirectos

Alias

  Los del objeto a que hace referencia (habitualmente la protección hace
referencia al objeto, no al nombre)

Ficheros indirectos


  problema: pueden apuntar a ficheros o directorios


  solución: ignorar sus derechos de acceso


  el objeto al que apuntan queda protegido por el camino que contienen

Listas de acceso

Lista de pares (usuario, derechos) asociada a cada objeto a proteger

Problemas:

  – longitud de las listas

  – dificultad para expresar derechos de acceso genéricos (ej: todos)

Solución:

  –
grupos de usuarios grupo universal (todos los usuarios del sistema)

  – listas de acceso condensadas (ej: Unix):

     dueño del objeto, grupo del objeto, resto del mundo

Descripción

• Motivacion:

  – Los modelos de manejo de memoria anteriores precisan que un
proceso esté completamente en memoria para poder ser ejecutado. En
consecuencia, el tamaño de los programas se halla limitado por el tamaño de la memoria física

  – Sin embargo, los programas no utilizan de forma simultánea todo su
espacio de direccionamiento; por ejemplo existen zonas de código para
el manejo de errores o datos de tablas que nunca se acceden. En
consecuencia, es posible ejecutar programas de tamaño mayor que la
memoria física

• Definición:

  – La memoria virtual es una técnica que permite crear espacios lógicos
de direcciones de tamaño superior al de la memoria física (sólo limitado
por el tamaño de las direcciones lógicas en el procesador y por el
espacio disponible en el almacenamiento secundario)

  – Se basa en utilizar una parte del almacenamiento secundario como una
extensión de la memoria principal

  – Utilizan como mecanismo de traducción de direcciones la
segmentación o la paginación, pero permiten a los procesos guardar
los segmentos/páginas en el dispositivo de almacenamiento secundario

  – Al espacio lógico de direcciones de un sistema que implemente
memoria virtual le denominaremos espacio virtual de direcciones. El
proceso utiliza direcciones que pueden residir en memoria principal o

en el sistema de almacenamiento secundario.

  – A las direcciones lógicas se les llama direcciones virtuales

Justificación

• Beneficios de la utilización de memoria virtual

  – El tamaño del programa no se halla limitado por el tamaño de la
memoria física, sino por el espacio virtual de direcciones

  – Cada programa precisa de menos memoria física para ejecutarse, ya
que parte de él puede residir en el almacenamiento secundario. Es por
ello por los que aumenta el grado de multiprogramación, es decir el
número de procesos que se pueden ejecutar simultáneamente en
memoria

  – Al mover páginas o segmentos a memoria y no todo el proceso (caso
del swapping) se reduce la cantidad de datos que se envían en la E/S

• Pero, ¿no será muy lento?

• No, gracias a la localidad.

  – los accesos a memoria siguen patrones bien establecidos

  – propiedad empírica debida a la forma de estructurar programas

• Localidad temporal

  – probabilidad alta de repetir accesos a las mismas posiciones

  – motivos: bucles, subrutinas, pilas y variables utilizadas para cuenta y
totalización

• Localidad espacial

  – probabilidad alta de accesos a direcciones cercanas

  – motivos: recorridos de vectores, ejecución secuencial de código, los
programadores suelen agrupar la declaración de variables relacionadas

Paginación versus Segmentación

• La paginación evita el problema de la fragmentación del espacio
de almacenamiento secundario

• Por este motivo es el mecanismo más utilizado para
implementar la memoria virtual

• En algunos casos se utiliza segmentación paginada (modelo
combinado)

Detección
y tratamiento de fallos de página

• Detección de los fallos de página

  – un proceso intenta acceder a una dirección de una página que no está en
memoria

  – el hw de traducción de direcciones genera una excepción

  – se activa la rutina apropiada del S.O.

• Tratamiento (en rutina de tratamiento de la excepción)

  – Comprobar en la TdP si el acceso es legal o ilegal

  – Si es ilegal se termina el proceso

  – Si no, se busca la página en disco

  – Se busca un marco de página libre

    • en la tabla de marcos libres que mantiene el S.O.

    • si no hay libres, se reemplaza uno ocupado.

  – Se programa la lectura de la página del disco

  – Al terminar se actualiza la TdP del proceso

  – Se reanuda la ejecución de la instrucción que causó el fallo

Implementación

• Cada entrada en la TdP o en la TdS contiene más información:

  – un bit de presencia, que indica si el elemento referenciado está en
memoria o en disco

  – Un bit de accedido, que indica si se ha accedido al segmento o página

  – Un bit de sucio, que indica si el elemento ha sido modificado

• El sistema de memoria virtual debe resolver las siguientes
cuestiones:

  – Obtención de páginas: Cuándo se deben traer las páginas o segmentos
del disco a memoria

  – Colocación: Elegir dónde se debe ubicar en memoria la nueva página o
segmento.

  – Reemplazo: En el caso de que no haya espacio para una colocación,
elegir la página o segmento a reemplazar

Estrategias de obtención de página

• Obtención por demanda:

  – Las páginas se cargan únicamente cuando se hace una referencia a un
contenido de la página de forma explícita.

• permite transferir las páginas estrictamente necesarias

• no se dedica tiempo a decidir qué páginas transferir

• no resulta fácil adivinar qué páginas serán utilizadas

  – El tiempo de ejecución de un proceso no es óptimo

• Obtención anticipada

  – Se utiliza la localidad espacial para llevar a memoria las páginas que
tienen una probabilidad alta de ser referenciadas, pero antes de que se
produzca dicha referencia

• Reduce el tiempo de ejecución de un proceso

• Como las operaciones de E/S necesarias para cargar una página se
hacen en paralelo con la ejecución de otros procesos, no supone
demasiada sobrecarga

• Si el disco no está siendo utilizado al 100%, transferir alguna página
de más no es grave

Estrategias de reemplazo de página

• Objetivo: minimizar la tasa de fallos de página

• Comparación de algoritmos:

  – nº de fallos de página generados al procesar una serie de accesos a
memoria con un determinado nº de marcos disponibles

  – la serie puede ser real o generada matemáticamente

  – incluir en la serie todos los accesos supone almacenar demasiada
información, basta con utilizar cadenas de referencia

• se usa sólo el número de página (el desplazamiento no influye)

• se usa sólo el primer acceso de una serie de accesos repetidos
(el 2º y posteriores no pueden generar fallos de página)

  – ejemplo: sistema de 32 bits con páginas de 4 KB (12 bits de despl.)

• 01123800, 01123801, 01123802, 00332000, 01123800...

• cadena de referencia:

  – sólo nº de página: 01123, 01123, 01123, 00332, 01123...

  – eliminamos accesos consecutivos repetidos:
00123, 00332, 00123...

• Algoritmo óptimo

  – Consiste en reemplazar la página que tardará más en referenciarse

  – Garantiza el mínimo número de fallos de página posible para cualquier
número de marcos de página

  – Es imposible de implementar ya que no se pueden adivinar las
referencias futuras (Se utiliza como patrón de comparación)

  – Ejemplo de algoritmo óptimo

• FIFO: primero el primero en llegar

  – Se reemplaza la página que más tiempo lleva en memoria

  – Se añade en la TdP un campo con el tiempo en que se cargó la pagina

  – Se puede implementar con una cola

  – Tiene una tasa de fallos elevada, al reemplazar las páginas que se
cargan muy pronto y que además son muy usadas

• UMR: usado menos recientemente

  – Se reemplaza la página que lleva más tiempo sin ser usada

  – Se apoya en el principio de localidad temporal

  – Se puede implementar con una lista y cada vez que se referencia una
página, se la pasa al final de la lista

  – Produce una tasa de fallos muy baja (si no hay ciclos grandes), pero
tiene un coste de implementación muy alto, al tener que registrar todas
las referencias

• NUR: no usado recientemente

  – No requiere hw especializado ya que emplea el bit de accedido

  – Existen varias variantes que se aproximan al UMR

  – Se elige el primer marco de la lista que tiene su bit de accedido a 0

  – Es necesario poner los bits de accedido a 0 de forma periódica:

    • Se ponen todos a cero en cada fallo de página

    • Se ponen todos a cero a intervalos fijos de tiempo

    • (mejora 1) Algoritmo del reloj:

      – Se realiza un búsqueda circular en la lista de marcos, comenzando
siempre por el que ocupa la posición siguiente al último que fue
reemplazado. Si el marco tiene su bit de accedido a 1, se pone a 0 y se
comprueba el siguiente marco, así hasta encontrar un 0.

    • (mejora 2) Algoritmo del reloj con bit de modificado:

       – También se realiza un búsqueda circular en la lista de marcos, con la
idea de reemplazar una página que no haya sido accedida recientemente
y además que tampoco haya sido modificada

      • Se realizan varios pasos:

        – 1) Se buscan páginas con A=0 y M=0 sin modificar el bit A

        – 2) Si falla, se buscan páginas con A=0 y M=1, pero poniendo el bit A a 0 de las páginas que se van recorriendo

        – 3) Si falla, se vuelve al paso 1

  – Tiene tasas de fallos parecidas al UMR, pero no necesita hw
especializado

  – Tiene el problema de que cuando se producen ciclos grandes puede
producir muchos fallos de página

Eficiencia

• Para calcular el tiempo efectivo de acceso, se define:

  – tam como tiempo de acceso a memoria sin fallo de página (100 ns)

  – tamf como tiempo de acceso a memoria con fallo de página (tiempo que
transcurre entre que se trata la excepción, se lee la página del disco y se
continúa con la ejecución del proceso) (25 ms)

  – TF como la tasa de fallos, es decir el tanto por uno de referencias que se
realizan a páginas no cargadas (1 fallo cada 1000 accesos)

• El tiempo efectivo de acceso se calcula como:

      tea = (1-TF) tam + TFtamf

      tea = (1-1/1000)*100 + 1/1000*25000 = 99'9 + 25 = 124'9 ns

• Ejemplo: Si se desean retrasos inferiores al 10 % del tam

      tea < 1'1* tam , (1-TF)*100 + TF*25000 < 110 , TF < 10/24900

      Debe haber menos de 1 fallo por cada 2490 accesos

Detalles de Implementación

• Se mantiene siempre un número mínimo de marcos libres

  – se liberan marcos antes de que sea necesario utilizarlos

  – evita tener que liberar marcos mientras los procesos están esperando a
que se traten los fallos de página →
disminuye el tiempo de tratamiento de los fallos de página

• Se aprovechan los tiempos de inactividad del dispositivo de
intercambio para ir guardando las páginas modificadas

• El S.O. anota la página que ocupa cada marco de página

  – permite localizar páginas en marcos libres que no hayan sido reutilizados
(evitando accesos a disco)

  – corrige decisiones incorrectas en el algoritmo de reemplazo

• Se permite que los procesos puedan anclar páginas en memoria
principal

  – ventaja: evita fallos de página en casos importantes

  – problema: reduce el nº de marcos gestionado por el S.O.

Asignación de marcos de página

• Cuando se ejecuta un proceso, será necesario que como mínimo
tenga asignados suficientes marcos como para poder traer todas las páginas a las que hace referencia cualquier instrucción
máquina.

• Las estrategias más directas de asignación del número de
marcos inicial que puede disponer cada proceso son:

  – Dividir los marcos entre los procesos a partes iguales

  – Dividir el número de marcos de forma proporcional al tamaño de los
procesos

  – Asignar mayor número de marcos a los procesos más prioritarios

  – Asignación mixta tamaño-prioridad

• Después, si la política del algoritmo de reemplazo de páginas es
global (frente a la local), este número podrá variar

  – En este caso, como el número de marcos de un proceso depende de los
demás, éste presentará comportamientos diferentes en ejecuciones
sucesivas. Sin embargo esta estrategia es más eficiente de forma
general

Hiperpaginación

• Si el número de marcos que dispone un proceso cae por debajo
del mínimo necesario para ejecutar una instrucción, el proceso se
deberá detener en espera de que hayan suficientes marcos libres

• Si un proceso tiene pocos marcos asignados, es posible que
cada fallo de página reemplace a una página que va a ser
solicitada de nuevo. En consecuencia se dice que el proceso está
hiperpaginando, puesto que está más tiempo trayendo páginas
del disco que ejecutando instrucciones (trashing)

• Si el sistema emplea estrategias de reemplazo globales, puede
bloquearse debido a que hiperpaginan todos los procesos

  – Si un S.O. aumenta el grado de multiprogramación en función del
porcentaje de utilización de la CPU

  – Cuando un proceso necesita más marcos se apropia de los de otros
procesos, que empezaran a su vez a paginar.

  – El descenso de uso de la CPU hace que se carguen más procesos

• Para evitar la hiperpaginación:

  – Si la estrategia de reemplazo de páginas es local, se aconseja asignar un
número mínimo de marcos a los procesos

  – Si la estrategia es global, habrá que monitorizar el número de marcos
disponible para cada proceso

• La siguiente figura muestra la relación entre el grado de
multiprogramación y la hiperpaginación

Conjunto de trabajo

• Se define el conjunto de trabajo de un proceso como el
conjunto de páginas que está utilizando activamente en un
determinado instante. De esta forma CT(t,v) define el conjunto de
páginas que han sido referenciadas en el intervalo [t-v,t]

• En función de v se obtendrá un conjunto de trabajo válido

  – Si v es demasiado pequeño, CT(t,v) no contendrá el conjunto de trabajo

  – Si v es demasiado grande, CT(t,v) contendrá muchas páginas que no
pertenecen al conjunto de trabajo del proceso

Asignación por conjunto de trabajo

• Se considera el conjunto de trabajo del proceso al conjunto de
páginas que deben estar en memoria principal para que el
proceso se ejecute con eficiencia

• En un sistema de paginación con obtención de páginas
anticipada, el S.O. deberá elegir un valor de v adecuado (llamado
ventana del conjunto de trabajo) de forma que CT(t,v) se
aproxime a la definición anterior

• El S.O asigna un número diferente de marcos a los procesos en
función del tamaño de su conjunto de trabajo

  – Si hay suficientes marcos libres se inician nuevos procesos

  – Si a un proceso no se le pueden asignar marcos suficientes se le
suspende

• Cuando un proceso cambia de conjunto se produce siempre un
incremento en su número de marcos asignado

• La implementación de esta estrategia es muy costosa

Asignación por frecuencia
de fallos de página

• El S.O. lleva cuenta de la tasa de fallos de página de los
procesos para asignarles un número de marcos determinado

• Implementación:

  – Se eligen dos límites temporales, uno superior y otro inferior en función
del tiempo que ha trascurrido desde el último fallo de página

  – Cuando ha trascurrido un tiempo mayor que el límite superior, se liberan
los marcos de las páginas a las cuales no se ha accedido durante ese
intervalo

  – Cuando se produce un fallo de página en un tiempo menor al del límite
inferior, se le asigna al proceso un nuevo marco  

• Con este algoritmo se ajusta dinámicamente el número de
marcos de los procesos, previniendo la hiperpaginación

• Esta estrategia, para asignar los marcos, monitoriza los fallos de
página, en vez de las referencias, por lo que tiene mejores
prestaciones que la estrategia de los CT.

 

• Aprovecha las ventajas de los modelos segmentado y paginado

  – La segmentación, debido a su tamaño variable:

• Permite un esquema de protección más flexible

• Se acopla mejor a la forma en que se estructuran los programas

  – La paginación, debido a que elimina la fragmentación externa y a que la
fragmentación interna se controla con un tamaño de página adecuado:

    • Supone un esquema de administración de memoria más eficiente

  – La paginación es el modelo más adecuado si se utiliza intercambio con el
disco (“swapping”)

• El sistema de traducción de direcciones maneja tres direcciones
diferentes:

  – Lógicas: Generadas por el programa (s,d)

  – Lineales: El hardware de segmentación traduce la dirección
bidimensional a una dirección unidimensional, la dirección lineal.

  – Físicas: Que se corresponden ya con direcciones de memoria física y se
generan a partir de la dirección lineal

Traducción de direcciones

 

• El espacio de direcciónes lógico se divide en bloques idénticos de
tamaño fijo, llamados páginas

• Cada página se almacena en memoria en un marco de página

• Ventaja: Se pueden almacenar trozos de programa en memoria
en cualquier orden, eliminando la fragmentación externa

• Es necesario utilizar una Tabla de Páginas (TdP) para almacenar
la información relativa a las páginas del proceso.

Tamaño de página

• Presenta el problema de la fragmentación interna

  – La unidad mínima de asignación es una página, con lo que se
desperdicia como media la mitad de una página por asignación

  – El tamaño mínimo elegido vendrá impuesto por el hardware, aunque se
pueden utilizar múltiplos de este tamaño de página

• Las TdP son menores con páginas grandes

• La fragmentación interna es menor con páginas pequeñas

• El modelo permite la relocalización dinámica en t. de ejecución

Traducción de direcciones

• Las direcciónes lógicas se dividen en Número de página (p) y

desplazamiento dentro de la página (d)

• Implementación:

  – Si las TdP son de tamaño reducido se implementan mediante registros
especializados en la CPU, permitiendo la traducción eficiente de las
direcciones, aunque retrasando los cambios de contexto.

  – Habitualmente las TdP se implementan en memoria: es necesario la
existencia del Registro Base de la Tabla de Páginas (RBTdP)

  – Existe también el Registro de Longitud de la TdP (RLTdP) que evita el
mantener una TdP completa, puesto que habitualmente los procesos no
gastan todo su espacio de direccionamiento

Tabla de páginas invertida

• En la tabla de páginas invertida existe una entrada en dicha
tabla por cada trama de página, independientemente del número
de procesos en el sistema y del número de páginas del espacio
lógico de los procesos

Buffer de traducción adelantada (TLB)

• El TLB (Translation Look-aside Buffer) está formado por un
conjunto de registros asociativos que guardan las entradas de la
TdP usadas más recientemente

• El uso del TLB reduce el “tiempo efectivo de acceso a memoria“
(tea)

  – Si se define:

    • tam como tiempo de acceso a memoria (cuando no hay mecanismo de
traducción de direcciones)

    • tab como el tiempo de acceso al TLB

    • TA como la tasa de aciertos

  – El tiempo efectivo de acceso (que es el tiempo medio) se calcula como:

tea = TA(tab+tam) + (1-TA)(tab+2tam)

Protección

• Es posible establecer permisos de acceso para cada página

• Los permisos se almacenan en la TdP

• Simultáneamente con la traducción se comprueban los permisos
y se genera una excepcción en el caso de que se intente un
acceso no autorizado.

Memoria Compartida

• Memoria compartida

  – Se utiliza el mismo esquema que para compartir segmentos

Gestión de procesos

• Cuando se desea ejecutar un nuevo proceso, el S.O.:

  – Identifica el tamaño del proceso en páginas

  – Comprueba que existen suficientes marcos de página libres en la
memoria física y crea una TdP para el proceso

  – Guarda la dirección de la TdP del proceso en su BCP

  – Para cada página del proceso

    1) Le asigna un marco y actualiza la correspondiente entrada en la TdP

    2) Copia los datos al marco

  – Incluye al proceso en la cola de procesos listos

• Si no existe suficiente memoria, el proceso debe esperar en cola

• Cuando se realiza un cambio de proceso, el S.O. cambia el
RBTdP y el RLTdP del procesador, cambiando por tanto de TdP

 

• La segmentación y la paginación permiten dividir a los procesos
en partes ocupando varias zonas dispersas de la memoria.

• El espacio lógico de direcciones está formado por un conjunto
de segmentos, definidos por la dirección base y su longitud.

• Se utilizan direcciones lógicas de 2 dimensiones: segmento y
desplazamiento dentro del mismo

– Cada segmento tiene propiedades
diferentes: L, L/E, privado,
compartido...

– Se suelen utilizar como mínimo
segmentos de datos, código y pila

– Tienen tamaños diferentes

– Los módulos del programa usan
segmentos diferentes, que se
enlazan empezando en la dirección
lógica de origen 0.

Traducción de direcciones

• La traducción de direcciones es el proceso por el cual se
convierten las direcciones lógicas (de dos dimensiones: segmento, desplazamiento) a una dirección física de una
dimensión.

– Existe una estructura de n
datos auxiliar: la Tabla
de Segmentos (TdS)

– La tabla tiene una
entrada para cada
segmento del proceso

– Existe una tabla para
cada proceso más otra
general para almacenar
las descripciones
comunes a varios
procesos.

Implementación

• La TdS se puede implementar en memoria o con registros

  – Registros:

     • La comprobación y el cálculo de direcciones se realiza en paralelo,
por lo que la traducción de direcciones es muy rápida.

     • Debe limitarse el número de segmentos para no usar muchos
registros

  – En memoria:

      • Adicionalmente se tiene un registro que apunta al comienzo de la
tabla (Registro Base de la TdS – RBTdS) y otro que contiene la
longitud de dicha tabla (Registro Longitud de la TdS – RLTdS).

     • Para traducir la dirección: Se comprueba que s < RLTdS y se forma la
dirección de acceso a la TdS mediante: RBTdS + s

     • Problema: Para acceder a memoria se requieren dos accesos (uno a
la TdS y otro a la dirección especificada). Se ralentiza el proceso.

     • Solución:

       – Usar registros que guardan las entradas usadas más recientemente

        – Usar registros que guardan las entradas necesarias para la ejecución

Protección

• Se asocian diferentes tipos de protección a los diferentes tipos
de segmento

Memoria Compartida

• El modelo segmentado permite que varios procesos compartan

áreas de memoria física.

  – Para el acceso a la memoria compartida, los procesos pueden utilizar
direcciones lógicas diferentes e incluso segmentos diferentes

  – Las referencias dentro de la zona compartida deben ser relativas (al
segmento actual o al contador de programa)

  – El código puede compartirse en modo de sólo lectura

Análisis del modelo segmentado

• Este modelo presenta desaprovechamiento de memoria (aunque
menor que con la asignación contigua)

  – Fragmentación externa: huecos pequeños entre segmentos

  – Espacio ocupado por las TdS de los procesos residentes en memoria

• Gestor de procesos:

  – Cuando se crea un proceso, el planificador realiza las tareas:

    • Comprobar que existe espacio para el nuevo proceso. Para ello debe
encontrar un hueco apropiado para cada segmento del mismo

    • Crea una TdS para el proceso

    • Guarda el RBTdS y el RLTdS en el BCP del proceso

    • Para cada segmento copia su contenido en la memoria que le ha sido
asignada y actualiza la entrada en la TdS

    • Incluye al proceso en la cola de procesos listos

  – En el cambio de contexto

    • Se guardan los registros con segmentos

    • Se restauran los registros con segmentos, el RBTdS y el RLTdS

Ejemplo de implementación:
procesadores “x86” de intel

• Disponen de registros especializados

  – para almacenar descripciones de segmentos (entradas en la TdS,
denominada “Tabla de Descriptores de Segmentos”)

    • CS: código, DS: datos, SS: pila

    • ES, FS, GS: uso general

  – para localizar las tablas de segmentos

    • GDTR, para localizar la GDT, Global Descriptor Table

    • LDTR, para localizar la LDT, Local Descriptor Table

• Cada dirección lógica se divide en:

  – Segmento: 16 bits

    • tabla (GDT/LDT), 1 bit

    • indice en la tabla, 13 bits (8192 segmentos por tabla)

    • Requested Privilege Level (RPL), 2 bits

  – Desplazamiento: 32 bits

• El espacio lógico de direcciones con segmentación es de:

  – 21 x 213 x 232 = 246 = 64 TB

• A continuación se describen modelos básicos que utiliza el S.O.
Para asignar memoria a los procesos en ejecución.

• Por asignación contigua se entiende que todo el proceso va a
utilizar una zona contigua de la memoria principal.

• Particiones Fijas

  – Inicialmente las particiones eran de tamaño fijo (acordado durante la
compilación del S.O.)

  – Cada partición se asigna a un proceso

  – El modelo permite la multiprogramación

  – Permite cambiar procesos en ejecución entre la memoria y el disco

  – Dos variantes:

    • Todas las particiones del mismo tamaño

    • Creación de particiones de diferente tamaño

– Presenta el problema de la fragmentación interna

• Particiones dinámicas

  – El número y el tamaño de las particiones es variable, adecuándose a
las necesidades en tiempo de ejecución.

    • Inicialmente se tiene una partición para el S.O. y otra con la
memoria libre

    • Cuando llega un proceso se busca una partición libre lo
suficientemente grande y se divide en dos; una para el proceso y la
otra queda libre

    • Al finalizar el proceso, su partición se libera y se une a la lista de
particiones libres (llamadas huecos)

  – Liberación de particiones:

    • Cuando se libera una partición, se debe tener la precaución de unir
en un solo hueco aquellos que resulten adyacentes.

  – Algoritmos de selección de huecos:

    • El primer ajuste (First-Fit): Se selecciona el primer hueco de la lista
lo suficientemente grande como para alojar al programa.

      – Suele ser el que mejores resultados ofrece

    • El siguiente ajuste(Next-Fit): Como el anterior, pero se comienza la
búsqueda en el lugar de la lista donde se dejó la vez anterior

    • El mejor ajuste(Best-Fit): Se toma el espacio del hueco que tiene el
tamaño más próximo al del bloque solicitado.

      – Se necesita recorrer toda la lista o tenerla ordenada por tamaño.

      – Genera los huecos más pequeños

    • El peor ajuste(Worst-Fit): Se toma el hueco más grande
independientemente del tamaño del proceso.

      – Se necesita recorrer toda la lista o tenerla ordenada por tamaño.

      – Genera los huecos más grandes

– Ejemplo: Liberación de un bloque en sistemas con particiones

variables

– Ejemplo: Llegan las peticiones de 75K y 250K

Fragmentación y Compactación

– Problema de la fragmentación externa: La memoria libre se divide en
huecos pequeños incapaces de albergar a un nuevo proceso, aun
cuando existe suficiente memoria libre como para satisfacer la petición.

• Si los hueco que genera una asignación tiene un tamaño reducido,
es aconsejable incluirlo en esta nueva asignación para evitar que se
forme. El coste de mantenerlo en la lista es mayor que los
beneficios que reporta.

– Solución a la fragmentación externa: Compactación: Esta estrategia
consiste en reunir los huecos dispersos en uno mayor. Para ello es
necesario desplazar los programas en memoria, con lo que se pierde
mucho tiempo copiando las direcciones de memoria.

• El S.O. debe proveer mecanismos de relocalización en tiempo de
ejecución.

• Debe existir apoyo del hardware para realizar la compactación de
forma eficiente.

Protección y Reubicación

– Al existir varios procesos en ejecución, es necesario evitar que entre
ellos puedan modificar los espacios de memoria que tienen reservados
(incluyendo el S.O.).

– El procesador tiene varios registros que ayudan a resolver el problema:

  • Registro base: Guarda la dirección física más pequeña que puede
generar un programa

  • Registro límite: Guarda la dirección lógica más grande permitida al
programa más uno. (La dirección lógica más pequeña es siempre 0).

– El S.O. se encarga de escribir en estos registros los valores adecuados
antes de transferir el control al proceso para mantener la integridad del
propio S.O. y la independencia en la ejecución de los procesos.

– Cuando el programa emplea una dirección lógica, el hardware
comprueba que sea inferior al límite y si es así, le añade el valor del
registro base para obtener la dirección física que se emplea para acceder
a memoria. En caso contrario se genera una excepción.

El espacio lógico de direcciones de un proceso es el
conjunto de direcciones (lógicas) a las que puede acceder

– Esquema hardware de funcionamiento

– Ejemplo de funcionamiento

– Este modelo tiene las siguientes características:

  • Permite relocalización dinámica en tiempo de ejecución

  • Permite proteger a unos procesos de otros y al S.O. de todos ellos.

Planificación

– Planificación a largo plazo

  • El planificador a largo plazo:

    – Mantiene una cola de programas nuevos

    – Carga los programas a medida que va quedando libre suficiente memoria

  • Algoritmos para gestionar la cola de programas nuevos:

    – Si usa una cola FIFO es posible que un proceso muy grande mantenga
esperando a procesos para los que existe suficiente memoria.

    – Si usa la mejor asignación se favorece la ejecución de procesos
pequeños que pueden retrasar indefinidamente la ejecución de un
proceso que necesite mucha memoria.

– Planificación a medio plazo

    • Intercambio con el disco de procesos completos.

    • El registro base permite la reubicación → los procesos pueden ser
cargados en una partición diferente cada vez

 

• La administración de la memoria supone la gestión de la memoria
física para que pueda ser compartida entre los procesos y el S.O.

• Se estudia la vertiente espacial y la temporal

• Objetivos de la gestión de la memoria

  – Permitir la protección y la compartición de áreas de memoria entre
procesos

  – Desaprovechamiento mínimo de la memoria

    • Reduciendo el espacio utilizado por el gestor de la memoria

    • Permitiendo la compartición de código

    • Reduciendo la fragmentación interna y externa

  – Mínima complejidad temporal del algoritmo gestor de la memoria

  – Mínimo recargo introducido por el gestor en el acceso a memoria


• La asignación de direcciones supone la sustitución de los
nombres simbólicos que se utilizan en los lenguajes de
programación por direcciones.

• Las direcciones pasan por 3 estados:

  – Direcciones simbólicas

  – Direcciones relocalizables

  – Direcciones absolutas

• Las direcciones se resuelven en:

  – Tiempo de compilación

  – Tiempo de carga

  – Tiempo de ejecución

• Las librerías del sistema ofrecen servicios y contienen el código
que permite mediante funciones de alto nivel realizar llamadas al
sistema. También contienen otras utilidades de uso común.

  – Librerías estáticas: El código de la librería se incluye en el ejecutable
final, con las referencias resueltas en tiempo de enlace.

  – Librerías dinámicas: Las librerías se cargan en memoria bien al cargar el
proceso, bien cuando se produce la llamada a primera función.

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)