Sistemas Operacionais:
Gerenciamento de Memória
Prof. Leandro Magno
Material gentilmente cedido pelo prof.
Dr. Ronaldo Augusto de Lara Gonçalves
DIN - UEM
2/18/13
FAFIMAN
1
Roteiro








2/18/13
Questões Importantes
Alocação Contígua
Alocação Particionada
Swapping
Paginação
Segmentação
Segmentação com Paginação
Memória Virtual do Linux
FAFIMAN
2
Questões Importantes
no Projeto de Memórias








2/18/13
Localização
Capacidade
Unidade de Transferência
Método de Acesso
Desempenho
Tipo Físico
Características
Gerenciamento
FAFIMAN
3
Gerenciamento da Memória Principal
alocação contígua simples
 alocação particionada (estática e
dinâmica)
 swapping
 paginação
 segmentação

2/18/13
FAFIMAN
4
Alocação Contígua Simples




para sistemas de monoprogramação
memória principal dividida em 2: SO + usuário
usuário tem controle de quase toda a memória
controle de acesso fora dos limites do usuário
registrador
delimitador
MP
SO
área para
1 programa
do usuário
2/18/13
128MB
FAFIMAN
5
Alocação Contígua com Overlay
SO
2MB
módulo
principal
1MB
módulo de
cálculo
3MB
módulo de
cadastro
3MB
módulo de
leitura
2MB
módulo de
impressão
1MB
área de
overlay
área livre
área ocupada pelo maior módulo de overlay
* módulos de overlay definidos em compilação
2/18/13
FAFIMAN
6
Alocação Particionada Estática
para sistemas multiprogramados
 memória é dividida em partições
 as
partições são definidas
durante o boot
 controle: tabela de partições
 absoluta e relocável

2/18/13
FAFIMAN
7
Alocação Particionada Estática
Part
MP
Tam
SO
1
A
2MB
área perdida
Tabela de Partições
N
NOME
TAM
USO
OCUP
1
A
2
1.2
1
2
-
2
0
0
3
B
3
2
1
4
-
3
0
0
2
3
2MB
B
3MB
área perdida
4
2/18/13
área livre
FAFIMAN
área livre
3MB
8
APE Absoluta
Part
MP
Tam
SO
2/18/13
G
D
A
1.5MB
1MB
2MB
H
E
B
2.5MB
3MB
2.5MB
F
C
3MB
3.5MB
1
2MB
2
3MB
3
4MB
FAFIMAN
9
APE Relocável
Part
MP
Tam
SO
C
B
A
5MB
2MB
3MB
2/18/13
1
1MB
2
3MB
3
6MB
FAFIMAN
10
Fragmentação
partições
MP
fragmentos
SO
1
A
área livre
B
D
E
2
área livre
4MB
5MB
C
3
2/18/13
área livre
FAFIMAN
Exis te m 6 MB
1MB l i v r e s m a s
n e n h u m
processo pode
ser alocado na
2MB
memó ria,
e m b o r a
pr ec ise m de 4
ou 5 MB.
3MB
11
Pergunta
Existe alguma forma onde a
memória pode ficar totalmente
preenchida por processos (sem
fragmentação), utilizando o
método de Alocação Particionada
Estática?
2/18/13
FAFIMAN
12
Alocação Particionada Dinâmica
•sem partições fixas
•cada programa utiliza o espaço que
precisar
•a partição é do tamanho do próprio
programa
2/18/13
FAFIMAN
13
Alocação Particionada Dinâmica
MP
Part
Tam
SO
Fila de Entrada
D
C
B
A
1M 4M 1M 2M
Tabela de Partições
2/18/13
N
NOME
TAM
OCUP
1
-
12
0
1
área livre
FAFIMAN
12MB
14
Alocação Particionada Dinâmica
MP
Part
Tam
SO
Tabela de Partições
2/18/13
N
NOME
TAM
OCUP
1
A
2
1
2
B
1
1
3
C
4
1
4
D
1
1
5
-
4
0
1
A
2MB
2
B
1MB
3
C
4MB
4
D
1MB
5
área livre
4MB
FAFIMAN
15
Fragmentação


