Gerenciamento de
Entrada e Saída e
Escalonamento de
Disco
Luiz Otávio Duarte
INPE MSc. Candidate
Prof. Dr. José Carlos Becceneri
INPE Researcher
Maio – 2004
Copyright © Luiz Otávio Duarte. É dada permissão para copiar,
distribuir e/ou modificar este documento sob os termos da Licença
de Documentação Livre GNU, Versão 1.1 ou qualquer versão
posterior publicada pela Free Software Foundation em
http://www.gnu.org/licenses/licenses.html, com todas as seções
Invariantes, com os Textos da Capa da Frente sendo
“Gerenciamento de entrada e saída e escalonamento de disco Luiz Otávio Duarte”, e com os textos prefaciados de “quarta-capa”
sendo as páginas numeradas de “ii” até “iii” deste documento.
Contato:
Luiz Otávio Duarte
INPE MSc Candidate
[email protected]
INPE – Instituto Nacional de Pesquisas Espaciais
Unidade de São José dos Campos
Laboratório Associado de Computação
Endereço:
Av. dos Astronautas, 1758 – Jd. Nazareth
12227-010 * São José dos Campos – SP – Brasil
Fone: 55-12-3945-6000
http://www.inpe.br/
ii
Prefácio
Este material é uma coleção dos slides e material auxiliar da palestra “Gerenciamento
de entrada e saída e escalonamento de disco”, ministrado aos alunos do curso de sistemas
operacionais como parte dos trabalhos para aprovação no curso, no dia 18 de maio de 2004.
A principal função destes slides e notas de aula é facilitar a realização das anotações
dos tópicos mais importantes discutidos durante a apresentação. Sugestões e apontamentos
de falhas podem ser enviadas diretamente aos autores, em [email protected].
Importante: Este material tem finalidade meramente educacional. Estas notas de aula
podem conter figuras e/ou textos extraídos de outras fontes, as quais, quando ocorrerem, serão
devidamente citados. Os direitos autorais dos textos citados são de propriedade de seus
detentores. A citação ou uso de material de outros autores, quando ocorrer, tem finalidade
meramente didática. As opiniões expressadas são de responsabilidade do autor e não refletem
a posição do INPE, Instituto Nacional de Pesquisas Espaciais. Nem o autor nem o INPE se
responsabilizam por quaisquer danos diretos ou indiretos que o uso deste material
possa causar. Este material pode ser copiado livremente, desde incluindo-se a nota de
copyright da página ii e que sejam citadas todas as fontes, e respeitados os detentores dos
direitos autorais. A referência a qualquer produto comercial específico, marca, modelo,
estabelecimento comercial, processo ou serviço, através de nome comercial, marca
registrada, marca de fantasia, nome de fabricante, fornecedor, ou nome de empresa,
necessariamente NÃO constitui ou insinua seu endosso, recomendação, ou
favorecimento por parte do INPE ou do autor. O INPE ou o autor não endossam ou
recomendam marcas, produtos, estabelecimentos comerciais, serviços ou fornecedores de
quaisquer espécie, em nenhuma hipótese. As eventuais marcas e patentes mencionadas são
de propriedade exclusiva dos detentores originais dos seus direitos e, quando citadas,
aparecem meramente em caráter informativo e educacional, para auxiliar os participantes do
curso ou treinamento, numa base de boa fé pública. Os participantes ou outros interessados
devem utilizar estas informações por sua conta e risco.
Este material didático não se trata de uma publicação oficial do INPE – Instituto Nacional
de Pesquisas Espaciais. Seu conteúdo não foi examinado ou editado por esta instituição. As
opiniões refletem a posição do autor.
São José dos Campos, 18 de maio de 2004.
Luiz Otávio Duarte
iii
Pós Graduação em Computação Aplicada
Gerenciamento de Entrada e Saída
Discentes: Cassius Gomes de Oliveira
Luiz Otávio Duarte
Disciplina: Sistemas Operacionais
Docente: José Carlos Becceneri
INPE
São José dos Campos
Maio/2004
Sumário
1
Resumo
3
2
Introdução
2.1 Dispositivos de Entrada/Saída . . . . .
2.2 Classificação dos dispositivos de E/S . .
2.3 Diferenças entre os Dispositivos de E/S
2.4 Interfaces de E/S . . . . . . . . . . . .
.
.
.
.
3
3
3
4
5
3
Estrutura de comunicação Dispositivos X CPU
3.1 Barramentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
5
4
Estrutura de Comunicação Dispositivo X Memória X CPU
6
5
Sinais de Controle
5.1 Strobing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Handshaking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
6
7
6
Organização da Função de E/S
6.1 Programmed I/O . . . . . . .
6.2 Interrupt-driven I/O . . . . . .
6.3 DMA - Direct Memory Access
6.4 I/O Processor . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
. 9
. 10
. 11
. 13
7
Finalidades do projeto do Sistema Operacional
13
7.1 Eficiência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.2 Generalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8
Bibliografia
15
1
Resumo
Uma das funções do sistema operacional é controlar todos os dispositivos de E/S (entrada/saída) [1]. Como existe
uma gama muito grande de dispositivos, também existe a dificuldade em se desenvolver e implementar uma solução de
gerenciamento eficiente e geral.
O objetivo desta apresentação é mostrar as possíveis abordagens para solucionar o gerenciamento de dispositivos de
E/S, bem como detalhar o escalonamento de disco.
2
2.1
Introdução
Dispositivos de Entrada/Saída
Segundo John D. Carpinelli [2] os computadores precisam ser capazes de interagir com o mundo externo e dispositivos além da memória.
Dispositivos que a CPU controla diretamente são ditos conectados on-line. Este dispositivos comunicam-se
diretamente com a CPU e transferem informações binárias para dentro ou fora da memória sob o comando
da CPU. Dispositivos de entrada e saída ligados ao computador on-line são ditos periféricos.[Mano Limes
576]
2.2
Classificação dos dispositivos de E/S
Diferentes autores classificam os dispositivos de E/S de diferentes formas. Andrew S. Tanenbaum [1] agrupa os
dispositivos de acordo como os dados podem ser acessados e/ou obtidos a partir destes dispositivos. Agrupando-os em
dispositivos de blocos e dispositivos de caracteres.
- Os dispositivos de blocos são dispositivos que armazenam as informações em blocos de tamanho fixo, cada um
com seu próprio endereço. Os discos são exemplos de dispositivos de blocos comuns;
- Os dispositivos de caractere são aqueles que recebem fluxos de caracteres, sem considerar qualquer estrutura
de blocos. Estes não são endereçáveis e não dispões de qualquer operação de posicionamento. Impressoras,
interfaces de rede, mouses e a maior parte de outros dispositivos que são diferentes do disco podem ser considerados
dispositivos de caractere;
Já Stallings[4] classifica a grosso modo os dispositivos em três categorias, segundo a finalidade do dispositivo e como
ele interage com os outros dispositivos e/ou usuário, Human Readable, Machine Readable e Communications;
- Human readable, são dispositivos adequados para a comunicação com o usuário. Exemplos destes dispositivos
incluem teclados, mouses, impressora, monitor, etc...;
- Machine readable, são dispositivos adequados para comunicação com dispositivos eletrônicos. Exemplos destes
dispositivos são, disco rígido drivers de fita magnética, censores, controladores, cdroms, etc...;
- Communication, são dispositivos adequados para comunicação com dispositivos remotos. Exemplos são modens,
dispositivos para redes, etc...
Carpineli classifica os dispositivos de E/S em dispositivos de Entrada, dispositivos de Saída e dispositivos de Entrada
e Saída.
- Dispositivos de entrada são aqueles como o teclado que é apenas utilizado para inserir dados no sistema;
- Dispositivos de saída são aqueles como o monitor que são utilizados apenas para saída dos dados do sistema;
- Dispositivos de entrada e saída como os discos rígidos e modens, são utilizados tanto para entrada de dados como
para saída de dados no sistema.
3
2.3
2.3
Diferenças entre os Dispositivos de E/S
Diferenças entre os Dispositivos de E/S
Existem grandes diferenças entre os dispositivos. Dentre estas diferenças destacam-se:[4]
- Data rate (Taxa de transferência): É a taxa com que os dados são enviados ou recebidos pelo ou para o dispositivo.
Por exemplo, o teclado tem uma taxa de transferência inferior a 10 B/s, visto que esta taxa depende exclusivamente
da rapidez com que o usuário pressiona as teclas do teclado. Entretanto, um monitor pode receber dados com uma
velocidade de 75 MB/s [3];
- Application (Aplicação): A finalidade de cada dispositivo influencia no software e nas políticas do sistema operacional e nos utilitários de suporte. Por exemplo, um disco utilizado para arquivos requer o suporte de um software
de gerenciamento de arquivos. Um disco utilizado para armazenar páginas em um esquema de memória virtual
depende do uso de software e hardware para memória virtual;
Portanto, um mesmo dispositivo utilizado para finalidades diferentes pode apresentar a necessidade de tratamento
diferente. O que pode gerar aumento na complexidade de gerenciamento do mesmo;
- Complexity of control (Complexidade do controle): Por exemplo, uma impressora requer uma interface de controle
relativamente simples. Enquanto o controle de um disco é muito mais complexo;
- Unit of Transfer (Unidade de Transferência): Os dados podem ser transferidos em como um conjunto de bytes ou
caracteres ou em grandes blocos de dados;
- Data representation (Representação dos Dados): Diferentes abordagens para codificações de dados são utilizadas
por diferentes dispositivos, isto inclui diferenças nos códigos dos caracteres e convenções de paridade;
- Error conditions (Condições de erro): A natureza dos erros, o modo como estes são reportados, suas conseqüências
e o conjunto de respostas possíveis difere enormemente de um dispositivo para outro.
4
2.4
2.4
Interfaces de E/S
Interfaces de E/S
Os dispositivos de E/S precisam de um canal especial para comunicação para interfacea-los com a CPU. Isto para resolver as diferenças nas propriedades de cada dispositivo com as propriedades da CPU e memória. As maiores diferenças
entre os periféricos, a CPU e memória são:
1. Dispositivos de E/S grande parte das vezes são dispositivos eletromecânicos cuja forma de operação difere da CPU
e da memória, que são dispositivos eletrônicos;
2. A taxa de transferência dos dispositivos de E/S são usualmente diferentes da taxa de relógio (clock rate) da CPU.
Conseqüentemente existe a necessidade de mecanismos de sincronização;
3. O formato e o código dos dados nos periféricos diferem do formato das palavras na CPU e memória.
Para resolver estas diferenças, os sistemas computacionais incluem hardwares especiais entre a CPU e os dispositivos
de E/S. Este componentes são chamadas interface units pois elas são a interface entre o barramento da CPU e os dispositivos de E/S. Além disso, cada dispositivo tem seu próprio controlador ara supervisionar as operações de um mecanismo
particular daquele dispositivo. Por exemplo, o controlador de uma impressora controla a quantidade de papel, o tempo
da impressão e a quantidade de caracteres a serem impressos.
3
Estrutura de comunicação Dispositivos X CPU
Uma estrutura típica de comunicação entre a CPU e vários periféricos pode ser observada na Figura 1.
Data bus
Central
processing
unit
(CPU)
Address bus
Control
Interface
Interface
Interface
Interface
Keyboard
CRT
display
Printer
Magnetic
disk
Input
device
Output
device
Output
device
Input and Output
device
Figura 1: Simples estrutura de comunicação - barramentos.
É importante notar que esta figura será tomada como base para ilustrar as diferenças da diferentes abordagens da
função de E/S.
3.1
Barramentos
Como visto na figura anterior, todas as interfaces são diretamente conectadas nos barramentos de dados, endereço e
controle.
5
Neste caso, quando a CPU deseja acessar algum dispositivo em particular, ela coloca o endereço do dispositivo no
barramento de endereço. Todos os periféricos com endereços não correspondentes àquele inserido pela CPU, desabilitam
sua interface. Quando uma interface detecta seu próprio endereço, esta ativa as linhas de barramento e o dispositivo
que esta interface controla. No mesmo tempo que o endereço é colocado no barramentos de endereços, o processador
provê um código de função nas linhas de controle. A interface selecionada responde à este código de função e continua a
executá-la. Se dados precisam ser transferidos, a interface comunica-se com o dispositivo e o barramento de dados para
sincronizar a transferência.
Além disso, a CPU deve se comunicar com a unidade de memória através de um barramento de endereço, dados e
controle.
4
Estrutura de Comunicação Dispositivo X Memória X CPU
Existem três maneiras dos barramentos se comunicarem com a memória e os dispositivos de E/S.
• Memory-mapped I/O (E/S mapeada em memória): Onde os barramentos de dados, endereços e controle são comuns. Um espaço de endereçamento comum é compartilhado entre as interfaces e as palavras de memória, cada
qual tendo valores distintos. Computadores que possuem E/S mapeada em memória lêem e escrevem nas interfaces
como se estas fossem endereços de memória através do uso das mesmas instruções de leitura e escrita da memória.
• Isoled I/O configuration (Configuração de E/S isolada): compartilha os barramentos de dados e endereços, mas
com barramentos de controle separados. Estes computadores possuem linhas separadas de leitura e escrita para
memória e dispositivos de E/S.
• Independent Set of data, address and control buses (Conjunto de barramentos de dados, endereços e controle
independentes). Isso é possível através do uso de I/O Processors que serão discutidos posteriormente.
5
Sinais de Controle
A CPU, a interface e o dispositivo de E/S possuem diferentes clocks que não estão sincronizados. Assim, estas
unidades são ditas assíncronas entre si. A transferência assíncrona de informações ou dados entre duas unidades independentes requer que sinais de controle sejam transmitidos entre estas unidades para indicar quando cada dado esta sendo
transmitido. No caso da comunicação CPU-para-interface, os sinais de controle também precisam indicar o tempo no
qual o endereço é válido. Dois métodos, strobing e handshaking, serão abordados a seguir.
5.1
Strobing
Na Figura 2(a) a transferência é iniciada pela unidade de destino. Na região achurada no barramento de dados, estes
são inválidos. Além disso, a mudança no Strobe no final de cada flecha causa uma mudança no barramento de dados no
início de cada flecha.
A unidade de destino modifica o Strobe de 0 para 1. Quando o valor 1 do Strobe chega a unidade emissora, a unidade
responde colocando o dado no barramento de dados. A unidade de destino espera o dado ser disponibilizado, no pior
dos casos, um tempo fixo depois do Strobe ter sido setado para 1. Então, a unidade de destino captura os dados em um
registrador e modifica o Strobe de 1 para 0. Em resposta ao valor 0 do Strobe a unidade emissora retira os dados do
barramento.
Na Figura 2(b) a transferência é iniciada pela unidade emissora. Neste caso, a unidade emissora coloca os dados no
barramento. Após um curto intervalo de tempo requerido para os dados se estabilizarem no barramento, a unidade de
origem modifica o Strobe de 0 para 1. Em resposta ao Strobe modificado de 0 para 1, a unidade de destino transfere os
dados para um de seus registradores. A unidade emissora então modifica o Strobe de 1 para 0. Finalmente, após um curto
período de tempo requerido para garantir que a transferência dos dados para o registrador da unidade de destino tenha
6
5.2
Handshaking
Data bus
Destination unit
Source unit
Strobe
Data bus
Strobe
(a) Destination-initiated transfer
Data bus
Source unit
Strobe
Destination unit
Data bus
Strobe
(b) Source-initiated transfer
Figura 2: Transferência assíncrona através de Strobe.
sido realizada, a unidade emissora retira os dados do barramento de dados, completando assim a transferência.
Apesar de simples, o método de transferência de dados com o uso de strobe possui muitas desvantagens. Primeiro,
quando a unidade emissora inicia a transferência, não existe indicação de que os dados foram realmente capturados pela
unidade de destino. Isto é possível, através de uma falha de hardware, no qual a unidade de destino não recebe a mudança
no Strobe. Segundo, quando a unidade de destino inicia a transferência, não existe indicação para ela que a unidade emissora já tenha colocado os dados no barramento. Assim, a unidade de destino pode ler valores arbitrários do barramento
ao invés dos dados esperados. Finalmente, a velocidade com que cada uma das várias unidades responde pode variar.
Se existirem múltiplas unidades, a unidade que inicializar a transferência precisa esperar pelo atraso da mais vagarosa
unidade antes de modificar o Strobe para 0. Assim , o tempo tomado para toda transferência é determinado pela unidade
mais lenta.
5.2
Handshaking
O método handshaking usa dois sinais de controle para tratar o tempo das transferências. Além do sinal da unidade
que inicia a transferência, existe um segundo sinal de controle da outra unidade envolvida na comunicação.
O princípio básico de um processo de handshaking de dois sinais é como se segue. Uma linha de controle da unidade
que deseja iniciar a transferência é utilizada para requisitar uma resposta da outra unidade. A segunda linha de controle
da outra unidade é utilizada para avisar à outra unidade que a resposta esta acontecendo. Desta forma, cada unidade
informa a outra a respeito de seu status.
A Figura 3 mostra o processo de transferência de dados através do uso do handshaking. Na Figura 3(a), a transferên7
5.2
Handshaking
Data bus
Destination unit
Request
Source unit
Reply
Data bus
Request
Reply
(a) Destination-initiated transfer
Data bus
Source unit
Request
Destination unit
Reply
Data bus
Request
Reply
(b) Source-initiated transfer
Figura 3: Transferência assíncrona através de handshaking.
cia é inicializada pela unidade de destino. As duas linhas de handshaking são chamadas de Request (Requisição) e Reply
(Resposta). O estado inicial é quando ambas, Request e Reply estão desabilitadas e no estado 00. Os estados subseqüentes
são 10, 11 e 01. A unidade de destino inicia a transferência habilitando Request. A unidade emissora responde colocando
os dados no barramento. Após um curto período de tempo, necessário para estabilizar os dados no barramento, a unidade
emissora ativa Reply para sinalizar a presença de dados. Em resposta ao Reply a unidade de destino captura os dados do
barramento em um registrador e desabilita Request. A unidade emissora então também desabilita Reply e o sistema volta
ao estado inicial. A unidade de destino não pode fazer outra requisição até que a unidade emissora esteja pronta para
prover novos dados, o que é sinalizado desabilitando Reply.
A Figura 3(b) representa o handshaking de uma transferência inicializada pelo emissor. Neste caso, o emissor controla o intervalo entre quando o dado é aplicado no barramento e Request é modificado para 1 e quando o dado é retirado
do barramento e Request volta a 0.
O método de hakdshaking prove um alto grau de flexibilidade e confiabilidade pois completar com sucesso uma
transferência de dados necessita da participação ativa das duas unidades. Se uma unidade esta com problemas, a transferência não será completa. Um erro pode ser detectado através de mecanismos de time-out, que produz um alarme se
a transferência não for realizada em um período de tempo pré-determinado. O time-out é implementado quando uma
unidade habilita um dos sinais (Request ou Reply) de handshaking. Se o handshake de retorno não ocorrer em um dado
8
período de tempo, a unidade assume que um erro ocorreu.
O sinal de time-out pode ser utilizado para interromper a CPU e executar uma rotina que tome a devida ação para
recuperação do erro.
6
Organização da Função de E/S
As informações binárias recebidas de um dispositivo externo é são usualmente armazenadas em memória para posterior processamento. Informações transferidas da CPU para um dispositivo tem como origem a memória.
A CPU simplesmente executa as instruções de E/S e pode aceitar os dados temporariamente, mas o destino final ou a
origem dos dados é a memória.
Atualmente quatro técnicas podem ser utilizadas para possibilitar a E/S.
- Programmed I/O (E/S Programada)
- Interrupt-driven I/O (E/S por Tratamento de Interrupção)
- DMA - Direct Memory Access (ADM - Acesso Direto a Memória)
- I/O Processor - (Processador de E/S)
A seguir, será detalhado o funcionamento de cada uma das abordagens.
6.1
Programmed I/O
Quando o processador esta executando um programa e encontra uma instrução relacionada à E/S, este executa aquela
instrução através da aplicação de um comando à interface do dispositivo apropriado. Usualmente, a transferência é realizada entre um registrador da CPU e um registrador da interface do dispositivo ou através da CPU e memória.
Figura 4: E/S programada
Com a E/S programada, quando um dispositivo realiza as operações desejadas, ou possui informações que devem
ser enviadas ele as envia para sua interface que simplesmente seta um bit no registrador de status (geralmente chamado
de flag) indicando sua necessidade de troca de dados. Nem uma outra ação é tomada pela interface do dispositivo para
alertar o processador. Assim, é responsabilidade do processador chegar a flag de status da interface de tempos em tempo.
9
6.2
Interrupt-driven I/O
O fluxograma da figura 5 do programa que deve ser escrito para possibilitar a transferência de um conjunto de bytes
de um dispositivo que devem ser armazenadas na memória. O programa continuamente examina o status da interface até
que ele seja estado como 1.
Read status register
Check flag bit
0
Flag
1
Read data register
Transfer data to memory
Operation
completed?
No
Yes
Continue Program
Figura 5: Fluxgrama de E/S programada
Na E/S programada, o processador permanece em um loop de programa chamado busy-wait loop (loop de espera
ocupada) até que a interface do dispositivo indique que esta pronta para transferência.
A transferência de dados controlada por programa é utilizada somente em sistemas que são dedicados a monitorar
um dispositivo constantemente. A diferença entre a taxa de transmissão de informação entre a CPU e o dispositivo de
E/S torna este tipo de transferência ineficiente.
Segundo [Stallings], o problema com a E/S programada é que o processador tem que esperar um longo período de
tempo para que a interface do dispositivo esteja pronto, tanto para recepção quanto para o envio de mais dados. O processador, enquanto espera, precisa continuamente interrogar o status da interface. Como resultado, o nível de performance
de todo o sistema é severamente degradado.
6.2
Interrupt-driven I/O
Uma alternativa à E/S programada é a E/S dirigida à interrupção (alguns autores referenciam este método como
Transferência iniciada por interrupção). Com isso a CPU não precisa constantemente chegar a flag das interfaces dos dia10
6.3
DMA - Direct Memory Access
positivos, ao invés disso ele permite que as interfaces o informe de quando estão prontas para transmissão. O processador
então a execução do processo atual e executa a transferência de dados, como feito no caso de E/S programada. Após ter
efetuado a transmissão o processador volta ao processamento que estava efetuando antes de ter sido interrompido.
Para efetuar a E/S, o processador precisa armazenar o contexto (e.g., program counter and processor registers) do
programa corrente e executar um programa para o tratamento da interrupção. Por exemplo, o processador pode ler uma
palavra de dados da interface e armazenar na memória.
E/S dirigida à interrupção, apesar de mais eficiente do que a simples E/S programada, ainda requer a intervenção
ativa do processador para transferir informações entre a memória e uma interface, e qualquer transferência de dados deve
atravessar o caminho através do processador. Assim tanto a E/S programada quanto a E/S dirigida à interrupção sofrem
de duas desvantagens inerentes:
1. A transferência é limitada pela velocidade com que o processador consegue testar e servir um dispositivo;
2. O processador esta amarrado ao gerenciamento de uma transferência de E/S; muitas instruções precisam ser executadas em cada transferência de E/S.
6.3
DMA - Direct Memory Access
A transferência de blocos de informação entre um rápido dispositivo de armazenamento com um disco magnético e a
CPU pode preocupar a CPU e pode permitir que pouco, se algum, outro processamento possa ser executado. Removendo
a CPU do caminho e deixando que o dispositivo periférico gerencie os barramentos de memória diretamente aliviará a
CPU de muitas operações de E/S e irá permitir que o processador continue com outro processamento. Nesta técnica de
transferência, chamada Acesso Direto a Memória - ADM (Direct Memory Access - DMA). O controlador DMA obtém
os barramentos para controlar a transmissão diretamente entre o dispositivo de E/S e a memória. Como conseqüência o
processador é temporariamente privado de acessar a memória e controlar os barramentos de memória.
Quando o processador deseja ler ou escrever um bloco de dados, ele envia um comando para o módulo DMA através
do envio das seguintes informações:
• Se a operação é de leitura ou escrita;
• O endereço do dispositivo de E/S envolvido;
• O endereço inicial na memória para ler ou escrever os dados;
• O número de palavras que deve ser lido.
DMA pode capturar os barramentos de muitas formas. Um método comum e muito utilizado em microprocessadores
é desabilitar os barramentos através de sinais de controle especiais. A figura 6 mostra dois sinais de controle em uma
CPU que facilita a transferência via DMA. A requisição de barramento (BR) é utilizada pelo controlador DMA para
solicitar à CPU que libere o controle dos barramentos. Quando o BR é ativado, a CPU coloca o barramento de endereços,
de dados e as linhas de leitura e escrita em alta impedância. Depois disso, a CPU ativa o sinal de Barramento Garantido
(BG) para informar ao DMA que ele pode tomar o controle dos barramentos. Enquanto a linha BG estiver ativa, a CPU
não poderá proceder com qualquer operação que necessite acessar os barramentos. Quando o BR é desabilitado pelo
módulo DMA, a CPU retorna a sua operação convencional, desabilita a saída BG e toma controle dos barramentos.
Quando a linha BG é habilitada, o controlador DMA toma controle do sistema de barramentos para comunicação
direta com a memória. A transferência pode ser feita para um bloco inteiro de palavras memória, suspendendo a operação da CPU até que o bloco todo seja transferido, este processo é conhecido como burst transfer (transferência por
rajadas). Ou a transferência pode ser realizada uma palavra por vez entre execuções de instruções da CPU, um processo
chamado single-cycle transfer (transferência em um ciclo) ou cycle stealing (roubo de ciclo). A CPU meramente faz suas
operações no sistema de barramentos aguardar um ciclo de memória para permitir a transferência direta da memória-E/S
11
6.3
DMA - Direct Memory Access
Figura 6: Sinais de controle da CPU para DMA
para “roubar” um ciclo de memória.
Maiores informações sobre o controlador DMA podem ser encontradas em [3 pg 603].
A posição do controlador DMA em um sistema computacional é ilustrado na Figura 7.
Figura 7: Posição do DMA em um sistema computacional.
12
6.4
6.4
I/O Processor
I/O Processor
Ao invés de ter cada interface comunicando com a CPU, um computador pode incorporar um ou mais processadores
externos e atribuir a tarefa de comunicar diretamente com todos os dispositivos de E/S. Um I/O Processor (IOP) pode ser
classificado como um processador com capacidades de acesso direto a memória, que se comunica com os dispositivos de
E/S. Nesta configuração, o sistema computacional pode ser dividido em uma unidade de memória e vários processadores
composto de CPU e um ou mais IOPs. Cada IOP toma conta das tarefas de E/S.
O benefício derivado do uso de IOPs é o aumento da performance do sistema , atingido através da liberação da CPU
das tarefas detalhadas relativa à E/S.
Um IOP é similar a uma CPU, exceto que esta é desenvolvida para suportar os detalhes do processamento de E/S.
Ao contrário, do DMA que precisa ser inteiramente configurado pela CPU, o IOP pode buscar e executar suas próprias
instruções . Instruções de IOP são desenvolvidas especificamente para facilitar as transferências de E/S. Além disso, o
IOP pode fazer outras tarefas de processamento, como aritmética, lógica e tradução de nomes.
O diagrama de blocos de um computador com dois processadores pode ser visto na figura 8:
Figura 8: Diagrama de um computador com dois processadores.
A comunicação entre o IOP e os dispositivos é similar ao método de transferência controlada por programa (Programmed I/O). A comunicação com a memória é similar ao método de DMA.
A comunicação entre a CPU e o IOP pode ser feita de diferentes formas. Na maioria dos casos, a memória atua como
um centro de mensagens. Onde cada processador deixa mensagem para o outro. Um exemplo da seqüência de operações
que podem ser realizadas é ilustrada no fluxograma a da figura 9.
7
Finalidades do projeto do Sistema Operacional
Dois objetivos são pertinentes no desenvolvimento da facilidade de E/S: Eficiência e Generalidade.
7.1
Eficiência
É importante pois as operações de E/S geralmente forma o gargalo em um sistema computacional. A maioria dos
dispositivos de E/S são extremamente lentos comparados com a memória principal e o processador.
13
7.2
Generalidade
Figura 9: Fluxograma da tranferência usando IOP.
Uma forma de endereçar este problema é multi-programação, que, como nós temos visto, permite que alguns processos estejam esperando por operações de E/S enquanto outro processo esta executando. Entretanto, mesmo com o grande
tamanho da memória principal nos computadores de hoje, ainda será freqüente o caso em que a E/S não acompanha as
atividades do processador. Swapping é usado para carregar processos prontos adicionais para manter a CPU ocupada,
mas isso por si só é uma operação de E/S. A área que tem recebido a maior atenção, por causa de sua importância é a E/S
em disco.
7.2
Generalidade
Outro grande objetivo. No que diz respeito a simplicidade e ausência de erros, é desejável lidar com todos os dispositivos de uma maneira uniforme.Esta afirmação em ambos, o modo como cada processo vê os dispositivos de E/S e o
modo em que o sistema operacional gerencia os dispositivos de E/S e operações.
Por causa, da diversidade das características, é difícil na prática endereçar a verdadeira generalidade. O que pode
ser feito é usar uma abordagem hierárquica e modular para o projeto da função de E/S. Esta abordagem esconde muitos
dos detalhes do dispositivo de E/S em rotinas de baixo-nível de maneira que processos de níveis superiores do sistema
operacional vêem os dispositivos em termo de funções gerais como read, write, open, close,lock,unlock.
14
8
Bibliografia
[1] Tanenbaum, A. S.; Sistemas Operacionais Modernos - Modern Operating Systems; Editora LTC; tradução da
primeira edição.
[2] Carpinelli, J. D. Carpinelli; Computer Systems Organization & Architecture ;Addison Wesley; primeira edição
revisada.
[3] Mano, M. M. & Kime, C. R.; Logic and Computer Design Fundamentals; segunda edição revisada.
15
Roteiro – Gerenciamento de E/S
Introdução
GERENCIAMENTO DE ENTRADA E SAÍDA
E ESCALONAMENTO DE DISCO
Comunicação: Dispositivos X CPU
Comunicação: Memória X Dispositivos X CPU
Sinais de Controle
Organização da Função de E/S
Discentes: CASSIUS GOMES DE OLIVEIRA
LUIZ OTÁVIO DUARTE
Docente: JOSÉ CARLOS BECCENERI
Finalidades do Projeto do S.O.
Buffers de E/S
1
Roteiro – Gerenciamento de Disco
1
Introdução (1/2)
Introdução
●
Parâmetros de performance de disco
●
Políticas de escalonamento de disco
RAID
●
Disk cache
1
O controle e o gerenciamento adequado dos
dispositivos de entrada e saída, tornam
possiveis as abordagens vistas anteriormente;
É uma das funções do Sistema Operacinal
gerenciar e controlar todos os dispositivos de
Entrada e Saída (E/S);
Como existem muitos dispositivos diferentes,
cuja forma de atuação também difere, existe a
dificuldade em se prover um gerenciamento
eficiente e geral para estes dispositivos.
1
1
Introdução (2/2)
●
Classificação dos Dispositivos de E/S (1/2)
O que são periféricos?
–
Periféricos são dispositivos de entrada e saída
conectados a um computador de maneira “online”;
–
São ditos on-line todos os dispositivos que cuja
CPU controla diretamente.
–
●
●
Os dispositivos de E/S podem ser agrupados
de diferentes forma;
Tanembaum classifica os dispositivos em:
–
Dispositivos de Blocos;
–
Dispositivos de Caracteres.
Exemplo de periféricos: Teclado, Disco Rígido,
Display gráfico, etc...
1
Classificação dos Dispositivos de E/S (2/2)
●
●
Stallings classifica os dispositivos em:
–
Human Readable;
–
Machine Readable;
–
Communication.
Dispositivo de entrada;
–
Dispositivo de saída;
–
Dispositivo de entrada e saída.
Diferenças dos dispositivos de E/S
●
Carpinelli os classifica, simplesmente em:
–
1
1
Mesmo agrupados em qualquer um dos
métodos apresentados anteriormente, existem
muitas diferenças entre dispositivos de E/S:
–
Data Rate (Taxa de Transferência);
–
Application (Aplicação);
–
Complexity of Control (Complex. do Controle);
–
Unit of transfer (Unidade de Transferência);
–
Data representation (Representação dos dados);
–
Error Conditions;
–
...
1
2
Data Rate
●
Application
É a taxa que os dados são enviados de ou
para um dispositivo de E/S.
●
●
Dispositivos diferentes são desenvolvidos para
finalidades diferentes. Portando, necessítam
de softwares específicos.
Existem casos onde o mesmo dispositivo pode
ter mais do que uma aplicação.
–
Por exemplo, um disco utilizado para arquivos
requer o suporte de um software de
gerenciamento de arquivos. Um disco utilizado
para armazenar páginas em um esquema de
memória virtual depende do uso de software e
hardware para memória virtual;
1
Complexity of control
●
Unit of Transfer
Diferentes dispositivos possuem complexidade
diferente na maneira como são controlados.
–
1
●
Por exemplo, uma impressora requer uma
interface de controle relativamente simples.
Enquanto o controle de um disco é muito mais
complexo;
1
As unidades utilizadas pelos dispositivos de
E/S podem ser diferentes. Alguns dispositivos
podem transferir blocos inteiros de dados a
cada operação de entrada e saída. Outros
transferem caracteres ou bytes.
1
3
Data Representation
●
●
Errors Conditions
Diferentes abordagens para codificações de
dados
são
utilizadas
por
diferentes
dispositivos;
●
Diferenças nos códigos dos caracteres e
convenções de paridade.
●
A forma como os erros ocorrem, a maneira
como podem ser tratados, como são
reportados e seus significados difere de
dispositivo para dispositivo.
Por exemplo, uma impressora pode reportar
erros através de leds do próprio dispositivo,
enquanto o mouse não possui esse recurso.
1
Interfaces de E/S
●
1
Interfaces de E/S
São hardwares específicos para tratar
diferenças entre a CPU e os dispositivos de E/S.
Estas diferenças estão presentes no modo de
operação, na taxa de transmissão de dados e
o formato do código de cada periférico.
1
1
4
Roteiro – Gerenciamento de E/S
Comunicação: Dispositivos X CPU
Introdução
Comunicação: Dispositivos X CPU
Comunicação: Memória X Dispositivos X CPU
Sinais de Controle
Organização da Função de E/S
Finalidades do Projeto do S.O.
Buffers de E/S
1
Roteiro – Gerenciamento de E/S
1
Com: Dispositivos X CPU X Memória
Introdução
●
Comunicação: Dispositivos X CPU
Comunicação: Memória X Dispositivos X CPU
Sinais de Controle
Organização da Função de E/S
A estrutura de comunicação entre dispositivos,
CPU e memória pode ser através de:
–
Memory-mapped I/O (E/S mapeada em memória);
–
Isoled I/O configuration (configuração de E/S
isolada);
–
Independent Set of data, address and control
buses (Conjunto de barramentos de dados,
endereços e controle independentes).
Finalidades do Projeto do S.O.
Buffers de E/S
1
1
5
Roteiro – Gerenciamento de E/S
Sinais de Controle
Introdução
●
Comunicação: Dispositivos X CPU
Comunicação: Memória X Dispositivos X CPU
Sinais de Controle
Organização da Função de E/S
●
Finalidades do Projeto do S.O.
Buffers de E/S
Como a CPU e os dispositivos de E/S são
assincronos entre si. Existe a necessidade de
que sinais de controle sejam trocados entre as
unidades para sinalizar quando os dados e
endereços (no caso da CPU) são válidos.
Alguns métodos
sinalização:
–
Strobing
–
Handshaking
são
desenvolvidos
para
1
Strobing (1/3)
1
Strobing (2/3)
●
●
1
Este é um método onde uma única linha
adicional é utilizada para informar à outra
unidade quando os dados estão válidos no
barramento.
Desvantagens
–
Quando a unidade emissora inicia a transferência,
não existe indicação de que os dados foram
realmente capturados pela unidade de destino.
–
Quando a unidade de destino inicia a
transferência, não existe indicação para ela que a
unidade emissora já tenha colocado os dados no
barramento.
1
6
Strobing (3/3)
●
Desvantagens cont.
–
●
Handshaking (1/2)
A velocidade com que cada uma das várias
unidades responde pode variar. Se existirem
múltiplas unidades, a unidade que inicializar a
transferência precisa esperar pelo atraso da mais
vagarosa unidade antes de modificar o Strobe
para 0.
Para tentar suprir estas desvantagens existe um
segundo
modelo
conhecido
como
handshaking.
1
Handshake (2/2)
●
●
●
1
Comunicação Serial
O método handshaking usa dois sinais de controle
para tratar as transferências. Um da unidade que
inicia a transferência e outro da outra unidade.
●
O sinal de request requisita uma resposta da outra
unidade e o sinal de reply é a resposta ao request.
O método de hakdshaking prove um alto grau de
flexibilidade e confiabilidade pois completar com
sucesso uma transferência de dados necessita da
participação ativa das duas unidades.
●
●
1
A Comunicação entre as unidades pode ser
realizada de duas formas:
–
Paralela;
–
Serial.
Na forma paralela, cada bit da mensagem
possui seu próprio linha e toda mensagem é
enviada de uma única vez. É mais rápida mais
necessita de muito mais fios para realizar a
comunição
Comunicação Serial necessita de linhas de
sinalização como strobe ou handshake.
1
7
Comunicação Serial (1/2)
●
●
●
Comunicação Serial (2/2)
A transmissão serial é mais lenta, porém mais
economica.
Modos de transmissão serial:
–
Simplex;
–
Half-Duplex;
–
Full-duplex.
A transmissão de dados pode ser:
–
Assincrona, onde start bits e stop bits são enviados
antes de cada transmissão.
–
Sincrona, onde informações são sempre trocadas
pra manter as duas unidades sincronizadas.
1
Roteiro – Gerenciamento de E/S
1
Organização da função de E/S (1/2)
Introdução
Comunicação: Dispositivos X CPU
●
Comunicação: Memória X Dispositivos X CPU
Sinais de Controle
●
Organização da Função de E/S
Finalidades do Projeto do S.O.
Buffers de E/S
●
1
A memória em uma operação de E/S é sempre
o destino ou a origem dos dados da
transmissão.
As informações podem ser armazenadas
temporariamente na CPU, mas sendo a origem
ou o destino final a memória principal.
A maneira como a transmissão dos dados
entre os dispositivos e a memória é fator
determinante de desempenho do sistema.
1
8
Organização da função de E/S (2/2)
●
Programmed I/O (1/3)
Existem várias maneira da transferência de
dados ocorrer entre o dipositivo de E/S e a
memória principal. Quatro deles são:
●
Programmed I/O (E/S programada);
Interrupt-driven I/O (E/S por tratamento de
interrupção);
●
DMA – Direct Memory Access (ADM – Acesso
Direto a Memória);
IOP – I/O Processor (Processador de E/S).
Quando uma transferência é solicitada, um
programa é executado, este fica em um “busywait loop” até que a transferência seja
terminada.
Com isso o processador deve verificar
constantemente o status das interfaces. Em
sistemas
convencionais
onde
inúmeras
transferências de E/S são realizadas em um
curto periodo de tempo, esta abordagem não
é aconselhavel.
1
Programmed I/O (2/3)
1
Programmed I/O (3/3)
1
1
9
Interrupt-driven I/O (1/2)
●
●
●
Interrupt-driven I/O (2/2)
Não ocorre a necessidade de constantes
checagem
do
status
das
interfaces
constantemente.
●
Daisy chain para prioridade de interrupção:
Fica a cargo da interface “interromper” a CPU
quando os dados estiverem prontos para
serem transmitidos ou recebidos.
Mas, como na Programmed I/O, possui a
desvantagem de que todos os dados
necessitam atravessar a CPU.
1
Direct Memory Access (1/4)
●
●
1
Direct Memory Access (2/4)
A transferência de blocos de informação entre
dispositivos rápidos e a CPU pode permitir
que pouco, se algum, outro processamento
possa ser executado.
●
Removendo a CPU do caminho e deixando
que o dispositivo periférico gerencie os
barramentos diretamente aliviará a CPU de
muitas operações de E/S e irá permitir que o
outros processamentos.
Quando o processador deseja ler ou escrever
um bloco de dados, ele envia um comando
para o módulo DMA através do envio das
seguintes informações:
–
Se a operação é de leitura ou escrita;
–
O endereço do dispositivo de E/S envolvido;
–
O endereço inicial na memória para ler ou
escrever os dados;
–
1
O número de palavras que deve ser lido.
1
10
Direct Memory Access (¾)
Direct Memory Access
1
I/O Processor (1/2)
●
1
I/O Processor (2/2)
É um processador capaz de se comunicar com
a memória através de acesso direto e capaz de
comunidar com os dispositivos através de E/S
programada.
1
1
11
Roteiro – Gerenciamento de E/S
Finalidades do Projeto de E/S
Introdução
●
Comunicação: Dispositivos X CPU
Comunicação: Memória X Dispositivos X CPU
Sinais de Controle
Organização da Função de E/S
●
Finalidades do Projeto do S.O.
Eficiência:
–
Como operações de E/S são geralmente o gargalo
do sistema, a eficiência torna-se muito importante;
–
Uma das formas de de endereças esta finalidade é
através da multi-programação.
Generalidade:
–
A generalidade permite um maior grau de
simplicidade para o gerenciamento dos
periféricos;
–
Entretanto, na prática é muito difícil obter uma
grande generalidade. O que pode ser feito é
utilizar uma programação hierarquica e modular. 1
Buffers de E/S
1
Roteiro – Gerenciamento de E/S
Buffers de E/S
Introdução
●
Comunicação: Dispositivos X CPU
Comunicação: Memória X Dispositivos X CPU
Sinais de Controle
●
Organização da Função de E/S
Finalidades do Projeto do S.O.
Buffers de E/S
1
Sistemas que não possuem buffers de E/S
podem ter problemas com swapping e
paginação.
Algumas técnicas de buffers utilizadas são:
–
Single Buffering;
–
Double Buffering;
–
Circular Buffering.
1
12
Buffers de E/S
Buffers de E/S
1
Roteiro – Gerenciamento de Disco
1
Introdução
Introdução
●
Parâmetros de performance de disco
Políticas de escalonamento de disco
RAID
●
Disk cache
1
É o primeiro dispositivo de armazenamento
de dados em massa, não volatil, de
velocidade intermediaria para maioria dos
sistemas.
O disco rígido é dividido em pratos
magnetizados nas duas faces. Existem uma ou
mais cabeças de leitura.
1
13
Disco Rígido:
Disco Rigido: Endereçamento
●
●
O endereçamento de um byte de um disco
rígido leva em consideração o número do
cilindro, o número da cabeça de leitura, o
número do setor e o deslocamento dentro do
setor.
O enderçamento leva em consideração que o
número de setores por trilha é fixo.
Entretando nos discos de alta capacidade
atuais isso pode não ser verdade.
1
Roteiro – Gerenciamento de Disco
1
Parâmetros de performance de disco
Introdução
●
Parâmetros de performance de disco
Políticas de escalonamento de disco
RAID
Disk cache
1
Para medir o desempenho de um disco rígido
é necessário levar em consideração alguns
parâmetros como:
–
Seek Time;
–
Rotational Delay;
–
Access Time;
–
Transfer Time;
–
...
1
14
Seek Time
●
●
Rotational Delay
É o tempo requerido para a movimentação
das cabeças de leitura do cilindro atual ao
cilindro desejado.
●
●
O seek time pode ser aproximado por:
Ts = m . n + s
●
Onde: Ts = Estimativa do seek time
n = número de trilhas para atravessar
m = constante que depende do driver
s = startup time
Segundo Stallings os discos possuem velocidades de
3.600 rpm, o que significa uma rotação a cada 16.7
ms. No caso médio teriamos um rotational delay de
8.3 ms.
Entretanto atualmente é fácil encontrar discos que
possuem velocidades de 5.000 rpm; 7.200 rpm e até
de 15K rpm. No caso de 7.200 rpm teriamos uma
rotação a cada 8.3ms. E no caso médio teriamos um
rotational delay de 4.15ms.
1
Access Time
●
É a quantidade de tempo gasta para que o setor
desejado no dispositivo seja alcaçado.
1
Transfer Time
A soma do seek time, se existir com o
rotational delay é conhecido como Access
Time, o tempo para chegar à posição correta
para escrita ou leitura.
●
●
Uma vez que a cabeça esta na posição correta,
é o tempo tomado para que a operação de
leitura e escrita seja feita a medida em que o
setor se move debaixo da cabeça.
Pode ser resumido por:
T=b/rN
Onde:
1
T = tempo de tranferência
b = número de bytes a serem transferidos
N = número de bytes de uma trilha
r = velocidade de rotação por segundo
1
15
Average Access Time
●
Portanto, o tempo médio de acesso pode ser
expressado por:
●
Ta = Ts + 1/2r + b/rN
●
Levando-se em consideração um simples
exemplo de leitura de disco.
1) Se os dados que precisam ser obtidos estão
compactados e armazenados seqüêncialmente
dentro do disco. Ou seja, dentro da mesma trilha
com setores adjacentes. Se tivessemos que ler uma
trilha inteira de dados. Teriamos um tempo de
acesso: Ta = Ts + 1/2r + b/rN
Mas simples exemplos podem mostrar que to
tempo de acesso para um mesmo problema
pode variar enormemente dependendo da
localização física dos dados no disco.
2) Se os dados estão espalhados em setores
randomicamente dentro do disco. Teriamos um
tempo de acesso: Ta = (Ts + 1/2r + c/rN)*b/c
1
Comparação de tempo.
Onde: c é o número de bytes por setor.
1
Roteiro – Gerenciamento de Disco
Introdução
●
Considere um Ts médio de 20ms, um disco
com 3.600 rpm e 512bytes por setor e 32
setores por trilha. Qual o Ta para a leitura de
16KBytes de dados ?
Parâmetros de performance de disco
Políticas de escalonamento de disco
1) Ta = Ts + 1/2r + b/rN =
= 20ms + 8.3ms + 16.7ms = 45ms
RAID
2) Ta = (Ts + 1/2r + c/rN)*b/c =
Disk cache
= (20 + 8.3 + 0.52)*32 = 922.24ms
1
1
16
Políticas de Escalonamento de Disco
●
Escalonamento Randomico
Em um ambiente de multiprogramação onde filas de
requisições são mantidas, podemos implementar
políticas de escalonamento:
–
Random Scheduling;
–
First-in-First-out (FIFO);
–
Priority;
–
Last In First Out (LIFO);
–
Shortest Service Time First (SSTF);
–
SCAN;
–
C-SCAN;
–
N-Step-SCAN e FSCAN.
●
●
●
●
1
Prioridade
É a forma mais simples de escalonamento, que
significa que os itens da fila são processadas
de maneira seqüêncial.
●
É um algoritmo justo pois todas as requisições
serão atendidas e as requisições são atendidas
na ordem em que chegaram.
Entretanto a performance deste método
freqüêntemente irá se aproximar à do
escalonamento randomico.
Podemos esperar que as trilhas seja acessadas
randomicamente, obtendo a pior performance
possível.
1
First-in-First-out (FIFO)
●
É um escalonamento utilizado apenas para
comparação entre os outros algorítmos de
escalonamento.
●
1
Em um sistema baseado em prioridades, o
controle do escalonamento esta fora do
controle do software de gerenciamento de
disco.
Não tem a inteção de otimizar a utilização do
disco e sim alcançar outros objetivos do
sistema operacional.
1
17
Last In First Out (LIFO)
●
●
●
É uma política onde
requisição é tratada.
Shortest Service Time First (SSTF)
sempre
a
última
Esta política seleciona a requisição que requer a
menor movimentação do braço do disco
(deslocamento da cabeça de leitura) da
posição atual.
Em alguns sistemas atribuir ao dispositivo a
última requisição pode resultar em pouca ou
nenhuma necessidade de movimentação da
cabeça de leitura.
●
Entretanto existe risco de starvation quando
muitas requisições são enviadas ao disco.
●
Assim, pretende-se encontrar o menor seek
time.
Pode ocorrer risco de starvation quando a
requisição possuir um seek time muito grande.
1
SCAN
●
●
●
1
C-SCAN
A movimentação da cabeça de leitura é
realizada em apenas uma direção, até que a
última trilha seja encontrada.
●
Após isso a movimentação passa a ser no
sentido contrário.
●
O escaneamento é restrito a uma única
direção.
Quando a última trilha é encontrada em uma
direção, a cabeça de leitura retora ao inicio
oposto do disco.
É uma alternativa para tentar se prevenir
starvation quando requisições possuem um
seek time muito grande.
1
1
18
N-STEP-SCAN e FSCAN
●
●
(1/2)
N-STEP-SCAN e FSCAN
Em todas as abordagens vistas, é possível que
a cabeça de leitura não se mova por um
periodo consideravel de tempo. Isso pois,
podem haver processos que possuiem uma
grande taxa de acesso a uma únca trilha.
●
Para evitar este tipo de problema, a fila de
requisição pode ser segmentada.
●
N-Step-SCAN
–
Segmenta a fila de requisição em sub-filas de
tamanho N.
–
As subfilas são então processadas uma por vez
utilizando-se SCAN.
–
Novas requisições são inseridas a outra fila
enquanto a fila é processada.
FSCAN
–
São formadas duas filas.
–
Enquanto uma é tratada a outra é preenchida.
1
1
Roteiro – Gerenciamento de Disco
Introdução
Parâmetros de performance de disco
Políticas de escalonamento de disco
RAID
Disk cache
1
1
19
RAID 0 (Não redundante)
1
RAID 1 (Espelhado)
1
RAID 2 (Redundancia através de código de Hamming)
1
1
20
RAID 3 (bit-interleaved parity)
RAID (block-level parity)
1
RAID 5 (block-level distributed parity)
1
RAID 6 (dual redundancy)
1
1
21
Roteiro – Gerenciamento de Disco
Cache de Disco
Introdução
●
Parâmetros de performance de disco
Políticas de escalonamento de disco
●
RAID
É um buffer em memória principal para
setores do disco.
Ou seja, contêm uma cópia de alguns dos
setores do disco.
Disk cache
1
Least Recently Used (LRU)
●
1
Least Frequently Used (LFU)
É uma estratégia de realocação onde o bloco
que estiver em cache o maior tempo sem ser
referênciado deverá ser retirado. (O bloco
que estiver no final da pilha.)
●
●
●
●
O bloco mais recentemente referênciado é
colocado no top da pilha.
●
Quando um novo bloco é inserido no cache
ele assume o topo da fila.
1
Neste método o bloco que tiver sido
referênciado o menor número de vezes é
retirado quando um novo bloco é trazido
para a cache.
Um contador é associado a cada bloco e é
incrementado a cada acesso.
Possui problemas com blocos que são
referênciados muitas vezes em um curto
periodo de tempo e não são mais necessários
mas acabam não sendo descartados.
1
22
Obrigado!
1
23