SistemiOperativi

Capitolo 1

Generalità sui sistemi operativi

Un computer moderno è un sistema complesso costituito da processori, memoria centrale, dischi e dispositivi di input/output. Per gestire questa complessità, i computer dispongono di uno strato software fondamentale: il sistema operativo.

I computer operano principalmente in due modalità:

Modalità kernel (o supervisor): Permette l’accesso completo a tutto l’hardware e l’esecuzione di qualsiasi istruzione la macchina sia in grado di svolgere. È qui che viene eseguito il sistema operativo.
Modalità utente: È la modalità in cui “gira” il resto del software e dei programmi applicativi, con privilegi limitati.

A differenza delle normali applicazioni, i sistemi operativi sono software molto grandi, complessi e longevi (sistemi come Linux o Windows raggiungono dimensioni nell’ordine dei cinque milioni di righe di codice).

Che cos’è un sistema operativo

Il sistema operativo è il software che opera in modalità kernel e svolge due funzioni principali e distinte:

Il sistema operativo come macchina estesa

L’architettura hardware nativa di un computer è primitiva e complessa da programmare. Il sistema operativo ha il compito di nascondere questa complessità, offrendo ai programmatori un insieme di astrazioni chiare, eleganti e coerenti.

Driver: Software che fornisce un’interfaccia semplificata per la gestione dell’hardware (ad esempio, per leggere o scrivere su un disco), sollevando il programmatore dall’occuparsi dei dettagli tecnici di basso livello.

Il sistema operativo come gestore delle risorse

Il sistema operativo fornisce un’allocazione ordinata e controllata delle risorse hardware tra i vari programmi. Questa gestione include la condivisione delle risorse, definita multiplexing, che avviene in due modalità:

Multiplexing nel tempo: Più programmi o utenti utilizzano la stessa risorsa alternandosi (facendo a turno).
Multiplexing nello spazio: I clienti non si alternano, ma ognuno ottiene una porzione specifica della risorsa.

Storia dei sistemi operativi

Prima generazione (1945-1955): Valvole termoioniche. Assenza totale di sistemi operativi; la programmazione avveniva in linguaggio macchina tramite cavi e interruttori.
Seconda generazione (1955-1965): Transistor e sistemi batch (a lotti). Introduzione dei primi software di base per automatizzare il passaggio da un lavoro (job) all’altro senza l’intervento umano continuo.
Terza generazione (1965-1980): Circuiti integrati (IC) e multiprogrammazione. Nascono il partizionamento della memoria e il timesharing (condivisione del tempo) per permettere a più utenti di interagire contemporaneamente con la macchina.
Quarta generazione (1980-oggi): Personal Computer. Grazie ai circuiti integrati su larga scala (LSI), i computer diventano personali. Nascono sistemi operativi come MS-DOS, UNIX e, successivamente, le interfacce grafiche (GUI) con Windows e macOS.
Quinta generazione (1990-oggi): Dispositivi mobili e cloud computing. Sistemi operativi fortemente interconnessi per smartphone, tablet e infrastrutture di rete.

Analisi dell’hardware

Un sistema operativo è intimamente legato all’hardware del computer su cui gira: ne estende l’insieme di istruzioni e ne gestisce le risorse.

Processori

La CPU (Central Processing Unit) è il “cervello” del computer. Il suo ciclo di base consiste nel prelevare un’istruzione dalla memoria (fetch), decodificarla per comprenderne tipo e operandi, eseguirla e passare alla successiva, fino al termine del programma.

Per migliorare le prestazioni, le moderne CPU adottano architetture avanzate:

Pipeline: Organizzazione che permette di eseguire più istruzioni contemporaneamente (es. mentre si esegue l’istruzione n, si decodifica la n+1 e si preleva la n+2).
Multithreading (o hyperthreading): Permette alla CPU di mantenere lo stato di due thread diversi, i quali appaiono al sistema operativo come due CPU separate.
Multicore: Chip CPU che contengono al loro interno più processori completi (core), richiedendo l’uso di un sistema operativo multiprocessore.
GPU (Graphics Processing Unit): Processori dotati di migliaia di core microscopici, eccezionali per l’esecuzione parallela di piccoli calcoli (come il rendering poligonale).

I Registri della CPU

Poiché l’accesso alla memoria è lento, la CPU utilizza memorie interne ad altissima velocità chiamate registri:

Program counter: Contiene l’indirizzo di memoria della successiva istruzione da eseguire.
Stack pointer: Puntatore allo stack.
PSW (Program Status Word): Registro che contiene i bit di condizione, la priorità della CPU e il bit che controlla la modalità operativa (utente o kernel).

Nota Operativa: Quando il sistema operativo ferma un programma per farne partire un altro (multiplexing temporale), deve salvare lo stato di tutti i registri per poterli ricaricare al riavvio del programma sospeso questo fenomeno si chiama context switching. Chiamate di Sistema e Interruzioni

System Call (Chiamata di sistema): Richiesta effettuata da un programma utente per ottenere servizi dal sistema operativo.
TRAP: Istruzione che cambia la modalità operativa da utente a kernel e avvia il sistema operativo. Le trap possono anche essere generate dall’hardware per segnalare situazioni eccezionali (es. divisione per zero).

Memoria

Poiché non esiste una memoria ideale (veloce, capiente e a basso costo contemporaneamente), il sistema è strutturato in strati gerarchici:

Registri della CPU: Strato alla sommità, velocissimi e a capacità ridotta.
Memoria Cache: Gestita dall’hardware. Si divide in Cache L1 (interna alla CPU, fornisce istruzioni codificate) e Cache L2. Conserva le linee di memoria usate più di frequente.
Memoria Principale (RAM): La memoria di lavoro vera e propria ad accesso casuale. Gestisce tutte le richieste della CPU non soddisfatte dalla cache.
Memoria non volatile: Include la ROM (Read Only Memory, programmata dal costruttore e non modificabile), la EEPROM (cancellabile elettricamente) e le memorie flash.

Dischi

L’Hard Disk (disco magnetico) si trova sotto la RAM nella gerarchia. È lento perché è un’unità meccanica formata da piatti metallici rotanti e un braccio meccanico.

Traccia: Regione anulare letta da una testina a una data posizione del braccio.
Cilindro: L’insieme di tutte le tracce relative a una specifica posizione del braccio.

Dispositivi di I/O

I dispositivi di Input/Output sono composti dal dispositivo fisico e da un controller (il chip che lo governa fisicamente). Il sistema operativo vede solo l’interfaccia del controller.

Device Driver: Software specifico necessario per controllare un determinato dispositivo di I/O. Gira in modalità kernel e può essere installato in tre modi:
1. Ricollegando il kernel al driver e riavviando.
2. Creando una voce in un file di sistema e riavviando.
3. Installazione “a caldo” mentre il sistema è in esecuzione (senza riavvio).

Gestione dell’Input/Output: Avviene tramite tre metodi principali:

Busy waiting: Il driver avvia l’I/O e interroga continuamente il dispositivo per controllare se ha terminato. Svantaggio: Impegna inutilmente la CPU.
Interrupt: Il driver avvia il dispositivo e si sospende. Al termine, il controller genera un interrupt (interruzione) per segnalare il completamento (il testo fa riferimento al vettore degli interrupt). La CPU può disabilitare temporaneamente gli interrupt per non essere interrotta in momenti inopportuni.
DMA (Direct Memory Access): Utilizza un hardware speciale che controlla il flusso di dati tra memoria e controller senza l’intervento costante della CPU. Al termine, il chip DMA genera un interrupt.

Panoramica dei vari sistemi operativi

Sistemi operativi per mainframe: Orientati all’esecuzione simultanea di numerosi lavori con massicce richieste di I/O. Offrono elaborazione di transazioni, timesharing e servizi batch, ossia l’esecuzione completamente automatica e sequenziale di grandi volumi di operazioni raggruppate in lotti (es. fatturazione o calcolo stipendi), senza necessità di interazione da parte dell’utente.
Sistemi operativi per server: Servono molteplici utenti in rete, permettendo la condivisione di risorse hardware e software.
Sistemi operativi multiprocessore: Varianti dei sistemi server ottimizzate per comunicazione e coerenza. Utilizzati sempre più spesso anche sui PC desktop dotati di chip multicore.
Sistemi operativi per personal computer: Progettati per supportare in modo ottimale un singolo utente.
Sistemi operativi per computer palmari (PDA): Sistemi sofisticati per dispositivi mobili, in grado di gestire CPU multicore, GPS, fotocamere e grandi memorie.
Sistemi operativi integrati (embedded): Installati su dispositivi non considerati veri computer (es. forni a microonde). Il software è su ROM, non accetta app esterne, rendendo inutile la protezione tra applicazioni.
Sistemi operativi real-time: Sistemi in cui il tempo è il parametro critico.
- Hard real-time: Forniscono garanzie assolute che un’azione avvenga in un momento preciso.
- Soft real-time: Tollerano il mancato rispetto occasionale di una scadenza.

Chiamate di sistema (System Call)

Le system call rappresentano l’interfaccia standard tra i programmi utente e il sistema operativo. Quando un programma ha bisogno di un servizio privilegiato (come leggere un file, allocare memoria o creare un processo), esegue una system call tramite un’istruzione TRAP, passando dalla modalità utente alla modalità kernel.

Esempi di standard per le system call sono POSIX (usato da Unix e Linux) e Win32 API (usato da Windows).

Struttura di un sistema operativo

Di seguito le strutture dei vari tipi di sistema operativo:

Sistemi monolitici

È l’organizzazione più comune. L’intero sistema operativo è un singolo programma eseguito in modalità kernel, formato da una raccolta di procedure collegate (linkate) tra loro. Poiché le procedure si richiamano liberamente senza restrizioni, il sistema risulta spesso pesante e difficile da capire.

Sistemi a livelli

Il sistema è organizzato gerarchicamente. Un esempio classico prevede sei livelli:

Livello 0: Allocazione del processore (multiprogrammazione base).
Livello 1: Gestione della memoria.
Livello 2: Comunicazione tra processi e console operatore.
Livello 3: Gestione dei dispositivi di I/O.
Livello 4: Programmi utente.
Livello 5: Operatore di sistema.

Microkernel

Nasce per garantire un’altissima stabilità. Il sistema è diviso in piccoli moduli ben definiti, ma solo il microkernel viene eseguito in modalità kernel. Driver, file system e server girano tutti in modalità utente. I programmi ottengono i servizi inviando brevi messaggi ai processi server.

Modello client-server

È una variazione del microkernel che distingue due classi di processi: i server (che forniscono i servizi) e i client (che li utilizzano). La comunicazione avviene tramite passaggio di messaggi (ottimizzabile se client e server risiedono sulla stessa macchina).

Macchine virtuali

Si basano su un monitor di macchina virtuale (oggi chiamato hypervisor di tipo 1) che gira direttamente sull’hardware e fornisce ai livelli superiori numerose macchine virtuali. Ogni macchina virtuale è identica all’hardware reale e può eseguire un proprio sistema operativo (guest).

Hypervisor di tipo 2: Strategia ibrida utilizzata comunemente sui PC (es. VMware Workstation). Non gira direttamente sull’hardware, ma ha bisogno di un sistema operativo host preesistente per installare e avviare il sistema operativo guest su un disco virtuale.

Capitolo 2

Processi

Nei computer moderni è normale che vengano svolti molti compiti contemporaneamente, si consideri innanzitutto un Web server. Arrivano richieste per pagine web da ogni dove, quindi diventa necessario un qualche sistema per modellare e controllare tale concorrenza. Così nasce il modello dei processi. In questo modello, tutto il software eseguibile sul computer è organizzato in una serie di attività sequenziali detti processi.

Processo: È un’istanza di un programma in esecuzione. Rappresenta un’attività in corso dotata di un proprio programma, di input, di output e di uno stato interno. Due istanze dello stesso programma costituiscono due processi distinti.
Programma: È un oggetto passivo (codice) che può essere memorizzato su disco.

Ricordiamo

In questo capitolo daremo per assodato che vi sia una sola CPU. Sempre più spesso tuttavia questo assunto non è valido, dato che i nuovi chip sono spesso multicore, con due, quattro o più CPU.

L’anatomia di un processo in memoria

Quando un processo viene caricato in memoria, è strutturato nei seguenti segmenti:

Sezione Text: Contiene il codice eseguibile vero e proprio.
Sezione Data: Contiene le variabili globali e statiche.
Heap: Memoria allocata dinamicamente a runtime.
Stack: Memoria utilizzata per gestire le chiamate a funzione e le variabili locali.

CPU virtuale e cambio di contesto

Concettualmente, il modello garantisce a ogni processo l’illusione di avere una propria CPU virtuale esclusiva e uno spazio di memoria virtualmente infinito. Nella realtà, la CPU dedica un quanto di tempo a ciascun processo, per poi passare al successivo.

Context Switch: È l’operazione con cui la CPU smette di dedicarsi a un processo per passare al successivo. Vengono salvate le istruzioni e le risorse del processo uscente e caricate quelle del processo entrante.
Multiprogrammazione / Pseudoparallelismo: È l’illusione di parallelismo creata dai continui e rapidissimi cambi di contesto in un sistema single-core.

Creazione dei processi

La creazione di un nuovo processo avviene principalmente in quattro circostanze:

All’avvio del sistema (Boot): Viene creato un processo radice (solitamente con Process ID = 1), che funge da capostipite per l’albero di tutti i processi successivi.
Tramite chiamate di sistema (Syscall): Un processo padre ne crea uno figlio per delegare compiti o distribuire il carico di lavoro (utile specie nei multiprocessori per evitare blocchi).
Azione dell’utente: Tipico dei sistemi interattivi (es. l’avvio di un’app).
Inizio di un job batch: Lo Scheduler, in base alle risorse libere, seleziona un lavoro dalla coda e crea un processo per eseguirlo.

All’avvio del sistema vengono avviati diversi processi, tra questi quelli eseguiti in background vengono chiamati demoni

Chiamate di Sistema per la Creazione

Sistemi UNIX: Usano una combinazione di due chiamate.
- fork: Crea una copia esatta del processo padre (stesso spazio di indirizzamento, permessi e file aperti).
- execve (o analoghe): Invocata solitamente dal processo figlio appena nato, sovrascrive la propria immagine di memoria per eseguire un nuovo programma
Sistemi Windows: Utilizzano un’unica chiamata di sistema atomica chiamata CreateProcess (API Win32). Questa funzione richiede ben 10 parametri (tra cui nome del programma, attributi di sicurezza, priorità, ecc.) e crea direttamente un nuovo processo con la sua immagine di memoria dedicata.

Terminazione dei processi

La chiusura di un processo avviene per:

Uscita normale (Volontaria): Terminazione ordinaria. Avviene tramite la syscall exit in UNIX e ExitProcess in Windows (ritorna un exit status).
Uscita su errore (Volontaria): Terminazione anomala ma gestita e concepita dal programma stesso.
Errore critico (Involontaria): Scatta automaticamente per azioni illegali (divisione per zero, scrittura in zone read-only). L’hardware genera un’eccezione e il processo viene interrotto senza tentativi di ripristino.
Terminato da un altro processo (Involontaria): Un processo uccide un altro processo (se appartengono allo stesso utente, o se si è amministratori). Si usano le syscall kill in UNIX e TerminateProcess in Windows. Quando parliamo della chiamata di sistema kill dobbiamo fare la seguente distinzione:
- Soft Kill: Viene inviato un segnale di chiusura al programma. Il programma può intercettarlo, eseguire una routine di pulizia e chiudersi, oppure persino rifiutare la chiusura.
- Hard Kill: Chiusura forzata e istantanea a priori, senza possibilità di replica per il processo.

Stati di un processo e ciclo di vita

Il ciclo di vita può essere descritto da un automa a 5 stati (3 principali e 2 transitori):

New: Fase transitoria di predisposizione delle risorse all’avvio.
Pronto (Ready): Il processo è pronto a usare la CPU ed è in attesa in una speciale coda gestita dallo Scheduler.
In Esecuzione (Running): Il processo detiene l’unica CPU disponibile in quel momento.
Bloccato (Blocked): Il processo è parcheggiato in attesa di un evento esterno (spesso operazioni di Input/Output “lente”).
Terminated: Fase finale di chiusura.

Per passare da uno stato all’altro abbiamo dei meccanismi di transizione:

Running $\to$ Blocked (Attesa di I/O): Quando un processo effettua una syscall “lenta” (che richiede tempi lunghi di risposta dal SO), si blocca volontariamente per non sprecare cicli di CPU.
- Nota: Blocking wait vs Busy wait: Passare allo stato Bloccato (Blocking wait) è molto più efficiente del Busy wait, perché la CPU non deve sprecare tempo a controllare continuamente se il dato è arrivato; sarà il SO a risvegliare il processo a tempo debito.
Running $\to$ Ready (Prelazione / Interrupt): Se un processo non effettua operazioni di I/O rischia di monopolizzare la CPU. Per evitare che questo accada esiste la prelazione: un’operazione tramite la quale il Sistema Operativo sposta il processo dallo stato di running a quello di ready. Questo avviene quando il processo ha esaurito la quantità massima di tempo CPU che gli era stata assegnata, ed è innescato direttamente tramite un interrupt.

La prelazione

Prelazione (Preemption): È l’operazione tramite cui il sistema operativo interrompe temporaneamente un processo in esecuzione (togliendogli l’uso della CPU) senza alcuna cooperazione da parte del processo stesso, al fine di permettere l’esecuzione di un altro processo.

Gestione dei processi

Per riuscire a gestire il parallelismo e i processi il sistema operativo utilizza:

Tabella dei processi: È una struttura dati dinamica (implementata come lista concatenata) che contiene tutte le informazioni dei processi del sistema.
Process Control Block (PCB): È il record all’interno della Tabella dei Processi. Viene allocato alla creazione del processo e deallocato alla sua morte. Contiene tutto il necessario per permettere il Context Switch senza perdita di dati:
- Stato del processo e Process ID (PID).
- Program Counter (PC) e contenuto dei registri della CPU.
- Limiti di memoria e file aperti.
- Processi imparentati (padre, figli).

TIP

Il PSW (acronimo di Program Status Word, o a volte Processor Status Word) è un registro hardware fondamentale all’interno della CPU che descrive lo stato attuale del processore in un determinato istante.

Le Code

I processi non sono gettati alla rinfusa, ma incolonnati in specifiche code gestite dal sistema operativo.

Coda dei processi pronti: Raccoglie tutti i processi in stato Ready. Non è una struttura in memoria separata, ma sfrutta i PCB della Tabella dei Processi uniti tra loro tramite speciali puntatori.
Code di I/O: Raccoglie i processi in stato Blocked in attesa di una specifica periferica o evento.
Coda di fork: una coda che raccoglie tutti quei processi che stanno perdendo tempo per forkarsi
Coda time slice expired: qua troviamo tutti i processi che hanno consumato tutto il loro tempo dentro la CPU Vediamo che tutte queste code confluiscono dentro la coda dei processi pronti, infatti una volta usciti dalla coda specifica andranno in quella generica per aspettare la CPU.

Thread

Introduzione al Modello a Thread Multipli

Il modello a thread multipli permette di gestire l’esecuzione di un singolo processo suddividendola su più flussi di esecuzione indipendenti. Mentre processi diversi non hanno risorse comuni e sono totalmente indipendenti, i thread appartenenti allo stesso processo condividono le risorse. Avere la possibilità di gestire più flussi è fondamentale per avere programmi complessi e responsivi.

Example

Esempio di un Text Editor: Senza thread, il rendering del file a schermo si bloccherebbe a ogni salvataggio, e il controllo ortografico impedirebbe la scrittura simultanea.

Esempio di un Web Server: Senza thread, le richieste verrebbero gestite una ad una; una richiesta onerosa bloccherebbe le successive, creando code e abbattendo il throughput.

Thread con risorse esclusive o condivise

Tutti i thread generati all’interno di un medesimo processo condividono lo stesso PID (Process ID). Da qui distinguiamo due tipi di thread, classificati in base a come gestiscono le risorse:

Risorse esclusive (Dx): Ogni thread possiede un proprio program counter (per sapere quale istruzione eseguire), propri registri, un proprio stack e un proprio stato (es. ready, running, blocked).
Risorse condivise (Sx): Tutti i thread del processo condividono lo spazio di indirizzamento, l’heap, la memoria globale, il codice (o testo) e i file aperti.

Operazioni, Stati e Context Switch

Lo scheduler del sistema operativo (nei sistemi moderni) tratta i thread come processi a sé stanti. I cambiamenti di stato sono identici a quelli dei processi: Running (in esecuzione), Ready (pronto) o Blocked (bloccato). Le primitive fondamentali dei thread:

thread_create: Un thread genera un nuovo thread.
thread_exit: Il thread chiamante ha finito il lavoro e termina.
thread_join: Un thread si blocca per sincronizzarsi in attesa della fine di un altro thread.
thread_yield: Il thread rilascia volontariamente la CPU per far eseguire qualcun altro.

Context Switch sui thread: Il context switch tra thread dello stesso processo è drasticamente più veloce rispetto a quello tra processi distinti. Il motivo risiede nell’hardware: cambiando solo thread e mantenendo lo stesso spazio di memoria, si solleva l’MMU (Memory Management Unit) dal dover essere riprogrammata.

MMU

L’MMU è un componente hardware (solitamente integrato direttamente all’interno della CPU) che ha il compito fondamentale di gestire l’accesso alla memoria durante l’esecuzione dei programmi.

Il suo scopo principale è la traduzione degli indirizzi di memoria: converte gli indirizzi logici (o virtuali) generati dalla CPU in indirizzi fisici (reali) all’interno della RAM.

Multicore Programming e Concorrenza

L’uso dei thread porta a benefici differenti in base all’hardware sottostante:

Sistemi Single-core: Si ottiene un’esecuzione alternata, ovvero uno pseudo-parallelismo (lo scheduler decide quali thread eseguire alternandoli tra di loro).
Sistemi Multi-core: Si ottiene un parallelismo puro, dove più thread vengono materialmente eseguiti nello stesso esatto istante su core diversi.

La programmazione multi-core non è banale e richiede di gestire quattro criticità principali:

