algorithm
Algorithmes en ligne

Remarques

Paging (mise en cache en ligne)

Préface

Au lieu de commencer par une définition formelle, l’objectif est d’aborder ces sujets via une rangée d’exemples, en introduisant des définitions en cours de route. La section remarque La théorie consistera en toutes les définitions, théorèmes et propositions pour vous donner toutes les informations nécessaires pour rechercher plus rapidement des aspects spécifiques.

Les sources de la section des remarques comprennent le matériel de base utilisé pour ce sujet et des informations supplémentaires pour une lecture ultérieure. De plus, vous trouverez les codes sources complets pour les exemples. Veuillez faire attention que pour rendre le code source des exemples plus lisible et plus court, il évite des choses comme la gestion des erreurs, etc. Il transmet également certaines fonctionnalités de langage spécifiques qui masqueraient la clarté de l'exemple

Pagination

Le problème de pagination provient de la limitation des espaces finis. Supposons que notre cache C a k pages. Nous souhaitons maintenant traiter une séquence de m pages qui doivent avoir été placées dans le cache avant d'être traitées. Bien sûr, si m<=k nous mettons simplement tous les éléments dans le cache et cela fonctionnera, mais habituellement, c'est m>>k .

Nous disons qu'une requête est un succès de cache , lorsque la page est déjà en cache, sinon, elle est appelée un échec de cache . Dans ce cas, nous devons amener la page demandée dans le cache et en expulser un autre, à condition que le cache soit plein. Le but est un calendrier d'expulsion qui minimise le nombre d'expulsions .

Il existe de nombreuses stratégies pour résoudre ce problème.

1. Premier entré, premier sorti (FIFO) : la plus ancienne page est expulsée
2. Last in, first out (LIFO) : la page la plus récente est expulsée
3. Moins utilisé récemment (LRU) : page d'éviction dont l'accès le plus récent était le plus ancien
4. Moins utilisé (LFU) : page d'éviction la moins fréquemment demandée
5. Distance la plus longue (LFD) : expulse la page dans le cache qui n'est demandée que plus tard.
6. Flush lorsqu'il est plein (FWF) : efface le cache complet dès qu'un échec de cache est survenu

Il y a deux façons d'aborder ce problème:

1. hors ligne : la séquence des demandes de pages est connue à l'avance
2. en ligne : la séquence des demandes de pages n'est pas connue à l'avance

Approche hors ligne

Pour la première approche, examinez le sujet Applications de la technique gourmande . C'est la troisième fois. Exemple La mise en cache hors ligne considère les cinq premières stratégies ci-dessus et vous donne un bon point d'entrée pour les éléments suivants.

L'exemple de programme a été étendu à la stratégie 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;
        }
    }
};

Le code source complet est disponible ici . Si nous réutilisons l'exemple du sujet, nous obtenons la sortie suivante:

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

Même si LFD est optimal, FWF a moins de caches manquants. Mais l'objectif principal était de minimiser le nombre d'expulsions et, pour la FWF, cinq manquants signifiaient 15 expulsions, ce qui en fait le choix le plus pauvre pour cet exemple.

Approche en ligne

Nous voulons maintenant aborder le problème en ligne de la pagination. Mais nous devons d'abord comprendre comment le faire. De toute évidence, un algorithme en ligne ne peut pas être meilleur que l'algorithme hors ligne optimal. Mais à quel point est-ce pire? Nous avons besoin de définitions formelles pour répondre à cette question:

Définition 1.1: Un problème d'optimisation of consiste en un ensemble d' instances Σ _Π . Pour tous les cas _{σ∈Σ Π} il existe un ensemble de solutions _{Ζ σ} et une fonction objective f _{σ: Ζ σ → ℜ ≥0} qui attribue apositive une valeur réelle à chaque solution.
Nous disons que OPT (σ) est la valeur d'une solution optimale, A (σ) est la solution d'un algorithme A pour le problème Π et w _A (σ) = f _σ (A (σ)) sa valeur.

Définition 1.2: Un algorithme en ligne A pour un problème de minimisation Π a un rapport compétitif de r ≥ 1 s'il existe une constante τ∈ℜ avec

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

pour toutes les instances σ∈Σ _Π . A s'appelle un algorithme en ligne r-concurrentiel . Est même

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

pour toutes les instances σ∈Σ _Π alors A est appelé un algorithme en ligne strictement compétitif .

La question est donc de savoir si notre algorithme en ligne est compétitif par rapport à un algorithme hors ligne optimal. Dans leur célèbre livre, Allan Borodin et Ran El-Yaniv ont utilisé un autre scénario pour décrire la situation de paging en ligne:

Il y a un adversaire malin qui connaît votre algorithme et l'algorithme hors ligne optimal. À chaque étape, il essaie de demander une page qui est la pire pour vous et simultanément la meilleure pour l’algorithme hors ligne. Le facteur de compétitivité de votre algorithme est le facteur déterminant dans la performance de votre algorithme par rapport à l'algorithme hors ligne optimal de l'adversaire. Si vous voulez essayer d'être l'adversaire, vous pouvez essayer le jeu de l' adversaire (essayez de battre les stratégies de pagination).

Algorithmes de marquage

Au lieu d'analyser chaque algorithme séparément, examinons une famille d'algorithmes en ligne spéciale pour le problème de pagination appelé algorithmes de marquage .

