algorithm
Algoritmi online

Osservazioni

Paging (cache online)

Prefazione

Invece di iniziare con una definizione formale, l'obiettivo è quello di affrontare questi argomenti attraverso una serie di esempi, introducendo definizioni lungo il percorso. La teoria della sezione di osservazione consisterà in tutte le definizioni, i teoremi e le proposizioni per darti tutte le informazioni per cercare più velocemente aspetti specifici.

Le origini delle sezioni di commento sono costituite dal materiale di base utilizzato per questo argomento e da ulteriori informazioni per ulteriori letture. Inoltre troverai i codici sorgente completi per gli esempi presenti. Si prega di fare attenzione che per rendere il codice sorgente degli esempi più leggibile e più breve si astiene da cose come la gestione degli errori ecc. Passa anche alcune caratteristiche linguistiche specifiche che oscurerebbero la chiarezza dell'esempio come l'uso estensivo di librerie avanzate ecc.

paging

Il problema del paging deriva dalla limitazione dello spazio finito. Supponiamo che la nostra cache C abbia pagine k . Ora vogliamo elaborare una sequenza di richieste di pagine m che devono essere state inserite nella cache prima di essere elaborate. Ovviamente se m<=k allora inseriamo tutti gli elementi nella cache e funzionerà, ma di solito è m>>k .

Diciamo che una richiesta è un colpo di cache , quando la pagina è già in cache, altrimenti è chiamata cache miss . In tal caso, dobbiamo portare la pagina richiesta nella cache ed eliminarne un'altra, supponendo che la cache sia piena. L'obiettivo è un programma di sfratto che riduce al minimo il numero di sfratti .

Esistono numerose strategie per questo problema, diamo un'occhiata ad alcuni:

1. First in, first out (FIFO) : la pagina più vecchia viene sfrattata
2. Last in, first out (LIFO) : la pagina più recente viene sfrattata
3. Meno recente utilizzato (LRU) : pagina Evict il cui accesso più recente è stato il più recente
4. Meno frequentemente usato (LFU) : Evita la pagina che è stata richiesta meno frequentemente
5. Distanza di inoltro più lunga (LFD) : Evita la pagina nella cache che non è richiesta fino al più lontano in futuro.
6. Flush a pieno (FWF) : svuota la cache completa non appena si verifica un errore di cache

Ci sono due modi per affrontare questo problema:

1. offline : la sequenza di richieste di pagine è conosciuta in anticipo
2. online : la sequenza di richieste di pagine non è nota in anticipo

Approccio offline

Per il primo approccio guarda il tema Applicazioni della tecnica Greedy . È terzo Esempio Il caching offline considera le prime cinque strategie dall'alto e offre un buon punto di ingresso per quanto segue.

Il programma di esempio è stato esteso con la strategia 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;
        }
    }
};

Il codice sorgente completo è disponibile qui . Se riutilizziamo l'esempio dall'argomento, otteniamo il seguente risultato:

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

Anche se LFD è ottimale, FWF ha meno errori di cache. Ma l'obiettivo principale era quello di ridurre al minimo il numero di sfratti e per cinque miss FWF si intendono 15 sfratti, il che rende la scelta più povera per questo esempio.

Approccio online

Ora vogliamo affrontare il problema online del paging. Ma prima dobbiamo capire come farlo. Ovviamente un algoritmo online non può essere migliore dell'algoritmo offline ottimale. Ma quanto peggio è? Abbiamo bisogno di definizioni formali per rispondere a questa domanda:

Definizione 1.1: Un problema di ottimizzazione Π consiste in un insieme di istanze Σ _Π . Per ogni istanza σ∈Σ _Π esiste un insieme Ζ _σ di soluzioni e una funzione obiettivo f _σ : Ζ _σ → ℜ _≥0 che assegna un valore reale apositivo a ogni soluzione.
Diciamo che OPT (σ) è il valore di una soluzione ottimale, A (σ) è la soluzione di un Algoritmo A per il problema Π e w _A (σ) = f _σ (A (σ)) il suo valore.

Definizione 1.2: Un algoritmo online A per un problema di minimizzazione Π ha un rapporto competitivo di r ≥ 1 se esiste una costante τ∈ℜ con

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

per tutte le istanze σ∈Σ _Π . A è chiamato algoritmo online r-competitivo . È anche

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

per tutte le istanze σ∈Σ _Π allora A è chiamato un algoritmo online strettamente r-competitivo .

Quindi la domanda è quanto sia competitivo il nostro algoritmo online rispetto a un algoritmo offline ottimale. Nel loro famoso libro Allan Borodin e Ran El-Yaniv hanno usato un altro scenario per descrivere la situazione del cercapersone online:

C'è un avversario malvagio che conosce il tuo algoritmo e l'algoritmo offline ottimale. In ogni passaggio, tenta di richiedere una pagina che è la peggiore per te e allo stesso tempo migliore per l'algoritmo offline. il fattore competitivo dell'algoritmo è il fattore di quanto male ha fatto l'algoritmo rispetto all'algoritmo offline ottimale dell'avversario. Se vuoi provare ad essere l'avversario, puoi provare il gioco dell'avversario (prova a battere le strategie di paging).

Algoritmi di marcatura

Invece di analizzare separatamente ogni algoritmo, esaminiamo una speciale famiglia di algoritmi online per il problema del paging chiamato algoritmi di marcatura .

Sia σ = (σ ₁ , ..., σ _p ) un'istanza per il nostro problema e k la nostra dimensione della cache, che σ può essere diviso in fasi:

