algorithm
Algoritmos en línea

Observaciones

Paginación (almacenamiento en caché en línea)

Prefacio

En lugar de comenzar con una definición formal, el objetivo es abordar este tema a través de una fila de ejemplos, introduciendo definiciones en el camino. La sección de comentarios La teoría consistirá en todas las definiciones, teoremas y proposiciones para proporcionarle toda la información para buscar más rápidamente aspectos específicos.

Las fuentes de la sección de comentarios consisten en el material de base utilizado para este tema e información adicional para lecturas adicionales. Además, encontrará los códigos fuente completos para los ejemplos allí. Preste atención a que para que el código fuente de los ejemplos sea más legible y más corto, se abstenga de cosas como el manejo de errores, etc. También transmite algunas características específicas del lenguaje que podrían ocultar la claridad del ejemplo, como el uso extensivo de bibliotecas avanzadas, etc.

Paginacion

El problema de la paginación surge de la limitación del espacio finito. Supongamos que nuestro caché C tiene k páginas. Ahora queremos procesar una secuencia de m solicitudes de página que se deben haber colocado en el caché antes de que se procesen. Por supuesto, si m<=k , simplemente colocamos todos los elementos en el caché y funcionará, pero generalmente es m>>k .

Decimos que una solicitud es un acierto de caché , cuando la página ya está en caché, de lo contrario, se denomina falta de caché . En ese caso, debemos traer la página solicitada al caché y desalojar a otro, suponiendo que el caché esté lleno. El objetivo es un programa de desalojo que minimiza el número de desalojos .

Existen numerosas estrategias para este problema, veamos algunas:

1. Primero en entrar, primero en salir (FIFO) : la página más antigua se desaloja
2. Último en entrar, primero en salir (LIFO) : la página más nueva se desaloja
3. Usado menos recientemente (LRU) : página de desalojo cuyo acceso más reciente fue el más antiguo
4. Uso menos frecuente (LFU) : página de desalojo solicitada con menor frecuencia
5. Distancia de avance más larga (LFD) : Desaloja la página en el caché que no se solicita hasta el momento más lejano.
6. Vaciar cuando esté lleno (FWF) : borre la memoria caché completa tan pronto como se produzca una falla de caché

Hay dos formas de abordar este problema:

1. fuera de línea : la secuencia de solicitudes de página se conoce de antemano
2. en línea : la secuencia de solicitudes de página no se conoce de antemano

Enfoque sin conexión

Para el primer enfoque mira el tema Aplicaciones de la técnica codiciosa . Es el tercer ejemplo. El almacenamiento en línea sin conexión considera las primeras cinco estrategias desde arriba y le brinda un buen punto de entrada para lo siguiente.

El programa de ejemplo se amplió con la estrategia FWF :

class FWF : public Strategy {
public:
    FWF() : Strategy("FWF")
    {
    }

    int apply(int requestIndex) override
    {
        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            // after first empty page all others have to be empty
            else if(cache[i] == emptyPage)
                return i;
        }

        // no free pages
        return 0;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {

        // no pages free -> miss -> clear cache
        if(cacheMiss && cachePos == 0)
        {
            for(int i = 1; i < cacheSize; ++i)
                cache[i] = emptyPage;
        }
    }
};

El código fuente completo está disponible aquí . Si reutilizamos el ejemplo del tema, obtenemos el siguiente resultado:

Strategy: FWF

Cache initial: (a,b,c)

Request cache 0 cache 1 cache 2 cache miss
  a       a       b       c
  a       a       b       c
  d       d       X       X       x
  e       d       e       X
  b       d       e       b
  b       d       e       b
  a       a       X       X       x
  c       a       c       X
  f       a       c       f
  d       d       X       X       x
  e       d       e       X
  a       d       e       a
  f       f       X       X       x
  b       f       b       X
  e       f       b       e
  c       c       X       X       x

Total cache misses: 5

