Diario delle Lezioni
A.A. 2022/2023

Progettazione di Sistemi Operativi
Ingegneria Informatica - Laurea Magistrale


Data
Argomento
Tipo
N Ore
Riferimento
Lun. 19/09/2022
BREVI NOZIONI DI SICUREZZA IN CASO DI EMERGENZE.
Introduzione all'insegnamento: obiettivi, programma, testi consigliati, esame, sito dell'insegnamento (Slide prog.pdf).
GENERALITÀ - Definizione di Sistema Operativo. Storia dei Sistemi Operativi: esecuzione sequenziale ed esecuzione batch: origine dei linguaggi comandi (come quello della shell di UNIX). Problema della grande differenza di velocità fra i dispositivi meccanici (lettori di schede e stampanti) e i dispositivi elettronici (CPU): soluzione sovrapporre le operazioni di I/O con quelle della CPU mediante 3 diverse modalità: 1) operazioni fuori linea e quindi origine del concetto di dispositivi logici di I/O e della ridirezione; 2) buffer di I/O utilizzati anche attualmente; 3) tecnica di spooling utilizzata ancora per la gestione delle stampe (Slide GeneralitaSO-1.pdf).
L
2
Mer. 21/09/2022
GENERALITÀ - Storia dei Sistemi Operativi: Ripreso Problema della grande differenza di velocità fra i dispositivi meccanici (lettori di schede e stampanti) e i dispositivi elettronici (CPU) già trattato la lezione scorsa per ripetere che: 1) la soluzione di sovrapporre le operazioni di I/O con quelle della CPU mediante operazioni fuori linea ha dato origine del concetto di dispositivi logici di I/O e della ridirezione; 2) la soluzione con buffer di I/O è utilizzata anche attualmente; 3) la soluzione con la tecnica di spooling utilizzata ancora per la gestione delle stampe. Ulteriore evoluzione: multiprogrammazione con vantaggi e svantaggi. Categorie di Sistemi Operativi: sistemi batch, sistemi multiprogrammati (esempi, sistemi real-time e sistemi in time-sharing) e misti. Struttura di un Sistema Operativo: monolitico, stratificato e a micro-kernel. Illustrazione dei vari gestori che costituiscono un Sistema Operativo in particolare multiprogrammato e multiutente. Meccanismi per gestire la protezione (bit di modo ed esecuzione differenziata, istruzioni privilegiate di I/O ed esempio di HW per la protezione della memoria) e ulteriori problematiche nel caso di sistemi distribuiti (Slide GeneralitaSO-1.pdf).
L
2
Gio. 22/09/2022
GENERALITÀ - Terminato illustrazione delle ulteriori problematiche nel caso di sistemi distribuiti. Definizione di Punto di Vista esterno e di Punto di Vista Interno. Distinzione fra politiche e meccanismi. Progettazione e istallazione di un Sistema Operativo (Slide GeneralitaSO-1.pdf).
PROCESSI - Primo livello di un Sistema Operativo: NUCLEO. Grafo di precedenza degli eventi. Definizione di Processo sequenziale: grafo ad ordinamento totale. Definizione di Processo non sequenziale: grafo ad ordinamento parziale. Requisiti per eseguire un processo NON sequenziale: elaboratore NON sequenziale e linguaggio di programmazione NON sequenziale. Definizione di processo concorrente e qualche dettaglio sul quasi-parallelismo (Slide Processi-2.pdf).
L
2
Lun. 26/09/2022
SOSPENSIONE DELLA LEZIONE A CAUSA DELLE ELEZIONI!
L
2
Mer. 28/09/2022
PROCESSI - Completato velocemente le due slide di approfondimento su punto di vista interno relative a stati di un processo e descrittore di processo, rimaste indietro dalla lezione precedente (Slide Processi-2.pdf).
Relazioni fra processi concorrenti: disgiunti e interagenti (competizione e cooperazione). Descrizione dei modelli dei processi ad ambiente globale e locale e relativi tipi di interazione. Il problema base della competizione in ambiente globale: la mutua esclusione (M.E.) con definizione di sezione critica e classe di sezioni critiche. I 6 requisiti per risolvere il problema della M.E. (lasciato da guardare i vari tentativi). Introdotto l'ipotesi di sezioni critiche sufficientemente brevi, con violazione requisito 6 e 4: primitive LOCK ed UNLOCK e loro implementazione con istruzioni HW tipo TEST-AND-SET oppure EXCHANGE.
Definizione di Semaforo: istanza di Tipo di Dato Astratto con rappresentazione interna (valore >=0 e coda dei descrittori di processi) e primitive WAIT e SIGNAL. Definizione di invariante del semaforo: prove di correttezza. Discusso se i 6 requisiti che deve avere una soluzione al problema della Mutua Esclusione perché sia accettabile sono soddisfatti nei semafori (Slide ProcessiConcorrenti-2bis.pdf).
L
2
Gio. 29/09/2022
Esercitazione in Laboratorio (1) - SILVIA CASCIANELLI - Esercizi su file e processi pesanti in Linux: spiegazione degli esercizi proposti sull'implementazione in C dei comandi Linux cat e head, con richiami al loro funzionamento come comandi e come filtri; Richiamo al concetto di I/O pointer e spiegazione degli esercizi proposti ad esso relativi (si vedano su Moodle il documento Esercitazione1 e per i primi due esercizi breve presentazione su cat e head nel Materiale di supporto alla Esercitazione 1).
E
2
Lun. 03/10/2022
PROCESSI - Breve riassunto degli ultimi argomenti partendo da slide 42. Quindi ripreso discorso sui semafori: osservazioni su WAIT e SIGNAL con dettaglio su transizioni di stato dei processi (slide 20). Indivisibilità di WAIT e SIGNAL (Slide 41, ProcessiConcorrenti-2bis.pdf).
Esempi di uso dei semafori: 1) gestore di risorse: una prima soluzione naif e seconda soluzione 'vera'. 2) problema lettori/scrittori: prima soluzione con discussione sul problema della starvation e ultima (terza) soluzione senza starvation; mostrato alla lavagna esempio di arrivo di alcuni processi lettori e processi scrittori (Slide EsempiDiUsoDISemafori-2ter.pdf).
L
2
Mer. 05/10/2022
PROCESSI - Ripreso discorso su esempi di uso dei semafori: 3) problema della cena dei filosofi: possibile soluzione e discussione problema di deadlock e soluzioni alternative (Slide EsempiDiUsoDISemafori-2ter.pdf).
Cooperazione fra processi nel modello ad ambiente globale. Problema di invio di segnali: soluzione con uso di semafori. Problema del produttore/consumatore: soluzione con buffer circolare e semafori. Caso più produttori e più consumatori: nuova soluzione sempre con buffer circolare e semafori, con aggiunta di due semafori di mutua esclusione (Slide ProcessiCooperantiInAmbienteGlobale-3.pdf).
MONITOR. Costrutti di sincronizzazione di alto livello per risolvere i problemi derivanti dall'uso dei semafori che sono meccanismi di basso livello: il costrutto di sincronizzazione MONITOR del Concurrent Pascal. Due livelli di controllo: mutua esclusione nell'accesso al monitor (coda di processi esterni al monitor) e variabili condizione (con operazioni WAIT e SIGNAL, quindi code di processi all'interno del monitor). Spiegato il comportamento delle operazioni WAIT e SIGNAL e le differenze rispetto alle omonime operazioni sui semafori (Slide CostruttiDISincronizzazione-3bis.pdf).
L
2
Gio. 06/10/2022
Esercitazione in Laboratorio (2) - SILVIA CASCIANELLI - Esercizi su processi pesanti in Linux: spiegazione degli esercizi proposti sull'implementazione in C di programmi per la creazione e comunicazione tra processi e operazioni su file. Richiamo al concetto di pipe (si veda su Moodle il documento Esercitazione2).
E
2
Lun. 10/10/2022
PROCESSI - Breve riassunto sullo strumento MONITOR. Presentazione delle due semantiche possibili della SIGNAL su una variabile condizione: la semantica SEGNALA E ASPETTA (Hoare) e quella SEGNALA E CONTINUA (cui si ispira Java).
Esempi di uso di MONITOR relativi a problemi di competizione in ambito globale: 1) semplice problema di MUTUA ESCLUSIONE su una risorsa; 2) problema LETTORI-SCRITTORI (QUEUE come ulteriore operazione su variabili condizione); 3) problema dei FILOSOFI.
Esempi di uso di MONITOR relativi a problemi di cooperazione in ambito globale: soluzione del problema PRODUTTORI-CONSUMATORI.
Realizzazione del Monitor in termini di semafori: un semaforo MUTEX per ogni istanza di tipo monitor, 1 semaforo inizializzato a 0 per ogni variabile condizione e 1 semaforo URGENT per realizzare la semantica SEGNALA E ASPETTA, oltre che un insieme di contatori.
Variabili condizione con priorità. Mostrato due esempi: 1) gestione risorsa con tempo di uso; 2) gestione disco a testine mobili che minimizza gli spostamenti del braccio. (Slide CostruttiDISincronizzazione-3bis.pdf).
L
2
Mer. 12/10/2022
PROCESSI - Problema dei monitor innestati (Slide CostruttiDISincronizzazione-3bis.pdf).
Ripreso differenze fra Modello ad Ambiente Globale e Modello ad Ambiente Locale: illustrato da dove sono derivati e discusso sul fatto che hanno lo stesso potere espressivo.
MODELLO AD AMBIENTE LOCALE - Scambio di messaggi e definizione di canale "logico" di comunicazione. Le 5 caratteristiche che può avere un canale che dipendono da 3 scelte implementative. 1) designazione coppia sender/receiver: a) identificazione diretta (schema simmetrico e asimmetrico) con illustrazione di pro e contro; b) identificazione indiretta (mailbox) con illustrazione di pro e contro. 2) Bufferizzazione: a) Assenza bufferizzazione (sincronicità); soluzioni al possibile problema di blocco con introduzione time-out oppure b) Presenza di bufferizzazione (asincronicità): caso di bufferizzazione finita (N) e infinita. Semantica della Receive non bloccante. 3) Lunghezza dei messaggi: a) fissa e b) variabile. Il caso delle pipe di UNIX. (Slide AmbienteLocale-5.pdf).
L
2
Gio. 13/10/2022
Esercitazione in Laboratorio (3) - SILVIA CASCIANELLI - Esercizi su processi pesanti in Linux: spiegazione di ulteriori esercizi proposti sull'implementazione in C di programmi per la creazione e comunicazione tra processi e operazioni su file.
E
2
Lun. 17/10/2022
PROCESSI - Ripreso MODELLO AD AMBIENTE LOCALE (o SCAMBIO DI MESSAGGI): riassunto alla lavagna di quanto visto la lezione scorsa. Realizzazione fisica di un canale logico: il caso di UNIX con anche dettaglio della tabella associata ad ogni zona di memoria riservata per una pipe (tutto in memoria KERNEL). Send sincrona vs. asincrona. Problemi di ordinamento dei messaggi. Condizioni di errore: terminazione dei processi (il caso di UNIX, pipe senza scrittore e pipe senza lettore), messaggi persi o corrotti. Esempi: due soluzioni al problema produttori/consumatori; due soluzioni per la realizzazione di un semaforo binario nel caso ci siano delle eccezioni al modello ad ambiente locale, come ad esempio in UNIX. Linguaggi di programmazione concorrenti con modello ad ambiente locale: CSP, OCCAM e ADA con rendez-vous esteso, presente anche nelle RPC dei sistemi operativi distribuiti o nelle RMI di Java (Slide AmbienteLocale-5.pdf).
L
2
Mer. 19/10/2022
NUCLEO. Breve riassunto su quanto visto riguardo il Punto di vista esterno del NUCLEO di un Sistema Operativo. Punto di vista interno del NUCLEO di un S.O.: aspetti relativi alla progettazione in termini di strutture dati e di operazioni primitive (supervisor call). Strutture dati: Processo Running, Ready Queue, code dei processi sospesi e descrittori di processo (esempio di UNIX e LiNUX). Primitive di base (creazione, distruzione, sospensione e riattivazione di processi) e loro relazione con le transizioni di stato; latre primitive (sospensione temporizzata, lettura e modifica di attributi di un processo). Transizioni di stato in generale e quindi rivisto le transizioni di stato in UNIX. Approfondimento process/context switching e spiegato il meccanismo del dispatcher. Approfondimento su creazione processi: rivisto il caso di UNIX: process table, text table, spazio di indirizzamento di un processo (kernel area, data area e code area) e primitive fork ed exec (Slide Nucleo-4.pdf).
L
2
Gio. 20/10/2022
PERSA A CAUSA DELLE LAUREE: si recupererà Lun. 24/10/2022 dalle 16 alle 18.
E
2
Lun. 24/10/2022
NUCLEO. Processi pesanti vs. processi leggeri (thread): modelli cui si ispirano, performance, implementazione e modelli di multithreading (Slide Nucleo-4.pdf).
Classificazione dei tipi di scheduler: a lungo, a medio e a breve termine (CPU-Scheduler). I 5 parametri per valutare le prestazioni dello scheduler di breve termine. CPU Scheduler senza preemption e con preemption (problematiche legate all'implementazione delle primitive). Concetto di CPU- e I/O-burst per lo scheduler di breve termine. Algoritmi di Scheduling: FCFS-First Come First Served, JSF-Shortest Next CPU Burst e SRTN-Shortest Remaining Time Next, ROUND-ROBIN fino a considerazione sul valore del Quanto di Tempo in confronto al tempo per il process switching (Slide Scheduler-4bis.pdf).
L
2
Lun. 24/10/2022
RECUPERO DELL'ESERCITAZIONE DEL 20/10/2022 PERSA A CAUSA DELLE LAUREE
Esercitazione in Laboratorio (4) - SILVIA CASCIANELLI - Approfondimento sui thread. La libreria POSIX Pthread: creazione, distruzione, join, recupero identificatore thread, uguaglianza fra identificatori e yield (Slide Pthread.pdf).
Esempi d'uso e interazione dei thread con la libreria Pthread.
E
2
Mer. 26/10/2022
NUCLEO - Riassunto alla lavagna di quanto visto la lezione scorsa sullo scheduler. Ripreso algoritmi di Scheduling: completato ROUND-ROBIN, con priorità con e senza preemption (per sistemi Soft Real-Time), con code multiple e anche con retroazione (il caso di UNIX). Scheduling per sistemi multiprocessore eterogenei e omogenei: asymmetric multiprocessing e symmetric multiprocessing; problema del bilanciamento del carico e predilezione del processore; accenno allo smart scheduling. Scheduling di Linux: prima della versione 2.5, dalla versione 2.6 e quello della versione 2.6.23 (Slide Scheduler-4bis.pdf).
L
2
Gio. 27/10/2022
Esercitazione in Laboratorio (5) - SILVIA CASCIANELLI - Proseguito con l'analisi della libreria POSIX Pthread: mutex e variabili condizione. Illustrato anche i semafori definiti per trattare shared memory ma usabili anche con i thread. Spiegazione di due esercizi sulla sincronizzazione di thread in Linux.
E
2
Lun. 07/11/2022
NUCLEO - Problema del DEADLOCK: definizione ed esempi. Le quattro condizioni necessarie. Grafo di allocazione: ciclo come condizione necessaria e caso particolare come condizione necessaria e sufficiente; esempi di cicli come situazione di deadlock e non. Classificazione dei metodi per il trattamento del deadlock: prevenzione vs. soluzione a posteriori. Metodi per il trattamento del deadlock: 1) Prevenzione statica: negazione di una delle 4 condizioni, in particolare dell'ultima (attesa circolare) con ordinamento dei tipi di risorse. 2) Prevenzione dinamica. Definizione di stato sicuro e di sequenza sicura. Primo semplice esempio (Slide Deadlock-6.pdf).
L
2
Mer. 09/11/2022
NUCLEO - DEADLOCK - Breve riassunto della scorsa lezione. Nell'ambito dei metodi per il trattamento del deadlock, ripreso 2) Prevenzione dinamica. Algoritmo del banchiere: vari esempi; svantaggi e caso particolare di tipi di risorse con singola istanza. 3) Detection e Recovery. Algoritmo di Detection con esempi e caso particolare. Osservazioni su quando attivare l'algoritmo di Detection. Varie possibilità di Recovery: uccisione o preemption delle risorse, in quest'ultimo caso necessità di checkpoint (accenno all'uso dei checkpoint per ottenere fault-tolerance). Metodi misti usati dai Sistemi Operativi per prevenire i deadlock nell'uso delle proprie risorse interne. Per i processi utenti, di solito, i S.O. non prevedono soluzioni come nel caso di UNIX, ma lasciano la soluzione del problema all'utente e/o al sistemista (Lucidi Deadlock-6.pdf).
L
2
Gio. 10/11/2022
Esercitazione in Laboratorio (6) - SILVIA CASCIANELLI - Spiegazione di quattro esercizi sulla sincronizzazione di thread in Linux tramite l'uso dei semafori.
E
2
Lun. 14/11/2022
MEMORIA - Terzo livello: Gestione della memoria. Punto di vista dell'utente: binding fra spazio di indirizzamento logico del programmatore e spazio di indirizzamento fisico; 3 possibilità per il binding: a tempo di traduzione (codice binario assoluto), a tempo di caricamento (codice rilocabile staticamente) e a tempo di esecuzione (codice rilocabile dinamicamente). Punto di vista interno: funzioni del Gestore della Memoria. Categorizzazione delle politiche di allocazione e parametri di valutazione. Politiche di allocazione contigua: 1) Monitor monoprocesso con esempio del SO MS-DOS: soluzioni al problema di protezione. 2) Partizionamento statico: strategie di selezione (first fit e best fit) e frammentazione interna. Definizione della tecnica di swapping: N.B. la tecnica di swapping NON è applicabile solo al partizionamento statico! (Lucidi MemoriaAllocazioneContigua-7.pdf).
L
2
Mer. 16/11/2022
MEMORIA - Breve riassunto della lezione scorsa. Ripreso politiche di allocazione contigua: 2) Partizionamento statico: completato discorso sullo swapping parlando delle sue problematiche. Problematiche di protezione e condivisione nel caso di partizionamento statico; conclusioni su Partizionamento statico.
3) Partizionamento dinamico: evoluzione del partizionamento statico. Algoritmo di allocazione: definizione costante c e strategie di selezione (first fit e next fit; best fit e worst fit). Algoritmo di deallocazione e problema della fusione aree libere. Frammentazione esterna: compattazione. Conclusioni su Partizionamento dinamico.
4) Segmentazione come soluzione per ridurre i problemi della frammentazione esterna del Partizionamento dinamico. Tabella dei segmenti (TDS). Osservazione su dimensione delle TDS e quindi necessità di registro base e registro limite della TDS. Problema overhead in accesso: soluzione con cache o registri di segmento. Protezione e condivisione. Conclusioni su segmentazione (Lucidi MemoriaAllocazioneContigua-7.pdf).
L
2
Gio. 17/11/2022
Esercitazione in Laboratorio (7) - SILVIA CASCIANELLI - Spiegazione di quattro esercizi sulla sincronizzazione di thread in Linux tramite l'uso dei semafori e delle condition variable.
E
2
Lun. 21/11/2022
MEMORIA - Politiche di allocazione non contigua: Paginazione. Tabella delle pagine (TDP). Allocazione/deallocazione delle pagine: tabella della memoria o lista numeri pagine libere. Requisiti Hw per implementare la paginazione: a) Registri base e limite della TDP; b) problema overhead in accesso: cache delle pagine: TLB miss, hit ratio e EAT (tempo di accesso effettivo). Protezione e condivisione: meno flessibili rispetto alla segmentazione. Approfondimenti sulla organizzazione delle TDP: paginazione gerarchica su 2 o 3 livelli e tabella delle pagine invertita. Conclusioni su paginazione. Confronto Segmentazione e Paginazione: possibilità di combinazione tramite la segmentazione con paginazione (Lucidi MemoriaAllocazioneNonContigua-8.pdf).
L
2
Mer. 23/11/2022
MEMORIA VIRTUALE - Definizione di Memoria Virtuale. Paginazione su richiesta: pager. Bit di presenza/mancanza di pagina. Meccanismo del page fault e problema della interrompibilità delle istruzioni dovute ad esso: requisiti Hw. Strategie di ricerca e di posizionamento. Possibilità di ottimizzazione se a livello Hw è presente il Dirty Bit. Strategie di sostituzione: 1) FIFO e anomalia di Belady; 2) Ottima (OPT); 3) LRU (Least Recently Used). La strategia optima e quella LRU NON soffrono dell'anomalia di Belady (Lucidi MemoriaVirtuale-8bis.pdf).
L
2
Gio. 24/11/2022
Esercitazione in Laboratorio (8) - SILVIA CASCIANELLI - Spiegazione di quattro esercizi sulla sincronizzazione di thread in Linux tramite l'uso dei semafori e delle condition variable. Introduzione del problema del Barbiere Addormentato.
E
2
Lun. 28/11/2022
L
2
Mer. 30/11/2022
L
2
Gio. 01/12/2022
E
2
Lun. 05/12/2022
L
2
Mer. 07/12/2022
L
2
Lun. 12/12/2022
L
2
Mer. 14/12/2022
L
2
Gio. 15/12/2022
E
2
Lun. 19/12/2022
L
2
Mer. 21/12/2022
L
2
Gio. 22/12/2022
E
2

Legenda:
E= Esercitazione
L= Lezione