Gerenciamento de memória

Nome:Fabio Condelli GirottoFranco Keneti DoiMoon 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

(a ) (b )

F i l a s M ú l t i p l a s

P a rtiç ã o 4 P a rtiç ã o 47 0 0 K

P a rtiç ã o 3 P a rtiç ã o 3F i l a Ú n i c a

4 0 0 K

P a rtiç ã o 2 P a rtiç ã o 2

2 0 0 K

P a r t iç ã o 1P a r t iç ã o 11 0 0 K

S O S O0

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

(a ) (b ) (c ) (d ) (e ) (f) (g)

t e m p o

S O S O S O S O S O S O S O

A A

B

A

B

C

B

C

D

B

C

D

C

D

E

C

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 deMemó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 deMemória

● Listas encadeadas– Existe uma lista ligada que relaciona os blocos de

memória alocados e livres– Normalmente a lista é ordenada por endereço

Antes do Processo Depois do Processo X terminar 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

Algoritmos de Alocação de memória

● First−fit– Escolhe o primeiro buraco aonde o novo

processo caiba● Next−fit

– Escolhe o próximo buraco aonde o processo caiba.

● Best−fit– 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