Ersättningsalgoritmer

Ersättningsalgoritmer är policies som styr vilka minnes- eller cacherader som ska ersättas när minne eller cache är fullt och ett nytt behov uppstår. De är centrala i virtuellt minne där sidor flyttas mellan huvudminne och sekundärminne, samt i olika nivåer av cacheminne i processor- och lagringssystem. Målet är att minimera antalet missar och därigenom reducera väntetider och öka systemets genomströmning.

Ersättningsalgoritmer kan delas in i olika sammanhang, där huvudområdena är sidersättning i virtuellt minne och cacheutvärdering. Viktiga kriterier är hur en algoritm bedömer vilka sidor eller rader som är minst användbara i närtid, hur mycket information som måste hållas och hur mycket overhead som tillkommer vid uppdateringar.

Vanliga algoritmer inkluderar:

- FIFO (First-In-First-Out): ersätter den sida som först lades in i minnet. Enkel men kan leda till sämre prestanda i vissa arbetsbelastningar.

- LRU (Least Recently Used): ersätter den sida som senast användes längst. Bra sammanhang med lokalitet men kräver spårning av recency, vilket kan medföra overhead.

- Optimal (Belady’s algoritm): ersätter den sida som används längst fram i framtiden. Teoretisk referenslösning som inte kan implementeras i praktiken men används som mål att nå nära.

- Clock/Second Chance: en effektiv approximation av LRU som använder en cirkulär struktur och små flaggor för åtgård. Bra balans mellan prestanda och kostnad.

- LFU (Least Frequently Used): ersätter den minst frekvent använda, ofta med åldring för att anpassa sig över tid.

Överväganden inkluderar overhead för att spåra användning, arbetsbelastningens strukturella egenskaper, risk för thrashning och hur algoritmen passar systemets minneshierarki och krav på svarstider. Valet av ersättningsalgoritm påverkar både mängden missar och systemets övergripande prestanda.