LRU er navnet på 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.

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: cache CPU-brikken, cache utenfor CPU-brikken, arbeidslager, disk og nederst: magnetbånd. Disk og magnetbånd er permanent lager, 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.

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.

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. 

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål om artikkelen? Skriv her, så får du svar fra fagansvarlig eller redaktør.

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