LRU er en mye brukt prioriteringsalgoritme til lagerplass i datamaskiner. LRU står for Least Recently Used, som kan oversettes med «lengst siden brukt» eller lengst ubrukt. Av de objekter som i øyeblikket har en lagerressurs, er det objektet som er lengst ubrukt som mister plassen når et nytt objekt uten plass blir aktivert.

Faktaboks

Også kjent som

Least Recently Used

Hensikt

Forskjellige lagertyper kan ordnes i et hierarki etter hastighet og kostnad per lagret enhet. De hurtigste lagrene er små og kostbare. Hovednivåene hierarkiet er: cacheCPU-brikken, cache utenfor CPU-brikken, arbeidslager, disk og nederst: magnetbånd. Disk og magnetbånd er permanent lager, mens cache og arbeidslager mister innholdet når strømforsyningen slås av. Data som skal brukes, hentes opp til et raskere medium. LRU-algoritmen skal bidra til at det er de mest aktive data som får plassen på det hurtigste mediet for å øke systemytelsen.

Virkemåte

LRU-algoritmen vedlikeholder en prioritetsliste av objekter som i øyeblikket er tildelt den etterspurte ressurs; en cachelinje eller en buffer i arbeidslager for data på disk eller magnetbånd og en plass på disk for data som normalt er lagret på magnetbånd. Hver gang et objekt blir brukt, får det høyeste prioritet. Objekter som ikke blir brukt taper prioritet etter hvert. Når et nytt objekt skal ha plass, mister objektet med lavest prioritet sin ressurs. LRU funger godt når en gruppe objekter blir gjenbrukt i en avgrenset periode. LRU fungerer maksimalt dårlig ved fortløpende lesing; objektet som blir lest kommer ikke til å bli lest igjen på lenge.

Realisering

Dataobjektenes størrelse avhenger av nivået: For cache er det en linje med dataord; 16 til 128 byte, i arbeidslager er det normalt en blokk av fast størrelse fra 4 kB til 512 kB, og for disk kan det være en hel fil. For cache og blokker som brukes i kravstyrt sidedeling (demand paging) skal LRU-data (prioritetslisten) oppdateres for hver lagerreferanse som CPU gjør. Det betyr at LRU-data må oppdateres direkte av innebygd elektronikk. Når en blokk brukes i et filsystem eller filer overføres fra magnetbånd til disk, har en så mye tid til rådighet at alt kan utføres i programvare.

I maskinvare kan en realisere en forenklet LRU – eller mer generelt en «aldringsalgoritme». Hver gang cachelinjen eller blokken blir lest eller skrevet, settes en «referert til bit». Når en blokk eller cachelinje kan skifte eier, testes blokkene eller cachelinjene i gruppen syklisk: Hvis «referert til bit» er satt spares ressursen, men «referert til bit» nulles og neste ressurs testes. Hvis «referert til bit» fortsatt er null blir dette offeret som skifter eier. Denne algoritmen kalles også klokkealgoritmen fordi den sykliske testingen kan sees som en viser som går rundt. Så lenge objektet blir brukt før viseren kommer tilbake beholder objektet ressursen.

I programvare vedlikeholdes en prioritetsstakk realisert som en dobbeltlenket sirkulær liste.

Les mer i Store norske leksikon

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

Du må være logget inn for å kommentere.

eller registrer deg