Appunti di Sistemi Operativi

Sistemi Operativi M

Nicola Severini

Marco Boschi, Matteo Galletti e Marco Rossini

A.A. 2017–2018

1 Virtualizzazione 1

1.1 Virtualizzazione di sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Emulazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Cenni storici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Realizzazione del VMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4.1 VMM di sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4.2 Supporto hardware alla virtualizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4.2.1 VMM in architetture non virtualizzabili . . . . . . . . . . . . . . . . . . . . . 4

1.4.2.2 Architetture virtualizzabili . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4.3 VMM nell’architettura x86 classica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5 Xen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.6 Migrazione VM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Protezione 7

2.1 Modelli, politiche e meccanismi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Dominio di protezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3 Matrice degli accessi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3.1 Realizzazione della matrice degli accessi . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3.2 Revoca dei diritti di accesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3.3 Soluzione mista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Sicurezza multilivello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4.1 Bell-La Padula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4.2 Biba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.5 Reference Monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Programmazione concorrente 12

3.1 Processi non sequenziali e tipi di interazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Esempio 3.1 – Lettura ed elaborazione di un file . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2 Architetture e linguaggi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2.1 Costrutti linguistici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.3 Proprietà dei programmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4 Modello a memoria comune 17

4.1 Regione critica condizionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Esempio 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.2 Richiami al problema della mutua esclusione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.3 Strumenti di sincronizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.3.1 Semaforo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.3.1.1 Semaforo di mutua esclusione . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.3.1.2 Semafori a evento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3.1.2.1 Problema del rendezvous . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3.1.2.2 Semafori binari composti . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3.1.3 Semafori condizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.3.1.4 Semafori risorsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Esempio 4.2 – Gestione di un pool di risorse equivalenti . . . . . . . . . . . . . 25

i

Esempio 4.3 – Problema dei produttori-consumatori con semafori risorsa . . . . 25

4.3.1.5 Condizione di sincronizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.3.1.6 Semafori privati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Esempio 4.4 – Applicazione dei semafori privati . . . . . . . . . . . . . . . . . . 27

4.3.1.7 Realizzazione dei semafori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5 Kernel di un sistema multiprogrammato 31

5.1 Kernel in sistemi monoprocessore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.1.1 Code e processi in esecuzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.1.2 Funzioni del kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.1.2.1 Cambio di contesto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.1.3 Semafori monoprocessore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.1.3.1 Realizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

P

5.1.3.2 Realizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

V

5.1.3.3 Passaggio dall’ambiente del kernel all’ambiente dei processi e viceversa . . . 35

5.2 Kernel in sistemi multiprocessore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.2.1 Modelli architetturali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.2.1.1 SMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.2.1.2 Kernel distinti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5.2.1.3 Confronto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.2.2 Semafori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.2.2.1 Modello SMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Esempio 5.1 – Processo risvegliato prioritario . . . . . . . . . . . . . . . . . . . 37

5.2.2.2 Modello a kernel distinti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.2.2.2.1 Semafori condivisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Esempio 5.2 – sospensiva su un semaforo condiviso . . . . . . . . . . . 38

P S

Esempio 5.3 – su un semaforo con rappresentanti in coda . . . . . . . . 38

V

5.2.2.2.2 Realizzazione dei semafori . . . . . . . . . . . . . . . . . . . . . . . . 38

6 Modello a scambio di messaggi 40

6.1 Primitive di comunicazione sincrone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.1.1 Definizione del canale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.1.2 Invio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.1.3 Ricezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6.1.4 Comando con guardia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.1.4.1 Comando con guardia alternativo . . . . . . . . . . . . . . . . . . . . . . . . 42

6.1.4.2 Comando con guardia ripetitivo . . . . . . . . . . . . . . . . . . . . . . . . . 42

Esempio 6.1 – Processo server . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.2 Primitive di comunicazione asincrone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.2.1 Risorsa condivisa con una sola operazione . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.2.2 Risorsa condivisa con più operazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

6.2.2.1 Soluzione senza comandi con guardia . . . . . . . . . . . . . . . . . . . . . . 44

6.2.2.2 Soluzione con comandi con guardia . . . . . . . . . . . . . . . . . . . . . . . 45