Aunque LFD es óptimo, FWF tiene menos errores de caché. Pero el objetivo principal era minimizar el número de desalojos y para FWF cinco fallos significan 15 desalojos, lo que la convierte en la opción más pobre para este ejemplo.

Enfoque en línea

Ahora queremos abordar el problema en línea de la paginación. Pero primero necesitamos un entendimiento de cómo hacerlo. Obviamente, un algoritmo en línea no puede ser mejor que el algoritmo sin conexión óptimo. ¿Pero cuanto peor es? Necesitamos definiciones formales para responder a esa pregunta:

Definición 1.1: Un problema de optimización Π consiste en un conjunto de instancias Σ _¸. Para cada instancia σ∈Σ _Π hay un conjunto Ζ _σ de soluciones y una función objetivo f _σ : Ζ _σ → ℜ _≥0 que asigna un valor real _positivo a cada solución.
Decimos que OPT (σ) es el valor de una solución óptima, A (σ) es la solución de un algoritmo A para el problema Π y w _A (σ) = f _σ (A (σ)) su valor.

Definición 1.2: Un algoritmo en línea A para un problema de minimización Π tiene una relación competitiva de r ≥ 1 si hay una constante τ∈ℜ con

w _A (σ) = f _σ (A (σ)) ≤ r ⋅ OPT (σ) + τ

para todas las instancias σ∈Σ _Π . A se llama un algoritmo en línea competitivo . Incluso

w _A (σ) ≤ r ⋅ OPT (σ)

para todas las instancias σ∈Σ _Π, entonces A se denomina algoritmo en línea estrictamente competitivo .

Entonces, la pregunta es cuán competitivo es nuestro algoritmo en línea en comparación con un algoritmo sin conexión óptimo. En su famoso libro Allan Borodin y Ran El-Yaniv usaron otro escenario para describir la situación de la paginación en línea:

Hay un adversario malvado que conoce su algoritmo y el algoritmo óptimo fuera de línea. En cada paso, intenta solicitar una página que sea peor para usted y, al mismo tiempo, mejor para el algoritmo sin conexión. el factor competitivo de su algoritmo es el factor de qué tan mal lo hizo su algoritmo contra el algoritmo fuera de línea óptimo del adversario. Si quieres tratar de ser el adversario, puedes probar el Juego Adversario (intenta superar las estrategias de paginación).

Algoritmos de marcado

En lugar de analizar cada algoritmo por separado, veamos una familia especial de algoritmos en línea para el problema de paginación llamado algoritmos de marcado .

Deje que σ = (σ ₁ , ..., σ _p ) sea una instancia de nuestro problema y k nuestro tamaño de caché, ya que σ se puede dividir en fases:

• La fase 1 es la subsecuencia máxima de σ desde el inicio hasta el máximo k se solicitan diferentes páginas
• La fase i ≥ 2 es la subsecuencia máxima de σ desde el final del pase i-1 hasta que se solicitan k páginas máximas diferentes.

Por ejemplo con k = 3:

Un algoritmo de marcado (implícito o explícito) mantiene si una página está marcada o no. Al comienzo de cada fase se encuentran todas las páginas sin marcar. Es una página solicitada durante una fase que se marca. Un algoritmo es un algoritmo de marcado si nunca desaloja una página marcada de la caché. Eso significa que las páginas que se utilizan durante una fase no serán desalojadas.

Proposición 1.3: LRU y FWF son algoritmo de marcado.

Prueba: al comienzo de cada fase (a excepción de la primera), FWF pierde el caché y lo borra. Eso significa que tenemos k páginas vacías. En cada fase se solicitan k páginas máximas diferentes, por lo que ahora habrá desalojo durante la fase. Así que FWF es un algoritmo de marcado.
Supongamos que LRU no es un algoritmo de marcado. Luego hay una instancia σ donde LRU una página marcada x en la fase i desalojada. Sea σ _t la solicitud en la fase i donde se desaloja x. Dado que x está marcado, debe haber una solicitud anterior σ _{t *} para x en la misma fase, entonces t * <t. Después de que t * x es la página más nueva de las memorias caché, para que se desaloje en t la secuencia σ _{t * + 1} , ..., σ _t debe solicitar al menos k de x páginas diferentes. Eso implica que la fase i ha solicitado al menos k + 1 páginas diferentes, lo que es contradictorio con la definición de la fase. Así que LRU tiene que ser un algoritmo de marcado.

