The Block I/O Layer
Rafael Lopes Bezerra
Block I/O

Dispositivos de Bloco:
– Dispositivos de hardware que acessam
aleatoriamente blocos de dados
– Ex: Disquete, CD-ROM, HD
 Dispositivo de Caracter:
– Dispositivos que acessam dados sequenciamente,
um byte após o outro
– Ex: portas seriais, teclado
 Gerenciar dispositivos de bloco no kernel requer mais
trabalho.
 Um sub-sistema dedicado ao gerenciamento de
dispositivos de bloco é necessário.
Anatomia de Um Dispositivo de Bloco





Menor unidade endereçável: setor
Tipicamente 512 bytes
O dispositivo não pode endereçar ou
operar em uma unidade menor que o
setor.
Software impõe sua própria unidade
lógica endereçável, o bloco.
Um bloco é uma abstração do sistema de
arquivos e só pode ser acessado em
múltiplos de blocos.
Anatomia de Um Dispositivo de Bloco

O kernel realiza todas as operações de
disco em termos de bloco.
 Um bloco não pode ser menor que um
setor e nem maior que uma página.
Tipicamente possui 512 bytes, 1 kilobyte e
4 kilobytes.
 O bloco precisa ser um múltiplo de um
setor, uma vez que um setor é a menor
unidade do dispositivo.
Anatomia de Um Dispositivo de Bloco
Buffer





Quando um bloco é armazenado na
memória é guardado no buffer.
Cada buffer é associado com um bloco.
Cada página pode conter um ou mais
blocos na memória.
O kernel requer alguma informação
acompanhando o dado, por isso cada
bloco é associado a um descritor.
O descritor contém todas as informações
necessárias para manipular buffers.
Buffer Head
struct buffer_head {
unsigned long b_state; /* buffer state flags */
atomic_t b_count;
/* buffer usage counter */
struct buffer_head *b_this_page; /* buffers using this page
*/
struct page *b_page;
/* page storing this buffer */
sector_t b_blocknr;
/* logical block number */
u32 b_size;
/* block size (in bytes) */
char *b_data;
/* buffer in the page */
struct block_device *b_bdev; /* device where block resides
*/
bh_end_io_t *b_end_io; /* I/O completion method */
void *b_private;
/* data for completion method */
struct list_head b_assoc_buffers; /* list of associated
mappings */
};
Buffer Head
Status
BH_Uptodate
BH_Dirty
BH_Lock
BH_Req
BH_Mapped
BH_New
BH_Async_Read
BH_Async_Write
BH_Delay
BH_Boundary
Flag Meaning
Buffer contém dados válidos
Buffer está sujo
Buffer está realizando disk I/O e está bloqueado
Buffer está envolvidocom um I/O request
Buffer está mapeado em um block no disco
Buffer foi mapeado via get_block() e não foi
ainda acessado
Buffer está realizando leitura asíncrona de I/O via
end_buffer_async_read()
Buffer está realizando escrita asíncrona de I/O via
end_buffer_async_write()
Buffer ainda não está associado a um bloco no
disco
Buffer forma o limite de blocos contíguo
Buffer Head
Antes do kernel 2.6 o cabeçalho do Buffer era a estrutura de
dados mais importante. Basicamente, era a unidade de E/S no
kernel.
 O cabeçalho do buffer não descrevia somente o mapeamento
do bloco do disco para a página física, mas também agia como
um contêiner usado para toda E/S do bloco.
Isso tinha dois problemas básicos:
1º) O cabeçalho do buffer era uma estrutura de dados grande e
difícil (O kernel prefere trabalhar em termos de páginas, que
são simples e permitem um maior desempenho);
2º) O cabeçalho do buffer quando usado como um contêiner para
todas as operações de E/S, faz com que o kernel divida as
operações de E/S do bloco em diversas estruturas buffer_head,
isso resulta em um overhead desnecessário e no consumo do
espaço

Estrutura Bio

O principal propósito da estrutura Bio é
representar operações block I/O que estão
ativas.
 Um segmento é uma porção de um buffer
contínuo na memória.
 Utilizando a estrutura bio o kernel pode