• La fase 1 è la sottosequenza massima di σ dall'inizio fino al massimo k vengono richieste diverse pagine
• La fase i ≥ 2 è la sottosequenza massima di σ dalla fine di pase i-1 fino a k massime sono richieste diverse pagine

Ad esempio con k = 3:

Un algoritmo di marcatura (implicitamente o esplicitamente) mantiene se una pagina è marcata o meno. All'inizio di ogni fase tutte le pagine sono deselezionate. Una pagina richiesta durante una fase viene contrassegnata. Un algoritmo è un algoritmo di marcatura se non elabora mai una pagina contrassegnata dalla cache. Ciò significa che le pagine che vengono utilizzate durante una fase non saranno sfrattate.

Proposizione 1.3: LRU e FWF sono algoritmo di marcatura.

Dimostrazione: all'inizio di ogni fase (tranne per il primo) FWF ha un errore di cache e cancella la cache. questo significa che abbiamo k pagine vuote. In ogni fase sono richieste al massimo k pagine diverse, quindi durante la fase ci sarà lo sfratto. Quindi FWF è un algoritmo di marcatura.
Supponiamo che LRU non sia un algoritmo di marcatura. Poi c'è un'istanza σ dove LRU è contrassegnata da una pagina x in fase i sfrattata. Lasciate σ _t la richiesta in fase I in cui viene sfrattato x. Poiché x è marcato deve esserci una richiesta precedente σ _{t *} per x nella stessa fase, quindi t * <t. Dopo t * x è la pagina più recente della cache, quindi per essere sfrattata alla sequenza σ _{t * + 1} , ..., σ _t deve richiedere almeno k da x pagine diverse. Ciò implica che la fase i abbia richiesto almeno k + 1 pagine diverse che sia in contraddizione con la definizione di fase. Quindi LRU deve essere un algoritmo di marcatura.

Proposizione 1.4: Ogni algoritmo di marcatura è strettamente competitivo .

Dimostrazione: Sia σ un'istanza per il problema di paging e l il numero di fasi per σ. È l = 1, quindi ogni algoritmo di marcatura è ottimale e l'algoritmo offline ottimale non può essere migliore.
Assumiamo l ≥ 2. il costo di ogni algoritmo di marcatura, per esempio, σ è delimitato dall'alto con l ⋅ k perché in ogni fase un algoritmo di marcatura non può sfrattare più di k pagine senza sfrattare una pagina marcata.
Ora proviamo a dimostrare che l'algoritmo offline ottimale sfrutta almeno k + l-2 pagine per σ, k nella prima fase e almeno una per ogni fase successiva tranne l'ultima. Per prova si definiscono le sequenze disgiunte di-di l-2. La successiva i ∈ {1, ..., l-2} inizia nella seconda posizione della fase i + 1 e termina con la prima posizione della fase i + 2.
Sia x la prima pagina della fase i + 1. All'inizio della sottosequenza i è presente la pagina x e al massimo k-1 pagine diverse nella cache degli algoritmi offline ottimale. Nella sottosequenza i k sono una richiesta di pagina diversa da x, quindi l'algoritmo offline ottimale deve rimuovere almeno una pagina per ogni sottosequenza. Dal momento che all'inizio della fase 1 la cache è ancora vuota, l'algoritmo offline ottimale causa uno sfratto durante la prima fase. Questo lo dimostra

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

Corollario 1.5: LRU e FWF sono rigorosamente k-competitivi .

Esercitazione: mostra che FIFO non è un algoritmo di marcatura, ma strettamente k-competitivo .

Non esiste una costante per cui un algoritmo online A è r-competitivo, chiamiamo A non competitivo

Proposizione 1.6: LFU e LIFO non sono competitivi .

Dimostrazione: Sia l ≥ 2 una costante, k ≥ 2 la dimensione della cache. Le diverse pagine della cache sono nubered 1, ..., k + 1. Guardiamo la seguente sequenza:

La prima pagina 1 è richiesta l volte di pagina 2 e quindi una. Alla fine, ci sono (l-1) richieste alternate per la pagina k e k + 1.
LFU e LIFO riempiono la cache con le pagine 1-k. Quando la pagina k + 1 è richiesta, la pagina k è sfrattata e viceversa. Ciò significa che ogni richiesta di sottosuccessione (k, k + 1) ^l-1 sfrutta una pagina. Inoltre, si tratta di errori di cache k-1 per il primo utilizzo delle pagine 1- (k-1). Quindi LFU e LIFO rimuovono le pagine esatte di k-1 + 2 (l-1).
Ora dobbiamo mostrare che per ogni costante τ∈ℜ e ogni costante r ≤ 1 esiste una l così che

che è uguale a

Per soddisfare questa disuguaglianza devi solo scegliere un numero sufficiente. Quindi LFU e LIFO non sono competitivi.

Proposizione 1.7: Non esiste un algoritmo deterministico online r-competetive per il paging con r <k .

La dimostrazione di quest'ultima proposizione è piuttosto lunga e basata sull'affermazione che LFD è un algoritmo offline ottimale. Il lettore interessato può cercarlo nel libro di Borodin e El-Yaniv (vedi fonti sotto).

La domanda è se potremmo fare di meglio. Per questo, dobbiamo lasciare l'approccio deterministico alle nostre spalle e iniziare a randomizzare il nostro algoritmo. Chiaramente, è molto più difficile per l'avversario punire il tuo algoritmo se è randomizzato.

Il paging randomizzato sarà discusso in uno dei prossimi esempi ...