6/11/15
Capítulo 3
Entrada/Saída
3.1 Princípios do hardware de E/S
3.2 Princípios do software de E/S
3.3 Camadas do software de E/S
3.4 Impasses
3.5 Discos
3.6 Terminais com base em caracteres
1
Introdução
O controle da E/S é uma das tarefas centrais de um sistema
operacional, que:
•  emite comandos para os controladores de dispositivo,
processa interrupções e trata de erros
•  esconde detalhes específicos dos diferentes dispoitivos
para o resto do S.O. através de uma interface uniforme
•  tenta paralelizar E/S e processamento da CPU/Memória
para minimizar latência e maximizar vazão de dados no
acesso aos dispositivos de E/S
•  controla o acesso concorrente dos dispositivos
O sub-sistema de E/S consiste de duas camadas:
•  Software independente dos dispositivos (para cada classe
de dispositivo)
•  Software dependente do dispositivo (drivers)
2
1
6/11/15
Tipos de Dispositivo
O Dispositivo de E/S é definido por:
–  Conjunto de comandos básicos disponibilizados
–  As funções que executa
–  As mensagens de status/erro que emite
Existem os seguintes tipos de dispositivo:
Dispositivos de bloco = transferem ou armazenam dados em blocos
de tamanho fixo, cada bloco possui um endereço e cada bloco
pode ser acessado independentemente (acesso aleatório).
Exemplos: Discos (SCSI, IDE), CD/DVD, Fitas, SSDs
Dispositivos de caractere = lê ou escreve uma sequência de
caracteres. Cada caractere não possui endereço e não pode ser
acessado aleatoriamente. Para cada caractere (ou conjunto
pequeno deles), é gerada uma interrupção. Exemplos: Teclado,
Mouse, etc.
Interfaces de Rede: Exemplos: Ethernet, linha serial, WLAN, WMAN
Obs: Esta classificação é apenas geral: nem todo dispositivo de E/S
se enquadra exatamente nessas 2 categorias. Por exemplo: Fitas
de backup, Relógio, Vídeo mapeado em memória, etc.
3
Categorias de Dispositivos
Outra classificação#
•  Para Interação Homem-Computador
–  Teclado, mouse, Display
–  Impressoras
•  Para armazenamento e processamento interno
– 
– 
– 
– 
– 
Discos
Pen-drives
Sensores
Controladores
Atuadores
•  Para comunicação remota
–  Interfaces de rede (Ethernet, 802.11, Bluetooth, …)
–  Modems
2
6/11/15
Controladores de Dispositivos
•  Partes de dispositivos de E/S
–  Componente eletro-mecânico (motor, engrenagem, cabeçote
magnético, sensores, etc.)
–  controlador do dispositivo (um Circuito integrado ou processador)
•  A interface de hardware (pinos) entre o controlador e a componente
mecânica é padronizada (ISO, SCSI, IDE)
•  Um controlador pode fazer o controle conjunto de vários
dispositivos (componentes eletro-mecânicas)
•  Tarefas do controlador
–  converter fluxo serial de bits em conjuntos de bytes
–  Verificação da consistência dos dados (bits de pariadade) e correção
de erros
–  Bufferização: agrupar bloco de bytes para transferência para a
memória principal
•  Do ponto de vista conceitual, o controlador é o dispositivo de E/S.
7
Arquitetura Conceitual
Conceitualmente, é como se houvesse conexão direta entre CPU/
Memória com todos os controladores
Em arquiteturas reais, existem vários barramentos e
processadores dedicados para tirar a carga da CPU principal e
servir de ponte entre os barramentos
8
3
6/11/15
Arquitetura Real
Arquitetura de um Pentium
9
Controladores de Dispositivos
•  Cada controlador possui alguns registradores que são usados
para fazer o controle da E/S (da parte eletro-mecânica) e para
emitir informações sobre status e condições de erro.
•  Os registradores abaixo compõe uma porta de E/S:
– 
– 
– 
– 
Reg. de status (bits)
Reg. de controle (bits)
Reg. de entrada de dados (1-4 bytes)
Reg. de saida de dados (1-4 bytes)
•  Em algumas arquiteturas, o espaço de endereçamento da
memória RAM e das portas de E/S é único (E/S mapeada em
memória) Exemplo: Motorola 680x0
•  Em outras arquiteturas, existe um espaço de endereçamento
específico para E/S (fora da memória), usado apenas pelos
controladores.
•  A associação de um endereço com a porta de E/S de um
controlador é feita no circuito de decodificação de endereços do
barramento.
10
4
6/11/15
E/S mapeada na memória
Espaços de memória e E/S separados
•  As instruções de E/S (com esses endereços) ativam linhas do barramento para
selecionar o dispositivo e transferir os bits de/para registradores da porta de E/S.
E/S mapeada na memória:
•  Portas de E/S do dispositivo estão mapeados no espaço de endereçamento do
processador. Driver executa instruções para ler e escrever nas portas (=nos
registradores da controladora)
Híbrido: alguns dispositivos usam portas separadas e também espaço mapeado na
memória ( controlador gráfico)
11
Endereços de Portas de E/S em um PC
12
5
6/11/15
Interação CPU-Controlador
Funcionamento básico:
• 
• 
• 
CPU (executando o driver) inicia E/S:
escreve instruções (que especificam
byte/palavra a ser escrita em uma porta
de E/S). Por exemplo, instruções
assembly
IN Reg,Port, e
OUT Reg,Port
O controlador gera interrupções (e.g.
IRQ = Interrupt ReQuest line), avisando
quando seus registradores podem ser
lidos/escritos ou quando a E/S foi
finalizada
Tratador de interrupção (parte do driver)
verifica status/erro e faz a transferência
do próximo byte (entre Controladora e
Memória)
13
Direct Memory Access (DMA)
Em várias arquiteturas existe um componente de HW
dedicado à transferência direta de blocos de dados
para a memória - Direct Memory Access (DMA):
•  Evita que a CPU tenha que executar o loop para
transferência do bloco de/para a memória principal.
•  CPU apenas inicia E/S informando: endereço inicial
na memória, endereço do bloco no disco, número de
bytes a serem transferidos.
17
6
6/11/15
Componentes da controladora DMA
Acesso Direto à Memória (DMA)
Fig.: Operação de uma transferência com DMA (iniciada pela CPU)
19
7
6/11/15
Funcionamento do DMA
Passo a passo de transferência de dados do dispositivo para a memória
usando DMA
20
Acesso Direto à Memória (DMA)
Uma controladora de DMA acessa a memória diretamente: não
têm noção de memória virtual
Duas alternativas:
•  Cópia dos dados para buffer no driver e posterior cópia para
área do processo
•  Cópia dos dados diratemente um endereço do processo, mas
então precisa-se garantir que a(s) páginas destino permaneçam
na memória (não sejam swapped out)
21
8
6/11/15
Configurações de uso de DMA
•  Uma controladora de DMA pode servir vários dispositivos:
•  Exemplo: ISA DMA controller possui 8 canais DMA. Cada canal
DMA possui um address register, um count register, um control
register.
•  Controladores são associados estaticamente ou dinamicamente a
um canal de DMA.
Saida (Escrita em Impressora)
Passos da impressão de uma cadeia de caracteres
23
9
6/11/15
E/S Programada com Polling
Software de E/S (driver) consulta repetidamente o status do
dispositivo para saber quando dispositivo está pronto (pronto
pare receber comando/dados)
Exemplo: Escrita de uma cadeia de caracteres para a impressora usando
E/S programada
Obs:
p[] o vetor de caracteres na memória e
printer_data_register e printer_status a porta da controladora da impressora.
24
E/S Orientada à Interrupção
Interrupções ajudam a detectar quando uma operacão de E/S está
finalizada. Gerenciamento é implementado pela interação entre
o device driver e o procedimento de tratamento de interrupcões.
Escrita de uma cadeia de caracteres para a impressora usando E/S orientada à
interrupção
a) 
b) 
Código executado quando é feita a chamada ao sistema para impressão
Rotina de tratamento de interrupção
25
10
6/11/15
E/S Usando DMA
Impressão de uma cadeia de caracteres usando DMA
a) 
b) 
Código executado quando quando é feita a chamada ao sistema para impressão
Rotina de tratamento de interrupção
26
Menor envolvimento da CPU
•  Seja uma transferência de 6208 bytes de uma
controladora para a memória, com um barramento
PCI de 32 bits e DMA com buffer de 1KB.
•  Número de interrupções da E/S sofridas pela CPU
sem e com DMA:
–  Sem DMA: 1552 (= 6208/4)
–  Com DMA: 7
(6x transf. 1024 + 1x 64)
27
11
6/11/15
Princípios do Software de E/S
Objetivos do Software de E/S (1)
•  Independência de dispositivo
–  Programas podem acessar qualquer dispositivo de E/S sem
especificar previamente qual tipo/modelo/ fabricante do
dispositivo
•  Nomeação uniforme
–  Em Unix, accesso a drivers por aplicações em modo usuário
através do sistema de arquivos (dispositivos representados
como arquivos especiais a serem abertos)
–  Exemplos:
•  /dev/hda
•  /dev/hdb
•  /dev/ttya
•  Tratamento de erro
–  Erros devem ser tratados o mais próximo possível do
hardware
29
Objetivos do Software de E/S (2)
•  Transferências Síncronas vs. Assíncronas
–  transferências bloqueantes vs. orientadas a
interrupção
–  utilização de buffers para armazenamento
temporário
–  dados provenientes de um dispositivo muitas
vezes não podem ser copiados diretamente para
o destino final (memória do processo)
•  Gerenciar o acesso concorrente (e otimizado)
a dispositivos compartilhados
–  Disco, monitor, teclado, mouse e rede são
dispositivos de E/S compartilhados
–  unidades de fita não são
30
12
6/11/15
Camadas do Software de E/S
Fig.: Camadas do software de E/S
31
Modelo de Operação de E/S
13
6/11/15
Drivers de Dispositivo
Características/Tarefas dos Drivers:
–  Software para controle básico do controlador do dispositivo
–  Geralmente realizam o tratamento de interrupções geradas
pelo dispositivo
–  Encapsula as especificidades de controle do dispositivo
–  Para alguns dispositivos mantém uma fila de requisições
pendentes
–  Para discos, traduz requisições lógicas (leia bloco x) em
comandos específicos da controladora (p.exemplo: mova
para cilindro 3; leia a transfira dados dos setores 34-35 da
trilha 6)
–  Espera a chegada de interrupção, verifica integridade dos
dados e transfere dados de/para a região de memória do
processo
33
Drivers de Dispositivos
•  Drivers escrevem e lêm as portas
de E/S (comandos específicos,
parâmetros de controle e estado
do dispositivo)
Quando sistema é carregado, cada
driver:
•  Se registra junto ao núcleo e
verifica se o controlador do seu
dispositivo está conectado
(ativo).
•  Se não, o driver simplesmente
permanece inativo.
34
14
6/11/15
Drivers de Dispositivo
•  Disponibiliza uma interface API
padrão (de sistema de arquivos)
para o restante do sistema
•  As operações sobre arquivos
open(), read(), write(), close(),
seek(), release(), mmap() etc.
são mapeadas para os
procedimentos específicos de
cada driver.
•  Cada dispsoitivo possum um:
–  major device number = indice para
uma Device Diver Table e um
–  minor device number = parâmetro
que caracteriza o aparelho (mas
interpretação pode variar de driver
para driver)
35
Drivers de Dispositivo
•  É um software que é ligado ao núcleo (e muitas vezes
executa em modo supervisor)
•  Drivers fazem uso dos serviços do núcleo como alocação
de memória, tratamento de interrupção, buffers e filas de
espera
•  Não fazem uso de memória virtual !
•  Driver não pode confiar que o processo solicitante esteja
na memóra: por isso, as estruras de dados e os buffers
ficam em memória do núcleo.
36
15
6/11/15
Dispositivo Disco
•  Geometria física: menos setores nas trilhas internas
•  Geometria lógica: mesma quantidade de setores por trilha
38
Software de E/S Independente
de Dispositivo
Implementa funções e estruturas de dados usadas por
vários tipos de E/S e fornece uma interface uniforme para
as aplicações.
Funções típicas do software de E/S independente de
dipositivo
API uniforme para os drivers dos dispositivos
Armazenamento em buffer
Relatório dos erros
Alocação e liberação de dispositivos dedicados
Define tamanho de bloco único, independente de
dispositivo
39
16
6/11/15
API e nomes uniformes
•  Drivers precisam implementar uma interface abstrata (API)
uniforme. Isso permite instalar novos drivers
API para block devices: open, close, strategy, size e xhalt;
API para character devices: open, close, read, write, ioctl, mmap, segmap, xpoll, xhalt
•  Chamadas de E/S como as de arquivos simplifica o uso
•  Nome do arquivo especial (em /dev) é representado por um vnode
•  Entrada de v-node contém:
Major device number = referência ao driver
Minor device number = parâmetro do driver (a unidade do dispositivo)
•  Bits de controle de acesso rwx também definem as
permissões de acesso ao dispositivo
40
Arquivos Especiais (em Unix)
Para dispositivos de caracter e de bloco:
/dev/tty0, tty1
/dev/hda, hdb!
/dev/console !
!- Terminal devices!
!- hard drives!
! !
Para dispositivos de rede:
• 
• 
Seus nomes são padronizados (e refletem o tipo de interface), onde
múltiplos dispositivos são numerados sequencialmente (0, 1…)
Exemplos:
/dev/ethN
/dev/slN
/dev/pppN
! - Ethernet devices!
! - linhas seriais !
!- dispositivos PPP!
/dev/lo
!- loopback device
41
17
6/11/15
Registro de Drivers de Caracteres
• 
• 
• 
• 
• 
Mesmo disp. de caracteres são
acessados por chamadas de sistema
open(), read(), write(), close(), como se
fossem um arquivo
Quando dispositivo é inicializado, se
registra junto ao núcleo e adiciona
entrada em chrdevs (vetor de
device_struct).
O major device identifier é o índice para
esse vetor chrdevs
Cada device_struct contém ponteiro
para o device driver e um ponteiro para
um bloco de operacões em arquivo
(estas são endereços das rotinas do
driver específico)
Ao abrir um dispositivo, é chamado
mknode e criado um v-node/i-node
contendo o major e minor device
number, e que receberá em f_op o
endereço dos procedimentos no driver.
42
E/S de Bloco
43
18
6/11/15
Registro de Drivers de Bloco
• 
• 
• 
• 
• 
Drivers de bloco se registram em blkdevs, (análogo a chrdevs)
Lá, cada device_struct aponta tb para diferentes classes de block devices
(SCSI , IDE, etc.), cada uma com sua API específicas de operações
Cada driver de bloco fornece tb ponteiro para, request_queue, que aponta
para uma fila de requisições no buffer cache do núcleo.
É registrado tb uma única operacão (request_f), que informa ao núcleo o
procedimento do driver específico para ler/escrever um bloco.
Para agrupar blocos consecutivos, cada request aponta para um buffer
head. Buffer heads são encadeados quando se tratam de blocos
consecutivos (e contém toda infomação para driver processar a requisição)
vnode
blkdevs
driver1
requ_queue
Buffer-heads
head
request_f
requests
request_f
buffer-cache
44
Registro de Drivers de Rede
Arquivos especiais de rede não são criados por mknode, surgem
espontaneamente (quando interfaces de rede são ativadas e inicializadas)
Drivers de rede cadastram os dispositivos que controlam na inicialização das
interfaces de rede (NIC)
A estrutura de dados device contém informacões sobre o dispositivo de rede:
1.  Informacão de Barramento:
–  Numero IRQ, número de canal de DMA usado,
2. 
3. 
flags de interface IFF_ (descrevendo caracteristicas da interf. de rede)
informacão de protocolo, por exemplo:
– 
– 
– 
– 
mtu: tamanho máximo de pacote que consegue transmitir
family: familia de prtocolos que o disspositivo suporta (p.ex. AF_INET)
tipo de HW de interface: Ethernet, X.25, Token Ring, Slip, PPP and Apple
Endereços relevantes para uso da interface de rede (p.ex. MAC-Address)
4. 
Referência a fila de pacotes esperando para transmissão (socket buffer
sk_buff)
5.  Funções de apoio (usadas por camadas de protocolo superiores) como
setup, frame transmit, adicionar headers de frames, estatísticas, etc.
45
19
6/11/15
Software Independente do Dispositivo
Núcleos provêm muitos serviços relacionados a E/S: escalonamento,
uso de buffers e caches, spooling, reserva e liberacão de dispositivo e
tratamento de erros
Escalonamento de E/S:
–  Quando processo faz requisição de E/S em bloco essa é
enfileirada, por dispositivo
–  O Escalonador de E/S decide sobre a ordem de envio das
requisições para os discos, p/ otimizar acesso (aumentar vazão,
baixar o tempo médio de resposta das requisições)
–  Faz a busca antecipada de blocos
Podem ter vários objetivos:
– 
– 
– 
– 
Minimizar seek time do disco
Priorizar E/S de certos processos
Garantir fatias iguais de largura de banda de disco para cada processo
Garantir que certas requisicões serão procesadas antes de um certo
tempo
46
Software Independente do Dispositivo
Tratamento de Erros:
•  chamadas de E/S retornam não só um valor de sucesso (0/1), mas
também um código de erro (em Unix errno), com informacão sobre
natureza do erro
•  Para erros transitórios, pode-se tentar repetir a operação de E/S,
mas erros permanentes precisam ser tratados
Alguns controladores/drivers também:
•  informam a natureza do erro de hardware (tipo de erro de hardware,
ou requisição ilegal)
•  mantém logs de erros identificados, que podem ser consultados.
Alocação e liberacão de dispositivos dedicados:
Exemplo: DVD/CD, ou fita magnética
•  Um lock é setado no v-node.
•  Ao tentar abrir o arquivo especial em uso, o v-node indicará se o
dispositivo está em uso, e retornar um valor de erro do open
47
20
6/11/15
Software Independente de Dispositivo
Bufferização:
•  para compensar diferentes taxas de transferência (RAM vs dispositivo)
•  para impedir acesso direto ao dispositivo
a. 
b. 
c. 
d. 
Sem buffer: E/S bloqueante e mono-programação
Buffer em espaço do usuário: E/S assíncrona, mono-programação
Buffer no núcleo e no processo: permite multi-programação
n Buffers no núcleo: permite paralelizar transf do dispositivo e cópia
para processo
48
Buffer Circular
•  É a generalização do buffer duplo
•  Desacopla a taxa de transferência de dados da E/S da taxa de
consumo dos dados pelo processo destinatário
•  Usado para fazer a busca antecipada de blocos (provável
necessidade de blocos vizinhos)
•  Permite atender requisições de leitura de vários processos
49
21
6/11/15
E/S com buffers
•  Orientados a bloco (block-oriented)
–  Processo pode processar um bloco enquanto o outro está sendo lido
para memória
–  Buffers ficam residentes em memória RAM
–  Subsistema de E/S mantém associação entre requisições (c/ seus
blocos) e processos do usuário
–  Escalonador de E/S otimiza transferência de/para disco
•  Orientados a caracteres (character-oriented)
–  Uma linha é lida/escrita de cada vez (com CR- Carriage return)
sinalizando fim da linha
–  Os caracteres no buffer podem ser pré processados antes de serem
entregues para o processo (raw & cooked mode)
–  Exemplo: no E/S de teclado: processar o efeito de DEL, ou CTRL
+caracter, ESC, etc.
Software Independente do Dispositivo
Principais Funções:
Exemplos:
APIs genéricas mapeadas para funções
específicas.
Mapeamento de nomes simbólicos (/
dev/tty00) para os drivers
correspondentes
Permissões para acesso aos dispositivos
como de arquivos
Mapeamento de tamanho de bloco único para
tamanhos de setores variados em discos
diferentes.
Transferência controlada de bytes do disco
para interface de rede, compensando
diferentes taxas de dados de cada dispositivo
Gerenciamento de blocos livres nos
dispositivos de bloco (discos)
Funções para a bloqueio e liberação de
dispositivos dedicados
Se erro não pode ser compensado/contornado
pelo driver, deve informar ao programa do
usuário o tipo e erro
52
22
6/11/15
Suporte a E/S em modo usuário
Há suporte a E/S nas bibliotecas ligadas a programas do usuário (stdio, ioctl,
etc.)
Por exemplo a formatação da entrada e saída,
printf e scanf efetuam a contatenacão de strings, e a conversão de
octetos para aracteres, inteiros, float, etc.
Mas também há utilitários e processos (daemons), responsáveis por realizar uma
tarefa específica relacionada à E/S
Exemplos:
•  lpd - spool de arquivos para a impressão
•  inetd, ftpd, rshd, httpd, dhcpd - processos que tratam E/S com a rede
53
Estrutura do Disco
•  Cilindro: coleção de N trilhas (uma em cada superfície de disco)
•  Trilha: uma circunferência de raio T completa em uma
superfície de disco; contém número variável de setores (8-32
em floppies, milhares em HD)
•  Setor: uma parte de uma trilha (com número fixo de bytes)
O tempo de acesso a um setor depende essencialmente do tempo
de posicionamento do pente de leitores até o cilindro
correspondente e da velocidade de rotação do disco.
trilha
Disco1
Disco 2
cilindro
Disco 3
setor
54
23
6/11/15
Setores em um Disco
Geometria física de um disco (com dois tamanhos de setor)
vs geometria virtual
A controladora conhece a geometria física e faz o
mapeamento de um endereço lógico de bloco para o setor
correspondente
56
Desempenho no acesso ao Disco
O cabeçote precisa ser posicionado na trilha, no início do setor alvo.
Isso envolve:
•  Tempo de posicionamento (Seek time)
–  Tempo para posicionar o cabeçote na trilha
•  Latência rotacional
–  Tempo necessário para que o início do setor apareça abaixo do cabeçote
24
6/11/15
Algoritmos de Escalonamento
de Acesso ao Disco
• 
O tempo necessário para ler ou escrever um bloco de
disco é dominado pelo tempo de posicionamento do
cabeçote no cilindro alvo (seek time)
Cilindro m
Cilindro k
Disco
• 
• 
A fim de minimizar o seek time médio para várias
requisições, deve-se escalonar as mesmas
O Escalonador de E/S de bloco executa um algoritmo
de escalonamento de disco
58
Algoritmos de Escalonamento
de Disco
1) First-Come-First Served (FCFS): não há como otimizar
tempo de posicionamento (seek time).
2) Algoritmo Mais-Próximo-Primeiro (Shortest Seek Time First SSTF) :
– 
– 
– 
– 
Usa tabela indexada por cilindro com lista de requisições para cada cilindro
Enquanto move o cabeçote para um cilindro, novos pedidos vão chegando
Escolhe sempre o cilindro mais próximo do atual
Atende todos os pedidos para o cilindro corrente
Ordem de
Requisições:
11
1
36
16
34
9
12
Posição #
inicial
Pedidos#
pendentes
Sequência de posicionamentos
59
25
6/11/15
Algoritmos de Escalonamento
de Disco
Principal problema do Shortes Seek Time First:
•  Se a chegada dos pedidos ocorre com distribuição
uniforme em todas os cilindros, então:
•  Para discos muito utilizados, o cabeçote tenderá a permanecer nos
cilindros do meio, e mover-se com menor probabilidade (PB) para
os cilindros nos extremos.
•  Portanto, dados gravados em cilindros extremos levarão mais
tempo para serem acessados do que dados em cilindros do meio.
PB Posição
atual
PA
PA
PA > PB
Posição
atual
PB
PA > PB
Disco
60
Algoritmos de Escalonamento
de Disco
Algoritmo do elevador (SCAN):
•  Manter o sentido da movimentação até que não haja mais pedidos para
acesso em “cilindros a diante”
•  No sentido de movimentação, atende primeiro os cilindros mais
próximos
•  Um flag (UP/DOWN) registra o sentido de movimentação.
Ordem
chegada:
11
1
36
16
34
9
12
Sequência de posicionamentos
61
26
6/11/15
Algoritmo do Elevador
Variantes:
1.  Mover o cabeçote somente até o cilindro mais afastado
para a qual exista uma requisição
• 
Vantagem: ganha-se eficiência no atendimento global das
requisições
2.  Mover o cabeçote até o cilindro mais afastado,
independente de haver requisição
• 
• 
Vantagem: garante-se um tempo médio igual de atendimento
para requisições nos cilindros centrais e extremos do disco
Desvantagem: se nunca houve escritas em cilindros além dos
limites, é improvável que aconteçam requisições para lá.
3.  Guardar quais foram os cilindros mais extremos usados
até então (cilmin, cilmax), e fazer a varredura dentro desse
intervalo.
Algoritmos de Escalonamento
de Disco
Algoritmo Circular SCAN (C-SCAN)
•  Objetivo: prover um tempo de espera mais uniforme para todas as
trilhas
•  Como o SCAN, move o cabeçote de uma extremidade para outra,
atendendo todas as requisições no caminho.
•  Mas quando o cabeçote atinge o cilindro mais extremo, ele retorna ao
início do disco (sem atender a requisições)
Ordem
chegada:
11
1
36
16
34
9
12
Sequência de posicionamentos
63
27
6/11/15
Desempenho de Acesso: Formatação de
Disco
Defasagem de setor inicial de cada trilha deslocado daquele da trilha
anterior: para agilizar o acesso sequencial de setores em trilhas
consecutivas.
Leva em conta o atraso da movimentação entre trilhas adjacentes
69
Desempenho de Acesso: Formatação de
Disco
Algumas controladoras são incapazes de fazer entrada e saida de
seu buffer em paralelo.
•  Por isso, discos são formatados com setores entrelaçados (b) e
(c), para permitir E/S mais eficiente de setores consecutivos
•  Enquanto controladora copia blocos do setor 0 para memória,
disco rotaciona e quando cabeçote está no setor 1, controladora
já está pronta para receber esse setor.
70
28
6/11/15
Aumento de desempenho por paralelismo
Como aumentar a taxa de atendimento de requisições ao disco?
•  Redundant Array of Inexpensive Disks (RAID)
•  A controladora RAID opera vários discos (multiplica a taxa de
atendimento de requisições)
•  Mais discos è maior probabilidade de falha do conjunto è requer
redundância de informacão
•  Faixa = conjunto de blocos (bytes, ou bits)
Faixas consecutivas
podem ser atendidas
em paralelo (sem
redundância)
Faixas espelhadas
em discos
•  garante
redundância
•  duplica a qtde
de discos
73
Aumento de desempenho por paralelismo
Fatiamento em nivel de
bits:
Bits de dados (nos discos
0-3) e bits de paridade
(nos discos 4-6)
Usa o Código de
Hamming para correção
de erros.
Todos os discos operam de forma sincronizada
(mesma velocidade e posição)
Não é mais utilizado pois em toda operação todos os
discos precisam ser acessados (não consegue atender
requisições simultaneamente)
Escrita: calcula os bits
de paridade e escreve tb
nos discos 4-6
Leitura: lê os dados e os
bits de paridade e verifica
consistência
Se não houver, corrige os
bits incorretos
74
29
6/11/15
Aumento de desempenho por paralelismo
Fatiamento em nivel de
bytes:
Bytes de dados (nos
discos 0-2) e bytes de
paridade (no disco 3)
•  Menos discos de
paridade
Discos precisam girar sincronizados
Raramente utilizado pois também não é capaz de
atender requisições simultâneas
75
Redundância de Disco
Fatiamento em blocos faz com que atualização possa ocorrer
somente no disco do bloco e no disco de paridade.
Mas o bloco a ser atualizado e o de paridade precisam ser
previamente lidos para a controladora. Para permitir o reFatiamento em nível de blocos: blocos de
paridade (XOR sobre o conteúdo dos blocos)
calculo do bloco de paridade.
em disco separado:
•  Corrige blocos com defeito
•  Disco único de paridade torna-se o
gargalo em requisições paralelas
(acabam sendo sequenciais)
Faixas de paridade espalhados por
todos os discos.
•  Corrige blocos com defeito
•  Requisições paralelas podem ser
executadas em paralelo
RAID nivel 6
Semelhante a RAID 5 mas com dupla
paridade: redundância de faixas de
redundância
•  Pode tolerar a falha de até dois
discos.
•  Mais discos estarão envolvidos em um
update de um bloco (B1) ->
76
diminuindo a possibilidade de
paralelismo
30
6/11/15
RAID 1+0 e 5+0
RAID 5+0
Aimações Flash: http://www.fujitsu.com/global/products/computing/storage/eternus/glossary/raid/index.html
77
E/S Orientada a caracteres
•  De/para dispositivos como:
– 
– 
– 
– 
– 
Teclado
Mouse
Terminal orientado a caracter
Portas Seriais
Interface de rede
•  As requisições são para leitura/escrita caracter a caracter (e.g.
put(c), get (c))
•  Para compensar diferentes taxas de produção e consumo de
caracteres, utiliza-se buffers
•  Vários caracteres possuem um significado especial (caracteres
de controle), que precisam ser interpretados ou gerados
•  Para alguns dispositivos, esses caracteres devem ser
interpretados/ gerados nos buffers, antes de serem enviados
serem consumidos.
84
31
6/11/15
E/S Orientada a caracteres
buffers
Produtor de
caracteres
Cosmumidor
de caracteres
Caracter = byte codificando um evento/comando de E/S
Exemplos de pares Produtor/Consumidor:
•  Entrada:
–  (teclado/ programa_usuário),
–  (interface_rede/ programa_usuário)
•  Saída:
–  (Programa_usuário, monitor orientado a texto)
–  (Programa _usuário, interface_rede)
85
Teclado: Funcionamento de uma
entrada de dados
•  Controlador gera uma interrupção para avisar que
tecla foi acionada (e seu # obtido)
•  Driver copia um número (código de tecla
pressionada/solta) da controladora para buffer
interno
–  driver converte para código ASCII
–  muitos SOs fornecem mapas de teclas ou páginas de
códigos carregáveis (pois teclados têm códigos de teclas
não padronizadas)
•  Núcleo recebe uma requisição de leitura de um
processo, e repassa para driver
86
32
6/11/15
Etapas Entrada de um Teclado
Software de Entrada
•  Processamento de caracteres
–  Usuário digita hella← o
–  Teclado gera: hellactrl-Ho
–  Processo deve receber hellactrl-Ho
ou hello ?
•  Modo crú (raw mode)
–  Driver entrega diretamente cada catacter ao processo (incl.
teclas ctrl, alt, f1-f10, alt, shift,…)
–  Sem modificações, sem eco (=mostrar o caracter digitado)
–  Alguns programas usuários exigem: shell, vi, emacs, login (p/
senha)
•  Modo processado (cooked mode)
–  Caracteres são armazenados em buffer até que uma linha toda
tenha sido acumulada
–  Driver faz o processamento de caracteres especiais no buffer,
e ecoa o resultado na tela
–  POSIX padroniza o efeito de teclas especiais
–  É o modo canônico (default)
33
6/11/15
Software de Entrada
Caracteres tratados de forma especial no modo canônico
89
Modo Cozido
•  Driver precisa...
–  Bufferizar uma linha inteira antes de passa-la para o
processo
–  Processar caracteres de controle especiais
•  Ctrl-C, ERASE, Del, line-erase, Tab, shift
–  Ecoar o caracter digitado
–  Nova linha pode ser procesada em paralelo com o
processamento de linha anterior
•  Para isso, precisa de buffers internos de entrada
•  Bufferização é necessária para lidar com digitação antecipada:
•  enquanto linha está sendo processada, outra linha é digitada
e já pode ser lida)
•  processo consumidor ainda não está executando
34
6/11/15
Software de Entrada
Buffers no Driver de terminal
Duas abordagens de bufferização p/ digitação antecipada:
•  para computadores com muitos terminais
Manter um pool de buffers a serem usados por demanda
•  para computadores com 1 usuário:
Manter um buffer por terminal (e.g., 500 bytes)
Pool de buffers
Buffer dedicado para cada terminal
91
A estrutura streams
É um canal de comunicação full-duplex entre um processo do usuário
e um dispositivo (presente na maioria dos Unix)#
Benefício: uma estrutura que apoia a técnica modular e incremental
usada por drivers de dispositivos e protocolos de rede#
#
stream consiste de:#
• 
Cabeça do stream (stream head) - interface com o processo do usuário)#
– 
– 
• 
• 
write()/ read() – escreve/lê dados brutos no fluxo#
putmsg()/ getmsg() – envia/recebe uma mensagem para/de o fluxo#
Extremidade do Driver - interface com o dispositivo de E/S#
Zero ou mais módulos entre eles. Cada módulo contém uma fila de read e uma de
write.#
Os módulos provêm funções de processamento e são associados ao
fluxo com a chamada ioctl()!
Mensagens assíncronas para transferir dados entre as filas (exceto
se houver módulo com controle de fluxo)#
35
6/11/15
streams
• 
Independente do acesso bloqueante na cabeça
do fluxo, a extremidade do driver vai ser
alimentada com os dados a medida que chegam. #
#
write():!
Cabeça do fluxo (stream head) copia
dados brutos para uma mensagem e
passa para a fila do módulo abaixo.#
#
Essa cópia prossegue até que a msg ser
copiada para a extremidade do driver,
quando é então retirada da mensagem e
passada para o dispositivo.#
#
Se o stream têm controle de fluxo, então
write(0 bloqueará até que haja espaço na
fila adjacente.#
#
read():!
Cabeça do fluxo pega a próxima msg da
fila do módulo abaixo, e retorna para o
processo do usuário dados não
estruturados. Bloqueia se não houver
msg.#
#
Módulos inferiores vão empurrando as
mensagens em direção do processo do
usuário.#
#
Exemplo
Inserção de um módulo de
processamento de catacteres
no stream entre o processo
do usuário e o driver.#
#
Módulos são empurrados da
cabeça do fluxo para baixo
em modo Last-In_first-Out
(LIFO)#
#
#
#
#
#
#
Nesse exemplo, o módulo
recebe o comando para
remover todas as ocorrências
de x e X (e qualquer string)#
o Comando é configurado
usando a estrutura strioctl#
94
36
6/11/15
A estrutura Streams
Comandos configurados por ioctl() são
apresentados aos módulos (de cima para
baixo), até que se encontre um que tenha a
capacidade de processá-los.
Módulos podem ser usados por diferentes
streams, e diferentes dispostivos
•  Exemplo: um módulo de um protocolo de
rede pode ser usado para acessar
interfaces Ethernet ou WiFi (802.11)
•  Isso os faz apropirados para protocolos de
rede
•  Streams permitem “empacotar” fluxos de
caracteres em mensagens e com
padronização de comandos de controle
95
E/S de Terminais orientados a caracter
echo de caracteres no monitor
read(mode,buff,1)
controllers
Raw/cooked
Echo (Y/N)
Driver
teclado
echo
Driver
monitor
ESC seq.
Interrupts and key numbers
Questões:
•  Onde colocar o echo? Dado que outros programa tambem podem estar escrevendo no terminal?
•  E quando a entrada ultrapassa a largura da linha do terminal? Troca de linha ou truncar linha?
•  Diferença de velocidade entre entrada e o echo: Alguns terminais processam letras/numeros mais
rápido do que mudança de linha; então o driver do teclado deve inserir caracteres de prenchimento
(nulos)
37
6/11/15
Saida para um terminal
•  O terminal aceita sequencias de escape (escape sequence), que
embutem controles especiais (para cursor)
ESCAPE:
0x1B
Exemplo:
esc [ 3 ; 1 H esc [ 0 K esc [ 1 M
Vá p/
Apague a Suba linhas
seguintes
posição (3,1)
linha
em 1 linha
Da tela
•  Cada fabricante de terminal define sequencias ligeiramente diferentes
–  Dificulta fazer software independente do dispositivo
–  Unix usa arquivo termcap
•  É uma base de dados que gera as sequencias de escape para cada
fabricante.
Papel do termcap
Fazer a tradução de comandos genéricos de saída
para sequências de escape específicas para o tipo
de terminal sendo usado.
38
6/11/15
Software de Saída
Seqüências de escapes ANSI são usadas para
controlar navegação e edição em editores de texto
•  reconhecidas pelo driver do terminal
•  ESC é o caractere de escape ASCII (0x1B)
•  n,m, e s são parâmetros numéricos opcionais
100
Hardware de Vídeo (1)
Para terminais/monitores mapeados na memória
•  driver escreve diretamente na RAM de vídeo do monitor
101
39
6/11/15
Hardware de Vídeo (2)
• 
Uma imagem da RAM de vídeo
–  tela monocromática simples
–  modo caractere
• 
Tela correspondente
–  os x´s são bytes de atributos
• 
Para rolagem da tela: controladora mantém um registro
de qual palavra na memória VRAM corresponde ao
início da tela
102
Terminais conectados por rede
X Window System (X11)
X windows (MIT) foi um sistema cliente-servidor, onde terminais podiam ser
compartilhados por várias máquinas na rede.
Usuário do terminal X precisava autorizar seus programas remotos (nos clientes) a
jogarem a saída para uma janela do terminal.
No X Windows: entrada é empacotada em mensagens, transferida pela rede para o
cliente, que processa o dado e retorna resultado (output) também através de um
pacote
109
40
6/11/15
Impasses (Deadlocks)
Em várias situações o sistema operacional (ou um programa do
usuário) precisa ter acesso exclusivo a mais de um recurso ou
dispositivo. Por exemplo, para cópia direta de dados entre dois
dispositivos de E/S
Impasses podem ocorrer para vários tipos de recurso: arquivos,
dispositivo de E/S (fita, CD/DVD gravável) ou uma base de
dados
•  Exemplo em Banco de Dados:
–  Processo A faz lock em registro R1, e B faz lock em registro R2.
Quando A tenta adquirir R2, é bloqueado, e não libera R1. Assim, B
pode ficar bloqueado também
Recurso:: qualquer coisa que pode ser acessada por um único
processo a cada vez.
Um sistema tem vários tipos de recurso, e geralmente várias
instâncias de cada tipo. Cada instância poderá ser usada por
um único processo.
117
Impasses
Recurso preemptivo:: que pode ser tirado do processo que o está
usando sem causar problemas
Exemplo de recurso: memória principal
–  Processo pode ser swapped out
Recurso não-preemptivo:: não pode ser tirado do processo que o está
usando sem causar uma falha no processamento ou inconsistência
no estado do recurso
Exemplo de recursos: impressora, ou fita
•  Impasses só ocorrem com recursos não-preemptivos!
•  Esperas mútuas por recursos preemtivos podem ser resolvidos
realocando o recurso de um processo para outro.
•  Recursos não preemptivos são acessados em sessão crítica:
(Requisita recurso; Usa recurso; Libera recurso)
A requisição bloqueia enquanto o recurso está em uso por outro
processo.
118
41
6/11/15
Impasses
Definição de Impasse:
Se todos os processos de um conjunto estão bloqueados e esperando por
um recurso (uma liberação da SC) atribuído a outro processo do
mesmo conjunto pode fazer.
Quatro condições são necessárias para existência de um impasse:
1. 
Exclusão Mútua: cada recurso só pode ser atribuído a no máximo
um processo;
2. 
Condição segura&pede: O processo que é detentor de um recurso
pode solicitar outros recursos.
3. 
Todos os recursos são não-preemtivos: apenas o processo detentor
do recurso pode liberá-lo;
4. 
Espera circular: deve existir uma cadeia circular de dois ou mais
processos, cada um esperando por recursos sendo mantidos por
outro processo;
119
Modelando Impasses
Essas 4 condições podem ser modeladas usando um Grafo
direcionado de Recursos (e processos)
Impasse ⇔ se houver um ciclo no grafo!
Grafos de Recursos podem seu usados para verificar se uma certa
sequência de requisições de recursos leva a um impasse:
è Execute as requições passo-a-passo e verifique se em algum momento
obtém-se um ciclo.
120
42
6/11/15
Exemplo
A ordem de alocação de recursos (escalonamento) determina ocorrência de impasse!
Sejam 3 processos:
Se existe possibilidade de ocorrência de impasse o S.O. precisa criar um
escalonamento seguro de processos, i.e. suspender temporariamente um
processo.
è No exemplo: executar primeiro A e C, depois B.
121
Estratégias para lidar com impasses
1. 
Ignore o problema, e torça para que não ocorra!
• 
• 
• 
2. 
Detecção e Recuperação
• 
• 
3. 
A cada alocação de recurso (ou periodicamente) verifique
o Grafo de Recursos;
se houver um ciclo, termine um dos processos (e desfaça
seus efeitos colaterais nos recursos já alocados)
Prevenção de impasses
• 
4. 
Abordagem prática
Compromisso entre: probabilidade de ocorrência vs
impacto negativo sobre uso do sistema vs custo de
implementação
A maioria dos Sistemas Operacionais (incl. Unix/Minix)
seguem essa abordagem
evite qualquer uma das 4 condições necessárias para
impasses
Alocação segura de recursos
122
43
6/11/15
Prevenção de Impasses
Idéia: impor restrições sobre os processos/ recursos para evitar
ocorrência de qualquer uma das 4 condições necessárias:
1. 
2. 
3. 
4. 
Exclusão Mútua: cada recurso é associado no máximo a um
processo;
Condição segura & pede: O processo que é detentor de um
recurso pode solicitar novos recursos.
Todos os recursos são não-preemtivos: somente o processo
de posse do recurso pode liberá-lo;
Espera circular: deve existir uma cadeia circular de dois ou
mais processos, cada um esperando por recursos sendo
mantidos por outro processo;
Vejamos métodos para (evitar) cada condição...
123
Prevenção de Impasses
1. 
Evitar exclusão mútua:
Limite o acesso ao recurso a único processo (gerente), e.g. spooler de
impressora
...mas nem todos os recursos podem ser gerenciados dessa forma
Exemplo: se spooler também usa espaço em disco: se começa a imprimir
job1 antes de ter todos os dados em disco, um job de impressão
(job2) pode ocupar todo o espaço restante no disco e evitar que job1
conclua impressão
124
44
6/11/15
Prevenção de Impasses
2. 
Evitar condição Segura&Pede:
Alternativa 1: Faça com que cada processo requisite todos os recursos
antes de começar. Mas isso gera problemas:
• 
Pode ser impossível conhecer de antemão todos os recursos que
processo irá acessar.
• 
Alocação de recursos não será eficiente: recursos serão bloqueados
(lock) mesmo enquanto o processo estiver acessando outros
recursos
Alternativa 2: Se um processo quer requisitar um novo recurso, precisa
antes liberar temporariamente (e re-adquirir posse) de todos os
recursos que detém
• 
Problemas: Os recursos já alocados têm um estado (relacionado ao
acesso) que precisa ser mantido. Então, liberação temporária teria
que desfazer esse estado. Os processos seriam frequentemente
interrompidos e teriam que refazer suas operacões (èaumenta a
sobrecarga)
125
Prevenção de Impasses
3. 
Evite nâo-preempção:
Todos os recursos teriam que ser preemptivos, mas isso é impossível
(p.ex. Impressora, fita backup)
4. 
Eliminar condição de espera circular – de alguma forma:
Alternativa 1: garanta que cada processo mantenha um único recurso a
cada momento (isso limitaria formas de acesso)
Alternativa 2: defina uma ordem global dos recursos e garanta que todas
as alocações são feitas sempre seguindo essa ordem. Ciclo é
evitado pois se i≠j então: se A mantém Ri não irá requisitar Rj, ou se
B mantém Rj não irá requisitar Pi.
Variante: Em vez de impor uma ordem estrita de requisições garanta que
nenhum processo requisite um recurso com no. maior do que um
recurso que já possui. Problema:
Pode ser impossível conhecer de antemão todo o conjunto de recursos
potencialmente requisitados, impossibilitando uma ordenação prévia
126
45
6/11/15
Alocação segura de recursos
As demandas máximas de recursos de todos processos
precisam ser conhecidas de antemão
Duas abordagens:
•  Não inicie um processo se as suas demandas
máximas pode gerar um impasse
•  Não permita uma alocação incremental de recursos
se esta pode levar a um impasse (Algoritmo do
Banqueiro)
128
Alocação segura de recursos
O Algoritmo do Banqueiro (Dijkstra,65) determina uma
alocação segura de recursos de forma que impasses
nunca irão ocorrer.
Idéia princial:
–  Mantenha sempre suficientes recursos (estado seguro) de
maneira que sempre exista um processo que possa alocar todos
os recursos que precisa e assim possa terminar
•  Estado seguro:: é um estado de alocação de recursos tal
que exista uma sequência de estados futuros de alocação
dos recursos (e finalização dos processos) que garanta
que todos os processos em algum momento obterão
todos os recursos necessários e terminarão.
129
46
6/11/15
Algoritmo do Banqueiro
Exemplo para várias instâncias de único tipo de recurso (por
exemplo, $$):
Um banco dá crédito a fazendeiros até um limite máximo; clientes
sacam o dinheiro à medida que precisam dele; o banco precisa
garantir que sempre haverá suficiente dinheiro disponível em face
aos créditos concedidos.
Exemplo: Banco tem um total de 10 unidades (p.ex. R$ 10 milhões)
para todos os seus clientes.
Estado inicial
Estado seguro
Estado não seguro
130
Algoritmo do Banqueiro
Generalizando para recursos de vários tipos
• 
Usa 2 matrizes (de recursos alocados/e recursos ainda não alocados) e 3
vetores:
–  E: total de instâncias de cada tipo de recurso
–  P: total de instâncias alocadas de cada tipo de recurso
–  A: quantidades disponíveis de cada tipo de recurso
Existe a sequência de processos que conseguem terminar:
D ; A; {C, E}; {E,C}, B
131
47
6/11/15
Algoritmo do Banqueiro
Verificação se uma nova requisição de recursos (equivale
a saque de parte do empréstimo) vai levar a um
estado seguro:
1.  Procure por processo P (linha da matriz de recursos
não alocados) cuja demanda restante de recursos é
menor do que A. Se não existe tal processo, então
sistema pode entrar em impasse;
2.  Senão, assuma que P terminou, marque-o como tal, e
adicione o número máximo de recursos de P ao vetor
A.
3.  Repita passos 1 e 2 até que todos os processos foram
marcados como terminados, ou então verificou-se que
estado não é seguro è requisição não deve ser
atendida.
132
Algoritmo do Banqueiro
Trata-se de um trabalho teórico interessante ... Mas
raramente aplicado na prática.
Principais problemas:
–  Impossibilidade de conhecer de antemão as quantidades
máximas de recursos necessários para cada processo;
–  Teria que analisar todos os processos no sistema
–  O conjunto de instâncias de recursos é dinâmico
Existem abordagens mais pragmáticas para a
Prevenção de Impasses (p.ex. Bloqueio em 2 fases,
principalmente para bancos de dados)
–  Processo tenta bloquear todos os registros que precisa (fase
fase 1) de uma vez. Se um (ou mais) dos registros já está
bloqueado, processo aborta e tenta alocar novamente mais
tarde
–  Se tiver sucesso, faz os acessos e libera todos os registros
simultaneamente (fase 2).
133
48