realizar operações de block I/O de um
buffer de diferentes partes da memória.
Estrutura Bio
struct bio {
sector_t bi_sector; /* associated sector on disk */
struct bio *bi_next; /* list of requests */
struct block_device *bi_bdev; /* associated block device */
unsigned long bi_flags; /* status and command flags */
unsigned long bi_rw; /* read or write? */
unsigned short bi_vcnt; /* number of bio_vecs off */
unsigned short bi_idx; /* current index in bi_io_vec */
unsigned short bi_phys_segments; /* number of segments after
coalescing */
unsigned short bi_hw_segments; /* number of segments after remapping
*/
unsigned int bi_size; /* I/O count */
unsigned int bi_hw_front_size; /* size of the first mergeable
segment */
unsigned int bi_hw_back_size; /* size of the last mergeable segment
*/
unsigned int bi_max_vecs; /* maximum bio_vecs possible */
struct bio_vec *bi_io_vec; /* bio_vec list */
bio_end_io_t *bi_end_io; /* I/O completion method */
atomic_t bi_cnt; /* usage counter */
void *bi_private; /* owner-private method */
bio_destructor_t *bi_destructor; /* destructor method */
Bio_vec

As estruturas bio_vec são usadas como listas de
segmentos individuais e descrevem um
segmento através da página física, a localização
do bloco como um offset para a página e o
tamanho do bloco.
struct bio_vec {
/* pointer to the physical page on which this buffer resides
*/
struct page *bv_page;
/* the length in bytes of this buffer */
unsigned int bv_len;
/* the byte offset within the page where the buffer resides */
unsigned int bv_offset;
};
Estrutura Bio
Buffer Head x Bio

Cabeçalhos do Buffer:
–
Representa um único buffer, que descreve um único bloco no
disco,
– São ligados a um único bloco do disco em uma única página,
resultando na divisão desnecessária das solicitações em partes do
tamanho do bloco;
– É requerido para funcionar como um descritor mapeando os
blocos do disco para as páginas.

Estrutura bio:
–
Representa uma operação E/S, que pode incluir uma ou mais
páginas na memória;
– É mais leve e pode descrever blocos descontínuos e não divide
desnecessariamente as operações de E/S
– Não contém nenhuma informação sobre o estado do buffer
Buffer Head x Bio
Buffer Head ainda é necessário:
contém informações para o buffer,
mapeia blocos para páginas
 Bio: descreve operações ativas, não
contém informações sobre o estado
de um buffer

Filas de Solicitação





Os dispositivos de bloco mantêm filas de solicitação para
armazenar suas solicitações de E/S do bloco pendente;
São representadas pela estrutura request_queue e é
definida em <linux.blkdev.h>
Contém uma lista de solicitações e informações de controle
associadas (as solicitações são adicionadas á fila pelo
código de nível mais alto no kernel como os sistemas de
arquivos);
A fila de solicitação não estando vazia, o driver do
dispositivo de bloco associado á fila obterá o cabeçalho da
fila e irá envia-lo para seu dispositivo de bloco associado.
Cada item na lista de solicitação da fila é uma solicitação
do tipo struct request
Schedulers de E/S



Funciona gerenciando a fila de solicitação de um
dispositivo de bloco;
Gerencia a fila de solicitação, decidindo a ordem das
solicitações e em qual hora cada solicitação é enviada para
o dispositivo de bloco;
Executa duas ações para minimizar as buscas:
–
Mescla: É a combinação de duas ou mais solicitações em
uma
–
Classificação


Não deve ser confundido com o scheduler do processo. O
sheduler do processo divide o recurso do processador
entre os processos no sistema.
Exemplo de schedulers de E/S: Elevador Linus (era o
scheduler de E/S default no 2.4).
Elevador Linus

Quando um pedido é adicionado à fila, 4
operações são possíveis:
1. Se um pedido para um setor adjacente está
na fila, mescla
2. Se um pedido na fila está velho, o novo
pedido vai para o final da fila
3. Se existe um lugar possível de inserção na
fila(um lugar na fila onde o novo pedido entra
entre pedidos existentes), então é inserido lá
4. Final da fila
Deadline I/O Scheduler

Tenta prevenir o starvation causado pelo Elevador
Linus
 Lista ordenada pela localização física
 “writes starving reads”
– Operações de escrita são assíncronas
– Operações de leitura são síncronas (a aplicação é
bloqueada até ter o resultado)
Latência de escrita é muito importante para a
performance do sistema
 Cada pedido é associado com um tempo de expiração
 Fila de pedidos de escrita x fila de pedidos de leitura
Deadline I/O Scheduler
Anticipatory I/O Scheduler

O Deadline Scheduler melhora a latência
de leitura, porém piora o throughtput
global
 Normalmente vários pedidos de leitura
acontecem juntos => O Anticipatory
espera algum tempo após atender um
pedido de leitura antes de voltar a atender
outros pedidos
 O Scheduler armazena estatisticas para
melhorar a antecipação
 É o Scheduler default do Linux
Complete Fair Queuing I/O
Scheduler
Cada processo possui uma fila, e as
filas são ordenadas por setor
 Dentro de cada fila os pedidos são
mesclados
 As filas são servidas Round-Robin

Noop I/O Scheduler

Não realiza um classificação
 Não precisa implementar algoritmos para
reduzir a latência de pedidos como os
anteriores
 Mescla pedidos próximos
 Projetado para ser utilizado por dispositivos
aleatórios que não tem overhead procurando
o local no disco
Seleção do Scheduler

O Anticipatory é o default
 Pode ser mudado na opção boot-time
elevator=nome na linha de comando do
kernel
–
–
–
–
as = Anticipatory
cfq = Complete Fair Queuing
deadline = Dealine
noop = Noop