Separazione dei task: Suddividere logicamente il lavoro.
Bilanciamento: Distribuire equamente le responsabilità e la durata temporale dei task tra i thread.
Dipendenze dei dati: Individuare risorse condivise e dipendenze (es. il thread $A$ non può procedere finché non riceve un dato elaborato dal thread $B$ ).
Test e debugging: È estremamente complesso individuare tutti i casi limite e le circostanze anomale nell’esecuzione parallela.

Thread a livello utente (modello 1-a-molti)

Questo modello viene gestito interamente da librerie nello spazio utente, ed è utile per lavorare su Kernel che non supportano nativamente i thread. Il sistema operativo vede solo un unico grande processo e un unico flusso di esecuzione. Lo scambio tra thread è gestito manualmente tramite la primitiva thread_yield, che salva i registri in una tabella locale nello spazio utente.

Punti di forza:
- Scheduling personalizzato: Permette priorità contestuali gestite dall’applicazione, molto più versatili rispetto a quelle generdell’OS.
- Dispatching senza trap: Operando in modalità utente, si evitano le lentissime chiamate a sistema (trap), rendendo i thread estremamente veloci.
Criticità:
- Chiamate bloccanti: Se un thread fa una chiamata lenta (es. I/O su disco), l’OS blocca l’intero processo, fermando di conseguenza tutti i thread utente. Anche i page-fault causano l’interruzione totale.
  - Soluzione (select): Si utilizza la chiamata a sistema select per verificare preventivamente se un’istruzione (es. input da tastiera) è pronta. Se non lo è, per evitare di bloccare il processo, si fa un thread_yield per cedere la CPU e si riprova in seguito.
- Possibilità di non rilascio: In assenza di interrupt hardware (prelazione), se un thread non rilascia volontariamente la CPU, nessun altro thread utente può forzarlo a farlo.

Page fault

Page fault: Se un thread tenta di accedere a una variabile o a un’istruzione che si trova in un’area di memoria non attualmente caricata nella memoria RAM (ad esempio perché è stata spostata nell’area di swap su disco), si genera un’eccezione hardware chiamata page fault.

Thread a livello kernel (Modello 1-a-1)

È il modello nativamente supportato dai sistemi operativi moderni, associando a ogni thread utente un thread a livello Kernel. La tabella dei thread è mantenuta nel Kernel ed è unica per tutti i processi.

Punti di forza: Una chiamata bloccante effettuata da un thread blocca esclusivamente quel thread, risolvendo il problema principale del modello utente.
Svantaggi:
- Context switch più lento: Passare da un thread all’altro richiede l’uso di costose trap di sistema (cambio di contesto simile a quello tra processi).
- Operazioni costose: Creare e distruggere frequentemente thread Kernel rallenta esponenzialmente l’intero sistema operativo.

Modello Ibrido (Molti-a-molti)

Questo modello mira a combinare i punti di forza dell’approccio a livello utente (efficienza e flessibilità) con quelli dell’approccio a livello kernel (vero parallelismo e tolleranza ai blocchi), mitigando i difetti di entrambi.

In pratica, il sistema effettua un multiplexing di numerosi thread a livello utente su un numero limitato (uguale o inferiore) di thread a livello kernel.

Livello Utente: Il programmatore, tramite la libreria, può creare tutti i thread necessari per la logica dell’applicazione. Il context switch tra questi thread rimane rapido perché avviene nello spazio utente.
Livello Kernel: Il sistema operativo fornisce e gestisce un pool di thread a livello kernel, assegnandoli ai processori fisici disponibili. La libreria di runtime si occupa poi di mappare dinamicamente i thread utente sui thread kernel liberi.

Il grande vantaggio: In questo modo, se un thread utente effettua una chiamata di sistema bloccante o subisce un page fault, il sistema operativo blocca solo il thread kernel associato in quel preciso momento. Gli altri thread a livello utente possono continuare la loro esecuzione appoggiandosi ai restanti thread a livello kernel disponibili.

Librerie di Riferimento: pthreads

Quasi tutti i sistemi operativi moderni implementano nativamente i thread Kernel. Per gestire invece i thread a livello utente, lo standard di riferimento è la libreria pthreads. pthreads: Basata sullo standard POSIX, fornisce un’interfaccia univoca e funzioni semplificate per la gestione dei thread. Il suo grande pregio è la portabilità: il codice sorgente è compilabile e funzionante su molteplici OS; pur cambiando ciò che avviene “dietro le quinte” in base al sistema, i risultati rimangono analoghi.

Comunicazione tra processi

Introduzione e complessità dell’IPC

La gestione della comunicazione tra processi (IPC - InterProcess Comunication) è fondamentale per ottenere sistemi reattivi e performanti. La complessità di un sistema aumenta drasticamente quando si passa da un’esecuzione puramente sequenziale (dove un processo $P_{n}$ segue l’altro in modo sincrono) a un sistema di processi concorrenti che comunicano tramite risorse condivise.

I tre problemi principali da affrontare sono:

Passaggio di informazioni: Come trasferire dati tra processi.
Sincronizzazione: Evitare che due o più processi si accavallino su dati comuni.
Sequenzialità: Gestire le dipendenze di ordine tra i processi. Questi problemi valgono anche per i thread, sebbene per essi il passaggio di informazioni sia facilitato dalla condivisione dello spazio di indirizzamento. Esistono diversi approcci per permettere ai processi di scambiare dati, ognuno con criticità specifiche.

Il modello pipe

È il modello più semplice e lineare, basato sull’unidirezionalità.

Funzionamento: Sfrutta i canali di input/output per concatenare i processi (es. cmd1 | cmd2).
Implicazioni: Crea una dipendenza di tempismo, poiché cmd2 deve attendere l’output di cmd1. Tra i processi è presente un buffer per conservare temporaneamente i dati.
Limiti: Non permette la comunicazione bidirezionale e i dati non sono propriamente condivisi, rendendolo un modello limitato.

Segmento di memoria condiviso

Rappresenta l’approccio ideale. Sfrutta uno spazio di memoria comune dove i processi possono leggere e scrivere. Tuttavia, richiede un coordinamento rigoroso per evitare l’accavallamento delle operazioni, senno si ricade nel problema della race condition.

Il Problema delle race condition

La race condition è la situazione in cui il risultato finale dipende dall’ordine di esecuzione dei processi (ovvero da chi viene “scelto” per primo dallo scheduler).

Esempio pratico: Se due processi eseguono simultaneamente un incremento $x = x + 10$ , il valore finale potrebbe essere inconsistente (es. 20 invece di 30) se entrambi leggono lo stesso valore iniziale prima che l’altro possa aggiornarlo. La parte di programma in cui si accede alla memoria condivisa e quindi dove si creano le race condition si chiama sezione critica è importante ricordare che è compito del programmatore individuare e circoscrivere queste sezioni. È buona norma definire sezioni critiche differenti per strutture dati indipendenti, così da non bloccare processi che non competono per la stessa risorsa.

Condizioni per una soluzione efficace

Per risolvere le race condition devono essere soddisfatte quattro condizioni:

Mutua esclusione: Due processi non possono trovarsi contemporaneamente nelle loro sezioni critiche.
Indipendenza Hardware: Nessun presupposto su velocità o numero di CPU.
Assenza di Blocchi Esterni: Un processo fuori dalla sua sezione critica non deve bloccare altri processi.
Attesa Finita: Nessun processo deve attendere all’infinito l’ingresso nella sezione critica; deve essere garantito un tempo massimo finito.

Di seguito le varie soluzioni proposte:

Inibizione degli interrupt

L’approccio più radicale consiste nel permettere a un processo, una volta entrato nella sezione critica, di disabilitare tutti gli interrupt. Poiché lo scheduler del sistema operativo si appoggia sugli interrupt (come il timer del clock) per effettuare il context switch, disabilitarli significa dare al processo il controllo totale della CPU.

Perché non si usa oggi? Sebbene funzioni perfettamente su sistemi mono-processore (garantendo l’atomicità per “forza bruta”), è estremamente pericoloso: un processo utente malizioso o buggato potrebbe bloccare l’intero sistema. Inoltre, nei moderni sistemi multicore, disabilitare gli interrupt su un core non impedisce agli altri core di accedere alla memoria condivisa, rendendo la soluzione del tutto inefficace.

Variabili di lock

Un’idea naturale è l’uso di una variabile di lock (0 se libero, 1 se occupato). Il processo controlla il lock: se è 0, lo imposta a 1 ed entra.

Il paradosso: Il problema è che l’azione di “controllare e poi impostare” non è atomica. Se il Processo A legge il lock e vede 0, ma viene interrotto un istante prima di impostarlo a 1, il Processo B potrebbe essere schedulato, leggere anche lui 0 e impostare il lock. Al ritorno di A, entrambi si ritroveranno nella sezione critica, causando proprio la race condition che volevamo evitare.

TIP

L’azione di testare continuamente una variabile finché non è valorizzata si chiama busy waiting. Andrebbe generalmente evitato, dato che consuma tempo di CPU. Il busy waiting è da utilizzare quando c’è la ragionevole aspettativa che l’attesa sia breve. Un lock che utilizza il busy waiting è chiamato spin lock.

Alternanza Stretta

Questa soluzione software obbliga i processi a passarsi il turno tramite una variabile turn.

Il limite: È una soluzione troppo rigida. Se il turno è del Processo 0, ma il Processo 0 è impegnato in una lunga operazione fuori dalla sezione critica (o termina), il Processo 1 rimarrà bloccato all’infinito anche se la risorsa è libera. Questo viola la regola fondamentale secondo cui un processo fuori dalla sezione critica non deve bloccare altri processi.

int N = 2 // numero di processi
int turn

function enter_region(int process):
    while(turn != process):
        do nothing // attende il proprio turno

function leave_region(int process):
    turn = 1 - process // passa il turno al prossimo

L’Algoritmo di Peterson

Sviluppato nel 1981, l’algoritmo di Peterson è una soluzione puramente software elegante che combina il concetto di “turno” con quello di “interesse”. Un processo dichiara di voler entrare nella sezione critica (interested[i] = true) ma, per cortesia, cede il turno all’altro. Entra solo se l’altro non è interessato o se il turno è tornato a lui.

Problemi moderni: Nonostante la sua correttezza logica, l’algoritmo di Peterson spesso fallisce sulle CPU moderne. I processori attuali eseguono il cosiddetto out-of-order execution (riordino delle istruzioni) per ottimizzare le prestazioni.

int N = 2; // numero di processi
int turn;
bool interested[N]; // tutti a false di default
 
// in entrata alla sezione critica
void enter_region(int process) {
    int other;
    other = 1 - process;
    interested[process] = true; // il processo in questione si dichiara "interessato"
    turn = process;             // si imposta il turno al proprio numero di processo
    
    while (interested[other] == true && turn == process) {
        /* do nothing*/
    }
}
 
// in uscita dalla sezione critica
void leave_region(int process) {
    interested[process] = false;
}

Istruzione TSL e XCHG

Per superare i limiti delle soluzioni software, le architetture moderne offrono istruzioni speciali che eseguono più operazioni come un unico blocco indivisibile (atomico). L’istruzione TSL legge il contenuto di una parola di memoria in un registro e, contemporaneamente, scrive un valore diverso da zero (solitamente 1) in quella stessa locazione. La CPU garantisce che, durante l’esecuzione di TSL, nessun altro processore possa accedere a quella parola di memoria (bloccando il bus di memoria).

enter_region:
    TSL REGISTER, LOCK   // registro = lock, lock = 1
    CMP REGISTER, #0     // se il registro è a 0, entra nella sezione critica
    JNE enter_region     // altrimenti aspetta
    RET
 
leave_region:
    MOVE LOCK, #0        // reimposta lock a 0
    RET

Molte architetture Intel x86 utilizzano l’istruzione XCHG, che scambia atomicamente il contenuto di un registro con quello di una locazione di memoria. La logica è identica a quella della TSL.

Conclusioni su queste soluzioni

Tutte le soluzioni basate su busy waiting sprecano cicli di clock e possono causare il problema dell’inversione della priorità.

Inversione della priorità

Si verifica quando un processo ad alta priorità ( $P_{H}$ ) rimane bloccato in attesa di un lock detenuto da un processo a bassa priorità ( $P_{L}$ ). Se un processo a priorità media ( $P_{M}$ ) viene eseguito, sottrae tempo di CPU a $P_{L}$ , impedendogli di terminare la sezione critica e, di conseguenza, bloccando indirettamente anche $P_{H}$ .

Primitive Sleep e Wakeup

Per evitare questi sprechi, l’OS offre chiamate di sistema che gestiscono lo stato dei processi:

Sleep: Sospende il processo chiamante, portandolo nello stato blocked.
Wakeup: Risveglia un processo specifico, riportandolo nello stato ready. Queste primitive permettono ai processi di non consumare CPU mentre attendono l’accesso a una risorsa condivisa.

Prima soluzione al problema del Produttore-Consumatore

Il problema del produttore-consumatore (noto anche come problema del bounded-buffer) è un classico esempio per illustrare le criticità della sincronizzazione.

Scenario: Due processi condividono un buffer di dimensioni fisse. Il produttore inserisce informazioni nel buffer, mentre il consumatore le preleva.
Criticità: Se il buffer è pieno, il produttore deve entrare in stato di sleep (sospensione) ed essere risvegliato solo quando il consumatore libera spazio. Viceversa, se il buffer è vuoto, il consumatore entra in sleep finché il produttore non inserisce un nuovo elemento.

Per tenere traccia degli elementi, si usa una variabile count. Tuttavia, se l’accesso a questa variabile non è vincolato, si verificano gravi race condition (condizioni di competizione).

function producer():
	while (true):
		item = produce_item
		if (count = N):
			sleep()
		insert_item (item)
		count = count + 1
		if (count = 1):
			wakeup(consumer)

function consumer():
	while (true):
		if (count = 0):
			sleep()
		item = remove_item()
		count = count - 1
		if (count = N - 1):
			wakeup(consumer)
		consume_item(item)

Immaginiamo la seguente sequenza di eventi:

Il buffer è vuoto. Il consumatore legge count = 0, ma prima di entrare in sleep, lo scheduler interrompe la sua esecuzione e passa al produttore.
Il produttore inserisce un elemento, porta count a 1 e, sapendo che prima era a 0, invia un segnale di wakeup al consumatore.
Il consumatore, non essendo ancora logicamente in sleep, perde il segnale. Quando riprenderà l’esecuzione, andrà in sleep e ci rimarrà per sempre.

Soluzione temporanea (inefficace): Aggiungere un bit di attesa wakeup (un “salvadanaio” per salvare i segnali). Funziona per due processi, ma fallisce non appena il sistema scala a tre o più processi, rendendo il problema persistente.

Semafori

Per risolvere definitivamente la perdita dei wakeup, Dijkstra introdusse una nuova primitiva di sincronizzazione, chiamata Semaforo ovvero una variabile intera utilizzata per contare il numero di wakeup salvati per uso futuro. Può valere:

0 (nessun wakeup salvato)
un numero positivo (uno o più wakeup in attesa).

I semafori operano tramite due azioni atomiche (garantisce il sistema operativo che lo siano):

Down: Generalizzazione dell’operazione di sleep. Verifica se il semaforo è $> 0$ . Se sì, lo decrementa (consuma un wakeup) e prosegue. Se è 0, il processo viene messo in sleep senza completare il down.
Up: Generalizzazione dell’operazione di wakeup. Incrementa il semaforo. Se ci sono processi in sleep su quel semaforo, il sistema ne sceglie uno (es. casualmente) e gli permette di completare il suo down.

I semafori inizializzati a 1 e usati da due o più processi, per assicurare che uno solo di loro possa entrare nella propria regione critica allo stesso tempo, sono chiamati semafori binari.

Soluzione al Produttore-Consumatore con i semafori

La soluzione richiede tre semafori implementati in maniera indivisibile (tramite chiamate di sistema che disabilitano brevemente gli interrupt):

Full: Conta i posti pieni (inizializzato a 0).
Empty: Conta i posti vuoti (inizializzato a N).
Mutex: Semaforo binario per la mutua esclusione (inizializzato a 1).

#define N 100                           /* numero di posti nel buffer */
typedef int semaphore;                  /* i semafori sono un tipo speciale di int */

semaphore mutex = 1;                    /* controlla l'accesso alla regione critica */
semaphore empty = N;                    /* conta i posti vuoti del buffer */
semaphore full = 0;                     /* conta i posti pieni del buffer */

void producer(void){
    int item;
    while (TRUE) {                      /* TRUE è la costante 1 */
        item = produce_item();          /* genera qualcosa da mettere nel buffer */
        down(&empty);                   /* decrementa il contatore empty */
        down(&mutex);                   /* entra nella regione critica */
        insert_item(item);              /* mette un nuovo elemento nel buffer */
        up(&mutex);                     /* lascia la regione critica */
        up(&full);                      /* incrementa il contatore dei posti pieni */
    }
}

void consumer(void){
    int item;
    while (TRUE) {                      /* ciclo infinito */
        down(&full);                    /* decrementa il contatore full */
        down(&mutex);                   /* entra nella regione critica */
        item = remove_item();           /* prende l'elemento dal buffer */
        up(&mutex);                     /* lascia la regione critica */
        up(&empty);                     /* incrementa il contatore dei posti vuoti */
        consume_item(item);             /* fa qualcosa con l'elemento */
    }
}

Mutex

I Mutex sono una versione semplificata dei semafori, utili unicamente per gestire la mutua esclusione di risorse o pezzi di codice.

Stati: Possono essere solo locked (bloccato, solitamente > 0) o unlocked (sbloccato, 0).
Operazioni:
- mutex_lock: Se unlocked, il thread entra nella regione critica. Se locked, il thread si blocca.
- mutex_unlock: Sblocca il mutex; se ci sono thread in attesa, ne viene scelto uno a caso per acquisire il lock.

Essendo semplici, i mutex possono essere realizzati nello spazio utente usando istruzioni hardware come TSL o XCHG. La differenza cruciale tra enter_regione e mutex_lock è l’uso di thread_yield: se il lock fallisce, il thread cede immediatamente la CPU allo scheduler, evitando sprechi di risorse dovuti al busy waiting.

Futex (Fast User Space Mutex)

I classici spin lock (attesa attiva) sono veloci ma sprecano CPU se l’attesa è lunga. Il blocco tramite kernel, d’altra parte, è oneroso se ci sono poche contese. La soluzione di Linux è il Futex.

Funzionamento: Opera interamente in spazio utente finché non ci sono contese. Condivide un intero a 32 bit come lock. Il thread tenta di prenderlo con un’istruzione atomica “decrement and test”.
In caso di contesa: Se il lock è già detenuto, il futex effettua una chiamata di sistema per mettere il thread in una coda d’attesa nel kernel (giustificando l’overhead del kernel system call solo quando strettamente necessario).
Rilascio: Avviene con un’istruzione “increment and test”. Se ci sono processi bloccati in coda, avvisa il kernel di sbloccarli.

Monitor

Poiché i mutex e i semafori sono difficili da usare correttamente, Brinch Hansen (1973) e Hoare (1974) hanno introdotto una primitiva di più alto livello ovvero i Monitor: una raccolta di procedure, variabili e strutture dati raggruppate in un modulo. I processi esterni possono chiamare le procedure, ma non possono accedere direttamente alle strutture dati interne. In un dato istante, solo un processo può essere attivo all’interno di un monitor, ed è il compilatore a gestire la mutua esclusione (di solito usando mutex o semafori binari dietro le quinte).

Variabili condizione: Per permettere ai processi di bloccarsi quando non possono procedere, si usano due operazioni:

wait: Blocca il processo chiamante e consente l’ingresso nel monitor a un altro processo.
signal: Risveglia un processo in attesa su quella condizione.

Per evitare di avere due processi attivi nel monitor contemporaneamente, abbiamo bisogno di una regola che indichi che cosa accade dopo una signal. Il libro propone di far sì che venga eseguito il processo appena svegliato, sospendendo l’altro.

Ad una prima occhiata si può pensare che le operazioni wait e signal siano simili a sleep e wakeup. Sono in effetti molto simili, ma con una differenza cruciale: sleep e wakeup fallivano perché mentre un processo stava tentando di entrare in sleep, l’altro stava provando a svegliarlo. Con i monitor questo non può accadere, grazie alla gestione automatica della mutua esclusione. In questo modo la programmazione parallela diventa molto meno incline agli errori rispetto all’uso manuale dei semafori.

Svantaggio: problema principale di questa soluzione è che i monitor sono costrutti del linguaggio di programmazione, ma non tutti i compilatori li supportano (es. C e Pascal ne sono sprovvisti).

Soluzione Produttore-Consumatore con i monitor

monitor pc_monitor
  condition full, empty;
  integer count = 0;

  function insert(item)
    if count = N then wait(full);
    insert_item(item);
    count = count + 1;
    if count = 1 then signal(empty)

  function remove()
    if count = 0 then
      wait(empty);
    remove = remove_item()
    count = count - 1;
    if count = N-1 then signal(full)

function producer()
  while (true) do
    item = produce_item()
    pc_monitor.insert(item)

function consumer()
  while (true) do
    item = pc_monitor.remove()
    consume_item(item)

Scambio di messaggi

Sia mutex che semafori sono stati pensati per essere utilizzati in sistemi che hanno una singola memoria pubblica collegata alle CPU, ma quando ci troviamo in sistemi distribuiti con memoria privata per ogni CPU, queste primitive diventano inutili, quindi si utilizza lo scambio di messaggi. Questo metodo si basa su due chiamate di sistema principali:

send: Invia un messaggio a una destinazione.
receive: Riceve un messaggio da una fonte. Questa soluzione ha delle criticità:

Messaggi persi: Si risolve costringendo il destinatario a inviare un messaggio di acknowledgment (conferma di ricezione). Se l’ack viene perso, si crea un nuovo problema di gestione delle ritrasmissioni.
Identificazione: Come identificare il destinatario in modo non ambiguo.
Autenticazione: Garantire che il client stia comunicando con il vero server e non con un impostore. Per indirizzare i messaggi si usano diverse tecniche:

Indirizzamento Diretto: Assegnazione di un indirizzo univoco a ciascun processo, alla quale la send invierà un messaggio
Mailbox: Una struttura dati usata come buffer che contiene un certo numero predefinito di messaggi. Se un processo tenta di inviare a una mailbox piena, viene sospeso finché non si libera spazio.
Rendezvous (Zero Buffer): La comunicazione avviene senza buffer intermedi. Se la send viene eseguita prima della receive, il mittente si blocca finché il destinatario non è pronto (e viceversa). È una strategia più rigida ma di semplice implementazione.

