MC504 - Sistemas Operacionais
Gerencia de Memoria II
Islene Calciolari GarciaInstituto de Computacao - UnicampPrimeiro Semestre de 2017
Sumario
Memoria Virtual
Tabelas por processo
Substituicao de paginas
What is Virtual Memory?
● A technique that gives each process the illusion of a private, contiguous address space
0x00000000 - 0xFFFFFFFF
disk
● From fragments of physical RAM and disk
RAMRAM
Fonte: Troy D. Hanson
virtual → physical
● Software deals with virtual addresses● Hardware needs physical addresses
0x12345678 → ???
Fonte: Troy D. Hanson
Memoria Virtual
Memory Management Unit (MMU)Tanenbaum: Figura 4.9
Memoria virtual maior do que a memoria fısicaPaginacao
Tanenbaum: Figura 4.10
Memoria virtual maior do que a memoria fısicaPaginacao e armazenamento no disco
virtualmemory
memorymap
physicalmemory
•••
page 0
page 1
page 2
page v
Silberschatz: Figura 9.01
Mapeamento basico de enderecos
Tanenbaum: Figura 4.11
Mapeamento basico de enderecos
physicalmemory
f
logicaladdress
page table
physicaladdress
CPU p
p
f
d df
f0000 … 0000
f1111 … 1111
Silberschatz: Figura 8.10
Paginacao - Exemplo
I 32 bits de enderecoI paginas de 4kI 20 primeiros bits indicam a paginaI 12 ultimos bits indicam o deslocamento dentro da pagina
I Veja o codigo pagesize.c
r-xrw- r-x r-x
Even though the whole space is addressable, only certain areas are legal for r-w-x
0x00000000 0xffffffff
Fonte: Troy D. Hanson
r-xrw- r-x r-x
These legally addressable areas are called
● Virtual Memory Areas
0x00000000 0xffffffff
Fonte: Troy D. Hanson
r-xrw- r-x r-x
0x00000000 0xffffffff
Read → segfault!
Fonte: Troy D. Hanson
r-xrw- r-x r-x
0x00000000 0xffffffff
Read → segfault!
Write → segfault!
Fonte: Troy D. Hanson
r-xrw- r-x r-x
Virtual Memory Areas
0x00000000 0xffffffff
[thanson@linux02]$ pmap 205800043e000 88K r-x-- /lib/ld-2.3.4.so00454000 4K r-x-- /lib/ld-2.3.4.so00455000 4K rwx-- /lib/ld-2.3.4.so00458000 1176K r-x-- /lib/tls/libc-2.3.4.so0057e000 8K r-x-- /lib/tls/libc-2.3.4.so00580000 8K rwx-- /lib/tls/libc-2.3.4.so00582000 8K rwx-- [ anon ]08048000 4K r-x-- /home/thanson/trash/csleep08049000 4K rw--- /home/thanson/trash/csleepb7f9d000 4K rw--- [ anon ]bffd1000 188K rw--- [ stack ]ffffe000 4K ----- [ anon ] total 1500K
Fonte: Troy D. Hanson
Espaco de enderecamento
I Apenas as paginas ocupadas precisam ser mapeadasI Veja o codigo sbrk.c
Tabelas de mais de um nıvel
Tanenbaum: Figura 4.12
Tabelas de mais de um nıvel
•••
•••
outer pagetable
page ofpage table
page tablememory
929
900
929
900
708
500
100
1
0
•••
100
708
•••
•••
•••
•••
•••
•••
•••
•••
•••
1
500
Silberschatz: Figura 8.17
Mapeamento de enderecos: tabela de dois nıveis
logical address
outer pagetable
p1 p2
p1
page ofpage table
p2
d
d
Silberschatz: Figura 8.18
Page tables● Linux uses a 3-level page table scheme
00010010 00110100 01010110 01111000
12 bits (4k)Offset within
page20 bits
Used to find page
pgd_t pmd_t pte_t
struct page
Physicalpage
A virtual address (in binary)
Fonte: Troy D. Hanson
Page tables
00010010 00110100 01010110 01111000
pgd_t pmd_t pte_t
struct page
Physicalpage
The hardware has a small cache called the TLBTranslation Lookaside Buffer
Fonte: Troy D. Hanson
TLB: Translation Lookaside Buffer
page table
f
CPU
logicaladdress
p d
f d
physicaladdress
physicalmemory
p
TLB miss
pagenumber
framenumber
TLB hit
TLB
Silberschatz: Figura 8.14
TLB: Translation Lookaside Buffer
Tanenbaum: Figura 4.14
Tabelas por processo
page 0
page 1
page 2
page 3
logicalmemory
page 1
page 3
page 0
page 2
physicalmemory
page table
framenumber
1
4
3
7
0
1
2
3
0
1
2
3
4
5
6
7
Silberschatz: Figura 8.11
Novo processo
(a)
free-frame list1413182015
13
14
15
16
17
18
19
20
21
page 0 page 1 page 2 page 3
new process
(b)
free-frame list15 13 page 1
page 0
page 2
page 3
14
15
16
17
18
19
20
21
page 0 page 1 page 2 page 3
new process
new-process page table
140123
131820
Silberschatz: Figura 8.13
Nem tudo precisa estar em memoria...
B
D
D EF
H
logicalmemory
valid–invalidbitframe
page table
1
0 4
62
3
4
5 9
6
7
1
0
2
3
4
5
6
7
i
v
v
i
i
v
i
i
physical memory
A
A BC
C
F G HF
1
0
2
3
4
5
6
7
9
8
10
11
12
13
14
15
A
C
E
G
Silberschatz: Figura 9.05
Compartilhamento de areas de codigo
7
6
5
ed 24
ed 13
2
data 11
0
3
4
6
1
page tablefor P1
process P1
data 1
ed 2
ed 3
ed 1
3
4
6
2
page tablefor P3
process P3
data 3
ed 2
ed 3
ed 1
3
4
6
7
page tablefor P2
process P2
data 2
ed 2
ed 3
ed 1
8
9
10
11
data 3
2data
ed 3
Silberschatz: Figura 8.16
Memoria compartilhada
int shmget(key t key, size t size,
int shmflg);
void *shmat(int shmid,
const void *shmaddr,
int shmflg);
I Veja os exemplos: sh1.c sh2.csh fork.c sh server.c e sh client.c
Copy on write (antes)
process1
physicalmemory
page A
page B
page C
process2
Silberschatz: Figura 9.07
Copy on write (depois)
process1
physicalmemory
page A
page B
page C
Copy of page C
process2
Silberschatz: Figura 9.08
Substituicao de paginas
valid–invalid bitframe
f
page table
victim
changeto invalid
page outvictimpage
page indesired
page
reset pagetable for
new page
physicalmemory
2
4
1
3
f
0 i
v
Silberschatz: Figura 9.10
Page fault
load M
referencetrap
i
page is onbacking store
operatingsystem
restartinstruction
reset pagetable
page table
physicalmemory
bring inmissing page
free frame
1
2
3
6
5 4
Silberschatz: Figura 9.06
Algoritmo otimo para substituicao de paginas
page frames
reference string
7 7
0
7
0
1
2
0
1
2
0
3
2
4
3
2
0
3
7
0
1
2
0
1
7 0 1 2 0 3 0 4 2 3 0 7 11 02 1 20 3
Silberschatz: Figura 9.14
I Baseado no uso futuro de uma paginaI Impossıvel de ser implementadoI Pode ser simulado (segunda execucao do mesmo
processo com a mesma entrada)I Util para comparacao entre algoritmos
Entrada na tabela
Tanenbaum: Figura 4.13
Nao usada recentemente
I Classe 0: nao referenciada, nao modificadaI Classe 1: nao referenciada, mas modificadaI Classe 2: referenciada, mas nao modificadaI Classe 3: referenciada e modificada
First In, First Out
7 7
0
7
0
1
page frames
reference string
2
0
1
2
3
1
2
3
0
4
3
0
4
2
0
4
2
3
0
2
3
7
1
2
7
0
2
7
0
1
0
1
3
0
7 0 1 2 0 3 0 4 2 3 0 7 11 02 1 20 3
1
2
Silberschatz: Figura 9.12
I Simplemente coloca as paginas em uma filaI Pode remover paginas importantes
Segunda chance
Tanenbaum: Figura 4.16
I Se o bit R == 0, a pagina e substituıda, senaoI bit R e limpo e a pagina e colocada no final da fila
Relogio
Tanenbaum: Figura 4.17
I Implementacao circular da segunda chance
Segunda chance (relogio)
circular queue of pages
(a)
nextvictim
0
referencebits
pages
0
1
1
0
1
1
……
circular queue of pages
(b)
0
referencebits
pages
0
0
0
0
1
1
……Silberschatz: Figura 9.17
LRU (Least Recently Used)
page frames
reference string
7 7
0
7
0
1
2
0
1
2
0
3
4
0
3
4
0
2
4
3
2
0
3
2
1
3
2
1
0
2
1
0
7
7 0 1 2 0 3 0 4 2 3 0 7 11 02 1 20 3
Silberschatz: Figura 9.15
I Elimina pagina que nao foi utilizada ha mais tempoI Implementacao utilizando lista duplamente ligadaI Implementacao em hardware
LRU em hardware
Acessos: 0 1 2 3 2 1 0 3 2 3Tanenbaum: Figura 4.18
Simulando LRU em softwarePagina nao usada frequentemente
I Contador de uso para cada pagina (soma o bit R a cadaclock tick)
I Nao esquece nada...I Considere um compilador baseado em passos
Nao usada frequentementeAging
I O contador e deslocado a direitaI Bit R e adicionado a esquerda
1 0 1 0 1 1 1 0 1 1 0 1
>> 1 1 0 1 0 1 >> 1 1 0 1 1 0
+ 1 1 1 0 1 0 1 + 0 0 1 0 1 1 0
Nao usada frequentemente
Tanenbaum: Figura 4.19
Working Set w(k , t)
page reference table. . . 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 3 4 4 4 3 4 4 4 . . .
Δ
t1WS(t1) = {1,2,5,6,7}
Δ
t2WS(t2) = {3,4}
Silberschatz: Figura 9.20
I Conjunto de paginas utilizadas nas ultimas k referenciasem relacao ao instante t .
I Paginacao sob demandaI PrepagingI Implementacao exata e muito cara
Substituicao baseada em Working Set
Tanenbaum: Figura 4.21
WSClock
Tanenbaum: Figura 4.22
Controle da carga
I Thrashing
thrashing
degree of multiprogramming
CP
U u
tiliz
atio
n
Silberschatz: Figura 9.18
I O Sistema Operacional so se ocupa das tarefas depaginacao e escalonamento
I Todos os processos precisam de mais memoriaI Swap (como escolher quais processos vao para o disco?)
Resumo
Tanenbaum: Figura 4.23