Clock Replacement
ক্লক রিপ্লেসমেন্ট
LRU-র সস্তা approximation — বৃত্তাকার ঘড়ির কাঁটা ঘুরিয়ে reference bit দেখে victim page বাছা।
also: clock-sweep, second-chance
Algorithm: কাঁটা ঘোরে, reference bit 1 দেখলে 0 করে এগোয় (second chance), 0 পেলে সেই page-ই victim।
while frame.ref_bit:
frame.ref_bit = 0
hand = (hand + 1) % n # আরেকবার সুযোগ দিলাম
return frames[hand] # bit 0 — এটাই ফেরবে- LRU-র linked-list bookkeeping নেই — শুধু এক bit + এক pointer, O(1) amortized
- Sequential flood-এ LRU পুরো pool ধুয়ে ফেলে; clock-ও ক্ষতিগ্রস্ত, কিন্তু usage count বাড়ার সুযোগ থাকায় কম
- PostgreSQL ব্যবহার করে clock sweep — usagecount এই bit-এরই সংখ্যাযুক্ত রূপ