Soluzione Produttore-Consumatore con i messaggi

Il consumatore invia N messaggi vuoti al produttore. Il produttore li preleva, li riempie e li rimanda al consumatore.

#define N 100               /* numero di posti nel buffer */

void producer(void)
{
    int item;
    message m;              /* buffer del messaggio */

    while (TRUE) {
        item = produce_item();          /* genera qualcosa da mettere nel buffer */
        receive(consumer, &m);          /* aspetta che ne arrivi uno vuoto */
        build_message(&m, item);        /* costruisci un messaggio da spedire */
        send(consumer, &m);             /* manda l'elemento al consumatore */
    }
}

void consumer(void)
{
    int item, i;
    message m;

    for (i = 0; i < N; i++) send(producer, &m); /* manda N vuoti */
    while (TRUE) {
        receive(producer, &m);          /* prende un messaggio che contiene un elemento */
        item = extract_item(&m);        /* estrae l'elemento dal messaggio */
        send(producer, &m);             /* ne manda indietro uno vuoto */
        consume_item(item);             /* fa qualcosa con l'elemento */
    }
}

Problema dei filosofi a cena

Il problema modella le sfide della concorrenza nell’accesso a risorse limitate.

Lo Scenario: Cinque filosofi sono seduti attorno a un tavolo circolare. Davanti a ciascuno c’è un piatto di spaghetti.
Le Risorse (Forchette): Tra un piatto e l’altro c’è una singola forchetta (5 forchette in totale). Gli spaghetti sono così scivolosi che per mangiare servono due forchette.
L’Obiettivo: Quando un filosofo ha fame, tenta di prendere la forchetta alla sua sinistra e quella alla sua destra (in qualsiasi ordine). Se ci riesce, mangia per un po’, posa le forchette e torna a pensare. Dobbiamo scrivere un programma che assicuri che ogni filosofo riesca a mangiare senza che il sistema si blocchi mai.

Tentativi di soluzione al problema dei filosofi a cena

Nel cercare di risolvere il problema, si va incontro a diverse problematiche tipiche della programmazione concorrente.

Tentativo 1: La Soluzione “Ovvia” (Errata) L’approccio più istintivo è far sì che ogni filosofo aspetti e prenda la forchetta sinistra, poi faccia lo stesso con la destra.

#define N 5

void philosopher(int i){
    while (TRUE) {
        think();
        take_fork(i);               /* Prende la sinistra */
        take_fork((i+1) % N);       /* Prende la destra */
        eat();
        put_fork(i);                /* Posa la sinistra */
        put_fork((i+1) % N);        /* Posa la destra */
    }
}

Questa soluzione è letale a causa del rischio di blocco totale. Supponiamo che tutti e cinque i filosofi prendano la loro forchetta sinistra contemporaneamente. Nessuno sarebbe in grado di prendere la sua forchetta destra e ci sarebbe un deadlock.

Tentativo 2: Rilascio e Attesa (Tempo Fisso)

Per evitare il deadlock, il filosofo prende la sinistra, controlla la destra: se è occupata, posa la sinistra, aspetta un tempo predefinito e riprova. Anche questa proposta fallisce, sebbene per una diversa ragione. Con un poco di sfortuna, tutti i filosofi potrebbero iniziare il loro algoritmo contemporaneamente, prendendo la loro forchetta sinistra, verificando che la destra non è disponibile, riponendo la forchetta sinistra, aspettando, riprendendo di nuovo la sinistra e così via, per sempre. Una situazione di questo genere, in cui tutti i programmi continuano a essere eseguiti indefinitamente, ma senza alcun avanzamento, è detta starvation.

Tentativo 3: Attesa Casuale Si potrebbe introdurre un tempo di attesa randomico anziché fisso. Sebbene riduca statisticamente il rischio di un blocco lungo, non offre una garanzia matematica. Nei sistemi critici, una soluzione deve funzionare sempre, non basarsi sulla fortuna.

Tentativo 4: Mutex globale Un miglioramento alla Figura 2.46 che non ha deadlock e non ha starvation è quello di proteggere le cinque dichiarazioni che seguono la chiamata a think da un semaforo binario. Prima di iniziare ad acquisire forchette un filosofo farebbe un down su mutex. Dopo aver riposto la forchetta, farebbe un up su mutex. Dal punto di vista teorico è ideone. Dal punto di vista pratico ha un difetto di prestazione; ci sarebbe un solo filosofo per volta che potrebbe mangiare, ma con la disponibilità di 5 forchette dovrebberò essere in 2.

Tentativo 5: macro LEFT e RIGHT Per evitare deadlock, eliminare la starvation e al contempo massimizzare il parallelismo (permettendo a due filosofi di mangiare assieme), si utilizza una logica basata sul tracciamento degli stati. Si introduce un array state che tiene traccia della condizione di ogni filosofo (THINKING, HUNGRY, EATING).

Quindi si definisce una regola d’oro: Un filosofo può passare allo stato EATING solo ed esclusivamente se nessuno dei suoi due vicini lo sta facendo in quel momento.

#define N           5           /* numero di filosofi */
#define LEFT        (i+N-1)%N   /* numero del vicino alla sinistra di i */
#define RIGHT       (i+1)%N     /* numero del vicino alla destra di i */
#define THINKING    0           /* il filosofo sta pensando */
#define HUNGRY      1           /* il filosofo tenta di prendere le forchette */
#define EATING      2           /* il filosofo mangia */

typedef int semaphore;          /* i semafori sono uno speciale tipo di int */
int state[N];                   /* array per tener traccia dello stato di ciascuno */
semaphore mutex = 1;            /* mutua esclusione per le regioni critiche */
semaphore s[N];                 /* un semaforo per filosofo */

void philosopher(int i)         /* i: numero del filosofo, da 0 a N-1 */
{
    while (TRUE) {              /* ripeti sempre */
        think();                /* il filosofo sta pensando */
        take_forks(i);          /* prende due forchette o si blocca */
        eat();                  /* yum-yum, spaghetti */
        put_forks(i);           /* ripone entrambe le forchette sul tavolo */
    }
}

void take_forks(int i)          /* i: numero del filosofo da 0 a N-1 */
{
    down(&mutex);               /* entra nella regione critica */
    state[i] = HUNGRY;          /* registra il fatto che il filosofo i ha fame */
    test(i);                    /* prova a prendere due forchette */
    up(&mutex);                 /* esce dalla regione critica */
    down(&s[i]);                /* si blocca se non sono state prese le forchette */
}

void put_forks(int i)           /* i: numero del filosofo da 0 a N-1 */
{
    down(&mutex);               /* entra nella regione critica */
    state[i] = THINKING;        /* il filosofo ha finito di mangiare */
    test(LEFT);                 /* guarda se il vicino a sinistra adesso può mangiare */
    test(RIGHT);                /* guarda se il vicino a destra adesso può mangiare */
    up(&mutex);                 /* esce dalla regione critica */
}

void test(int i)                /* i: numero del filosofo da 0 a N-1 */
{
    /* Se ho fame e i miei vicini non stanno mangiando, inizio a mangiare */
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING;
        up(&s[i]);              /* Sblocca il semaforo personale del filosofo */
    }
}

Problema dei lettori-scrittori

Un altro famoso problema è quello dei lettori e degli scrittori, che modella l’accesso a una base di dati. È accettabile avere molteplici processi che leggono il database contemporaneamente, ma se un processo sta aggiornando (scrivendo) il database, nessun altro processo può avere accesso al database, nemmeno i lettori. Come programmiamo i lettori e gli scrittori per seguire queste regole?

Tentativi di soluzione al problema dei lettori-scrittori

Tentativo 1: Soluzione basata sui semafori (Priorità ai lettori) L’approccio iniziale utilizza i semafori per gestire l’accesso. Si usa un semaforo mutex per proteggere la variabile contatore dei lettori (rc) e un semaforo db per garantire l’accesso esclusivo al database da parte degli scrittori. Il primo lettore che arriva blocca il database agli scrittori, e l’ultimo lettore che esce lo sblocca.

semaphore mutex = 1
semaphore db = 1
int rc = 0

function reader()
    while true do
        down(mutex)
        rc = rc + 1
        if (rc == 1) down(db)   /* Il primo lettore blocca gli scrittori */
        up(mutex)
        
        read_database()
        
        down(mutex)
        rc = rc - 1
        if (rc == 0) up(db)     /* L'ultimo lettore sblocca gli scrittori */
        up(mutex)
        use_data_read()

function writer()
    while true do
        think_up_data()
        down(db)                /* Richiede l'accesso esclusivo */
        write_database()
        up(db)

Problema: Questa soluzione è fortemente sbilanciata a favore dei lettori. Come evidenziato nella slide, lo scrittore potrebbe attendere per un tempo indefinito (starvation). Finché continua ad arrivare almeno un nuovo lettore prima che l’ultimo se ne sia andato, rc non scenderà mai a 0, il semaforo db non verrà rilasciato, e lo scrittore rimarrà bloccato per sempre.

Tentativo 2: Soluzione n.1 basata sui monitor (Incapsulamento senza risolvere la starvation) Per strutturare meglio il codice, si passa all’uso di un monitor. Si introducono le variabili di condizione (read, write), un contatore di lettori (rc) e un flag booleano (busy_on_write). In questa versione, un lettore aspetta solo se uno scrittore è attualmente in fase di scrittura (busy_on_write == true).

monitor rw_monitor
    int rc = 0; boolean busy_on_write = false
    condition read, write

    function start_read()
        if (busy_on_write) wait(read)
        rc = rc + 1
        signal(read)

    function end_read()
        rc = rc - 1
        if (rc == 0) signal(write)

    function start_write()
        if (rc > 0 OR busy_on_write) wait(write)
        busy_on_write = true

    function end_write()
        busy_on_write = false
        if (in_queue(read))
            signal(read)
        else
            signal(write)

Problema: Nonostante l’eleganza del monitor, la logica di base non cambia. I nuovi lettori continuano a entrare liberamente se non c’è uno scrittore attivo (anche se c’è uno scrittore in attesa). Inoltre, quando uno scrittore finisce (end_write), controlla prima se ci sono lettori in coda e li risveglia, dando loro di nuovo la precedenza. La starvation per gli scrittori è ancora possibile.

Tentativo 3: Soluzione n.2 basata sui monitor (Frenare i nuovi lettori) Per mitigare la starvation degli scrittori, si introduce una piccola ma cruciale modifica nella funzione start_read()

function start_read()
	/* Modifica: aspetta anche se c'è uno scrittore in coda */
	if (busy_on_write OR in_queue(write)) wait(read)
	rc = rc + 1
	signal(read)

Miglioramento e limite: Adesso, se uno scrittore si mette in attesa, i nuovi lettori che arrivano vengono bloccati. Questo evita che un flusso continuo di lettori tenga in ostaggio il database. Tuttavia, c’è un’incoerenza: quando lo scrittore finisce di scrivere (end_write), la logica precedente risveglia ancora prima i lettori in coda rispetto ad altri scrittori in coda. Questo porta a un’alternanza poco efficiente se ci sono molte scritture pendenti.

Tentativo 4: Soluzione n.3 basata sui monitor (Priorità agli scrittori) Per risolvere definitivamente la latenza per gli scrittori, si inverte la logica di risveglio al termine di una scrittura.

monitor rw_monitor
    int rc = 0; boolean busy_on_write = false
    condition read, write

    function start_read()
        if (busy_on_write OR in_queue(write)) wait(read)
        rc = rc + 1
        signal(read)

    function end_read()
        rc = rc - 1
        if (rc == 0) signal(write)

    function start_write()
        if (rc > 0 OR busy_on_write) wait(write)
        busy_on_write = true

    function end_write()
        busy_on_write = false
        /* Logica invertita: precedenza agli scrittori */
        if (in_queue(write))
            signal(write)
        else
            signal(read)

In questa soluzione definitiva, si garantisce che:

I nuovi lettori si fermano se c’è uno scrittore in attesa.
Quando uno scrittore termina, cede il passo immediatamente al prossimo scrittore in coda.

Scheduling

Introduzione allo scheduling

Quando un computer lavora in multiprogrammazione, si verifica spesso una competizione per l’utilizzo della CPU tra processi o thread che si trovano contemporaneamente nello stato “pronto”. Se il sistema dispone di una singola CPU, è necessario decidere a chi assegnarla.

Scheduler: La componente del sistema operativo incaricata di decidere quale processo eseguire.
Algoritmo di scheduling: La logica e le regole utilizzate dallo scheduler per operare questa scelta.

Effettuare il cambio di processo (o context switch) è un’attività estremamente onerosa in termini di prestazioni. Richiede il passaggio in modalità kernel, il salvataggio dei registri e della mappa di memoria, l’aggiornamento della Memory Management Unit (MMU) e l’invalidazione della memoria cache, che dovrà poi essere ricaricata. Un numero eccessivo di scambi penalizza l’efficienza globale.

Comprendere il comportamento dei processi è fondamentale per il design di un buon algoritmo:

Processi CPU-bound: Spendono la maggior parte del loro tempo eseguendo calcoli complessi (lunghi burst di CPU) con rare attese di I/O.
Processi I/O-bound: Spendono gran parte del loro tempo in attesa di terminare operazioni I/O (brevi burst di CPU). Si noti che la durata dell’I/O non c’entra: il punto è che non effettuano elaborazioni consistenti tra una richiesta e l’altra. Poiché le CPU evolvono più rapidamente dei dischi, la tendenza è che i processi diventino progressivamente sempre più I/O-bound.

Quando effettuare lo scheduling

Le decisioni di scheduling si rendono necessarie in quattro momenti chiave:

Alla creazione di un processo, lo scheduler sceglie se eseguire prima il genitore o il figlio.
Alla terminazione di un processo, per pescarne uno nuovo dalla coda dei pronti.
Al blocco di un processo (es. attesa I/O, attesa su un semaforo), per non lasciare la CPU inattiva.
Al verificarsi di un interrupt di I/O (un dispositivo ha terminato un’operazione, sbloccando potenzialmente un processo in attesa).

Categorie di Algoritmi e ambienti

Il modo in cui gli algoritmi reagiscono agli interrupt del clock definisce la loro natura:

Algoritmo non preemptive: Un processo selezionato mantiene il possesso della CPU ininterrottamente finché non si blocca volontariamente o termina. Non viene mai interrotto forzatamente per limiti di tempo.
Algoritmo preemptive: Al processo è assegnato un tempo massimo di esecuzione. Scaduto tale intervallo, un interrupt del clock permette allo scheduler di riprendere forzatamente il controllo della CPU e assegnarla a un altro processo.

Gli obiettivi di uno scheduler variano a seconda dell’ambiente operativo:

Obiettivi universali: Equità (giusta condivisione delle risorse), corretta applicazione delle policy stabilite e bilanciamento del sistema.
Sistemi batch: Massimizzare il throughput (lavori/ora), ridurre il tempo di turnaround (attesa dalla sottomissione al completamento) e mantenere la CPU sempre attiva.
Sistemi interattivi: Offrire tempi di risposta immediati per soddisfare le aspettative umane.
Sistemi Real-Time: Garantire il rispetto delle scadenze (deadline) ed evitare il degrado della qualità.

Algoritmi per sistemi batch

First-come first-served (FCFS): Algoritmo non preemptive basato su una singola coda. Assegna la CPU nell’ordine di arrivo delle richieste.
- Pro: Facilissimo da implementare e comprendere.
- Contro: Fortemente svantaggioso in ambienti misti. Un singolo processo compute-bound può monopolizzare la CPU per un secondo intero, ritardando inutilmente centinaia di processi I/O-bound che avrebbero impiegato pochi millisecondi.
Shortest job first (SJF): Algoritmo non preemptive che preleva sempre il processo con il tempo stimato di esecuzione più breve. È matematicamente ottimale per ridurre il tempo medio di turnaround, ma solo se tutti i processi sono disponibili simultaneamente.
Shortest remaining time next: La variante preemptive dell’SJF. Lo scheduler subentra e cambia processo se ne arriva uno il cui tempo necessario alla conclusione è inferiore al tempo rimanente del processo attualmente in esecuzione.

Algoritmi per sistemi interattivi

Round-robin: A ogni processo è assegnato un intervallo di tempo, chiamato quanto, durante il quale gli è consentito di essere eseguito. Se alla fine del quanto il processo è ancora in esecuzione, la CPU viene prelazionata e assegnata a un altro processo. Se il processo si blocca o termina prima che sia trascorso il quanto, viene fatto uno scambio di CPU, naturalmente, quando il processo si blocca. Il round-robin è facile da realizzare. Tutto quello che lo scheduler deve fare è mantenere una lista dei processi eseguibili

Come viene gestita la lunghezza di un quanto di tempo L’unica questione interessante che riguarda il round-robin è la durata del quanto. La gestione del passaggio da un processo a un altro richiede una certa quantità di tempo.

Supponete che questo scambio di contesto richieda $1 m s$ , supponete anche che il quanto sia impostato a $4 m s$ . Con questi parametri, dopo $4 m s$ di lavoro utile, la CPU deve spendere (cioè sprecare) $1 m s$ per lo scambio di processo. È evidente che è troppo.

Per migliorare l’efficienza della CPU, potremmo, diciamo, impostare il quanto a $100 m s$ . Il tempo sprecato è ora solo l’1%. Ma si consideri che cosa accade su un sistema server se arrivano $50$ richieste in un intervallo di tempo molto breve e con richieste di CPU molto diverse. Cinquanta processi saranno messi nell’elenco dei processi eseguibili. Se la CPU è inattiva, il primo partirà immediatamente, il secondo non potrà partire prima di $100 m s$ e così via.

La conclusione può essere formulata come segue: impostare un quanto come troppo breve causa troppi scambi di processo e riduce l’efficienza della CPU, ma impostarlo come troppo alto può causare una risposta scadente alle richieste rapide interattive. Un quanto di circa 20-50 ms è spesso un compromesso ragionevole.
Scheduling a priorità: A ciascun processo viene assegnato un valore di priorità statico (es. ruoli aziendali) o dinamico. La CPU va al processo eseguibile con priorità massima.

Per impedire che i processi ad alta priorità siano eseguiti indefinitamente, lo scheduler può abbassare la priorità del processo attualmente in esecuzione a ogni scatto del clock (cioè a ogni interrupt). Se questa azione fa sì che la sua priorità vada al di sotto di quella del processo successivo, avviene uno scambio di processo. In alternativa a ciascun processo può essere assegnato un quanto di tempo massimo in cui può essere eseguito.

Al fine di ottenere determinati obiettivi le priorità possono essere anche assegnate dinamicamente dal sistema. Per esempio, alcuni processi sono molto I/O bound e spendono gran parte del loro tempo aspettando che l’I/O termini. In qualunque momento un processo di questo tipo richieda la CPU, dovrebbe essergli data immediatamente, per consentirgli di far avviare la sua richiesta successiva di I/O, che può poi procedere in parallelo con un altro processo effettivamente in elaborazione.

È spesso conveniente raggruppare i processi in classi di priorità e usare lo scheduling a priorità fra le classi, ma all’interno di ciascuna classe usare lo scheduling round-robin. L’algoritmo di scheduling è il seguente: finché vi sono processi eseguibili a priorità 4, eseguire ciascuno per un quanto, in stile round-robin, senza perder tempo con le classi di priorità basse. Se la priorità 4 è vuota, allora eseguire i processi a priorità 3 in round-robin e così via.
Code multiple: astrazione dello scheduling con priorità provvisto di divisione in classi, in pratica qui scegliamo un algoritmo di scheduling verticale (che decide quale classe avviare prima) e uno di scheduling orizzontale (che decide quale processo mettere in esecuzione in una specifica classe), si può avere un algoritmo di scheduling orizzontale diverso per ogni classe.

Il problema di questo modello puro a Code Multiple è il rischio di Starvation se le code “alte” si riempiono continuamente, le code più basse non otterranno mai la CPU. Per prevenire questo problema i Sistemi Operativi reali implementano una logica chiamata code multiple con Retroazione. In pratica, anziché ancorare un processo alla sua coda orizzontale in modo perpetuo, il sistema valuta il suo comportamento dinamico facendolo scivolare nelle code a priorità inferiore se questo consuma interamente il suo quanto di tempo senza mai bloccarsi per compiere operazioni di I/O. Questa discesa verso il basso isola i processi pesanti e puramente computazionali per favorire quelli interattivi. Di conseguenza, avremo le code a priorità alta popolate da processi I/O bound, quelle a priorità bassa da processi CPU bound e quelle a priorità intermedia da processi misti. Per assecondare questa struttura, si assegnano quanti di tempo più piccoli nelle priorità alte, che vengono utilizzati per i processi I/O bound che rendono il sistema molto più reattivo, mentre nelle code a priorità bassa si usano quanti di tempo progressivamente più grandi.

A tal proposito, la classe con la priorità più bassa in assoluto può avere un quanto di tempo pari a più infinito, il che significa adottare un algoritmo orizzontale First-Come, First-Served: essendo l’ultima ruota del carro, eseguita solo quando il resto del sistema è inattivo, conviene far girare i processi pesanti in modo ininterrotto per evitare gli sprechi di prestazioni causati dai continui cambi di contesto.

