FSO Aula02

Prévia do material em texto

FUNDAMENTOS DE 
SISTEMAS 
OPERACIONAIS
Parte 03
Prof. Gabriel Fernandes
gfernandes+estacio@gmail.com
GERENCIAMENTO DE 
MEMÓRIA
3
Gerenciamento de Memória
• Recurso importante;
• Tendência atual do software
• Lei de Parkinson: “Os programas se expandem para preencher a 
memória disponível para eles” (adaptação);
• Original: “o trabalho se expande para preencher o tempo 
disponível para ser concluído”
• Hierarquia de memória:
• Cache;
• Principal;
• Disco;
4
Gerenciamento de Memória
Hierarquia de Memória
• Cache
• Pequena quantidade 
• K/M bytes
• Alto custo por byte
• Muito rápida
• Volátil
• Memória Principal
• Quantidade intermediária
• M/G bytes
• Custo médio por byte
• Velocidade média
• Volátil
• Disco
• Grande quantidade –
• G/T bytes
• Baixo custo por byte
• Lenta
• Não volátil
5
Gerenciamento de Memória
• Para cada tipo de memória:
• Gerenciar espaços livres/ocupados;
• Alocar processos/dados na memória;
• Localizar dado;
• Gerenciador de memória: 
• Responsável por alocar e liberar espaços na memória para os 
processos em execução; 
• Responsável por gerenciar a troca de processos entre a memória 
principal (MP) e o disco, quando a MP não for suficiente para 
conter todos os processos;
6
Gerenciamento de Memória
• Monoprogramação:
• Sem definição de páginas: gerenciamento mais simples;
• Apenas um processo na memória;
Programa 
de usuário
0
0xFFF...
RAM
S.O.
S.O.
Programa
de usuário
DRIVERS
Programa
de usuário
S.O.
ROM
RAM
(a) (b) (c)
RAM
ROM
7
Gerenciamento de Memória
• Modelo de Multiprogramação:
• Múltiplos processos sendo executados;
• Eficiência da CPU;
Memória Principal - RAM
Processo
8
Gerenciamento de Memória
Grau de Multiprogramação
9
Gerenciamento de Memória
Partições/Alocação
• Utilizando Multiprogramação, a memória pode ser 
particionada de duas maneiras: 
• Partições fixas (ou alocação estática);
• Partições variáveis (ou alocação dinâmica);
• Partições Fixas: 
• Tamanho e número de partições são fixos (estáticos);
• Não é atrativo, porque partições fixas tendem a desperdiçar 
memória (Qualquer espaço não utilizado é literalmente perdido)
• Mais simples;
10
Gerenciamento de Memória
Partições Fixas
• Partições Fixas: 
• Filas múltiplas:
• Problema: filas não balanceadas;
• Fila única:
• Facilita gerenciamento; 
• Sempre que uma partição fica disponível, procura-se um job no começo 
da fila que caiba na partição
• Outra implementação, para evitar desperdício:
• Pesquisa toda a lista procurando pelo job que melhor se encaixa na partição
• Melhor utilização da memória, pois procura o melhor processo para a partição 
considerada;
• Problema: processos menores são prejudicados;
11
Gerenciamento de Memória
Partições Fixas
• Divisão da Memória em Partições Fixas:
partição 4
partição 3
partição 2
partição 1
S.O.
0
100 k
200 k
400 k
700 k partição 4
partição 3
partição 2
partição 1
S.O.
Filas
Múltiplas
Fila
Única
...
(a) (b)
12
Gerenciamento de Memória
Partições Fixas
• Partições Fixas: problemas com fragmentação:
• Interna: desperdício dentro da área alocada para um processo;
• Ex.: processo de tamanho 40K ocupando uma partição de 50k;
• Externa: desperdício fora da área alocada para um processo;
• Duas partições livres: PL1 com 25k e PL2 com 100k, e um processo de 
tamanho 110K para ser executado;
• Livre: 125K, mas o processo não pode ser executado; 
13
Gerenciamento de Memória
Partições Variáveis
• Partições Variáveis:
• Tamanho e número de partições variam;
• Otimiza a utilização da memória, mas complica a alocação e 
liberação da memória;
• Partições são alocadas dinamicamente;
• SO mantém na memória uma lista com os espaços livres;
• Menor fragmentação interna e grande fragmentação externa;
• Solução: Compactação;
14
Gerenciamento de Memória
Partições Variáveis
• Partições Variáveis:
SO
A
(a)
SO
A
(b)
B
SO
A
(c)
B
C
SO
(d)
B
C
SO
(e)
B
C
D
SO
(f)
C
D
SO
(g)
C
D
A
Tempo
Memória livre
15
Gerenciamento de Memória
• Minimizar espaço de memória inutilizados:
• Compactação: necessária para recuperar os espaços perdidos por 
fragmentação; no entanto, muito custosa para a CPU;
• Técnicas para alocação dinâmica de memória:
• Bitmaps;
• Listas Encadeadas;
16
Gerenciamento de Memória
• Técnica com Bitmaps:
• Memória é dividida em unidades de alocação em kbytes;
• Cada unidade corresponde a um bit no bitmap:
0 à livre
1 à ocupado
• Tamanho do bitmap depende do tamanho da unidade e do 
tamanho da memória;
• Ex.:
• unidades de alocação pequenas à bitmap grande; 
• unidades de alocação grandes à perda de espaço;
17
Gerenciamento de Memória
• Técnica com Bitmaps:
Memória livre
8 16
A B C ...Memória
1 1 1 1 1 0 0 0 
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1
...
1 1 1 1 1 0 0 0
Bitmap
Memória ocupada
18
Gerenciamento de Memória
• Técnica com Listas Encadeadas:
• Uma lista para os espaços vazios e outra para os espaços cheios, 
ou uma lista para ambos!
“espaço º segmento”
P 0 5 H 5 3 P 8 6 H 29 3 x.......
começa
com zero tamanho 5
Processo Hole
(espaço vazio)
começa
com 5
tamanho 3
19
Gerenciamento de Memória
• Algoritmos de Alocação à quando um novo processo é 
criado:
• FIRST FIT
• 1º segmento é usado;
• Rápido, mas pode desperdiçar memória por fragmentação;
• NEXT FIT
• 1º segmento é usado;
• Mas na próxima alocação inicia busca do ponto que parou 
anteriormente;
• SIMULAÇÕES: desempenho ligeiramente inferior;
20
Gerenciamento de Memória
• BEST FIT
• Procura na lista toda e aloca o espaço que mais convém;
• Menor fragmentação se os processos se encaixam perfeitamente nos 
espaços vazios, porém maior fragmentação se começar a sobrar 
poucos espaços;
• Mais lento;
• WORST FIT
• Aloca o maior espaço disponível; 
• QUICK FIT
• Mantém listas separadas para os espaços mais requisitados;
21
Gerenciamento de Memória
• Cada algoritmo pode manter listas separadas para 
processos e para espaços livres:
• Vantagem:
• Aumenta desempenho;
• Desvantagens:
• Aumenta complexidade quando espaço de memória é liberado –
gerenciamento das listas;
• Fragmentação;
22
Gerenciamento de Memória
• Multiprogramação à Vários processos na memória:
• Como proteger os processos uns dos outros e o kernel de todos os 
processos?
• Como tratar a relocação? 
• Todas as soluções envolvem equipar a CPU com um 
hardware especial à MMU (memory management unit);
23
Gerenciamento de Memória
• Relocação:
• Quando um programa é linkado (programa principal + rotinas do 
usuário + rotinas da biblioteca à executável) o linker deve saber 
em que endereço o programa irá iniciar na memória;
• Nesse caso, para que o linker não escreva em um local indevido, 
como por exemplo na área do SO (100 primeiros endereços), é 
preciso de relocação:
• #100 + Dà que depende da partição!!!
24
Gerenciamento de Memória
• Proteção:
• Com várias partições e programas ocupando diferentes espaços 
da memória é possível acontecer um acesso indevido;
• Solução para ambos os problemas:
• 2 registradores à base e limite
• Quando um processo é escalonado o registrador-base é carregado com 
o endereço de início da partição e o registrador-limite com o tamanho 
da partição;
• O registrador-base torna impossível a um processo uma remissão a 
qualquer parte de memória abaixo de si mesmo.
25
Gerenciamento de Memória
• 2 registradores à base e limite
• Automaticamente, a MMU adiciona o conteúdo do 
registrador-base a cada endereço de memóriagerado;
• Endereços são comparados com o registrador-limite
para prevenir acessos indevidos;
26
Gerenciamento de Memória
Registradores base e limite
b) MMU mais
sofisticada à
dois pares de 
registradores:
segmento de 
dados usa um 
par separado;
§ MMU 
modernas 
têm mais pares
de 
registradores.
27
Gerenciamento de Memória
• Tipos básicos de gerenciamento:
• Com troca de processos (swapping): Processos são movidos 
entre a memória principal e o disco; artifício usado para resolver o 
problema da falta de memória;
• Se existe MP suficiente não há necessidade de se ter troca de 
processos;
• Sem troca de processos: não há chaveamento;
28
Gerenciamento de Memória Swapping
• Swapping: chaveamento de processos inteiros entre a 
memória principal e o disco;
• Transferência do processo da memória principal para a memória 
secundária (normalmente o disco): Swap-out;
• Transferência do processo da memória secundária para a memória 
principal: Swap-in;
• Pode ser utilizado tanto com partições fixas quanto com partições 
variáveis; 
29
Gerenciamento de Memória
Alocando memória (tamanho)
a) segmento
de dados;
b) segmento
de dados e de
pilha;
30
Gerenciamento de Memória Memória 
Virtual (MV)
• Programas maiores que a memória eram divididos em 
pedaços menores chamados overlays;
• Programador define áreas de overlay; 
• Vantagem: expansão da memória principal;
• Desvantagem: custo muito alto;
31
Gerenciamento de Memória Memória 
Virtual (MV)
• Sistema operacional é responsável por dividir o programa 
em overlays; 
• Sistema operacional realiza o chaveamento desses 
pedaços entre a memória principal e o disco; 
• Década de 60: ATLAS à primeiro sistema com MV 
(Universidade Manchester - Reino Unido);
• 1972: sistema comercial: IBM System/370;
32
Gerenciamento de Memória Memória 
Virtual (MV)
• Com MV existe a sensação de se ter mais memória 
principal do que realmente se tem;
• O hardware muitas vezes implementa funções da 
gerência de memória virtual:
• SO deve considerar características da arquitetura;
33
Gerenciamento de Memória
Memória Virtual
• Espaço de Endereçamento Virtual de um processo é 
formado por todos os endereços virtuais que esse 
processo pode gerar;
• Espaço de Endereçamento Físico de um processo é 
formado por todos os endereços físicos/reais aceitos pela 
memória principal (RAM);
34
Gerenciamento de Memória
Memória Virtual
• Um processo em Memória Virtual faz referência a 
endereços virtuais e não a endereço reais de memória 
RAM;
• No momento da execução de uma instrução, o endereço 
virtual é traduzido para um endereço real, pois a CPU 
manipula apenas endereços reais da memória RAM à
MAPEAMENTO;
35
Gerenciamento de Memória
Mapeamento MV
• MMU: Realiza mapeamento dos endereços lógicos 
(usados pelos processos) para endereços físicos;
Processador MMU MemóriaPrincipal
Endereço
Lógico
Endereço
Físico
Unidade de Processamento
36
Gerenciamento de Memória Memória 
Virtual
• Técnicas de MV:
• Paginação:
• Blocos de tamanho fixo chamados de páginas;
• SO mantém uma lista de todas as páginas;
• Endereços Virtuais formam o espaço de endereçamento virtual;
• O espaço de endereçamento virtual é dividido em páginas virtuais;
• Mapeamento entre endereços reais e virtuais realizado pela MMU;
• Segmentação: 
• Blocos de tamanho arbitrário chamados segmentos;
37
Gerenciamento de Memória Memória 
Virtual - Paginação
• Memória Principal e Memória Secundária são 
organizadas em páginas de mesmo tamanho; 
• Página é a unidade básica para transferência de 
informação;
• Tabela de páginas: responsável por armazenar 
informações sobre as páginas virtuais:
• argumento de entrada à número da página virtual;
• argumento de saída (resultado) à número da página real (ou 
moldura de página - page frame);
38
Gerenciamento 
de Memória 
Memória Virtual 
Paginação Proces s o A
Esp aço d e
en dereça m en to
virtu a l d e A
En dereço v ir tu a l 1
.
.
.
Tab e la de
m a pea m en to
d e A
Esp aço d e
en dereça m en to
virtu a l d e B
En dereço v ir tu a l 1
.
.
.
Tab e la de
m a pea m en to
d e B
Proces s o B
Mem ór ia Pr in cip al
39
Gerenciamento de Memória
Memória Virtual
• Exemplo: 
• Páginas de 4KB 
• 4096 bytes/endereços (0-4095);
• 64KB de espaço virtual;
• 32KB de espaço real;
• Temos:
• 16 páginas virtuais;
• 8 páginas reais; 
40
Gerenciamento de Memória
Memória Virtual
Espaço de 
Endereçamento 
Virtual
Tamanho da 
página
Número de 
páginas
Número de 
entradas nas 
tabela de 
páginas
232 endereços
232 endereços
264 endereços
264 endereços
512 bytes
4 kbytes
4 kbytes
64 kbytes
223
220
252
248
223
220
252
248
Espaço Virtual X Tamanho da Página
41
Gerenciamento de Memória Memória 
Virtual - Paginação
• Problemas:
• Fragmentação interna;
• Definição do tamanho das páginas;
• Geralmente a MMU que define e não o SO;
• Páginas maiores: leitura mais eficiente, tabela menor, mas maior 
fragmentação interna;
• Páginas menores: leitura menos eficiente, tabela maior, mas menor 
fragmentação interna;
• Tamanhos possíveis entre 512 bytes a 64 KB;
• Mapa de bits ou uma lista encadeada com as páginas 
livres; 
42
Gerenciamento de Memória
Endereço Virtual à Endereço Real
§ MMU realiza o mapeamento
§ Página virtual mapeada para
página real;
43
Gerenciamento de Memória
Mapeamento da MMU
§ Operação interna de 
uma MMU com 16 
páginas de 4Kb;
§ Endereço virtual de 16 
bits: 4 bits para nº de 
páginas e 12 para 
deslocamento; 
§ Com 4 bits é possível ter 
16 páginas virtuais (24);
§ 12 bits para 
deslocamento
é possível endereçar os
4096 bytes;
44
Gerenciamento de Memória
Mapeamento da MMU
§ Número da página virtual 
é usado como índice; 
§ Se página está na 
memória RAM, então o nº 
da página real (110) é 
copiado para os três bits 
mais significativos do 
endereço de saída (real), 
juntamente com o 
deslocamento sem 
alteração;
§ Endereço real com 15 
bits é enviado à memória;
índice
45
Gerenciamento de Memória Memória 
Virtual - Paginação
• A Tabela de páginas pode ser armazenada de três 
diferentes maneiras:
• Em um conjunto de registradores, se a memória for pequena;
• Vantagem: rápido
• Desvantagem: precisa carregar toda a tabela nos registradores a cada 
chaveamento de contexto
• Na própria memória RAM à MMU gerencia utilizando dois 
registradores:
• Registrador Base da tabela de páginas (PTBR – page table base 
register): indica o endereço físico de memória onde a tabela está 
alocada;
• Registrador Limite da tabela de páginas (PTLR – page table limit 
register): indica o número de entradas da tabela (número de páginas);
• Dois acessos à memória; 
46
Gerenciamento de Memória Memória 
Virtual - Paginação
• Em uma memória cache na MMU chamada Memória Associativa; 
• Também conhecida como TLB (Translation Lookaside Buffer - buffer de 
tradução dinâmica);
• Hardware especial para mapear endereços virtuais para endereços 
reais sem ter que passar pela tabela de páginas na memória principal; 
• Melhora o desempenho;
47
Gerenciamento de Memória Memória 
Virtual - Paginação
• Estrutura de uma tabela de páginas (normalmente 32 
bits)
Identifica a página real;
Campo mais importante;
Número da Moldura de Página
48
Gerenciamento de Memória Memória 
Virtual - Paginação
Bit de Residência:
Se valor igual 1, então entrada válida para uso;
Se valor igual 0, então entrada inválida, pois 
página virtual correspondente não está na memória;
Número da Moldura de Página
• Estruturade uma tabela de páginas (normalmente 32 
bits)
49
Gerenciamento de Memória Memória 
Virtual - Paginação
Bits de Proteção:
Indicam tipos de acessos permitidos:
1 bit à 0 – leitura/escrita
1 – leitura
3 bits à 0 – Leitura
1 – Escrita
2 - Execução
Número da Moldura de Página
• Estrutura de uma tabela de páginas (normalmente 32 
bits)
50
Gerenciamento de Memória Memória 
Virtual - Paginação
Bit de Modificação (Bit M):
Controla o uso da página;
Se valor igual a 1, página foi escrita; 
página é copiada para o disco
Se valor igual a 0, página não foi modificada;
página não é copiada para o disco;
Número da Moldura de Página
• Estrutura de uma tabela de páginas (normalmente 32 
bits)
51
Gerenciamento de Memória Memória 
Virtual - Paginação
Bit de Referência (Bit R):
Controla o uso da página;
Auxilia o SO na escolha da página que deve deixar a MP (RAM);
Se valor igual a 1, página foi referenciada (leitura/escrita);
Se valor igual a 0, página não referenciada;
Número da Moldura de Página
• Estrutura de uma tabela de páginas (normalmente 32 
bits)
52
Gerenciamento de Memória Memória 
Virtual - Paginação
Bit de Cache:
Necessário quando os dispositivos de entrada/saída
são mapeados na memória e não em um endereçamento
específico de E/S;
Número da Moldura de Página
• Estrutura de uma tabela de páginas (normalmente 32 
bits)
53
Gerenciamento de Memória Memória 
Associativa (TLB)
1 140 1 RW 31
1 20 0 R X 38
1 130 1 RW 29
1 129 1 RW 62
1 19 0 R X 50
1 21 0 R X 45
1 860 1 RW 14
1 861 1 RW 75
Bit R
Página
Virtual Bit M
Página 
Física
Bits de
Proteção
Até 32/64 entradas
54
Gerenciamento de Memória 
Alocação de Páginas
• Quantas páginas reais serão alocadas a um processo?
• Duas estratégias:
• Alocação fixa ou estática: cada processo tem um número máximo 
de páginas reais, definido quando o processo é criado;
• O limite pode ser igual para todos os processos;
• Vantagem: simplicidade;
• Desvantagens: (i) número muito pequeno de páginas reais pode causar 
muita paginação (troca de páginas da memória principal); (ii) número 
muito grande de páginas reais causa desperdício de memória principal; 
55
Gerenciamento de Memória 
Alocação de Páginas
• Alocação variável ou dinâmica: número máximo de páginas reais 
alocadas ao processo varia durante sua execução;
• Vantagem: (i) processos com elevada taxa de paginação podem ter seu 
limite de páginas reais ampliado; (ii) processos com baixa taxa de 
paginação podem ter seu limite de páginas reais reduzido;
• Desvantagem: monitoramento constante; 
56
Gerenciamento de Memória 
Busca de Página
• Política de busca de página: determina quando uma página deve ser 
carregada para a memória principal
• Três estratégias:
• Paginação simples: 
• Todas as páginas virtuais do processo são carregadas para a memória principal;
• Assim, sempre todas as páginas são válidas;
• Paginação por demanda (Demand Paging): 
• Apenas as páginas referenciadas são carregadas na memória principal; 
• Quais páginas virtuais foram carregadas à Bit de controle (bit de residência);
• Página inválida;
• Paginação antecipada (Antecipatory Paging)
• Carrega para a memória principal, além da página referenciada, outras páginas 
que podem ou não ser necessárias para o processo
57
Gerenciamento de Memória 
Busca de Página
• Página inválida: MMU gera uma interrupção de proteção
e aciona o sistema operacional;
• Se a página está fora do espaço de endereçamento do processo, o 
processo é abortado;
• Se a página ainda não foi carregada na memória principal, ocorre 
uma falta de página (page fault);
58
Gerenciamento de Memória 
Busca de Página
• Falta de Página:
• Processo é suspenso e seu descritor é inserido em uma fila 
especial – fila dos processos esperando uma página virtual;
• Uma página real livre deve ser alocada;
• A página virtual acessada deve ser localizada no disco; 
• Operação de leitura de disco, indicando o endereço da página 
virtual no disco e o endereço da página real alocada;
59
Gerenciamento de Memória 
Busca de Página
• Após a leitura do disco:
• Tabela de páginas do processo é corrigida para indicar que a 
página virtual agora está válida e está na página real alocada;
• Pager: carrega páginas especificas de um processo do disco para a 
memória principal;
• O descritor do processo é retirado da fila especial e colocado na 
fila do processador; 
GERENCIAMENTO DE 
MEMÓRIA
Parte 04
Prof. Gabriel Fernandes
gfernandes+estacio@gmail.com
61
Gerenciamento de Memória 
Troca de Páginas
A
B
C
D
E
F
G
H
0
1
2
3
4
5
6
7
Memória Virtual
0
1
2
3
4
5
6
7
10
3
4
i
i
v
v
i
i
v
i
Tabela de Páginas 
Simplificada DG
Memória Principal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 
CPágina
Virtual
Página Real
62
Gerenciamento de Memória 
Troca de Páginas
• Se todas as páginas estiverem ocupadas, uma página 
deve ser retirada: página vítima;
• Exemplo: 
• Dois processos P1 e P2, cada um com 4 páginas virtuais;
• Memória principal com 6 páginas; 
63
Gerenciamento de Memória 
Troca de Páginas
0
1
2
3
A
B
C
D
Memória Virtual P1
0
1
2
3
3
2
4
v
v
v
i
Tabela de Páginas P2 
Simplificada0
1
2
3
E
F
G
H
Memória Virtual P2
D
A
F
E
G
B
Memória Principal
0
1
2
3
4
5
à P2 tenta acessar página 3! Falta de Página!
3 páginas de 
cada processo
0
1
2
3
1
5
0
v
v
i
v
Tabela de Páginas P1 
Simplificada
64
Gerenciamento de Memória 
Troca de Páginas
à Página 2 (virtual) é escolhida como vítima!
0
1
2
3
A
B
C
D
Memória Virtual P1
0
1
2
3
1
5
0
v
v
i
v
Tabela de Páginas P1 
Simplificada
0
1
2
3
E
F
G
H
Memória Virtual P2
0
1
2
3
3
2
4
v
v
i
v
Tabela de Páginas P2 
Simplificada
D
A
F
E
H
B
Memória Principal
0
1
2
3
4
5
3 páginas de 
cada processo
65
Gerenciamento de Memória 
Troca de Páginas - Paginação
• Algoritmos:
• Ótimo;
• NRU;
• FIFO;
• Segunda Chance; 
• Relógio; 
• LRU;
• Working set;
• WSClock; 
66
Gerenciamento de Memória 
Troca de Páginas - Paginação
• Algoritmo Ótimo:
• Retira da memória a página que tem menos chance de ser 
referenciada;
• Praticamente impossível de se saber;
• Impraticável;
• Usado em simulações para comparação com outros algoritmos;
67
Gerenciamento de Memória 
Troca de Páginas - Paginação
• Algoritmo Not Recently Used Page Replacement (NRU) 
ou Não Usada Recentemente (NUR)
• Troca as páginas não utilizadas recentemente:
• 02 bits associados a cada página à R (referência) e M 
(modificação)
• Classe 0 (R = 0 e M = 0) à não referenciada, não modificada;
• Classe 1 (R = 0 e M = 1) à não referenciada, modificada;
• Classe 2 (R = 1 e M = 0) à referenciada, não modificada;
• Classe 3 (R = 1 e M = 1) à referenciada, modificada;
• R e M são atualizados a cada referência à memória;
68
Gerenciamento de Memória 
Troca de Páginas - Paginação
• NRU:
• Periodicamente, o bit R é limpo para diferenciar as páginas que 
não foram referenciadas recentemente; 
• A cada tick do relógio ou interrupção de relógio;
• Classe 3 à Classe 1;
• Vantagens: fácil de entender, eficiente para implementar e fornece 
bom desempenho;
69
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo First-in First-out Page Replacement (FIFO)
• SO mantém uma listas das páginas correntes na memória;
• A página no início da lista é a mais antiga e a página no final da lista é a 
mais nova;
• Simples, mas pode ser ineficiente, pois uma página que está em 
uso constante pode ser retirada;
•Pouco utilizado;
70
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo da Segunda Chance
• FIFO + bit R;
• Página mais velha é candidata em potencial;
Se o bit R==0, então página é retirada da memória,
senão, R=0 e se dá uma nova chance à página colocando-a
no final da lista;
A DCB
0 73 8
1ª página Página mais recente
B ADC
3 87 10
1ª página Página mais recente
Se página A com
R==1; e
falta de página em
tempo 10;
Então R=0 e página A 
vai para final da lista;
tempo
71
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo do Relógio
• Lista circular com ponteiro apontando para a página mais antiga
• Algoritmo se repete até encontrar R==0;
Se R==0
- troca de página
- desloca o ponteiro
Se R==1
- R = 0
- desloca o ponteiro
- continua busca
72
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo do Relógio
73
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo Least Recently Used Page Replacement
(LRU) ou Menos Recentemente Usada (MRU)
• Troca a página menos referenciada/modificada recentemente;
• Alto custo
• Lista encadeada com as páginas que estão na memória, com as mais 
recentemente utilizadas no início e as menos utilizadas no final; 
• A lista deve ser atualizada a cada referência da memória;
74
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo Least Recently Used Page Replacement (LRU)
• Pode ser implementado tanto por hardware quanto por software:
• Hardware: MMU deve suportar a implementação LRU; 
• Contador em hardware (64 bits);
• Após cada referência à memória, o valor do contador é armazenado na tabela 
de páginas;
• Quando ocorre falta de página, o SO examina todos os contadores e escolhe 
a página que tem o menor valor
• Software: duas maneiras
• NFU (Not frequently used) ou LFU (least frequently used);
• Aging (Envelhecimento); 
75
Gerenciamento de Memória 
Troca de Páginas - Paginação
• Software: NFU ou LFU (least)
• Para cada página existe um contador à
iniciado com zero e incrementado a cada 
referência à pagina; 
• Página com menor valor do contador é candidata a troca; 
• Esse algoritmo não se esquece de nada
• Problema: pode retirar páginas que estão sendo referenciadas com 
freqüência; 
• Compilador com vários passos: passo 1 tem mais tempo de execução que 
os outros passos à páginas do passo 1 terão mais referências 
armazenadas; 
76
Gerenciamento de Memória 
Troca de Páginas - Paginação
• Software: Algoritmo aging (envelhecimento)
• Modificação do NFU, resolvendo o problema descrito 
anteriormente; 
• Além de saber quantas vezes a página foi referenciada, também 
controla quando ela foi referenciada;
• Geralmente, 8 bits são suficientes para o controle se as interrupções de 
relógio (clock ticks) ocorrem a cada 20ms (10-3);
77
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo aging
clock tick 0
1 0 1 0 1 1
10000000
10000000
00000000
10000000
00000000
10000000
0
1
2
3
4
5
a)
Bits R para páginas 0-5
clock tick 1
1 1 0 0 1 0
11000000
11000000
10000000
01000000
00000000
01000000
b)
clock tick 2
1 1 0 1 0 1
11100000
01100000
11000000
00100000
10000000
10100000
c)
clock tick 3
1 0 0 0 1 0
11110000
10110000
01100000
00010000
01000000
01010000
d)
clock tick 4
0 1 1 0 0 0
01111000
01011000
10110000
10001000
00100000
00101000
e)
Contadores
78
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo aging
clock tick 0
0 0 1 0 1 1
0
1
2
3
4
5
a)
Bits R para páginas 0-5
clock tick 1
1 0 0 1 1 0
b)
clock tick 2
1 1 0 1 1 1
c)
clock tick 3
1 0 1 0 1 0
d)
clock tick 4
0 1 1 0 0 0
e)
Contadores
79
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo Working Set (WS):
• Paginação por demanda à páginas são carregadas na memória 
somente quando são necessárias;
• Pré-paginação à Working set
• Carregar um conjunto de páginas que um processo está efetivamente 
utilizando (referenciando) em um determinado tempo t antes de ele 
ser posto em execução;
w(k,t)
WS
t1 t2
tempo
P1 P3 P4 P7 P8 P4
80
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo Working Set (WS):
• Objetivo principal: reduzir a falta de páginas 
• Um processo só é executado quando todas as páginas necessárias no 
tempo t estão carregadas na memória;
• SO gerencia quais páginas estão no Working Set;
• Para simplificar à o working set pode ser visto como o conjunto de 
páginas que o processo referenciou durante os últimos t segundos 
de tempo;
• Utiliza bit R e o tempo de relógio (tempo virtual) da última vez que 
a página foi referenciada;
81
Gerenciamento de Memória Troca de 
Páginas - Paginação
Tempo virtual atual (CVT): 2204
age = CVT – TLU 
(Ex.: 2204-2084 = 120)
τ = múltiplos clock ticks
Bit R
2084 1
1213 0
1980 1
2003 1
2014 1
2020 1
2032 1
1620 0
Tabela de Páginas
Tempo do último
Uso (TLU)
Percorrer as páginas examinando bit R;
Se (R==1)*
página foi referenciada;
faz TLU da página igual ao CVT;
Se (R==0 e age > τ)
página não está no working set;
remove a página;
Se (R==0 e age <= τ) **
página está no working set;
guarda página com maior age;
§ Algoritmo Working Set:
* Se todas as páginas 
estiverem com R==1, 
uma página é 
escolhida
aleatoriamente;
** Se todas as páginas
estiverem no WS, a 
página mais velha 
com
R==0 é escolhida;
82
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo WSClock:
• Clock + Working Set;
• Lista circular de molduras de páginas formando um anel a cada 
página carregada na memória;
• Utiliza bit R e o tempo da última vez que a página foi referenciada;
• Bit M utilizado para agendar escrita em disco;
83
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo WSClock: Tempo virtual atual: 2204
Tempo do último 
uso
2003 1
2084 1
1620 0
2032 1
1980 1
1213 0
2014 1
2020 1
Bit R
a)
2084 1
1620 0
2032 1
2003 1
1980 1
1213 0
2014 0
2020 1
b)
Se R==1
Então R=0 e ponteiro avança
84
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo WSClock: Tempo virtual atual: 2204
Tempo do último 
uso
2003 1
2084 1
1620 0
2032 1
1980 1
1213 0
2014 0
2020 1
Bit R
c)
2084 1
1620 0
2032 1
2003 1
1980 1
2204 1
2014 0
2020 1
d)
Nova páginaSe R==0 e age>t
Então M==0 (não agenda escrita) à troca
85
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo WSClock: Tempo virtual atual: 2204
2003 1
2084 1
1620 0
2032 1
1980 1
1213 0
2014 0
2020 1
c)
2084 0
2204 1
2032 1
2003 0
1980 0
1213 0
2014 0
2020 1
d)
Nova página
R==0 e age>t
M==1 (agenda escrita e continua procura)
86
Gerenciamento de Memória Troca de 
Páginas - Paginação
• Algoritmo WSClock: 
• Se todas estiverem com M==1; então escreve página atual no 
disco, e troca a página;
• Melhor desempenho à menos acessos ao disco;
GERENCIAMENTO DE 
MEMÓRIA
Parte 05
Prof. Gabriel Fernandes
gfernandes+estacio@gmail.com
88
Gerenciamento de Memória
Troca de Páginas
• Política de Substituição Local: páginas dos próprios 
processos são utilizadas na troca;
• Dificuldade: definir quantas páginas cada processo pode utilizar; 
• Política de Substituição Global: páginas de todos os 
processos são utilizadas na troca; 
• Problema: processos com menor prioridade podem ter um número 
muito reduzido de páginas, e com isso, acontecem muitas faltas de 
páginas;89
Gerenciamento de Memória
Troca de Páginas
• a) Configuração inicial;
• b) Alocação local;
• c) Alocação global;
90
Gerenciamento de Memória
Troca de Páginas
• Política de alocação local (número fixo de 
páginas/processo) permite somente política de 
substituição local de páginas
• Política de alocação global (número variável de 
páginas/processo) permite tanto a política de substituição 
de páginas local quanto global
91
Gerenciamento de Memória 
Troca de Páginas - Paginação
• Algoritmos de substituição local:
• Working Set;
• WSClock;
• Algoritmos de substituição local/global:
• Ótimo;
• NRU;
• FIFO;
• Segunda Chance;
• LRU;
• Relógio;
92
Gerenciamento de Memória
Implementação da Paginação
• Até agora, vimos somente como uma página é 
selecionada para remoção. Mas onde a página 
descartada da memória é colocada?
• Memória Secundária – Disco
• A área de troca (swap area) é gerenciada como uma lista de 
espaços disponíveis;
• O endereço da área de troca de cada processo é mantido na 
tabela de processos;
• Cálculo do endereço: MMU;
93
Gerenciamento de Memória
Implementação da Paginação
• Memória Secundária – Disco
• Possibilidade A - Assim que o processo é criado, ele é copiado 
todo para sua área de troca no disco, sendo carregado para 
memória quando necessário;
• Área de troca diferente para dados, pilha e programa, pois área de 
dados pode crescer e a área de pilha crescerá certamente;
94
Gerenciamento de Memória
Implementação da Paginação
• Memória Secundária – Disco (cont.)
• Possibilidade B - Nada é alocado antecipadamente, espaço é 
alocado em disco quando a página for enviada para lá. Assim, 
processo na memória RAM não fica “amarrado” a uma área 
específica;
95
Gerenciamento de Memória
Implementação da Paginação
Como fica o disco – memória secundária
Área de troca estática Área de troca dinâmica
96
Gerenciamento de Memória 
Tabela de Páginas Invertida
• Geralmente, cada processo tem uma tabela de páginas 
associada a ele à classificação feita pelo endereço 
virtual;
• Pode consumir grande quantidade de memória;
• Alternativa: tabela de páginas invertida;
• SO mantém uma única tabela para as molduras de páginas da 
memória;
• Cada entrada consiste no endereço virtual da página armazenada 
naquela página real, com informações sobre o processo dono da 
página virtual;
• Exemplos de sistemas: IBM System/38, IBM RISC System 6000, 
IBM RT e estações HP Spectrum;
97
Gerenciamento de Memória 
Tabela de Páginas Invertida
• Quando uma referência de memória é realizada (página 
virtual), a tabela de páginas invertida é pesquisada para 
encontrar a moldura de página correspondente;
• Se encontra, o endereço físico é gerado à
<i, deslocamento>;
98
Gerenciamento de Memória 
Tabela de Páginas Invertida
CPU
Memória
pid p d
Endereço lógico
i d
Endereço 
físico
Tabela de páginas invertida
pid pPesquisa
ýi
Endereço lógico: <id processo (pid), número página (p), deslocamento (d)>
99
Gerenciamento de Memória 
Tabela de Páginas Invertida
• Vantagens:
• Ocupa menos espaço;
• É mais fácil de gerenciar apenas uma tabela;
• Desvantagens:
• Aumenta tempo de pesquisa na tabela, pois, apesar de ser 
classificada por endereços físicos, é pesquisada por 
endereços lógicos;
• Aliviar o problema: tabela hashing;
• Uso da TLB (memória associativa) para manter entradas recentemente 
utilizadas;
100
Gerenciamento de Memória
Memória Virtual - Segmentação
• Segmentação: Visão do programador/compilador
• Tabelas de segmentos com n linhas, cada qual apontando para um 
segmento de memória;
• Vários espaços de endereçamento;
• Endereço real à base + deslocamento;
• Alocação de segmentos segue os algoritmos já estudados:
• FIRST-FIT;
• BEST-FIT;
• NEXT-FIT;
• WORST-FIT;
• QUICK- FIT;
101
Gerenciamento de Memória
Memória Virtual - Segmentação
• Segmentação:
• Facilita proteção dos dados;
• Facilita compartilhamento de procedimentos e dados entre 
processos;
• MMU também é utilizada para mapeamento entre os endereços 
lógicos e físicos;
• Tabela de segmentos informa qual o endereço da memória física do 
segmento e seu tamanho; 
102
Gerenciamento de Memória Memória 
Virtual - Segmentação
• Segmentação:
• Problemas encontrados à embora haja espaço na memória, não 
há espaço contínuo:
• Política de relocação: um ou mais segmentos são relocados para abrir 
espaço contínuo;
• Política de compactação: todos os espaços são compactados;
• Política de bloqueio: fila de espera;
• Política de troca: substituição de segmentos;
• Sem fragmentação interna, com fragmentação externa;
103
Gerenciamento de Memória Memória 
Virtual - Segmentação
Pilha
Árvore
de Parse
Livre
Constantes
Fonte
Tabela
de Símbolos
Tarefa: Compilação
Espaço de 
Endereçamento
Virtual
Tabela
de
Símbolos
Fonte
Constantes
Árvore
de
Parser
0k
20k
0k0k0k0k
12k
02k
16k
Pilha
12k
Segmentos (0-4)
104
Gerenciamento de Memória Memória 
Virtual - Segmentação
Editor
Segmento 0 Dados1
Segmento 1
Memória Lógica P1
Editor
Segmento 0 Dados2
Segmento 1
Memória Lógica P2
Limite Base
8850 90003
25286 43062
Tabela de Segmentos P2
0
1
Limite Base
4425 68348
25286 43062
Tabela de Segmentos P1
0
1 Editor
Dados 1
Dados 2
43062
68348
72773
90003
98553
Memória Física
105
Gerenciamento de Memória
Segmentação-Paginada
• Espaço lógico é formado por segmentos
• Cada segmento é dividido em páginas lógicas;
• Cada segmento possui uma tabela de páginas à mapear o 
endereço de página lógica do segmento em endereço de página 
física;
• No endereçamento, a tabela de segmentos indica, para cada 
segmento, onde sua respectiva tabela de páginas está;
106
Gerenciamento de Memória
Segmentação-Paginada
s p d
Tabela de Segmentos
Tabela de Páginas 
Segmento 0
Tabela de Páginas
Segmento 3
p.f d 
GERENCIAMENTO DE 
DISPOSITIVOS DE E/S
Prof. Gabriel Fernandes
gfernandes+estacio@gmail.com
108
Dispositivos de E/S 
Princípios de Software
• Organizar o software como uma série de camadas facilita 
a independência dos dispositivos:
• Camadas mais baixas apresentam detalhes de hardware:
• Drivers e manipuladores de interrupção;
• Camadas mais altas apresentam interface para o usuário:
• Aplicações de Usuário;
• Chamadas de Sistemas;
• Software Independente de E/S ou Subsistema de Kernel de E/S;
109
Dispositivos de Entrada e Saída
C on tro lado res
D ispo s it ivo s d e E/S
Proces s o
Sis tem a
 d e Arq u ivo s
D evice D rive r s
Su b s is tem a d e E/S
Operações d e E/S
M
od
o 
U
su
ár
io
M
od
o 
Ke
rn
el
In d epe n d en te
d o d isp os i t ivo
(a )
D ep en d en te
d o d isp os i t ivo
(b )
SO
FT
W
A
RE
H
A
RD
W
A
RE
110
Dispositivos de Entrada e Saída
C on tro lado res
D ispo s it ivo s d e E/S
Proces s o
Sis tem a
 d e Arq u ivo s
D evice D rive r s
Su b s is tem a d e E/S
Operações d e E/S
M
od
o 
U
su
ár
io
M
od
o 
Ke
rn
el
In d epe n d en te
d o d isp os i t ivo
(a )
D ep en d en te
d o d isp os i t ivo
(b )
SO
FT
W
A
RE
H
A
RD
W
A
RE
111
Dispositivos de E/S 
Princípios de Software - Camadas
• Drivers: 
• São gerenciados pelo kernel do SO;
• Contêm todo o código dependente do dispositivo;
• Controlam o funcionamento dos dispositivos por meio de 
seqüência de comandos escritos/lidos nos/dos registradores da 
controladora;
• Dispositivos diferentes possuem driversdiferentes;
• Classes de dispositivos podem ter o mesmo driver;
• São dinamicamente carregados;
• Drivers defeituosos podem causar problemas no kernel do SO;
112
Dispositivos de E/S 
Princípios de Software - Camadas
Comunicação feita
por barramento;
113
Dispositivos de Entrada e Saída
C on tro lado res
D ispo s it ivo s d e E/S
Proces s o
Sis tem a
 d e Arq u ivo s
