Spartinančiosios atminties algoritmas
Talpyklos algoritmas - tai algoritmas, naudojamas talpyklai arba duomenų grupei valdyti. Kai talpykla prisipildo, jis nusprendžia, kurį elementą reikia ištrinti iš talpyklos. Žodžiu hit rate apibūdinama, kaip dažnai užklausa gali būti aptarnauta iš talpyklos. Terminas latentinis laikas (latency) apibūdina, per kiek laiko galima gauti talpyklos elementą. Talpyklos aloritmai - tai kompromisas tarp pataikymo greičio ir delsos.
- Efektyviausias spartinančiosios atminties algoritmas būtų visada atmesti informaciją, kurios nereikės ilgiausiai ateityje. Šis optimalus rezultatas vadinamas Beladžio optimaliuoju algoritmu arba aiškiaregystės algoritmu. Kadangi paprastai neįmanoma nuspėti, kaip toli ateityje prireiks informacijos, praktiškai tai paprastai neįgyvendinama. Praktinį minimumą galima apskaičiuoti tik atlikus eksperimentą ir palyginti faktiškai pasirinkto talpyklos algoritmo efektyvumą su optimaliu minimumu.
- Mažiausiai naudotas (LRU): pirmiausia ištrinami mažiausiai naudoti elementai. Šis algoritmas reikalauja sekti, kas ir kada buvo naudojama. Tai brangu, jei norima užtikrinti, kad algoritmas visada pašalintų mažiausiai naudotą elementą. Įgyvendinant šį metodą paprastai reikia saugoti talpyklos eilučių "amžiaus bitus" ir pagal amžiaus bitus sekti "mažiausiai naudotą" talpyklos eilutę. Įgyvendinant tokį metodą, kiekvieną kartą, kai naudojama talpyklos eilutė, keičiasi visų kitų talpyklos eilučių amžius. LRU iš tikrųjų yra spartinančiosios atminties algoritmų šeima, kurios nariai yra šie: Theodore'o Johnsono ir Denniso Shasha'os sukurtą 2Q ir Pato O'Neilo, Betty O'Neil ir Gerhardo Weikumo sukurtą LRU/K.
- Paskutinį kartą naudotas (MRU): Šis algoritmas pirmiausia ištrina vėliausiai naudotus elementus. Šis spartinančiosios atminties mechanizmas paprastai naudojamas duomenų bazių atminties talpyklose.
- Pseudo-LRU (PLRU): Tam tikrais atvejais LRU įgyvendinti labai sunku. Tokiais atvejais gali pakakti žinoti, kad daugeliu atvejų vienas iš mažiausiai naudotų elementų yra ištrinamas. Čia galima naudoti PLRU algoritmą, nes jam veikti reikia tik vieno bito kiekvienam talpyklos elementui.
- 2 krypčių asocijuotoji: skirta sparčiosioms procesorių talpykloms, kai net PLRU yra per lėta. Naujo elemento adresas naudojamas apskaičiuoti vieną iš dviejų galimų talpyklos vietų, į kurią jis gali būti perkeltas. LRU iš šių dviejų atmetama. Tam reikia vieno bito kiekvienai talpyklos eilučių porai, kad būtų galima nurodyti, kuri iš šių dviejų vietų buvo mažiausiai naudota.
- Tiesiogiai žymima talpykla: skirta sparčiausioms procesoriaus talpykloms, kai net 2 krypčių asociatyviosios talpyklos yra per lėtos. Pagal naujo elemento adresą apskaičiuojama viena talpyklos vieta, į kurią jam leidžiama patekti. Viskas, kas ten buvo prieš tai, atmetama.
- Rečiausiai naudojamas (LFU): LFU skaičiuoja, kaip dažnai elemento prireikia. Pirmiausia išmetami tie, kurie naudojami rečiausiai.
- Adaptyvioji pakeitimo talpykla (ARC): nuolat balansuoja tarp LRU ir LFU, kad pagerintų bendrą rezultatą.
- Kelių eilių (MQ) spartinimo algoritmas: Philbin ir Kai Li).
Kiti dalykai, į kuriuos reikia atsižvelgti:
- Skirtingos kainos daiktai: pasilikite daiktus, kuriuos brangu gauti, pvz., tuos, kuriuos gauti reikia daug laiko.
- Daugiau talpyklos užimantys elementai: Jei elementai yra skirtingo dydžio, talpykla gali norėti išmesti didelį elementą, kad galėtų saugoti kelis mažesnius.
- Prekės, kurių galiojimo laikas su laiku baigiasi: Naujienų talpykla, DNS talpykla arba žiniatinklio naršyklės talpykla). Kompiuteris gali išmesti elementus, nes jų galiojimo laikas yra pasibaigęs. Priklausomai nuo talpyklos dydžio, gali neprireikti tolesnio talpyklos algoritmo elementams išmesti.
Taip pat egzistuoja įvairūs algoritmai talpyklos darnai palaikyti. Tai taikoma tik tais atvejais, kai tiems patiems duomenims naudojamos kelios nepriklausomos spartinančiosios atmintinės (pavyzdžiui, keli duomenų bazių serveriai atnaujina vieną bendrą duomenų failą).
Kurias atminties vietas galima talpinti į spartinančiąją atmintį
Klausimai ir atsakymai
K: Kas yra talpyklos algoritmas?
A: Spartinančiosios atminties algoritmas - tai algoritmas, naudojamas talpyklai arba duomenų grupei valdyti. Jis nusprendžia, kurį elementą reikia ištrinti iš talpyklos, kai ji yra pilna.
K: Kas yra pataikymo rodiklis?
A: Patenkinimo rodiklis apibūdina, kaip dažnai užklausa gali būti aptarnauta iš talpyklos.
K: Ką apibūdina uždelsimas?
A: Vėlavimas apibūdina, per kiek laiko galima gauti talpyklos elementą.
K: Kas yra Beladžio optimalus algoritmas?
A: Beladžio optimalus algoritmas, dar vadinamas aiškiaregystės algoritmu, yra veiksmingas spartinančiosios talpyklos algoritmas, pagal kurį visada atmetama informacija, kurios nereikės ilgiausiai ateityje. Šio rezultato paprastai negalima įgyvendinti praktiškai, nes reikia numatyti, ko prireiks tolimoje ateityje.
Klausimas: Kaip veikia mažiausiai neseniai naudotas (angl. Least Recently Used, LRU)?
A: LRU pirmiausia ištrina mažiausiai naudotus elementus, todėl reikia sekti, kas ir kada buvo naudojama, naudojant kiekvienos talpyklos eilutės "amžiaus bitus" ir stebint, kuri eilutė buvo mažiausiai naudota pagal amžiaus bitus. Kiekvieną kartą, kai naudojama talpyklos eilutė, atitinkamai pakeičiamas visų kitų talpyklos eilučių amžius.
K: Kaip veikia MRU (Most Recently Used)?
A: MRU pirmiausia ištrina vėliausiai naudotus elementus, ir šis spartinančiosios atminties mechanizmas paprastai naudojamas duomenų bazių atminties talpyklose.
K: Kokie kiti algoritmai taikomi spartinančiosios atmintinės darnai palaikyti?
A; Kai bendriems duomenims naudojami keli nepriklausomi talpyklos, pavyzdžiui, kai keli duomenų bazių serveriai atnaujina vieną bendrą duomenų failą, egzistuoja įvairūs algoritmai talpyklos darnai palaikyti.