Surge na medida em que as partições estão
sendo liberadas
Necessita reorganizar os espaços livres
M P
D
6 k
2/18/13
S O
4 k
C
3 k
A
1 k
liv re
l i v8
re
k liv re , e m
o
p ro g .
D
e x e c u ta d o .
liv re
FAFIMAN
16
Soluções para Diminuir a Fragmentação


unir partições adjacentes
remanejar as partições ocupadas
M P
M P
M P
M P
SO
SO
SO
SO
C
1k
A
2k
4k
4k
C
A
1k
3k
2k
1k
2/18/13
A
8 k liv re
C
2k
1 k liv re
A
FAFIMAN
1k
3k
2k
1k
8 k liv
17
Estratégias para a escolha da
Partição a ser utilizada



tentar evitar ou diminuir o problema
da "fragmentação“
o SO deve possuir uma lista de
áreas livres ou "free-list“
3 técnicas principais:
worst-fit e first-fit
2/18/13
FAFIMAN
best-fit,
18
S O
3 k
B e s t-fi t
H
4 k
I
G
1 k
M
P
S O
S O
3 k
G
1 k
3 k
H
4 k
I
W
H
G
o r s t-fi t
2 k
F i r s t-fi t
I
3 k
2 k
S O
G
2 k
H
4 k
I
2 k
2/18/13
FAFIMAN
19
Pergunta

2/18/13
Como fica a tabela de
partições na alocação
particionada dinâmica?
FAFIMAN
20
Resolva a Situação
A l o c a ç ã o
P a r t i c i o n a d a
T a b e
P a r t i
S O
(D e a d l i n e )
P a I rn tFi c
i
0 K
1 0 4" 0
1 "0
2 "5
1 "5
3 "0 "
1
2
F E D C B A
L I V R E
:
:
1 0
4 k
0
6 k
0
2 k
0
3 k
5
5 k
0 k
N
(T a m a n h o )
1 0 0 K
t i m e -s l i c e
=
5 "
e s c a l o n a m e n t o
a
l o n g
e s t r a t é g i a
p / e s c o l h a
e s c a l o n a m e n t o
a
c u r t
r e d u ç ã o
d a
f r a g m e n t a
o b s : c o n s i d e r e
a p e n a
2/18/13
FAFIMAN
21
Responda



quanto tempo levará para executar
todos os programas ?
após 65", qual a situação da
memória e da tabela de partição ?
após 95", qual a situação da
memória e da tabela de partição ?
2/18/13
FAFIMAN
22
Swapping
m e m ó ria p rin cip a l
S .O
A
swapp
H
B
out
4K
C
B
D
m e m ó ria
s e cu n d á ria
Problema de
Relocação ??
2/18/13
m e m ó ria p rin c ip
S .O
A
B
s wa pp C
in
B
m e m ó ria
s e cu n d á ria
FAFIMAN
23
Memória Virtual
M
EMPrincipal
0
1
2
3
M
EM
Virtual
espaçode
enderecos
virtuais
0
1
2
3
espaçode
enderecos
reais
M
aplicação
N
disco
M
EMSecundária
2/18/13
FAFIMAN
24
Mapeamento
tab
P1
MEM real
tab
P2
2/18/13
FAFIMAN
25
Questões Importantes
2/18/13

Controle

Endereçamento

Mapeamento

Tipos de Gerenciamento

TLB
FAFIMAN
26
Paginação




Divisão do Endereçamento
Tabela de Páginas
Page Fault
Técnicas de Busca de Páginas
 Por
demanda
 Antecipada


2/18/13
Fragmentação
Tabela de Páginas HASH
FAFIMAN
27
Endereçamento
endereç
o
endereç
o da palav
ra a s
er ac
es
s
ada
N
P
D
ESL
00000000
00000001
00000010
0 0 0 0 1 0 0 1
nro da página
00
00000011
00000100
00000101
00000110
01
00000111
00001000
00001001
00001010
10
00001011
00001100
00001101
00001110
11
00001111
2/18/13
FAFIMAN
28
Estrutura Geral
0
1
M em Virtual
M em Real
program a
program a
ins truç ão a s er
ex ec utada
end v irtual
N
nro pag v irtual des l
end real
nro pag real
des l
tabela de páginas
end tab pag
bits de
nro pág real
c ontrole
2/18/13
FAFIMAN
29
Fragmentação
pg 0
program exemplo;
pg 1
begin
:
pg 2
end.
fragmentação
"espaço perdido"
pg 3
2/18/13
FAFIMAN
30
Tabela de Páginas Hash
end virtual
NPV
DESL
tab pag
tab hash
NPV
NPR
PROX
NPR
DESL
hash
pag
end real
2/18/13
FAFIMAN
31
Tabela de Páginas e TLB
program a tenta
ac es s ar a página
iníc i o
entrada
da Tab Pag es tá
na TLB?
s im
não
não (page faul t)
pag da
Tab de Pag es tá
na M em ?
s im
SO ativ a dis pos itiv o
de E/S env iar dados
lê dados da M em
di s pos itiv o de E/S
trans fere página
atualiz a TLB
s im
des c arta/
s ubs titui
M em c heia?
lê dados da TLB
não
SO Atualiz a Tab Pag
gera end real
(NPR + DESL)
c ac he / m em ória
2/18/13
FAFIMAN
32
Questões Importantes



Working Set
Thrashing
Algoritmos de Substituição
 Aleatória
 FIFO
 LRU
 LFU
2/18/13
FAFIMAN
33
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
60t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
1
2
3
4
5
6
7
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
34
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
60t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
2
3
4
5
6
7
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
35
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
60t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
3
4
5
6
7
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
36
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
60t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
4
5
6
7
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
37
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
60t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
5
6
7
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
38
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
60t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
6
7
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
39
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
60t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
7
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
40
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
60t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
41
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
40t
55t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
42
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
50t
35t
55t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
8
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
43
Simulação de Paginação
Fila de Processos
35t
45t
20t
40t
45t
35t
55t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
C2
9
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
44
Simulação de Paginação
Fila de Processos
35t
45t
20t
35t
45t
35t
55t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
C2
D2
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
45
Simulação de Paginação
Fila de Processos
35t
45t
15t
35t
45t
35t
55t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
C2
D2
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
46
Simulação de Paginação
Fila de Processos
35t
40t
15t
35t
45t
35t
55t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
C2
D2
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
47
Simulação de Paginação
Fila de Processos
30t
40t
15t
35t
45t
35t
55t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
C2
D2
10
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
48
Simulação de Paginação
Fila de Processos
30t
40t
15t
35t
45t
35t
50t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
C2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
49
Simulação de Paginação
Fila de Processos
30t
40t
15t
35t
45t
30t
50t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C1
D1
E1
F1
G1
C2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
50
Simulação de Paginação
Fila de Processos
30t
40t
15t
35t
40t
30t
50t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C3
D1
E1
F1
G1
C2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
51
Simulação de Paginação
Fila de Processos
30t
40t
15t
30t
40t
30t
50t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C3
D1
E1
F1
G1
C2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
52
Simulação de Paginação
Fila de Processos
30t
40t
10t
30t
40t
30t
50t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
A1
B1
C3
D1
E1
F1
G1
C2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
53
Simulação de Paginação
Fila de Processos
30t
35t
10t
30t
40t
30t
50t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
F2
B1
C3
D1
E1
F1
G1
C2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
54
Simulação de Paginação
Fila de Processos
25t
35t
10t
30t
40t
30t
50t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
F2
B1
C3
C2
E1
F1
G1
C2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
55
Simulação de Paginação
Fila de Processos
25t
35t
10t
30t
40t
30t
45t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
F2
B1
C3
C2
E1
F1
G1
C2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
56
Simulação de Paginação
Fila de Processos
25t
35t
10t
30t
40t
25t
45t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
F2
B1
C3
C2
E1
F1
G1
B2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
57
Simulação de Paginação
Fila de Processos
25t
35t
10t
30t
35t
25t
45t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
F2
B1
C3
C2
E1
F1
G1
B2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
58
Simulação de Paginação
Fila de Processos
25t
35t
10t
25t
35t
25t
45t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
F2
B1
C3
C2
E1
F1
G1
B2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
59
Simulação de Paginação
Fila de Processos
25t
35t
5t
25t
35t
25t
45t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
F2
B1
C3
C2
E1
E2
G1
B2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
60
Simulação de Paginação
Fila de Processos
25t
30t
5t
25t
35t
25t
45t
G
F
E
D
C
B
A
3p
3p
2p
2p
3p
4p
3p
Memória Real
F2
B1
C3
C2
E1
E2
F3
B2
D2
A2
time-slice = 5t / escalonamento round-robin / remoção de páginas FIFO
2/18/13
FAFIMAN
61
Segmentação