D evice D rive r s
Su b s is tem a d e E/S
Operações d e E/S
M
od
o 
U
su
ár
io
M
od
o 
Ke
rn
el
In d epe n d en te
d o d isp os i t ivo
(a )
D ep en d en te
d o d isp os i t ivo
(b )
SO
FT
W
A
RE
H
A
RD
W
A
RE
114
Dispositivos de E/S 
Princípios de Software - Camadas
• Software de E/S no nível Usuário:
• Bibliotecas de E/S são utilizadas pelos programas dos usuários 
• Chamadas ao sistema (system calls);
115
Dispositivos de E/S 
Princípios de Software - Camadas
• Software Independente de E/S:
• Realizar as funções comuns a qualquer dispositivos;
• Prover uma interface uniforme para os drivers dos dispositivos
• Número de procedimentos que o restante do SO pode utilizar para 
fazer o driver trabalhar para ele;
• Fazer o escalonamento de E/S;
• Atribuir um nome lógico a partir do qual o dispositivo é identificado;
• Ex.: UNIX à (/dev)
• Prover buffering: ajuste entre a velocidade e a quantidade de 
dados transferidos; 
• Cache de dados: armazenar na memória um conjunto de dados 
freqüentemente acessados; 
116
Dispositivos de E/S 
Princípios de Software - Camadas
(a) Sem padrão de interface
(b) Com padrão de interface (uniforme)
117
Dispositivos de E/S 
Princípios de Software - Camadas
• Software Independente de E/S:
• Reportar erros e proteger os dispositivos contra acessos indevidos
:
• Programação: Ex.: tentar efetuar leitura de um dispositivo de saída 
(impressora, vídeo);
• E/S: Ex.: tentar imprimir em uma impressora desligada ou sem papel;
• Memória: escrita em endereços inválidos; 
• Gerenciar alocação, uso e liberação dos dispositivos à acessos 
concorrentes;
118
Dispositivos de E/S 
Princípios de Software
• Software Independente de E/S:
• Transferência de dados:
• Síncrona (bloqueante): requer bloqueio até que os dados estejam 
prontos para transferência;
• Assíncrona (não-bloqueante): transferências acionadas por 
interrupções; mais comuns;
• Tipos de dispositivos:
• Compartilháveis: podem ser utilizados por vários usuários ao mesmo 
tempo; Exemplo: disco rígido;
• Dedicados: podem ser utilizados por apenas um usuário de cada vez; 
Exemplo: impressora, unidade de fita; 
119Dispositivos de E/S - Ciclo de E/S
Pedido de E/S
Enviar pedido para driver,
bloquear processo se
necessário
Processar pedido, enviar
comandos para
controladora, configurar
controladora para bloquear
até interrupção
Monitorar o dispositivo,
interromper quando E/S
estiver concluída
E/S concluída, dados de
entrada disponíveis ou
saída concluída
Transferir dados (se
necessário) para o
processo, retornar código
de conclusão ou falha
Determinar que operação
de E/S foi concluída,
indicar mudança de estado
para o subsistema de E/S
Receber interrupção,
armazenar dados no buffer
se for entrada, sinalizar
para desbloquear driver de
dispositivo
E/S concluída, gerar
interrupção
Pedido pode ser
atendimento
imediatamente?
Chamada de sistema
Comandos da controladora
Sim
Não
Interrupção
Processo de
usuário
Subsistema de E/S
do Kernel
Subsistema de E/S
do Kernel
Driver
Controladora
TEMPO
Rotina de
Tratamento de
Interrupção
120
Dispositivos de E/S - Ciclo de E/S
Sequência da Figura anterior
• Um processo emite uma chamada de sistema bloqueante (por 
exemplo: read) para um arquivo que já esteve aberto (open);
• O código da chamada de sistema verifica os parâmetros. Se os 
parâmetros estiverem corretos e o arquivo já estiver no buffer
(cache), os dados retornam ao processo e a E/S é concluída;
• Se os parâmetros estiverem corretos, mas o arquivo não estiver no 
buffer, a E/S precisa ser realizada;
• E/S é escalonada;
• Subsistema envia pedido para o driver; 
121
Dispositivos de E/S - Ciclo de E/S
Sequência da Figura anterior
• Driver aloca espaço de buffer, escalona E/S e envia comando para a 
controladora do dispositivo escrevendo nos seus registradores de 
controle;
• Driver pode usar a DMA;
• A controladora do dispositivo opera o hardware, ou seja, o dispositivo 
propriamente dito;
• Após a conclusão da E/S, uma interrupção é gerada;
• A rotina de tratamento de interrupções apropriada recebe a 
interrupção via vetor de interrupção, armazena os dados, sinaliza o 
driver e retorna da interrupção;
122
Dispositivos de E/S - Ciclo de E/S
Sequência da Figura anterior
• Driver recebe o sinal, determina qual pedido de E/S foi concluído, 
determina o status e sinaliza que o pedido está concluído;
• Kernel transfere dados ou códigos de retorno para o espaço de 
endereçamento do processo que requisitou a E/S e move o processo 
da fila de bloqueados para a fila de prontos;
• Quando o escalonador escalona o processo para a CPU, ele retoma 
a execução na conclusão da chamada ao sistema.
123
Dispositivos de E/S - Discos
• Cada superfície é dividida em 
trilhas;
• Cada trilha é dividida em setores ou
blocos (512 bytes a 32K);
• Um conjunto de trilhas (com a 
mesma distância do eixo central) 
formam um cilindro;
• Cabeças de leitura e gravação; 
• Tamanho do disco: 
nº cabeças (faces) x 
nº cilindros (trilhas) x 
nº setores x 
tamanho_setor; 
Disco Magnético
superfície
cabeçote
124
Dispositivos de E/S - Discos
• Discos Magnéticos:
• Grande evolução em relação a:
• Velocidade de acesso (seek): tempo de deslocamento do cabeçote até 
o cilindro correspondente à trilha a ser acessada;
• Transferências: tempo para transferência (leitura/escrita) dos dados; 
• Capacidade;
• Preço;
125
Dispositivos de E/S - Discos
• Técnica para reduzir o tempo de acesso: entrelaçamento 
(interleaving):
• Setores são numerados com um espaço entre eles;
• Entre o setor K e o setor K+1 existem n (fator de entrelaçamento) 
setores; 
• Número n depende da velocidade do processador, do barramento, da 
controladora e da velocidade de rotação do disco; 
126
Dispositivos de E/S - Discos
Disco A
N = 0
Disco B
N = 2
Trilhas com 16 setores
0
1
2
3
6789
11
12
13
15
4
510
14 0 11
6
1
21383
9
4
15
5
12
714
10
127
Dispositivos de E/S - Discos
• Drivers de Disco:
• Fatores que influenciam tempo para leitura/escrita no disco: 
• Velocidade de acesso (seek) à tempo para o movimento do braço até o 
cilindro; 
• Delay de rotação (latência) à tempo para posicionar o setor na cabeça 
do disco;
• Tempo da transferência dos dados;
• Tempo de acesso:
• Tseek + Tlatência* + Ttransferência;
* Tempo necessário para o cabeçote se posicionar no setor de escrita/leitura;
128
Dispositivos de E/S – Discos
• Algoritmos de escalonamento no disco:
• FCFS (FIFO) à First-Come First-Served;
• SSF à Shortest Seek First;
• Elevator (também conhecido como SCAN);
• Escolha do algoritmo depende do número e do tipo de 
pedidos;
• Driver mantém uma lista encadeada com as requisições 
para cada cilindro;
129
Dispositivos de E/S - Discos
Disco com 37 cilindros;
Lendo bloco no cilindro 11;
Requisições: 1,36,16,34,9,12, nesta ordem
X X XX X X X
0 5 10 15 20 25 30 36
Pos. inicial
FCFS à atendimento: 1,36,16,34,9,12; 
movimentos do braço (número de cilindros): 10,35,20,18,25,3 = 111;
Tempo
130
Dispositivos de E/S - Discos
Disco com 37 cilindros;
Lendo bloco no cilindro 11;
Requisições:1,36,16,34,9,12, nesta ordem
X X XX X X X
0 5 10 15 20 25 30 36
Pos. inicial
SSF (requisição mais próxima) à
atendimento: 12,9,16,1,34,36;
movimentos do braço (número de cilindros): 1,3,7,15,33,2 = 61;
Tempo
131
Dispositivos de E/S - Discos
Disco com 37 cilindros;
Lendo bloco no cilindro 11;
Requisições: 1,36,16,34,9,12, nesta ordem
X X XX X X X
0 5 10 15 20 25 30 36
Pos. inicial
Elevator (requisições na mesma direção) à
atendimento: 12,16,34,36,9,1
movimentos do braço (número de cilindros): 1,4,18,2,27,8 = 60;
Bit de direção corrente (driver):
Se Up à atende próxima requisição;
senão Bit = Down;
muda direção e atende requisição;
Tempo
132
Dispositivos de E/S – Discos
RAID
• RAID (Redundant Array of Independent Disks) à
armazena grandes quantidades de dados;
• RAID combina diversos discos rígidos em uma estrutura 
lógica:
• Aumentar a confiabilidade, capacidade e o desempenho dos 
discos;
• Recuperação de dados à redundância dos dados;
• Armazenamento simultâneo em vários discos permite que os 
dados fiquem protegidos contra falha (não simultânea) dos discos; 
• Performance de acesso, já que a leitura da informação é 
simultânea nos vários dispositivos;
133
Dispositivos de E/S – Discos
RAID
• Pode ser implementado por:
• Hardware (controladora): 
• Instalação de uma placa RAID no servidor, o subsistema RAID é 
implementado totalmente em hardware;
• Libera o processador para se dedicar exclusivamente a outras tarefas; 
• A segurança dos dados aumenta no caso de problemas devido à 
checagem da informação na placa RAID antes da gravação;
134
Dispositivos de E/S – Discos
RAID
• Pode ser implementado por:
• Software (sistema operacional)
• Menor desempenho no acesso ao disco;
• Oferece um menor custo e flexibilidade;
• Sobrecarrega o processador com leitura/escrita nos discos;
• Para o SO existe um único disco;
135
Dispositivos de E/S – Discos
RAID
• A forma pela qual os dados são escritos e acessados 
define os níveis de RAID (até 9 níveis):
• RAID 0: 
• Também conhecido como Stripping;
• Arquivos são espalhados entre os discos em stripes; 
• Melhora desempenho das operações de E/S;
• Sem controle ou correção de erros;
• Todo o espaço do disco é utilizado para armazenamento;
• Utilizam mesma controladora (controladora RAID);
• Aplicações multimídia (alta taxa de transferência);
136
Dispositivos de E/S – Discos
RAID
• Nível 0
M
I
E
A
N
J
F
B
O
K
G
C
etc...
L
H
D
137
Dispositivos de E/S – Discos
RAID
• RAID 1:
• Conhecido como espelhamento (mirroring);
• Operações de escrita no disco primário são replicadas em um disco 
secundário;
• Pode ter controladoras diferentes;
• Desvantagem: espaço físico em dobro (alto custo);
• Transações on-line (tolerância a falhas); 
• RAID 10:
• Combinação dos RAID 1 e RAID 0;
138
Dispositivos de E/S – Discos
RAID
• Nível 10
D
C
B
A
D
C
B
A
=
H
G
F
E
H
G
F
E
=
139
Dispositivos de E/S – Discos
RAID
• RAID 2/3/4:
• Dados são armazenados em discos diferentes com paridade (permite reconstruir 
dados perdidos); Stripes;
• Paridade é mantida em um disco apenas;
• Diferença básica: como a paridade é calculada (na transferência):
• Raid 2 - Hamming ECC (error-correcting codes)– nível de bit;
• Raid 3 - XOR ECC - nível de byte ou bit;
• Raid 4 – XOR ECC - nível de bloco; 
• RAID 5:
• Stripes;
• Paridade XOR ECC distribuída - nível de bloco;
• Paridade está distribuída nos discos; 
• RAID 6:
• Stripes;
• Raid 5 com dois discos de paridade;
140
Dispositivos de E/S – Discos
RAID
• Nível 2
D0
C0
B0
A0
D1
C1
B1
A1
D2
C2
B2
A2
D3
C3
B3
A3
ECC Dx
ECC Cx
ECC Bx
ECC Ax
ECC Dy
ECC Cy
ECC By
ECC Ay
ECC Dz
ECC Cz
ECC Bz
ECC Az
141
Dispositivos de E/S – Discos
RAID
• Nível 3
D0
C0
B0
A0
D1
C1
B1
A1
D2
C2
B2
A2
D3
C3
B3
A3
Stripe 0 Stripe 1 Stripe 2 Stripe 3
Gerador de
Paridade
Paridade D
Paridade C
Paridade B
Paridade A
Paridade
Stripes 0,
1, 2 e 3
142
Dispositivos de E/S – Discos
RAID
• Nível 4
143
Dispositivos de E/S – Discos
RAID
• Nível 5
Gerador de
Paridade
Paridade 3
A2
A1
A0
B3
Paridade 2
B1
B0
C3
C2
Paridade 1
C0
D3
D2
D1
Paridade 0
144
Dispositivos de E/S – Discos
RAID
• Nível 6
• 2 cálculos diferentes de paridade
DÚVIDAS?