Swapping

#

Hasta ahora, habíamos asumido que todos los espacios de direccionamiento de todos los procesos, y en específico todas las páginas en uso por todos los procesos, cabían en memoria, pero la realidad es diferente.

Generalmente, cuando tengamos una cantidad limitada de RAM para alojar una cantidad arbitraria de procesos, tendremos que encontrar la manera de desplazar o swappear las páginas (que aunque tienen datos válidos en memoria reservada, no están siendo usadas activamente) a un sitio en el que tengamos más espacio disponible, para dejar la RAM a los procesos que la necesiten (y luego traerlas de vuelta a la RAM). Habitual y conceptualmente este otro sitio es el disco duro, aunque evidentemente resulta mucho más lento acceder a datos en disco que a datos en RAM, pero por eso mismo se suelen swappear los datos que menos se usan.

Ese sitio en disco en el que se alojan las páginas swappeadas recibe el nombre de swap space, y puede imaginarse como una zona dividida en páginas, cuya dirección base debe conocer el sistema operativo.

Present Bit (y TLB Valid Bit)

#

Entre los bits de control que decíamos que podían tener las entradas de la tabla de paginación está el Present Bit, cuyo propósito es indicar si una página específica está en memoria (present=1) o ha sido swappeada a disco (present=0). Este Present Bit está únicamente en la tabla de paginación, no en el TLB.

Esto quiere decir que, si el Valid Bit en una página del TLB está a 1, obligatoriamente esa página tiene que estar en memoria, no en disco. Si tenemos una página en memoria, en el instante en el que el SO la swappea, necesariamente tiene que actualizar la entrada del TLB y poner el valid bit a 0. Aunque puede parecer problemático, si una página se elige entre todas para ser swappeada, es normalmente porque lleva un rato sin usarse, y si lleva un rato sin usarse, es menos probable que tenga una entrada en el TLB que por tanto deba ser invalidada.

Page Faults

#

Sin el swapping, cuando un programa accedía a una dirección, el SO comprobaba el TLB, y en el peor caso (TLB Miss) tenía que ir a la tabla de paginación, coger la traducción y meterla al TLB. Ahora hay un caso todavía peor: Que cuando el SO va a la tabla, se encuentre el Present Bit a 0 (página en disco). En ese caso, se producirá una excepción denominada Page Fault.

Por simplicidad, los Page Faults se gestionan por software siempre. Dado que acceder a disco y las operaciones de E/S en sí son tan lentas, el overhead que supone hacer esto por software es mínimo frente al tiempo que tarda una operación I/O en realizarse. El subsistema del SO que se encarga de gestionar un Page Fault se llama Page-Fault Handler.

Para atender a un Page Fault, el handler debe saber dónde está ubicada la página en disco para poder moverla a memoria. Una forma de hacer esto es usar algunos bits que no estén en uso (como los del PFN) en la entrada específica de la tabla de paginación para guardar la ubicación de la página en disco. Mientras se esté recuperando la página del disco, el proceso se bloqueará para que el sistema pueda antender a otros procesos.

Proceso de un Page Fault

#

Antes de continuar, hay que tener claro que, como decía la nota “Seguimos en LDE”, las traducciones a memoria las realiza el hardware sin despertar al SO, a no ser que se lance un fault o una excepción.

Dicho esto, si asumimos que las comprobaciones y traducciones las hace el hardware (de forma cableada en la CPU), y únicamente el Page-Fault Handler es código real de la CPU, el proceso quedaría así (sacado de OSTEP):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// PSEUDOCÓDIGO equivalente a lo que hace el hardware de forma cableada.
// Cuando un proceso intenta acceder a una dirección de memoria, pasa esto.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT  // Se saca la VPN de la dirección virtual
(Success, TlbEntry) = TLB_Lookup(VPN)       // Se comprueba si está en el TLB

// TLB Hit (Está en el TLB)
if (Success == True) 
    // Se tienen permisos para acceder a la página?
    if (CanAccess(TlbEntry.ProtectBits) == True) // Sí. Se calcula la @ física y se accede.
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT) // No. Se produce fault y el SO interviene.

// TLB Miss (NO está en el TLB, hay que acceder a la tabla de paginación)
else 
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    // El programa puede acceder a la memoria a la que quiere acceder?
    if (PTE.Valid == False)
        RaiseException(SEGMENTATION_FAULT) // No: Se lanza SegFault, interviene el SO.
    else // Sí: Se siguen comprobando cosas.
        if (CanAccess(PTE.ProtectBits) == False)
            RaiseException(PROTECTION_FAULT)
        else if (PTE.Present == True)
            // Si la página está en memoria, se guarda en el TLB y se reintenta el acceso.
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()
        else if (PTE.Present == False)
            // Si la página NO está en memoria, se produce un PAGE_FAULT. El SO interviene.
            // Aquí se llama al Page-Fault Handler, que SÍ ES CÓDIGO DEL SO.
            RaiseException(PAGE_FAULT)

