Appunti di Sistemi Operativi, prof. Cattaneo, libro consigliato Sistemi Operativi: Concetti ed Esempi di Abraham Silberschatz

Sistemi Operativi

Cosimo Botticelli

2021

Contents

1 Parte Prima, Capitolo 1: Introduzione 7

1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2 Cosa è un Sistema Operativo . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.1 Punto di vista dell’utente . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.2 Punto di vista del sistema . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.3 Definizione di Sistema Operativo . . . . . . . . . . . . . . . . . . . 9

1.3 Organizzazione di un sistema elaborativo . . . . . . . . . . . . . . . . . . . 10

1.3.1 Interrupt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.2 Struttura della memoria . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.3 Struttura di I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Architettura degli elaboratori . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4.1 Sistemi monoprocessore e multiprocessore . . . . . . . . . . . . . . 12

1.5 Attività del sistema operativo . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5.1 Multiprogrammazione . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5.2 Duplice modalità di funzionamento . . . . . . . . . . . . . . . . . . 15

1.5.3 Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6 Gestione delle risorse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.1 Gestione dei processi . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.2 Gestione della memoria . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.6.3 Gestione dei file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.6.4 Gestione della memoria di massa . . . . . . . . . . . . . . . . . . . 17

1.6.5 Gestione della cache . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.6.6 Gestione dell’I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.7 Virtualizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 Parte Prima, Capitolo 2: Strutture dei Sistemi Operativi 20

2.1 Servizi di un Sistema Operativo . . . . . . . . . . . . . . . . . . . . . . . . 21

2.1.1 Funzionalità utili all’utente . . . . . . . . . . . . . . . . . . . . . . 21

2.1.2 Funzioni utili al sistema . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 System Calls (chiamate di sistema) . . . . . . . . . . . . . . . . . . . . . . 22

2.2.1 Categorie di system calls . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 Struttura del sistema operativo . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3.1 Struttura monolitica . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3.2 Approccio stratificato . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1

2.3.3 Microkernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3.4 Moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4 Linker e Loader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3 Parte Seconda, Capitolo 3: Processi 28

3.1 Concetto di Processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1.1 Il Processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1.2 Stato del processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.1.3 Blocco di controllo del processo . . . . . . . . . . . . . . . . . . . . 31

3.1.4 Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2 Scheduling dei processi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2.1 Code di scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2.2 Scheduling della CPU . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.2.3 Cambio di contesto . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.3 Operazioni sui processi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.3.1 Creazione di processi . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.3.2 Terminazione di un processo . . . . . . . . . . . . . . . . . . . . . . 35

3.3.3 Comunicazione tra processi . . . . . . . . . . . . . . . . . . . . . . 36

4 Parte Seconda, Capitolo 4: Thread e Concorrenza 37

4.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.1.1 Motivazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.1.2 Vantaggi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2 Programmazione multicore . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2.1 Tipi di parallelismo . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.3 Modelli di supporto al multithreading . . . . . . . . . . . . . . . . . . . . . 40

4.3.1 Modello da molti a uno . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.3.2 Modello da uno a uno . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.3.3 Modello da molti a molti . . . . . . . . . . . . . . . . . . . . . . . . 42

5 Parte Seconda, Capitolo 5: Scheduling della CPU 44

5.1 Concetti fondamentali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.1.1 Ciclicità delle fasi di elaborazione e di I/O . . . . . . . . . . . . . . 45

5.1.2 Scheduler della CPU . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.1.3 Scheduling con e senza prelazione . . . . . . . . . . . . . . . . . . . 45

5.1.4 Dispatcher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.2 Criteri di scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3 Algoritmi di scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.3.1 Scheduling in ordine d’arrivo . . . . . . . . . . . . . . . . . . . . . . 47

5.3.2 Scheduling shortest-job-first . . . . . . . . . . . . . . . . . . . . . . 48

5.3.3 Scheduling circolare (round-robin) . . . . . . . . . . . . . . . . . . . 49

5.3.4 Scheduling con priorità . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.3.5 Scheduling a code multilivello . . . . . . . . . . . . . . . . . . . . . 50

5.3.6 Scheduling a code multilivello con retroazione . . . . . . . . . . . . 50

2

5.4 Scheduling dei thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.4.1 Ambito della contesa . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.5 Scheduling per sistemi multiprocessore . . . . . . . . . . . . . . . . . . . . 51

5.5.1 Approcci allo scheduling per multiprocessori . . . . . . . . . . . . . 51

5.5.2 Processori multicore . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.5.3 Bilanciamento del carico . . . . . . . . . . . . . . . . . . . . . . . . 53

5.5.4 Predilezione per il processore . . . . . . . . . . . . . . . . . . . . . 53

5.5.5 Multiprocessing eterogeneo . . . . . . . . . . . . . . . . . . . . . . . 54

5.6 Valutazione degli algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.6.1 Modellazione deterministica . . . . . . . . . . . . . . . . . . . . . . 54

