Sartomiki.net

Algoritmi di sostituzione delle pagine
Questi algoritmi servono per gestire al meglio i page fault:
-algoritmo FIFO. Si sostituisce la prima pagina inserita (in termini di tempo assoluto) con la nuova pagina. Per l'implementazione reale dell'algoritmo è necessario un puntatore alla pagina più vecchia (vettore circolare). L'algoritmo FIFO non è sempre ottimale, in quanto alcune pagine inserite da molto tempo potrebbero in realtà contenere informazioni riguardanti variabili molto usate, inizializzate precedentemente. In più in alcuni casi si può verificare che, aumentando il numero di pagine di uno stesso processo in memoria principale, il numero di page fault aumenti (anomalia di Belady).
-algoritmo ottimo (predittivo), detto anche OPT o MIN. Si sostituiscono le pagine, in base alla stringa in ingresso, in modo da minimizzare il numero di page fault. In un caso reale non si può guardare la stringa degli accessi in anticipo (in quanto si conoscono solo le pagine usate in passato). Questo algoritmo, inapplicabile, prevede di scartare le pagine che non saranno usate per più tempo. E' utile considerare questo caso per analizzare quale sia il limite minimo di page fault in una simulazione.
-algoritmo Least Recently Used (LRU). E' un algoritmo greedy, in quanto si basa sulla località degli accessi. Questo algoritmo prevede di eliminare dalla lista la pagina non usata da più tempo. Per implementare questa tecnica è necessario un contatore per ogni frame, che memorizzi l'istante in cui è stato effettuato l'ultimo accesso (causa un accesso a memoria per ogni scrittura e un tempo alto di ricerca per trovare la pagina usata meno di recente. In più bisogna considerare l'overflow del contatore). Un metodo migliore per implementare questo algoritmo è quello che si ottiene utilizzando uno stack (implementato con una lista doppio-linkata), in cui si memorizzano in ordine gli accessi alle varie pagine. In caso di inserimento di una nuovo elemento si ha la necessità di modificare 6 indirizzi (abbastanza onerosa in quanto sono necessarie 6 scritture in memoria), mentre non si hanno tempi di ricerca O(1). Anche LRU è soggetto all'anomalia di Belady, anche se esistono alcuni algoritmi derivati che non sono soggetti a questo fenomeno. Questi algoritmi vengono detti "a pila" e per essi si può dimostrare che l'insieme di pagine per n frame è un sottoinsieme delle pagine che si troverebbero in memoria con n+1 frame. Il problema principale dell'algoritmo LRU è l'architettura necessaria per una corretta implementazione. Sono quindi usati più frequentemente altri algoritmi di sostituzione delle pagine.
-algoritmo con bit supplementari di riferimento. Molte CPU, nel momento in cui accedono ad una pagina settano un bit di riferimento. Leggendo e azzerando il bit di riferimento ad intervalli regolari è possibile stabilire la sequenza di accesso ad una determinata pagina. Questa sequenza non è univoca, ma permette di stabilire le pagine che sono state usate meno di recente e quindi procedere con la sostituzione. Nel caso in cui si prenda in considerazione solo l'ultimo bit di riferimento si hanno 2 tipi di algoritmi:
--I approssimazione di LRU. Quando si rimpiazza una pagina, si elimina una di quelle con reference bit a 0. Ogni volta che si fa accesso ad una pagina, già presente in memoria viene settato a 1 il reference bit. Esistono tecniche diverse di implementazione, ad esempio quando una pagina viene caricata in memoria principale il reference bit può essere messo a 1 o a 0.
--II approssimazione di LRU (second chance). Viene preso in considerazione il reference bit secondo una coda circolare. Si parte da un punto arbitrario e si procede sempre nello stesso verso.  Nel momento in cui si cerca una vittima, tutti i bit a 1 che si incontrano vengono messi a 0, mentre la prima pagina che ha già il reference bit a 0 viene rimpiazzata. Questo algoritmo può essere migliorato prendendo in considerazione anche il bit di modifica, che indica se la pagina sia da riscrivere in memoria secondaria o sia semplicemente da eliminare.
-algoritmo LFU, si tiene conto del numero di accessi alla pagina. La pagina che ha il numero di accessi inferiore viene eliminata. questo algoritmo ha come punto debole il caso in cui una pagina sia utilizzata molto nella fase di inizializzazione di un processo e che poi non venga più usata. Per risolvere questo problema si potrebbe pensare di scorrere i conteggi a destra di un bit ad intervalli regolari.
-algoritmo MFU, è uguale alla tecnica precedente, ma viene eliminata la pagina con il numero di accessi maggiore. Questo algoritmo si basa sul fatto che una pagina appena inserita non sia ancora stata utilizzata.

Algoritmi di allocazione dei frame
E' possibile allocare i frame con strategie diverse:
-allocazione dei frame fissa.
--paritetica (uniforme), tutti i processi hanno lo stesso numero di frame.
--proporzionale, il numero di frame è basato sulla dimensione (effettiva) del processo, in modo che tutti i processi abbiano un po' di spazio in memoria.
-allocazione dei frame a priorità. Questo metodo è simile alla allocazione fissa proporzionale, ma si basa sulla priorità di ciascun processo. La priorità si basa su diversi fattori, come l'importanza del processo, oppure in base al comportamento. In base a questo meccanismo di priorità è possibile riallocare dinamicamente la dimensione di un processo.

Allocazione locale/globale
Nel caso in cui si verifichi un page fault, i processori si possono comportare in modi differenti:
-rimpiazzamento globale, se la vittima è scelta tra tutti i frame. Questo tipo di rimpiazzamento soffre del problema che ciascun processo non possa controllare i propri page fault, anche se in realtà consente un'ottima produttività complessiva del sistema.
-rimpiazzamento locale, se la vittima è scelta tra i frame del processo che genera page fault.
-rimpiazzamento ibrido, la vittima è scelta in modo ibrido.

Thrashing
Il fenomeno del thrashing (paginazione degenere) si verifica quando il numero dei frame allocati per un determinato processo è inferiore al numero minimo richiesto dall'architettura. In questo caso si generano continuamente page fault (si fa sempre swapping). La cosa migliore da fare in questo caso è meglio terminare alcuni processi, in modo da diminuire i page fault (diminuire il grado di multiprogrammazione).
Per evitare problemi di thrashing si può usare un metodo di rimpiazzamento locale, oppure un algoritmo di sostituzione dei frame a priorità.

Working set
Il modello dell'insieme di lavoro si basa sulla località dei riferimenti. L'idea consiste nel considerare come insieme di lavoro di un processo tutte le pagine che devono essere usate dal processo stesso. Se l'insieme di lavoro è infinito, esso coincide con l'insieme di tutte le pagine a cui il processo fa riferimento. La "richiesta totale dei frame" è data dalla somma degli insiemi di lavoro di tutti i processi. Il sistema operativo, nel momento in cui un processo deve essere avviato, assegna al processo un numero di frame disponibili in base alle dimensioni del suo insieme di lavoro. Nel caso in cui lo spazio non sia disponibile, il processo non viene avviato, evitando il fenomeno del thrashing.
Il problema di implementazione di questa tecnica sta nel fatto che l'insieme di lavoro è dinamico ed è quindi difficilmente quantificabile a priori.
Grazie al working set è possible prepaginare all'avvio di un processo alcune pagine dello stesso insieme di lavoro, in modo da evitare numerosi page fault nella fase di avvio di un processo.

Frequenza di assenza di pagine
Il modello del working set è utile per implementare la paginazione, anche se non è un ottimo sistema per individuare il fenomeno del thrashing. Per questo motivo è di uso comune gestire il thrashing mediante la frequenza di assenza di pagina. Se un processo ha pochi page fault è probabile che ad esso siano stati attribuiti troppi frame, al contrario se si verificano troppi page fault è probabile che ad esso siano stati attribuiti troppi pochi frame. Si definiscono nell'architettura 2 limiti (uno inferiore e l'altro superiore), che permettono di assegnare più o meno pagine ai processi.