Embed Size (px)
Citation preview
Sumário
Memória VirtualFundamentosConversão de EndereçosPage FaultsAlgoritmos de Substituição de PáginasSwap AreaEnvolvimento do SOInteracção com E/S
Leitura Adicional
Sumário
Memória VirtualFundamentosConversão de EndereçosPage FaultsAlgoritmos de Substituição de PáginasSwap AreaEnvolvimento do SOInteracção com E/S
Leitura Adicional
Memória Virtual (MV)
I Ideia:I Decompôr o espaço de endereçamento dum processo em
blocos.I Manter em memória apenas alguns desses blocos (código
e dados) do processo em execução.I Manter os outros blocos no disco:
I na área de swap;I no sistema de ficheiros (código, p.ex.).
I Transferir os blocos entre o disco e a memória, conformenecessário.
I MecanismosI Paginação;I Segmentação;
(ambos requerem suporte do HW).
MV vs. swapping
+ Permite programas maiores do que a memória físicadisponível;
+ Possibilita ter mais processos em memória (ainda que sóparte deles);
+ Reduz tempo de arranque dum processo+ Facilita a partilha de memória entre processos- Exige suporte do HW mais sofisticado- Pode conduzir a thrashing
MV Paginada
I A memória física está dividida empage frames, ou frames:
I o tamanho das frames édeterminado pelo HW(tipicamente, 4 Kbyte ou 8 Kbyte).
I O espaço de endereçamento dumprocesso está dividido em páginas:
I de tamanho igual ao das frames.I O conteúdo das páginas é
transferido de e para frames.
Virtual address
space
Physical memory address
60K-64K
56K-60K
52K-56K
48K-52K
44K-48K
40K-44K
36K-40K
32K-36K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
Virtual page
Page frame
X
X
X
X
7
X
5
X
X
X
3
4
0
6
1
2
Exemplo Páginas de 4 KB (4096 bytes)Espaço de endereço virtual 16 páginas (64 KB)Espaço de endereço físico 8 frames (32 KB)
Conversão de Endereços em MV PaginadaI Paginação determina dois espaços de endereçamento:
virtual ou lógico que é o que o CPU conhece - ocódigo executável usa endereços virtuais oulógicos;
físico que é usado no barramento de endereços damemória.
I O mapeamento dos endereços dum espaço no outro érealizado pela Memory Management Unit (MMU):
CPU package
CPU
The CPU sends virtual addresses to the MMU
The MMU sends physical addresses to the memory
Memory management
unit
MemoryDisk
controller
Bus
Conversão de Endereços com uma Tabela (1/2)I Em sistemas com MV paginada um endereço tem 2
componentes:
Page # Offset
I O número da página, parte mais significativa do endereço;I O deslocamento (offset) na página, parte menos
significativa.
I Como frames e páginas têm o mesmo tamanho, a MMU sótem que mapear o número da página no número da frame.
I O mapeamento pode ser feito usando uma tabela,implementada como um vector:
I o número da página é usado como indíce para obter onúmero da frame que a contém.
I O uso de páginas cujo tamanho é uma potência de 2,simplifica o cálculo do endereço físico:
I Basta substituir o no da página pelo no da frame com o seuconteúdo
Conversão de Endereços com uma Tabela (2/2)
Virtual address
space
Physical memory address
60K-64K
56K-60K
52K-56K
48K-52K
44K-48K
40K-44K
36K-40K
32K-36K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
Virtual page
Page frame
X
X
X
X
7
X
5
X
X
X
3
4
0
6
1
2
Page size 4096 bytes, i.e. 12 bits
# Pages per address space 64KB/4KB = 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
000 000 000 000 111 000 101 000 000 000 011 100 000 110 001 010
0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 Present/
absent bit
Page table
12-bit offset copied directly from input to output
Virtual page = 2 is used as an index into the page table Incoming
virtual address (8196)
Outgoing physical address (24580)
110
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
00 1 0 0 0 0 0 0 0 0 0 0 1 0 0
Page Table Entry (PTE)Caching disabled Modified Present/absent
Page frame number
Referenced Protection��I Se o CPU usar endereços de 32 bits, e páginas de 4 Kbyte(12 bits), a page table terá ∼4 Mbyte!!!
I O espaço de endereço virtual tem 220 = 232/210 páginasI Cada PTE ocupa 4 bytes (20 bits para o no da frame)I Cada página pode conter até 1024 (210) PTEI Sendo necessárias 1024 (220/210) páginas
I Normalmente, um processo usa apenas uma pequenaparte do seu espaço de endereçamento:
I A maioria dos elementos da page table não são usadosI Muitas das páginas da page table estão vazias
Tabelas com 2 NíveisI Permite não usar páginas da tabela vazias
I Exige uma “tabela” adicional paraas páginas com as conversõesde endereços
I Elementos correspondentes apáginas vazias têm o bitPresent/absent a 0
I Os outros elementos apontampara páginas com conversões
I A conversão é feita em 2 passos:I Os 10 bits mais significativos
são usados para seleccionar apágina de 2o nível que poderáconter o elemento desejado
I Os 10 bits seguintes sãousados como indíce da “tabela”contida nessa página
(a)
(b)
Top-level page table
Second-level page tables
To pages
Page table for the top 4M of memory
6 5 4 3 2 1 0
1023
6 5 4 3 2 1 0
1023
Bits 10 10 12
PT1 PT2 Offset
I Este esquema pode ser generalizado a 3 ou mais níveis
Tabelas InvertidasI Alguns CPUs de 64 bits usam tabelas invertidas:
I têm um elemento por frame, em vez de ...I cada elemento contêm informação sobre (processo, página
virtual) contido pela frameI A tabela está organizada como uma hash table
I usa o endereço virtual da página (e o processo) como key
Traditional page table with an entry for each of the 252 pages
256-MB physical memory has 216
4-KB page frames Hash table216 -1
252 -1
216 -1
0 0Indexed by virtual
page
0Indexed
by hash on virtual page
Virtual page
Page frame
Desempenho da Conversão de EndereçosI Pode traduzir-se um endereço com tantos acessos à
memória quantos os níveis da page tableI no caso de tabelas invertidas são necessários 2 acessos
no mínimo, mais se houver colisões.I Obviamente, temos um problema:
I cada acesso à memória, requereria acessos adicionaispara converter endereços.
I A solução é usar uma cache, a Translation LookasideBuffer, de elementos da page table usados em conversõesrecentes:
Valid Virtual Page Modified Protection Page Frame1 140 1 RW 311 20 0 R X 381 130 1 RW 291 129 1 RW 621 19 0 R X 50
Translation Lookaside Buffer (TLB)
I A TLB usa memória associativa:I cada posição de memória consiste num par (key, value);I o endereçamento é feito comparando o valor do endereço
da página com o valor de key de todas as posições da TLBem paralelo (i.e. a TLB usa full associative memory )
Em termos de implementação, a TLB é semelhante àcache de instruções ou dados.
I Funciona como uma fully associative cacheI O número de posições da TLB não precisa ser muito
elevado:I por causa da localidade no acesso à memória.
I Quando da comutação de processos, o conteúdo da TLBtem que ser invalidado, a menos que use um identificadordo espaço de endereçamento também como chave
TLB Misses
I E se o endereço a converter não estiver na TLB (TLBmiss)?
I Há que consultar a page tableI Normalmente, o HW de gestão de memória, a Memory
Management Unit (MMU), processa automaticamente asTLB misses:
I A MMU precisa conhecer a localização da page table doprocesso em execução:
I A MMU tem um registo com o endereço da page table, oqual faz parte do PCB, i.e. do contexto do processo
I A MMU de alguns CPUs RISC não processam TLB misses,deixam essa tarefa a cargo do SO.
Desempenho da Conversão de Endereços com TLB
I Seja:p a TLB hit ratiom o no de acessos à memória no caso duma TLB miss
I Admitindo que no caso de um TLB hit, o custo é zero, ocusto efectivo da utilização de MV paginada vem:
(1 − p)mI Seja:
p = 0.98m = 3Então o custo será de: 0.06 acessos à memoria porconversão de endereço
Page FaultQuando um processo tenta aceder a uma página e essapágina não está em memória ocorre uma page fault
I A MMU gera uma excepção, que é processada pelo pagefault handler :
I O page fault handler consulta uma outra estrutura dedados (address map do processo) para determinar:
I se a referência é válida: protecção;I e, em caso afirmativo, onde se encontra a página.
I O handler obtém uma frame livre.I Transfere a página do disco para a frame.I Actualiza a page table.
I O CPU terá que reiniciar/retomar a execução da instruçãoque causou a page fault :
I Depende das instruçõesI Instruções que transferem blocos de dados, e.g. IA32 move
string instructions, são particularmente problemáticasI Depende do processador
I E.g. os processadores IA32 alteram os registos, de modo aque a instrução possa ser retomada transparentemente
Address Map
I É a estrutura de dados do SO que mapeia o espaço deendereçamento dum processo no espaço no disco:
I ficheiros;I partes da área de swap
I É usada pelo page-fault handler para determinar:I a validade da referência;I em caso positivo, qual a fonte da página referenciada.
I Quando o SO cria um processo:I mapeia o ficheiro com o código correspondente no espaço
de endereçamento desse processo;I reduz o tempo de arranque dum processo.
I transfere algumas páginas desse ficheiro para a memória(prepaging):
I evita uma page fault rate excessiva inicialmente.
more /proc/1/maps em Linux
08048000-0804f000 r-xp 00000000 03:02 8954 /sbin/init0804f000-08050000 rw-p 00006000 03:02 8954 /sbin/init08050000-08054000 rwxp 00000000 00:00 040000000-40012000 r-xp 00000000 03:02 8862 /lib/ld-2.1.3.so40012000-40013000 rw-p 00011000 03:02 8862 /lib/ld-2.1.3.so40013000-40014000 rwxp 00000000 00:00 04001b000-400f0000 r-xp 00000000 03:02 8864 /lib/libc-2.1.3.so400f0000-400f4000 rw-p 000d4000 03:02 8864 /lib/libc-2.1.3.so400f4000-400f8000 rw-p 00000000 00:00 0bfffe000-c0000000 rwxp fffff000 00:00 0
I O p na segunda coluna indica que a região é privadaI A saída gerada por kernels mais recentes é bem mais
extensa
Partilha de CódigoI O address map facilita a partilha de memória entre
processos.I Um exemplo muito comum é o código de bibliotecas
partilhadas
Address−SpaceProcess 2
Address−SpaceProcess 1
SharedCode
E se não houver qualquer frame livre?
I Se, quando duma page-fault, todas as frames estiveremocupadas, o SO tem que libertar uma:
I se a frame seleccionada tiver sido modificada, terá que sertransferida para o disco.
I Por razões de eficiência, o SO tipicamente executa umprocesso (pageout daemon) que procura manter um certonúmero de frames livres.
I Em qualquer dos casos, põe-se o problema:Que páginas transferir para o disco?
É bom que se faça uma boa escolha, doutro modo odesempenho sofre . . .
I Este problema é comum a qualquer cache. Mas:
disk access timememory access time
� memory access timecache access time
Algoritmos de Substituição de Páginas
222222222222222222222222222222222222222222222222222222222222222222222222Algorithm Comment222222222222222222222222222222222222222222222222222222222222222222222222
Optimal Not implementable, but useful as a benchmark222222222222222222222222222222222222222222222222222222222222222222222222NRU (Not Recently Used) Very crude222222222222222222222222222222222222222222222222222222222222222222222222FIFO (First-In, First-Out) Might throw out important pages222222222222222222222222222222222222222222222222222222222222222222222222Second chance Big improvement over FIFO222222222222222222222222222222222222222222222222222222222222222222222222Clock Realistic222222222222222222222222222222222222222222222222222222222222222222222222LRU (Least Recently Used) Excellent, but difficult to implement exactly222222222222222222222222222222222222222222222222222222222222222222222222NFU (Not Frequently Used) Fairly crude approximation to LRU222222222222222222222222222222222222222222222222222222222222222222222222Aging Efficient algorithm that approximates LRU well222222222222222222222222222222222222222222222222222222222222222222222222Working set Somewhat expensive to implement222222222222222222222222222222222222222222222222222222222222222222222222WSClock Good efficient algorithm222222222222222222222222222222222222222222222222222222222222222222222222111111111111111
111111111111111
111111111111111
Algoritmo ÓptimoSequência de acessos 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5# de frames 41 2 3 4 51 2 1 2 3 4 5
1
2
3
4
4
5
Algoritmo Quando da substituição duma página, expulsa-se apágina que será referenciada depois de todas as outras.Problema O SO não consegue prever o futuro
Utilidade permite comparar a qualidade de algoritmos que sãoexequíveis:
I requer o registo das operações de acesso à memóriapor um processo;
I importante que a execução seja representativaSolução Usar o passado recente para prever o futuro
I Os diferentes algoritmos diferem nos pormenores
Algoritmo Least Recently Used (LRU)Ideia Assumir que páginas usadas mais recentemente serão
usadas em breveI expulsar a página usada menos recentemente, i.e.
acedida pela última vez há mais tempo1 2 3 4 51 2 1 2 3 4 5
2
5
1
4
3
3
4
5
I Normalmente o HW não fornece os mecanismosnecessários para uma implementação eficiente destealgoritmo
I A sua implementação em SW não é viável na práticaI Porquê?
I A alternativa é tentar aproximar o LRU usando outrosalgoritmos
FIFO
I Expulsar a página que está no sistema há mais tempo
1 2 3 4 51 2 1 2 3 4 5
1
2
3
4
5
1
2
3
4
5
I Curiosamente, com 3 frames o no de page faults nestecaso é inferior1 2 3 4 5
1
2
1 2 1 2 3 4 5
1
2
3
4 5
3
4
I Este comportamento é contra-intuitivo
Anomalia de Belady
I Intuitivamente,I quanto maior o número de page frames, i.e. memória,
menor será a taxa de page-faultsI Porém Belady mostrou que nem todos os algoritmos de
substituição de páginas garantem que assim é.I Alguns algoritmos apresentam casos patológicos nos quais
o aumento da memória conduz a mais page-faultsI Uma classe de algoritmos de substituição que não sofre
deste problema é conhecida por stack algorithmsI Estes algoritmos garantem que:
M(n, r) ⊆ M(n + 1, r)
onde M(f , r) dsigna o conteúdo da memória com f framesapós r referências
ClockI As páginas são mantidas numa fila circularI O algoritmo usa um apontador que varre a filaI Usa o referenced bit (R-bit), activado em cada acesso à
memóriaI Quando é preciso libertar uma página:
I Se a página apontada pelo apontador tem o R-bit a 0,então expulsa-a, e actualiza o apontador
I Senão, limpa o R-bit e avança para a página seguinte
When a page fault occurs, the page the hand is pointing to is inspected. The action taken depends on the R bit: R = 0: Evict the page R = 1: Clear R and advance hand
AB
C
D
E
FG
H
I
J
K
L
Clock: Variantes
I Usar um segundo apontador que se move em conjuntocom o primeiro
I O primeiro apontador limpa o R-bitI O segundo expulsa a página, se o R-bit tiver valor 0I Especialmente útil se o no de frames for muito grande
I Usar o modified-bit (M-bit) o qual é activado sempre queuma página é modificada (também designado por dirty-bit
I Classificar cada página numa de 4 classes:1. não referenciadas, não modificadas2. não referenciadas, mas modificadas3. referenciadas, não modificadas4. referenciadas, modificadas
e expulsar as páginas pela ordem indicadaI Alternativamente, se o M-bit estiver ativo, iniciar a sua
transferência para o disco.I Só expulsa páginas não referenciadas e não modificadas
Conceito de Working Set
I Com paginação pura, as páginas dum processo só sãotrazidas para a memória quando o processo tem umapage-fault.
I Quando um processo inicia, tem uma taxa de page-faultselevada, até que eventualmente essa taxa diminui:
I este comportamento deve-se à localidade de referência.I O conjunto de páginas acedidas por um processo num
determinado intervalo designa-se por working set.I Se o working set dum processo estiver em memória, um
processo tem um taxa de page-faults muito baixa,reciprocamente . . .
I Tipicamente, o working set dum processo varia no tempo.
Definição de Working SetWorking set conjunto de páginas acedidas nos k acessos à
memória mais receentes
w(k,t)
kI w(k , t) é o tamanho do working set no instante t
I w(k , t) é uma função monótona crescenteI Contudo w(k , t) não pode nunca ser superior ao no de
páginas do espaço de endereçamento do processoI Excepto para valores de k muito baixos, o tamanho do
working set dum processo é praticamente independente dek
Algoritmo WSClock
Ideia Expulsar as páginas que não fazem parte do working setProblema Como determinar se uma página faz parte do WS?Solução Manter um tempo virtual que é aproximadamente o
tempo de execução do processo.
I Manter o tempo do “último” acessoa cada frame
I Periodicamente, actualizá-lo deacordo com o R-bit
I Usar o algoritmo do relógioI Quando ocorre uma page-fault o
handler analisa a páginaapontada pelo ponterio.
I O algoritmo só expulsa páginascuja idade é superior a τ
I Pode usar-se 2 apontadores
2204 Current virtual time
1213 0
2084 1 2032 1
1620 0
2020 12003 1
1980 1 2014 1
Time of last use
R bit
(a) (b)
(c) (d)
New page
1213 0
2084 1 2032 1
1620 0
2020 12003 1
1980 1 2014 0
1213 0
2084 1 2032 1
1620 0
2020 12003 1
1980 1 2014 0
2204 1
2084 1 2032 1
1620 0
2020 12003 1
1980 1 2014 0
Algoritmos de Substituição de Páginas
222222222222222222222222222222222222222222222222222222222222222222222222Algorithm Comment222222222222222222222222222222222222222222222222222222222222222222222222
Optimal Not implementable, but useful as a benchmark222222222222222222222222222222222222222222222222222222222222222222222222NRU (Not Recently Used) Very crude222222222222222222222222222222222222222222222222222222222222222222222222FIFO (First-In, First-Out) Might throw out important pages222222222222222222222222222222222222222222222222222222222222222222222222Second chance Big improvement over FIFO222222222222222222222222222222222222222222222222222222222222222222222222Clock Realistic222222222222222222222222222222222222222222222222222222222222222222222222LRU (Least Recently Used) Excellent, but difficult to implement exactly222222222222222222222222222222222222222222222222222222222222222222222222NFU (Not Frequently Used) Fairly crude approximation to LRU222222222222222222222222222222222222222222222222222222222222222222222222Aging Efficient algorithm that approximates LRU well222222222222222222222222222222222222222222222222222222222222222222222222Working set Somewhat expensive to implement222222222222222222222222222222222222222222222222222222222222222222222222WSClock Good efficient algorithm222222222222222222222222222222222222222222222222222222222222222222222222111111111111111
111111111111111
111111111111111
I O que é que o “utilizador”/programador pode fazer?I Pouco a menos que o SO suporte user-level pagers
User-level Pager
DiskMain memory
External pager
Fault handler
User process
MMU handler
1. Page fault
6. Map page in
5. Here is page
User space
Kernel space
2. Needed page
4. Page arrives
3. Request page
I Mais um exemplo de separação entre mecanismos epolíticas
I Idealmente, o SO deveria suportar uma API quepermitisse expulsar páginas da memória
I O algoritmo de substituição precisa tipicamente de acederaos bits R e M.
Swap Area
I É uma zona do disco para onde é transferido o conteúdodas páginas modificadas expulsas da memória:
I páginas de ficheiros não alteráveis, p.ex. código, nãoprecisam ser transferidas para a swap area.
I Pode ser implementada:I directamente sobre o disco – mais eficiente;I sobre ficheiros – fácil de ajustar o seu tamanho.
I Em qualquer caso, o SO tem que gerir o espaço disponívelna swap area.
I A alocação de espaço na àrea de swap pode ser:optimista só é alocada quando necessário – possibilidade
de deadlock?pessimista é reservada – pode não vir a ser usada e,
consequentemente, reduzir a utilização dos recursos.
Swap Area: Modos de Alocação.
0
4
3
6
6
43
0
7
5
21
Pages
Page table
Main memory Disk
Swap area
(a)
0
4
3
6
6
43
0
5
1
7
2
Pages
Page table
Main memory Disk
Swap area
(b)
Disk map
Working Set e ThrashingI Normalmente, a frequência de page faults depende do
número de frames atribuídas a um processo:
Pag
e fa
ults
/sec
Number of page frames assigned
A
B
I Quando a maioria dos processos não tem um número depáginas suficiente em memória, i.e. o seu working set, ocomputador pode entra num estado de thrashing:
usa a maioria dos seus recursos para transferirpáginas entre a memória principal e o disco
Escalonamento Multinível
I Se a frequência de page faults aumenta bastante,indicando a possibilidade de thrashing, o SO pode “fazer oswapout de processos”:
i.e. transferir todas as páginas dum ou maisprocessos para o disco.
I Ou seja, o SO poderá usar dois níveis de escalonamento:I O nível superior determina quais os processos em
memória.I O nível inferior faz o escalonamento dos processos em
memória.
Envolvimento do SO na Gestão de MV Paginada
I Criação dum processo:I criar page table.
I Comutação de processos:I configurar a MMU para o novo processo;I invalidar o TLB.
I Page-fault :I determinar e validar o endereço que a causou;I transferir página do disco para a memória, possivelmente
com troca.I Terminação dum processo:
I libertação da page table e das frames.I Outras tarefas:
I manter número mínimo de frames livres;I swap-out processos, se frequência de page-faults
excessiva.
Interacção com E/S
I Converter endereços para realizar E/S:I Dispositivos de E/S usam endereços físicos, não lógicos.
I Impedir que as páginas usadas numa operação de E/Ssejam expulsas enquanto a operação não terminar:
I pin-down/lock páginas na memória.
Algumas Questões
I Relacionadas com a implementação:I Qual deve ser o tamanho duma página?I Onde é que as tabelas devem residir?I Será que as páginas que constituem a tabela têm que estar
sempre em memória?I E as páginas com o SO?
I Outras:I Quantas page tables são necessárias?I Como é que a MV paginada assegura protecção entre
processos?I Que medidas se pode tomar para reduzir a frequência de
page-fault?I Por que razões a MV funciona, i.e. tem um desempenho
próximo do dum sistema com capacidade de memóriainfinita?
Sumário
Memória VirtualFundamentosConversão de EndereçosPage FaultsAlgoritmos de Substituição de PáginasSwap AreaEnvolvimento do SOInteracção com E/S
Leitura Adicional
Leitura Adicional
Modern Operating Systems, 2nd. Ed.
I Secção 4.1: Fundamentos (4.1.1, 4.1.2 e 4.1.5)I Secção 4.2: SwappingI Secção 4.3: Memória VirtualI Secção 4.4: Page Replacement AlgorithmsI Secção 4.6: Design Issues (até 4.6.2 inclusivé).I Secção 4.7: Implementation Issues (excepto 4.7.3).