6 Parte Terza, Capitolo 6: Strumenti di Sincronizzazione 56

6.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.2 Problema della sezione critica . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.3 Supporto hardware per la sincronizzazione . . . . . . . . . . . . . . . . . . 58

6.3.1 Barriere di memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.3.2 Istruzioni hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.3.3 Variabili atomiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.4 Lock mutex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.5 Semafori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7 Parte Quarta, Capitolo 9: Memoria Centrale 60

7.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.1.1 Hardware di base . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.1.2 Associazione degli indirizzi . . . . . . . . . . . . . . . . . . . . . . . 62

7.1.3 Spazi di indirizzi logici e fisici . . . . . . . . . . . . . . . . . . . . . 62

7.1.4 Caricamento dinamico . . . . . . . . . . . . . . . . . . . . . . . . . 63

7.1.5 Linking dinamico e librerie condivise . . . . . . . . . . . . . . . . . 63

7.2 Allocazione contigua della memoria . . . . . . . . . . . . . . . . . . . . . . 63

7.2.1 Protezione della memoria . . . . . . . . . . . . . . . . . . . . . . . . 64

7.2.2 Allocazione della memoria . . . . . . . . . . . . . . . . . . . . . . . 64

7.2.3 Frammentazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3 Paginazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3.1 Metodo di base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3.2 Supporto hardware alla paginazione . . . . . . . . . . . . . . . . . . 66

7.3.3 Protezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7.3.4 Pagine condivise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7.4 Struttura della tabella delle pagine . . . . . . . . . . . . . . . . . . . . . . 68

7.4.1 Paginazione gerarchica . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.4.2 Tabella delle pagine invertita . . . . . . . . . . . . . . . . . . . . . 68

7.5 Swapping dei processi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

7.5.1 Swapping standard . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3

8 Parte Quarta, Capitolo 10: Memoria Virtuale 70

8.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

8.2 Paginazione su richiesta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

8.2.1 Concetti fondamentali . . . . . . . . . . . . . . . . . . . . . . . . . 72

8.2.2 Lista dei frame liberi . . . . . . . . . . . . . . . . . . . . . . . . . . 73

8.3 Copiatura su scrittura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

8.4 Sostituzione delle pagine . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

8.4.1 Sostituzione di pagina . . . . . . . . . . . . . . . . . . . . . . . . . 74

8.4.2 Sostituzione delle pagine secondo l’ordine di arrivo (FIFO) . . . . . 75

8.4.3 Sostituzione ottimale delle pagine . . . . . . . . . . . . . . . . . . . 75

8.4.4 Sostituzione delle pagine usate meno recentemente (LRU) . . . . . . 75

8.4.5 Sostituzione delle pagine per approssimazione a LRU . . . . . . . . 76

8.4.6 Sostituzione delle pagine basata su conteggio . . . . . . . . . . . . . 77

8.5 Allocazione dei frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

8.5.1 Numero minimo di frame . . . . . . . . . . . . . . . . . . . . . . . . 78

8.5.2 Allocazione globale e allocazione locale . . . . . . . . . . . . . . . . 78

8.5.3 Accesso non uniforme alla memoria . . . . . . . . . . . . . . . . . . 79

8.6 Thrashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

8.6.1 Cause del thrashing . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

8.6.2 Modello del working set . . . . . . . . . . . . . . . . . . . . . . . . 80

8.6.3 Frequenza dei page fault . . . . . . . . . . . . . . . . . . . . . . . . 81

8.7 Altre considerazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

8.7.1 Dimensione delle pagine . . . . . . . . . . . . . . . . . . . . . . . . 81

8.7.2 Portata del TLB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

8.7.3 Tabella delle pagine invertita . . . . . . . . . . . . . . . . . . . . . 82

8.7.4 Struttura dei programmi . . . . . . . . . . . . . . . . . . . . . . . . 82

9 Parte Quinta, Capitolo 11: Memoria di massa 83

9.1 Struttura dei dispositivi di memorizzazione . . . . . . . . . . . . . . . . . . 84

9.1.1 Dischi rigidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

9.1.2 Dispositivi NVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

9.2 Gestione delle unità di memoria secondaria . . . . . . . . . . . . . . . . . . 85

9.2.1 Formattazione del disco, partizioni e volumi . . . . . . . . . . . . . 86

9.2.2 Blocco d’avviamento . . . . . . . . . . . . . . . . . . . . . . . . . . 86

9.2.3 Blocchi difettosi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

9.3 Gestione dell’area di avvicendamento (swap space) . . . . . . . . . . . . . 87

9.3.1 Uso dell’area di swap . . . . . . . . . . . . . . . . . . . . . . . . . . 88

9.3.2 Collocazione dell’area di swap . . . . . . . . . . . . . . . . . . . . . 88

9.4 Connessione dei dispositivi di memorizzazione . . . . . . . . . . . . . . . . 88

9.4.1 Memoria secondaria connessa alla macchina . . . . . . . . . . . . . 88