Un altro modo per gestire l’equità è cambiare lo scheduling verticale assegnando un tempo T a un ciclo. Per ogni livello verrà assegnata una percentuale di T a ogni coda di priorità. Se una coda è vuota la percentuale di T sarà minore (es. 50%, 25%, 15%, 10%).
Shortest process next (Sui sistemi interattivi): Tenta di applicare la logica SJF stimando la durata del prossimo comando tramite l’esperienza passata, con una tecnica chiamata aging. Un approccio è quello di fare delle stime basate sull’esperienza maturata ed eseguire il processo con il tempo di esecuzione stimato più breve. Supponiamo che il tempo stimato per un comando per un certo terminale sia $T_{0} $ . Supponiamo che la sua esecuzione successiva sia misurata come $T_{1}$ . Potremmo aggiornare la nostra stima facendo una somma pesata dei numeri, ossia: $a T_{0} + (1 - a) T_{1}$ Tramite la scelta di a possiamo decidere se avere il processo di stima che dimentica in breve tempo le ultime esecuzioni o le ricorda a lungo. La tecnica di stimare il valore successivo di una serie prendendo la media pesata del valore attuale misurato e la stima precedente è talvolta detta aging.
Scheduling garantito: Il sistema fa una promessa all’utente (es. con $n$ processi, otterrai $1/ n$ della potenza CPU). Per riuscire a mantenere questa promessa, il sistema deve tener traccia di quanta CPU ha ricevuto ogni processo dal momento della sua creazione. Poi calcola la quantità di CPU che ognuno ha diritto ad avere, cioè il tempo dalla creazione diviso n. Poiché è conosciuta la quantità di tempo di CPU ricevuto da ogni processo, è semplice calcolare il rapporto fra effettivo tempo di CPU consumato e tempo di CPU cui si ha diritto. Un rapporto di 0,5 significa che un processo ha avuto la metà di quanto avrebbe dovuto, un rapporto di 2,0 significa che il processo ha avuto il doppio di quanto aveva diritto. L’algoritmo esegue poi il processo con il rapporto minore finché il suo rapporto non supera quello del suo più vicino concorrente.
Scheduling a lotteria: L’idea base è quella di dare ai processi un biglietto della lotteria per le diverse risorse del sistema, come il tempo di CPU. Ogni volta che deve essere presa una decisione di scheduling si pesca un biglietto della lotteria e il processo che ha quel biglietto si aggiudica la risorsa.

Ai processi più importanti possono essere assegnati dei biglietti extra, per aumentare le loro possibilità di vincere. Se ci sono 100 biglietti non estratti e un processo ne possiede 20, ha il 20% di possibilità di vincere ogni estrazione. A lungo termine si prenderà il 20% della CPU.

Processi cooperanti possono, se lo desiderano, scambiarsi i biglietti. Per esempio, quando un processo client manda un messaggio a un processo server e poi si blocca, può elargire tutti i propri biglietti al server, per aumentare la possibilità che il server sia il prossimo a essere eseguito. Quando il server ha terminato, restituisce i biglietti al client, in modo che possa nuovamente essere eseguito. Di fatto, in assenza di client, ai server non serve alcun biglietto.
Scheduling fair-share: Finora abbiamo ipotizzato che ogni processo fosse schedulato per proprio conto, senza considerare a chi appartenesse. Di conseguenza, se l’utente $1$ avvia $9$ processi e l’utente $2$ ne avvia $1$ , con il round-robin o le priorità uguali, l’utente $1$ si prenderà il $90%$ della CPU e l’utente $2$ ne prenderà solo il $10%$ . Per evitare questa situazione, prima di schedularlo, alcuni sistemi prendono in considerazione chi possiede un processo. In questo modello, a ogni utente viene assegnata una frazione di CPU e lo scheduler raccoglie i processi in modo tale da farla rispettare. Così se a due utenti è stato assegnato il $50%$ della CPU, l’avranno, indipendentemente da quanti processi abbiano attivi.

Scheduling nei sistemi Real-Time

I sistemi real-time sono generalmente divisi in categorie come hard real-time, nel caso di scadenze assolute da assolvere, o soft real-time che implica un certo grado di tollerabilità.

Gli eventi cui un sistema real-time può dover rispondere possono ulteriormente essere categorizzati come periodici (che avvengono a intervalli regolari) o non periodici (che avvengono imprevedibilmente).

Gli algoritmi di scheduling real-time possono essere statici e dinamici. I primi intraprendono le loro decisioni di scheduling prima che il sistema inizi l’esecuzione, i secondi durante l’esecuzione. Lo scheduling statico funziona solo dove esiste in anticipo la disponibilità di un’informazione perfetta riguardo al lavoro da svolgere e le scadenze da raggiungere.

Scheduling a Thread

Quando molti processi hanno ognuno molteplici thread, abbiamo due livelli di parallelismo presenti: processi e thread.

Lo scheduling in questi sistemi si differenzia sostanzialmente a seconda che siano supportati thread utente o a livello kernel (o entrambi).

Consideriamo per primi i thread utente. Dato che il kernel non è a conoscenza dell’esistenza dei thread, opera come fa sempre, prendendo un processo, diciamo A, e assegnando ad A il controllo per il suo quanto. Lo scheduler di thread interno ad A decide quale thread eseguire, diciamo A1. Poiché per questi thread non vi sono interrupt del clock, questo può continuare l’esecuzione quanto vuole. Se utilizza l’intero quanto del processo, il kernel selezionerà un altro processo da eseguire. La sola restrizione è l’assenza di interrupt del clock che interrompano un thread eseguito troppo a lungo.

Consideriamo adesso la situazione con i thread del kernel. In questo caso il kernel preleva un particolare thread da eseguire. Non deve tener conto del processo cui appartiene il thread, ma può farlo, se vuole. Al thread è dato un quanto e se eccede quel quanto è sospeso forzatamente. Poiché il kernel sa che il passaggio da un thread nel processo A a un thread nel processo B è più costoso che eseguire un secondo thread nel processo A (dovuto al fatto di dover cambiare la mappa di memoria e dover svuotare la memoria cache), può tener conto di questa informazione quando deve prendere una decisione. Per esempio, dati due thread che sono ugualmente importanti, con uno di loro appartenente allo stesso processo del thread che si è bloccato, la preferenza potrebbe essere assegnata a questo.

Una differenza rilevante fra i thread utente e i thread del kernel sta nelle prestazioni. Fare uno scambio di thread utente richiede una manciata di istruzioni macchina. Con i thread del kernel richiede di fare uno scambio completo di contesto, il che è più lento di parecchi ordini di grandezza. D’altra parte, con i thread del kernel, un thread bloccato in attesa di I/O non sospende l’intero processo, come avviene con i thread utente.

Lo Scheduling su Sistemi Multiprocessore

Multielaborazione asimmetrica: Un processore assume il ruolo di master e concentra su di sé tutta la logica di scheduling, mentre gli altri fungono da slave.
- Pro: Nessun problema di accesso concorrente alle code dei processi.
- Contro: Scarsissima scalabilità. Il master diventa presto un collo di bottiglia (bottleneck).
Multielaborazione simmetrica (SMP): Architettura standard attuale. Tutti i processori hanno lo stesso ruolo e i medesimi diritti. La gestione concorrente delle code può avvenire in due modi:
- Coda unificata: Richiede meccanismi di sincronizzazione stretta (es. un lock). Quando uno scheduler di un core interroga la struttura dati, la blocca per tutti gli altri, che si metteranno in fila. Non c’è necessità di bilanciamento del carico.
- Code separate: Ciascun core dispone di un proprio scheduler e di una coda personale. È la via più utilizzata. Sviluppa enormemente la prelidezione, ovvero l’alta probabilità che un core riprenda a elaborare un processo di cui si era già occupato, massimizzando il numero di cache hit.

L’approccio a code separate necessita di gestire le discrepanze, affinché non ci sia un core sovraccarico e uno inattivo. Esistono due metodologie:

Migrazione guidata: Un core supervisiona periodicamente il sistema. Se rileva uno sbilanciamento, interviene spalmandone il carico in eccesso sulle code vuote. (Ecco perché, anche con code separate, serve implementare un sistema di lock).
Migrazione spontanea: È il core inattivo a prendere l’iniziativa. Esplora le code dei core intasati e “ruba” loro alcuni processi. Questo meccanismo abbatte il principio della prelidezione, ma è spesso affiancato da regole di prelidezione forte, che forzano certi core a gestire specifici processi proprio per preservare e favorire i vantaggiosi cache hit.

Lo Scheduling nei principali sistemi operativi

Windows: Utilizza uno scheduler basato su code di priorità separate. Fa largo uso di euristiche per favorire i processi interattivi in foreground (tipici dei sistemi desktop) e per prevenire il problema dell’inversione della priorità.
MacOS: Molto simile a Windows, impiega un Mach scheduler anch’esso basato su code di priorità ed euristiche.
Linux: Non distingue rigidamente processi e thread, ma gestisce una loro generalizzazione chiamata task. Utilizza il Completely Fair Scheduler (CFS). Il CFS usa un albero rosso-nero per ordinare i task in base al loro virtual run-time. La CPU viene sempre assegnata al task con il tempo virtuale minore.

Capitolo 3

La memoria

Introduzione alla gerarchia della memoria

I moderni sistemi informatici adottano una gerarchia della memoria per bilanciare costi e prestazioni. Questa struttura si articola solitamente in tre livelli:

Memoria molto veloce: Pochi megabyte, estremamente costosa e volatile.
Memoria di medio costo: Qualche gigabyte, abbastanza veloce e volatile (RAM).
Memoria su disco: Alcuni terabyte, non volatile, lenta ma a basso costo. Gestore della memoria: È la componente del sistema operativo incaricata di gestire questa gerarchia.

Storicamente, dai primi mainframe (prima del 1960) fino ai primi personal computer (prima del 1980), non esisteva alcuna astrazione della memoria. Ogni programma interagiva direttamente con la memoria fisica. In questo scenario, il modello presentato al programmatore è un insieme di indirizzi che vanno da 0 a un limite massimo. In assenza di astrazione, non è possibile eseguire due programmi contemporaneamente: se un programma scrivesse in una posizione usata da un altro, ne cancellerebbe i dati. Esistono tre varianti principali per l’organizzazione del sistema operativo in questo modello:

S.O. in RAM: Il sistema operativo risiede nel fondo della memoria nella RAM (Random Access Memory).
S.O. in ROM: Il sistema operativo si trova in cima alla memoria nella ROM (Read Only Memory).
Modello Ibrido: I driver dei dispositivi risiedono nella ROM in cima alla memoria, mentre il resto del sistema è nella RAM sottostante. Questo modello è tipico dei primi PC con MS-DOS, dove la parte in ROM è nota come BIOS (Basic Input Output System).

Esecuzione di molteplici programmi senza astrazione

È possibile ottenere un certo grado di parallelismo anche senza astrazione, seguendo diverse strategie:

Programmazione con thread: Un metodo per avere parallelismo è utilizzare molteplici thread all’interno dello stesso contesto di memoria. Essendo thread fanno parte dello stesso processo, quindi non è una vera esecuzione di più programmi.
Swapping (Versione primitiva): Un’altra possibilità è eseguire un programma alla volta, salvando l’intero contenuto della memoria su disco quando si passa al processo successivo. Finché risiede un solo programma in memoria, non si verificano conflitti.
Protezione tramite chiavi (IBM 360): Con l’ausilio di hardware speciale, è possibile far risiedere più programmi contemporaneamente. L’IBM 360 utilizzava una chiave di protezione di 4 bit per ogni cella di memoria. La PSW di un processo conteneva conteneva una chiave di 4 bit che gli permetteva di interagire con la locazione di memoria a lui assegnata. L’hardware intercettava ogni tentativo di accesso alla memoria: se il codice di protezione del processo non coincideva con la chiave nella PSW, l’accesso veniva bloccato.

Il problema della rilocazione

Anche se i programmi sono protetti dalle chiavi, sorge il problema degli indirizzi assoluti. Se due programmi da 16 KB vengono caricati uno sopra l’altro, il secondo (caricato all’indirizzo 16.384) fallirà se tenta di eseguire un salto relativo al proprio inizio (es. JMP 28), poiché finirà per saltare a un indirizzo nel primo programma invece che nel proprio. In questo esempio vediamo esattamente questa cosa, dopo aver caricato il processo a e b in memoria (c) possiamo notare che:

processo A: il jump 24 funzionerà bene e il processo finisce in modo corretto
processo B: il jump 28 cercherà di saltare ma entra nella memoria del primo processo e andrà in errore

Una soluzione a questo problema è la rilocazione statica: consiste nel modificare il programma direttamente durante il caricamento in memoria, aggiungendo l’indirizzo di partenza (es. 16.384) a ogni indirizzo del programma. Funzionava in questo modo: quando un programma era caricato all’indirizzo 16.384, la costante 16.384 era aggiunta a ogni indirizzo del programma durante il processo di caricamento. Anche se questo meccanismo funziona bene se eseguito in modo corretto, ma non è una soluzione in generale e rallenta il caricamento.

L’astrazione della memoria: lo spazio degli indirizzi

Esporre la memoria fisica presenta due gravi inconvenienti:

I programmi utente possono distruggere il sistema operativo.
È difficile gestire l’esecuzione contemporanea di più programmi.

Per risolvere i problemi di protezione e riposizionamento, è stata introdotta l’astrazione chiamata spazio degli indirizzi. Lo spazio degli indirizzi: è l’insieme degli indirizzi che un processo può utilizzare per indirizzare la memoria. Per rendere possibile questa astrazione virtuale in prima battuta facciamo uso della tecnica della rilocazione dinamica

Rilocazione dinamica: registri base e limite

La rilocazione dinamica, mappa lo spazio degli indirizzi di ogni processo su porzioni diverse di memoria fisica tramite hardware speciale, ovvero attraverso due registri della CPU:

Registro Base: Contiene l’indirizzo fisico di partenza del programma in memoria.
Registro Limite: Contiene la lunghezza del programma. Quando un processo accede alla memoria, l’hardware esegue due passaggi automatici:

Somma: Aggiunge il valore del registro base all’indirizzo generato dal programma prima di inviarlo al bus.
Controllo: Verifica se l’indirizzo è uguale o maggiore del valore nel registro limite; in tal caso, genera un errore e interrompe l’accesso. Su questa soluzione possiamo dire che:

Vantaggi: Permette a ogni processo di avere uno spazio privato degli indirizzi in modo semplice.
Svantaggi: Ogni riferimento alla memoria richiede una somma e un confronto, il che può rappresentare un onere computazionale.

Gestione del sovraccarico di memoria

Spesso la quantità totale di RAM richiesta dai processi in esecuzione supera la memoria fisica effettivamente disponibile. Per gestire questo scenario, i sistemi operativi hanno storicamente adottato due strategie principali:

Swapping: Consiste nello spostare interamente su disco i processi temporaneamente inattivi per fare spazio ad altri.
Memoria virtuale: Un’evoluzione successiva che consente l’esecuzione di programmi caricandone in RAM solo le parti strettamente necessarie.

Lo Swapping e la Frammentazione

Immaginiamo di avere due programmi, $P_{1}$ e $P_{2}$ . Attualmente $P_{1}$ è in esecuzione, ma vogliamo eseguire anche $P_{2}$ . Purtroppo, la memoria centrale (RAM) è piena. A questo punto interviene il componente del sistema operativo chiamato swapper: esso esegue uno swap-out (sposta $P_{1}$ dalla RAM al disco) e uno swap-in (carica $P_{2}$ dal disco alla RAM). Il disco viene quindi usato come “memoria secondaria” di appoggio. Il processo $P_{1}$ , finché si trova su disco, è penalizzato poiché non riceve risorse dalla CPU. Sebbene sembri una soluzione perfetta, lo swapping continuo di programmi di dimensioni diverse crea un grave problema: la frammentazione della memoria . Ne esistono due tipi:

Frammentazione Interna: Si verifica quando a un processo viene assegnata un’area di memoria leggermente più grande delle sue reali esigenze. Lo spazio extra all’interno di quell’area allocata rimane inutilizzato e sprecato.
Frammentazione Esterna: Si verifica quando la memoria totale libera sarebbe sufficiente per ospitare un nuovo processo, ma è suddivisa in tanti piccoli blocchi non contigui (buchi). Poiché il processo necessita di memoria contigua, non può essere caricato. L’unica soluzione è la Memory Compaction (Compattazione della memoria): il S.O. sposta fisicamente tutti i processi attivi verso il fondo della memoria per unire tutti i “buchi” in un unico grande spazio libero in cima. È una procedura estremamente lenta e si cerca di evitarla il più possibile.

Il problema dell’Allocazione con Dimensione Dinamica

La gestione della frammentazione è ulteriormente complicata dal fatto che i processi non hanno sempre dimensioni fisse. Durante l’esecuzione, i dati di un programma possono crescere (ad esempio, allocando memoria dinamicamente). La struttura ottimale per gestire la crescita dinamica all’interno di un processo prevede due segmenti mobili:

Segmento Dati (Heap): Posizionato subito dopo il codice statico del programma, cresce verso l’alto.
Segmento Stack (per variabili locali e ritorni): Posizionato in cima all’area di memoria allocata per il processo, cresce verso il basso. Se questi due segmenti crescono fino a scontrarsi, il processo ha finito lo spazio. Come interviene il S.O.?
Soluzione 1 (Sospensione): Se non c’è spazio adiacente in RAM per far crescere il processo e l’area di swap su disco è piena, il processo deve essere sospeso o terminato.
Soluzione 2 (Pre-allocazione): Una strategia preventiva. Quando il S.O. carica o sposta un processo, gli assegna preventivamente un “cuscinetto” di memoria extra, prevedendone la crescita. Tuttavia, se la crescita non avviene, questa memoria extra rimane sprecata (causando frammentazione interna).

Tenere traccia della memoria: Bitmaps e Liste

A causa dello swapping e delle dimensioni variabili dei processi, la memoria fisica diventa rapidamente un puzzle disordinato di “blocchi occupati” alternati a “buchi liberi”. Il Sistema Operativo ha quindi bisogno di strumenti per ricordarsi esattamente quali parti di RAM sono occupate e quali sono libere. Utilizza principalmente due tecniche:

A. Gestione con Bitmap La memoria viene idealmente divisa in “unità di allocazione” (che possono andare da pochi byte a vari kilobyte). La Bitmap è una lunga mappa in cui ogni bit rappresenta un’unità: 0 significa libera, 1 significa occupata (o viceversa).

Il parametro cruciale: La dimensione dell’unità di allocazione. Se scegliamo unità molto piccole (es. 4 byte), avremo una mappa enorme (per mappare 32 bit di memoria ci vorrà 1 bit di mappa).
Vantaggi: La dimensione della bitmap è fissa e dipende solo dalla quantità totale di RAM e dalla dimensione scelta per l’unità.
Svantaggi: Quando bisogna caricare un nuovo processo che richiede k unità contigue, il S.O. deve scansionare la lunghissima sequenza di bit per cercare una stringa ininterrotta di k zeri. Questa ricerca è estremamente lenta. B. Gestione con Liste Collegate Invece di mappare ogni singolo blocco, il S.O. mantiene una lista dinamica (Linked List) che mappa interi segmenti . Ogni nodo (voce) della lista descrive un blocco contiguo, e contiene:

Il tipo: Processo occupato (P) o Buco vuoto (H - Hole).
L’indirizzo fisico di partenza.
La lunghezza del blocco.
Il puntatore al segmento successivo. La lista è ordinata in base all’indirizzo fisico crescente. Il momento più delicato in questo sistema è quando un processo termina o viene “swappato”. Il suo segmento P diventa un segmento H. A questo punto, il S.O. deve guardare i segmenti vicini per evitare la frammentazione, potendo incontrare 4 casistiche:

(a) Nessun vicino vuoto: Si aggiorna semplicemente il nodo da P ad H.
(b) Vicino vuoto sopra: Il nuovo buco e quello precedente vengono fusi. La lista si accorcia di una voce.
(c) Vicino vuoto sotto: Il nuovo buco e quello successivo vengono fusi. La lista si accorcia di una voce.
(d) Entrambi i vicini vuoti: Si fondono tre buchi adiacenti in un unico grande spazio vuoto. Vengono eliminati due elementi dalla lista.

Algoritmi di allocazione: Come scegliere il “buco” giusto?

Quando arriva un nuovo processo, il gestore della memoria deve scorrere la lista collegata per trovargli un buco adeguato. Ma quale sceglie se ce n’è più di uno? Usa degli specifici algoritmi:

First fit (Primo incastro): È il più semplice e veloce. Scorre la lista dall’inizio e prende il primo buco abbastanza grande. Se il buco è più grande del processo, viene diviso in due: una parte per il processo e una per il buco residuo.
Next fit (Incastro successivo): Identico al First fit, ma “si ricorda” dove aveva trovato l’ultimo spazio. La ricerca successiva riparte da quel punto invece che dall’inizio. Previene l’accumulo di piccoli buchi tutti all’inizio della memoria.
Best fit (Miglior incastro): Cerca in tutta la lista e sceglie il buco più piccolo tra quelli in grado di contenere il processo.
- Svantaggio: È più lento (deve scorrere tutta la lista) e paradossalmente genera un enorme spreco di memoria: crea tantissimi microscopici “buchini” residui, inutilizzabili per qualsiasi altro processo.
Worst fit (Peggior incastro): Nasce per risolvere i difetti del Best fit. Cerca in tutta la lista e sceglie intenzionalmente il buco più grande in assoluto. L’idea è che il buco residuo che avanzerà sarà ancora abbastanza grande da poter ospitare altri processi in futuro.

TIP

Per velocizzare queste ricerche, i progettisti hanno ideato tre strategie di ottimizzazione:

Liste separate: Invece di una lista mista, si usano due liste distinte: una solo per i processi e una solo per i buchi vuoti. Così gli algoritmi scansionano solo i buchi, risparmiando tempo.

Ordinamento per dimensione: La lista dei buchi viene ordinata dal più piccolo al più grande. Questo trasforma il Best fit in un algoritmo velocissimo: il primo buco utile che incontra è per forza di cose il più piccolo adatto (quindi il migliore).

Svantaggio dell’ordinamento: Quando un processo termina, ritrovare i suoi vicini “fisici” per unire i buchi (le casistiche a,b,c,d viste prima) diventa un incubo computazionale, perché la lista non è più ordinata per posizione.

Quick fit: Usa array o tabelle che puntano a liste di buchi di dimensioni standardizzate e molto richieste (es. una lista solo per buchi da 4 KB, un’altra per buchi da 8 KB, ecc.).
- Vantaggio: Allocazione praticamente istantanea se il processo richiede una misura standard.
- Svantaggio: Come per l’ordinamento per dimensione, la deallocazione e la fusione dei buchi adiacenti restano operazioni molto dispendiose.

La memoria virtuale

Come abbiamo visto, gestire “buchi” di memoria di dimensioni variabili (tramite liste e algoritmi di allocazione) è complesso e non risolve mai del tutto il problema della frammentazione. Per eliminare definitivamente questo ostacolo, l’informatica ha introdotto un’astrazione rivoluzionaria: la memoria virtuale.

L’obiettivo di questa astrazione è creare un’illusione perfetta: far credere a ogni programma in esecuzione di disporre di un’intera memoria centrale privata, continua e protetta. Con questa tecnica, lo spazio di memoria originario diventa uno spazio di indirizzamento virtuale, il quale viene suddiviso in piccoli blocchi di dimensione fissa chiamati pagine.

