Gyorsítótár

Gyorsítótár [1] [2] [3] [4] vagy gyorsítótár [5] [6] [7] ( angol  gyorsítótár , francia nyelvből  cacher  - "elrejtés"; ejtsd: [ kæʃ ] - "gyorsítótár") - közbenső puffer gyors hozzáférést biztosít hozzá, amely a legnagyobb valószínűséggel kérhető információkat tartalmaz. A gyorsítótárban lévő adatokhoz való hozzáférés gyorsabb, mint az eredeti adatok lekérése lassabb memóriából vagy távoli forrásból, de mennyisége jelentősen korlátozott a forrásadattárhoz képest.

Történelem

A "gyorsítótár" szót először 1967 -ben használták számítógépes környezetben, amikor egy cikket készítettek elő az IBM Systems Journalban való közzétételre . A cikk a fejlesztés alatt álló IBM System/360 85-ös modell memóriafejlesztéseivel foglalkozott . A folyóirat szerkesztője, Lyle Johnson a "nagysebességű puffer" helyett inkább leíró kifejezést kért, de ötlethiány miatt ő maga javasolta a "gyorsítótár" szót. A cikk 1968 elején jelent meg, a szerzőket az IBM díjazta , munkájukat terjesztették, majd továbbfejlesztették, és a "gyorsítótár" szó hamarosan általános kifejezéssé vált a számítógépes szakirodalomban [8] .

Működés

A gyorsítótár gyorsabb elérési sebességű memória, amelyet arra terveztek, hogy felgyorsítsa a memóriában állandóan tárolt adatokhoz való hozzáférést alacsonyabb hozzáférési sebességgel (a továbbiakban: "fő memória"). A gyorsítótárazást a CPU , a merevlemezek , a böngészők , a webszerverek , a DNS és a WINS szolgáltatások használják .

A gyorsítótár egy sor bejegyzésből áll. Minden bejegyzés hozzá van rendelve egy adatelemhez vagy adatblokkhoz (egy kis adatdarabhoz), amely az adatelem másolata a fő memóriában. Minden bejegyzésnek van egy azonosítója , amelyet gyakran címkének neveznek , és amely meghatározza a gyorsítótárban lévő adatelemek és a fő memóriában lévő megfelelőik közötti megfelelést.

Amikor egy gyorsítótár-kliens (CPU, webböngésző, operációs rendszer) hozzáfér az adatokhoz, először a gyorsítótárat vizsgálja meg. Ha a gyorsítótárban olyan bejegyzés található, amelynek azonosítója megegyezik a kért elem azonosítójával, akkor a rendszer a gyorsítótárban lévő elemeket használja. Az ilyen eseményt gyorsítótár találatnak nevezik . Ha a kért adatelemet tartalmazó bejegyzés nem található a gyorsítótárban, akkor a rendszer a fő memóriából beolvassa a gyorsítótárba, és elérhetővé válik a későbbi hozzáférésekhez. Az ilyen esetet úngyorsítótár hiányzik . A gyorsítótárban elért találatok százalékos arányát találati aránynak vagy gyorsítótár találati arányának nevezzük .

Például egy webböngésző ellenőrzi a helyi gyorsítótárat a lemezen, keresve egy weboldal helyi másolatát, amely megegyezik a kért URL-lel. Ebben a példában az URL az azonosító, a weboldal tartalma pedig az adatelemek.

Ha a gyorsítótár mérete korlátozott, akkor kihagyás esetén előfordulhat, hogy eldobunk néhány bejegyzést, hogy helyet szabadítson fel. Különböző kilakoltatási algoritmusokat használnak annak kiválasztására, hogy melyik rekordot kell elvetni .

Ha a gyorsítótárban lévő adatelemek módosulnak, azok a fő memóriában frissülnek. A gyorsítótárban lévő adatok módosítása és a fő memória frissítése közötti késleltetést az úgynevezett írási politika szabályozza .

A csak írható gyorsítótárban minden változás a fő memóriában lévő adatok szinkron frissítését okozza.

A visszaírási (vagy visszaírási ) gyorsítótárban frissítés történik, amikor egy adatelemet kiürítenek, időszakonként vagy az ügyfél kérésére. A módosított adatelemek nyomon követéséhez a gyorsítótár bejegyzései módosítási jelzőt tárolnak ( módosított vagy "piszkos" ). A visszaírással járó gyorsítótár-hiány két hozzáférést igényelhet a fő memóriához: az első a helyettesített adatok gyorsítótárból történő kiírásához, a második a szükséges adatelem beolvasásához.