9.4.2 Memoria secondaria connessa alla rete . . . . . . . . . . . . . . . . 88

9.4.3 Memoria secondaria su cloud . . . . . . . . . . . . . . . . . . . . . . 89

9.4.4 Storage-area network e storage array . . . . . . . . . . . . . . . . . 89

9.5 Strutture RAID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4

9.5.1 Miglioramento dell’affidabilità tramite la ridondanza . . . . . . . . 89

9.5.2 Miglioramento delle prestazioni tramite il parallelismo . . . . . . . . 90

9.5.3 Livelli RAID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

10 Parte Quinta, Capitolo 12: Sistemi di I/O 93

10.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

10.2 Hardware di I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

10.2.1 I/O memory mapped . . . . . . . . . . . . . . . . . . . . . . . . . . 94

10.2.2 Polling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

10.2.3 Interruzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

10.2.4 Accesso diretto alla memoria (DMA) . . . . . . . . . . . . . . . . . 96

10.2.5 Concetti principali dell’hardware I/O . . . . . . . . . . . . . . . . . 97

10.3 Interfaccia di I/O delle applicazioni . . . . . . . . . . . . . . . . . . . . . . 98

10.3.1 Dispositivi con trasferimento a blocchi e a caratteri . . . . . . . . . 99

10.3.2 I/O non bloccante e asincrono . . . . . . . . . . . . . . . . . . . . . 99

11 Parte Sesta, Capitolo 13: Interfaccia del File System 101

11.1 Concetto di file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

11.1.1 Attributi dei file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

11.1.2 Operazioni sui file . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

11.1.3 Tipi di file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

11.1.4 Struttura dei file . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

11.1.5 Struttura interna dei file . . . . . . . . . . . . . . . . . . . . . . . . 105

11.2 Metodi di accesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

11.2.1 Accesso sequenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

11.2.2 Accesso diretto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

11.2.3 Altri tipi di accesso . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

11.3 Struttura delle directory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

11.3.1 Directory a un livello . . . . . . . . . . . . . . . . . . . . . . . . . . 107

11.3.2 Directory a due livelli . . . . . . . . . . . . . . . . . . . . . . . . . . 107

11.3.3 Directory con struttura ad albero . . . . . . . . . . . . . . . . . . . 108

11.4 Protezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

11.4.1 Tipi d’accesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

11.4.2 Controllo degli accessi . . . . . . . . . . . . . . . . . . . . . . . . . 110

11.4.3 Altri metodi di protezione . . . . . . . . . . . . . . . . . . . . . . . 110

12 Parte Sesta, Capitolo 14: Realizzazione del File System 112

12.1 Struttura del file system . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

12.2 Operazioni del file system . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

12.2.1 Panoramica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

12.2.2 Utilizzo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

12.3 Realizzazione delle directory . . . . . . . . . . . . . . . . . . . . . . . . . . 116

12.3.1 Lista lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

12.3.2 Tabella hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

5

12.4 Metodi di allocazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

12.4.1 Allocazione contigua . . . . . . . . . . . . . . . . . . . . . . . . . . 117

12.4.2 Allocazione concatenata . . . . . . . . . . . . . . . . . . . . . . . . 118

12.4.3 Allocazione indicizzata . . . . . . . . . . . . . . . . . . . . . . . . . 119

13 Argomenti Avanzati, Capitolo 18: Macchine Virtuali 120

13.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

13.2 Storia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

13.3 Vantaggi e caratteristiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

6

Chapter 1

Parte Prima, Capitolo 1:

Introduzione 7

1.1 Introduzione !!!DISCLAIMER!!!

Questo corso si basa fortemente sullo studio del libro Sistemi Operativi: Concetti ed

Esempi di Abraham Silberschatz. I seguenti appunti fungono dunque da guida e riassunto

di quanto studiato sul libro, ma non hanno una funzione sostitutiva. I riferimenti a pagine

e capitoli del libro sono riguardanti la decima edizione Italiana.

L’obiettivo di questo corso, dal punto di vista teorico, è capire con un certo livello di

precisione e dettaglio cosa sia un sistema operativo, le motivazioni dietro lo stesso e come

funzioni. Dal punto di vista pratico sarà scrivere un programma che invoca correttamente

delle (system calls). Questo percorso ha inizio con questa prima parte, che

syscall

comprende delle definizioni di base di sistema operativo, dei cenni storici e uno studio

della struttura di un sistema operativo.

1.2 Cosa è un Sistema Operativo

Un Sistema Operativo è innanzitutto un programma, nonostante abbia struttura e fun-

zioni piuttosto diverse da quelle dei programmi con cui siamo abituati a interagire.

Per capire la funzione di un SO e in che modo è diverso da tutti gli altri programmi,

ci conviene posizionarlo all’interno di un contesto software e hardware:

Figure 1.1: Componenti di un sistema elaborativo.

Facciamo dunque una suddivisione dell’intero sistema elaborativo in quattro compo-

nenti, e in particolare vediamo che l&rsq