Lezioni Anno Accademico 2017/18 II semestre

Lezione del 28 febbraio 2018

Inizia oggi la seconda parte del corso di Sistemi Operativi che si terrà dal 28/02/18 al 25/05/18.
Le lezioni si svolgeranno, il mercoledì e il giovedì, in aula E1. Il venerdì invece ci sposteremo in M1.
La suddivisione degli argomenti trattati sarà: mercoledì teoria, giovedì tendenzialmente parte progettuale (potrebbe iniziare con un po' di teoria) e venerdì, data la scarsa dotazione dell'aula assegnataci, verranno svolti esercizi scritti in preparazione all'esame.

Nel corso della lezione ci siamo chiesti, riprendendo un po' il filo logico delle lezioni dello scorso semestre, quali siano i servizi che ci aspettiamo da un sistema operativo.
Questa volta, tuttavia, non li analizzeremo dal punto di vista dell'utilizzatore, ma da un punto di vista interno al sistema stesso.
I servizi elencati sono stati:

• Scheduling (Gestione CPU)
• Gestione dei processi
• Gestione della memoria primaria
• Gestione dei device di I/O
• Gestione della memoria secondaria
• Filesystem
• Networking
• Protezione
• Shell

Come in tutta l'informatica spesso succede, la complessità di questi servizi viene gestita tramite la creazione di livelli di astrazione.
Il livello zero di astrazione, quello più basso, sarà l'hardware che noi dovremo considerare come un linguaggio (l'ISA del processore).
Seguito poi da due blocchi:

• Kernel
• Utente

Cosa va incluso nel kernel di un S.O.? Cosa nella parte utente? Meglio massimizzare o minimizzare le operazioni nello livello kernel?
KERNEL MONOLITICO O MICRO-KERNEL?

I kernel monolitici (tipo Linux) hanno il vantaggio di essere leggermente più performanti, mentre i microkernel (che presentano più livelli di astrazione) sono molto più flessibili e facili da manutenere. Ad esempio, nei microkernel un bug non obbliga necessariamente a riavviare la macchina perché è possibile riavviare il singolo "modulo" che presenta l'errore.

Lezione del 1 marzo 2018

La lezione tace come concordato con gli studenti.

Lezione del 2 marzo 2018

La lezione tace causa chiusura dell'intero Ateneo per condizioni climatiche avverse.

Lezione del 7 marzo 2018

Tutto incomincia dal boot, la fase che carica il kernel, la quale termina subito dopo la creazione del primo processo (init) tramite la compilazione della tabella (come si vede sotto) che verrà passata allo scheduler. Una volta caricato, il kernel ha davanti una gradissima diversità di modelli hardware, ma come utilizzare tutti questi dispositivi hardware? Una prima soluzione sarebbe quella di includere nel kernel tutti i relativi device driver, tuttavia il kernel diventerbbe davvero corposo, a meno che non si crei un kernel ad hoc per una specifica macchina. Un'altra soluzione (quella comunemente adottata) utilizza i moduli. I moduli vengono caricati dal kernel all'occorrenza senza essere inseriti direttamente in esso (non è quindi necessaria la ricompilazione). Tuttavia con quest'ultima soluzione si viene a creare un dilemma, ovvero:
Chi carica i moduli? Il kernel.
Chi carica il kernel? Il boot tramite moduli.

