Kätkö

Välimuisti [1] [2] [3] [4] tai välimuisti [5] [6] [7] ( engl.  cache , ranskasta  cacher  - "piilota"; lausutaan [ kæʃ ] - "välimuisti") - välipuskuri nopea pääsy siihen, joka sisältää tietoja, joita voidaan pyytää suurimmalla todennäköisyydellä. Välimuistissa olevien tietojen käyttö on nopeampaa kuin alkuperäisten tietojen hakeminen hitaammalta muistilta tai etälähteestä, mutta sen määrä on huomattavasti rajoitettu verrattuna lähdetietovarastoon.

Historia

Sanaa "välimuisti" käytettiin ensimmäisen kerran tietokonekontekstissa vuonna 1967 valmisteltaessa artikkelia julkaistavaksi IBM Systems Journal -lehdessä . Artikkeli käsitteli muistin parannuksia kehitteillä olevan IBM System/360 - mallin 85 . Lehden toimittaja Lyle Johnson pyysi kuvaavampaa termiä kuin "high-speed buffer", mutta ideoiden puutteen vuoksi hän itse ehdotti sanaa "kätkö". Artikkeli julkaistiin vuoden 1968 alussa, kirjoittajat palkittiin IBM :ltä , heidän töitään levitettiin ja parannettiin myöhemmin, ja sanasta "kätkö" tuli pian yleinen termi tietokonekirjallisuudessa [8] .

Toimiva

Välimuisti on nopeammalla pääsynopeudella varustettu muisti, joka on suunniteltu nopeuttamaan pysyvästi muistissa olevien tietojen käyttöä pienemmällä käyttönopeudella (jäljempänä "päämuisti"). Välimuistia käyttävät CPU , kiintolevyt , selaimet , web-palvelimet , DNS- ja WINS - palvelut .

Välimuisti koostuu joukosta merkintöjä. Jokainen merkintä liittyy tietoelementtiin tai tietolohkoon (pieneen tietoon), joka on kopio päämuistissa olevasta tietoelementistä. Jokaisella tiedolla on tunniste , jota usein kutsutaan tunnisteeksi , joka määrittää vastaavuuden välimuistissa olevien tietokohteiden ja niiden vastineiden välillä päämuistissa.

Kun välimuistiasiakas (CPU, verkkoselain, käyttöjärjestelmä) käyttää tietoja, välimuisti tutkitaan ensin. Jos välimuistista löytyy merkintä, jonka tunnus vastaa pyydetyn kohteen tunnusta, välimuistissa olevia kohteita käytetään. Tällaista tapahtumaa kutsutaan välimuistiosuukseksi . Jos välimuistista ei löydy pyydetyn tietoelementin sisältävää merkintää, se luetaan päämuistista välimuistiin ja tulee saataville myöhempiä käyttöjä varten. Tällaista tapausta kutsutaanvälimuistin ikävä . Välimuistin osumien prosenttiosuutta, kun tulos löydetään, kutsutaan osumasuhteeksi tai välimuistin osumasuhteeksi .

Esimerkiksi verkkoselain tarkistaa paikallisesta levyvälimuististaan, löytyykö pyydettyä URL-osoitetta vastaavan Web-sivun paikallinen kopio. Tässä esimerkissä URL-osoite on tunniste ja verkkosivun sisältö tietoelementtejä.

Jos välimuisti on kooltaan rajoitettu, väliin jäämisen yhteydessä saatetaan päättää hylätä osa sisääntulosta tilan vapauttamiseksi. Erilaisia ​​häätöalgoritmeja käytetään valitsemaan hylättävä tietue .

Kun välimuistin tietokohteita muutetaan, ne päivitetään päämuistiin. Aikaviivettä välimuistin tietojen muuttamisen ja päämuistin päivityksen välillä ohjataan ns. kirjoituskäytännöllä .

Vain kirjoitus -välimuistissa jokainen muutos aiheuttaa synkronisen päivityksen päämuistissa oleviin tietoihin.

Takaisinkirjoitus (tai takaisinkirjoitus) -välimuistissa päivitys tapahtuu, kun tietoelementti häädetään , määräajoin tai asiakkaan pyynnöstä. Muokattujen tietokohteiden seuraamiseksi välimuistin merkinnät tallentavat muokkauslipun ( muokattu tai "likainen" ). Välimuistin puuttuminen takaisinkirjoituksella voi vaatia kaksi pääsyä päämuistiin: ensimmäinen kirjoittaa korvatun tiedon välimuistista, toinen lukeakseen vaaditun tietoelementin.