La caratteristica cruciale della memoria virtuale è che non tutte le pagine di un programma devono risiedere contemporaneamente nella memoria fisica (RAM) per poterne permettere l’esecuzione. Le pagine virtuali vengono mappate sulla memoria fisica in modo dinamico:

Accesso diretto: Quando il programma fa riferimento a un indirizzo che fa parte di una pagina attualmente caricata nella memoria fisica, l’hardware esegue il mapping in modo diretto e istantaneo.
Recupero dal disco: Quando, al contrario, il programma fa riferimento a uno spazio degli indirizzi che non è al momento presente nella memoria fisica, l’hardware genera un’interruzione. Il sistema operativo viene allertato per andare a recuperare il “pezzo” mancante dal disco (memoria secondaria), caricarlo in RAM, e infine rieseguire l’istruzione che era fallita.

La Paginazione (Paging) e la MMU

La paginazione ci permette quindi di suddividere la memoria fisica da quella virtuale associata ad ogni processo infatti quando un programma esegue un’istruzione come:

MOV REG,1000 // muove quello che c'è all'indirizzo 1000 dentro REG

Per eseguirla deve accedere prima alla memoria e lo fa generando degli indirizzi detti indirizzi virtuali (l’insieme di questi indirizzi forma lo spazio virtuale degli indirizzi che sarebbero l’insieme degli indirizzi a disposizione di un processo). Gli indirizzi virtuali generati dalla CPU non vanno direttamente al bus di memoria ma passano prima attraverso un componente hardware dedicato chiamato MMU (Memory Management Unit) che consiste in un unità di gestione della memoria che ha il compito di mappare gli indirizzi virtuali sugli indirizzi di memoria fisica.

Pagine e frame

Le unità base della gestione della paginazione sono:

Pagine: unità di dimensione fissa in cui è suddiviso lo spazio degli indirizzi virtuali.
Frame: Unità di memoria della memoria fisica (RAM).

EXAMPLE

Prendendo ad esempio pagine da $4 K B$ (coma da img):

L’intervallo segnato come $0 K - 4 K$ significa che gli indirizzi virtuali in quella pagina vanno dall’indirizzo $0$ all’indirizzo $4095$ .

L’intervallo $4 K - 8 K$ si riferisce agli indirizzi che vanno da $4096$ a $8191$ , e così via.

Di conseguenza, ogni pagina contiene esattamente $4096$ indirizzi, che partono da un multiplo di $4096$ fino al multiplo di $4096$ successivo.

La maggior parte delle volte abbiamo molte più pagine virtuali che pagine fisiche, questo perché quella virtuali possono risiedere anche in disco. Per gestire questa cosa nella tabella degli indirizzi è presente un bit presente/assente, il quale tiene traccia di quali pagine sono fisicamente presenti in memoria. Quando cerchiamo di indirizzare un indirizzo non mappato nella memoria fisica viene sollevato dalla CPU un trap verso il sistema operativo detto page fault. Quando accade il sistema operativo interviene prelevando frame poco utilizzato e ne scrive il suo contenuto su disco (se il dirty bit è true), fatto ciò inserisce l’indirizzo del frame di memoria richiesto dentro la mappatura dell’MMU e riavvia l’istruzione che era andata in trap.

EXAMPLE

Esempio con un istruzione reale prendendo in considerazione la tabella degli indirizzi dell’immagine precedente:

Tentativo di accesso: La CPU esegue MOV REG, 32780, chiedendo di accedere alla Pagina virtuale 8.

Page Fault: La MMU consulta la Page Table, vede che la Pagina 8 non è in RAM (bit assente) e genera un’interruzione (trap) verso il Sistema Operativo.

Swap-Out: Il Sistema Operativo libera spazio in RAM: prende un frame usato poco e lo copia su disco.

Swap-In: Il Sistema Operativo preleva la Pagina 8 dal disco e la scrive nel frame appena liberato in RAM, e aggiorna la usata dall’MMU.

Riavvio: La CPU ripete l’istruzione MOV REG, 32780. Questa volta la MMU trova la pagina e l’operazione va a buon fine.

Il processo di traduzione

Per tradurre un indirizzo virtuale in indirizzo fisico la CPU esegue uno specifico processo, prendendo in esame l’istruzione:

MOV REG,0 //mette quello che c'è all'indirizzo 0 in REG

Viene eseguita in questo modo

L’indirizzo virtuale 0 viene inviato alla MMU.
La MMU vede che questo indirizzo virtuale cade nella pagina 0 (che copre gli indirizzi da 0 a 4095).
Secondo il mapping interno della MMU, la pagina 0 corrisponde al frame 2 (che copre gli indirizzi fisici da 8192 a 12287).
La MMU trasforma così l’indirizzo virtuale 0 nell’indirizzo fisico 8192 e lo invia esternamente sul bus.

Risultato: La MMU ha effettivamente mappato tutti gli indirizzi virtuali compresi fra 0 e 4095 sugli indirizzi fisici che vanno da 8192 a 12287.

Come si comporta la MMU

La tabella delle pagine

Di seguito nomineremo spesso la tabella delle pagine, ci basta sapere che è una tabella che contiene informazioni riguardo ogni pagina come i bit presente/assente e l’indirizzo fisico del frame alla quale è mappata quella pagina

Gli indirizzi virtuali generati dalla CPU sono così formati:

numero di pagina: questi sono gli $m$ bit più significativi dell’indirizzo virtuale e ci indicano quale pagina guardare per trovare il nostro indirizzo (il numero di pagine totali è $2^{m}$ )
offset: questi sono gli $n$ bit meno significativi che ci indicano quale indirizzo prendere tra quelli disponibili nella singola pagina. ( $2^{n}$ sono gli indirizzi contenuti da una pagina)

Esercizio di esame

