Gerenciamento de memória
Nome:
Fabio Condelli Girotto
Franco Keneti Doi
Moon Sik Kim
Introdução
TAREFAS
●
●
●
Manter informações em quais partes da memória
estão em uso e quais não.
Alocar e desalocar memória para os processos
Gerenciar o swapping de processos entre a
memória principal e o disco
Gerenciamento de Memória
2 GRUPOS
●
●
Aqueles que trazem e levam os processos entre a
memória principal e o disco durante a execução
(swapping e paginação)
Aqueles que não fazem swapping - que são os
mais simples
Monoprogramação
O esquema de gerenciamento de memória mais
simples possível é ter apenas um processo na
memória por vez e permitir que esse processo use
toda a memória.
●
MONOPROGRAMAÇÃO – sem swapping ou
paginação
Multiprogramação
Mais de um processo na memória ao mesmo tempo.
–
É mais fácil programar uma aplicação que possa
ser quebrada em dois ou mais processos.
–
Computadores de grande porte normalmente
oferecem serviço interativo para vários usuários
simultaneamente, o que requer mais que um
processo presente na memória ao mesmo tempo
para que seja obtido um desempenho razoável .
Gerenciamento de Memória
Multiprogramação com partições fixas
Como a memória deve ser organizada para
suportar multiprogramação?
➔ O modo mais simples é dividir a memória em
"n" partes (possivelmente desiguais).
Multiprogramação
Partições Fixas
Filas Múltiplas
Partição 4
Partição 4
700K
Partição 3
Partição 3
Fila Única
400K
Partição 2
Partição 2
200K
Partição 1
Partição 1
100K
SO
SO
0
(a)
(b)
Swapping
Por exemplo: em um sistema interativo, em que o
tempo é compartilhado entre vários usuários
normalmente existem mais usuários do que memória
para armazenar todos esses processos, de modo que
é necessário manter os processos em excesso no
disco. Para que estes processos possam executar,
eles têm que ser trazidos para a memória principal.
A movimentação dos processos da memória para o
disco e do disco para a memória é chamada de
swapping.
Multiprogramação
Partições Variáveis
Quando partições variáveis são usadas, o número e o
tamanho dos processos variam dinamicamente
●
tempo
B
C
C
C
B
B
B
C
C
E
A
SO
(a)
A
SO
(b)
A
SO
(c)
D
D
D
SO
SO
SO
SO
(d )
(e)
(f)
(g)
Gerenciamento de Memória
Existem pelo menos dois modos de se manter a
informação sobre o uso da memória:
Mapas de bits
● Listas encadeadas
●
Métodos de Gerenciamento de
Memória
●
Bit−map
–
Memória dividida em unidades de alocação
–
Existe um bit−map para sinalizar se cada unidade de
alocação está alocada ou livre
–
Procura por espaços livres não é eficiente
–
Quanto menor for a unidade de alocação, maior o
mapa de bits
Métodos de Gerenciamento de
Memória
●
Listas encadeadas
–
Existe uma lista ligada que relaciona os blocos de
memória alocados e livres
–
Normalmente a lista é ordenada por endereço
Algoritmos de Alocação de
memória
Antes do Processo
X terminar
Depois do Processo
X terminar
(a)
se torna
(b)
se torna
(c)
se torna
(d)
se torna
Combinação de vizinhanças do processo X
(a) A atualização da lista requer a troca de um processo P por um buraco B
(b) e (c) Duas entradas são unidas numa só, e a lista fica com uma entrada a menos
(d) Três entradas são fundidas numa só e dois itens são removidos da lista
Algoritmos de Alocação de
memória
●
First−fit
–
●
Next−fit
–
●
Escolhe o próximo buraco aonde o processo
caiba.
Best−fit
–
●
Escolhe o primeiro buraco aonde o novo
processo caiba
Escolhe o menor buraco. Tende a gerar buracos
pequenos.
Worst−fit
–
Escolhe o maior buraco. Tende a gerar buracos
grandes.
Algoritmos de Alocação de memória
●
Fragmentação
–
externa ocorre quando uma partição está livre e
disponível, mas é muito pequena para acomodar
qualquer processo (portanto inútil)
–
interna ocorre quando um processo que precisa de
"m" palavras de memória, roda numa partição de "n"
palavras, onde n >= m, a diferença entre estes dois
valores (n - m) é a fragmentação interna que é interna
à partição mas não está sendo utilizada.
Memória Virtual
●
●
Processo é dividido em páginas; memória é dividida
em quadros de mesmo tamanho
Páginas/quadros são de pequeno tamanho (em geral
1K): fragmentação interna pequena
●
Elimina fragmentação externa
●
SO mantém uma tabela de páginas por processo
●
Processo não precisa estar completamente na MP
●
●
Processo não precisa ocupar área contígua em
memória
Endereços são gerados dinamicamente em tempo de
execução
Memória Virtual
computador que pode gerar endereços de 16 bits, de 0 à 64K
Vantagens da paginação
●
●
●
●
Mais processos (pedaços!) podem estar na
MP
Mais provável de existirem processos na fila
dos prontos
Processos podem ser maiores que a MP (tão
grandes quanto a MS)
Reduz o tempo de swapping
Substituição de páginas
●
Quando ocorre uma falha de páginas, o SO tem
que escolher uma página para ser removida da
memória de modo a dar lugar para a outra página
que tem que ser trazida. Pode então ocorrer duas
situações:
–
Se a página a ser removida foi modificada enquanto
estava na memória, ela tem que ser reescrita para o
disco para que a cópia em disco fique atualizada.
–
Se a página não foi modificada (por ex., a página contém
o texto do programa), a cópia já está atualizada e
portanto não precisa ser reescrita.
Substituição de páginas
●
A questão sobre qual página deve ser
removida da memória sempre que ocorrer
uma falha de página levou à criação de
vários algoritmos
Algoritmo Ótimo de
Substituição de Página
 No momento em que ocorrer uma falha de página, um