In verità non esiste solo il kernel ma anche un filesystem che contiene i moduli chiamato "init.rd" (inutile se il kernel è configurato per una specifica macchina). Arrivati a questo punto ci si chiede: come si compila un kernel? Prima di tutto occorrono i sorgenti (quelli di linux sono reperibili su https://www.kernel.org). Una volta scaricati, si deve configurare il file “.config” che sostanzialmente descrive le specifiche del kernel. Questo file lo si può configurare a mano o tramite il “menuconfig” che dovrà essere prima di tutto opportunatamente compilato. All'interno del menuconfig tra le altre cose c'è una lista di tutti i device driver supportati e possono essere spuntati con: * (driver inserito nel kernel) o M (creazione del relativo modulo). Una volta configurato il “.config” non resta che compilare il kernel per la macchina ospite o per una specifica architettura. Ad esempio:

wget link_of_kernel_source #scarica i sorgenti
tar xf source_compressed_file # decomprime i relativi sorgenti, in questo caso dal file.tar.xz
cd linux #entra nella directory dei sorgenti
(Di regola esiste già un .config standard ma per configurarlo)
make menuconfig
make #compila il kernel per la macchina ospite
(make -arch=armhf, compila secondo l'architettura dei processori armhf)
( make -j n, compila il kernel per la macchina ospite utilizzando i suoi n-1 core)

Una volta compilato l'immagine del kernel si troverà in arch/nome_architettura/boot/bzImage.

Ora si ricordi la differenza tra processo e thread: Il processo è l'entità titolare delle risorse, mentre il thread è la componente sequenziale dell'elaborazione. Nei sistemi monothread il concetto di thread si sovrappone al concetto di processo ma in linea generale un processo può avere anche più di un thread. Ma quali sono le caratteristiche principali dei processi e dei thread?

Processo (PCB)	Thread (TCB)
ID (self, parent,child etc)	ID
Info sulla memoria (puntatore alla tabella dei segmenti)	Stato del processore
File aperti	Stato: Ready, Running,Block
Ownership	Puntatori
Interprocess comunication
Informazioni sull'accounting

Modo Kernel e Modo User
Si definisce Mode Switch il passaggio da Kernel Mode a User Mode e viceversa (esiste tale differenza per motivi di sicurrenzza). Attenzione però a non confondere la kernel mode con i permessi di root (root è l'utente con più permessi in assoluto ma è comunque gestito in user mode). Si definisce Context Switch il passaggio di processi. Ad esempio un processo A in user mode si ferma e passa il controllo al trap che tramite lo scheduler chiama un altro processo. Da qui si capische che è lo scheduler a decidere il prossimo processo da mandare avanti (tramite la Ready Queue). Un tipico scheduler è lo scheduler FIFO non preemptive (ossia il processo in esecuzione utilizzerà il processore finché non passerà allo stato di wait o termina l'esecuzione) per sistemi batch. I thread posso essere creati sia in modo kernel che in modo user.

Lezione del 8 marzo 2018

Lo scheduler è quella parte del sistema operativo che si occupa di assegnare le risorse (specialmente il processore) ai vari processi, decidendone l'ordine e il tempo di esecuzione. Di scheduler ne esistono di 2 tipi; quelli non-preemptive (o cooperative) dove il context switch avviene solo se il processo in esecuzione fa I/O o una system call bloccante passando allo stato di wait o termina e quelli preemptive quando il processo in esecuzione può passare allo stato ready mediante un interrupt.

I criteri con cui vengono scelti gli scheduler sono:

• Throughput: la quantità di processi completati per unità di tempo
  
• Turnaround: il tempo che intercorre da quando un processo entra nella coda ready fino alla fine della sua esecuzione
  
• Percentuale di utilizzo del processore
  
• Tempo di attesa: quanto tempo tempo un processo rimane nella coda ready prima di iniziare la sua esecuzione
  

Partendo dal più semplice da realizzare, troviamo lo scheduler FCFS (First Come, First Served), il quale usa una politica FIFO quindi i processi vengono eseguiti in ordine di arrivo, è cooperative e non è per nulla efficiente.

Uno scheduler più avanzato, ma sempre cooperative, è lo SJF (Shortest Job First) che da la priorità ai processi con meno tempo di CPU burst (tempo di utilizzo del processore). Il tempo di utilizzo della CPU viene stimato basandosi sulle precedenti esecuzioni e calcolato mediante la media esponenziale dando maggior peso alle esecuzioni più recenti. Una variante preemptive del SJF è lo Shortest-Remeaning-Time First il quale fa passare dallo stato running a ready un processo se nel frattempo arriva nella coda ready un altro processo con un tempo di CPU burst più breve. Il problema principale però è che entrambi possono generare starvation.

Lo scheduler Round-Robin, di tipo preemptive, fa uso della Time-Slice (ovvero un quanto di tempo). I processi vengono eseguiti in ordine di arrivo ma possono rilasciare il processore anticipatamente nel caso in cui finisca la time-slice a loro disposizione. Per implementare questo scheduler, tuttavia, è necessario un supporto hardware chiamato "interval time", il quale non fa altro che generare un input ogni tot tempo scelto dal sistema operativo, questo input non ha nessuno scopo se non quello di generare un interrupt che possa interrompere l'esecuzione di un processo. La time-slice non piò essere troppo breve perché il context-switch ha un costo, non è istantaneo, ma nemmeno un troppo lunga altrimenti non si avrebbe l'idea di un sistema fluido ed istantaneo.

Esistono anche gli scheduler che assegnano una priorità ai processi ed eseguono prima quelli con priorità più elevata. Questi scheduler esistono sia con priorità statica, che con priorità dinamica, ma potendo generare starvation, quelli con priorità dinamica possono utilizzare l'aging, ossia un processo con priorità bassa aumenta di volta in volta la sua priorità fino a diventare massima per poi, una volta eseguito, tornare alla priorità originaria. Un po' più complessi sono gli scheduler con classi di priorità, in cui la coda ready è divisa in diverse sottocode, una per ogni classe di processi. Gli scheduler multilivello utilizzano sempre le classi di priorità ma assegnano ad ogni classe delle politiche diverse, adatte per i processi che contiene.

Per applicazioni particolari, in cui la correttezza del programma dipende da tempo entro i quale viene data la risposta, esistono gli scheduler real-time.

Lezione del 9 marzo 2018

Esercizi su monitor e semafori degli esami di gennaio e febbraio 2018.

Testo:

Monitor bridge
	boolean bridge_is_down
	int crossingCars
	int crossingBoat
	int waitingCars
	int waitingBoats
	condition ok2cars
	condition ok2boats

procedure_entry car_enter(direction)
	if(crossingBoat || waitingBoats > 0){
		waitingCars++
		ok2cars.wait()
		waitingCars--
	}
	bridge_is_down = true
	crossingCars++
	ok2cars.signal()

procedure_entry car_exit(direction)
	crossingCars--
	if(crossingCars == 0) ok2boat.signal()

procedure_entry boat_enter(direction)
	if(crossingCars > 0 || crossingBoat > 0){
		waitingBoats++
		ok2boat.wait()
		waitingBoats--
	}
	bridge_is_down = false
	crossingBoat++

procedure_entry boat_exit(direction)
	crossingBoat--
	ok2cars.signal()
	if(crossingCars == 0) ok2boat.signal()

Testo: implementare, utilizzando semafori ordinari, i semafori ternari

class ternarySemaphore

	semaphore pos
	semaphore neg
	
	void ternarySemaphore(int init)
	void P(void)
	void V(void)

	void ternarySemaphore(void init)
		// init is -1 or 1
		pos = new semaphore(1 + init)
		neg = new semaphore(1 - init)

	void P(void)
		pos.P()
		neg.V()

	void V(void)
		neg.P()
		pos.V()

Soluzione alternativa, meno di stile ma ugualmente funzionante

class ternarySemaphore

	semaphore queue
	semaphore mutex
	int value

	void ternarySemaphore(int init)
	void P(void)
	void V(void)

	void ternarySemaphore(void init)
		mutex = new semaphore(1)
		value = init
		queue = new sem_queue

	void P(void)
		mutex.P()
		if(value == 1 && !queue.empty()){
			s = queue.dequeue()
			s.V()
		}else{
			if(value == -1){
				s = new semaphore(0)
				queue.enqueue(s)
				mutex.V()
				s.P()
			}else{
				value--
				mutex.V()
			}
		}

	void V(void)
		mutex.P()
		if(value == -1 && !queue.empty()){
			s = queue.dequeue()
			s.V()
		}else{
			if(value == -1){
				s = new semaphore(0)
				queue.enqueue(s)
				mutex.V()
				s.P()
				free(s)
			}else{
				value++
				mutex.V()
			}
		}

Lezione del 14 marzo 2018

RISORSE

Cosa intendiamo per risorsa? Quali sono i problemi comuni e le tecniche per risolverli?
Nel frattempo definiamo come CLASSI DI RISORSE l'insieme formato da risorse tra loro equivalenti (byte della memoria, stampanti dello stesso tipo, etc.).
Una prima distinzione può essere fatta tra risorse ad assegnazione statica e ad assegnazione dinamica: le prime, una volta assegnate, non possono essere più prelevate finché il processo che le possiede non termina. Nel secondo caso, invece, l'assegnazione può mutare nel tempo.
Si può distinguere il tipo di richiesta che viene fatta alla risorsa: singola o multipla, bloccante o non bloccante. Intuitivamente, la prima distinzione si riferisce alla molteplicità di richieste che la risorsa può eseguire nello stesso momento mentre, la seconda distinzione, si riferisce al comportamento della richiesta.
Altre distinzioni possono essere fatte tra risorse non condivisibili (dette anche seriali) e risorse condivisibili (o non seriali), tra risorsa non pre-emptible e pre-emptible. Una risorsa può essere pre-emptible se e solo se non ha uno stato interno o se lo stato può essere salvato per poi essere ripristinato.
Può accadere che un processo A effettui una richiesta bloccante ad una risorsa non-preemptible e non condivisibile che al momento è utilizzata da un qualche processo B. B, a sua volta, fa la stessa cosa ma, con una risorsa in possesso di A. Cosa accade?
DEADLOCK
Le condizioni necessarie affinché un deadlock si verifichi sono:

• RICHIESTA BLOCCANTE
• RISORSA NON CONDIVISIBILE
• RISORSA NON-PREEMPITIBLE
• ATTESA CIRCOLARE

work in progress

Lezione del 15 marzo 2018

(la lezione tace per impegno del docente)

Lezione del 16 marzo 2018

Esercizi

Lezione del 21 marzo 2018

Algoritmo Banchiere, Gestione memoria, Partizionamento statico e dinamico

Lezione del 22 marzo 2018

Gestione memoria, Paginazione e Segmentazione

Alcuni errori comuni della fase 1 del progetto:

• file sparsi nell'archivio, invece di una sola cartella che li contiene tutti
• uso del Makefile senza regole automatiche
• uso di sentinelle globali nella ricorsione
• uso di licenze non compatibili tra di loro
• indentazione sbagliata

Memoria Principale

La MMU è una componente hardware che implementa una funzione che associa gli indirizzi usati dal sorgente (logici) a quelli reali in memoria (fisici).

Un modo per calcolare gli indirizzi fisici corrispondenti agli indirizzi logici di un processo è dare un registro base ad ogni processo; quando un processo accede all'indirizzo della variabile A, ad esempio, la MMU calcola il suo indirizzo fisico aggiungendo al suo indirizzo logico il valore del registro base.

Qual è il problema con questo approccio? Non si hanno indirizzi più piccoli dell'indirizzo base, ma si può sforare nello spazio di indirizzi di un altro processo, dato che non c'è un limite superiore. Questo problema si risolve facilmente aggiungendo al registro base un registro limite. Un processo può accedere a tutti gli indirizzi compresi tra i due indirizzi, e, se va fuori, si genera una trap di memoria. Questo fornisce anche un meccanismo di protezione della memoria.

Se adottiamo questo approccio quando allochiamo spazio in memoria per un processo dobbiamo farlo in maniera contigua. Come? Ci sono vari metodi:

• Partizionamento statico: in una sezione iniziale della memoria sta il kernel, il resto della memoria è divisa in parti; man mano che arrivano i processi vengono assegnati alle varie parti di memoria. Che problemi ha questo approccio? È statico, ovvero la disposizione iniziale è quella definitiva. Inoltre dobbiamo scegliere il segmento dove inserire il nuovo processo allocato. Spesso la memoria disponibile è maggiore di quella necessaria; di conseguenza ci sarà uno spreco. Quando ci sono aree di memoria inutilizzate all'interno di porzioni di memoria di dimensioni stabilite a priori si parla di frammentazione interna. È' un problema che vogliamo risolvere;

• Partizionamento dinamico: potremmo, ad esempio, stackare i blocchi di memoria dei processi, così da non sprecare memoria. Problema: come facciamo quando un processo termina? In questo caso avremmo degli spazi di memoria inutilizzati sparsi per la memoria, che potrebbero dare spazio ad un altro processo se uniti assieme, ma che da soli non riescono perché sono troppo piccoli. Si parla in questo caso di frammentazione esterna. Si può risolvere il problema compattando le zone di memoria. Per fare ciò è necessario:
  • copiare il PCB dal posto in cui si trova alla cima dello stack;
  • cambiare base register e limit register;
  • aspettare che il processo sia "fermo"; se fosse in esecuzione spostarlo ovviamente creerebbe delle inconsistenze.

Se il processo è interattivo e si prova a fare compattazione, si parla di Giga da muovere: altamente inefficiente. L'approccio migliore è quello di limitare la frammentazione esterna. Come? Scegliendo, tra le varie aree libere, quella migliore per contenere un processo. Per fare queste operazioni è necessario qualcuno che tenga traccia della contabilità della memoria del sistema. Ci pensa un programma chiamato Memory Manager. Come fa? Con una lista delle aree di memoria libere. Questo permette di vedere se esistono zone di memoria libere contigue e di unirle assieme eventualmente. Si possono usare anche le tabelle di bit: se consideriamo la memoria divisa in unita' di allocazione possiamo associare ad ogni unità un bit, acceso o spento se libera o meno.

Per scegliere le aree di memoria ci sono vari approcci:

• Best Fit: scelgo l'area più piccola che contiene il mio processo;
• First Fit: scelgo la prima area capace di contenere il mio processo che trovo dall'inizio della memoria;
• Next Fit: come First Fit ma parto dall'ultimo processo a cui sono arrivato con la precedente scansione;
• Worst Fit: scelgo l'area più grande che contiene il mio processo.

Quale tecnica è la migliore? Statisticamente First Fit.

Questi meccanismi funzionavano per sistemi batch; per sistemi molto dinamici queste cose ci fanno sprecare memoria o è richiesta la compattazione, che richiede tempo. La MMU con base register e limit register non permettono altro. Si può fare di meglio? Sì.

Come? Con la paginazione della memoria. La memoria viene divisa in blocchi di dimensione fissata dette pagine. Ovviamente l'ampiezza della pagina è una potenza di 2. L'indirizzo logico visto dal programma viene diviso in due parti: il numero di pagina e l'offset all'interno della pagina. La MMU usa il numero della pagina come indice all'interno di una tabella. A quell'indice è associato, nella tabella, l'indirizzo fisico che contiene la pagina. La parte di memoria fisica che contiene la pagina è detta frame. L'indirizzo fisico corrispondente sarà dato, una volta ottenuto l'indirizzo del frame che lo contiene, dai bit che precedono l'offset e, subito dopo, dall'offset stesso, che viene copiato identico alla fine dell'indirizzo fisico.

Questo meccanismo è molto più flessibile del partizionamento della memoria. C'è frammentazione interna? Sì, ma poca: nel peggiore dei casi abbiamo un processo che ha bisogno di n pagine + 1 bit. In questo caso verranno allocate n+1 pagine. Quindi la frammentazione interna che abbiamo sarà al massimo dell'ordine della dimensione di una pagina per ogni processo. C'è frammentazione esterna? Potrebbe, ma sarebbe irrisoria: potrebbe esserci all'inizio della memoria dove risiede il kernel.

Il problema della frammentazione è risolto. Ma dove sta il costo nascosto? Nella MMU. Come si gestisce la sua tabella? La cosa migliore sarebbe una matrice associativa, sarebbe molto veloce, e questa caratteristica è necessaria visto che la tabella va gestita ad ogni accesso in memoria. Problema: il costo elevato di una componente hardware capace di mantenere una tabella delle pagine. Mettiamo la tabella in memoria? Non è ideale, perché dopo servirebbero due accessi in memoria per ogni accesso in memoria. Le prestazioni della memoria risultano quindi dimezzate.

La soluzione? Una cache: il Translation Lookahead Buffer. È una matrice associativa, ma fa da cache alla tabella della MMU, che è salvata in memoria. È quindi molto più piccola della tabella. Quando viene fatta una operazione in memoria si può avere un TLB hit: la velocità è alta. Potremmo avere un TLB miss. In questo caso l'indirizzo richiesto non è in cache. Questo genera un interrupt, quindi il controllo passa al kernel, che va a vedere nella tabella in memoria se l'indirizzo richiesto è legale, nel qual caso lo carica. Questo meccanismo è ragionevolmente veloce e ha prezzi accessibili. Va tuttavia fatto notare che una macchina che usa allocazione contigua senza paginazione è più veloce di una macchina con paginazione. Ovviamente quello che abbiamo con questo meccanismo è un tradeoff. Paghiamo due prezzi: uno in termini di performance, un altro in termini di linearità di esecuzioni, in cambio di un miglior utilizzo della memoria.

Gli effetti positivi della paginazione sono tanti, ma rimangono alcuni problemi da risolvere. Se noi abbiamo una libreria dinamica con la paginazione tradizionale avremmo tante copie della stessa libreria in memoria, e quindi un enorme spreco. Per fare questo si usa il codice reentrant. La memoria allocata per un processo è così divisa:

• area text: testo dell'eseguibile; solitamente read-only, dato che può anche essere sharable;
• area data: variabili globali; condivisibile per scelta;
• area stack: area dove cresce lo stack; MAI condivisibile.

Come risolviamo questo problema? Col loading dinamico, ovvero loading di codice dalla memoria a run-time. È una funzionalità fornita agli sviluppatori per scrivere codice più efficiente.

Un'altra funzionalità è il linking dinamico. Le librerie dinamiche servono a questo: quando il codice usa una libreria non la linka nell'eseguibile, ma si segna che è presente e si segna la versione che usa; a run time, raggiunta quella parte di codice, si va a recuperare la libreria dinamica già caricata in memoria (o casomai si carica); questo viene fatto dal linker.

È possibile attaccarsi alla libreria già caricata in memoria grazie a memory mapping. Questo pero' non è possibile con la paginazione tradizionale. Occorre introdurre un nuovo concetto: la segmentazione. L'idea è di dividere l'area richiesta dai processi in segmenti adibiti a scopi specifici. Si possono avere segmenti testo, data, stack, shared data, etc., ognuno con le sue proprietà di leggibilità o di scrittura. Una MMU che supporta segmentazione è così fatta: la parte iniziale (piccola) dell'indirizzo identifica il segmento, la parte finale identifica l'offset all'interno del segmento. Per ogni segmento vi è una entry in una tabella, in cui vengono mantenute le varie proprietà del segmento. Tra le varie cose viene mantenuto l'indirizzo base del segmento (da sommare all'offset). Di segmenti ce ne sono pochi, di pagine tante.

Facciamo un confronto tra paginazione e segmentazione:

Pagine	Segmenti
Limita frammentazione	Permette la condivisione e la protezione
Hanno tutte la stessa ampiezza (e.g. 4k)	Hanno ampiezza (molto) variabile O(k),....,O(G)
Hanno un indirizzo	Hanno un nome
Possono contenere dati disomogenei	Contengono informazioni omogenee
Divisione in pagine automatica	Divisione in segmenti; alcune divisioni sono strutturali, altre sono decise dal programmatore

Nella pratica che tecnica si usa? Entrambe: paginiamo i segmenti. Gli indirizzi logici contengono l'identificatore del segmento, della pagina, l'offset ed il contesto. In caso di miss si usa il numero di segmento per accedere ad una tabella con i bit di controllo. Se l'indirizzo è legale la entry punta ad una page table. Si usa poi il numero di pagina per identificare la pagina e l'offset per ottenere la parte di memoria desiderata.

Lezione del 23 marzo 2018

Esercizi

Lezione del 28 marzo 2018

Memoria virtuale, algoritmi di rimpiazzamento

Lezione del 4 aprile 2018

Trashing. Gestione memoria secondaria

Lezione del 5 aprile 2018

FIle system: visione utente e programmatore. Allocazione e gestione aree libere.

Lezione del 6 aprile 2018

Esercizi (parte generale).

Lezione del 11 aprile 2018

File system, Gestione directory. Gestione della coerenza (fsck, journaling)

Lezione del 12 aprile 2018

Sicurezza: principi. Crittografia. Attacchi.

Lezione del 13 aprile 2018

Esercizi

Lezione del 18 aprile 2018

Sicurezza: autenticazione, Easter egg, trojan horse, backdoor, virus worm.

Lezione del 19 aprile 2018

(la lezione tace per impegni del docente)

Lezione del 20 aprile 2018

Esercizi

Lezione del 26 aprile 2018

Phase2 presentazione specifiche

Lezione del 27 aprile 2018

Esercizi