Dato un indirizzo virtuale dobbiamo fare la seguente cosa per tradurlo in indirizzo fisico: Supponiamo di avere una RAM a $32$ kilobyte, e di voler accedere all’indirizzo virtuale $v = 8196$ . Con $dimensione dei frame = 4096$ , effettuiamo: $\frac{8196}{4096} = {2 (Numero di Pagina) 4 (Offset)$ Supponiamo che nella nostra tabella delle pagine, la pagina $2$ è associata al frame $6$ . Moltiplichiamo adesso $6 \cdot dimensione dei frame = 6 \cdot 4096 = 24576$ . Otterremo quindi il primo indirizzo fisico appartenente al frame 6. Sommiamo l’offset ottenuto in precedenza, $24576 + 4 = 24580$ .

Scendendo nel dettaglio di cosa fa l’MMU possiamo dire che: il processo di traduzione viene eseguito in maniera più veloce e intuitiva. La divisione è sempre di potenze di 2, in quanto strettamente legata alla dimensione dei frame. Sarà quindi possibile implementarla con uno shift. Nello specifico segue questi step (input: indirizzo virtuale):

Estrazione del numero di pagina (Quoziente): Viene eseguito uno shift logico verso destra di $n$ bit sull’indirizzo virtuale. Formula: NumeroPagina = VA >> n
Estrazione dell’offset (Resto): Viene eseguito un AND logico tra l’indirizzo virtuale e una maschera composta da $n$ bit a 1. Formula: Offset = VA AND ((1 << n) - 1)
Consultazione della tabella delle pagine: L’hardware usa il NumeroPagina appena trovato come indice per cercare nella tabella delle pagine il NumeroFrame corrispondente (se la pagina è in RAM).
Allineamento del frame: Il NumeroFrame trovato viene shiftato verso sinistra di $n$ bit. Questo crea lo spazio per inserire l’offset e, matematicamente, equivale esattamente a calcolare $numeroFrame \times 2^{n}$ . Formula: IndirizzoBaseFisico = NumeroFrame << n
Composizione dell’indirizzo fisico: Si esegue un OR logico (che in questo caso equivale a una somma, dato che i bit inferiori dell’indirizzo base sono tutti zeri) tra l’indirizzo base fisico e l’offset. Formula: IndirizzoFisico = IndirizzoBaseFisico OR Offset

Esercizio di esame

Virtual memory = 4Mb

voci tabella pagine = $2^{13}$

Numero di frame a 8bit

Quanta RAM ho? Avendo 4Mb = $2^{22}$ byte di virtual memory, con $\frac{2 ^{22}}{2 ^{13}}$ avrei la dimensione della singola pagina, ovvero $2^{9}$ .

$2^{9} b y t e \cdot 2^{8} (numero di frame) = 128 kb$

La tabella delle pagine

La tabella delle pagine è una tabella utilizzata dall’MMU insieme al sistema operativo per tradurre da indirizzi virtuali a fisici, l’esatto layout di una voce di una singola tabella della pagina dipende molto dalla macchina su cui si opera. Tuttavia, il tipo di informazioni presenti è più o meno lo stesso per tutte le architetture. Di seguito una rassegna dei campi contenuti in una voce:

Numero del frame (frame number): È il campo più importante in assoluto, in quanto indica l’indirizzo fisico in cui si trova la pagina.
Bit Presente/Assente: Se questo bit è 1, la voce è valida e può essere utilizzata normalmente. Se è 0, significa che la pagina virtuale cui appartiene la voce non è effettivamente in memoria in quel momento.
Protezione: Specifica quali tipi di accesso sono consentiti per quella pagina. Nella sua forma più basilare, questo campo contiene 1 solo bit: il valore 0 significa lettura/scrittura consentita, mentre il valore 1 indica l’accesso in sola lettura.
Bit Modificato (Dirty bit): Tiene traccia dell’uso della pagina. Se la pagina è stata modificata rispetto alla sua versione in disco (cioè è considerata “sporca”), questo bit è impostato. Se la pagina non è stata modificata (cioè è considerata “pulita”), in caso di sfratto il suo contenuto può essere semplicemente abbandonato senza sovrascriverlo, poiché la copia originaria presente sul disco è ancora perfettamente valida.
Bit Referenziato: È impostato dall’hardware ogni qualvolta si faccia riferimento alla pagina, sia per un’operazione di lettura sia in scrittura. Serve ad aiutare il sistema operativo a scaricare (cioè a “sfrattare”) una pagina quando si verifica un page fault. Le pagine inutilizzate (non referenziate) sono le candidate migliori per lo sfratto rispetto a quelle usate di recente.
Disabilitazione della cache: L’ultimo bit consente di disabilitare la cache per la specifica pagina. Questo è fondamentale per l’I/O: fa in modo che la macchina debba prelevare la parola direttamente da quel dispositivo hardware, senza rischiare di usare una vecchia parola non aggiornata messa precedentemente in cache.

Problemi principali della paginazione

Nei sistemi operativi, la gestione della memoria tramite paginazione impone due sfide architetturali critiche e diametralmente opposte:

Velocità di traduzione: La mappatura dall’indirizzo virtuale a quello fisico deve essere quasi istantanea. Poiché questa operazione avviene per ogni singolo riferimento alla memoria, un minimo ritardo genera un collo di bottiglia per l’intero sistema.
Dimensione delle tabelle: Con i moderni spazi di indirizzamento a 64 bit, il numero di pagine virtuali è immenso, rendendo le relative Tabelle delle Pagine (Page Table) enormi e ingombranti. La necessità di avere un meccanismo che sia contemporaneamente gigantesco e ultra-veloce rappresenta un ostacolo storico per i progettisti. Dal punto di vista concettuale, il problema si scontra con due approcci estremi, nessuno dei quali è praticabile da solo.

Nel primo approccio (basato sull’hardware), l’intera tabella delle pagine viene memorizzata in un array di registri interni alla CPU. Durante l’esecuzione le prestazioni sono eccellenti, poiché il processore non deve mai accedere alla RAM per tradurre gli indirizzi. Tuttavia, i costi architetturali sono proibitivi: con le dimensioni delle tabelle moderne, i tempi e le risorse necessarie per aggiornare milioni di registri a ogni context switch paralizzerebbero il sistema.
All’estremo opposto (approccio in memoria), l’intera tabella viene mantenuta esclusivamente nella RAM. In questo scenario all’hardware basta un singolo registro dedicato, il PTBR (Page Table Base Register), che punta all’inizio della tabella del processo in esecuzione. Se da un lato il context switch diventa istantaneo (è sufficiente aggiornare il valore del PTBR) e si risolvono i limiti di spazio, dall’altro la lentezza diventa inaccettabile: ogni singola istruzione richiederebbe un accesso extra alla RAM solo per consultare la tabella, dimezzando di fatto le prestazioni del computer.

Translation Lookaside Buffer (TLB)

Per bilanciare velocità e dimensioni, la soluzione escogitata è stata quella di equipaggiare i computer di un piccolo dispositivo hardware dedicato esclusivamente a mappare gli indirizzi virtuali sugli indirizzi fisici senza dover passare ogni volta dalla tabella delle pagine in memoria, questo dispositivo si chiama TLB Acronimo di Translation Lookaside Buffer, talvolta chiamato anche memoria associativa.

Capacità e Struttura: Contiene solitamente poche voci, ciascuna voce contiene informazioni cruciali riguardo una pagina, tra cui:
- il numero di pagina virtuale
- un dirty bit: quando avviene una modifica ad un record questo viene macchiato come dirty, quando questo succede e quel record deve essere eliminato dalla TLB la modifica deve essere riportata alla tabella delle pagine.
- il codice di protezione (i permessi di lettura, scrittura ed esecuzione)
- il frame fisico
Funzionamento: Quando un indirizzo virtuale viene presentato alla MMU per la traduzione, l’hardware per prima cosa guarda se il suo numero di pagina virtuale è presente nel TLB, confrontandolo simultaneamente (cioè in parallelo) con tutte le voci.
- TLB hit (successo di TLB): Il numero di pagina viene trovato e la traduzione avviene istantaneamente.
- TLB miss (fallimento di TLB): Avviene quando il numero di pagina virtuale non è nel TLB. In questo caso, la MMU rileva il miss e fa una normale ricerca sulla tabella delle pagine in memoria. Quindi sfratta una delle voci dal TLB e la rimpiazza con la voce della tabella delle pagine appena cercata e recuperata. In questo modo, se quella stessa pagina è riusata a breve termine, la seconda volta si avrà un successo (TLB hit).
Caratteristiche: è importante dire che questa memoria hardware è comparabile ad una cache e la ricerca viene fatta su tutte le sue celle in modo parallelo, quindi è molto veloce.

Effective Access Time (EAT)

L’Effective Access Time (EAT), o tempo di accesso effettivo, è una metrica fondamentale per valutare le prestazioni di un sistema di memoria con paginazione che utilizza un Translation Lookaside Buffer (TLB). L’EAT ci permette di calcolare il tempo medio ponderato di accesso alla memoria, tenendo conto del TLB Hit Ratio ( $ε$ ), ovvero la percentuale di volte in cui la traduzione viene trovata con successo all’interno della TLB.

Facciamo un esempio

tempo di accesso alla memoria: $α = 100 ns$

Tempo di accesso alla TLB: $β = 20 ns$

I tempi effettivi?

Con un TLB hit abbiamo $100 + 20 = 120 ns$ .

Con un TLB miss abbiamo $2 \cdot 100 + 20 = 220 ns$ .

Con un ratio TLB = $ε$ , tempo di accesso alla TLB = $β$ e tempo di accesso alla memoria $α$ abbiamo $EAT = ε (α + β) + (1 - ε) (2 α + β)$

Osservazioni importanti sulla TLB

Di seguito alcune osservazioni importanti sulla TLB:

Alcuni attributi dei record delle tabelle delle pagine non sono presenti, come il bit di referenzialmento o di validità di allocazione. Osserviamo che, se un record è presente nella TLB, dev’essere per forza valido e referenziato.
La TLB conterrà sempre record relativi a pagine utili per il programma attuale. Inoltre, quando avviene una TLB miss, si andrà ad aggiornare il valore sulla TLB.
Alcuni voci possono essere vincolate ad essere nella TLB, migliorando le tempistiche.

Le tabelle delle pagine sono una per processo: ne consegue che gli stessi indirizzi virtuali possono essere riutilizzati per rifarsi a indirizzi fisici differenti. Tuttavia, la TLB è unica per la CPU (o il core). Detto ciò, a causa del riutilizzo degli indirizzi virtuali, bisogna avere un modo per disambiguare i record riguardanti ogni processo. Di seguito vediamo due strategie:

Flush totale della TLB a ogni context-switch: Non ideale, favorisce un alto numero di cache miss iniziali.
Address-space ID: Aggiungendo un identificatore, chiamato ASID, è possibile disambiguare le voci delle TLB con lo stesso indirizzo virtuale, ma appartenenti a processi differenti, favorendo cache hit ad ogni context switch.

La strategia migliore è la seconda. Complica un po’ la ricerca, aggiungendo gli ASID alla ricerca del record nella TLB, ma è molto efficiente in ambienti multithread. È un ottimo compromesso.

Gestione TLB via software nelle architetture RISC

Finora si è supposto che ogni macchina con memoria virtuale paginata abbia delle tabelle delle pagine riconosciute direttamente dall’hardware, più un TLB. Nel passato questo assunto era valido. Tuttavia, molte macchine ad architettura RISC moderne eseguono quasi tutta questa gestione delle pagine tramite software.

Nella gestione del TLB via software, è fondamentale capire la differenza fra due tipi di miss:

Soft miss: Avviene quando la pagina di riferimento non è nel TLB, ma si trova comunque all’interno della memoria RAM. La risoluzione è rapida.
Hard miss: All’opposto, avviene quando la pagina stessa non è in memoria (e ovviamente nemmeno nel TLB). Per prendere la pagina serve un accesso al disco, il che comporta tempistiche di parecchi millisecondi. Questa situazione può esitare in un errore di segmentazione (segmentation fault).

I TLB possono essere usati per velocizzare la traduzione dell’indirizzo virtuale nell’indirizzo fisico rispetto allo schema originale della “tabella-delle-pagine-in-memoria”. Rimane però un altro problema aperto: quale comportamento assumere con spazi degli indirizzi virtuali molto grandi?

Tabelle delle pagine multilivello

La paginazione multilivello è una struttura gerarchica utilizzata dai sistemi operativi per tradurre gli indirizzi di memoria virtuale in indirizzi fisici riducendo drasticamente il consumo di RAM.

Invece di mantenere in memoria un’unica, gigantesca tabella che mappa l’intero spazio virtuale a disposizione di un processo (anche le enormi porzioni vuote), si utilizza una tabella principale e compatta, chiamata Page Directory.

Questa directory contiene semplicemente dei puntatori a svariate tabelle secondarie più piccole. Il grande vantaggio di questo approccio è che le tabelle secondarie vengono create e mantenute in RAM esclusivamente per le porzioni di memoria effettivamente utilizzate dal programma; le aree non allocate non richiedono alcuna tabella.

Inoltre, se il sistema ha bisogno di liberare spazio, le tabelle secondarie non consultate da tempo possono essere temporaneamente spostate sul disco fisso, lasciando in memoria solo la essenziale directory principale.

Meccanismo a due livelli: Quando viene presentato un indirizzo virtuale alla MMU, l’hardware sa che è composto da due sotto-indirizzi quindi per prima cosa estrae il primo campo (chiamato PT1) e usa questo valore come indice nella tabella delle pagine di livello più alto. Il secondo campo, PT2, adesso è usato come un indice nella tabella delle pagine di secondo livello (selezionata dal passo precedente) per cercare il numero di frame della pagina stessa.
Espansione dei livelli: Possiamo aumentare il numero di livelli per supportare indirizzi molto grandi; questo ci permette di risparmiare memoria (tenendo su disco i livelli non usati) a discapito però della velocità, poiché sarà richiesto un accesso in più alla memoria RAM per ogni livello aggiunto alla gerarchia.

Tabelle delle pagine invertite

Un’alternativa al continuo aumento dei livelli nella paginazione gerarchica è rappresentata dalle tabelle delle pagine invertite. In questa architettura, il paradigma classico viene ribaltato: anziché mantenere una voce per ogni pagina dello spazio virtuale, la tabella contiene una singola voce per ogni frame fisico effettivamente presente nella memoria RAM. Questo approccio comporta due conseguenze contrapposte:

Enorme risparmio di spazio: La dimensione della tabella dipende unicamente dalla quantità di memoria fisica installata e non da quella virtuale. Questo è un vantaggio cruciale nei sistemi moderni, dove lo spazio di indirizzamento virtuale è enormemente più vasto della RAM disponibile.
Traduzione complessa e lenta: Nelle tabelle tradizionali, la pagina virtuale p funziona esattamente come l’indice di un array, consentendo un accesso diretto e immediato alla riga corrispondente per leggere il frame fisico. Nella tabella invertita, invece, la struttura cambia: le righe rappresentano i frame fisici e al loro interno viene annotato quale processo (n) (tramite ASID) e quale pagina virtuale (p) vi sono ospitati in quel momento. Di conseguenza, quando l’hardware ha bisogno di tradurre l’indirizzo, si ritrova in mano la coppia (n, p) ma non sa a priori in quale riga sia scritta. Non potendo usare l’accesso diretto, è costretto a effettuare una vera e propria ricerca per contenuto, scansionando la tabella finché non trova la riga con l’esatta corrispondenza (il cui indice indica finalmente il frame fisico). Senza strutture aggiuntive, questa ricerca si tradurrebbe in innumerevoli e lenti accessi sequenziali alla RAM, paralizzando le prestazioni.

Per aggirare questo ostacolo prestazionale, il sistema fa un impiego massiccio del TLB (Translation Lookaside Buffer). Finché le pagine utilizzate più di frequente si trovano in questa memoria cache ultra-veloce, la traduzione avviene in modo istantaneo, esattamente come nelle architetture tradizionali.

Il problema si pone in caso di TLB miss (quando la pagina cercata non è nella cache), evento che costringe l’hardware a interrogare la grande tabella invertita in RAM. Per evitare di doverla scandire linearmente dall’inizio alla fine, la ricerca viene ottimizzata strutturando la tabella come una hash table basata sull’indirizzo virtuale, riducendo così drasticamente i tempi necessari per localizzare il frame fisico.

Cache della memoria vs Memoria virtuale

La cache della memoria può essere basata sugli indirizzi fisici, o sugli indirizzi virtuali. Ciò dipenderà rispettivamente, se posizioniamo l’MMU prima o dopo la cache.

Indirizzi fisici: Pro: non servirà invalidare la cache sul context-switch. Avendo indirizzi fisici già tradotti nella cache, non si avranno problemi di ambiguità. Contro: l’MMU diventa un collo di bottiglia per la cache.
Indirizzi virtuali. Pro: più veloce ed efficace Contro: servono gli ASID per non invalidare la cache Soluzione effettiva: approccio ibrido La cache $L 1$ basata su indirizzi virtuali, si pone prima dell’MMU, basandosi sugli indirizzi virtuali. La cache $L 2$ e successive dopo l’MMU, basate su indirizzi fisici.

Gestione della memoria virtuale e algoritmi di sostituzione delle pagine

Quando si verifica un page fault, il sistema operativo deve fare spazio alla pagina entrante scegliendo una pagina residente da sfrattare. Se la pagina scelta è stata modificata durante la sua permanenza, deve essere prima riscritta sul disco per mantenerne la copia aggiornata. Le prestazioni del sistema risultano ottimali se si sceglie di rimuovere una pagina non particolarmente utilizzata.

Algoritmo di Sostituzione Ottimale

Il miglior algoritmo di sostituzione delle pagine è puramente teorico. L’idea è etichettare ciascuna pagina in memoria con il numero di istruzioni da eseguire prima che venga referenziata nuovamente. Al momento del page fault, l’algoritmo rimuove la pagina con l’etichetta più alta. Questo approccio è irrealizzabile, poiché il sistema operativo non ha modo di sapere in anticipo quando le pagine verranno referenziate la volta successiva.

Not Recently Used (NRU)

Per raccogliere statistiche sull’uso delle pagine, l’hardware mette a disposizione due bit di stato associati a ciascuna voce della tabella delle pagine:

Bit R (Referenced): Impostato a 1 quando si fa riferimento alla pagina (in lettura o scrittura).
Bit M (Modified): Impostato a 1 solo quando la pagina viene scritta (modificata).

All’avvio, questi bit sono azzerati. Periodicamente (es. a ogni interrupt del clock), il Bit R viene ripulito per distinguere le pagine usate di recente da quelle inattive. Al verificarsi di un page fault, l’algoritmo NRU divide le pagine in quattro categorie in base ai valori attuali dei bit:

Classe 0: non referenziato, non modificato.
Classe 1: non referenziato, modificato.
Classe 2: referenziato, non modificato.
Classe 3: referenziato, modificato.

L’algoritmo rimuove una pagina a caso dalla classe non vuota con il numero più basso. È infatti preferibile rimuovere una pagina modificata ma non usata di recente, piuttosto che una pagina pulita ma usata frequentemente.

First-in, First-out (FIFO) e Seconda Chance

L’algoritmo FIFO tiene una lista delle pagine in memoria ordinandole per tempo di arrivo. A un page fault, rimuove semplicemente la pagina più vecchia in testa. Questo approccio rigido rischia di eliminare pagine vecchie ma ancora usate intensamente. Per evitare questo problema, l’algoritmo della Seconda Chance controlla il Bit R della pagina più vecchia prima di rimuoverla:

Se R = 0: La pagina è vecchia e inutilizzata, quindi viene sostituita immediatamente.
Se R = 1: Il bit viene azzerato, la pagina viene spostata in fondo alla lista (rinnovando il suo tempo di caricamento) e la ricerca continua. Se tutte le pagine sono state referenziate, degenera in un FIFO puro.

Algoritmo Clock

L’algoritmo della Seconda Chance è inefficiente perché sposta continuamente le pagine lungo la lista. L’algoritmo Clock migliora la struttura mantenendo i frame su una lista circolare a forma di orologio. Una lancetta indica la pagina vecchia. Quando avviene un page fault, si esamina la pagina indicata: se R = 0, la pagina viene sfrattata e la lancetta avanza; se R = 1, il bit viene azzerato e la lancetta passa alla pagina successiva finché non ne trova una sacrificabile. Se tutti i valori di R sono uguali a 1 nel momento in cui si verifica un page fault, la lancetta dell’algoritmo Clock farà un giro completo dell’orologio (360 gradi). Al termine di questo giro, la pagina che era inizialmente indicata dalla lancetta verrà sfrattata.

Least Recently Used (LRU)

L’algoritmo Least Recently Used (LRU) rappresenta un’eccellente approssimazione dell’algoritmo ottimale teorico. Per realizzare un LRU hardware puro, i progettisti dovrebbero dotare il sistema di un contatore a 64 bit capace di incrementarsi automaticamente a ogni singola istruzione eseguita dalla CPU. Parallelamente, ogni voce della tabella delle pagine dovrebbe possedere uno spazio dedicato per memorizzare questo valore. In questo scenario, ogni volta che la memoria viene referenziata, il valore attuale del contatore globale viene copiato istantaneamente nella voce della tabella corrispondente alla pagina appena utilizzata. Al verificarsi di un page fault, il sistema operativo è costretto a esaminare tutti i contatori presenti nella tabella delle pagine per individuare il valore assoluto più basso. Quella cifra identifica matematicamente la pagina usata meno recentemente, che diventa la candidata perfetta per la rimozione. Questa implementazione, per quanto teoricamente ineccepibile, si scontra duramente con la realtà ingegneristica. Aggiornare un contatore nella memoria a ogni singola istruzione, per poi dover scansionare l’intera tabella a ogni errore di pagina, richiederebbe un hardware dedicato estremamente complesso e costoso. Trovare una pagina, aggiornarla e riordinarla in tempo reale comporta un dispendio di tempo e risorse che rende l’LRU puro impraticabile per la quasi totalità dei computer commerciali.

Not Frequently Used (NFU)

Proprio per superare gli ostacoli fisici ed economici dell’LRU, i progettisti hanno ideato delle simulazioni implementabili via software. La prima e più intuitiva di queste è l’algoritmo Not Frequently Used (NFU).

Il suo funzionamento si basa sull’associazione di un contatore software a ciascuna pagina residente in memoria, rigorosamente inizializzato a zero al momento del caricamento. Invece di agire a ogni singola istruzione, l’NFU sfrutta l’interrupt periodico del clock. A ogni “tic” del clock, il sistema operativo effettua una rapida scansione e somma il valore del Bit R (il bit di riferimento, che vale 1 se la pagina è stata usata in quel ciclo, 0 altrimenti) al contatore di ciascuna pagina. In questo modo, i contatori accumulano punteggio, tenendo una traccia sommaria di quante volte ogni singola pagina è stata utilizzata durante la sua permanenza in memoria. Al momento di un page fault, la scelta della “vittima” da sfrattare ricade semplicemente sulla pagina che possiede il contatore numericamente più basso.

Tuttavia, l’NFU nasconde un difetto strutturale critico che lo rende imperfetto rispetto all’LRU: è dotato di una memoria infallibile, ovvero non dimentica mai il passato. Per comprendere il problema, possiamo immaginare l’esecuzione di un compilatore strutturato a passaggi multipli. Durante il primo passaggio, il programma utilizzerà intensamente un gruppo specifico di pagine, facendo schizzare i loro contatori a valori altissimi. Quando il programma passa alla seconda fase, quelle pagine del primo passaggio non gli serviranno più; tuttavia, il loro punteggio storico le proteggerà ostinatamente dalla rimozione. Di conseguenza, il sistema operativo finirà paradossalmente per rimpiazzare le pagine nuove e realmente utili della fase in corso (che partono inevitabilmente da un contatore basso), salvando invece le pagine vecchie e inattive. L’NFU fallisce quindi nel cogliere il vero concetto di “recente”, limitandosi a premiare un generico utilizzo totale, per risolvere questo limite si usa l’algoritmo di Aging.

Algoritmo di Aging

Ha due fasi principali ad ogni interrupt di clock:

Prendo il contatore software e faccio uno shift a destra di 1 bit.
Aggiungo (colloco) il bit di referenziamento (R) a sinistra, in modo che prenda il posto del bit più significativo. Questo fa sì che il bit scartato a destra sia quello meno significativo (il più vecchio nel tempo).

EXAMPLE

Di seguito un esempio di come funziona dalla parte alta di questa immagine si capisce quali frame vengono utilizzati ad ogni ciclo di clock(i bit messi a 1 indicano che quello specifico frame è stato utilizzato)

In caso di page fault, si sceglie la pagina con il contatore più piccolo, scelta coerente con il principio della LRU. L’1 aggiunto a sinistra ha il contributo maggiore, pesando di più degli accessi passati.

Limiti dell’Algoritmo di Aging rispetto a LRU:

Memoria limitata del contatore: L’Aging ha una “memoria” limitata dal numero di bit del contatore (es. 64 bit). Se due pagine hanno lo stesso contatore, significa che hanno avuto la stessa storia recente, ma la LRU vera sarebbe capace di guardare ancora più indietro per spareggiare. In caso di ex aequo tra due contatori pessimi, si ripiega solitamente su una scelta FIFO.
Mancanza di granularità nel singolo ciclo: All’interno di un singolo ciclo di clock (span temporale), dietro a un bit ‘1’ ci può essere stato un solo referenziamento così come un milione. L’Aging segna solo che c’è stato un accesso, mentre una LRU hardware saprebbe distinguere l’esatto istante di ogni singolo accesso.

Il Modello Working Set

Il ciclo di vita della memoria di un processo inizia generalmente con la strategia del Demand Paging (paginazione su richiesta). Nella sua forma più pura, un processo viene avviato senza che nessuna delle sue pagine sia presente in memoria fisica. Appena la CPU tenta di prelevare la prima istruzione, genera inevitabilmente un page fault. Questo innesca il caricamento della pagina iniziale. Subito dopo, seguiranno a raffica altri page fault per caricare lo stack, le variabili globali e le istruzioni successive. Dopo questa fase di assestamento iniziale, il processo disporrà delle pagine fondamentali e inizierà a girare in modo fluido. Le pagine vengono quindi caricate letteralmente “su richiesta”, senza alcun pre-caricamento.

Ma perché, dopo una raffica iniziale di errori, il processo si stabilizza? Questo accade grazie a una proprietà fondamentale del software nota come Località di Riferimento. I processi non accedono al loro spazio di indirizzamento in modo casuale o uniforme; al contrario, tendono a concentrare le loro letture e scritture su una frazione relativamente piccola e ristretta di pagine in ogni specifica fase della loro esecuzione. Ad esempio, un ciclo for continuerà a richiamare sempre le stesse istruzioni e le stesse variabili per migliaia di iterazioni prima di passare ad altro.

Questo specifico sottoinsieme di pagine attivamente referenziate in un dato istante prende il nome di Working Set (o insieme di lavoro). Finché l’intero working set del processo riesce a risiedere fisicamente in memoria, il programma verrà eseguito in modo efficiente. Ma cosa succede se la RAM è troppo piccola o troppo frammentata per contenerlo tutto? Il processo inizierà a scartare pagine che gli serviranno di nuovo pochissimi millisecondi dopo, generando un page fault ogni poche istruzioni. Questa condizione catastrofica di perenne blocco e caricamento prende il nome di Thrashing. Quando un sistema entra in thrashing, l’intero computer rallenta fino a bloccarsi, poiché la CPU spende più tempo a gestire i page fault che a eseguire calcoli utili.

Per scongiurare il thrashing, i sistemi operativi moderni adottano il “modello working set”. L’obiettivo è tenere traccia attivamente del working set di ogni processo e assicurarsi che questo sia interamente pre-caricato in memoria prima di consentirne l’esecuzione. Questa tecnica di caricamento anticipato prende il nome di Prepaginazione (prepaging) e abbatte drasticamente il numero di page fault a runtime.

L’Algoritmo di Sostituzione basato sul Working Set

Per tradurre questa teoria in un algoritmo pratico, il sistema operativo deve definire in modo misurabile cos’è il working set. Invece di contare gli ultimi “k” riferimenti alla memoria (metodo teorico impossibile da tracciare), si utilizza il Tempo virtuale attuale, ovvero la quantità di tempo di CPU effettivamente consumata da quel processo dal momento del suo avvio. Si stabilisce poi una determinata soglia temporale massima, indicata con $τ$ .

Tempo virtuale attuale

l tempo virtuale attuale (o current virtual time) di un processo rappresenta la quantità esatta di tempo di CPU che quello specifico processo ha effettivamente consumato dal momento in cui è stato avviato.

A differenza del tempo reale (quello del mondo fisico scandito dall’orologio del computer), il tempo virtuale di un processo avanza solo ed esclusivamente quando il processo si trova in esecuzione attiva sulla CPU. Se il sistema operativo decide di sospendere il processo, ad esempio per metterlo in attesa del completamento di un’operazione di I/O o per dare spazio a un altro programma, il suo tempo virtuale si “congela” istantaneamente, per poi riprendere a scorrere non appena il processo torna in esecuzione.

Quando si verifica un page fault, l’algoritmo deve scansionare la tabella delle pagine alla ricerca di una vittima al di fuori del working set. Analizzando ogni pagina, il sistema controlla prima di tutto il Bit R (Referenziato):

Se R = 1: La pagina è stata usata di recente, quindi fa indiscutibilmente parte del working set. Non può essere rimossa. Il sistema operativo si limita ad aggiornare il suo “tempo di ultimo utilizzo” scrivendovi il tempo virtuale attuale.
Se R = 0: La pagina non è stata usata nell’ultimo ciclo. Per capire se sia davvero “vecchia”, l’algoritmo calcola la sua età (sottraendo il tempo di ultimo utilizzo dal tempo virtuale attuale) e la confronta con la soglia $τ$ .
- Se l’età è maggiore di $τ$ : La pagina è matematicamente uscita dal working set. Viene scelta come vittima e rimossa istantaneamente.
- Se l’età è minore o uguale a $τ$ : La pagina si è “salvata” per un pelo; è temporaneamente inattiva ma appartiene ancora al working set. L’algoritmo non la rimuove, ma ne prende nota nel caso in cui non si trovi nient’altro di meglio.

Se, terminata l’ispezione di tutta la tabella, non viene trovata nessuna pagina con età maggiore di $τ$ , significa che tutto ciò che è in memoria fa parte del working set. A questo punto, costretto a liberare spazio, il sistema operativo rimuoverà la pagina con R = 0 che risulta avere l’età in assoluto maggiore tra quelle presenti. Se persino questo tentativo fallisce (perché tutte le pagine hanno miracolosamente R = 1), sceglierà a caso una pagina pulita da sacrificare.

Confronti prestazionali dei vari algoritmi di sostituzione delle pagine

Per valutare e confrontare oggettivamente l’efficienza dei vari algoritmi di sostituzione delle pagine, si utilizza come metrica fondamentale il numero di page fault generati. Le valutazioni standard vengono effettuate simulando una memoria RAM limitata, ad esempio con 3 frame disponibili , e sottoponendo il sistema a una specifica sequenza compatta di accessi in memoria (come la stringa 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1). In queste sequenze di test, le ripetizioni immediate dello stesso numero vengono omesse poiché non influenzano il verificarsi dei page fault.

Valutazione dei Modelli Base

Sottoponendo la sequenza di riferimento ai tre algoritmi principali, emergono chiare differenze prestazionali: Il modello OPT (Ottimale) funge da termine di paragone assoluto. Genera il minimo storico di soli 9 page fault. Resta tuttavia un algoritmo puramente teorico, poiché per prendere le sue decisioni necessita di informazioni impossibili da ottenere sui riferimenti futuri a breve termine. (ogni quadrato grigio indica un page fault, in alto troviamo le pagine richieste, e in basso dentro i quadratini quelle che ci sono in memoria) Passando alle implementazioni reali, l’algoritmo FIFO si dimostra molto meno efficiente, registrando ben 15 page fault Questo algoritmo soffre del problema noto come anomalia di Belady. L’algoritmo LRU (Least-Recently Used) invece si posiziona nel mezzo registrando 12 page fault. Oltre alle buone prestazioni, inoltre quest’ultimo è immune a l’anomalia di Belady.

Anomalia di Belady e Proprietà di Inclusione

Testando determinati algoritmi, i progettisti si sono scontrati con un fenomeno matematico imprevisto. Anomalia di Belady: È un’anomalia controintuitiva che associa un inaspettato aumento dei page fault a un aumento della memoria RAM fisica disponibile. Questa anomalia si verifica solo di fronte a specifiche sequenze di accesso. Ad esempio, sottoponendo a un sistema la sequenza $[1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]$ , si può osservare un peggioramento delle prestazioni passando da 3 a 4 frame di memoria. L’algoritmo LRU non presenta questa anomalia perché il suo modello matematico soddisfa un requisito stringente.

Proprietà di Inclusione: È una proprietà matematica secondo cui, in ogni istante di tempo $t$ e con una memoria di $n$ frame, l’insieme dei frame caricati è sempre un sottoinsieme di quelli che verrebbero caricati avendo a disposizione $n + 1$ frame. In formula: $B_{t} (n) \subseteq B_{t} (n + 1)$ . Qualsiasi algoritmo che rispetti questa proprietà è matematicamente immune all’anomalia di Belady.

Comportamento degli algoritmi derivati

Comprendere l’anomalia di Belady e la proprietà di inclusione permette di classificare anche l’efficienza e i difetti di tutti gli algoritmi derivati impiegati nei sistemi operativi reali: Tutti gli algoritmi che si basano sul principio temporale del FIFO, ovvero Seconda Chance, Clock e anche la rozza approssimazione NRU, soffrono dell’anomalia di Belady e possono peggiorare le loro prestazioni all’aumentare della memoria. Al contrario, gli algoritmi che nascono per approssimare l’LRU, ovvero NFU e Aging, ereditano e godono della proprietà di inclusione, risultando stabili e sicuri. In particolare, l’Aging si distingue come una buona approssimazione dell’LRU, vantando anche un’implementazione software altamente efficiente.

Problemi di progettazione dei sistemi di paginazione

Politiche di Allocazione: Globali e Locali a Confronto

Nei paragrafi precedenti abbiamo analizzato gli algoritmi che scelgono quale pagina sostituire al momento di un page fault. Tuttavia, in un sistema multiprogrammato, i progettisti devono affrontare un’altra questione fondamentale: come dovrebbe essere ripartita la memoria fisica totale fra tutti i processi concorrenti in esecuzione? Per comprendere il problema, possiamo fare riferimento alla Figura 3.22 Immaginiamo una situazione in cui i processi A, B e C si trovano in memoria. A un certo punto, il processo A genera un page fault. L’algoritmo di sostituzione deve ora prendere una decisione cruciale: cercare la pagina da sfrattare considerando solo l’insieme di pagine attualmente allocate ad A, oppure valutare tutte le pagine presenti nell’intera memoria, a prescindere da chi le stia usando?

Algoritmi di Sostituzione Locale: Se l’algoritmo decide di confinare la sua ricerca alle sole pagine del processo A (scegliendo, ad esempio, la sua pagina più vecchia per fare spazio a quella nuova), stiamo applicando un Algoritmo di sostituzione locale. Questo approccio assegna a ogni processo una frazione rigida e fissa di memoria. Tuttavia, presenta dei gravi difetti prestazionali legati all’imprevedibilità dei programmi. Se il working set di un processo si restringe durante l’esecuzione, l’algoritmo locale continuerà a tenergli assegnata la stessa quantità di memoria, sprecando preziosi frame che rimarranno inutilizzati. Al contrario, se il working set del processo aumenta improvvisamente, l’algoritmo lo costringerà a sostituire continuamente le proprie pagine in un circolo vizioso, portandolo al thrashing pur in presenza di frame liberi e disponibili nel resto della memoria.
Algoritmi di Sostituzione Globale: Se invece l’algoritmo, al verificarsi dell’errore di A, valuta tutte le pagine del sistema e decide, ad esempio, di sottrarre la pagina meno utilizzata in assoluto (magari appartenente al processo B) per assegnarla ad A, in questo caso, il numero di frame assegnato a ciascun processo varia dinamicamente nel tempo.

In generale, gli algoritmi globali funzionano nettamente meglio di quelli locali proprio perché riescono ad assecondare le naturali variazioni di dimensione dei working set. Scegliendo una politica globale, il sistema deve però stabilire quanti frame assegnare all’avvio. Dividere la memoria in parti uguali ha poco senso, perché tratterebbe allo stesso modo un piccolo processo da 10 KB e uno enorme da 300 KB. L’approccio più saggio è avviare ogni processo assegnandogli un numero di pagine strettamente proporzionale alla sua dimensione totale (garantendo comunque un limite minimo a tutti per poter funzionare), per poi aggiornare questa assegnazione dinamicamente mentre i programmi girano.

L’Algoritmo Page Fault Frequency (PFF)

Il metodo più efficace per gestire questa “assegnazione dinamica” dei frame è l’algoritmo Page Fault Frequency (PFF), il cui grafico di funzionamento è illustrato nella Figura 3.23 È importante precisare che il PFF non sceglie quale pagina sostituire (quello è compito di algoritmi come Clock o WSClock), ma indica solo quando è il caso di aumentare o diminuire il numero totale di pagine allocate a un determinato processo. Il funzionamento si basa sulla misurazione costante della frequenza degli errori, calcolando i page fault per secondo di ogni processo (spesso calcolati facendo una media tra i page fault del secondo appena trascorso e la media attuale di esecuzione, divisa per due). Il sistema operativo stabilisce dei limiti di accettabilità per questa frequenza:

Limite Superiore (Linea tratteggiata A): Se la frequenza di paginazione di un processo supera questa soglia, significa che il tasso di errore è troppo alto. Il processo è “in sofferenza” per mancanza di spazio, quindi il sistema interviene aumentandogli la quota di frame assegnati.
Limite Inferiore (Linea tratteggiata B): Se la frequenza di paginazione scende al di sotto di questa soglia, significa che il processo sta girando con un numero di errori così basso da far supporre che abbia troppa memoria a disposizione rispetto al necessario. In questo caso, il sistema operativo può tranquillamente sottrargli dei frame per riassegnarli a processi più bisognosi. In questo modo, il PFF lavora costantemente in background cercando di mantenere la frequenza di paginazione di tutti i processi all’interno di una fascia sicura e ottimale.

Politica di Pulitura e Gestione dei Frame Liberi

Il meccanismo di risoluzione dei page fault è davvero efficiente e rapido solo se ci sono frame liberi sempre disponibili in memoria. Quando i frame scarseggiano e si è costretti a rimuovere una pagina, la gestione diventa lenta, soprattutto se la pagina è “sporca” (modificata), poiché richiede una preventiva e pesante scrittura su disco. Per evitare questo collo di bottiglia, sistemi operativi come Linux e Windows utilizzano il paging daemon, un processo di servizio che monitora costantemente l’occupazione globale della RAM. Questo daemon agisce d’anticipo: individua le pagine che presume non saranno utili nel breve periodo, le seleziona e le rende disponibili, mantenendo così un pool di frame liberi sempre pronti all’uso. La caratteristica chiave di questo pool è che i dati non vengono cancellati subito, lasciando aperta la possibilità di un ripescaggio istantaneo: se un processo richiede quella pagina prima che il frame venga effettivamente sovrascritto, il sistema la recupera immediatamente senza dover scatenare un vero e proprio page fault, riducendo drasticamente l’overhead generale.

Controllo del Carico

Se i working set combinati superano la capacità di memoria, il PFF indicherà che tutti i processi necessitano di memoria, portando inesorabilmente al thrashing. L’unica soluzione è lo Swapping, scaricando quanti più processi sul disco. La scelta di chi scaricare dipende dal grado di multiprogrammazione e dalle caratteristiche del processo (I/O bound o CPU bound).

Dimensione delle Pagine

La scelta della dimensione della pagina di base è importante. Al crescere o decrescere della dimensione delle pagine, otteniamo effetti positivi e negativi. Pro delle pagine più grandi

Tabella delle pagine più piccole. Il numero di record della tabella delle pagine è pari al numero di pagine. Il numero di pagine, a parità di memoria, è inversamente proporzionale alla dimensione delle pagine.
Migliore efficienza nel trasferimento I/O. Utilizzando pagine più grandi, un input/output potrà essere effettuato su pagine più grandi, e quindi un numero minore di pagine a cui accedere. Questi vantaggi si sentono di più all’interno di memorie di tipo elettromeccanico.
Minori page fault (e conseguente minor overhead). Pagine più grosse $\Rightarrow$ meno pagine $\Rightarrow$ meno page fault. Non sempre ne vale la pena, ma è un fatto da tenere in considerazione.

Pro delle pagine più piccole

Minore frammentazione interna. Pagine più grandi causano più spreco. Pagine
Migliore risoluzione nel definire il working set. Meno memoria sprecata! Le approssimazioni saranno più precise. Le pagine sono di dimensione fissa: blocchi più piccoli permettono di rispondere alle nostre esigenze in maniera migliore.

I pro di uno, sono i contro dell’altro. Per bilanciare gli svantaggi, i sistemi operativi utilizzano a volte pagine di dimensioni diverse per le diverse parti del sistema: per esempio, pagine grandi per il kernel e più piccole per | processi utente.

Pagine Condivise e Gestione della Cache

Fino ad ora abbiamo immaginato che ogni processo avesse le sue pagine isolate. Ma cosa succede se abbiamo più istanze dello stesso programma in esecuzione? Entra in gioco un’ottimizzazione del sistema operativo mirata a risparmiare memoria: le pagine condivise. Invece di caricare copie identiche, il sistema porta in RAM una sola copia fisica del codice eseguibile condiviso e fa puntare le tabelle delle pagine dei vari processi esattamente allo stesso frame. Questo funziona perfettamente perché il codice è mantenuto in modalità sola lettura. Le pagine condivise si possono usare anche come strumento di comunicazione inter-processo (IPC) in lettura/scrittura, a patto di utilizzare i classici meccanismi di sincronizzazione per buffer condivisi, come i MUTEX. L’uso di questa memoria condivisa crea però delle sfide architetturali:

Il problema dell’aliasing in Cache: Nelle cache “pre-MMU” basate su indirizzi virtuali, i processi vedono la stessa risorsa fisica usando indirizzi (e chiavi) virtuali diversi. Questo genera falsi cache miss e seri problemi di sincronizzazione, dato che la cache rischia di caricare la stessa pagina in due voci distinte.
La soluzione ibrida: Si utilizzano cache che effettuano ricerche tramite indirizzi virtuali ma associate a tag fisici (sfruttando l’offset). Questa ricerca “preliminare” avviene in parallelo alla traduzione effettuata dalla MMU, permettendo di scremare le voci rapidamente senza disabilitare la cache.
Tabelle Invertite: Le pagine condivise rendono le tabelle delle pagine invertite un incubo da gestire. Avendo un solo record per ogni frame fisico, risulta impossibile associarvi due indirizzi virtuali diversi senza dover modificare continuamente il record a ogni page fault o context switch.

Copy-on-Write (COW) e Zero-fill-on-demand

Condividere le pagine è una tecnica eccellente per risparmiare memoria RAM, ma sorge un problema quando un processo necessita di modificare i propri dati. Prendendo in esame una chiamata fork(), i processi figli vengono creati identici al padre e, per ottimizzare, le loro tabelle delle pagine punteranno inizialmente agli stessi frame. L’obiettivo è mantenere questa condivisione il più a lungo possibile, intervenendo unicamente in caso di scrittura per non corrompere la memoria altrui.

Il meccanismo del Copy-on-write gestisce questa criticità in modo elegante: il sistema operativo, di default, imposta tutte le pagine condivise come read-only (portando il bit di scrittura a 0). Quando un processo tenta di effettuare una scrittura, la MMU intercetta l’operazione non consentita ma, invece di generare un errore fatale, invoca una specifica procedura del sistema operativo. A questo punto, l’OS crea una copia fisica identica della singola pagina interessata, assegnandola in esclusiva al processo che ha richiesto la modifica. Infine, il sistema aggiorna i puntatori nelle rispettive tabelle delle pagine e ripristina il bit di scrittura a 1 per entrambe le nuove copie, rendendole di fatto indipendenti.

Una logica simile è alla base dello Zero-fill-on-demand, utilizzato quando un processo richiede nuova memoria per l’heap tramite chiamate come sbrk(). Anziché allocare e pulire immediatamente dei frame reali, il sistema operativo illude il processo associando temporaneamente le nuove pagine a una read-only static zero page, ovvero un frame speciale pre-azzerato e privo di informazioni. Soltanto nel momento in cui il processo tenterà per la prima volta di utilizzare (e quindi scrivere su) queste pagine, si innescherà il meccanismo del copy-on-write: il sistema operativo pulirà dei frame reali on-demand, li assegnerà al processo e aggiornerà i puntatori nella tabella delle pagine.

Librerie Condivise, File Mappati e Layout della Memoria

Quando un programma ha bisogno di usare funzioni appartenenti a librerie esterne, può inglobarle in due modi molto diversi:

Linking statico (L’approccio pesante): Tutto il codice binario della libreria precompilata viene inserito fisicamente dentro l’eseguibile nei posti in cui le funzioni vengono chiamate. Il programma ha tutto a disposizione subito, ma l’eseguibile finisce per occupare molto spazio.
Linking dinamico (L’approccio smart): Nell’eseguibile risiede solo il sorgente. A run-time, alla prima chiamata, la libreria viene portata tutta in RAM e messa a disposizione del processo. Se altri processi necessitano della stessa libreria, non ne viene creata una copia nuova, ma tutti si agganceranno a quell’unica copia condivisa.

Un’evoluzione ancora più prestante per la condivisione è l’utilizzo dei file mappati. La mappatura in memoria è un meccanismo che permette di associare un’area della memoria virtuale di un processo al contenuto di un file memorizzato sul disco, permettendo così di accedere a quest’ultimo come se fosse parte della memoria RAM. Questa tecnica consente un accesso rapido ed efficiente ai dati (successivamente a un page fault), migliorando le prestazioni di applicazioni che gestiscono file di grandi dimensioni e facilitando la comunicazione tra processi che condividono memoria.

Allocazione della Memoria per il Kernel

Il sistema operativo ha bisogno di spazio in RAM per ospitare le proprie strutture dati di supporto (come PCB, semafori, code, ecc.). A differenza della memoria utente che viene paginata, il Kernel sbatte contro un ostacolo fisico: moduli che dialogano direttamente con l’hardware o con il sistema DMA necessitano obbligatoriamente di indirizzi fisici e frame fisicamente contigui.

Per allocare questa memoria complessa mirando a una frammentazione interna nulla, Linux impiega lo slab allocator. Questo modello si basa su due elementi:

Slab: È una sequenza di frame fisicamente adiacenti (un pezzo fisico di memoria contiguo).
Cache: È un insieme di slab. Il grande vantaggio è che ogni cache è fortemente specializzata per ospitare un singolo tipo di struttura dati: ad esempio, avremo una cache esclusivamente per oggetti da 3 KB e un’altra per quelli da 7 KB.

L’efficienza è massima perché l’OS sceglie sempre di allocare slab di dimensione perfettamente multipla allo spazio richiesto. Così facendo, la frammentazione esterna si annulla totalmente (tutto lo spazio che non serve al kernel viene rimbalzato alla paginazione classica), e l’operare direttamente con indirizzi fisici garantisce un overhead minimo.

Capitolo 4

File System

Introduzione al File System

I file, le directory e il file system sono astrazioni offerte dal sistema operativo. La gestione di grandi quantità d’informazioni, in maniera persistente e condivisa tra processi, è l’obiettivo che ci poniamo durante la progettazione di un sistema operativo.

Il File system

Il termine file system viene spesso utilizzato per indicare due cose:

L’interezza dei file in memoria (Cancellare l’intero file system → Cancellare tutti i file in memoria).
L’astrazione di gestione dei file (Il file system di UNIX è diverso da quello di Windows).

Quando useremo il termine file system, ci riferiremo sempre all’astrazione di gestione dei file. Ogni file system si differenzia per i propri dettagli di gestione e di implementazione. Tra questi dettagli di gestione, individuiamo:

Nomenclatura. Dimensione e formattazione dei nomi (MS-DOS: 7 caratteri + 3 per l’estensione), case sensitivity (UNIX-based OS - case sensitive, Windows - case insensitive).
Tipi di file. Tra questi, nei sistemi operativi UNIX, abbiamo i device file. Rappresentano un dispositivo che appare nel file system, e tramite cui è possibile effettuare operazioni di input/output. Una schea audio, ad esempio, apparirà come un file nel file system.
Tipi di accesso. Sequenziale o diretto. Nel primo, il file pointer viene portato avanti ad ogni operazione di lettura e scrittura. Nel secondo, il file pointer è completamente svincolato. Al giorno d’oggi l’accesso diretto è lo standard, e permette di emulare anche un accesso sequenziale.
Metadati e attributi. Tra cui nome, time-stamp (data creazione - ultima modifica), permessi di modifica, autore del file e maschere di permessi, tramite cui è possibile stabilire accesso protetto ad un file. Ogni utente potrebbe avere il proprio spazio nel file system.
Operazioni supportate sui file. Consentire a due processi di leggere e scrivere sullo stesso file, ci porta alle stesse condizioni delle race condition. Il sistema operativo gestisce l’accesso condiviso ai file tramite dei lock. I lock possono essere:
- Condivisi o Esclusivi. Sono due tipologie di lock ben distine. I lock condivisi consentono a più processi di accedere allo stesso file, e vengono utilizzati quando più processi vogliono leggere dallo stesso file. I lock esclusivi garantiscono accesso esclusivo ad un processo su quel file. Questo lock preclude l’accesso a qualsiasi altro processo, e viene usato solitamente per operazioni di scrittura.
- Mandatory o Advisory. Con la strategia mandatory, i processi sono obbligati a rispettare i lock tramite l’intervento diretto del sistema operativo, che blocca il processo che ha intenzione di accedere al file lockato. Con la strategia advisory il sistema operativo informa il processo se è riuscito o meno ad ottenere un lock sul file che ha intenzione di usare. Sconsiglia al processo di operare sul file trovato bloccato, ma non gli vieta di farlo.
Strutture dati per la gestione dei file. Esistono tabelle globali per visualizzare i file in uso.

Struttura di un File system

Il file system risiede sopra una partizione di memoria. Una partizione può ospitare più file system. La gestione delle partizioni non concerne quindi il file system. Il partizionamento può essere gestito in due modi principali.

Master Boot Record

È un metodo storico. Il master boot record contiene quattro voci prestabilite, che tracciano l’inizio e la fine delle partizioni di memoria (esiste quindi un cap limite di massimo 4 partizioni di memoria). Il disco ha quindi in memoria:

Al più quattro partizioni.
La tabella delle partizioni.
Il boot record. È il primo blocco della memoria, i primi 512 byte, contenente codice di avvio della macchina. Carica il sistema operativo presente nella rispettiva partizione.

All’interno di ogni partizione, individuiamo:

Boot block. Una volta sfruttato per parte del codice di avvio di ciascuno dei sistemi operativi delle partizioni. Il suo utilizzo, che ne spiegava il nome, è ormai deprecato. Rimane ormai inutilizzato, vuoto.
Superblock. Contiene dei metadati relativi alla partizioni: specifica il tipo di file system, la dimensione dei cluster. Il resto della partizione sarà gestita in cluster.
Free space management.
I-nodes.
Rood directory. La radice della directory del file system.
File e directories.

GUID Partition Table

È un layout moderno alternativo, preferito al MBR. Una partizione prestabilita, la partizione EFI, ha un compito dedicato per l’avvio del sistema. La partizione EFI è formattata in FAT e all’interno del file system esistono vari file di configurazione e gli eseguibili EFI da lanciare in un ambiente minimale. Questi binari si occuperanno dell’avvio dei sistemi operativi.

Implementazione dei file

Definire le strategie relative all’implementazione dei file, è fondamentale per capire il funzionamento del file system.

Strategie principali

Ogni oggetto file ha una dimensione specifica in blocchi. Lo spazio richiesto in blocchi è il risultato di un arrotondamento: a ogni file, coinciderà uno spreco (frammentazione interna) causata dalla differenza tra la dimensione di un blocco e la taglia del file.

Allocazione contigua. I blocchi relativi ad un file devono essere contigui. Permette l’accesso diretto ad un blocco in tempo $O (1)$ : una sola lettura, sapendo già indirizzo e offset. Sfortunatamente, l’allocazione contigua è ingestibile in situazioni di crescita dinamica dei file. Il vincolo di contiguità è troppo stretto: cosa facciamo se il prossimo blocco è occupato? Spostiamo tutti i blocchi del file da qualche altra parte? Troppo oneroso. Il metodo è utilizzabile solo nei file system di sola lettura.

Allocazione con liste collegate. Detta anche allocazione concatenata. Ogni blocco del file conterrà un indirizzo (di un numero di byte commisurato alla memoria della partizione), che farà riferimento al prossimo blocco del file. Questa strategia presenta un problema: con $n$ blocchi dedicati a un file, la ricerca di un qualsiasi blocco richiederà $O (n)$ accessi in memoria.

FAT - File Allocation Table. I blocchi non devono essere contigui. In più, in memoria è presente una tabella dei file allocati: ha un record per ogni blocco. Ecco come funziona:
- La FAT ha un record per ogni blocco della partizione.
- Nel record del blocco $i$ , è contenuto l’indice del prossimo blocco, rispetto al file di $i$ .
- Se è presente l’indice $- 1$ , il blocco sarà l’ultimo del file di appartenenza.
- I record vuoti coincidono a blocchi inutilizzati. Scopriremo poi che altri file system, come gli i-node, implementano strutture per tracciare i blocchi inutilizzati. Per i file system FAT non è necessario! Le informazioni necessarie sono già presenti nella FAT.

Il FAT è di fondamentale importanza per il file system: il file system non esiste senza questa tabella! Notiamo inoltre che riprende gli stessi presupposti dell’allocazione con liste collegate (non contiguità, riferimenti tra blocchi). Per trovare un blocco qualsiasi di un file con $n$ blocchi, sono richiesti $O (n)$ accessi all’interno della tabella. Supponendo però che l’intera FAT sia caricata in RAM, la ricerca all’interno della tabella richiedera $O (n)$ passaggi meno computazionalmente onerosi, rispetto agli $O (n)$ accessi in memoria delle liste collegate.

Allocazione con i-node, index-node, nodi indice. I metadati di un file vengono scritti all’interno della tabella i-node (ad eccezione del nome, che è contenuto nella directory del file). Tra questi metadati abbiamo informazioni releative allo UID e il GUID dell’owner, la dimensione del file e vari timestamps. Tra questi, alcuni sono detti data block pointers: questi, sono puntatori a blocchi di memoria.

Questi indirizzi, possono puntare a

Un blocco diretto: è un blocco effettivo del file.
Un blocco indiretto singolo: questo, punta a $n$ blocchi del disco.
Un blocco indiretto doppio: questo, punta a $n$ blocchi indiretti singoli.
Un blocco indiretto triplo: questo, punta a $n$ blocchi indiretti doppi.

Nel file system Unix un i-node contiene quindici puntatori:

10 puntatori a blocco diretto. Uno a a uno.
Un puntatore a blocco indiretto singolo. Per arrivare ad un blocco, sono richiesti al più due accessi in memoria. Uno a $n$ .
Un puntatore a blocco indiretto doppio. Per arrivare ad un blocco, sono richiesti al più tre accessi in memoria. Uno a $n^{2}$ .
Un puntatore a blocco indiretto triplo. Per leggere un blocco, sono richiesti quattro accessi in memoria. Uno a $n^{3}$ .

Questra struttura fornisce un upper bound alla ricerca di un blocco di un qualsiasi file, a partire da qualsiasi i-node. Inoltre, a differenza della FAT, non c’è l’esigenza di portare in memoria l’intera tabella: bensì, i blocchi diretti, indiretti singoli, doppi e tripli, verranno portati in memoria RAM solo on-demand. I sistemi moderni prediligono gli i-node, anche se le chiavette usano la FAT32.

Implementazione delle directory

Dove vengono inseriti i metadati e attributi?

In un file system FAT, i metadati sono contenuti all’interno della directory del file.
In un file system con i-node, i metadati sono contenuti all’interno della tabella degli i-node, tranne il nome! Il nome sta nella directory.

Tutti gli attributi hanno una lunghezza fissata, ad eccezione dei nomi. Nei sistemi operativi moderni, dove il nome può raggiungere centinaia di caratteri e codifiche UNICODE più dispendiose, è fondamentale conservare in maniera opportuna il nome del file.

Come gestire in maniera opportuna i nomi

Le strategie in questione variano relativamente poco tra i file system FAT e con i-node.

Strategia 1 - lunghezza variabile. Il primo campo del file stabilisce la lunghezza in byte dell’entry, (o del nome, negli i-node). L’unico valore di dimensione variabile è il nome: ponendo il nome come ultimo attributo del file, diventa possibile stabilire quando inizia e quando finisce il nome. A fine nome, è presente un carattere di terminazione.
Strategia 2 - heap, suddivisione tra parte fissata e variabile. Le parti di dimensione fissa dei record, vengono unificate in una parte di memoria. In questo modo, si evita totalmente la frammentazione esterna. Tra gli attributi, si ha un puntatore al nome del file. Le parti variabili (i nomi) si trovano in una sezione a parte, chiamata heap. Un’accozzaglia di nomi, separati da carattere di terminazione. Separare parte variabile e fissa, permette di facilitarne la gestione.

Condivisione di un File System tra utenti

Immaginiamo di voler condividere un file tra due o più utenti.

Alcune idee implementative

Duplicando le FAT. L’idea potrebbe eseere quella di duplicare le liste con i riferimenti ai blocchi ottenendo liste distinte. Come possiamo mantenere coerenti le modifiche al contenuto e ai metadati? Con un’append, si aggiorna la dimensione in byte: l’aggiornamento dei metadati diventa un problema.
Usando i-node, gli hard link. All’interno di un i-node, inseriamo un contatore che tiene traccia degli utenti che hanno accesso al file. Possiamo mettere riferimenti diversi allo stesso file. Non ci sarà l’esigenza di aggiornare i metadati, in quanto questi sono situati proprio dentro l’i-node. Il nome può infatti essere diverso tra i vari utenti!
Soft link, o link simbolici. Viene creato un i-node per un nuovo oggetto. Questo oggetto conterrà il path al file di cui vogliamo creare il soft-link.

Soft e Hard link a confronto

Nei sistemi UNIX sono supportati entrambi i tipi di link.

Creare directory condivise. È (teoricamente) possibile con entrambi i tipi di link.
Capire qual è il riferimento originale. Con la tecnica degli hard link, il riferimento originale è indistinguibile dall’hard link creato successivamente. Ciò potrebbe modificare la struttura ad albero del file system, creando un grafo ciclico, rischiando di creare loop infiniti. Per questo motivo, UNIX vieta gli hard link a directory.
Cross file-system links. Impossibili tramite gli hard link. UNIX gestisce più file systems agganciandoli all’albero del file system originale. In questo modo, è sempre possibile trovare un cammino dalla root a qualsiasi file di qualsiasi file system. Windows usa un approccio a dischi e file system separati.

Perché non è possibile avere collegamenti tra file systems tramite hard link? L’enumerazione degli i-node è relativa ad ogni file system. È ad esempio impossibile creare un hard link tra la directory /home e la directory /tmp. In Unix, the /tmp directory will often be a separate disk partition. In systems with magnetic hard disk drives, performance (overall system IOPS) will increase if disk-head movements from regular disk I/O are separated from the access to the temporary directory.

Gestione dei blocchi liberi

Anche nel caso dei file system, è fondamentale il tracciamento dei blocchi liberi.

Alcune strategie

Usare una bitmap. Relativamente piccola, ha una dimensione inversamente proporzionale alla dimensione dei blocchi e direttamente proporzionale al numero di blocchi. È conservata nel disco, ma può essere portata in RAM a fine di velocizzarne l’utilizzo.
Usare liste concatenate. Un’enorme lista concatenata di blocchi contenenti indirizzi a blocchi liberi. Richiede più spazio, ma la struttura è unificata, sfrutta blocchi liberi in memoria. È interessante osservare come la lista dei blocchi liberi si accorcia quando vengono utilizzati blocchi. Un blocco viene sottratto? La lista viene accorciata, liberando spazio sul disco.

Un’ulteriore ottimizzazione potrebbe essere inserire un contatore ad un dato indirizzo, per indicare il numero di blocchi contigui successivi.

La FAT che approccio usa?

La FAT ha già un record per ogni blocco. Dando un valore specifico al numero del blocco non allocato (magari un -2 o uno 0), si possono marcare facilmente i blocchi liberi. Entrambi i meccanismi sarebbero ridondanti.

E i-node?

Usano la strategia bitmap. Questa è inserita in uno spazio dedicato (presente in ogni partizione) chiamato free space management. Contiene una bitmap per i blocchi liberi, e una bitmap per gli i-node liberi.

Controlli di consistenza

Crash di sistema e problemi con l’hardware possono causare inconsistenze nel file system. Lavorare su un file system con delle incoerenze, potrebbe creare problematiche di vario tipo: scrittura consentita su blocchi che sono in realtà allocati per altri file. Parleremo quindi di strategie che permettono di individuare delle incongruenze.

Flag

Quando un file system viene montato, un flag relativo a questo file system viene settato a 1. Quando viene smontato correttamente (e in fase di shutdown) viene settato a 0. Un malfunzionamento lascerà il flag a 1, e quando verrà rimontato, alcune utility avvieranno dei controlli di consistenza.

Controlli di consistenza

Tra i principali controlli di consistenza, abbiamo quelli relativi all’occupazione dei blocchi, e quelli relativi al numero di riferimenti agli i-node.

Sull’occupazione dei blocchi

Si confronta il contenuto della bitmap con l’occupazione effettiva dei blocchi.

Dati consistenti.
Blocco 2 sia libero che occupato.
Blocco 5 usato da più file. Qui, ci scappa il morto!

Sul numero di riferimenti agli i-node

Dentro ogni i-node è presente un campo contenente il numero di riferimenti ad esso. Il controllo di consistenza scorrerà l’intero albero del file system tenendo conto dei riferimenti di ogni i-node.

Se il numero di volte in cui un i-node è stato individuato nel file system è zero, il contatore deve essere a zero, e quindi l’i-node non è ancora stato allocato.
Altrimenti, il numero di riferimenti deve coincidere con quello contato.

Journaling

L’idea è la seguente: un file system qualsiasi può essere corredato con un journal, un log. È una struttura dati che può essere mantenuta nella stessa o in un’altra partizione. Il log tiene conto di tutte le operazioni sui meta-dati (e strutture dati, quali i-node, bitmap e così via), tiene conto delle macro operazioni su tutti i file. Il journal sta sul disco, e il sistema operativo verifica che sia aggiornato correttamente. Quando una sequenza di istruzioni è stata conclusa con successo, questa viene totalmente cancellata. Se la sequenza di istruzioni non è stata conclusa, e il flag relativo alle anomalie è stato trovato a 1, tutti i passi nel log vengono rieffettuati.

Il rischio è che alcune operazioni vengano effettuate più volte (una pre e una post crash). Per questo motivo, le operazioni devono essere idempotenti e non creare problemi se reiterati.

L’obiettivo del journaling è creare un log delle operazioni sui meta-dati, per preservare lo stato dei file system nel caso di crash.

Un esempio di operazione non idempotente: aggiungi questi blocchi alla lista dei blocchi liberi.
Un esempio di operazione idempotente: aggiungi questi blocchi alla lista dei blocchi liberi, se non sono già presenti.

Non tutte le operazioni sui meta-dati sono inserite nel journal. Memorizzare cambiamenti relativi al contenuto sarebbe molto utile e sicuro, ma anche tanto tanto dispendioso. Garantire l’integrità dei metadati (e quindi delle directory e della struttura del file system) è più importante per non propagare i danni all’intera struttura.

I file system moderni

In una situazione di crash, i file system moderni, limitano i controlli di integrità ai blocchi citati all’interno del journal. Questo velocizza di molto il ripristino della coerenza. È inutile fare un controllo a tappeto.

Cache del disco

Per migliorare le prestazioni dei dischi si usa una cacne del disco. Fa da ponte tra una memoria veloce ma di piccole dimensioni, e una memoria lenta ma di grande dimensioni. La cache del disco contiene i dati che sono stati letti di recente e, in alcuni casi, aree di dati adiacenti a cui è probabile che si acceda in seguito. È una soluzione totalmente software. Un’idea sarebbe quella di utilizzare la stessa strategia LRU, mantenendo un timestamp relativo all’ultimo utilizzo di un blocco.

Struttura basata su tabelle hash.

Con riferimenti a tutti i blocchi presenti nella coda, e in cui individuiamo blocchi least recently used (LRU) e most recently used (MRU). La tabella hash consente accessi a tempo costante.

L’implementazione vede in realtà due liste: una per mantenere l’ordine degli elementi rispetto all’ultimo utilizzo, una per accedere agli elementi dell’hash table.

Free-behind e Read-ahead

Immaginiamo di star gestendo un file in lettura o scrittura sequenziale (in generale, un accesso sequenziale, non casuale): ciò che faremo, sarà leggere blocco per blocco il file.

Free-behind. Effettuata una scrittura sequenziale, si liberano i blocchi precedentemente scritti: raramente immaginiamo di dover leggere gli stessi blocchi.
Read-ahead. Si ottimizza il processo ad accesso sequenziale, leggendo non solo i blocchi richiesti, ma anche quelli successivi.

Con enormi vantaggi sui dischi elettromeccanici.

Altro da sapere

La cache del disco può essere inibita.

Che file system usano i nostri sistemi operativi?

Windows

exFAT. Sui dischi rimovibili
NTFS. Sui dischi fissi. Supporta journaling, cifratura, compressione (trasparente, prima dell’effettiva scrittura), copia shadow (Copy-on-write sui file. Permette di risparmiare spazio in memoria quando si hanno due copie dello stesso file: fino a quando uno dei due non verrà modificato, la copia sarà solo un riferimento agli stessi blocchi di memoria. I file comuni verranno separati nel momento di una modifica) e dischi multipli (tecniche RAID gestite dal sistema operativo). È un file system moderno e molto complesso.
ReFS, attualmente in sviluppo. Seguendo la falsa riga di BTRFS.

Linux

ext-4. Journaling, allocazione efficiente.
BTRFS. È un file system molto recente. Piuttosto stabile, offre journaling, compressione (trasparente), dischi multipli (con tecniche RAID), checksum dei dati e dei metadati (Per garantire congruenza tra i dati e metadati prima di lettura e scrittura, per evitare di leggere dati danneggiati. Un checksum può tornare falsi negativi), volumi e clonazione (CoW).

MacOS

HFS+ recentemente soppiantato da APFS.

Scheduling del disco

Gestione della coda delle richieste pendenti di I/O su disco. Si può mandare mandare al controller del disco solo una richiesta alla volta. Il nostro obiettivo è massimizzare il numero di richieste in unità di tempo (throughput), minimizzando il tempo medio d’accesso.

Ogni richiesta ha un costo: questo dipende da varie circostanze. Per questo motivo, si possono stabilire delle politiche di selezione per la prossima richiesta da effettuare.

FIFO. Tecnica banale, non premia particolarmente.
Tempo di posizionamento più corto. O Seek-time, metrica che studieremo.
Latenza di rotazione. Il problema di cui parleremo, è chiamato problema dello scheduling del movimento della testina su disco.

Ottimizzare il Seek-time

La lista delle richieste sarà, partendo dal cilindro 53: $98, 183, 37, 122, 14, 124, 65, 67$

Strategia FIFO

First-Come-First-Served. $(98 - 53) + (183 - 98) + (183 - 37) + (122 - 37) + (122 - 14) + (124 - 14) + (124 - 65) + (67 - 65) = 640$

Vengono percorse, in totale, 640 tracce. È un algoritmo semplice (letteralmente nulla da modificare), equo, ma non efficiente.

SSTF Shortest Seek Time First

Si minimizza il tempo di ricerca su disco, di ogni richiesta.

236 tracce. Si ottengono ottime prestazioni, ma non è equo (si rischia starvation, soprattutto di fronte ad un alto numero di richieste in arrivo)

Algoritmo dell’ascensore (o scansione, look)

Mantiene un verso fino all’ultima richiesta in tale direzione. Le richieste sono soddisfatte o da sinistra verso destra, o da destra verso sinistra, fino a quando non ci sono richieste da poter soddisfare nel verso stabilito. 299 tracce, più di SSTF. Garantisce un’upper bound ai tempi di attesa per ogni richiesta (in questo caso, 199 tracce), non rischia starvation, e scansiona in maniera uniforme. Il nome deriva dal fatto che, lo stesso algoritmo, viene usato dagli ascensori.

Scheduling per scansione circolare

Considera le posizioni come collegate in modo circolare. Arrivato a fine disco (ovvero all’ultima richiesta soddisfacibile dal verso corrente), la testina si sposta alla richiesta più lontana dal verso opposto, ignorando qualsiasi richiesta pendente. È uno spostamento molto veloce.

Con questa sorta di effetto pac-man, si abbassa il tempo di attesa medio, in attesa di tante richieste. Il ritorno indietro è molto veloce, minimizzando il tempo di attesa nei casi peggiori.

In situazioni ad alto carico, il sistema circolare è il migliore.
A basso-medio carico, si preferisce SSTF o la scansione standard.

Esempio di esercizio

Supponiamo di avere un disco con 200 tracce (numerate da 0 a 199) la cui velocità di seek è di 1 traccia per $m s$ . All’istante $t = 0$ il sistema operativo sta servendo una richiesta sulla traccia 100 e in coda ci sono già le seguenti richiesto per le tracce (50, 115, 180). Successivamente arrivano altre richieste all’istante $t = 70$ per la traccia 150 e all’istante $t = 130$ per la traccia 90. Si calcoli il tempo di ricerca complessivo (in ms) per servire tutte le richieste secondo la politica LOOK (scansione), Iniziando in ordine ascendente (dalla traccia 0 verso la traccia 199) e trascurando la latenza rotazionale e il tempo di trasferimento. Indicare anche la sequenza di scheduling considerata.

Parallelismo dei dischi (Sistemi RAID)

I sistemi RAID (Redundant Array of Independent Disks - Array Ridondante di dischi indipendenti) offrono una gestione di un’unico disco logico (virtuale) su più dischi fisici. fittizio. Che benefici otteniamo?

Le richieste verso il disco sono pilotate verso il disco virtuale, ma le operazioni di lettura e scrittura verranno effettuate sui dischi effettivi, ovvero tutti i dischi fisici coinvolti. Permette di sfruttare più dischi indipendenti in maniera parallela, con fine ultimo quello di aumentare le prestazioni, e di migliorare la resilienza ai guasti, tramite meccanismi di ricostruzione delle informazioni perse.

Striping

I dati relativi ad un’unità logica (un file, un volume) vengono distribuiti su più dischi: questa procedura è detta striping. Gli stripe sono multipli del blocco, di medio-grandi dimensioni. Le stripe sono distribuite sui vari dischi in maniera casuale.

I sistemi operativi attuali, preferiscono gestire lo striping tramite software. Si ottengono prestazioni simili tramite hardware (da parte del controller dei dischi).

Rischi relativi all’uso di più dischi - maggiore sensibilità?

Usare più dischi fisici per distribuire un volume logico, significa rendere i dati molto sensibili ai guasti di uno dei dischi coinvolti qualsiasi: i sistemi raid aggiungono ridondanza per ottenere migliore affidabilità, ed è possibile contemplare dischi spare con meccanismi di sostituzione automatica.

Aumento di prestazioni

Le richieste al disco virtuale, sono distribuite parallelamente ai dischi effettivi sottostanti. Questi opereranno in parallelo. Supponendo dischi uguali a pari prestazioni, e con porzioni di file uguali, otterremo un boost delle performance di 4 volte.

Guasti

Un guasto su un disco qualsiasi, si propaga sul volume logico RAID: aumentando la ridondanza dei dati, migliora l’affidabilità. Esistono inoltre meccanismi di sostituzione dei dischi tramite dischi di riserva (prima dei guasti non fanno parte del sistema RAID), che vengono ripopolati il prima possibile redistribuendo i dati.

RAID

Redundant Arrays of Inexpensive Disks, noti anche come Redundant Arrays of Indipendent Disks. Esistono vari livelli dei sistemi RAID.

RAID 0 - striping

Effettua striping in modalità round-robin. Ottiene prestazioni ottimali tramite un approccio semplice e con letture di grandi volumi.

Nella migliore delle ipotesi, con $n$ richieste ed $m$ dischi, ci saranno

$\frac{n}{m} richieste/disco$

E se sono sfortunato :(? Tutte le richieste saranno sullo stesso disco. Fortunatamente, nei grandi numeri, la distribuzione delle richieste è più vicina al best case che al worst. Inoltre, non usa ridondanza: sono quindi molto vulnerabili ai guasti, considerando che ogni disco può guastarsi. Teoricamente, anche se i dischi di oggi sono molto sicuri, la probabilità che si guastino aumenta col numero di dischi del sistema RAID.

RAID 1 - mirroring

Gli eventuali stripe sono anche chiamati duplicati, ma può anche essere usato senza striping. Le prestazioni in lettura raddoppiano (in tutti i casi), ma a causa del doveroso aggiornamento di ambo i dischi, non abbiamo aumenti di performance per la scrittura (rispetto ai RAID 0, se abbiamo striping). Otteniamo tuttavia maggiore tolleranza ai guasti. Caso peggiore in lettura $2 \times$ , caso peggiore in scrittura $1 \times$ , caso migliore in scrittura $4 \times$ . C’è un alto overhead causato dal disco praticamente duplicato. Con $n$ dischi, ne sfrutto $n /2$ . Pago quattro tera per averne due…

RAID 2 - striping a livello di bit con ECC

Lavora sulle word applicando un codice di correzione degli errori ECC. Può correggere singoli bit di errore tramite i codici di hamming.

Un esempio? 4 bit con 3 bit di ridondanza. Distribuendo i 7 bit su 7 dischi differenti, e gestendo opportunatamente la sincronia delle rotazioni dei dischi, si ottiene una forte fault tollerance, resistenza ai guasti.

Guastato un disco, se ne fa un altro. Tramite gli altri 6 dischi, è possibile ricostruire l’informazione nel disco perso, qualsiasi esso sia. Con 7 dischi, ne sfrutto 4. L’ECC è overkill.

RAID 3 - striping a livello di bit con bit di parità

Aggiunge un solo disco con raccolti i bit di parità.

Guastato un disco, fortunatamente, è facile stabilire il valore dei bit persi basandosi sul valore di parità. Offre gli stessi benefici del RAID 2 a costo minore. Serve ancora sincronia tra i dischi. Con 5 dischi, ne sfrutto 4.

I prossimi due RAID sono quelli effettivamente usati.

RAID 4 - striping a livello di bit con XOR sull’ultimo disco)

È basato sullo striping a blocchi. L’ultimo disco contiene solo ridondanza: lo XOR dei bit degli strip. Il disco dedicato alla parità è molto utilizzato. $P_{0 - 3} = s_{0} \oplus s_{1} \oplus s_{2} \oplus s_{3}$ Guasto di $s_{2}$ ? $s_{2} = P_{0 - 3} \oplus s_{0} \oplus s_{1} \oplus s_{3}$ Qualsiasi guasto può essere corretto, anche nei dischi di parità.

Prestazioni in lettura: $n \times$ .
In scrittura, apparentemente, pessimo costo: $n - 2$ letture e 2 scritture per ogni bit. Fortunatamente lo XOR può essere ricalcolato anche solo conoscendo il vecchio valore del bit riscritto $s_{x} \to \overline{s_{x}}$ . $\overline{P_{0 - 3}} = P_{0 - 3} \oplus s_{0} \oplus \overline{s_{0}}$ Questo perché due XOR si annullano.

RAID 5 - striping a livello di bit con informazioni di parità distribuite)

Risolve il problema relativo all’uso maggiore del quinto disco. Ogni scrittura su un disco, in RAID 4, richiede una scrittura fissa sul quinto disco. Distribuendo le informazioni di parità, distribuiamo il carico di lavoro, con analoga resistenza ai guasti e performance. RAID 5 risolve l’unica problematica di RAID 4.

Un’ultimo vantaggio? Potenzialmente il lavoro è distribuibile su tutti i dischi. Nessun disco ha uno scopo fisso, tutti possono soddisfare richieste, tutti hanno delle informazioni di parità.

Recap sui vari RAID

RAID	Tipo di stripe	Ridondanza	In breve
0	Blocco	No	Sensibile a guasti di qualsiasi disco, velocizza in maniera importante le letture di grandi volumi, soprattutto se questi sono ben distribuiti su più dischi.
1	Blocco	Mirroring (non corregge)	Performance di lettura $\times n$ per $n$ dischi, buona fault tollerance ma alto overhead. Il numero di scritture aumenta per ogni mirror, ma la velocità è limitata dal disco più lento.
2	Bit	Hamming (ECC)	Richiede sincronia a causa dei bit, bottleneck del disco fisico di velocità minima, ottima fault tollerance. Numero di dischi stabilito secondo le regole dell’ECC ( $2^{n}$ ). Lo striping a livello di bit è molto pesante.
3	Bit	Parità	Un solo disco per la correzione, stessa fault tollerance di RAID 2 a basso costo. Lo striping a livello di bit è molto pesante.
4	Blocco	XOR	Un singolo disco conterrà gli XOR di ogni blocco. Non necessita sincronia, ottima fault tollerance. L’aggiornamento dei blocchi di parità è ottimizzato calcolando lo XOR dei vecchi valori di parità con i nuovi valori dei blocchi aggiornati.
5	Blocco	XOR distribuito	Distribuendo i blocchi di parità su tutti i dischi fisici, si crea meno bottleneck, si distribuisce l’usura su tutti i dischi del volume RAID. Ogni disco ha pari responsabilità.