Jos päämuistissa olevia tietoja voidaan muokata välimuistista riippumatta, välimuistin merkintä voi vanhentua . Tietojen johdonmukaisuutta ylläpitävien välimuistien välisiä kommunikointiprotokollia kutsutaan välimuistin koherenssiprotokolliksi .

Laitteiston toteutus

CPU-välimuisti

Prosessorien toimintataajuuden kasvun ja RAM-alijärjestelmän ( RAM) suorituskyvyn kasvun vuoksi tiedonsiirtoliitännästä on tullut laskentajärjestelmän pullonkaula.

Välimuisti voi tarjota merkittäviä suorituskykyetuja, kun RAM-muistin kellonopeus on huomattavasti pienempi kuin prosessorin kellonopeus. Useissa prosessorimalleissa on oma välimuisti, joka minimoi käyttöajan RAM-muistiin, joka on hitaampi kuin rekisterit (näitä rekistereitä ja I/O-puskureita voidaan pitää välimuistitason nollana). Välimuistin kellonopeus ei yleensä ole paljon pienempi kuin suorittimen taajuus.

Virtuaaliosoitteita tukevat prosessorit sisältävät usein pienen, nopean osoitteenmuunnospuskurin (TLB). Sen nopeus on tärkeä, koska se kysytään jokaisen muistin käytön yhteydessä.

Eri välimuistien (sekä yhden että usean prosessorin) välinen synkronointiongelma ratkaistaan ​​välimuistin koherenssilla .

Tietojen vaihtamiseen eri tasoisten välimuistien tai, kuten sanotaan, välimuistiarkkitehtuurien välillä on kolme vaihtoehtoa: inclusive, exclusive ja non-exclusive.

Yksinomainen välimuisti olettaa välimuistin eri tasoilla sijaitsevien tietojen ainutlaatuisuuden ( AMD :n suosima ).

Ei-yksinomaisissa välimuistit voivat käyttäytyä kuten haluavat.

Prosessorin välimuistin tasot

CPU-välimuisti on jaettu useisiin tasoihin. Välimuistien enimmäismäärä on neljä. Yleisessä prosessorissa tasojen lukumäärä voi tällä hetkellä olla jopa kolme. Tason N+1 välimuistit ovat yleensä suurempia ja hitaampia pääsyssä ja tiedonsiirrossa kuin tason N välimuistit.

  • Nopein on ensimmäisen tason välimuisti - L1-välimuisti (tason 1 välimuisti). Itse asiassa se on olennainen osa prosessoria, koska se sijaitsee samassa sirussa ja on osa toiminnallisia lohkoja. Nykyaikaisissa prosessoreissa L1 on yleensä jaettu kahteen välimuistiin - käskyvälimuistiin (käsky) ja datavälimuistiin ( Harvard-arkkitehtuuri ). Useimmat prosessorit ilman L1:tä eivät voi toimia. L1 toimii prosessorin taajuudella, ja yleensä sitä voidaan käyttää joka kellojaksolla . Usein on mahdollista suorittaa useita luku-/kirjoitustoimintoja samanaikaisesti.
  • Toiseksi nopein on L2-välimuisti, joka, kuten L1, sijaitsee yleensä samassa sirussa prosessorin kanssa. Varhaiset prosessorit toteuttivat L2:n erillisenä muistipiirisarjana emolevyllä. L2:n tilavuus on 128 kilotavua 1-12 megatavuun. Nykyaikaisissa moniytimisissä prosessoreissa samalla sirulla sijaitseva toisen tason välimuisti on erillinen muisti - välimuistin kokonaiskoon ollessa n MB, jokaisessa ytimessä on n / c MB, missä c on prosessoriytimien lukumäärä.
  • Kolmannen tason välimuisti on vähiten nopea, mutta se voi olla erittäin suuri - yli 24 Mt. L3 on hitaampi kuin aiemmat välimuistit, mutta silti huomattavasti nopeampi kuin RAM. Moniprosessorijärjestelmissä se on yleisesti käytössä ja on suunniteltu synkronoimaan eri L2-tason tietoja.
Välimuistin assosiatiivisuus

