Sistemi Operativi AA 2002/2003 - Cos'e' un Sistema Operativo? - Caratteristiche di un Sistema Operativo. - Storia dei Sistemi Operativi - Parallelismo fra "generazioni" di hardware e generazioni di Sistemi Operativi. - Esecuzioni Batch. - Il concetto di spooling. - Il concetto di multiprogrammazione. - Time Sharing. - L'avvento dei P.C., effetti sui sistemi operativi. - Sistemi Distribuiti e Sistemi Paralleli - Sistemi in tempo Reale Programmazione Concorrente: - Cos'e' u programma concorrente - Parallelismo apparente e parallelismo reale - Concetto di processo - Stati di un processo - Assioma di finite progress - Notazioni per descrivere i processi: - esplicita - cobegin/coend - fork/join/quit - Interazione tra processi - Correttezza di un programma concorrente - Proprieta' di safety e liveness - Deadlock - Starvation - Concetto di azione atomica - Critical section - Implementazione di critical section: problemi - Proprieta' delle critical section - Algoritmo di Dekker - Dimostrazione delle proprieta' delle critical section per l'algoritmo di Dekker - Algoritmo di Peterson - Dimostrazione delle proprieta' delle critical section per l'algoritmo di Peterson - Critical section: implementazioni tramite istruzioni tipo Test&Set - Semafori: definizione e invariante - Implementazione delle C.S. tramite semafori - Implementazione dei semafori tramite C.S. - Semafori Binari - Implementazione di semafori tramite semafori binari - Problemi classici delle programmazione concorrente: definizione e problematiche. - Producer-consumer - Bounded buffer - Dining philosophers - Dining philosophers: invarianti del problema. - Readers and writers. - Readers and writers: invarianti del problema. - Implementazione di producer-consumer tramite semafori - Implementazione di bounded buffer tramite semafori - Implementazione di dining philosophers tramite semafori - Implementazione di readers and writers tramite semafori - Operatore await e sua implementazione tramite semafori. - Tecnica del passaggio di testimone (passing le baton) - Regioni critiche condizionali (definizione e sintassi) - Implementazione dei semafori tramite CCR - Implementazione di producer-consumer tramite CCR - Implementazione di dining philosophers tramite CCR - Implementazione di readers and writers tramite CCR - Implementazione di bounded buffer tramite CCR (con accesso esclusivo) - Implementazione di bounded buffer tramite CCR (con accesso concorrente) - Implementazione delle CCR tramite semafori - Monitor: definizione e sintassi - Variabili di condizione significato e uso - Monitor: rappresentazione grafica - Confronto operazioni su semafori e su variabili di condizione - Altre politiche di signaling (oltre signal-urgent) - Implementazione dei semafori tramite monitor - Implementazione di readers and writers tramite monitor - Implementazione di producer-consumer tramite monitor - Implementazione di bounded buffer tramite monitor - Implementazione di dining philosophers tramite monitor - Message passing sincrono e asincrono - Implementazione di message passing sincrono tramite message passing asincrono - Implementazione di message passing asincrono tramite message passing sincrono - Implementazione di dining philosophers tramite MP asincrono - Implementazione di producer-consumer tramite message passing sincrono Richiami di Archittetura - Architettura di Von Neumann - Interrupt e Trap - Gestione degli interrupt - Sistemi operativi "interrupt driven" - Interrupt Multipli - Programmed I/O - Interrupt Driven I/O - DMA - Memory Mapped I/O - Dispositivi I/O: dischi, nastri, etc. - Gerarchia di memoria e concetto di cache - Modo kernel e modo user - Protezione hardware per la memoria - Memory Management Unit Struttura interna dei Sistemi Operativi - Concetti generali relativi alla struttura dei S.O. - Componenti di un S.O. - Gestore dei processi - Gestore della memoria principale - Gestore dei file - Gestore dell'I/O - Gestore della memoria secondaria - Gestore della rete - Sistema di sicurezza - Interprete di comandi - Servizi del S.O. - System Call - Programmi di sistema - Tipi di strutture standard di S.O. - Struttura semplice - Struttura a livelli - Microkernel - Macchine virtuali - Progettazione di un sistema operativo - Separazione politica/meccanismi - Definizione e tecniche di O.S. generation. Kernel - Tabella dei descrittori di processi - Stato di un processo - Scheduler, scheduling, schedule - Mode switching e context switching - Vita di un processo nello scheduler - Classi di scheduler - Gerarchia di processi - Concetto di thread - Benefici dei thread - Implementazione del multithreading - Modelli di multithreading - Diagramma di Ganntt - Scheduling preemptive e scheduling cooperativo - Criteri di scelta dello scheduler - Caratteristiche dei processi - Scheduler FCFS - Scheduler shortest job first (SJF) - Calcolo approssimato della durata di un CPU burst - Scheduler round robin - Scheduler a priorita' - Tecniche di aging - Scheduler a classi di priorita' - Scheduler multilivello - Scheduler Real-Time. - Differenze fra Hard e Soft Real-Time - Processi periodici e processi aperiodici - Scheduler Earliest Deadline First - Scheduler Rate monotonic - (Analisi dei tempi di risposta) - (Schedule Deadline Monotonic Priority Assignment) - (Dimostrazione dell'ottimalita' di DMPO fra i metodi a priorita' statica) Gestione delle Risorse - Definizione di risorsa e classe di risorse. - Assegnazione statica o dinamica delle risorse. - Richiesta singola o richiesta multipla - Richieste bloccanti o non bloccanti - Risorse seriali - Risorse prerilasciabili - Condizioni necessarie e sufficienti per lo stato di deadlock - Grafo di Holt, definizione e possibili rappresentazioni grafiche - Metodi di gestione dello stato di deadlock - Deadlock detection tramite il grafo di Holt: una sola risorsa per classe - Deadlock detection tramite il grafo di Holt: molteplici risorse per classe metodo di riduzione - Deadlock detection tramite il grafo di Holt: molteplici risorse per classe tramite riconoscimento dei knot - Meccanismi per il deadlock recovery - Deadlock prevention - Allocazione gerarchica e totale - Deadlock avoidance - Algoritmo del banchiere - Definizione di stato safe, differenza fra caso mono valuta e multi valuta. - Stato unsafe non implica deadlock: dimostrazione tramite controesempio - Teorema dell'algoritmo del banchiere - Algoritmo dello struzzo Gestione della Memoria - Compiti del Gestore della memoria - Binding: durante la compilazione, il caricamento o l'esecuzione. - Indirizzi logici e dinamici - Loading e linking dinamici - Allocazione: definizione - Allocazione contigua o non contigua - Allocazione statica o dinamica - A partizioni fisse o variabili - Il problema della frammentazione (interna e esterna) - Politiche di allocazione: first fit, best fit, worst fit - Strutture dati per la gestione della memoria: mappe di bit e liste con puntatori - Compattazione - Paginazione - Supporto hardware per la paginazione: funzioni richieste alla MMU - Scelta dell'ampiezza delle pagine - Supporto hardware efficiente per la paginazione - Paginazione a piu' livelli - Segmentazione - Confronto fra paginazione e segmentazione - Supporto della condivisione tramite segmentazione - Il problema della frammentazione in una gestione con segmentazione. - Uso combinato di segmentazione e paginazione. - Memoria virtuale - Paginazione a richiesta - Funzionamento di un processo pager - Algoritmi di rimpiazzamento - Definizione di "stringa dei riferimenti" - Algoritmo fifo - Anomalia di Belady - Algoritmo ottimo (MIN) - Algoritmo LRU - Definizione di Algoritmo a Stack. - Altri algoritmi (LFU, MFU, RAND...) - Algoritmo di Second Chance (Orologio) - Allocazione in memoria virtuale - Allocazione locale o globale - Fenomeno di trashing - Definizione di Working Set - Scelta dell'ampiezza di finestra del working set Gestione della memoria secondaria - Caratteristiche fisiche dei dischi - Problema della gestione delle richieste concorrenti - La minimizzazione del numero di seek - Algoritmo FCFS - Algoritmo SSTF - Algoritmo SCAN (o dell'ascensore) - Algoritmo C-SCAN - Algoritmi LOOK e C-LOOK - Sistemi RAID - Concetto di disk mirroring e disk striping File System - Concetto di File - Attributi dei file - Tipi di file, estensioni standard - Gestione dei tipi di file - Distinzione tra file regolari e file speciali - Struttura interna dei file - Record logici/record fisici - Metodi di accesso - File con indice (ISAM) - Operazione sui file - Struttura di directory - Semantica della coerenza nell'accesso al file system - Organizzazione di un disco - Metodi di allocazione - Allocazione contigua - Allocazione concatenata - Allocazione tramite FAT - Allocazione indicizzata - Tecniche per migliorare le prestazioni dell'allocatore del file system - Gestione dello spazio libero: vettore di bit - Gestione dello spazio libero: lista concatenata - Gestione dello spazio libero: tramite FAT - Scelta della dimensioni dei blocchi - Implementazione delle directory: lista lineare o tabella hash - Directory basate su grafi aciclici - Tecniche per garantire la coerenza - File system basati su log - Tecniche di cache del file system - Esempi di file system: MS-DOS, Windows 95, Unix V7 Sicurezza - Protezione e sicurezza: definizioni - Obiettivi della sicurezza - Politiche e meccanismi - Crittografia - Funzioni one-way - Crittografia a chiave segreta - Crittografia a chiave pubblica - Buffer overflow - Errori tempo controllo / tempo utilizzo - Trojan horse - Bombe logiche - Backdoor / Trapdoor - Virus e worm - Autenticazione: definizione - Gestione password - Shadow file, salt - Cracking e password "deboli" - Login spoofing - Autorizzazione: definizione - Trusted computing base - Reference monitor - Principi fondamentali dell'autorizzazione - Matrice di accesso - Access control list - Capability - Protezione in POSIX - DAC / MAC: Definizioni - SELinux (Cenni) Windows 2000 - Definizione e Storia - Principi di progettazione - API Win 32 - Architettura di Windows 2000 - Hal - Kernel - Dispatcher Object - Control Object - Job,Processi,Thread,Fiber - Stati di un processo in Windows 2000 - Priorit�in Windows 2000 - Scheduler di Windows 2000 - Gestione delle eccezioni - DPC & APC - Interrupt & Windows 2000 multiprocessore - Executive - Object manager: oggetti temporanei e oggetti permanenti - Object manager: principali operazioni - Nomi degli oggetti - Virtual-Memory Manager - Allocazione di memoria - Condivisione di Memoria - Memory Manager: strutture dati - Struttura di un indirizzo virtuale - Struttura di una PTE - Process Manager - Local Procedure Call - Quick LPC - I/O manager - I/O manager: cache - Environmental Subsystem - MS-DOS subsystem - WIN16 subsystem - Win32 subsystem - POSIX subsystem - OS/2 subsystem - Logon e Security Subsystem - File System: NTFS - NTFS cluster - NTFS: Struttura del file - NTFS: MFT - NTFS: File Reference - NTFS: Struttura delle directory - NTFS: Gestione dei metadati - NTFS: recovery di guasti - NTFS: Fault tolerance - NTFS: Compressione - Nt networking: protocolli - NT networking: meccanismi - Redirector e Server - NT Domain - Name Resolution in NT - WINS - DHCP LINUX - Storia di Linux - Principi costruttivi - Linux: architettura - Moduli del kernel - Gestione dei processi - Scheduling - Gestione della memoria - File system UNIX - Principi costruttivi - Interfaccia di programmazione - Interfaccia utente - Inter-process communication - Principali chiamate di sistema