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

Nessuna lezione.

Lezione del 22 marzo 2018

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

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 puo risolvere il problema comppattando 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 è interativo 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 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 asieme 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 libero o meno.

Quale è la tecnica migliore 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 che trovo dall'inizio della memoria;
- Next Fit: come First Fit, ma parto dall'ultimo 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ì.

TO BE CONTINUED