En el caso en el que se llega hasta RaiseException(PAGE_FAULT), el SO toma el control y se inicia el page-fault handler, algo así (también de OSTEP):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// PAGE FAULT HANDLER. Esto sí es código que el desarrollador del SO ha tenido 
// que programar.

PFN = FindFreePhysicalPage();  // Se busca una página libre en memoria
if (PFN == -1){                // Si no se encuentra ninguna:
    PFN = EvictPage();         // Se llama a un algoritmo de reemplazamiento
}                              // (Todavía no se han visto estos algoritmos)

DiskRead(PTE.DiskAddr, PFN);   // sleep (wait for I/O)
PTE.present = True;            // Actualizar tabla de paginación
PTE.PFN = PFN;                 // (present/translation)
RetryInstruction();            // Se reintenta la instrucción, se vuelve al código anterior.

Swapping Proactivo

#

Podría parecer que no tiene mucho sentido swappear datos al disco si tenemos espacio en RAM para mantenerlos, pues esto supondría un coste innecesario en velocidad, y que la idea por tanto sería recurrir al swapping solo cuando la memoria esté llena.

Sin embargo, si esperamos a que la memoria esté al 100%, estamos duplicando el tiempo de penalización de un Page Fault, porque obligamos al sistema a escribir una página en disco para sacarla de memoria (EvictPage()), y a leer otra swappeada del disco para meterla en el hueco liberado (DiskRead()). Además, hay veces que el propio SO necesita asignar memoria de emergencia (p.ej al recibir paquetes de red) y no puede permitirse esperar a que termine un swap.

Para evitar estos casos, los Sistemas Operativos mantienen un colchón mínimo de memoria libre. No esperan hasta alcanzar el 100%, sino que empiezan a frenar antes definiendo dos límites conocidos como Watermarks:

• Low Watermark (LW): Si la cantidad de páginas libres cae por debajo de LW, se ejecuta un hilo encargado de liberar memoria swappeando páginas.
• High Watermark (HW): Ese hilo hace su trabajo hasta que haya un mínimo de HW páginas libres.

Ese hilo recibe el nombre de Swap Daemon o Page Daemon. En Linux modernos puede verse con el nombre de kswapd:

1
2
3
4

$ ps aux | grep kswapd
USER         PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root         140  0.0  0.0      0     0 ?        S    13:54   0:00 [kswapd0]
# El motivo por el que el nombre está entre [] es porque es un hilo del kernel.

Políticas: Qué swappear?

#

Incluso aunque contemos con un daemon encargado de no hacernos llegar al 100% de uso de memoria, puede darse el caso en el que esto suceda. En esa situación, el Page-Fault handler tendrá que hacer uso de EvictPage(), que tendrá que mandar una página al disco para poder traer a memoria la que hemos solicitado. Pero cómo elige cuál de todas las páginas en memoria mandar a disco?

Para hacer los cálculos y decidir objetivamente qué método es mejor, vamos a considerar que la memoria RAM es una memoria caché, y que por tanto nuestro objetivo va a ser conseguir el menor número de cache misses (el número de veces que la página a buscar está en disco y no en memoria). Para los cálculos nos olvidamos del TLB.

Una vez conozcamos el número de Cache Hits y Misses, podremos definir el Tiempo Medio de Acceso a Memoria (AMAT):

• \(T_M\) = Costo de acceder a memoria (Cache Hit)
• \(T_D\) = Costo de acceder a disco (Cache Miss)
• \(P_{\text{MISS}}\) = Probabilidad de un Cache Miss. \(P_{\text{MISS}}\in[0,1]\)

Optimal Policy - Ideal

#

Para poder ver cómo de bien funciona nuestra política de reemplazamiento, vendría bien una política ideal que nos marque el camino. Esta política recibe el nombre de Optimal Policy, y su algoritmo es sencillo:

Cuando haya que mover una página de memoria a disco, se mueve a la que más tarde en el futuro se va a acceder.

Aunque tenemos el pequeño problema de que seguimos sin poder predecir el futuro, este modelo puede servirnos para ejecutarlo sobre una muestra de procesos una vez hayan terminado y ver cuál sería el \(\text{AMAT}\) óptimo. Luego compararíamos el \(\text{AMAT}\) de nuestra política con el de Optimal y veríamos cuánto margen de mejora hay.

Ejemplo con 4 páginas y un caché con 3 espacios. Notar que el caché empieza vacío:

Si calculamos la tasa de Cache Misses:

También podemos calcularla ignorando el primer Miss de cada página, pues es algo inevitable para cualquier algoritmo. Estos primeros misses reciben el nombre de Compulsory Misses (Obligatorios).

Y podemos definir la tasa de Hits como \(1-P_{\text{MISS}}\), que aquí quedarían como \(54.\overline{54}\space\%\) y \(85.71\space\%\), respectivamente.

Con estas medidas, podríamos definir una tasa de Hits objetivo para nuestra política de reemplazamiento, y ver si merece la pena seguir intentando mejorarla, o si eso la haría innecesariamente compleja para una mejora imperceptible.

