Menu Chiudi

Clock Algorithm

Condividi questo articolo:

Il Clock Algorithm, chiamato anche Second Chance Algorithm, è un algoritmo usato per la politica di rimpiazzamento delle pagine in un buffer di un DBMS.

Si tratta di un’euristica che emula la politica LRU (Least Recently Used).  

In queste pagine proponiamo una semplice implementazione su Scratch di questo algoritmo.

I rettangoli azzurri rappresentano le pagine che vengono disposte 
in modo circolare, come se fossero su una corona di un orologio.
Con i tasti – e +, presenti in ogni pagina azzurra, aumentiamo il PinCount 
che ci indica quanti stanno utilizzando quella determinata pagina.

Mentre la nostra lancetta gira possiamo diminuire o aumentare il PinCount relativo a quella pagina simulando l’utilizzo della stessa da parte di uno o più processi (e.g.: se il PinCount è uguale a 2 vuol dire che la stanno usando due processi).

Quando nessuno la sta più utilizzando, cioè quando il PinCount è uguale a zero, allora il ReferBit della relativa pagina viene posto a 1, questo sta ad indicare che la pagina è candidata ad essere rimpiazzata, ma questa verrà scalzata solo se la pagina non verrà richiesta da nessun altro processo per tutto un intero giro della lancetta. 

Non è stata implementata la sostituzione della pagina e l’avvento di una nuova. In questa implementazione quando la pagina viene rimossa ne compare subito un’altra dello stesso colore. 

ECCO IL LINK PER VEDERE IL CODICE E TESTARE IL PROGRAMMA DIRETTAMENTE ONLINE: https://scratch.mit.edu/projects/458881467

(Il programma ha solo scopi didattici).

www.nicolapalmeri.it

https://en.wikipedia.org/wiki/Page_replacement_algorithm
https://en.wikipedia.org/wiki/Page_replacement_algorithm

Clock Algorithm

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *