Fundamentos de Sistemas Operacionais

Aula 16: Entrada e Saída: Estudo de Caso

Diego Passos

Última Aula

Software de Entrada e Saída.

● Subsistema de E/S.○ Conjunto de camadas de abstração para realização de

operações de E/S.● SO usa device drivers para fazer manipulações específicas

de dispositivos de E/S.● SO provê camada com serviços comuns a todos os tipos de

dispositivos.● SO provê uma interface para o usuário (programador).

○ Através de chamadas de sistema.○ Linguagens e bibliotecas fornecem abstrações mais

altas.● Há três modos de execução de uma E/S:

○ Bloqueante, não-bloqueante e assíncrona.

Disco Rígido: Visão Geral

Por que estudar o Disco Rígido

● Há inúmeros dispositivos de E/S.● Estudar todos seria inviável.● O disco rígido (ou HD) é um dos dispositivos mais

interessantes.● É utilizado em diversas tarefas dentro do sistema:

○ Armazenamento não-volátil.○ Swap.○ ...

● É um dos poucos dispositivos nos computadores modernos que faz uso de operações mecânicas.

○ Por isso:■ Tende a ser muito mais lento que os demais

componentes.■ Tende a apresentar falhas muito mais

frequentemente.

Outros Dispositivos de Armazenamento em Massa

● Há vários outros dispositivos deste tipo.● Baseados em mídia removível:

○ Cartões de memória.○ Pendrives○ CD, DVD, e Blu-ray.

● Há também outros não removíveis:○ SSDs.

■ Usados em substituição aos HDs em netbooks.■ Empregam memória flash.

○ HyperDrives.■ Usados em substituição aos HDs em servidores

muito especializados.■ Empregam memória RAM e baterias (para manter

informações permanentemente)

Domínio do Mercado

● HDs convencionais ainda dominam o mercado.○ Baixos preços.○ Grandes capacidades de armazenamento.

■ É possível ter um PC com HD de 1TB a custo acessível.

Composição Física

● Composto por conjunto de discos metálicos.

○ Chamados de pratos.

○ Recobertos por uma película magnética.

○ Giram em torno de um eixo comum.

● Há ainda um braço mecânico com cabeçotes de leitura e escrita.

Composição Lógica

● Cada superfície de um prato é dividida em trilhas.○ Circunferências concêntricas (centradas no eixo de

rotação).● Cada trilha é composta por setores.

○ Arcos sobre a circunferência da trilha.○ Ângulos são fixos.○ Setores são conjuntos de bits.

■ "Pedaços" da película do prato que armazenam fisicamente um bit.

● Conjunto de trilhas de um mesmo raio em todos os pratos é chamado de cilindro.

Composição Lógica (mais)

Representação de um Bit

● Bits são representados pela orientação magnética de partes da película que recobre os pratos.

● Vários tipos de modulação podem ser usados.● A mais simples de todas é simplesmente definir duas

orientações opostas. Exemplo:○ Orientação de dentro para fora do prato representa 0.○ Orientação de fora para dentro do prato representa 1.

● Durante a escrita, cabeçote gera um campo que polariza a película.

● Durante a leitura, o campo da película induz uma corrente no cabeçote.

Densidade de Bytes por Área

● Setores são divisões radiais das trilhas.● Logo, toda trilha deve ter o mesmo número de setores.● Fisicamente, isso significa que trilhas mais externas

armazenam menos bytes por unidade de área.○ A densidade nestas trilhas é menor.

● Duas consequências:○ Tendência de falhas é maior nas trilhas internas.○ Alguns fabricantes testaram HDs de densidade

homogênea.■ Trilhas mais externas têm mais setores.■ Mudança feita em hardware.■ Para o software, geometria continuava igual

Capacidade de Armazenamento de um HD

● Em geral, fabricantes identificam quatro informações em um HD:

○ Número de cabeçotes (Heads ou h).■ Cada cabeçote corresponde a uma superfície de

leitura/escrita.○ Número de cilindros (Cylinders ou c).○ Número de setores por trilha (Sectors ou s).○ Bytes por setor.

● A capacidade de um HD pode ser calculada pelo produto destes três valores. Exemplo:

○ HD tem 16 cabeçotes,1016 cilindros, 51 setores e 512 bytes por setor.

○ Capacidade é 424476672 bytes (400 MB).

Endereçamento de Dados em um HD

● Originalmente, os HDs só suportavam um modo de endereçamento de dados: o CHS.

○ Três componentes:■ Cilindro.■ Cabeçote.■ Setor.

● Mais recentemente, surgiu o LBA (Linear Block Addressing).

○ Setores do HD são vistos como sequenciais.○ Cada um recebe um identificador numérico único,

começando do 0.○ Endereçamento é mais intuitivo.

● Pode-se facilmente converter um endereço do LBA para o CHS (e vice-versa).

○ Basta saber as características do HD.

Tempo de Acesso de um HD

Operações Necessárias para Acesso

● Quando uma requisição de leitura ou escrita chega ao HD, este realiza uma sequência de três operações:

○ Seek: posicionamento do cabeçote de leitura sobre a trilha desejada.

○ Latência: espera até que o giro do prato faça a setor desejado se posicionar sob o cabeçote.

○ Transferência: leitura/escrita efetiva, realizada durante a passagem do setor sob o cabeçote.

● Tempo total de acesso é dado pelo somatório dos tempos das três operações.

Tempos de Cada Operação

● O tempo de seek é determinado pela velocidade de movimentação do braço que manipula os cabeçotes.

○ Em média, da ordem de 10 ms.● O tempo de latência é determinado pela velocidade de

rotação do disco (que varia de 3600 a 15000 RPM).○ Em média, da ordem de 5 ms.

● O tempo de transferência também depende da velocidade de rotação do disco.

○ Bem menor que 1 ms.● Os tempos de seek e latência também dependem das

posições atuais do prato e do cabeçote.● Tempo de seek domina o tempo total de acesso a disco.

Entrelaçamento

● Técnica para melhorar o tempo de acesso a disco.● Também chamada de Interleaving. ● Processos, em geral, requisitam leitura de vários setores

consecutivos.○ Exemplo, setores 14 e 15.○ Quando leitura do setor 14 termina,CPU (ou DMA) tem

que fazer a requisição do setor 15.○ Neste intervalo, prato continua em rotação.

■ Provavelmente, já passando pelo setor 15.○ Quando a requisição chega, setor 15 já passou.

■ É preciso esperar uma nova revolução completa do prato.

Entrelaçamento (mais)

● Ideia do entrelaçamento:○ Não colocar setores de IDs consecutivos fisicamente

consecutivas.○ Inserir outros setores intermediários.

■ Usar um Fator de Entrelaçamento.■ Número de setores entre dois consecutivos.

Algoritmos de Escalonamento

Motivação

● Um HD é um dispositivo que pode receber várias requisições ao mesmo tempo.

● A ordem de grandeza do tempo de acesso de um HD é muito maior que a dos demais dispositivos da máquina.

● Por exemplo, nos 10 ms utilizados pela operação de seek, um processador de 2 GHz executa20 milhões de ciclos.

● Otimizaro tempo de acesso a disco é fundamental.○ Pequenos ganhos percentuais, são enormes em termos

absolutos.

Objetivo

● O objetivo do escalonamento do HD é sempre maximizar a vazão.

○ Quantidade de dados lidos/escritos por unidade de tempo.

● Uma vez que o cabeçote de leitura esteja posicionado sobre o setor desejado, a velocidade de leitura/escrita é sempre igual.

○ Determinada pela velocidade de rotação dos pratos.● Portanto, vazão é maximizada minimizando os tempos de

seek e latência.○ Especialmente o de seek, que é maior.

Algoritmo FIFO

● Não se preocupa com o desempenho.● Apenas escalona as requisições na ordem em que elas

chegam ao SO.● Desempenho é "aleatório".

○ Determinado ao acaso, pela ordem de chegada das requisições.

● Vantagem: implementação muito simples.

Algoritmo SSTF

● Shortest Seek Time First.● Dentre as requisições, atende primeiro a que tiver o menor

tempo de seek.○ A trilha desejada é a mais próxima da trilha atual.

● Tem bom desempenho, no melhor caso.○ Quando as requisições chegam em uma ordem propícia.

● Tem péssimo desempenho no pior caso.○ Quando as requisições chegam em uma ordem ruim.

● Pode resultar em starvation.○ Requisições para trilhas muito distantes da atual podem

nunca ser atendidos.

Algoritmo SCAN

● Determina um sentido de percorrimento para os cabeçotes.● Por exemplo:

○ Inicialmente, cabeçotes estão na parte mais externa dos pratos.

○ Sentido de percorrimento será sempre em direção a parte mais interna.

○ Ao longo do caminho, requisições são atendidas na ordem de percorrimento.

● Quando os cabeçotes chegam ao outro extremo dos pratos, sentido de percorrimento é invertido e procedimento continua.

● Também conhecido como Algoritmo do Elevador.○ Funcionamento similar a um elevador.

Algoritmo SCAN (mais)

● Tem diversas variações:○ CSCAN: Quando cabeçotes chegam ao outro extremo

dos pratos, eles voltam ao início, sem atender novos pedidos.

■ Objetiva maior justiça para requisições em trilhas nos extremos.

○ LOOK: não vai até o extremo, se não há outras requisições para lá.

■ Para na trilha da última requisição e começa a volta.○ ...

Comparação dos Algoritmos

FIFO SSTF

SCAN CSCAN

Comparação dos Algoritmos

● FIFO é o mais simples.○ Mas não leva em consideração informações de

desempenho.● SSTF pode resultar em bom desempenho.

○ Mas desempenho varia muito e pode levar a starvation.● O algoritmo do elevador (e suas variações) resultam nos

melhores desempenhos na média.○ Mas são tem implementação complexa.

RAID

Redundant Array of Independent Disks

● Técnica utilizada para minimizar dois problemas comuns do uso de HDs em grande escala:

○ Velocidade de acesso baixa (comparada aos demais componentes da máquina).

○ Alta probabilidade de falha.■ Ocasionando perda de dados.

● Ideia é formar um vetor de HDs físicos, que contenha algum tipo de redundância.

○ A redundância permite a recuperação dos dados em caso de certas falhas.

○ O vetor de vários HDs é visto como um único grande HD.

● Existem vários níveis de RAID.○ Cada um com características específicas.

RAID 0

● Não há redundância.● Todos os discos armazenam apenas dados.● Vantagens:

○ Como há vários HDs físicos, requisições podem ser atendidas em paralelo.

■ RAID 0 faz um balanceamento de carga na distribuição dos dados pelos HDs.

○ Ou seja, o RAID 0 oferece benefícios apenas de desempenho.

● Esquema conhecido também como stripping.● Capacidade total de armazenamento é igual a soma das

capacidades dos HDs.

RAID 1

● Método de espelhamento.● São usados n HDs de igual capacidade.

○ Um principal, outros secundários.● Todos os dados são escritos no HD principal.

○ Mas automaticamente são espelhados para os HDs secundários.

● Em caso de falha do HD principal, os outros contêm uma cópia perfeita.

● Não há benefícios de desempenho.● Capacidade total de armazenamento é igual a soma das

capacidades dos HDs dividida por n.

RAID 2/3/4

● Os três níveis são parecidos.● Todos usam n+1 HDs.

○ Os n primeiros, armazenam dados.○ O último armazena informações de redundância:

■ Paridade de bit, no RAID 2.■ Paridade de byte, no RAID 3.■ Paridade de bloco, no RAID 4.

● Há tanto benefícios de desempenho (stripping nos n primeiros HDs), quanto de redundância.

○ Em caso de falha de um dos n primeiros HDs, as informações dos demais, pode ser usada para recuperar os dados perdidos.

RAID 5

● Idêntico ao RAID 4, exceto pelo fato de que as informações de paridade são distribuídas por todos os discos.

● Isto é, não existe um único HD para armazenar informações de paridade.

● Objetivo:○ Evitar que o HD de paridade se torne um gargalo na

escrita.

RAID 6

● Idêntico ao RAID 5, porém com um esquema de paridade dupla.

● No RAID 5, se um HD falha, todo o sistema fica sujeito a perda de dados até que este HD seja substituído.

○ Se mais um HD falhar antes da substituição, dados serão perdidos.

● O RAID 6 tolera a falha de até dois HDs do conjunto.○ Logo, no caso de um defeito em um HD, o sistema

ainda tem uma proteção contra perda de dados.

RAID 10

● Combina os níveis 0 e 1.● Há vários conjuntos de HDs que fazem espelhamento.● Cada conjunto é usado como um HD do nível 0.● Vantagens:

○ Alta tolerância a falhas.■ A falha de um HD é facilmente corrigida através da

ativação de um HD secundário do seu conjunto.○ Alto desempenho.

■ Até k requisições podem ser atendidas simultaneamente, onde k é o número de conjuntos.

● Desvantagem:○ Ao menos 4 discos são necessários.○ Custo muito alto.

Implementações do RAID

● RAID pode ser implementado tanto por hardware, quanto por software.

● Caso implementado em hardware, SO vê todo o vetor de discos como um único HD.

○ Funcionamento é completamente transparente para o SO.

● Implementação em hardware tende a ser mais rápida que em software.

○ Mas a diferença já foi bem maior.

Revisão

Para Lembrar

● Funções do HD nos computadores.○ Armazenamento não volátil.○ Swap.

● Características de um HD (enquanto dispositivo de E/S).○ Partes mecânicas.

■ Altos tempos de acesso.■ Alta probabilidade de falha.

● Componentes do tempo de acesso a disco.○ Tempo de seek, latência, transferência.

● Redução do tempo de acesso.○ Entrelaçamento.○ Algoritmos de escalonamento.

● RAID.○ O que é e para que serve.