1

Entrada/Saída

Capítulo 3

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

2

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)

3

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.

Obs: Esta classificação é apenas geral: nem todo dispositivo de E/S

se enquadra exatamente em uma dessas categorias. Por exemplo: Fitas de backup, Vídeo mapeado em memória, Modem, Interface de Rede etc.

7

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 física (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 para conjuntos de bytes –  Verificação da consistência dos dados (checksum) 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.

8

Arquitetura Conceitual Conceitualmente, é como se houvesse conexão direta entre CPU/Memória e todos os controladores

Em arquiteturas reais, existem vários barramentos e circuitos dedicados para seu acesso, que servem de ponte entre os barramentos

10

Controladores de Dispositivos

•  Cada controlador possui 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.

•  Registradores que compõem uma porta de E/S: –  Reg. de status (bits) –  Reg. de controle (bits) –  Reg. de entrada de dados (1-4 bytes) –  Reg. de saída 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 para interação com os 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.

11

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

Endereços de Portas de E/S em um PC

12

15

Passos de uma leitura de bloco controlada por CPU

1.  CPU escreve comando (p.ex., ler bloco de determinado endereço) em registrador do controlador de disco

2.  Controlador aciona a componente eletro-mecânica, e transfere os dados bit-a-bit do disco para um buffer do controlador

3.  Controlador calcula a checksum para verificar se há dados corrompidos. Se houver, faz nova leitura.

4.  Quando bloco de dados foi completamente lido, controlador levanta uma interrupção

5.  Driver executa loop para copiar byte-by-byte o bloco do controlador para a memória principal

Obs: o driver executa na CPU

17

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.

19

Acesso Direto à Memória (DMA)

Fig.: Operação de uma transferência com DMA (iniciada pela CPU)

20

Funcionamento do DMA Passo a passo de transferência de dados do dispositivo para a memória

usando DMA

21

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 do dispositivo e posterior

cópia para a memória alocada ao processo •  Cópia dos dados diratemente para 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)

23

Saida (Escrita em Impressora)

Passos da impressão de uma cadeia de caracteres

24

E/S Programada com Polling

Exemplo: Escrita de uma cadeia de caracteres para a impressora usando E/S programada

Software de E/S (driver) consulta repetidamente o status do dispositivo para saber quando dispositivo está pronto (pronto pare receber comando/dados)

Obs: p[] o vetor de caracteres na memória e printer_data_register e printer_status são a porta da controladora da impressora.

25

E/S Orientada à Interrupção

Escrita de uma cadeia de caracteres para a impressora usando E/S orientada à interrupção

a)  Código executado quando é feita a chamada ao sistema para impressão b)  Rotina de tratamento de interrupção

Interrupções indicam 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.

26

E/S Usando DMA

Impressão de uma cadeia de caracteres usando DMA a)  Código executado quando quando é feita a chamada ao sistema para impressão b)  Rotina de tratamento de interrupção

29

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

30

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

31

Camadas do Software de E/S

Fig.: Camadas do software de E/S

Modelo de Operação de E/S

33

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

34

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 é 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.

35

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 dispositivo possum um: –  major device number = índice 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)

39

Camadas do Software de E/S

Fig.: Camadas do software de E/S

40

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

Bufferização

Tratamento e notificação de falhas

Alocação e liberação de dispositivos dedicados Definição de tamanho único de bloco, independente de dispositivo

API e nomes uniformes •  Drivers precisam implementar uma interface (API) uniforme.

Isso permite isolar as especificidades dos dispositivos e instalar novos drivers

•  Chamadas de sistema para E/S como as de arquivos simplifica

o uso •  Arquivos especiais (em /dev) representam dispositivos de E/S

41

Seus i-nodes contém: Major device number = número do driver Minor device number = parâmetro do driver (a unidade do dispositivo)

•  Bits de controle de acesso rwx definem as permissões de acesso ao dispositivo

API para block devices: open, close, strategy, size e xhalt; API para character devices: open, close, read, write, ioctl, mmap, segmap, xpoll, xhalt

Software Independente do Dispositivo Provê vários serviços relacionados à E/S: escalonamento, uso de buffers e caches, spooling, alocação 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 para cache

Escalonador de E/S pode ter vários objetivos: –  Minimizar seek time do disco –  Priorizar E/S de certos processos –  Garantir iguais larguras de banda p/ acesso do disco para cada processo –  Garantir que certas requisicões serão procesadas antes de um certo

tempo

47

Software Independente do Dispositivo Tratamento de falhas: •  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 informação sobre natureza da falha

•  Para falhas transitórias, pode-se tentar repetir a operação de E/S, mas erros permanentes precisam ser tratados

Alguns controladores/drivers: •  informam a natureza da falha de hardware (tipo de erro de hardware, ou

requisição ilegal) •  geram logs de erros, que podem ser consultados. Exemplos de falhas: •  Requisição para um setor inexistente •  Setor de disco fisicamente danificado •  Impureza na superfície do disco •  Erro na busca (braço do cabeçote não se posicionou no cilindro correto) •  … 48

49

Software Independente de Dispositivo

a.  Sem buffer: E/S bloqueante e mono-programação b.  Buffer em espaço do usuário: E/S assíncrona, mono-programação c.  Buffer no driver e no processo: permite multi-programação d.  2 ou mais buffers no driver: permite paralelizar transferência dos dados

do dispositivo e cópia para processo

Bufferização: •  para compensar diferentes taxas de transferência (RAM vs dispositivo) •  para mapear quantidade de bytes da requisição a tamanhos de blocos

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

50

E/S com buffers •  E/S Orientada 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

•  E/S Orientada 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: na E/S de teclado: processar o efeito de DEL, ou CTRL,