Solid State Disk - SSD

Sono dispositivi basati su memorie flash. Usano tecnologie NAND, con architetture più simili alle RAM, ma dalla natura non volatile. Offrono letture molto veloci, grazie all’assenza di parti meccaniche. Per questo motivo, gli SSD ignorano i meccanismi di scheduling del disco, questi vengono inibiti, in quanto innecessari: basta un approccio FIFO per ottenere prestazioni ottimali.

Prestazioni

Gli SSD si usurano ad ogni operazione di cancellazione. Ogni riscrittura di (parte di) un blocco avviene previa cancellazione dell’intero blocco. Definiamo blocco come un’unità di cancellazione. Un blocco è composto da pagine, definite come unità di allocazione.

Le letture sono effettuate su pagine, le cancellazioni sono sugli interi blocchi. Per aggiornare un’informazione di una pagina, va effettuata la cancellazione e riscrittura dell’intero blocco.

Memorie Flash e File System

Cancellare ad oltranza singole pagine, usura rapidamente blocchi. Bisogna avere un file system ottimale per minimizzare il deterioramento. Immaginiamo un sistema FAT su un SSD: i blocchi contenenti la FAT verrebbero consumati molto rapidamente.

Flash-Friendly File System.
Rimappaggio dei blocchi tramite controller hardware, detti Flash Translation Layer. A prescindere dal file system, il controller gestirà una sorta di mappa (stile tabella delle pagine) che si pone tra memoria effettiva e file system, mappando blocchi logici a blocchi effettivi. Il controller, in fase di riscrittura di un blocco, invece di cancellarlo, rimapperà lo stesso blocco logico ad un nuovo blocco fisico, in modo da uniformare l’usura dei blocchi.

Una sovrascrittura di un blocco logico, coinciderà con una scrittura ad un altro blocco fisico.

Garbage Collection e TRIM

Le celle piene di spazzatura (file modificati e cancellati), vengono cancellate solo quando è necessario. La cancellazione all’ultimo momento possibile, permette di scegliere il miglior blocco da cancellare: un blocco con tante pagine da eliminare e poche da mantenere, sarà migliore.

Il controller stesso, crea spazzatura: i blocchi cancellati nel volume logico, rimangono nel sistema fisico.

Il controller non ha visibilità relativa a quali file sono spazzatura o meno: in fase di riscrittura, cancellerà anche i file non più necessari all’OS, usurando velocemente e rendendo lenti dischi virtualmente vuoti. L’operazine TRIM, offerta dal Controller al Sistema Operativo, permette di segnalare quali blocchi possono essere ignorati in fase di cancellazione. Il Sistema Operativo potrà informare il controller in fase di cancellazione.

Andrea Girlando

Explorer

SistemiOperativi

Explorer

Capitolo 1

Generalità sui sistemi operativi

Che cos’è un sistema operativo

Il sistema operativo come macchina estesa

Il sistema operativo come gestore delle risorse

Storia dei sistemi operativi

Analisi dell’hardware

Processori

I Registri della CPU

Memoria

Dischi

Dispositivi di I/O

Panoramica dei vari sistemi operativi

Chiamate di sistema (System Call)

Struttura di un sistema operativo

Sistemi monolitici

Sistemi a livelli

Microkernel

Modello client-server

Macchine virtuali

Capitolo 2

Processi

L’anatomia di un processo in memoria

CPU virtuale e cambio di contesto

Creazione dei processi

Chiamate di Sistema per la Creazione

Terminazione dei processi

Stati di un processo e ciclo di vita

Gestione dei processi

Le Code

Thread

Introduzione al Modello a Thread Multipli

Thread con risorse esclusive o condivise

Operazioni, Stati e Context Switch

Multicore Programming e Concorrenza

Thread a livello utente (modello 1-a-molti)

Thread a livello kernel (Modello 1-a-1)

Modello Ibrido (Molti-a-molti)

Librerie di Riferimento: pthreads

Comunicazione tra processi

Introduzione e complessità dell’IPC

Il modello pipe

Segmento di memoria condiviso

Il Problema delle race condition

Condizioni per una soluzione efficace

Inibizione degli interrupt

Variabili di lock

Alternanza Stretta

L’Algoritmo di Peterson

Istruzione TSL e XCHG

Conclusioni su queste soluzioni

Primitive Sleep e Wakeup

Prima soluzione al problema del Produttore-Consumatore

Semafori

Soluzione al Produttore-Consumatore con i semafori

Mutex

Futex (Fast User Space Mutex)

Monitor

Soluzione Produttore-Consumatore con i monitor

Scambio di messaggi

Soluzione Produttore-Consumatore con i messaggi

Problema dei filosofi a cena

Tentativi di soluzione al problema dei filosofi a cena

Problema dei lettori-scrittori

Tentativi di soluzione al problema dei lettori-scrittori

Scheduling

Introduzione allo scheduling

Quando effettuare lo scheduling

Categorie di Algoritmi e ambienti

Algoritmi per sistemi batch

Algoritmi per sistemi interattivi

Scheduling nei sistemi Real-Time

Scheduling a Thread

Lo Scheduling su Sistemi Multiprocessore

Lo Scheduling nei principali sistemi operativi

Capitolo 3