Yksi välimuistin perusominaisuuksista - assosiatiivisuuden taso - heijastaa sen loogista segmentointia, joka johtuu siitä, että kaikkien välimuistirivien peräkkäinen luettelointi tarvittavan tiedon etsimiseksi vaatisi kymmeniä syklejä ja mitätöisi kaiken hyödyn käyttämällä CPU:n sisäänrakennettua muistia. Siksi RAM-solut on kiinteästi kytketty välimuistilinjoihin (jokainen rivi voi sisältää dataa kiinteästä osoitejoukosta), mikä vähentää merkittävästi hakuaikaa.

Samalla välimuistikoolla suurempi assosiatiivisuus on vähiten nopea, mutta tehokkain (neljäsäikeisen toteutuksen jälkeen "ominaistehokkuuden" kasvu säiettä kohti kasvaa vain vähän).

Ulkoisen tallennustilan välimuisti

Monet tallennusoheislaitteet käyttävät sisäistä välimuistia nopeuttaakseen asioita, erityisesti kiintolevyt käyttävät 1 Mt - 256 Mt välimuistia ( NCQ / TCQ -mallit käyttävät sitä tallennus- ja kyselynkäsittelyyn), CD/DVD/BD-levyt myös tallentavat lukutiedot välimuistiin nopeuttaakseen haku.

Käyttöjärjestelmä käyttää myös osaa RAM-muistista välimuistina levytoimintoihin (esimerkiksi ulkoisille laitteille, joilla ei ole omaa välimuistia, mukaan lukien kiintolevyt, flash-muisti ja levykkeet). Usein kaikki ilmainen (ei prosesseille osoitettu) RAM tarjotaan kiintolevyjen välimuistiin.

Ulkoisten asemien välimuistin käyttö johtuu seuraavista tekijöistä:

  1. prosessorin nopeus RAM-muistiin on satoja tai useampia kertoja suurempi kuin ulkoisten asemien muistiin;
  2. levytallennuslaitteiden (kovat, levykkeet, optiset levyt) suorituskyky on maksimaalinen luettaessa ja kirjoitettaessa useita peräkkäisiä lohkoja ja heikkenee merkittävästi yksittäisillä pyynnöillä levyn eri paikkoihin, mikä johtuu pään mekaanisen aseman inertiasta.
  3. äärimmäisen epätasainen ulkoisten asemien eri muistilohkojen käyttötaajuus:
    1. osan lohkoista käyttö useissa prosesseissa samanaikaisesti lukemiseen ja kirjoittamiseen (esimerkiksi tietokantoihin)
    2. erittäin usein osan lohkoista lukeminen (hakemistotiedostot, tiedostojärjestelmän hakemistot)
    3. osan lohkojen (lokitiedostot, päiväkirjat, tietokantatiedostot; tiedostojärjestelmän metatiedot) kirjoittaminen hyvin usein.

Luettaessa välimuisti antaa sinun lukea lohkon kerran, tallentaa sitten yhden kopion lohkosta RAM-muistiin kaikille prosesseille ja palauttaa lohkon sisällön "välittömästi" (verrattuna levypyyntöön). On olemassa "ennakkopyyntö" -tekniikka - taustalla käyttöjärjestelmä lukee myös seuraavat muutamat lohkot (vaatimuksen jälkeen) välimuistiin.

Kirjoittaessasi välimuistin avulla voit ryhmitellä lyhyitä tietueita suurempiin tietueisiin, joita asemat käsittelevät tehokkaammin, tai välttää välimuutosten kirjoittamista. Tässä tapauksessa kaikki lohkon välitilat näkyvät prosesseille RAM-muistista.

Ulkoisen tallennustilan välimuisti parantaa huomattavasti järjestelmän suorituskykyä optimoimalla I/O-käytön. Tekniikan etuna on läpinäkyvä (ohjelmille näkymätön) automaattinen levymuistin käytön optimointi, kun tiedostojen kanssa työskentelevien sovellusten logiikka pysyy ennallaan.

Kirjoitusvälimuistin haittapuoli on aika, joka kuluu ohjelman kirjoituspyynnön ja lohkon varsinaisen levylle kirjoittamisen välillä, sekä kirjoitusten uudelleenjärjestäminen, mikä voi johtaa tietojen menettämiseen tai rakenteen epäjohdonmukaisuuksiin sähkökatkon tai järjestelmän aikana. ripustaa. Tätä ongelmaa lieventää pakotettu säännöllinen synkronointi (muuttuneiden välimuistirivien kirjoittaminen) ja tiedostojärjestelmän kirjaaminen.

Ohjelmiston toteutus

Välimuistin kirjoituskäytäntö

