Sistemi operativi

Sistemi Operativi

Facoltà di Informatica

Antonio Mastrolembo Ventura

2023/2024

Sistemi Operativi INDICE

Indice

1 Introduzione 4

1.1 Che cosa fa un sistema operativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Organizzazione di un sistema elaborativo . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Interruzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.2 Struttura della memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.3 Sistemi monoprocessore e multiprocessore . . . . . . . . . . . . . . . . . . . . . . 7

1.2.4 Cluster di elaboratori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Attività del sistema operativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.1 Multiprogrammazione e multitasking . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.2 Duplice modalità di funzionamento . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Strutture dei sistemi operativi 10

2.1 Chiamate di sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.1 API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Linker, loader e dipendenza dal sistema operativo . . . . . . . . . . . . . . . . . . . . . . 11

2.3 Struttura del sistema operativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3.1 Struttura monolitica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3.2 Struttura stratificata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3.3 Struttura Microkernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.4 Moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.5 Sistemi ibridi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.6 macOS, IOS e Android . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Processi 15

3.1 Stato del processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Blocco di controllo del processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3 Scheduling dei processi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.4 Cambio di contesto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.5 Creazione di un processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4 Algoritmi di scheduling della CPU 20

4.1 Scheduling con e senza prelazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.2 Criteri di scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3 Algoritmi di scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3.1 Scheduling first-come, first-served . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3.2 Scheduling shortest-job-first . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.3.3 Scheduling round-robin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3.4 Scheduling con priorità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.3.5 Scheduling a code multilivello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.3.6 Scheduling a code multilivello con retroazione . . . . . . . . . . . . . . . . . . . . 26

5 Thread e concorrenza 27

5.1 Vantaggi della programmazione multithread . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.2 Programmazione multicore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.2.1 Le sfide della programmazione multicore . . . . . . . . . . . . . . . . . . . . . . . 29

5.2.2 Tipi di parallelismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.3 Modelli di supporto al multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.3.1 Modello da molti a uno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.3.2 Modello da uno a uno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

1

Sistemi Operativi INDICE

5.3.3 Modello da molti a molti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.4 Librerie dei thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.5 Scheduling dei thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.5.1 Ambito della contesa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6 Strumenti di sincronizzazione 35

6.1 Problema del produttore-consumatore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6.1.1 Race conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

6.2 Problema della sezione critica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6.3 Soluzione di Peterson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.4 Supporto hardware per la sincronizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.4.1 Barriere di memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.4.2 Istruzioni hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

6.5 Lock mutex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6.6 Semafori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.6.1 Uso dei semafori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.6.2 Implementazione dei semafori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.7 Lock mutex e Semafori POSIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.7.1 Lock mutex POSIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.7.2 Semafori POSIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

6.8 Classici problemi di sincronizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.8.1 Problema produttore-consumatore con buffer limitato . . . . . . . . . . . . . . . 47

6.8.2 Problema dei lettori-scrittori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.8.3 Problema dei cinque filosofi (dining philosophers) . . . . . . . . . . . . . . . . . . 49

6.9 Monitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.10 Liveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6.11 Valutazione delle soluzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

7 Memoria centrale 53

7.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

7.1.1 Hardware di base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

7.1.2 Associazione degli indirizzi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

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

7.2 Allocazione contigua della memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

7.3 Paginazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

7.3.1 Supporto hardware alla paginazione . . . . . . . . . . . . . . . . . . . . . . . . . 59

7.4 Struttura della tabella delle pagine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.4.1 Paginazione gerarchica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.4.2 Tabelle hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

7.4.3 Tabella delle pagine invertita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

7.5 Avvicendamento dei processi (swapping) . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

8 Memoria virtuale 65

8.1 Paginazione su richiesta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

8.2 Sostituzione delle pagine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8.2.1 Sostituzione di pagina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8.2.2 Sostituzione delle pagine secondo l’ordine di arrivo (FIFO) . . . . . . . . . . . . 69