conjunto de páginas vai estar na memória
 Uma destas páginas vai eventualmente ser referenciada
numa instrução
 Outras páginas podem não ser referenciadas nas próximas
10, 100 ou talvez 1000 instruções
 Cada página pode ser rotulada com o número de instruções
que vão ser executadas antes daquela página ser
referenciada pela primeira vez
 O algoritmo ótimo de substituição de página diz
simplesmente que a página que contiver o rótulo mais alto
deve ser removida. Se uma página não vai ser referenciada
nas próximas 8 milhões de instruções, e uma outra página
não vai ser referenciada nas próximas 6 milhões de
instruções, a remoção da primeira página adia uma possível
falha de página, que vai buscá-la de volta, o máximo
possível.
Algoritmo Ótimo de
Substituição de Página
●
●
O melhor algoritmo possível de substituição de
página é fácil de descrever mas impossível de
implementar.
O problema com este algoritmo é que ele é
irrealizável. Vejamos porque:

No momento que ocorre uma falha de página, o SO não
tem meios de saber quando cada uma das páginas vai
ser referenciada em seguida;
 Rodando um programa no simulador e mantendo
informação sobre todas as referências de páginas é
possível implementar este algoritmo numa segunda
rodada usando a informação sobre as referências de
páginas coletadas na primeira rodada do programa.
Substituição da Página não
Utilizada Recentemente
●
De modo a permitir que o SO colete
estatísticas úteis sobre quais páginas estão
sendo usadas e quais não, a maioria dos
computadores com memória virtual tem dois
bits associados a cada página:

Bit R, ou bit de referência, é setado toda vez que
a página é referenciada
 Bit M, ou bit de modificação, é setado toda vez
que a página é modificada
Substituição da Página não
Utilizada Recentemente
●
●
Estes bits têm que ser atualizados a cada
referência à memória, por isso é essencial
que eles sejam setados pelo hardware. Uma
vez que um bit tenha sido setado para 1, ele
permanece 1 até que o SO reseta ele para 0
em software.
Os maiores atrativos deste algoritmo são:
–
–
–
fácil entendimento
eficiente para implementar
dá um desempenho que apesar de não ser
ótimo, é bastante adequado
Algoritmo de Substituição de
Páginas pela ordem FIFO
●
Neste algoritmo o SO mantém uma lista de
todas as páginas atualmente na memória,
onde a cabeça da lista contém a página mais
antiga e o final da lista contém a página que
chegou mais recentemente. Na ocorrência
de uma falha de página, a página na cabeça
de lista é removida e a nova página é
adicionada no final da lista.
Algoritmo de Substituição de
Páginas pela ordem FIFO
●
O problema com a FIFO é que uma página
altamente utilizada pode ser retirada da
memória. Um modo de prevenir-se contra
isto é através de uma pequena modificação
que envolve o seguinte:
–
–
–
Inspecionar os bits R e M da página mais antiga
Se a página pertencer à classe 0 ela é removida,
senão a próxima página mais velha é
inspecionada e assim por diante
Se não houverem páginas na classe 0 presentes
na memória, o algoritmo é então repetido para
as classes 1, 2 e 3.
Algoritmo de Substituição da
Página Menos Utilizada
Recentemente
●
Aproximação do algoritmo ótimo é baseada
na seguinte observação:
As páginas que foram altamente utilizadas nas
ultimas instruções serão, provavelmente,
altamente utilizadas novamente nas
próximas instruções. Reciprocamente, as
páginas que não têm sido utilizadas há
longo tempo vão permanecer,
provavelmente, sem uso por um longo
tempo.
Algoritmo de Substituição da
Página Menos Utilizada
Recentemente
●
●
A implementação deste algoritmo consiste
em manter uma lista encadeada de todas as
páginas na memória, com a página mais
usada recentemente na cabeça da lista, e a
menos usada no final da lista.
A maior dificuldade aqui, é que a lista tem
que ser atualizada a cada referência à
memória o que são operações que
consomem muito tempo.
Segmentação
●
●
A paginação implementa um amplo espaço
linear numa memória física limitada, onde os
programas são executados num segmento
contínuo de memória.
Na segmentação, esta restrição é removida
sendo permitido a um programa (e seus
dados) ocupar vários segmentos separados
de memória real.
Segmentação
●
●
Um segmento é uma entidade lógica, que o
programador sabe que existe e usa como
uma única entidade lógica.
Um segmento pode conter um procedimento,
um arranjo, uma pilha, uma coleção de
variáveis escalares, mas normalmente não
contém uma mistura de tipos diferentes.
Segmentação
●
●
●
Com uma memória unidimensional, os
procedimentos são empacotados uns próximos aos
outros, sem qualquer espaço de endereços entre
eles.
Consequentemente, a alteração do tamanho de um
procedimento pode afetar o endereço inicial de
outros procedimentos não relacionados.
Isto requer a modificação de todos os
procedimentos que chamam quaisquer dos
procedimentos movidos, de modo a incorporar
seus novos endereços iniciais
Segmentação
●
Deve-se entender que a proteção faz sentido
numa memória segmentada mas não numa
memória unidimensional paginada. Numa
memória segmentada, o usuário sabe o que
há em cada segmento. Normalmente, um
segmento não conteria um procedimento e
uma pilha, por exemplo, mas sim um ou
outro.
Comparação