Dataa luettaessa välimuisti parantaa suorituskykyä selvästi. Tietoja kirjoitettaessa voittoja voidaan saada vain heikentyneen luotettavuuden kustannuksella. Siksi eri sovellukset voivat valita eri välimuistin kirjoituskäytännöt.

On olemassa kaksi päämuistin kirjoituskäytäntöä - läpikirjoitus ja takaisinkirjoitus:

  1. Kirjoitus - kirjoitus tehdään suoraan päämuistiin (ja kopioidaan välimuistiin), eli kirjoitusta ei tallenneta välimuistiin.
  2. Laiska kirjoitus - tiedot kirjoitetaan välimuistiin. Kirjoitus päämuistiin suoritetaan myöhemmin (ennakolta tai ajan kuluttua) ryhmittelemällä useita kirjoitustoimintoja naapurisoluihin yhteen operaatioon. Takaisinkirjoitustekniikka tekee päämuistissa olevista tiedoista merkityksettömiä joksikin aikaa, nämä epäolennaisuudet eivät ole havaittavissa CPU:lle itselleen, mutta ennen kuin päästään toisen johtavan järjestelmäväylän muistiin ( DMA -ohjain, PCI -väylä-pääväylälaite ), välimuistin on oltava kirjoitetaan muistiin väkisin. Käytettäessä takaisinkirjoitusta moniprosessorijärjestelmässä, eri suorittimien välimuistien on oltava yhdenmukaisia ​​(tai prosessorien on jaettava sama välimuisti).
Takaisinkirjoitusvälimuistialgoritmi

Aluksi kaikki puskurin otsikot sijoitetaan vapaalle puskuriluettelolle. Jos prosessi aikoo lukea tai muokata lohkoa, se suorittaa seuraavan algoritmin:

  1. yrittää löytää puskurin otsikon annetulla numerolla hash-taulukosta ;
  2. jos vastaanotettu puskuri on varattu, odottaa sen vapautumista;
  3. jos puskuria ei löydy hash-taulukosta, se ottaa ensimmäisen puskurin vapaan listan loppupäästä;
  4. jos vapaiden puskurien luettelo on tyhjä, suoritetaan häätöalgoritmi (katso alla);
  5. jos vastaanotettu puskuri on merkitty "likaiseksi", suorittaa puskurin sisällön asynkronisen kirjoituksen ulkoiseen muistiin.
  6. poistaa puskurin hash-taulukosta, jos se on sijoitettu siihen;
  7. asettaa puskurin hash-taulukkoon uudella numerolla.

Prosessi lukee tiedot vastaanotettuun puskuriin ja vapauttaa sen. Muokkauksen tapauksessa prosessi merkitsee puskurin "likaiseksi" ennen sen vapauttamista. Kun puskuri vapautetaan, se sijoitetaan vapaan puskuriluettelon kärkeen.

Tällä tavalla:

  1. jos prosessi lukee jonkin lohkon puskuriin, niin on erittäin todennäköistä, että toinen prosessi tätä lohkoa lukiessaan löytää puskurin RAM-muistista;
  2. tietojen kirjoittaminen ulkoiseen muistiin suoritetaan vain, kun "puhtaita" puskureita ei ole tarpeeksi tai pyynnöstä.

Siirtymäalgoritmi

Jos vapaiden puskurien luettelo on tyhjä, puskurin tyhjennysalgoritmi suoritetaan. Häätöalgoritmi vaikuttaa merkittävästi välimuistin suorituskykyyn. On olemassa seuraavat algoritmit:

  1. Toteutettu ajastimella :
    1. LRU ( englanniksi  Least Recently Used ) - pisimpään käyttämätön puskuri vaihdetaan;
    2. MRU ( englanniksi  Most Recently Used ) - viimeksi käytetty puskuri korvataan;
  2. Toteutettu laskurilla :
    1. LFU ( eng.  Least Frequently Used ) - vähiten käytetty puskuri vaihdetaan;
    2. ARC ( englanniksi  Adaptive Replacement Cache ) on IBM :n patentoimapursotusalgoritmi, joka yhdistää LRU :n ja LFU :n .

Yhden tai toisen algoritmin käyttö riippuu tiedon välimuististrategiasta. LRU on tehokkain, jos tiedot taataan uudelleenkäyttöön mahdollisimman pian. MRU on tehokkain, jos tietoja ei taatusti käytetä uudelleen lähiaikoina. Jos sovellus määrittää nimenomaisesti välimuististrategian jollekin datajoukolle, välimuisti toimii tehokkaimmin.

Käyttöjärjestelmän välimuisti

