Gestión de Memoria y Dispositivos E/S

Algoritmos de Reemplazo de Páginas

• Least Recently Used (LRU): Usado menos recientemente. Se reemplaza la página que fue usada por última vez hace más tiempo. Ofrece un buen resultado, pero es muy costoso de implementar si no lo soporta el hardware:
  • Instante de tiempo de último uso de cada página.
  • Lista encadenada.
• First-In First-Out (FIFO): Primero en entrar, primero en salir. Se reemplaza la página que hace más tiempo que fue cargada. Es muy fácil de implementar mediante un buffer circular de tamaño fijo. Se basa en una premisa errónea: que la página más antigua es la menos accedida.
• Not Recently Used (NRU): No usado recientemente. Aproximación a LRU. Se elimina una página al azar en el siguiente orden:
  • Una página con bits de referencia a 0 y modificación a 0.
  • Una página con bit de referencia a 0 y bit de modificación a 1.
  • Una página con bit de referencia a 1 y bit de modificación a 0.
  • Una página con bits de referencia 1 y modificación a 1.

  El bit de referencia se pone a 0 periódicamente.

• Second Chance: Segunda oportunidad. Versión modificada del FIFO. Antes de eliminar una página se comprueba el bit de referencia:
  • Si es 0: Se elimina la página.
  • Si es 1: Se pone el bit a 0 y se coloca la página al final de la cola.
• Algoritmo del reloj: Versión avanzada del FIFO.
  • Buffer circular.
  • Cuando se produce un reemplazo se recorre el buffer circular a partir de la posición del último reemplazo:
    1. A Si el bit de referencia de la entrada está a 1, se pone a 0.
    2. B Si el bit de referencia de la entrada está a 0, se reemplaza.
    3. Se avanza a la siguiente entrada.
  • Se puede mejorar cambiando el número de bits de referencia.

Ejercicio de Fragmentación en Paginación

Imagina un sistema operativo que emplea una gestión de memoria paginada. Cada página tiene un tamaño de 2048 bytes (o posiciones). La memoria física disponible para los procesos es 8kbytes.

Primero llega un proceso que necesita 31.566 bytes de memoria y después llega otro proceso que consume 18.432 bytes cuando se carga en memoria. Se pide:

1. ¿Qué fragmentación interna provoca cada proceso?
2. ¿Qué fragmentación externa provoca cada proceso?

• Cada página ocupa 2.048 bytes (2¹¹ bytes)
• La memoria física es de 8kbytes (2¹³ bytes)

Solución

1. Si el primer proceso necesita 31.566 bytes ocupará 31.566/2.048 = 15,41 marcos.
   Es decir, completamente 15 marcos, es decir, 15 x 2.048 = 30.720 bytes.
   En el siguiente marco sólo se ocuparán 31.566 – 30.720 = 846 bytes, quedando libres (fragmentación interna) 2.048 – 846 = 1.202 bytes.
2. El segundo proceso necesita 18.432 bytes con lo que ocupará: 18.432/2.048 = 9 marcos.
   En este caso, no se produce fragmentación interna puesto que lo que ocupa el proceso es múltiplo del tamaño del marco. La gestión de memoria por paginación evita la fragmentación externa.

Controlador de Dispositivo

El controlador de dispositivo actúa de interfaz entre la CPU y el dispositivo de E/S.

• Cada controlador puede ocuparse de uno o varios dispositivos del mismo tipo (controlador IDE → varios HDD, o un HDD y un CDRW, ..)
• Los controladores se comunican con la CPU a través de unos registros o puertos. Generalmente incluyen:
  • Registros de control: Para enviar órdenes al dispositivo.
  • Registros de estado: Para obtener información del estado del dispositivo o controlador, disponibilidad de datos.
  • Registros de datos: Pueden ser de entrada, salida o bidireccionales.