Soit σ = (σ ₁ , ..., σ _p ) une instance pour notre problème et k notre taille de cache, que σ peut être divisé en phases:

• La phase 1 est la sous-séquence maximale de σ du début jusqu'à ce que k différentes pages soient demandées.
• La phase i ≥ 2 est la sous-séquence maximale de σ à partir de la fin du passage i-1 jusqu'à ce que k différentes pages soient demandées.

Par exemple avec k = 3:

Un algorithme de marquage (implicite ou explicite) maintient si une page est marquée ou non. Au début de chaque phase, toutes les pages ne sont pas marquées. Est-ce une page demandée pendant une phase qui est marquée. Un algorithme est un algorithme de marquage s'il n'est jamais expulsé d'une page marquée du cache. Cela signifie que les pages utilisées pendant une phase ne seront pas expulsées.

Proposition 1.3: LRU et FWF sont des algorithmes de marquage.

Preuve: Au début de chaque phase (sauf pour la première), FWF a un cache manquant et a effacé le cache. cela signifie que nous avons k pages vides. Dans chaque phase, k maximum de pages différentes sont demandées, il y aura donc maintenant une expulsion pendant la phase. Donc, FWF est un algorithme de marquage.
Supposons que LRU ne soit pas un algorithme de marquage. Ensuite, il y a une instance σ où LRU une page marquée x dans la phase j'ai expulsé. Soit σ _t la requête dans la phase i où x est expulsé. Puisque x est marqué, il doit y avoir une requête antérieure σ _{t *} pour x dans la même phase, donc t * <t. Après t * x est la page la plus récente des caches, donc pour être expulsé à la séquence σ _{t * + 1} , ..., σ _t doit demander au moins k à partir de x pages différentes. Cela implique que la phase i a demandé au moins k + 1 pages différentes, ce qui est en contradiction avec la définition de la phase. Donc, LRU doit être un algorithme de marquage.

Proposition 1.4: Chaque algorithme de marquage est strictement k-compétitif .

Preuve: Soit σ une instance pour le problème de pagination et l le nombre de phases pour σ. Is l = 1 alors tout algorithme de marquage est optimal et l'algorithme hors ligne optimal ne peut être meilleur.
Nous supposons que l ≥ 2. Le coût de chaque algorithme de marquage, par exemple, σ est limité par le haut avec l ⋅ k car dans chaque phase un algorithme de marquage ne peut pas expulser plus de k pages sans expulser une page marquée.
Nous essayons maintenant de montrer que l’algorithme hors ligne optimal expulse au moins k + l-2 pages pour σ, k dans la première phase et au moins une pour chaque phase suivante, à l’exception de la dernière. Pour preuve, définissons l-2 sous-séquences disjointes de σ. La sous-séquence i ∈ {1, ..., l-2} commence à la deuxième position de la phase i + 1 et se termine à la première position de la phase i + 2.
Soit x la première page de la phase i + 1. Au début de la sous-séquence, il y a page x et au plus k-1 pages différentes dans le cache optimal des algorithmes hors ligne. Dans la sous-séquence, la requête de page k est différente de x, donc l'algorithme hors ligne optimal doit expulser au moins une page pour chaque sous-séquence. Comme à la phase 1, le cache est toujours vide, l’algorithme hors ligne optimal provoque des expulsions au cours de la première phase. Cela montre que

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

Corollaire 1.5: LRU et FWF sont strictement k-compétitives .

Exercice: Montrer que le FIFO n’est pas un algorithme de marquage, mais strictement k-compétitif .

N'y a-t-il pas de constante pour laquelle un algorithme en ligne A est concurrentiel, nous appelons A non compétitif

Proposition 1.6: LFU et LIFO ne sont pas compétitifs .

Preuve: Soit l ≥ 2 une constante, k ≥ 2 la taille du cache. Les différentes pages de cache sont nubered 1, ..., k + 1. Nous regardons la séquence suivante:

La première page 1 est demandée 1 fois plus que la page 2 et ainsi de suite. À la fin, il y a (l-1) requêtes alternées pour la page k et k + 1.
LFU et LIFO remplissent leur cache avec les pages 1-k. Lorsque la page k + 1 est demandée, la page k est expulsée et vice versa. Cela signifie que chaque requête de sous-séquence (k, k + 1) ^l-1 expulse une page. De plus, leur cache est k-1 pour la première fois en utilisant les pages 1 (k-1). Ainsi, LFU et LIFO expulsent les pages exactes k-1 + 2 (l-1).
Maintenant, il faut montrer que pour toute constante τ∈ℜ et toute constante r ≤ 1, il existe un l pour que

qui est égal à

Pour satisfaire cette inégalité, il suffit de choisir une taille suffisante. Donc LFU et LIFO ne sont pas compétitifs.

Proposition 1.7: Il n'existe pas d' algorithme en ligne déterministe r-compétitif pour la pagination avec r <k .

La preuve de cette dernière proposition est plutôt longue et basée sur l'affirmation que LFD est un algorithme hors ligne optimal. Le lecteur intéressé peut consulter le livre de Borodin et El-Yaniv (voir les sources ci-dessous).

La question est de savoir si nous pourrions faire mieux. Pour cela, nous devons laisser l’approche déterministe derrière nous et commencer à randomiser notre algorithme. De toute évidence, il est beaucoup plus difficile pour l'adversaire de punir votre algorithme s'il est randomisé.

La pagination aléatoire sera discutée dans l'un des prochains exemples ...