RAM-välimuisti koostuu seuraavista elementeistä:

  1. joukon RAM-sivuja, jotka on jaettu puskureihin, jotka ovat yhtä pitkiä kuin vastaavan ulkoisen muistilaitteen datalohko;
  2. joukon puskuriotsikoita, jotka kuvaavat vastaavan puskurin tilaa;
  3. hash-taulukko , joka sisältää otsikkoa vastaavan lohkonumeron;
  4. luettelot ilmaisista puskureista.

Web-sivujen välimuisti

Tietojen siirtämisessä verkon kautta voidaan käyttää web-sivujen välimuistia - prosessia, jossa usein pyydettyjä asiakirjoja tallennetaan (väli) välityspalvelimille tai käyttäjän koneelle, jotta voidaan estää niiden jatkuva lataaminen lähdepalvelimelta ja vähentää liikennettä . Näin tieto siirtyy lähemmäs käyttäjää. Välimuistia ohjaavat HTTP - otsikot.

Vaihtoehtoisesti web-sivujen välimuisti voidaan tehdä käyttämällä tietyn sivuston CMS :ää palvelimen kuormituksen vähentämiseksi suuren liikenteen aikana. Välimuisti voidaan tehdä sekä muistissa että tiedostovälimuistissa [9] . Välimuistiin tallennuksen haittapuoli on, että yhdessä selaimessa tehdyt muutokset eivät välttämättä heti näy toisessa selaimessa, joka hakee tietoja välimuistista.

Työtulosten välimuisti

Monet ohjelmat kirjoittavat jonnekin työn väli- tai aputuloksia, jotta niitä ei lasketa joka kerta, kun niitä tarvitaan. Tämä nopeuttaa työtä, mutta vaatii lisämuistia (RAM tai levy). Esimerkki tällaisesta välimuistista on tietokannan indeksointi .

Katso myös

Muistiinpanot

  1. ↑ Käteinen // Venäjän kielen suuri oikeinkirjoitussanakirja / toim. S. G. Barkhudarova , I. F. Protchenko ja L. I. Skvortsova . - 3. painos - M . : ONIKS Mir and Education, 2007. - S. 399. - ISBN 978-5-488-00924-0 . - ISBN 978-5-94666-375-5 .
  2. ↑ Suuri venäjän kielen selittävä sanakirja / Kirjoittaja, comp. ja Ch. toim. S. A. Kuznetsov. Kielellisen tutkimuksen instituutti RAS, 2000
  3. ↑ Zakharenko E. N., Komarova L. N., Nechaeva I. V. Uusi vieraiden sanojen sanakirja. M.: 2003
  4. ↑ Tietojenkäsittelytieteen selittävä sanakirja. Microsoft Press, venäläinen painos, 1995
  5. ↑ Venäjän oikeinkirjoitussanakirja: noin 180 000 sanaa [Sähköinen versio] / O. E. Ivanova , V. V. Lopatin (vastaava toimittaja), I. V. Nechaeva , L. K. Cheltsova . — 2. painos, korjattu. ja ylimääräistä - M .: Venäjän tiedeakatemia . V. V. Vinogradovin mukaan nimetty venäjän kielen instituutti , 2004. - 960 s. — ISBN 5-88744-052-X .
  6. ↑ Pershikov V.I., Savinkov V.M. Informatiikan selittävä sanakirja / Arvostelijat: Cand. Fys.-Math. Sci. A. S. Markov ja Dr. Phys.-Math. Tieteet I. V. Pottosin. - M. : Talous ja tilastot, 1991. - 543 s. – 50 000 kappaletta.  - ISBN 5-279-00367-0 .
  7. ↑ Borkovsky A. B. Englanti-venäläinen ohjelmoinnin ja informatiikan sanakirja (tulkintineen). - M . : Venäjän kieli, 1990. - 335 s. - 50 050 (lisä) kopiota.  — ISBN 5-200-01169-3 .
  8. ↑ G.C. Stierhoff, A.G. Davis. IBM Systems Journalin historia // IEEE Annals of the History of Computing. - Tammikuu 1998. - V. 20 , nro 1 . - S. 29-35 . - doi : 10.1109/85.646206 .
  9. ↑ Hajautettu käyttöjärjestelmä . Haettu 29. marraskuuta 2009. Arkistoitu alkuperäisestä 10. syyskuuta 2010.

Kirjallisuus

  • Bach M.J. UNIX-käyttöjärjestelmän arkkitehtuuri