6.2.3 Risorsa condivisa con più operazioni e condizioni di sincronizzazione . . . . . . . . . . 45

6.3 Modelli di processi servitori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.4 Realizzazione primitive asincrone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.4.1 Architettura mono e multiprocessore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.4.1.1 Ricezione su più canali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4.2 Architetture distribuite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.4.2.1 Pacchetti, interfacce e canali . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.5 Realizzazione primitive sincrone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Esempio 6.2 – Mailbox di lunghezza finita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6.5.1 Uso di semafori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

ii

6.5.2 Uso di primitive asincrone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6.5.3 Uso di primitive del kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

7 Comunicazione con sincronizzazione estesa 54

7.1 RPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

7.2 Rendezvous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

7.2.1 Selezione delle richieste in base ai parametri di ingresso . . . . . . . . . . . . . . . . . 55

8 Algoritmi di sincronizzazione distribuiti 56

8.1 Soluzione centralizzata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

8.2 Soluzione distribuita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

8.2.1 Algoritmo Ricart-Agrawala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Esempio 8.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

8.2.2 Algoritmo Token Ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

8.2.3 Algoritmi di elezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

8.2.3.1 Bully . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

8.2.3.2 Elezione ad anello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

8.3 Algoritmi per la gestione del tempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

8.3.1 Orologi logici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

9 Azioni atomiche 60

9.1 Serializzabilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Esempio 9.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

9.2 Tutto o niente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

9.3 Two phase lock protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Esempio 9.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

9.3.1 Commit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

9.3.1.1 Meccanismo di ripristino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

9.4 Realizzazione di azioni atomiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

9.4.1 Caso monoprocesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

9.4.2 Caso multiprocesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

9.4.2.1 Two phase commit protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

9.4.2.2 Modello a memoria comune . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

9.4.2.3 Modello a scambio di messaggi . . . . . . . . . . . . . . . . . . . . . . . . . . 65

9.4.2.4 Malfunzionamenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

9.4.3 Azioni atomiche nidificate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

9.5 Realizzione della memoria stabile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

A Esercitazione I 68

A.1 Standard POSIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

A.2 pthreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

A.2.1 Identificativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

A.2.2 Creazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

A.2.3 Terminazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

A.2.4 Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

A.2.5 Compilazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

A.2.6 Semafori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

A.2.6.1 Mutua esclusione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

A.2.6.1.1 Inizializzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

A.2.6.1.2 Lock e unlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

A.2.6.2 Semafori di LinuxThreads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

A.2.6.2.1 Inizializzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

iii

B Modelli di processi servitori 71

B.1 Pool di risorse equivalenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

B.2 Simulazione di un semaforo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

B.3 Pool di risorse equivalenti con priorità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

B.4 Produttori-consumatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

B.5 Mailbox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

C Esercitazione III 76

Esempio C.1 – Hello World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

C.1 Costrutti linguistici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

C.1.1 Dichirazioni e definizioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

C.1.1.1 Short declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

C.1.2 Assegnamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

C.1.3 If . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

C.1.4 For . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

C.1.5 Switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

C.1.6 Funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

C.1.7 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

C.1.8 Struct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

C.2 Struttura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Esempio C.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

C.3 Concorrenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

C.3.1 Crezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

C.4 Canali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

C.4.1 Inizializzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

C.4.2 Utilizzo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

C.4.2.1 Invio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

C.4.2.2 Ricezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

Esempio C.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

C.4.2.3 Sincronizzazione padre-figlio . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

C.4.2.4 Funzioni-canali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

C.4.2.5 Chiusura canale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

C.4.2.6 Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

C.4.3 Send asincrone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

C.5 Select . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

C.5.1 Guardia logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

D Esercitazione V 84

D.1 Costrutti linguistici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

D.1.1 Tipi scalari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

D.1.2 Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

D.1.3 Record . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

D.1.4 Puntatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

D.1.5 Istruzioni di controllo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

D.1.5.1 If . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

D.1.5.2 Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

D.1.5.3 For-each . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

D.2 Concorrenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

D.2.1 Select . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

D.2.2 Famiglie di entry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

D.2.3 Politiche basate su priorità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

iv

E MapReduce 90

E.1 Apache Spark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .