1
Lezione 33
Il Block Layer
Sistemi Operativi (9 CFU), CdL Informatica, A. A. 2020/2021 Dipartimento di Scienze Fisiche, Informatiche e Matematiche Università di Modena e Reggio Emilia
http://weblab.ing.unimo.it/people/andreolini/didattica/sistemi-operativi
Quote of the day
(Meditate, gente, meditate...)
“I think the major good idea of UNIX was its clean and simple interface: open, close, read and write.”
Ken Thompson (1943-)
Ingegnere, Programmatore
Ideatore del sistema operativo UNIX Creatore di Belle
3
GESTIONE STRATIFICATA I/O BLOCCHI
Eterogeneità dei dispositivi
(Elevata, purtroppo)
La gestione di un dispositivo a caratteri prevede di mantenere una sola posizione, quella attuale del cursore di lettura/scrittura.
La gestione di un dispositivo a blocchi (che può effettuare seek) è molto più complessa.
La complessità è incrementata dalla presenza di dispositivi a blocchi con caratteristiche molto diverse.
Rotazionali (a disco) e non rotazionali (SSD).
Logici (LVM) e non.
Provvisti di meccanismi per la lettura concorrente (ad
5
Componenti del Block Layer
(Generic Block Layer)
Generic block layer.
Fornisce una interfaccia di accesso comune a tutti i dispositivi a blocchi nascondendo i dettagli tipici del singolo dispositivo.
Nasconde i dettagli tipici del singolo dispositivo a blocchi al file system.
Consente il disaccoppiamento tra organizzazione logica del file (file system) e posizione fisica del dato sottostante.
Utilizza politiche efficienti di servizio delle richieste di I/O.
Componenti del Block Layer
(Scheduler di I/O)
Scheduler del disco.
Decide l'ordine di servizio delle richieste di I/O per uno specifico dispositivo a blocchi.
L'utente può selezionare, tra quelli compilati nel kernel, lo scheduler utilizzato per ciascun dispositivo a blocchi.
7
Componenti del Block Layer
(Diagramma semplificato)
File system File system Descrittore del disco
Generic block layer Block layer
Driver del dispositivo
Scheduler del disco Scheduler del disco
Driver del dispositivo
Blocchi e settori
(Unità di trasferimento del block layer e del dispositivo)
L'unità di indirizzamento minima di un dispositivo a blocchi è il
settore.Dimensione: è una caratteristica fisica del dispositivo.
Dimensione tipica: 512 byte.
Il block layer utilizza, come unità di
memorizzazione, il blocco.Struttura dati “di collegamento” tra file system, mapping layer e block layer.
Dimensione: multiplo di un settore.
9
Blocchi e settori
(Uno schema semplificato)
Un blocco è un insieme di settori contigui su disco.
Blocchi Settore
...
più settori contigui = 1 blocco
Blocchi e pagine
(Una pagina Uno o più blocchi)→
Una pagina di memoria può contenere uno o più blocchi.
La dimensione del blocco non può eccedere quella della pagina.
Quando un blocco è mappato in memoria si dice
“contenuto in un buffer”.
Un buffer è la porzione di una pagina di memoria
corrispondente ad un blocco.
11
La struttura buffer_head
(Già incontrata nel contesto della page cache)
La struct buffer_head ha il compito di mappare un buffer di una pagina di memoria nel blocco corrispondente.
http://lxr.linux.no/linux+v3.6.5/include/linux/buffer_head.h#L59
La struttura dati contiene:
informazioni sulla pagina.
indirizzo della pagina di memoria.
indirizzo del buffer all'interno della pagina.
informazioni sul blocco.
dispositivo fisico al quale il blocco si riferisce.
numero di blocco.
La struttura buffer_head
(Uno schema semplificato)
page buffer buffer
...
Dispositivo
Blocco buffer_head
b_page b_blocknr
2
settori b_size
b_data b_bdev
13
Problemi delle buffer_head
(Prestazionali)
Nelle versioni del kernel Linux precedenti alla 2.6, la struct buffer_head non descriveva solo la mappatura tra blocchi a pagine.
Era utilizzata per tutte le operazioni di I/O.
Ciascuna operazione di I/O era effettuata sul singolo blocco.
Operazioni di I/O potenzialmente grandi risultavano frammentate.
Aggravio computazionale enorme.
Alto consumo di memoria (tante strutture piccole in caso di letture consistenti).
La struct bio
(Risolve i problemi delle buffer_head)
La struct bio (introdotta nel kernel v2.6 come rimpiazzo dei buffer) rappresenta le operazioni di I/O in corso come una lista di segmenti.
Un segmento è una porzione di buffer contigua in memoria.
Può essere più grande di un blocco!
I singoli buffer non devono essere contigui in
memoria.
15
Definizione della struct bio
(Una lista di segmenti)
La struct bio rappresenta le operazioni di I/O in corso come una lista di segmenti.
http://lxr.linux.no/#linux+v3.6.6/include/linux/blk_types.h#L35
La struttura contiene:
una lista di struct bio_vec, ciascuna delle quali rappresenta un segmento, ovvero una porzione di memoria ad un certo offset all'interno di una certa pagina.
dimensioni dell'I/O da effettuare.
caratteristiche del dispositivo coinvolto dall'operazione di I/O.
I/O vettorizzato
(Scatter-gather I/O)
La struct bio consente al kernel di effettuare I/O a blocchi da locazioni multiple di memoria.
I/O vettorizzato (scatter-gather I/O): sfrutta il parallelismo del dispositivo per scrivere in memoria più buffer contemporaneamente.
Dischi veloci, schede di rete.
17
La struct iovec
(Contiene i dati letti in maniera vettorizzata)
struct iovec: contiene un campo “base” ed uno
“lunghezza” → identifica un “segmento” da leggere in memoria.
La chiamata di sistema readv() legge una lista di segmenti (anche non contigui).
La struct bio_vec
(Il vettore di segmenti)
struct bio_vec {
/* puntatore alla pagina */
struct page *bv_page;
/* lunghezza del segmento */
unsigned int bv_len;
/* posizione del segmento */
unsigned int bv_offset;
};
segmento pagina
19
Relazione tra bio, bio_vec e pagine
(Come è implementata la lista di segmenti) struct bio
bio_vec bio_vec bio_vec bio_vec
pagina
pagina
pagina pagina
bi_io_vec bi_idx (posizione attuale dell'I/O)
Pagine coinvolte
nell'operazione di I/O
PROGRAMMAZIONE ASINCRONA I/O
21
Accesso a dispositivi a blocchi
(Sincrono o asincrono)
Non è detto che una richiesta di I/O debba risultare bloccante per il flusso di esecuzione di un processo.
Se è una lettura, c'è la possibilità che lo sia.
Il processo generalmente ha bisogno dei dati che legge per proseguire con l'elaborazione.
Questo non è sempre vero.
Se è una scrittura, è stata delegata dal processo al flusher.
Così come il processo, il flusher non ha bisogno di bloccarsi in attesa del suo completamento.
Accesso a dispositivi a blocchi
(Sincrono o asincrono)
Tuttavia, l'accesso al dispositivo fisico avviene in modo concorrente.
C'è sempre qualcuno che deve aspettare il proprio turno...
Il block layer deve interagire con il device driver del singolo dispositivo a blocchi.
Bisogna rispettare i tempi del dispositivo fisico, che può essere impegnato in altre operazioni.
23
La struct request_queue
(Contiene le operazioni di I/O in attesa di essere elaborate dal driver)
La struct request_queue è utilizzata per memorizzare le operazioni di I/O in attesa di servizio da parte del device driver.
http://lxr.linux.no/#linux+v3.6.6/include/linux/blkdev.h#L286
La struct request_queue
(Contiene le operazioni di I/O in attesa di essere elaborate dal driver)
Ciascun dispositivo a blocchi ha la propria request_queue.
Rappresentata dal sottoalbero di sysfs /sys/block/<dispositivo>/queue.
Contiene una lista doppiamente concatenata di struct request (viste in seguito) rappresentanti richieste di I/O.
La coda è mantenuta ordinata per settori crescenti (in modo tale da ridurre i seek).
25
Accesso a dispositivi via request queue
(È il driver a pescare richieste dalla request_queue)
Nel momento in cui il block layer vuole mettere a disposizione del device driver di un dispositivo una richiesta, la accoda nella request_queue del dispositivo.
Quando il driver è pronto a servire una richiesta, controlla se la request_queue del dispositivo è vuota.
Se non lo è, estrae una richiesta dalla request_queue e la serve.
Se lo è, attende che il block layer lo solleciti ad estrarre una richiesta. Tipicamente, ciò avviene ogni volta che un processo viene messo in attesa.
Uso di callback
(Asincronia delle operazioni)
Il completamento di una operazione di I/O viene segnalato dal device driver al block layer con l'uso di un callback ( elv_completed_request()).
L'invocazione del callback:
avviene nella bottom half del dispositivo a blocchi.
provoca la cancellazione delle strutture dati non più utili ai fini dell'operazione.
provoca la schedulazione di altre richieste di I/O.
27
RIORGANIZZAZIONE RICHIESTE I/O
Modalità di I/O
(I/O sequenziale)
Un processo può effettuare richieste di I/O secondo due modalità.
I/O sequenziale: una richiesta riguarda settori contigui rispetto a quelli della richiesta precedente.
Esempi: lettura di un file grande, file system check, ...
29
Modalità di I/O
(I/O casuale)
Un processo può effettuare richieste di I/O secondo due modalità.
I/O casuale: una richiesta non riguarda settori contigui rispetto a quelli della richiesta precedente.
Esempio: il caricamento in memoria di librerie preliminare all'avviamento di un'applicazione segue un pattern casuale.
Modalità di I/O
(Un problema)
Ciascuna richiesta di I/O è rappresentata dalla struct bio, che mantiene la mappatura tra i blocchi e le pagine interessati dall'operazione.
Si consideri il caso di un processo che effettua accesso sequenziale ad un disco.
Il fatto di avere multiple richieste di I/O per blocchi i cui settori sottostanti sono adiacenti introduce:
aggravio computazionale inutile.
31
La struct request
(Identifica la singola richiesta da fare al dispositivo fisico)
La struct request rappresenta un'operazione di I/O in corso su un insieme di blocchi i cui settori sottostanti sono adiacenti.
Può coinvolgere diverse bio.
Consente al block layer di comunicare con il device driver ( struct request è la struttura accodata nella request_queue del dispositivo).
http://lxr.linux.no/#linux+v3.6.5/include/linux/blkdev.h#L95
La struct request contiene il puntatore ad
una lista di struct bio.
Fusione di richieste
(Merging: una forma di batching)
Nel momento in cui una struct bio viene costruita nel block layer:
si controlla se esistono, all'interno del block layer, una o più struct request che riguardano settori adiacenti.
In caso affermativo, le strutture dati bio sono accorpate in una unica struct request.
→ Operazione di merging: fusione di una bio in una o più richieste già esistenti.
In questo modo, si riduce l'aggravio legato alla
33
Fusione di richieste
(Front merge, back merge)
Front merge: inserimento della nuova richiesta prima di una richiesta già presente.
Back merge: inserimento della nuova richiesta dopo una richiesta già presente.
Coalesce: raggruppamento di tre richieste in seguito al fatto che la nuova sia successiva alla prima e precedente alla seconda.
nuova bio
richiesta già presente
nuova bio
Back merge
Coalesce
Front merge richiesta
già presente
Plugging
(Un'altra forma di batching)
Se le richieste fossero date immediatamente al driver, la testina subirebbe molti seek.
Ciò va evitato come la peste.
Plugging: il block layer attende per un po' di tempo, nella speranza che arrivino tanti richieste fondibili.
Obiettivo: creare poche richieste grandi e vicine.
Al verificarsi di un evento, viene attivato il device driver.
Scadenza di un timer.
35
Plugging per processo
(Abbassa le latenze dovute al plugging “globale”)
Il plugging è un ottimo meccanismo che, tuttavia, soffre di un problema.
Se diversi processi fanno richieste, tutti provano a prendere lo stesso lock sulla request_queue.
Le attese possono diventare lunghe.
Nelle ultime versioni del kernel, il lock è stato reso a grana più fine.
Una struttura dati di plug per processo.
Un lock per struttura dati di plug.
Esempi successivi: plugging classico.
Tempi di esecuzione della richiesta
(Seek, latency, transfer)
In generale, il tempo impiegato da un disco magnetico per trasferire una certa quantità di dati può essere rappresentato come somma di:
tempo di seek tempo di posizionamento della testina → sulla traccia corretta.
latenza rotazionale → tempo impiegato per posizionare il settore giusto al di sotto della testina (tipicamente, la metà del tempo di rotazione indicato dal costruttore)
tempo di trasferimento dei dati
37
Accesso ad un dispositivo rotazionale
(Un diagramma semplificato) Disco magnetico
Ultima posizione della testina
Tempo di seek
Latenza rotazionale
Tempo di trasferimento Settori da trasferire traccia
Sorting
(Si riordina la sequenza di richieste casuale per ridurre i seek)
Il tempo di trasferimento è costante.
Si conosce il valor medio della latenza (è fornito dal costruttore).
Il tempo di seek dipende dalla posizione della richiesta servita rispetto alla posizione precedente della testina.
Anche in questo caso si conosce il valor medio.
Conoscendo i settori interessati dalle richieste di I/O, però, è possibile ridurre il numero di seek effettuati.
Sorting: riordinamento delle strutture dati request per settori crescenti.
39
Sorting
(Un esempio)
Si consideri un semplice scenario di accesso casuale a un dispositivo a blocchi.
Disco rotazionale avente tempo medio di seek di 15 millisecondi.
10 richieste effettuate per settori collocati su tracce diverse nel seguente ordine:
10, 2, 5, 8, 4, 7, 1, 9, 3, 6.
Accesso senza riordinamento
(La testina si sposta di continuo)
10 seek
10 * (15 ms)
= 150 ms
0,15 secondi sono persi nelle operazioni di seek
Il tasso di servizio ne risente
8
1 2
3 4
5
6 7
10 9 Settore
41
Accesso con riordinamento
(La testina non si sposta mai)
1 seek (per raggiungere il primo settore, se
necessario)
Attesa di 15 ms
In seguito, il
trasferimento avviene in modo continuato con alto tasso di servizio Settore
Tempo 1
2
3
4
5
6
7
8
9 10
Scheduler del disco
(Riordina le richieste di I/O)
Scheduler del disco: componente il cui compito è decidere in che ordine le strutture request debbano essere messe a disposizione del device driver.
Tipicamente, persegue due obiettivi:
il tasso di servizio deve essere alto.
le richieste devono essere servite il prima possibile.
Implementa politiche di gestione delle richieste.
Deve rispettare prototipi generici definiti in un descrittore.
43
Scheduler del disco
(Riordina le richieste di I/O)
La politica implementata da uno scheduler solitamente prevede che partecipi alle operazioni di merge e sort operate dal generic block layer.
Dà il consenso ad operazioni di merge su request già presenti nelle proprie strutture dati private.
Tipicamente, gestisce le richieste secondo
l'algoritmo dell'ascensore (elevator): non salta
follemente di piano in piano, ma serve le richieste
in ordine di settore.
UNA VISIONE D'INSIEME
45
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel
mode
Hardware Block layer
Il processo richiede un dato via read(). Il VFS individua il giusto dispositivo ed invoca la do_sync_read(), che attiva il block layer.
Richiesta lettura blocco
Pagina memoria
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel Block layer mode
Il block layer decide se è il caso di effettuare una anticipazione (read ahead) di 128KB, per migliorare le prestazioni delle read() successive (nel caso di accesso sequenziale).
Read ahead
Pagina
memoria Pagina
memoria ...
47
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel
mode
Hardware Block layer
Il block layer prepara la struct bio descrivente il segmento di memoria coinvolto nella lettura.
Preparazione struct bio
Pagina
memoria Pagina
memoria ...
bio
bio_vec ... bio_vec
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel Block layer mode
Il block layer trasforma la bio in una request e la inserisce nella coda di richieste dello scheduler di I/O.
Inserimento della bio nello
scheduler
Pagina
memoria Pagina
memoria ...
bio request
49
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel
mode
Hardware Block layer
Il block layer trasforma la bio in una request e la inserisce nella coda di richieste dello scheduler di I/O. La coda è ordinata per settori crescenti.
Inserimento della bio nello
scheduler
Pagina
memoria Pagina
memoria ...
bio request
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel Block layer mode
Lo scheduler opera una fusione delle richieste, se contigue.
Inserimento della bio nello
scheduler
Pagina
memoria Pagina
memoria ...
bio request
51
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel
mode
Hardware Block layer
Il block layer NON invia subito la richiesta al device driver, bensì attende per uno specifico intervallo (unplug timeout). L'idea è quella di operare più fusioni possibili, ottenendo poche, grandi richieste.
Inserimento della bio nello
scheduler
Pagina
memoria Pagina
memoria ...
bio request
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel Block layer mode
Allo scadere del timer di unplug, il device driver è attivato. Esso chiede una richiesta allo scheduler di I/O e la inserisce nella coda delle richieste del dispositivo in modo tale da mantenere ordinati i settori.
Device driver
Pagina
memoria Pagina
memoria ...
request Coda
scheduler
53
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel
mode
Hardware Block layer
Successivamente, il device driver pesca la prima richiesta dalla coda del dispositivo e la programma in DMA.
Device driver
Pagina
memoria Pagina
memoria ...
request Coda
scheduler
Coda
dispositivo DMA
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
Processo User
mode Kernel Block layer mode
La richiesta è programmata. Non rimane che attendere l'interruzione del dispositivo. Il device driver rischedula il processo: schedule().
Device driver
Pagina
memoria Pagina
memoria ...
schedule()
55
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
User mode Kernel
mode
Hardware Block layer
Quando arriva l'interruzione del dispositivo, viene eseguita la sua top half, che controlla lo stato del dispositivo, riabilita le interruzioni e schedula la bottom half. Attenzione: i dati richiesti sono già in memoria centrale (il trasferimento è avvenuto in DMA).
Top half
Pagina
memoria Pagina
memoria ...
Bottom half Processo
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
User mode Kernel Block layer mode
Quando viene eseguita la bottom half, si dichiara completata la richiesta. Il device driver distrugge, per conto della bottom half, tutte le strutture dati coinvolte per la gestione della stessa.
Pagina
memoria Pagina
memoria ...
Bottom half Device driver
Coda
scheduler
Processo
57
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
User mode Kernel
mode
Hardware Block layer
Il device driver chiede allo scheduler la prossima richiesta da programmare in DMA. La procedura di prelievo si ripete fino a quando non sono portati in memoria centrale tutti i dati.
Pagina
memoria Pagina
memoria ...
Bottom half Device driver
Coda
scheduler
Coda
dispositivo
request Processo
Un esempio concreto di I/O
(Interazione fra i componenti del block layer)
User mode Kernel Block layer mode
Il device driver risveglia il processo.
Pagina
memoria Pagina
memoria ...
Device driver Processo
