Sistemi operativi: domande base esame con soluzioni

Argomenti base esame di sistemi operativi

Ingegneria informatica ed elettronica

• Macchine virtuali
• Paravirtualizzazione
• Stati di processi
• Fork ed exec
• Algoritmi di scheduling dei processi (FCFS, SJF, RR, con priorità, garantito, real-time)
• Semafori
• Monitor
• Gestione thread a livello utente ed a livello nucleo
• Deadlock e condizione necessaria per un deadlock
• MMU
• Algoritmi del page fault (ottimo, FIFO; tutti tranne clock)
• Working set
• I-node (cosa è)
• I/O
• Soft-link e Hard-link
• Algoritmi di scheduling disco (FCFS, SS, SST, Cscan, ride)
• Allocazione di file contigua e con lista indicizzate
• Paginazione multilivello
• Stenografia
• Cifratura a chiave asimmetrica
• Disabilitazione interrupt (alla fine)
• Algoritmo del banchiere (sicuro, non sicuro)
• Starvation
• Buddy System
• Cosa è un page fault
• Barriere

1. Macchine virtuali

I sistemi operativi e le applicazioni che funzionano su di una macchina virtuale vengono eseguiti in un ambiente che ha anche funzioni di protezione e limitazione. L'obiettivo di una VM è di permettere l’esecuzione di ambienti differenti sulla stessa macchina, con la particolarità che ognuno di questi essi ha la parvenza di avere il completo utilizzo dell'hardware fisico. In questo modo si riescono a eseguire diversi sistemi operativi (ognuno all'interno di una VM) contemporaneamente su una sola macchina fisica.

Per fare ciò è necessaria la presenza dell'hypervisor: esso si occupa della creazione delle VM e fornisce ad ognuna di esse un'interfaccia grazie alla quale l'ambiente virtuale può "vedere" l'hardware della macchina host. Esistono diversi tipi di hypervisor:

Tipo 1

Le VM possono utilizzare l'hardware grazie all'interfaccia messa a disposizione dall'hypervisor. È una sorta di SO che viene lanciato al momento del boot, ha il completo controllo dell’hardware. La comunicazione tra macchine virtuali e hardware è diretta e passa solamente attraverso l'hypervisor.

Tipo 2

Viene introdotto un nuovo livello tra le VM e l'hardware, ossia il sistema operativo dell'host. Può controllare diverse VM e funziona in modalità utente (come una normale app).

Vantaggi:

• Bloccare lo stato della VM per poi recuperarlo in seguito
• Parti semplici, flessibili e facili da mantenere
• Completa protezione delle risorse di sistema
• Rende facile lo sviluppo di un SO

Svantaggio: l’isolamento della VM rende complessa la condivisione di risorse. Ciò si supera con la creazione di reti di VM virtuali, il NAT DHCP permette di avere una protezione delle VM rispetto alla rete virtuale.

Gestione delle chiamate di sistema

Esistono 3/4 modalità: Utente virtuale, Kernel virtuale, [utente fisico], kernel fisico. Quando si esegue un'istruzione privilegiata nella modalità utente di un sistema ospite si provoca una TRAP (eccezione) che viene gestita dal kernel fisico, dopodiché il controllo torna all'utente virtuale. L'ambiente ospite ha in questo modo l'illusione che la chiamata sia stata gestita dal kernel virtuale.

2. Caratteristiche principali della paravirtualizzazione

L'ambiente ospite non ha più l'illusione di avere a disposizione il completo hardware, ma ha a disposizione delle speciali API con funzionalità molto simili a quelle fisiche dell'host. Per questo motivo il sistema operativo guest non può essere lo stesso della virtualizzazione classica, ma il suo kernel deve essere invece necessariamente modificato (per permettere un corretto funzionamento delle API).

Il SO ospitato deve essere modificato, se una istruzione di questo sistema genera una TRAP, ne deve gestire le conseguenze. Questo metodo può venir visto come una sorta di binary rewriting, con la differenza che viene eseguito a tempo di compilazione, anziché di esecuzione (come nel binary rewriting).

Queste modifiche SO riguardano ad esempio le hypercall, ossia chiamate che il sistema guest esegue per interagire con le risorse fisiche del sistema (queste chiamate vengono indirizzate all'hypervisor che se ne occupa). Nella paravirtualizzazione non si ha la completa emulazione dell'hardware e di conseguenza un blocco di un sistema guest potrebbe avere ripercussioni anche sulle altre macchine ospitate (ed eventualmente sull’host stesso).

Quando il SO guest prova ad eseguire istruzioni privilegiate, il VMM “intrappola” l’operazione e le esegue correttamente, effettuando quindi hypercall per interagire con le risorse del sistema. L’hypervisor controlla ed interrompe eventuali attività pericolose.

Tra gli altri, i vantaggi della virtualizzazione che i sostenitori della tecnologia vedono in questa soluzione ben progettata sono di riduzione dei costi consolidando l’hardware. L’hypervisor alloca le risorse dinamicamente quando e dove necessario, riduce in modo drastico il tempo necessario alla messa in opera di nuovi sistemi, isola l’architettura nel suo complesso da problemi a livello di sistema operativo ed applicativo.

3. Descrivere gli stati dei processi e le loro transizioni

Un processo, durante la sua esecuzione, è spesso soggetto a cambiamenti di stato:

• NUOVO: il processo è appena stato creato
• PRONTO: il processo attende di essere assegnato alla CPU
• ESECUZIONE: il processo è stato assegnato alla CPU
• BLOCCATO: il processo è in attesa del verificarsi di un evento (es. completamento I/O)
• TERMINATO: il processo ha terminato la propria esecuzione

Nel diagramma delle code è descritto il possibile ciclo di esecuzione di un processo. Nel momento in cui un processo viene creato e diventa pronto, esso viene inserito nella ready “queue” (coda), dove attende di essere assegnato alla CPU. Una volta assegnato alla CPU, il processo può interrompere la propria esecuzione per una serie di ragioni:

• Esecuzione → Bloccato: Il processo richiede una operazione di I/O al SO, quindi rilascia la CPU e entra nella coda per utilizzare un particolare dispositivo di I/O
• Il processo crea un processo figlio e quindi deve attendere che la sua esecuzione termini
• Il processo esaurisce il quanto di tempo assegnatogli, quindi la CPU gli viene sottratta e viene reinserito nella ready queue
• Il processo può essere rimosso forzatamente dalla CPU a causa di un’interruzione ed essere reinserito nella coda dei processi pronti

Nei primi due casi, al completamento della richiesta di I/O o al termine del processo figlio, il processo passa dallo stato d’attesa allo stato pronto ed è nuovamente inserito nella ready queue. Un processo continua questo ciclo fino al termine della propria esecuzione.

N.B. Il passaggio da esecuzione a pronto si ha solamente in un sistema con prelazione.

N.B.B. Il metodo di scheduling Round Robin è considerato a prelazione (a fine del quanto il processo passa da esecuzione a pronto, se ha ancora operazioni da svolgere).

4. Chiamate di sistema fork ed exec

In Unix, la chiamata di sistema fork() duplica il processo padre, creando un processo figlio identico (il cui spazio degli indirizzi sarà una copia di quello del processo padre). La fork restituisce il valore del pid del figlio al padre, e 0 al figlio (così che si renda conto di esser tale).

Generalmente, dopo una chiamata di sistema fork(), uno dei due processi impiega una chiamata di sistema exec() per sostituire lo spazio di memoria del processo con un nuovo programma. La chiamata di sistema exec() carica in memoria un file (passato come parametro), cancellando l’immagine di memoria del programma contenente la stessa chiamata di sistema exec(), quindi avvia la sua esecuzione. Viene inoltre azzerato lo stack.

Il processo genitore può anche generare più processi figli, oppure, se durante l’esecuzione del processo figlio non ha nient’altro da fare, può invocare la chiamata di sistema wait() per rimuovere se stesso dalla coda dei processi pronti fino alla terminazione del figlio.

Exec è in realtà una famiglia di primitive, con numerose varianti (execl, execle, execlp, execve) che differiscono nel numero e nella tipologia di parametri richiesti. In ogni caso, l’ultimo parametro passato a queste funz. (execl) deve esser necessariamente un puntatore NULL per far capire al programma che son finiti i parametri (ciò vale anche con i vettori). Nel caso della programmazione multithread, la fork() può avere due esiti differenti: se è seguita immediatamente da una exec(), essa si limita a duplicare unicamente il thread che ha invocato la fork(), altrimenti duplica tutti i thread del processo padre.

5. Descrivere gli algoritmi di scheduling dei processi

Gli algoritmi di scheduling offrono allo scheduler del SO delle modalità per selezionare la sequenza con cui i processi vengono assegnati alla CPU. La decisione di scheduling della CPU può avvenire quando un processo:

• Termina
• Passa da Esecuzione → Attesa
• Passa da Esecuzione → Pronto
• Passa da Attesa → Pronto

Nota che 1 e 4 sono non-preemptive, mentre 2 e 3 lo sono.

Il dispacher è il modulo che dà il controllo della CPU al processo selezionato dallo scheduler.

FCFS (First Come, First Served)

Implementa il concetto di coda tradizionale. La CPU viene assegnata al processo che la richiede per primo. Quando un processo entra nella ready queue, si collega il suo PCB (Process Control Block) all’ultimo elemento della coda. Quando la CPU è libera, essa viene assegnata al processo che si trova alla testa della coda, rimuovendolo da essa. Il tempo medio di attesa risulta essere generalmente lungo. Per ottenere un tempo di attesa medio minore possibile, è meglio eseguire prima i processi più brevi.

SJF (Shortest Job First)

Garantisce sempre il minimo tempo medio di risposta. Serve determinare quali tra i processi eseguibili è il più breve. Se arriva un nuovo processo con un CPU burst atteso più breve del tempo rimanente per il processo corrente, il nuovo processo ottiene la CPU. Se due processi hanno sequenze con la stessa lunghezza, l’algoritmo si riduce a un FCFS.

Si sfrutta l’ “aging”, tecnica per la stima del valore successivo in una serie basata sul calcolo della media pesata del valore corrente misurato e la stima precedente:

τ (n+1) = α*tn + (1- α)* τ (n)

τ (n): stima della precedente sequenza, tn: valore effettivo della precedente sequenza, τ (n+1): stima della successiva sequenza, α: controlla il peso relativo sulla predizione della storia recente e di quella passata.

Questo scheduling può essere con o senza prelazione (preemptive o non-preemptive).

Round-Robin

Simile allo scheduling FCFS ma con l’aggiunta del time sharing, ossia ad ogni processo viene assegnato un quanto di tempo della CPU (time slice, es 10-100 ms), ogni processo ha uguale priorità di esecuzione. Lo scheduler della CPU scorre la ready queue (la quale è con diritto di prelazione, ossia preemptive), la quale viene trattata come una coda circolare, assegnando la CPU a ciascun processo per un intervallo di tempo della durata massima di un quanto di tempo.

Due situazioni:

• Il processo ha una sequenza di istruzioni più breve del time slice e quindi rilascia spontaneamente la CPU consentendo al processo in testa alla coda di impadronirsi della CPU.
• La durata della sequenza di istruzioni è maggiore del quanto di tempo che il processo ha a disposizione e quindi al termine del time slice il timer scade e invia un segnale di interrupt al SO (la CPU viene sottratta al processo che viene reinserito in fondo alla ready queue).

L’efficienza dell’algoritmo è chiaramente legata alla durata del time slice. Un time slice troppo corto implica un elevato numero di context switch, mentre un time slice lungo rischia di far degenerare l’algoritmo in un FCFS. In genere basta che il time slice sia ampio rispetto al tempo richiesto per effettuare il context switch (negli algoritmi precedenti era trascurabile, qui non più).

Priorità

Ogni processo viene dotato di una certa priorità, dunque i processi a priorità maggiore avranno la precedenza nell’utilizzo della CPU rispetto a quelli a priorità inferiore. A parità di priorità, i processi vengono ordinati secondo l’algoritmo FCFS. Per evitare che processi con una priorità alta vengano eseguiti indefinitamente, durante la loro esecuzione, a ogni interrupt del clock, la loro priorità viene decrementata. Avviene un context switch quando la priorità del processo in esecuzione diventa più bassa di quella del processo con più alta priorità nella ready queue.

Code multilivello

I processi vengono suddivisi in code distinte (ad esempio i processi in background {batch} verranno separati da quelli in foreground {interattivi}) con diversi livelli di priorità, e ciascuna sarà gestita con un proprio algoritmo di scheduling. Lo scheduling tra le code è invece solitamente uno scheduling a priorità fissa con prelazione, dove ogni coda ha una sua percentuale di utilizzo della CPU, che viene poi a sua volta suddivisa tra i processi di ogni coda. I processi si assegnano in modo permanente a una coda.

Code multilivello con retroazione

In questa situazione, la classe di priorità alla quale un processo viene assegnato non è permanente, ma può variare. All’ingresso nella ready queue i processi che vengono assegnati alla prima coda ottengono un quanto di tempo, mentre quelli assegnati alla seconda ne ottengono due, quelli assegnati alla terza ne ottengono quattro, e così via. I processi che non terminano la propria sequenza di istruzioni entro il time slice che gli è stato concesso vengono spostati alla fine della coda di livello inferiore. Con questo metodo i processi lunghi scendono nelle code a priorità bassa per dare la precedenza all’esecuzione di processi interattivi brevi.

Garantito

La promessa è che se ci sono n utenti connessi, ogni utente riceverà 1/n della potenza di CPU. Per poter mantenere la promessa, il sistema calcola la priorità in base al rapporto tra il tempo di CPU effettivamente usato da un utente ed il tempo che gli sarebbe spettato. L’algoritmo privilegia l’esecuzione di quei processi che rischiano maggiormente di non rispettare le scadenze.

A lotteria

Ad ogni processo vengono assegnati dei biglietti della lotteria (che rappresentano del tempo di CPU) e il processo a cui viene assegnata la CPU è estratto a caso tra quelli pronti che dispongono di questi biglietti. Questo