algorithm
Online algoritmen

Opmerkingen

Paging (online caching)

Voorwoord

In plaats van te beginnen met een formele definitie, is het doel om dit onderwerp via een reeks voorbeelden te benaderen en onderweg definities te introduceren. De opmerkingsectie Theorie zal bestaan uit alle definities, stellingen en stellingen om u alle informatie te geven om specifieke aspecten sneller op te zoeken.

De bronnen van de opmerkingensectie bestaan uit het basismateriaal dat voor dit onderwerp is gebruikt en aanvullende informatie voor verdere lezing. Bovendien vindt u daar de volledige broncodes voor de voorbeelden. Let op: om de broncode voor de voorbeelden leesbaarder en korter te maken, onthoudt het zich van dingen zoals foutafhandeling enz. Het geeft ook enkele specifieke taalfuncties door die de duidelijkheid van het voorbeeld zouden verdoezelen, zoals uitgebreid gebruik van geavanceerde bibliotheken enz.

paging

Het pagingsprobleem komt voort uit de beperking van eindige ruimte. Laten we aannemen dat onze cache C k pagina's heeft. Nu willen we een reeks m paginaverzoeken verwerken die in de cache moeten zijn geplaatst voordat ze worden verwerkt. Natuurlijk, als m<=k dan stoppen we gewoon alle elementen in de cache en het zal werken, maar meestal is m>>k .

We zeggen dat een verzoek een hit in de cache is, wanneer de pagina al in de cache staat, anders wordt het een cache-misser genoemd . In dat geval moeten we de gevraagde pagina in de cache plaatsen en een andere verwijderen, ervan uitgaande dat de cache vol is. Het doel is een uitzettingsschema dat het aantal uitzettingen minimaliseert .

Er zijn tal van strategieën voor dit probleem, laten we eens kijken naar enkele:

1. First in, first out (FIFO) : de oudste pagina wordt uitgezet
2. Last in, first out (LIFO) : de nieuwste pagina wordt uitgezet
3. Minst recent gebruikte (LRU) : ontruimingspagina waarvan de meest recente toegang het vroegst was
4. Minst frequent gebruikte (LFU) : ontruimingspagina die het minst vaak werd opgevraagd
5. Langste voorwaartse afstand (LFD) : verwijder de pagina in de cache die pas in de toekomst wordt aangevraagd.
6. Flush wanneer vol (FWF) : maak de cache leeg zodra er een cachefout is gebeurd

Er zijn twee manieren om dit probleem aan te pakken:

1. offline : de volgorde van paginaverzoeken is van tevoren bekend
2. online : de volgorde van paginaverzoeken is niet van tevoren bekend

Offline aanpak

Kijk voor de eerste benadering naar het onderwerp Toepassingen van hebzuchtige techniek . Het is het derde voorbeeld Offline Caching beschouwt de eerste vijf strategieën van hierboven en geeft je een goed beginpunt voor het volgende.

Het voorbeeldprogramma werd uitgebreid met de FWF- strategie:

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;
        }
    }
};

De volledige broncode is hier beschikbaar. Als we het voorbeeld uit het onderwerp hergebruiken, krijgen we de volgende uitvoer:

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

Hoewel LFD optimaal is, heeft FWF minder cache-missers. Maar het belangrijkste doel was om het aantal uitzettingen te minimaliseren en voor FWF betekenen vijf missers 15 uitzettingen, wat het de slechtste keuze voor dit voorbeeld maakt.

Online aanpak

Nu willen we het online probleem van paging benaderen. Maar eerst moeten we begrijpen hoe we het moeten doen. Het is duidelijk dat een online algoritme niet beter kan zijn dan het optimale offline algoritme. Maar hoeveel slechter is het? We hebben formele definities nodig om die vraag te beantwoorden:

Definitie 1.1: Een optimalisatieprobleem Π bestaat uit een set instanties Σ _Π . Voor elke instantie σ∈Σ _{Π is} er een set Ζ _σ van oplossingen en een objectieve functie f _σ : Ζ _σ → ℜ _≥0 die een positieve reële waarde toekent aan elke oplossing.
We zeggen dat OPT (σ) de waarde is van een optimale oplossing, A (σ) is de oplossing van een algoritme A voor het probleem Π en w _A (σ) = f _σ (A (σ)) zijn waarde.

Definitie 1.2: Een online algoritme A voor een minimalisatieprobleem Π heeft een competitieve verhouding van r ≥ 1 als er een constante τ∈ℜ is met

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

voor alle instanties σ∈Σ _Π . A wordt een r-competitief online algoritme genoemd. Is zelfs

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

voor alle instanties σ∈Σ _Π wordt A een strikt r-competitief online algoritme genoemd.

De vraag is dus hoe competitief ons online algoritme is in vergelijking met een optimaal offline algoritme. In hun beroemde boek gebruikten Allan Borodin en Ran El-Yaniv een ander scenario om de online paging-situatie te beschrijven:

Er is een kwaadaardige tegenstander die je algoritme en het optimale offline algoritme kent. In elke stap probeert hij een pagina aan te vragen die het slechtst is voor u en tegelijkertijd het beste voor het offline algoritme. de concurrentiefactor van uw algoritme is de factor hoe slecht uw algoritme deed tegen het optimale offline algoritme van de tegenstander. Als je wilt proberen de tegenstander te zijn, kun je het spel Tegenstander proberen (probeer de pagingstrategieën te verslaan).

Algoritmen markeren

Laten we, in plaats van elk algoritme afzonderlijk te analyseren, kijken naar een speciale online algoritmenfamilie voor het pagingsprobleem, genaamd markeringsalgoritmen .

Laat σ = (σ ₁ , ..., σ _p ) een instantie voor ons probleem en k onze cachegrootte, dan kan σ in fasen worden verdeeld:

