Memória Virtual

Transcrição

Memória Virtual

Laboratório de Sistema de Distribuídos – LaSiD
Departamento de Ciência da Computação – DCC
UFBA
Gerenciamento de
Memória
Prof. Raimundo Macêdo
Tópicos
) Introdução
) Particionamento
P ti i
t de
d memória
ói
) Swapping
) Memória virtual/Paginação
) Segmentação
) Exercícios
LaSiD - Laboratório de Sistemas Distribuídos
http://www.lasid.ufba.br
1
Tópicos
) Introdução
) Particionamento
P ti i
t de
d memória
ói
) Swapping
) Memória virtual/Paginação
) Segmentação
) Exercícios
Motivação para gerenciamento
)Em geral a memória principal não comporta todos
os processos ativos num determinado momento
9 O S.O. deve manter os processos que estejam fazendo uso efetivo
da memória ou que sejam prioritários
9 Em geral apenas parte do processo (espaço lógico) é carregado
9 Requisitos de memória,
memória freqüência de uso e prioridades variam
dinamicamente
Tempo de resposta
9Objetivos finais
Throughput (número de tarefas executadas)
2
O Problema
)alocar espaço de memória para processos
9Monoprogramação: duas partes
ÊSO + um processo
p
9Multiprogramação: várias partes
ÊSO + vários processos
9Alguns problemas...
ÊComo organizar os espaços de memória?
ÊQuando mapear (bind) endereço de programa em end. de
memória?
ÊEm que posição da memória?
ÊComo proteger um processo da invasão de sua área ou
permitir um compartilhamento controlado de sua área?
3
Background
1. Program must be brought into memory
and placed within a process for it to be
run.
2. Input queue – collection of processes
on the disk that are waiting to be
brought into memory to run the
pprogram.
g
3. User programs go through several
steps before being run.
Multistep Processing of a User Program
4
Logical vs. Physical Address Space
) The concept of a logical address space that is bound
to a separate
p
pphysical
y
address space
p
is central to
proper memory management.
9 Logical address – generated by the CPU; also referred to as
virtual address.
9 Physical address – address seen by the memory unit.
) Logical and physical addresses are the same in
compile-time and load-time address-binding
schemes; logical (virtual) and physical addresses
differ in execution-time address-binding scheme.
Binding of Instructions and Data to Memory
Address binding of instructions and data to memory addresses can
happen at three different stages:
1. Compile time: If memory location known a
priori, absolute code can be generated; must
recompile code if starting location changes.
2. Load time: Must generate relocatable code if
memory location is not known at compile time.
3. Execution time: Binding delayed until run time
if the process can be moved during its execution
from one memory segment to another. Need
hardware support for address maps (e.g., base and
limit registers).
5
Memory-Management Unit (MMU)
) Hardware device that maps virtual to physical
address.
) In MMU scheme, the value in the relocation register
is added to every address generated by a user process
at the time it is sent to memory.
) The user program deals with logical addresses; it
never sees the real physical addresses.
addresses
Dynamic relocation using a relocation
register
6
Dynamic Loading
)Routine is not loaded until it is called
)Better memory-space utilization; unused
routine is never loaded.
)Useful when large amounts of code are
needed to handle infrequently occurring
cases.
)No special support from the operating system
is required implemented through program
design.
Tópicos
Introdução
P ti i
Particionamento
t de
d memória
ói
Swapping
Memória virtual/Paginação
Segmentação
Exercícios
7
Partições Iguais de Tamanho Fixo
(como gerenciar a mem. entre os processos?)
Memória Principal
)Problema
9Dificilmente os processos têm
o tamanho da partição
Êfragmentação interna
SO
Partições Diferentes de Tamanho Fixo
)Filas Múltiplas X Fila Única
Memória
Principal
Novos
Processos
Memória
Principal
Novos
Processos
SO
SO
8
Partições Diferentes de Tamanho Fixo
)Filas Múltiplas
9 um processo pode esperar muito para começar a execução,
mesmo se existe espaço disponível
)Fila Única
9 pode-se percorrer a fila para achar o processo com tamanho
mais adequado para a partição disponível
Ê discriminação de processos pequenos (p.e., processos interativos)
9 outras estratégias de escolha
Ê um processo não pode deixar de usar a memória mais que k vezes
Ê reservar partições pequenas
Partições de Tamanho Variável
)pontos fracos das partições fixas
9pequenos processos desperdiçam memória
9pouca flexibilidade
)solução
9criar partições dinamicamente:
Êdar ao processo o que for necessário
9
Partições de Tamanho Variável
SO
SO
SO
SO
SO
SO
SO
SO
)aspectos:
9fragmentação externa:
Ê necessidade de compactação (desfragmentação) da memória
9tamanho dos processos:
Ê alocação de espaço extra para alocação dinâmica (heap e
pilha)
Gerenciando a Alocação da Memória
)Mapa de Bits
9 Dividir a memória em unidades de alocação
9 Cada unidade está relacionada com um bit
Ê Tamanho da unidade X Tamanho do mapa de bits
9 Na alocação de memória (n unidades de alocação)
Ê busca-se por n bits consecutivos indicando memória livre
Ê Ponto fraco: algoritmo de busca seqüencial
Memória
Principal
Mapa de Bits
Processo 1
Espaços
Processo 2
...
Processo n
111110000111111...111
10
Gerenciando a Alocação de Memória
)Lista Ligada
9Ordenada por endereço: facilita a atualização da lista
ÊDois espaços consecutivos se transformam em apenas um
Memória
Principal
Lista Ligada
Processo 1
P|0|5
Espaços
E|5|4
Processo 2
P|9|6
...
...
Processo n
P|x|y
Algoritmos de Alocação
) first fit:
9 busca o primeiro espaço no qual o processo cabe
) next fit:
9 semelhante a first fit, mas a busca não começa do início
) best fit:
9 busca espaço com tamanho mais próximo do tamanho do processo
) worst fit:
9 busca o espaço com a pior aproximação de tamanho
) first fit: algoritmo com melhor desempenho e melhor uso de
memória
11
Sistema Buddy de Alocação
)Características
9 Rápida alocação
9 Listas de espaços com tamanhos potências de 2
9 Fragmentação interna
0
P1: 140 K
P2: 70 K
P3: 130 K
P3: 35 K
256 K
256 K
256 K
256 K
256 K
128K
128K
128K 64K
tempo
1 Mb
512 K
256 K
256 K
OBS: o SO mantém listas de alocação por potência de 2
12
RELOCAÇÃO
)Quando um programa é carregado na
memória o enrereço real (atual) é determinado
memória,
)Um processo pode ocupar diferentes posiçoes
de memória durante a execução (causado por
swapping)
13
Endereços
)Logico
9 Referente a uma localização de memória
independente de associações atuais
9 É necessário tradução para end. físico
)Relativo
9 Expressado como um enrereço relativo a algum
ponto conhecido
)Físico
9 Enrereço absoluto ou atual na memória principal
Relocação e Proteção
)Endereçamento relativo
End. Relativo (X)
Início do
Processo
Reg. Base
Somador
Comparador
LDA X
X
Reg Limite
Reg.
Interrupção
14
Tópicos
Introdução
P ti i
Particionamento
t de
d memória
ói
Swapping
Segmentação
Exercícios
Swapping
) ação de mover processos entre a memória e o disco
p
a limitação do tamanho de memória
) mecanismo ppara superar
) swap space: área para armazenar processos no disco durante
swapping
) algoritmos de alocação do processo no disco semelhantes aos de
alocação na memória
15
Tópicos
Introdução
P ti i
Particionamento
t de
d memória
ói
Swapping
Segmentação
Exercícios
Memória Virtual
) o tamanho total da área de código, dados e pilha pode exceder o
tamanho da memória física
) o sistema operacional mantém as partes do programa em uso na
memória e as outras partes em disco
) os endereços gerados nos programas são chamados endereços
virtuais
) os endereços virtuais formam o espaço de endereçamento virtual
16
Suporte de hardware necessário
Para memória virtual
)Suporte de HW para paginação e
segmentação
)O SO tem que gerenciar o deslocamento
d páginas
de
á i
e segmentos
t entre
t a memória
ói e
o disco
Paginação
)Cada processo possui uma tabela de
páginas
)Cada entrada na tabela de página contêm
o número de um frame para a memória
principal
)Um bit é necessário para indicar se a
página está na memória
17
Bit de modifiação
)Outro bit é necessário para indicar se a
pagina foi modificada desde sua última
carga na memória
)Caso não tenha ocorrido alterações, a
página não necessita ser “swapped
swapped out
out”
Entradas da tabela de página
18
Two-Level Scheme for
32-bit Address
19
Tabelas de Páginas
)A tabela de páginas pode ocupar espaço
demais da memória
)Tabelas de páginas são também
colocadas em memória virtual
)Quando o processo está rodando, parte
da tabela de página está na memória
Translation Lookaside Buffer
)Each virtual memory reference can
cause two physical memory accesses
9one to fetch the page table entry
9one to fetch the data
)To overcome this problem a high-speed
cache is set upp for page
p g table entries
9called the TLB - Translation Lookaside
Buffer
20
)Contains page table entries that have
been most recently used
)Functions same way as a memory cache
)Given a virtual address, processor
examines the TLB
)If page table entry is present (a hit), the
frame number is retrieved and the real
address is formed
)If
If page table entry is not found in the
TLB (a miss), the page number is used
to index the process page table
21
)First checks if page is already in main
memory
9if not in main memory a page fault is issued
)The TLB is updated to include the new
page entry
22
Page Size
)Smaller page size, less amount of internal
fragmentation
g
)Smaller page size, more pages required per
process
)More pages per process means larger page
tables
)Larger page tables means large portion of page
tables
bl in
i virtual
i
l memory
)Secondary memory is designed to efficiently
transfer large blocks of data so a large page
size is better
Page Size
)Small page size, large number of pages
will be found in main memory
)As time goes on during execution, the
pages in memory will all contain
portions of the process near recent
references. Page faults low.
)Increased page size causes pages to
contain locations further from any recent
reference. Page faults rise.
23
Page Size
)Small page size, large number of pages
will be found in main memory
)As time goes on during execution, the
pages in memory will all contain
portions of the process near recent
references. Page faults low.
)Increased page size causes pages to
contain locations further from any recent
reference. Page faults rise.
24
Memória Virtual (cont.)
a CPU envia endereços
virtuais para a UGM
Placa
com CPU
CPU
Memória
Unidade de Gerenciamento
de Memória (UGM)
Controlador
de disco
a UGM envia
endereços físicos
para a memória
Barramento
Paginação
)Idéia Básica
9Dividir a memória (p
(page
g fframes)) e o pprocesso em
pedaços pequenos (páginas virtuais)
)Semelhante às partições de tamanho fixo
9Páginas são menores
9Um processo pode ocupar mais que uma página
9A páginas
9As
á i
não
ã precisam
i
ser alocadas
l d continuamente
i
25
Tabela de Páginas
espaço
de end.
virtual
0-4K
4K-8K
8K-12K
12K-16K
16K-20K
20K-24K
24K-28K
28K-32K
32K-36K
36K-40K
40K-44K
44K-48K
48K-52K
52K-56K
56K-60K
60K-64K
2
1
6
0
4
3
X
X
X
5
X
7
X
X
X
X
0-4K
4K-8K
8K-12K
12K-16K
16K-20K
20K-24K
24K-28K
28K-32K
endereços
d
de memória
física
page frame
página virtual
Paginação: Tabelas de Páginas
0
0 0
0 2
0 3
1 1
1 9
1 4
2 6
2 10
2 5
3 7
3 11
Memória
Principal
1
2
3
4
5
Tabelas de Páginas
6
7
8
9
10
11
26
Operação Interna da UGM
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
endereço virtual: 8196
0010 000000000100
010
001
110
000
100
011
000
000
000
101
000
111
000
000
000
000
1
1
1
1
1
1
0
0
0
1
0
1
0
0
0
0
110 000000000100
endereço físico de saída: 24580
Paginação: Endereçamento
) Ilustração do Procedimento de
Endereçamento
9 Exemplo
l
Ê Tamanho da Página: 2K
Ê Tamanho do Processo: 4,5 K
Ê Endereço Relativo: 05DE
Número de
Página
Deslocamento
0 0
1 1
Processo
2 7
5DE
00000
10111011110
05DE
Tabela de Página
27
Exemplo de Entrada da
Tabela de Páginas
ppresente/ausente
modificada
número do page frame
referenciada
proteção
Exemplos de tamanho de páginas
28
Objetivos da Substituição de Páginas
)Objetivo Principal
9 Minimizar o número de faltas de páginas
)Conseqüentemente...
9 Minimizar a sobrecarga do sistema operacional
9 Minimizar o número de I/O
9 etc
Substituição de Páginas
Páginas virtuais referenciadas são colocadas na memória até que
todas as molduras (frames) estejam preenchidas
Quando não há mais molduras vazias, escolhe-se uma das
que estão ocupadas. Qual ????
Fatores que influenciam:
1) A seqüência
üê i de
d referências
f ê i (endereços
( d
das
d páginas)
á i )
2) O número de molduras disponíveis
3) O algoritmo de substituição
29
Algoritmos de Substituição de Páginas
1. Algoritmo ótimo
2. Página
g não usada recentemente: NRU ((Not-Recently-Used
y
ppage)
g )
3. First-In, First Out (FIFO)
4. Segunda Chance
5. Algoritmo do Relógio
6. Substituição da página menos recentemente usada: LRU (Least
Recently Used)
Anomalia de Balady : nem sempre é verdadeiro que quanto
mais molduras,, menos faltas de p
página
g
ocorrerão.
Quando uma página
referenciada não está na
memória
Exemplo :
Seqüência : 0 1 2 3 0 1 4 0 1 2 3 4
3 e 4 molduras
Algoritmo FIFO
30
Algoritmo Ótimo
) o frame a ser substituído é o que será referenciado por último
) impossível
i
í l de
d ser implementado
i l
t d
) útil para análises comparativas de comportamento de algoritmos
Página não Usada Recentemente (NRU)
) os seguintes bits são mantidos para cada página:
9 R- página referenciada (lida ou escrita)
9 M -página
á i modificada
difi d
) classes
9
9
9
9
Classe 0: R=0 e M=0
Classe 1: R=0 e M=1
Classe 2: R=1 e M=0
Classe 3: R=1 e M=1
Algoritmo: remover
aleatoriamente uma página
procurando da classe 0 à classe 3
) fácil de programar, bom desempenho e simples
31
Algoritmo FIFO
) mantém-se uma lista de páginas ordenada por tempo de carga
) algoritmo:
9 primeira página carregada, primeira página a sair
) simplicidade
) ponto fraco: o critério não é bom
9 páginas antigas podem estar sendo muito referenciadas
Algoritmo da Segunda Chance
) baseado no algoritmo FIFO
) usa o bit R
R. Se R=1
R=1, faz R=0 e coloca a página no final da fila
Lista de Páginas
R=1 R=0 R=0 R=1 R=1
Lista de Páginas
Lista de Páginas
R=0 R=0 R=0 R=1 R=0
R=0 R=0 R=1 R=0 R=0
32
Algoritmo do Relógio
) forma alternativa de implementação do algoritmo de segunda
chance
) mantém uma lista circular de páginas com um apontador para a
página mais antiga
) se R=0, substitui a página e atualiza o apontador
) se R=1, atualiza o apontador
Lista de
Páginas
Lista de
Pá i
Páginas
R=1
R
1
R=1
R=0
R=0
R=0
R=0
R=0
Lista de
Páginas
R=1
R=0
R=0
R=0
R=0
R=1
R=0
R=0
Algoritmo da
Página Menos Recentemente Usada (LRU)
) baseia-se no princípio da localidade de referência
) remove a página
á i usada
d há mais
i tempo
t
) algumas implementações:
9 em hardware
9 em software
33
Implementação de LRU em hardware (1)
) equipar o hardware com um contador C que automaticamente
tem seu valor incrementado a cada instrução
ç
) cada entrada na tabela de páginas tem um campo para um valor
do contador
) depois de cada acesso à memória, o valor de C é armazenado na
entrada da página acessada
) quando uma página tiver que sair, escolhe-se a página com
menor valor do contador
Implementação de LRU em hardware (2)
) mantém-se uma matriz M(n x n), onde n é o número de
páginas
) algoritmo
9 M←0
9 se página k for referenciada
Ê M[k,*] ← 1
Ê M[*,k] ← 0
9 a linha com menor número de bits será a página referenciada há mais
tempo
Problema: SO
dependente do
Hardware
34
Implementação de LRU por software
) pequena variação de LRU (aging)
) manter um contador associado a cada página e periodicamente:
9 ddeslocar
l
os bits
bi do
d contador
d para a direita
di i
9 somar o bit R à parte mais significativa
) escolhe a página com menor valor do contador
Obs.: dentro de um
intervalo pode
haver várias
referências
P1 P2 P3 P4 P5
R: 1 0 1 1 0
R: 0 1 0 1 0
C1: 1000
C2: 0000
C3: 1000
C4: 1000
C5: 0000
C1: 0100
C2: 1000
C3: 0100
C4: 1100
C5: 0000
Questões de Projeto
de Sistemas de Paginação
)
)
)
)
políticas de carregamento de páginas
políticas
líti
dde alocação
l
ã ((global/local)
l b l/l l) de
d páginas
á i
tamanho das páginas
aspectos de implementação
35
Políticas de Carregamento de Páginas
) por demanda
9 uma página é carregada apenas quando uma referência a ela é feita
(falta de página)
9 pode haver muitas faltas de página no início do processo, depois há
uma estabilização
) pré-paginação
9 antecipa-se às faltas de páginas, trazendo para a memória um
conjunto de páginas
9 pode ser usada no início do processo ou quando o processo é rere
escalonado para executar (trazido do disco para memória)
9 baseia-se no working set do processo (conjunto de páginas sendo
acessadas pelo processo)
Políticas de
Alocação (global/local) de páginas
) alocação local: considera-se somente um processo
) alocação
l
ã global:
l b l consideram-se
id
t d os processos na memória
todos
ói
9 em geral funciona melhor, principalmente quando o working set pode
variar
) quantas páginas alocar por processo
9 a cada processo um número fixo de frames
Ê se for menor que o conjunto de trabalho do processo?
9 a cada processo um número variável de frames
Ê se o número de faltas for alto, mantém mais páginas na memória
Ê custo de gerenciamento: mais um ponto para ser controlado
36
Tamanho das Páginas
)páginas pequenas x páginas grandes:
9 páginas pequenas:
Ê tendem a uma menor fragmentação interna
Ê tendem a um melhor uso da memória
9 páginas grandes:
Ê tendem a melhor eficiência (menos páginas sendo movidas para/de o
disco (swapped))
Aspectos de Implementação
) trancas (locks) em molduras
9 algumas molduras podem ser trancadas (locked) e não podem ser retiradas
da memória (suporte a operação de I/O)
) quando uma página modificada será escrita em memória
secundária
9 por demanda
Ê somente quando a página é selecionada para ser substituída
Ê minimiza o número de escritas
Ê aumenta o tempo de substituição de páginas
9 pré-atualização
Ê antes de ser substituída (periodicamente, várias páginas que sofreram
atualização são escritas no disco)
Ê manutenção de um conjunto de frames livres
37
Aspectos de Implementação (cont.)
) buffer de informação sobre a tabela de páginas em cache interno à
UGM (translation lookaside buffer)
9 reduzir o número de acessos à memória
Tópicos
Introdução
P ti i
Particionamento
t de
d memória
ói
Swapping
Segmentação
Exercícios
38
Segmentação
) Idéia Básica
9 Dividir o processo em segmentos não necessariamente de tamanhos iguais
) Características
9 Esquema de endereçamento
Ê tabelas de segmentos para indicar o tamanho do segmento e o endereço base
9 Podem ser de tamanhos diferentes
9 Visível para o programador ou para o compilador
Ê geralmente definem-se segmentos de dados, código, pilha etc
9 partes de um programa podem mudar de tamanho independentemente de
outras
9 auxilia na implementação de bibliotecas compartilhadas
Exemplo de Segmentação:
Tabelas de um Compilador
segmento 0
segmento 1
segmento 2
segmento 3
segmento 4
árvore
de
parsing
pilha
de
chamadas
constantes
texto
fonte
tabela
de
símbolos
Array ...
39
Segmentação Pura
segm.0
4K
g
segm.7
5K
segm.0
4K
segm.7
g
5K
segm.0
4K
segm.7
g
5K
3K
3K
3K
segm.2
5K
segm.2
5K
segm.2
5K
segm.3
8K
segm.3
8K
segm.3
8K
segm.2
5K
segm.6
4K
4K
segm.4
7K
segm.4
7K
segm.5
4K
3K
segm.0
4K
segm.1
8K
segm.0
4K
segm.7
g
5K
segm.2
5K
segm.6
4K
segm.5
4K
segm.5
4K
3K
10K
Segmentação com Paginação
tabela de descritores
de segmentos
segm. 0
segm. 1
tabela de páginas para segmento 0
pág. 0
pág. 1
ponteiros
para páginas
á i
pág. 2
segm. 2
segm. 3
tabela de páginas para segmento 1
segm. 4
segm 5
segm.
pág. 0
pág. 1
ponteiros
i
para páginas
pág. 2
40
Obtenção de Endereço Físico
com Segmentação
Endereco virtual : {#seg, deslocamento)
seletor de
segmento
deslocamento
descritor
endereço base
+
limite
outros campos
endereço linear
endereço físico
tradução de endereço em
segmentação pura
#seg
Deslocmento d
base + d
Tam | Base | bit P
tam
Tabela de Segmento
por processo
41
tradução de endereço em
segmentação com paginação
num página #p, desl. página d
#seg
Deslocmento
#p’
#P
#p’
end físico
#p’ + d
#tab Página
Tabela de Segmento
por processo
tab de páginas, uma por seg.
Entrada da tabela de segmentos
42
P t ã
Proteção
E
Compartilhamento
Exercícios
Extraídos de Modern Operating Systems, A.S.Tanenbaum, Prentice Hall, Inc. 1992
1. Considere um sistema de swapping em que a memória consiste dos
seguintes tamanhos de espaços (em ordem de memória): 10K, 4K,
20K, 18K, 7K, 9K, 12K e 15K. Qual espaço é usado para pedidos
sucessivos de segmentos de
(a) 12K
(b) 10K
(c) 9K
usando-se first fit? Repita a questão para best fit, worst fit e next fit.
43
Exercícios (cont.)
2. Um minicomputador usa o sistema buddy para gerenciamento de
memória. Inicialmente ele tem um bloco de 256K no endereço
ç 0.
Depois de pedidos sucessivos de 5K, 25K, 35K e 20K, quantos
blocos existirão no sistema e quais serão seus tamanhos e
endereços?
3. Qual a diferença entre um endereço físico e um endereço virtual?
4. Usando a tabela de página da Fig. 3-11, dê o endereço físico
correspondente
co
espo de te a cada um
u dos endereços
e de eços virtuais
v tua s seguintes:
segu tes:
(a) 20
(b) 4100
(c) 8300
Exercícios (cont.)
5. Um computador tem 4 page frames. O tempo de carregamento,
tempo de último acesso e os bits M e R para cada página estão
mostrados abaixo (tempos em clock ticks):
Page frame Carregado
Últ.referência R M
0
126
279
0 0
1
230
260
1 0
2
120
272
1 1
3
160
280
1 1
(a) que página seria substituída por NRU?
(b) que página seria substituída por FIFO?
(c) que página seria substituída por LRU?
(d) que página seria substituída por Segunda Chance?
44
Exercícios (cont.)
6. Se o algoritmo FIFO de substituição de páginas é usado com
quatro page frames e oito páginas virtuais, quantas faltas de
páginas ocorrerão para a cadeia de referências 0172327103 se os
quatro page frames estão inicialmente vazios? Repita o problema
para LRU.
7. Um pequeno computador tem quatro page frames. No primeiro
clock tick os bits R são 0111 (página 0 à esquerda). Em clock
ticks subseqüentes os valores são 1011, 1010, 1101, 0010, 1010,
1100 e 0001. Se o algoritmo de aging for usado com um contador
de 8 bits, dê os valores dos quatro contadores depois do último
tick.
45

Memória Virtual

Transcrição

Documentos relacionados

Formulário Prudential Foundation TWC

Escolas Públicas de Framingham

Junho - faced

http://raulhc.cc

FORMULÁRIO DE HOSPEDAGEM DE SITE (F-AT-04)

Microsoft PowerPoint - Seguran\347a na Rede - PoP-BA

instituiç ão tema título orientador/ departament o membros - Crea-BA

Programação_Seminário_Fortunati e Horn_de

AAI seleciona Estudantes de Graduação para Intercâmbio

Solicitação de Videoconferência PDF