Sistemi operativi: risposte alle domande d'esame ed esercizi svolti

Esempio prova esame

Mercoledì 7 giugno 2023 10:04

Sincronizzazione dei processi

I semafori sono una possibile soluzione al problema della sincronizzazione dei processi. In generale un semaforo è una variabile intera per il conteggio del numero di wakeup pendenti, che può avere valore: 0 se non è stato salvato alcun wakeup, >0 se ci sono più wakeup pendenti.

Le operazioni utilizzabili sui semafori sono down() e up() (generalizzazioni di sleep e wakeup) che rispettivamente diminuiscono e aumentano i wakeup pendenti sul semaforo. In particolare le azioni corrispondenti ad up() e down() devono essere atomiche, ossia devono essere eseguite come un'unica ed indivisibile azione.

Esempio di implementazione

Un esempio della sua implementazione può essere quella per il problema del produttore-consumatore: qui si utilizzano tre semafori per mutua esclusione e sincronizzazione.

Interface Semaforo {
    void down();
    void up();
}
public static Semaforo getDefaultSemaforo(int n) {
    Semaforo nuovo = new MioSemaforo(n);

Algoritmi di gestione della memoria

• Algoritmo ottimale: Impossibile da implementare. Consiste nel sostituire la pagina che non sarà utilizzata per più tempo (poiché non è possibile sapere in anticipo le pagine che verranno richieste è irrealizzabile). Questo algoritmo avrebbe la frequenza di page-fault minima, inoltre non soffre dell'anomalia di Belady. Può essere utilizzato insieme ad un algoritmo di predizione delle pagine, ma in generale è utilizzato solo come riferimento.
• Algoritmo NRU (not recently used): Per implementare questo algoritmo il sistema si avvale di due informazioni sulle pagine presenti in memoria centrale; mantiene memorizzati nella tabella delle pagine due bit di stato per ciascuna pagina: bit RB (o R) posto a 1 ogni volta che la pagina viene riferita; Bit D (o M) che vale 1 se la pagina dal momento in cui è stata caricata in memoria centrale è stata modificata (se vale 0 in caso di selezionamento per il page-fault si effettua solo uno swap-in, cioè viene sovrascritta poiché in memoria di massa è presente già uguale). Entrambi questi due bit sono aggiornati direttamente dall'hardware ogni volta che la pagina viene riferita. Due bit vengono utilizzati come criterio di scelta della pagina da sostituire, a seconda del loro valore sono individuate delle classi di pagine diverse: quelle ad avere la maggior probabilità di essere sostituite hanno RB=0 e D=0. Quelle meno convenienti hanno RB=1 e D=1.
• Algoritmo LRU (last recently used): Si basa sull'idea che le pagine che sono state frequentemente usate nelle ultime istruzioni lo saranno anche nelle prossime istruzioni, mentre quelle non utilizzate da lungo tempo non lo saranno ancora per lungo tempo. Per tenere traccia del tempo l'algoritmo è implementato aggiungendo ad ogni entrata nella tabella della pagine un campo che indica il tempo ogni volta che una pagina viene riferita. La CPU deve mantenere aggiornato un contatore, incrementato ad ogni istruzione, che tiene traccia del tempo che passa ed è utilizzato per aggiornare il campo nella tabella. Il sistema seleziona la pagina che ha il tempo minore. Non è molto vantaggioso per vari motivi (devono essere aggiunte informazioni nella tabella che ne aumentano la dimensione, per selezionare la pagina il sistema deve fare una scansione di tutta la lista, occorre stabilire un numero di bit per il contatore che non sia troppo grande per aumentare troppo la dimensione della tabella e che non sia troppo piccolo per contenere il valore del contatore).
• Algoritmo con bit supplementari di riferimento (NFU) (not frequently used): Approssimazione del LRU che si ottiene memorizzando ad intervalli regolari bit di riferimento delle pagine, l'algoritmo seleziona la pagina da più tempo non riferita. Questo algoritmo tiene traccia della frequenza con cui vengono riferite le pagine anche attraverso il bit RB. Il sistema mantiene una tabella in memoria contenente per ogni pagina un registro in traslazione che funziona da contatore. Periodicamente una routine va in esecuzione e, per ogni pagina, trasla il contenuto del registro a destra e inserisce il valore del bit RB a sinistra. Quando si verifica un page-fault, il sistema seleziona per il rimpiazzamento la pagina con il contatore più basso.
• Algoritmo con bit di riferimento a seconda chance: Con una semplice modifica dell'algoritmo FIFO è possibile evitare il problema della rimozione di pagine molto utilizzate. Viene controllato il bit RB della pagina più vecchia: se vale 0 la pagina viene sostituita; se vale 1 il bit viene azzerato e la pagina viene messa in coda alla lista come se fosse appena arrivata in memoria e viene consultata la pagina successiva fino a quando non se ne trova una con RB=0 che verrà sostituita. L'algoritmo si basa sulla ricerca di una pagina che non sia stata referenziata nell'ultimo giro di clock; se tutte le pagine sono state referenziate nel giro di clock allora sfocia nel FIFO puro.
• Algoritmo di CLOCK: (come seconda chance con lista circolare) Il sistema realizza questo algoritmo utilizzando una lista circolare di pagine o di descrittori di pagina. Ad ogni pagina associa un bit RB che inizialmente è settato ad 1. Quando si verifica un page-fault il sistema scansiona la lista partendo da dove si trova il puntatore della lista e ogni volta che individua una pagina con RB=1 lo setta a 0 e prosegue fino a quando non trova una pagina con RB=0 (non necessariamente quella non più tempo) che viene scelta per il rimpiazzamento. Alla prima scansione, quando tutte le pagine hanno RB=1, prima vengono settate tutte con RB=0 e poi viene rimpiazzata la prima della lista.
• Modello a Working Set (prepaging): A differenza degli altri algoritmi questo modello non utilizza la paginazione su richiesta, ma il prepaging. Poiché la maggior parte dei processi esibiscono la località degli accessi (durante qualsiasi fase dell'esecuzione il processo fa riferimento ad un piccolo insieme di pagine) prima di eseguire un processo viene caricato in memoria centrale il working set del processo. In generale invece di inserire una sola pagina in memoria ad ogni richiesta, si inseriscono più pagine in modo da avere più pagine possibili del working set in memoria centrale, così da ridurre i page-fault.

Thrashing e paging demon

Quando un programma causa page-fault per ogni piccolo insieme di istruzioni viene detto in thrashing, cioè in memoria sono presenti troppi processi. Per evitare il thrashing viene utilizzato un processo chiamato Paging Demon che è eseguito in background e che periodicamente controlla lo stato della memoria e, se il numero di frame liberi in memoria non è sufficiente, si occupa di selezionare le pagine da eliminare (secondo un algoritmo scelto). La memoria secondaria rappresenta la parte più bassa del file system.