• Fase 1 is de maximale deelreeks van σ vanaf het begin tot maximaal k verschillende pagina's worden gevraagd
• Fase i ≥ 2 is de maximale deelreeks van σ vanaf het einde van fase i-1 tot maximaal k verschillende pagina's worden gevraagd

Bijvoorbeeld met k = 3:

Een markeringsalgoritme houdt (impliciet of expliciet) vast of een pagina gemarkeerd is of niet. Aan het begin van elke fase zijn alle pagina's niet gemarkeerd. Is een pagina aangevraagd tijdens een fase die wordt gemarkeerd. Een algoritme is een markeringsalgoritme als het nooit een gemarkeerde pagina uit de cache verwijdert. Dat betekent dat pagina's die tijdens een fase worden gebruikt, niet worden uitgezet.

Stelling 1.3: LRU en FWF zijn markering algoritme.

Bewijs: Aan het begin van elke fase (behalve de eerste) heeft FWF een cachefout en wist de cache. dat betekent dat we k lege pagina's hebben. In elke fase worden maximaal k verschillende pagina's gevraagd, dus er zal nu uitzetting zijn tijdens de fase. FWF is dus een markeringsalgoritme.
Laten we aannemen dat LRU geen markeringsalgoritme is. Dan is er een instantie σ waarbij LRU een gemarkeerde pagina x in fase i heeft uitgezet. Laat σ _t verzoek in fase I met X is uitgezet. Aangezien x is gemarkeerd, moet er een eerdere aanvraag σ _{t * zijn} voor x in dezelfde fase, dus t * <t. Na t * x is de caches de nieuwste pagina, dus om op t de reeks σ _{t * + 1 te krijgen} , moet σ _t ten minste k van x verschillende pagina's aanvragen. Dat betekent dat de fase i ten minste k + 1 verschillende pagina's heeft aangevraagd, wat in tegenspraak is met de fasedefinitie. LRU moet dus een markeringsalgoritme zijn.

Stelling 1.4: Elk markeringsalgoritme is strikt k-competitief .

Bewijs: Laat o een exemplaar van de paging probleem en L het aantal fasen σ zijn. Is l = 1 dan is elk markeringsalgoritme optimaal en kan het optimale offline algoritme niet beter zijn.
We nemen aan dat l ≥ 2. de kosten van elk markeringsalgoritme, bijvoorbeeld, σ wordt van bovenaf begrensd met l ⋅ k omdat een markeringsalgoritme in elke fase niet meer dan k pagina's kan verwijderen zonder één gemarkeerde pagina te verwijderen.
Nu proberen we aan te tonen dat het optimale offline algoritme ten minste k + l-2 pagina's uitschakelt voor σ, k in de eerste fase en ten minste één voor elke volgende fase behalve de laatste. Laten we als bewijs l-2 niet-opeenvolgende deelreeksen van σ definiëren. Volgorde i ∈ {1, ..., l-2} begint op de tweede positie van fase i + 1 en eindigt met de eerste positie van fase i + 2.
Laat x de eerste pagina zijn van fase i + 1. Aan het begin van subreeks i is er pagina x en hoogstens k-1 verschillende pagina's in de optimale offline algoritmencache. In de volgorde ben ik een k paginaverzoek anders dan x, dus het optimale offline algoritme moet ten minste één pagina verwijderen voor elke subreeks. Omdat bij het begin van fase 1 de cache nog steeds leeg is, veroorzaakt het optimale offline algoritme k uitzettingen tijdens de eerste fase. Dat laat zien

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

Corollary 1.5: LRU en FWF zijn strikt k-competitief .

Oefening: laat zien dat FIFO geen markeringsalgoritme is, maar strikt k-competitief .

Is er geen constante r waarvoor een online algoritme A r-competitief is, dan noemen we A niet competitief

Stelling 1.6: LFU en LIFO zijn niet concurrerend .

Bewijs: Laat l ≥ 2 een constante, k ≥ 2 de cachegrootte. De verschillende cachepagina's zijn nuber 1, ..., k + 1. We kijken naar de volgende volgorde:

De eerste pagina 1 wordt l keer aangevraagd dan pagina 2 en zo een. Aan het einde zijn er (l-1) afwisselende aanvragen voor pagina k en k + 1.
LFU en LIFO vullen hun cache met pagina's 1-k. Wanneer pagina k + 1 wordt gevraagd, wordt pagina k uitgezet en vice versa. Dat betekent dat elke aanvraag voor deelreeks (k, k + 1) ^l-1 één pagina uitzet. Bovendien zijn er k-1 cache-missers voor het eerste gebruik van pagina's 1- (k-1). Dus verwijderen LFU en LIFO exacte k-1 + 2 (l-1) pagina's.
Nu moeten we aantonen dat er voor elke constante τ∈ℜ en elke constante r ≤ 1 een l bestaat, zodat

die gelijk is aan

Om aan deze ongelijkheid te voldoen, moet je gewoon voldoende groot kiezen. LFU en LIFO zijn dus niet concurrerend.

Stelling 1.7: Er is geen r-competetive deterministisch online algoritme voor paging met r <k .

Het bewijs voor deze laatste propositie is vrij lang en gebaseerd op de stelling dat LFD een optimaal offline algoritme is. De geïnteresseerde lezer kan het opzoeken in het boek Borodin en El-Yaniv (zie bronnen hieronder).

De vraag is of we het beter kunnen doen. Daarvoor moeten we de deterministische benadering achter ons laten en ons algoritme willekeurig gaan maken. Het is duidelijk dat het voor de tegenstander veel moeilijker is om je algoritme te bestraffen als het willekeurig is.

Gerandomiseerde paging wordt besproken in een van de volgende voorbeelden ...