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

Estructura de los discos

Numeración de los sectores

Particiones y volúmenes

Estructura de los sistemas de ficheros

  Sistemas de ficheros

• Estructura de la información en una partición

• Debe ser capaz de alojar todos los elementos lógicos
(ficheros, directorios, alias, ficheros indirectos...)

• Incluye:

  – gestión del espacio libre

  – asignación de espacio

• Importante: tamaño de bloque
(eficiencia frente a fragmentación interna)

• Superbloque:


  – información básica para interpretar la información alojada en la partición

  – incluye:

    • estadísticas (tamaño, nº de bloques libres...)

    • lista de bloques libres (o un puntero a donde comienza)

    • localización del directorio raíz

Gestión del espacio libre

  Mapa de bits

• Cada bit representa a un bloque (0: ocupado, 1: libre)

• Ventajas:

  – simple y eficiente (si se tiene todo el mapa en memoria)

• Inconvenientes

  – ocupa espacio aunque casi toda la partición esté llena

  – poco eficiente (si no se puede mantener todo el mapa en memoria)

Listas enlazadas

• cada bloque libre contiene el número del siguiente bloque libre

• ventajas:

  – no es necesario reservar espacio para la lista de bloques libres

• inconvenientes

  – resulta lento obtener N bloques libres

Listas enlazadas con agrupaciones

• un bloque libre que contenga punteros está lleno de punteros a
bloques libres

• ventajas:

  – no es necesario reservar espacio para la lista de bloques libres

  – eficiente independientemente de la fragmentación de la partición

Métodos de asignación de espacio

  Asignación contigua

• cada fichero ocupa una serie de bloques consecutivos

• localización del fichero: (primer bloque, nº de bloques)

• ventajas

  – adecuado para acceso secuencial

  – adecuado para acceso aleatorio

  – minimiza el tiempo de búsqueda

• inconvenientes

  – fragmentación externa

  Asignación mediante enlaces

• cada fichero se organiza como una lista enlazada de bloques

• localización del fichero: (primer bloque, último bloque)

• ventajas

  – adecuado para acceso secuencial

  – elimina la fragmentación externa

• inconvenientes

  – acceso aleatorio poco eficiente

  – poco fiable

  – espacio ocupado por punteros

  Tabla de asignación de ficheros (FAT)

• asig. mediante enlaces con los punteros en una tabla (la FAT)

• ventajas

  – reduce el nº de accesos a disco (la FAT suele mantenerse en memoria)

• inconvenientes

  – la FAT puede no caber en memoria

  – acceso aleatorio poco eficiente

  Asignación indexada

• existen bloques especialidados: los bloques de índices (BI)

• cada fichero tiene su BI

• ventajas

  – apropiado para el acceso secuencial y aleatorio

• inconvenientes

  – tamaño máximo de fichero:
nº de punteros por bloque (NPB)

  – espacio ocupado por el BI

• formar una lista enlazada con los BI

  – ineficiente para acceso directo en ficheros grandes

  Asignación indexada multinivel

• todos los ficheros necesitarán varios BIs
(también los ficheros pequeños)

• todo acceso requiere atravesar todos los
niveles (tb. en los fich. pequeños)

  Asignación indexada combinada (nodos i)

• cada fichero se representa por un nodo-i que contiene

  – atributos del fichero: tamaño, permisos, dueño...

  – punteros a datos

  – punteros indirectos (apuntan a BI)

  – punteros doblemente indirectos (apuntan a BI que apuntan a BI)

  – punteros triplemente indirectos

• solución de compromiso:


  – ficheros pequeños: acceso directo, no se utilizan BI

  – ficheros medianos/grandes: pocos niveles de indirección

• tamaño máximo de fichero: TB· (12 + NPB + NPB2 + NPB3)

  – TB: tamaño de bloque

  – TP: tamaño de un puntero

  – NPB: nº de punteros por bloque (TB/TP)

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