8.2.3 Sostituzione ottimale delle pagine (OPT) . . . . . . . . . . . . . . . . . . . . . . 70

8.2.4 Sostituzione delle pagine usate meno recentemente (LRU) . . . . . . . . . . . . . 71

8.3 Allocazione dei frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

8.3.1 Algoritmi di allocazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

8.3.2 Allocazione globale e locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

2

Sistemi Operativi INDICE

8.4 Thrashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

8.4.1 Modello del working set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

8.4.2 Frequenza dei page fault . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

8.5 Compressione della memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

8.6 Allocazione di memoria del kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

8.6.1 Sistema buddy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

8.6.2 Allocazione a lastre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

9 Interfaccia del file system 78

9.1 Concetto di file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

9.1.1 Attributi dei file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

9.1.2 Operazioni sui file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

9.1.3 Tipi di file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

9.2 Metodi d’accesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

9.2.1 Accesso sequenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

9.2.2 Accesso diretto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

9.2.3 Altri metodi d’accesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

9.3 Struttura della directory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

9.3.1 Directory a un livello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

9.3.2 Directory a due livelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

9.3.3 Directory con struttura ad albero . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

9.3.4 Directory con struttura a grafo generale . . . . . . . . . . . . . . . . . . . . . . . 83

10 Realizzazione del file system 85

10.1 Struttura del file system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

10.2 Operazioni del file system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

10.3 Realizzazione delle directory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

10.4 Metodi di allocazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

10.4.1 Allocazione contigua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

10.4.2 Allocazione concatenata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

10.4.3 Allocazione indicizzata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

10.5 Gestione dello spazio libero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

10.5.1 Vettore di bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

10.5.2 Lista concatenata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

10.5.3 Raggruppamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

10.5.4 Conteggio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

3

Sistemi Operativi 1 Introduzione

1 Introduzione

Che cos’è un sistema operativo? Un sistema operativo è un programma (software) che agisce da

intermediario tra l’utente e la struttura fisica (hardware) di un calcolatore (una sorta di mediatore). Lo

scopo è quello di offrire un ambiente nel quale l’utente possa eseguire programmi in modo efficiente e

conveniente. I sistemi operativi sono ovunque, dalle automobili, agli elettrodomestici, agli smartphone,

ai pc, ecc...

Per comprendere a fondo il ruolo di un sistema operativo in un ambiente di elaborazione moderno è

importante capire l’organizzazione e l’architettura dell’hardware del computer, che include la CPU,

la memoria, i dispositivi I/O e i dispositivi di memorizzazione. Una responsabilità fondamentale del

sistema operativo è allocare queste risorse ai programmi.

1.1 Che cosa fa un sistema operativo

Un sistema di elaborazione si può suddividere in quattro com-

ponenti: hardware, sistema operativo, programmi applicativi e

un utente.

L’hardware, composto da CPU, memoria e dispositivi di

I/O, fornisce al sistema le risorse elaborative fondamentali.

I programmi applicativi definiscono il modo in cui si usano

queste risorse per la risoluzione dei problemi computazionali

degli utenti. Il sistema operativo offre gli strumenti per impie-

gare in modo corretto queste risorse: non compie operazioni

di per sé utili, ma fornisce semplicemente un ambiente nel

quale altri programmi possono lavorare in modo utile.

Riassumendo, possiamo distinguere il ruolo del sistema operativo per l’utente e per il sistema: per

l’utente, la facilità d’uso del dispositivo che utilizza è fondamentale: un insieme di programmi e ser-

vizi software progettati per fornire un ambiente interattivo e user-friendly. Per il calcolatore invece,

il sistema operativo è il programma più vicino al suo hardware, un assegnatore di risorse e dunque

un gestore di esse. Di fronte a richieste di risorse numerose ed eventualmente conflittuali, il sistema

operativo deve decidere come assegnarle agli specifici programmi affinchè il calcolatore operi in modo

efficiente ed equo.

Il kernel è il nucleo centrale di un sistema operativo, il solo programma che funziona sempre nel

