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.
Vanliga algoritmer inkluderar:
- FIFO (First-In-First-Out): ersätter den sida som först lades in i minnet. Enkel men kan leda till
- LRU (Least Recently Used): ersätter den sida som senast användes längst. Bra sammanhang med lokalitet men
- Optimal (Belady’s algoritm): ersätter den sida som används längst fram i framtiden. Teoretisk referenslösning som inte
- Clock/Second Chance: en effektiv approximation av LRU som använder en cirkulär struktur och små flaggor för
- LFU (Least Frequently Used): ersätter den minst frekvent använda, ofta med åldring för att anpassa sig
Överväganden inkluderar overhead för att spåra användning, arbetsbelastningens strukturella egenskaper, risk för thrashning och hur algoritmen