• Típicamente son registros de 1 a 8 bytes de tamaño.
• Algunos controladores tienen chips FIFO que permiten almacenar pequeñas ráfagas de datos (buffers), mientras el host (CPU) no los puede tomar.

Ejercicio: Tamaño de Mapa de Bits

El sistema operativo utiliza un mapa de bits para contabilizar el uso de la memoria. Se sabe que la memoria tiene un tamaño de 1.5Gbytes, que se utiliza un sistema de gestión de memoria paginada y que el tamaño de página es de 3K. Se desea conocer cuántos Kbytes ocupa el mapa de bits que contabiliza el uso de la memoria.

Memoria: 1.5Gbytes = 1.5 x 2³⁰

Tamaño de marco/página: 3K = 3 x 2¹⁰

Número de marcos: (1.5 x 2³⁰) / (3 x 2¹⁰) = 0.5 x 2²⁰ = 2¹⁹ = 2⁹ x 2¹⁰ = 524.288 marcos

Es decir, se necesitan 524.288 bits para indicar si una posición esta ocupada o no.

524.288 bits son 524.288 / 8 = 65.536 bytes, es decir, 2¹⁶ bytes, es decir, 64Kbytes

Ejercicio 1: Tamaño de la Tabla de Páginas

Calcule el espacio de una tabla de páginas de un nivel para un espacio de direcciones de 16 bits, 32 bits, 48 bits. Asuma que cada entrada de páginas es del mismo tamaño que el espacio de direcciones (16 bits → 2 bytes)

El tamaño de página es 8kB (2¹³)

• Espacio de direccionamiento de 16 bits
  • Nº de páginas = 2¹⁶ / 2¹³ = 2³ = 8 páginas de 8kB cada una
  • Cada entrada en la tabla de páginas ocupa 16 bits, es decir, 2 bytes
  • Espacio de la tabla de páginas = 2B x 2³ = 2⁴ = 16B por tabla
• Espacio de direccionamiento de 32 bits
  • Nº de páginas = 2³² / 2¹³ = 2¹⁹ páginas de 8kB cada una
  • Cada entrada en la tabla de páginas ocupa 32 bits, es decir, 4 bytes
  • Espacio de la tabla de páginas = 4B x 2¹⁹ = 2²¹ = 2MB por tabla
• Espacio de direccionamiento de 48 bits
  • Nº de páginas = 2⁴⁸ / 2¹³ = 2³⁵ páginas de 8kB cada una
  • Cada entrada en la tabla de páginas ocupa 48 bits, es decir, 6 bytes
  • Espacio de la tabla de páginas = 6B x 2³⁵ = (2 + 2²) x 2³⁵ = 2³⁶ + 2³⁷ = 64GB + 128GB = 192GB por tabla

Ejercicio 2: Tabla de Página Multinivel

• Repetir los cálculos para el espacio de direcciones de 32bits, 2 niveles de página, tamaño de página de 4kB

Tamaño de página 4kB → 12 bits

Nº entradas: 2 niveles:

• Si reservamos 12 bits para el desplazamiento dentro de la página, nos quedan 20 bits, de los cuales los 10 bits más significativos se usarán para el primer nivel y los 10 bits menos significativos para el segundo.
• Cada entrada ocupa 32 bits, esto es, 4 bytes
• Tamaño del nivel 1: 2¹⁰ x 4B = 4kB
• nº de tablas de página de nivel 2 = nº de entradas de tabla de nivel 1 = 2¹⁰

Por tanto, Tamaño del nivel 2: 4 x 2¹⁰ x 2¹⁰ = 2²² = 4MB – Tamaño total: 4,004MB

Módulo DMA

• Componente separado del procesador.
• Se encarga de las operaciones de Entrada/Salida.
• Posee acceso directo a la memoria principal. Descarga al procesador de la tarea del intercambio de datos.
  • Sin módulo DMA: El procesador supervisa cada copia de datos.
  • Con módulo DMA: El procesador simplemente da la orden de hacer la copia.