calcolatore. Oltre al kernel troviamo i programmi di sistema, associati al sistema operativo, e i

programmi applicativi che includono tutti i programmi non correlati al sistema operativo. In si-

stemi operativi mobili troviamo anche un middleware: fa in modo che le diverse parti del software

possano collaborare senza problemi. 4

Sistemi Operativi 1 Introduzione

1.2 Organizzazione di un sistema elaborativo

Un moderno calcolatore è composto da una o più CPU e da un certo numero di controllori di disposi-

tivi connessi attraverso un canale di comunicazione comune (bus) che permette l’accesso alla memoria

si occupa di un solo tipo di dispositivo fisico

condivisa dal sistema. Ciascun controllore (hardware)

e ha il compito di far comunicare il dispositivo con il calcolatore in modo corretto. Ad esempio, se

hai una stampante collegata al computer, c’è un controllatore che si occupa di tradurre i comandi di

stampa del computer in istruzioni comprensibili per la stampante.

I sistemi operativi includono tipicamente dei driver del dispositivo per ciascun tipo di dispositivo.

Questi driver sono software specializzati che conoscono le specifiche di un determinato dispositivo e for-

niscono un’interfaccia uniforme tra il dispositivo e il sistema operativo. Controllori e driver comunicano

per mezzo di interrupt.

1.2.1 Interruzioni

L’hardware della CPU dispone di una linea, chiamata linea di richiesta di interruzione o sempli-

cemente linea degli interrupt che la CPU controlla dopo l’esecuzione di ogni istruzione. Ma cosa

sono e come funzionano?

Gli interrupt sono utilizzati per gestire eventi o richieste di interruzione che possono verificarsi in modo

asincrono, cioè in qualsiasi momento, mentre il processore sta eseguendo altre istruzioni.

Andiamo per step:

1. Gli interrupt possono essere generati da diverse sorgenti, tra cui dispositivi hardware (controllori

dei dispositivi), errori di esecuzione (come divisioni per zero), richieste software e timer;

2. Il processore deve costantemente monitorare se ci sono interrupt in sospeso, e questo in genere

avviene tra un’istruzione e un’altra. Prima di gestire l’interrupt, il processore salva il suo stato

corrente, inclusi registri importanti, il valore del contatore di programma (PC) che indica l’istru-

zione corrente e altre informazioni necessarie per riprendere l’esecuzione dal punto in cui è stata

interrotta.

3. Una volta identificato il tipo di interrupt, il processore va nella tabella degli interrupt (un array)

in cui ogni cella contiene l’indirizzo di memoria della routine da eseguire;

4. Dopo aver eseguito la routine, il processore ripristina lo stato salvato precedentemente e gli

consente di tornare all’esecuzione normale del programma dal punto in cui è stato interrotto.

La CPU ha due linee di richiesta di interruzione: una è non mascherabile, riservata ad eventi che il

processore deve obbligatoriamente affrontare e non può ignorare o rimandare; sono utilizzate per eventi

critici o situazioni di emergenza che richiedono una risposta immediata. La seconda è mascherabile,

utilizzata per eventi meno critici o per eventi che possono essere gestiti in un secondo momento senza

causare gravi problemi. 5

Sistemi Operativi 1 Introduzione

1.2.2 Struttura della memoria

La CPU può caricare istruzioni esclusivamente dalla memoria, quindi tutti i programmi da eseguire

devono esservi caricati. La memoria principale è chiamata memoria ad accesso casuale (random

access memory, RAM). Quando il computer esegue programmi o elabora dati, carica temporaneamente

queste informazioni nella RAM in modo che possano essere rapidamente accedute e modificate. La

RAM è veloce nel fornire dati al processore, ma è volatile, il che significa che i dati vengono persi

quando spegni il computer.

I computer utilizzano anche altri tipi di memoria: le EEPROM (memoria di sola lettura elet-

tricamente cancellabile e programmabile), sono lente e contengono principalmente programmi

statici e dati utilizzati con poca frequenza.

Abbiamo anche un