Abban az esetben, ha a fő memóriában lévő adatok a gyorsítótártól függetlenül módosíthatók, a gyorsítótár-bejegyzés elavulttá válhat . Az adatkonzisztenciát fenntartó gyorsítótárak közötti kommunikációra szolgáló protokollokat gyorsítótár-koherencia protokolloknak nevezzük .

Hardver implementáció

CPU gyorsítótár

A processzorok működési gyakoriságának növekedése és a RAM alrendszer ( RAM) teljesítményének növekedése miatt az adatátviteli interfész a számítási rendszer szűk keresztmetszetévé vált.

A gyorsítótár jelentős teljesítményelőnyökkel járhat, ha a RAM órajele lényegesen alacsonyabb, mint a processzor órajele. Számos processzormodell rendelkezik saját gyorsítótárral, amely minimalizálja a véletlen elérésű memóriához (RAM) való hozzáférési időt, amely lassabb, mint a regiszterek (ezek a regiszterek és az I/O pufferek nulla gyorsítótárszintnek tekinthetők). A cache memória órajele általában nem sokkal kisebb, mint a CPU frekvencia.

A virtuális címzést támogató processzorok gyakran tartalmaznak kisméretű, gyors címfordító puffert (TLB). A sebessége azért fontos, mert minden memóriaeléréskor lekérdezik.

A különböző gyorsítótárak (egy és több processzor) közötti szinkronizálás problémáját a gyorsítótár koherenciája oldja meg .

Három lehetőség van a különböző szintű gyorsítótárak, vagy ahogy mondani szokás, a cache architektúrák közötti információcserére: inkluzív, kizárólagos és nem kizárólagos.

Az exkluzív gyorsítótár a gyorsítótár különböző szintjein található információk egyediségét feltételezi (az AMD által preferált ).

A nem kizárólagos gyorsítótárak tetszés szerint viselkedhetnek.

Processzor gyorsítótár szintjei

A CPU gyorsítótár több szintre oszlik. A gyorsítótárak maximális száma négy. Egy univerzális processzorban a szintek száma jelenleg legfeljebb három lehet. Az N+1 szintű gyorsítótárak általában nagyobbak és lassabbak a hozzáférésben és az adatátvitelben, mint az N szintű gyorsítótárak.

  • A leggyorsabb az első szintű gyorsítótár - L1 gyorsítótár (1. szintű gyorsítótár). Valójában ez a processzor szerves része, mivel ugyanazon a chipen található, és a funkcionális blokkok része. A modern processzorokban az L1 általában két gyorsítótárra oszlik - az utasítás (utasítás) gyorsítótárra és az adatgyorsítótárra ( Harvard architektúra ). A legtöbb L1 nélküli processzor nem működik. Az L1 a processzor frekvenciáján működik, és általában minden órajelben elérhető . Gyakran lehetséges több olvasási/írási művelet végrehajtása egyidejűleg.
  • A második leggyorsabb az L2 gyorsítótár, amely az L1-hez hasonlóan általában ugyanazon a chipen található, mint a processzor. A korai processzorok az L2-t külön memórialapkakészletként valósították meg az alaplapon. Az L2 kötete 128 KB és 1-12 MB között van. A modern többmagos processzorokban az ugyanazon a chipen található második szintű gyorsítótár egy külön memória - n MB teljes gyorsítótármérettel, minden mag n / c MB, ahol c a processzormagok száma.
  • A harmadik szintű gyorsítótár a legkevésbé gyors, de nagyon nagy is lehet - több mint 24 MB. Az L3 lassabb, mint a korábbi gyorsítótárak, de még mindig lényegesen gyorsabb, mint a RAM. Többprocesszoros rendszerekben általánosan elterjedt, és különféle L2 adatok szinkronizálására szolgál.
  • A gyorsítótárnak van egy negyedik szintje, amelynek használata csak többprocesszoros, nagy teljesítményű szervereknél és nagyszámítógépeknél indokolt . Általában egy külön chippel valósítják meg.
Gyorsítótár asszociativitás

A cache memória egyik alapvető jellemzője - az asszociativitás szintje - a logikai szegmentációját tükrözi, amelyet az okoz, hogy az összes gyorsítótár-sor szekvenciális felsorolása a szükséges adatok keresése során több tíz ciklust igényelne, és semmissé tenné az ebből származó nyereséget. a CPU-ba épített memória használatával. Ezért a RAM-cellák a gyorsítótár-sorokhoz vannak kötve (minden sor tartalmazhat adatokat rögzített címkészletből), ami jelentősen csökkenti a keresési időt.

Azonos gyorsítótár-méret mellett egy nagyobb asszociativitással rendelkező séma lesz a legkevésbé gyors, de a leghatékonyabb (négyszálas implementáció után a szálonkénti „fajlagos hatékonyság” növekedése alig nő).

Külső tároló gyorsítótárazása

Sok tárolóperiféria belső gyorsítótárat használ a dolgok felgyorsítására, különösen a merevlemezek 1 MB-tól 256 MB-ig terjedő gyorsítótárat használnak (az NCQ / TCQ modellek tárolásra és lekérdezések feldolgozására használják), a CD/DVD/BD-lemezek az olvasási információkat is gyorsítótárazzák a felgyorsítás érdekében. visszakeresés.

Az operációs rendszer a RAM egy részét gyorsítótárként is használja a lemezműveletekhez (például olyan külső eszközökhöz, amelyek nem rendelkeznek saját gyorsítótárral, beleértve a merevlemezeket, a flash memóriát és a hajlékonylemezeket). A merevlemezek gyorsítótárazásához gyakran az összes ingyenes (a folyamatokhoz nem rendelt) RAM rendelkezésre áll.

A gyorsítótárazott külső meghajtók használata a következő tényezőknek köszönhető:

  1. a processzor RAM-hoz való hozzáférésének sebessége több százszor nagyobb, mint a külső meghajtók memóriájához;
  2. a lemezes tárolóeszközök (kemény, floppy, optikai lemezek) teljesítménye több egymást követő blokk olvasása-írása esetén maximális, és jelentősen csökken a lemez különböző helyeire irányuló egyedi kérések esetén, ami a fej mechanikus meghajtójának tehetetlenségének köszönhető.
  3. a külső meghajtók különböző memóriablokkjaihoz való hozzáférés rendkívül egyenetlen gyakorisága:
    1. a blokkok egy részének több folyamat egyidejű felhasználása olvasásra és írásra (például adatbázisokban)
    2. a blokkok egy részének nagyon gyakori olvasása (indexfájlok, könyvtárak a fájlrendszerben)
    3. a blokkok egy részének nagyon gyakori írása (naplófájlok, naplók, adatbázis fájlok; fájlrendszer metaadatai).

Olvasáskor a gyorsítótár lehetővé teszi a blokk egyszeri beolvasását, majd a blokk egy példányának eltárolását a RAM-ban az összes folyamat számára, és "azonnal" visszaadja a blokk tartalmát (a lemezkéréshez képest). Van egy "pre-request" technika - a háttérben az operációs rendszer a következő néhány blokkot is beolvassa (a szükséges után) a gyorsítótárba.

Íráskor a gyorsítótár lehetővé teszi a rövid rekordok nagyobb rekordokba csoportosítását, amelyeket a meghajtók hatékonyabban dolgoznak fel, illetve elkerülhető a közbenső módosítások írása. Ebben az esetben a blokk összes köztes állapota látható a RAM-ból származó folyamatok számára.

A külső tároló gyorsítótárazása nagymértékben javítja a rendszer teljesítményét az I/O használat optimalizálásával. A technológia előnye a lemezmemória használatának átlátható (programok számára láthatatlan) automatikus optimalizálása, miközben a fájlokkal dolgozó alkalmazások logikája változatlan marad.

Az írási gyorsítótárazás hátránya az, hogy mennyi idő telik el a programtól érkező írási kérés és a blokk tényleges lemezre írása, valamint az írások újrarendezése között, ami áramkimaradás vagy rendszer esetén információvesztéshez vagy szerkezeti inkonzisztenciákhoz vezethet. lóg. Ezt a problémát enyhíti a kényszerített időszakos szinkronizálás (megváltozott gyorsítótár sorok írása) és a fájlrendszer naplózása.

Szoftver implementáció

Gyorsítótárazási írási szabályzat

Adatok olvasásakor a gyorsítótár egyértelmű teljesítménynövekedést ad. Adatíráskor nyereség csak a megbízhatóság csökkenése árán érhető el. Ezért a különböző alkalmazások eltérő gyorsítótár írási házirendeket választhatnak.

Két fő gyorsítótár-írási szabályzat létezik: az átírás és a visszaírás:

  1. Átírás - az írás közvetlenül a fő memóriába történik (és duplikálódik a gyorsítótárban), vagyis az írás nem gyorsítótárazódik.
  2. Lusta írás – az adatok a gyorsítótárba íródnak. A főmemóriába való írás később történik (előre vagy idő letelte után), több írási műveletet csoportosítva a szomszédos cellákba egy műveletben. A visszaírási technológia egy ideig irrelevánssá teszi a fő memóriában lévő adatokat, ezeket az irrelevánsságokat maga a CPU nem veszi észre, de mielőtt hozzáférne egy másik vezető rendszerbusz ( DMA vezérlő, PCI busz-master busz eszköz ) memóriájához, a cache-nek kell erőszakkal a memóriába kell írni. Ha többprocesszoros rendszeren visszaírást használ, a különböző CPU-k gyorsítótárainak konzisztensnek kell lenniük (vagy a processzoroknak ugyanazon a gyorsítótáron kell osztozniuk).
Gyorsítótár-visszaírási algoritmus

Kezdetben az összes pufferfejléc a pufferek szabad listájára kerül. Ha egy folyamat egy blokkot kíván olvasni vagy módosítani, akkor a következő algoritmust hajtja végre:

  1. megpróbálja megkeresni a megadott számú puffer fejlécét a hash táblában ;
  2. ha a fogadott puffer foglalt, várja, hogy felszabaduljon;
  3. ha a puffer nem található a hash táblában, akkor a szabad lista végéből veszi az első puffert;
  4. ha a szabad pufferek listája üres, akkor a kilakoltatási algoritmus végrehajtásra kerül (lásd alább);
  5. ha a fogadott puffer "piszkosnak" van jelölve, a puffer tartalmát aszinkron módon írja a külső memóriába.
  6. eltávolítja a puffert a hash táblából, ha benne volt;
  7. a puffert egy új számmal a hash táblába helyezi.

A folyamat beolvassa az adatokat a fogadott pufferbe, és felszabadítja azokat. Módosítás esetén a folyamat a puffert "piszkosnak" jelöli, mielőtt felszabadítaná. Felszabadításkor a puffer a szabad pufferlista élére kerül.

Ilyen módon:

  1. ha egy folyamat beolvas egy blokkot a pufferbe, akkor nagyon valószínű, hogy egy másik folyamat ennek a blokknak az olvasásakor megtalálja a puffert a RAM-ban;
  2. Az adatok külső memóriába írása csak akkor történik, ha nincs elég "tiszta" puffer, vagy kérésre.

Eltolási algoritmus

Ha a szabad pufferek listája üres, akkor a puffer-öblítési algoritmus végrehajtásra kerül. A kilakoltatási algoritmus jelentősen befolyásolja a gyorsítótár teljesítményét. A következő algoritmusok léteznek:

  1. Időzítővel megvalósítva :
    1. LRU ( angolul  Least Recently Used ) - a leghosszabb ideig nem használt puffer kicserélésre kerül;
    2. MRU ( angolul :  Most Recently Used ) – az utoljára használt puffer lecserélésre kerül;
  2. Számlálóval megvalósítva :
    1. LFU ( eng.  Least Frequently Used ) - a legkevésbé gyakran használt puffert kicseréljük;
    2. Az ARC ( angolul  Adaptive Replacement Cache ) egy extrudálási algoritmus, amely egyesíti az LRU -t és az LFU -t, és amelyet az IBM szabadalmaztatott.

Az egyik vagy másik algoritmus használata az adatgyorsítótárazási stratégiától függ. Az LRU akkor a leghatékonyabb, ha az adatok a lehető leghamarabb újrafelhasználhatók. Az MRU akkor a leghatékonyabb, ha az adatok egyhamar nem használhatók fel újra. Ha az alkalmazás kifejezetten gyorsítótárazási stratégiát ad meg bizonyos adatkészletekhez, akkor a gyorsítótár fog a leghatékonyabban működni.

Operációs rendszer gyorsítótár

A RAM gyorsítótár a következő elemekből áll:

  1. a megfelelő külső memóriaeszköz adatblokkjával megegyező hosszúságú pufferekre osztott RAM-oldalak készlete;
  2. a megfelelő puffer állapotát leíró pufferfejlécek készlete;
  3. a fejléchez illő blokkszámot tartalmazó hash tábla ;
  4. ingyenes pufferek listája.

Weboldal gyorsítótár

A hálózaton keresztüli információátvitel során a weboldal gyorsítótárazása használható - a gyakran kért dokumentumok (köztes) proxyszervereken vagy a felhasználó gépén történő tárolásának folyamata, hogy megakadályozzák azok folyamatos letöltését a forrásszerverről és csökkentsék a forgalmat . Így az információ közelebb kerül a felhasználóhoz. A gyorsítótárazást a HTTP - fejlécek vezérlik .

Alternatív megoldásként a weboldalak gyorsítótárazása elvégezhető egy adott webhely CMS -jével, hogy csökkentse a szerver terhelését nagy forgalom esetén. A gyorsítótárazás mind a memóriában, mind a fájl gyorsítótárban történhet [9] . A gyorsítótárazás hátránya, hogy az egyik böngészőben végrehajtott változtatások nem feltétlenül jelennek meg azonnal egy másik böngészőben, amely az adatokat a gyorsítótárból tölti le.

Munkaeredmények gyorsítótárazása

Sok program írja valahova a munka közbenső vagy segéderedményeit, hogy ne számítsa ki minden alkalommal, amikor szükség van rájuk. Ez felgyorsítja a munkát, de további memóriát (RAM vagy lemez) igényel. Ilyen gyorsítótárazásra példa az adatbázis-indexelés .

Lásd még

Jegyzetek

  1. ↑ Készpénz // Az orosz nyelv nagy helyesírási szótára / szerk. S. G. Barkhudarova , I. F. Protchenko és L. I. Skvortsova . - 3. kiadás - M . : ONIKS Mir and Education, 2007. - S. 399. - ISBN 978-5-488-00924-0 . - ISBN 978-5-94666-375-5 .
  2. ↑ Az orosz nyelv nagy magyarázó szótára / Szerző, összeáll. és Ch. szerk. S. A. Kuznyecov. RAS Nyelvtudományi Kutatóintézet, 2000
  3. ↑ Zakharenko E. N., Komarova L. N., Nechaeva I. V. Az idegen szavak új szótára. M.: 2003
  4. ↑ Számítástechnikai magyarázó szótár. Microsoft Press, orosz kiadás, 1995
  5. ↑ Orosz helyesírási szótár: körülbelül 180 000 szó [Elektronikus változat] / O. E. Ivanova , V. V. Lopatin (felelős szerk.), I. V. Nechaeva , L. K. Cheltsova . — 2. kiadás, javítva. és további - M .: Orosz Tudományos Akadémia . V. V. Vinogradov Orosz Nyelv Intézete , 2004. - 960 p. — ISBN 5-88744-052-X .
  6. ↑ Pershikov V.I., Savinkov V.M. Informatikai magyarázó szótár / Lektorok: Cand. Fiz.-Matek. Sci. A. S. Markov és Dr. Phys.-Math. Tudományok I. V. Pottosin. - M. : Pénzügy és statisztika, 1991. - 543 p. — 50.000 példány.  - ISBN 5-279-00367-0 .
  7. ↑ Borkovsky A. B. Angol-orosz programozási és informatikai szótár (értelmezésekkel). - M . : Orosz nyelv, 1990. - 335 p. - 50 050 (további) példány.  — ISBN 5-200-01169-3 .
  8. ↑ G.C. Stierhoff, A.G. Davis. Az IBM Systems Journal története // IEEE Annals of the History of Computing. - 1998. január - V. 20. , 1. sz . - S. 29-35 . - doi : 10.1109/85.646206 .
  9. ↑ Elosztott operációs rendszer . Letöltve: 2009. november 29. Az eredetiből archiválva : 2010. szeptember 10.

Irodalom

  • Bach M.J. UNIX operációs rendszer architektúrája