FIFO Policy

#

La más sencilla de diseñar e implementar. La primera página en entrar a memoria será la primera en irse a disco cuando el SO necesite reemplazar una por otra.

Esta política tiene el problema de que no le importa si a una página se ha accedido mucho más que a otras, por lo que puede ser muy ineficiente, dado que no tiene en cuenta la “importancia” de cada página.

Random Policy

#

Otra también sencilla de diseñar e implementar. Cuando haya que mover una página a memoria, esta se elige al azar.

El problema es evidente. Unas veces puede conseguir una tasa de hits tan alta como Optimal, y otras veces puede conseguir la menor tasa de hits posible.

LRU & LFU Policies

#

De forma similar a como hacía MLFQ para determinar qué proceso traer al frente, una política óptima puede usar el pasado para intentar conseguir el mejor futuro.

Para tomar la decisión, el handler puede llevar la cuenta de dos cosas:

• A qué página se ha accedido más veces desde el inicio.
• A qué páginas se ha accedido más recientemente.

La política LRU (Least Recently Used) elige la página en función de cuánto hace que se ha accedido a ella. La política LFU (Least Frequently Used) la elige en función de las veces a las que se ha accedido en total a dicha página en todo el período de tiempo.

Evidentemente, estas políticas aprovechan las localidades temporal y espacial en los accesos a memoria. Si dichos accesos son completamente aleatorios, en una muestra suficientemente grande todas las políticas (FIFO, Random, LRU, LFU) lo harán igual de bien (o mal), pero prácticamente siempre por debajo de Optimal.

Problemas de LRU y LFU

#

De todas formas, igual que MLFQ, estos son modelos teóricos, aunque tienen la diferencia de que no pueden implementarse directamente de forma viable.

Esto es porque, para implementar, p.ej, LRU, el sistema debe hacer esto:

• Llevar la cuenta de cuándo se ha accedido a cada página.
• Con cada acceso a memoria, actualizar dicha variable.
• Cuando haya que swappear, buscar la página cuya variable de tiempo sea menor.

Para unas pocas páginas no es gran cosa, pero si tenemos 4GB de RAM y páginas de 4kB, tendremos que buscar entre un millón de páginas para ver a qué página hace más rato que se ha accedido. Esto es inviable, y más todavía en sistemas modernos con muchas más páginas.

La solución a esto: una aproximación.

Aproximación de LRU: Clock Algorithm

#

Esto requiere cierto apoyo del hardware en forma de un bit denominado Use Bit o Reference Bit. Las políticas que usan la mayoría de sistemas modernos (al menos Linux) se basan en esta.

Hay un Use Bit por cada página del sistema. Estos bits se guardan en algún sitio, p.ej, en un array. Cuando se accede (R/W) a una página, el hardware pone su Use Bit a 1. El hardware nunca lo pone a 0, eso es trabajo del SO.

El algoritmo usado para aprovechar este bit es el clock algorithm:

• Imagina todas las páginas de un proceso puestas en una circunferencia. Cada una tiene el Use Bit a 1 o a 0.
• Cuando hay que reemplazar una página, aparece una manecilla de reloj apuntando a una página cualquiera \(P\)
• Si esa página tiene el Use Bit a 0, es porque no se ha usado en un rato, así que se elige para ser swappeada. Si no, simplemente se pone dicho bit a 0 y se va a por la página \(P+1\)
• Este ciclo se repite hasta que se encuentre una página con el Use Bit a 0 de primeras. Esto significará que o bien la página lleva sin ser usada un rato, o se ha dado la vuelta completa a la circunferencia.

Consideración: Dirty Bit

#

Cuando hay una página swappeada en disco y un proceso accede a dicha página, el SO la copia a RAM, pero no borra ni invalida la copia que estaba en el disco. Ahora la página está tanto en RAM como en disco, actuando como como respaldo.

El problema es que ahora hay que tener en cuenta si lo que hay en disco es coherente con lo que hay en memoria, porque esto segundo puede haber sido modificado posteriormente. Para ello, se mantiene un Dirty Bit en la página swappeada que indique si la página no ha sido modificada en memoria (dirty=0) o si ha sido modificada (dirty=1).

Al mantener esa copia en disco, se abren dos escenarios distintos cuando el SO necesita expulsar esa página de la RAM por falta de espacio:

• Dirty=0: Los datos en RAM y disco son los mismos. El coste de expulsar esta página de la RAM es nulo porque los datos ya están guardados en disco al no haber sido modificados.
• Dirty=1: Los datos en RAM y disco NO son los mismos. El coste de expulsar esta página de la RAM es muy alto porque hay que guardar los datos de nuevo antes de swappearla, y por tanto hace falta una operación de I/O.

Así que el algoritmo ahora se modifica, con el añadido de que se prefiere expulsar páginas con el Dirty Bit a 0 (no hay que guardarlas antes de swappearlas) antes que páginas con el Dirty Bit a 1 (pueden swappearse directamente).