Proposición 1.4: Cada algoritmo de marcado es estrictamente competitivo .

Prueba: Sea σ una instancia para el problema de paginación y l el número de fases para σ. Es l = 1, entonces, cada algoritmo de marcado es óptimo y el algoritmo fuera de línea óptimo no puede ser mejor.
Suponemos que l ≥ 2. el costo de cada algoritmo de marcado, por ejemplo, σ está limitado desde arriba con l ⋅ k porque en cada fase un algoritmo de marcado no puede expulsar más de k páginas sin desalojar una página marcada.
Ahora intentamos mostrar que el algoritmo fuera de línea óptimo desaloja al menos k + l-2 páginas para σ, k en la primera fase y al menos una para cada fase siguiente, excepto la última. Para la prueba vamos a definir l-2 subsecuencias disyuntivas de σ. La subsecuencia i ∈ {1, ..., l-2} comienza en la segunda posición de la fase i + 1 y termina con la primera posición de la fase i + 2.
Sea x la primera página de la fase i + 1. Al comienzo de la subsecuencia i hay una página x y, como máximo, k-1 páginas diferentes en el caché de algoritmos fuera de línea óptimo. En la subsecuencia, la solicitud de la página k es diferente de x, por lo que el algoritmo fuera de línea óptimo debe desalojar al menos una página para cada subsecuencia. Dado que en el inicio de la fase 1, el caché aún está vacío, el algoritmo óptimo fuera de línea causa k desalojos durante la primera fase. Eso demuestra que

w _A (σ) ≤ l⋅k ≤ (k + l-2) k ≤ OPT (σ) ⋅ k

Corolario 1.5: LRU y FWF son estrictamente competitivos .

Ejercicio: Mostrar que FIFO no es un algoritmo de marcado, sino estrictamente k-competitivo .

¿No hay una r constante para la cual un algoritmo en línea A es r-competitivo, llamamos A no competitivo?

Proposición 1.6: LFU y LIFO no son competitivos .

Prueba: Deje l ≥ 2 una constante, k ≥ 2 el tamaño del caché. Las diferentes páginas de caché están nubladas 1, ..., k + 1. Nos fijamos en la siguiente secuencia:

La primera página 1 se solicita más veces que la página 2, y por lo tanto una. Al final, hay (l-1) solicitudes alternas para las páginas k y k + 1.
LFU y LIFO llenan su caché con las páginas 1-k. Cuando se solicita la página k + 1, la página k se desaloja y viceversa. Eso significa que cada solicitud de subsecuencia (k, k + 1) ^l-1 desaloja una página. Además, su caché de k-1 se pierde por primera vez en el uso de las páginas 1- (k-1). Así que LFU y LIFO desalojan páginas exactas k-1 + 2 (l-1).
Ahora debemos mostrar que para cada constante τ∈ℜ y cada constante r ≤ 1 existe una l para que

que es igual a

Para satisfacer esta desigualdad solo tienes que elegir lo suficientemente grande. Entonces, LFU y LIFO no son competitivos.

Proposición 1.7: No hay un algoritmo en línea determinista r-competetive para paginar con r <k .

La prueba de esta última proposición es bastante larga y se basa en la afirmación de que LFD es un algoritmo sin conexión óptimo. El lector interesado puede buscarlo en el libro de Borodin y El-Yaniv (consulte las fuentes a continuación).

La pregunta es si podríamos hacerlo mejor. Para eso, tenemos que dejar atrás el enfoque determinista y comenzar a aleatorizar nuestro algoritmo. Claramente, es mucho más difícil para el adversario castigar tu algoritmo si es aleatorio.

La paginación aleatoria se tratará en uno de los siguientes ejemplos ...