ESC, etc.

53

Software Independente do Dispositivo Principais Funções:

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

Exemplos: APIs genéricas mapeadas para funções específicas.

54

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 caracteres, inteiros, float, etc.

Mas também há programas 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

55

Disco 3

E/S orientada a bloco: 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 •  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.

Disco 2 cilindro

Disco1

setor

trilha

57

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

Geometria física Geometria lógica

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

•  A fim de minimizar o seek time médio para várias requisições pendentes, deve-se escalonar as mesmas

•  O Escalonador de E/S de bloco executa um algoritmo de escalonamento de disco

59

Algoritmos de Escalonamento de Disco

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

Posição "inicial

Pedidos"pendentes

1) First-Come-First Served (FCFS): não há como otimizar tempo de posicionamento (seek time).

Ordem de Requisições: 11 1 36 16 34 9 12 Sequência de posicionamentos

60

Algoritmos de Escalonamento de Disco

Principal problema do Shortest Seek Time First: •  Se a chegada dos pedidos ocorre com distribuição

uniforme em todos 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 das extremidades levarão mais tempo para serem acessados do que dados em cilindros centrais.

Disco

Posição atual

PB PA PA > PB Posição atual

PB PA PA > PB

61

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

Algoritmo do Elevador

Variantes: 1.  Mover o cabeçote somente até o cilindro mais afastado

para 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 não há blocos escritos nos cilindros além dos

limites, é improvável que cheguem requisições para lá. 3.  Registrar quais foram os cilindros mais extremos usados

até então (cilmin, cilmax), e fazer a varredura dentro desse intervalo.

63

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

65

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 faz a rotação e quando cabeçote está sobre o setor 1, controladora já está pronta para receber esse setor.

68

Aumento de desempenho por paralelismo

•  Redundant Array of Inexpensive Disks (RAID) •  A controladora RAID opera vários discos sincronamente e

multiplica a taxa de atendimento de requisições •  Mais discos è maior probabilidade de falha do conjunto è requer

redundância de informacão •  Possibilita também a troca de discos sem parar o sistema (hot

swap) •  Faixa = conjunto de blocos (bytes, ou bits)

Faixas espelhadas em discos •  garante

redundância •  mas duplica a

qtde de discos

Como aumentar a taxa de atendimento de requisições ao disco?

Faixas consecutivas podem ser atendidas

em paralelo (sem redundância)

71

Redundância de Disco

Faixas de paridade espalhadas por todos os discos. •  Corrige blocos com defeito •  Requisições concorrentes de escrita

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) -> diminuindo a possibilidade de paralelismo

Fatiamento em blocos faz com que escrita 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 re-calculo do bloco de paridade.

Fatiamento em nível de blocos: blocos de paridade (XOR sobre o conteúdo dos blocos) em disco separado: •  Corrige blocos com defeito •  Disco único de paridade torna-se o

gargalo em requisições paralelas (acabam sendo sequenciais)

RAID 1+0 e 5+0

72

Animações Flash: http://www.fujitsu.com/global/products/computing/storage/eternus/glossary/raid/index.html

RAID 5+0

E/S Orientada a caracteres •  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

•  Alguns caracteres são de controle e precisam ser interpretados antes de serem consumidos pelo processo alvo.

79

81

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

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 caracter ao processo (incl. teclas

ctrl, alt, f1-f10, alt, shift,…) –  Sem modificações, sem eco (=mostrar o caracter digitado) –  Alguns programas usuários requerem esse modo: 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)

84

Software de Entrada

Caracteres tratados de forma especial no modo canônico

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

86

Pool de buffers Buffer dedicado para cada terminal

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)

E/S de Terminais orientados a caracter “echo” de caracteres no monitor

Driver teclado

Driver monitor

ESC seq.

echo

Interrupts and key numbers

read(mode,buff,1)

Raw/cooked Echo (Y/N)

controllers

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)

Saida para um terminal

•  O terminal aceita sequencias de escape (escape sequence), que embutem controles especiais (para cursor)

Exemplo: esc [ 3 ; 1 H esc [ 0 K esc [ 1 M

•  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.

Vá p/ posição (3,1)

Da tela

Apague a linha

Suba linhas seguintes em 1 linha

ESCAPE: 0x1B

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.

95

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

96

Hardware de Vídeo (1)

Para terminais/monitores mapeados na memória •  driver escreve diretamente na RAM de vídeo do monitor

97

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

104

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

112

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.

113

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.

114

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;

115

Modelando Impasses Essas 4 condições podem ser modeladas usando um Grafo

direcionado de Recursos (e processos)

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.

Impasse ⇔ se houver um ciclo no grafo!

116

Exemplo

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.

A ordem de alocação de recursos (escalonamento) determina ocorrência de impasse! Sejam 3 processos:

117

Estratégias para lidar com impasses 1.  Ignore o problema, e torça para que não ocorra!

•  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

2.  Detecção e Recuperação •  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) 3.  Prevenção de impasses

•  evite qualquer uma das 4 condições necessárias para impasses

4.  Alocação segura de recursos

118

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.  Exclusão Mútua: cada recurso é associado no máximo a um

processo; 2.  Condição segura & pede: O processo que é detentor de um

recurso pode solicitar novos recursos. 3.  Todos os recursos são não-preemtivos: somente o processo

de posse 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;

Vejamos métodos para (evitar) cada condição...

119

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

120

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)

121

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

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)

123

124

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.

125

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

126

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

127

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.

128

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).

Na prática, alguns das abordagens discutidas são combinadas: •  Agrupar recursos em classes e ordenar os recursos

em cada classe. •  Evitar espera circular para evitar impasse entre

classes de recursos

129