Cache Replacement Policy — cache setdagi barcha way band bo‘lganda yangi satr uchun qaysi mavjud entry chiqarilishini tanlaydigan qoida. To‘g‘ri tanlov yaqin kelajakda qayta ishlatilmaydigan satrni qurbon qiladi; noto‘g‘ri tanlov esa tez orada kerak bo‘ladigan data’ni chiqarib, qo‘shimcha miss va trafik keltiradi.
Asosiy algoritmlar
LRU eng uzoq vaqt ishlatilmagan satrni tanlaydi. Kichik associativity’da aniq tartib yuritish mumkin, katta keshda metadata va update yo‘li qimmatlashadi. Pseudo-LRU daraxt yoki bitlar bilan taxminiy tanlov beradi. Random sodda, tez va ayrim takrorlanuvchi adversarial patternlarga chidamli.
FIFO kirish vaqtini, MRU esa eng yaqin ishlatilgan satrni mezon qiladi. Optimal Belady algoritmi kelajakda eng kech ishlatiladigan satrni chiqaradi, ammo kelajakni bilmagani uchun real apparatda qo‘llanmaydi; u simulyatsiyada taqqoslash chegarasi sifatida xizmat qiladi.
Zamonaviy bashorat
Reuse-aware siyosat satrning qayta murojaat masofasini yoki program counter tarixini o‘rganadi. Streaming access bir marta ishlatiladigan satrlarni past priority bilan joylashtiradi. Hot satrlar uzoqroq saqlanadi. Dynamic insertion policy bir nechta setda turli strategiyani sinab, kam miss berganini qolgan setlarga qo‘llaydi.
Prefetch satri demand satr bilan bir xil qiymatga ega bo‘lmasligi mumkin. Noto‘g‘ri prefetch foydali data’ni chiqarmasligi uchun insertion position past bo‘ladi. Prefetch keyin demand bilan ishlatilsa uning priority’si oshiriladi.
Dirty va coherence omillari
Dirty victim quyi darajaga write-back talab qiladi, clean victim esa tez chiqariladi. Faqat clean satrni tanlash yozuv bandwidthini tejaydi, biroq issiq clean satrni yo‘qotishi mumkin. Cost-aware algoritm reuse ehtimoli bilan write-back xarajatini birga baholaydi.
Pinned, locked yoki coherence tranzaksiyasidagi way victim bo‘la olmaydi. Shared LLC partition mask bo‘yicha faqat request egasiga ruxsat etilgan way’lardan tanlaydi. Inclusive cache eviction private nusxalarni back-invalidate qilishi sabab victim narxi yanada katta bo‘lishi mumkin.
Baholash
Replacement samarasi miss rate, write-back, pollution va critical miss latency bilan o‘lchanadi. Bir workload’da yaxshi siyosat boshqasida yomon bo‘lishi mumkin. Trace-driven simulyatsiya ko‘p variantni tez taqqoslaydi, full-system tajriba esa coherence va timing ta’sirini ko‘rsatadi.
Metadata update’lari parallel hit, fill va invalidation bilan race qilmasligi kerak. Formal invariant bir setda valid entrylar, reserved way va replacement holati izchil qolishini tekshiradi. Performance uchun tanlov arxitektura correctnessini hech qachon buzmasligi lozim.
Policy’ni xavfsizlik nuqtai nazaridan ham baholash mumkin. Deterministik LRU boshqa context accessi haqida aniqroq timing izi berishi, random tanlov esa shovqin qo‘shishi mumkin, lekin randomning o‘zi himoya emas. Tenant isolation uchun replacementdan tashqari way partition, scheduling va memory mapping nazorati kerak.
Replacement qarori talab yo‘lidagi kritik latencyga aylanmasligi uchun victim ko‘pincha fill kelishidan oldin tanlanadi. Keyingi hit tanlangan way’ni qayta faollashtirsa controller victimni almashtirishi yoki requestni qayta boshlashi kerak.
Fill cancellationda ajratilgan way va metadata eski valid satrni tasodifan yo‘qotmasdan rollback qilinadi. Bu hodisa coherence retry bilan birga sinovdan o‘tadi.
Shuningdek, invalidation bilan bir vaqtdagi hit eski metadata’ni qayta tiriltirmasligi kerak.
Bu xususiyat alohida sinovdan o‘tkaziladi.
Bog‘liq tushunchalar
LRU, pseudo-LRU, cache eviction, associativity, reuse distance, cache pollution