2/18/13
Divisão do Endereçamento
Modularidade do Programa
Tabela de Segmentos
Fragmentação
Estratégias de Alocação de
Espaço Livre
FAFIMAN
62
Exemplo
memória virtual
seg 0
memória real
tab seg
main
1000
seg
base
tam
function A
0
2100
300
seg 2
function B
1
2
1000
1500
200
300
1500
3
disco
500
1800
procedure C
seg 1
function B
seg 2
main
seg 0
1200
seg 1
seg 3
function A
2100
2400
2/18/13
FAFIMAN
63
Estratégias para Alocação
de Espaço Livre
2/18/13

Best-Fit

Worst-Fit

First-Fit
FAFIMAN
64
Fragmentação

Áreas Não-Adjacentes

Estratégias
 Dividir
Segmento do Programa
 Liberar Segmento Adjacente ao Fragmento
 Reagrupar Segmentos Ocupados na MEM
2/18/13
FAFIMAN
65
Segmentação com Paginação
Seg. Virtual
Tab. Seg.
etp = ender. da tab. de
end
ef = ender. do frame
v irt
etp
Mem. Física
ef
ns np desl
ns = nro do segm.
np = nro da pag.
ef
desl
desl = deslocamento
end. físico
2/18/13
FAFIMAN
66
Memória Virtual do Linux
TABELA DE PÁGINAS DE 3 NÍVEIS
p
á
g
in
a
d
ire
tó
rio
g
lo
b
a
l
D
ire
tó
rio
2/18/13
d
ire
tó
rio
In
te
rm
e
d
iá
rio
In
te
rm
e
d
iá
rio
ta
b
e
lad
e
p
á
g
in
a
s
P
á
g
in
a
FAFIMAN
p
a
la
vra
p
ro
cu
ra
d
a
D
e
slo
ca
m
e
n
to
g
67
Alocação de Páginas No Linux
BUDDY ALGORITHM
32
32
32
32
32
32
32
32
8
8
8
8
8
4
4
4
4
4
4
8
8
8
64
16
16
16
32
8
8
16
(1)
2/18/13
(2)
(3)
16
8
8
8
8
8
(4)
(5)
(6)
(7)
(8)
FAFIMAN
(9)
68
Projeto em Grupo
Implementar Núcleo
Com Paginação
2/18/13
FAFIMAN
69
Especificação do Projeto
-
Descartar primitivas de semáforos
-
Descartar aplicação da ponte
-
Implementar primitiva UsaPágina(n,t)
-
Implementar processo GerenteMemória()
-
Readequar a primitiva CriaProcesso()
-
Implementar nova aplicação concorrente
2/18/13
FAFIMAN
70
Primitiva UsaPágina(n,t)
-
Objetivo: simular acesso a página n por um tempo t (loop)
-
Uso: cada processo da aplicação concorrente deverá simular o
acesso a suas páginas de memória. Para cada processo
deverá existir uma tabela de página. O número total de
páginas de cada processo deverá ser passado na primitiva
CriaProcesso(). A chamada a primitiva UsaPágina() deverá
verificar “continuamente” se a página está carregada. Caso a
página não esteja carregada na memória, o processo deverá
ser suspenso em uma fila de espera por falta página.
2/18/13
FAFIMAN
71
Processo GerenteMemória
-
Objetivo:Tratar da fila de espera por falta páginas
-
Uso: Este processo será criado tal como os demais processos
do núcleo e concorrerá ao escalonamento mas não poderá ter
sua execução interrompida. Quando em execução, deverá
tratar o primeiro processo suspenso por falta página e colocar
a página dele na memória (ajustando a tabela de páginas do
processo, retirando-o da fila de suspenso por falta página e
recolocando-o na fila de prontos). A cada execução, limpará a
tela e atualizará graficamente o mapa da memória. Após seu
trabalho devolverá o controle ao escalonador.
2/18/13
FAFIMAN
72
Aplicação Concorrente
-
Objetivo:Implementar vários processos concorrentes
-
Cada Processo:
Loop
:
: :
UsaPagina(1,100);
UsaPagina(2, 200);
UsaPagina(3, 500);
UsaPagina(2, 300);
: :
:
Forever
2/18/13
FAFIMAN
73