Sistemi operativi: domande base esame con soluzioni

Thread a livello kernel e thread a livello utente

SO2. La commutazione tra i thread non richiede l'intervento del nucleo.

Lo scheduling dei thread è indipendente da quello del nucleo.

Lo svantaggio del loro utilizzo è invece il fatto che le chiamate di sistema sono bloccanti e i vari thread non possono essere eseguiti parallelamente su diversi core di elaborazione. Inoltre non si sfrutta un eventuale parallelismo hardware.

Con i thread a livello kernel invece sono gestiti dal SO e le chiamate di sistema non sono bloccanti per l'intero processo, ma bloccano solo il thread che ha effettuato la chiamata. Permettono inoltre di eseguire i thread di uno stesso processo su diverse unità di elaborazione (non è che se ho 4 CPU vado 4 volte più veloce, in condizioni ottime ci si avvicina).

Nei thread a livello kernel il tempo di elaborazione della CPU è distribuito equamente per ogni thread (ogni thread riceve lo stesso tempo di CPU), mentre nei thread a livello utente ho che due processi A e B ricevono lo stesso tempo di CPU.

stesso tempomacchina, diviso equamente tra i processi (ogni processo riceve lo stessotempo di CPU).

Deve sempre esistere una relazione tra i thread a livello utente e quelli a livellokernel, e ci sono 3 opzioni di modelli di programmazione multithread:

1. MODELLO DA MOLTI A UNO: molti thread a livello utente sono mappati inun singolo thread a livello kernel. Tuttavia, l’intero processo rimane bloccato nelmomento in cui un thread effettua una chiamata di sistema di tipo bloccante.Inoltre, poiché un solo thread alla volta può accedere al kernel, è impossibileeseguire vari thread parallelamente su diverse unità di elaborazione.
2. MODELLO DA UNO A UNO: fa corrispondere un thread a livello utente ad unthread a livello kernel. In questo modo, se un thread effettua una chiamata disistema di tipo bloccante risulterà bloccato solo quel thread e non l’interoprocesso. Inoltre, più thread potranno essere eseguiti parallelamente su diversicore di elaborazione.

Lo svantaggio è che per ogni thread a livello utente dovrà essere creato un thread anche a livello kernel, che può sovraccaricare le prestazioni di un'applicazione (quindi molte realizzazioni di questo modello limitano il numero di thread supportabili dal sistema).

MODELLO DA MOLTI A MOLTI: fa corrispondere molti thread a livello utente ad un numero minore o uguale di thread a livello kernel. Se un thread invoca una chiamata di sistema di tipo bloccante, il kernel può schedulare un altro thread.

MODELLO A DUE LIVELLI: Simile al modello molti a molti, ma permette ad un particolare thread utente di essere associato ad un particolare thread del nucleo. Utile nel caso in cui fossero richieste prestazioni particolari per certi scopi.

9. Condizioni necessarie per il verificarsi di un deadlock

Esistono potenziali conflitti tra i processi che utilizzano risorse condivise. La maggior parte delle risorse prevede un utilizzo esclusivo (es. CD-ROM), ma non necessariamente i

deadlock coinvolgono dispositivi di I/O (es. database in rete). I deadlock possono verificarsi quando i processi ottengono accessi esclusivi a determinate "risorse" (dispositivi o oggetti software). Le risorse possono essere di diverso tipo, ma vengono comunemente classificate in due tipi diversi:

1. risorse "con prerilascio": possono essere tolte ai processi senza problemi (es. memoria, CPU)
2. risorse "senza prerilascio": se vengono tolte ai processi si ha il fallimento dell'elaborazione (es. stampanti)

In generale i deadlock coinvolgono risorse senza prerilascio. La sequenza dei passi necessari per l'uso di una risorsa è: 1) richiesta, 2) uso, 3) rilascio (se la risorsa non è disponibile il processo viene messo in attesa, talvolta viene risvegliato automaticamente quando la risorsa torna disponibile). Nei casi in cui la richiesta di una risorsa è bloccante, spesso la risorsa viene protetta dal SO tramite meccanismi di<p>sincronizzazione (come un semaforo).“Un insieme di processi è in deadlock se ogni processo dell’insieme è in attesadi un evento che solo un altro processo appartenente allo stesso insieme puòcausare”Un processo in deadlock non procede e non termina mai la sua esecuzione(processi in deadlock possono bloccare l’intero sistema).</p> <p>Le condizioni necessarie per avere una situazione di stallo sono 4 e devonoverificarsi contemporaneamente:</p> <ol> <li>MUTUA ESCLUSIONE: almeno una risorsa non deve essere condivisibile(ossia utilizzabile da un solo processo alla volta)</li> <li>POSSESSO E ATTESA: un processo deve essere in possesso di almeno unarisorsa e attendere di acquisire risorse già in possesso di altri processi.</li> <li>ASSENZA DI PRELAZIONE: le risorse possono essere rilasciate solo dalprocesso che le detiene, il rilascio non può essere forzato</li> <li>ATTESA CIRCOLARE: deve esistere un insieme di processi (Po, P1, P2, …, Pn)tale che Po attende una risorsa</li> </ol>

Posseduta da P1, P1 una posseduta da P2, ecosì via (ossia una lista circolare di processi/risorse coinvolti dal deadlockstesso).

10. Descrivere le funzioni dell’MMU (Memory Management Unit)

La parte del SO che gestisce la memoria ha compiti:

• Tenere traccia di quali parti di memoria sono in uso e quali non lo sono
• Allocare la memoria ai processi che la necessitano e deallocarla
• Gestire lo swapping tra la memoria principale e il disco quando la memoria principale non è sufficientemente grande per mantenere tutti i processi

In qualsiasi computer, ogni programma può produrre indirizzi di memoria. Questi indirizzi generati dal programma sono detti indirizzi virtuali e formano lo spazio di indirizzamento virtuale. Nei computer senza memoria virtuale, l'indirizzo virtuale viene messo direttamente sul bus di memoria. Quando viene utilizzata la memoria virtuale, gli indirizzi virtuali non vengono mandati direttamente sul bus di memoria, ma vengono inviati alla

Memory Management Unit (MMU), un chip che mappa gli indirizzi virtuali sugli indirizzi della memoria fisica.

La memoria fisica è divisa in blocchi di dimensione fissa (detti frame) e si suddivide la memoria logica in blocchi di pari dimensione (dette pagine).

I trasferimenti fra la memoria ed il disco avvengono sempre per unita di pagina.

Quando si deve eseguire un processo, si caricano le sue pagine nei frame disponibili. Alcune pagine virtuali quindi non avranno corrispondenza in memoria fisica e negli attuali circuiti hardware un bit presente/assente è utilizzato per indicare se la pagina è mappata sulla memoria fisica oppure no.

Se una pagina non mappata in memoria fisica viene richiesta, la MMU genera un interrupt della CPU al SO chiamato PAGE FAULT, dopo il quale il SO sceglie un frame di pagina poco utilizzato e salva il suo contenuto su disco, quindi recupera la pagina referenziata e la alloca nel frame appena liberato (fetching della pagina), cambia la mappa e riparte.

con l'istruzione bloccata. Supponiamo che l'indirizzo virtuale sia di 16 bit e sia diviso in due parti. 4 bit rappresentano il numero di pagina, che serve come indice nella tabella delle pagine cosi da ottenere l'indirizzo fisico, mentre gli altri 12 rappresentano l'offset che deve essere sommato all'indirizzo di base per trovare l'indirizzo corretto in memoria fisica e che viene inviato all'unità di memoria.

• Se il bit presente/assente è 0 viene causata una eccezione
• Se il bit presente/assente è 1 il numero del frame trovato nella tabella delle pagine viene copiato nei 3 bit di ordine alto del registro di output con i 12 bit dell'offset (copiati senza modifiche dall'indirizzo virtuale)
• Il contenuto del registro di output viene messo sul bus di memoria come indirizzo di memoria fisica.

Il modello descritto è semplice, vi sono però dei problemi: la tabella delle pagine può essere molto grande,Il mapping (da virtuale a fisico) deve essere veloce. Il modello più semplice consiste di una singola tabella delle pagine costituita da un array di registri hardware con un elemento per ogni pagina virtuale indicizzato dal numero di pagina virtuale. Quando viene iniziato un processo, il SO carica la sua tabella delle pagine nei registri. Vantaggi: il mapping è immediato, nessun riferimento in memoria. Svantaggi: il mapping è potenzialmente costoso (se la tabella delle pagine è grande) e il caricamento della tabella delle pagine nei registri ad ogni context switch può alterare le prestazioni (si noti che deve esistere una tabella diversa per ogni processo). All'estremo opposto la soluzione è mantenere la tabella delle pagine interamente in memoria. L'hardware necessario è un singolo registro che punta all'inizio della tabella delle pagine. Vantaggi: consente di modificare la mappa di memoria ad un context switch ricaricando un solo registro. Svantaggi:durante l'esecuzione di un'istruzione richiede uno o più riferimenti in memoria per leggere gli elementi della tabella delle pagine. 11. Algoritmi di rimpiazzamento delle pagine in memoria Per ogni page fault, il SO deve scegliere una pagina da rimuovere dalla memoria per creare spazio per la nuova pagina. Scegliere la pagina da rimpiazzare con un algoritmo per sostituire pagine poco utilizzate può portare a un miglioramento delle prestazioni. Se la pagina da rimuovere è stata modificata, la copia su disco deve essere aggiornata, se non c'è stata alcuna modifica, la nuova pagina sovrascrive quella da rimuovere. - Algoritmo ottimo: a ogni pagina viene assegnata un'etichetta corrispondente al numero di istruzioni che dovranno essere eseguite prima che quella pagina venga referenziata. L'algoritmo ottimo consiste nel rimuovere la pagina con etichetta maggiore, cioè la pagina che verrà referenziata tra più tempo. Non è

però realizzabile nella realtà, perché non è possibile conoscere a priori, al momento del page fault, quali pagine verranno referenziate.

Algoritmo FIFO: quando avviene un page fault, viene rimossa la pagina che si trova in memoria da più tempo. Questo algoritmo soffre dell'anomalia di Belady: aumentando il numero di frame e usando questo algoritmo, il numero di page fault può aumentare. L'algoritmo FIFO in questa forma viene utilizzato raramente: infatti, non è detto che la pagina più vecchia sia anche la meno utilizzata.

Algoritmo NRU: a ogni pagina vengono associati due bit: un bit R che indica che la pagina è stata referenziata e un bit M che indica che la pagina è stata modificata. Inizialmente i bit R e M vengono inizializzati a 0 dal SO. Periodicamente (ad esempi