2009 1 - sistemas operacionais - aula 8 - memoria

1Pearson Education Sistemas Operacionais Modernos – 2ª Edição

Sistemas Operacionais-Gerência de Memória

Ernesto Massa

(slides fornecidos pela Prentice Hall e adaptados para esta disciplina)


Gerenciamento de Memória

Idealmente, o que se deseja é dispor de uma memória que seja Grande, rápida e não volátil.

Hierarquia de memórias Cache

pequena quantidade de memória rápida, de alto custo.

Memória Principal Quantidade considerável de velocidade

média, custo médio. Armazenamento em disco

Velocidade e custo baixos.


Gerenciamento de Memória

Algumas funções do Gerenciador de memória: Controlar quais as unidades de memória estão

ou não estão em uso, para que sejam alocadas quando necessário;

Liberar as unidades de memória que foram desocupadas por um processo que finalizou;

Tratar do Swapping entre memória principal e memória secundária.

Transferência temporária de processos residentes na memória principal para memória secundária.


Gerenciamento Básico de Memória: Monoprogramação

Sistema operacional com apenas um processo de usuário

(a) Inicialmente utilizados em Mainframes(b) Sistemas Embarcados(c) Primeiros Microcomputadores Pessoais


Alocação Contígua Simples

Alocação implementada nos primeiros sistemas e ainda usada nos monoprogramáveis;

A Memória é dividida em duas áreas: Área do Sistema Operacional Área do Usuário

Um usuário não pode usar uma área maior do que a disponível;

Sem proteção: Um usuário pode acessar a área

do Sistema Operacional.

Memória principal

Sistema Operacional

Área deProgramas do usuário



Registrador de proteção delimita as áreas do sistema operacional e do usuário;

Sistema verifica acessos à memória em relação ao endereço do registrador;

A forma de alocação era simples, mas não permitia utilização eficiente de processador e memória;

Memória principal

Sistema Operacional

Área deProgramas do usuário

Reg



Programas de usuário limitados pelo tamanho da memória principal disponível.

Solução: Overlay Dividir o programa em módulos; Permitir execução independente

de cada módulo, usando a mesma área de memória;

Área de Overlay Área de memória comum onde

módulos compartilham mesmo espaço.

Memória principal

Sistema Operacional

Área deOverlay

Área do Módulo Principal

A B C


Multiprogramação:Alocação Particionada

Multiprogramação. Necessidade do uso da memória por vários usuários

simultaneamente. Ocupação mais eficiente do processador; A memória foi dividida em pedaços de tamanho

fixo chamados partições; O tamanho de cada partição é estabelecido na

inicialização do sistema; Para alteração do particionamento, é necessário

uma nova inicialização com uma nova configuração.


Alocação Particionada Estática

Proteção: Registradores com limites

inferior e superior de memória acessível.

Programas não ocupam totalmente o espaço das partições, gerando uma fragmentação interna.

Memória principal

Sistema Operacional

Partição C

Partição A

Reg

Reg

Partição B


Alocação Particionada Estática

Alocação Particionada Estática Absoluta: Compiladores gerando código absoluto;

Endereços relativos ao início da memória; Programas exclusivos para partições

específicas.

Alocação Particionada Estática Relocável: Compiladores gerando código relocável;

Endereços relativos ao início da partição; Programas podem rodar em qualquer partição.


Multiprogramação com Partições Fixas (Estática)

Partições fixas de memória (a) Filas de entrada para cada partição (b) Fila única de entrada


Alocação Particionada Dinâmica

Não existe o conceito de partição dinâmica. O espaço utilizado por um

programa é a sua partição. Não ocorre fragmentação

interna. Ao terminarem, os programas

deixam espalhados espaços pequenos de memória, provocando a fragmentação externa.

Memória principal

Sistema Operacional

Processo E

Processo A

Processo C

Processo F


Considerações sobreRelocação e Proteção

Não se sabe com certeza onde o programa será carregado na memória As Localizações de endereços de variáveis e de

código de rotinas não podem ser absolutos Soluções:

Instruções do programa são modificadas segundo a partição de memória em que ele será carregado

Uma solução para relocação e proteção: uso de registradores com valores base e limite

As localizações de endereços são somadas ao valor base antes de serem mapeadas na memória física

Referência a endereços superiores ao limite indicam erro.


Alocação Dinâmica:Troca de Processos (ou Swapping)

Alterações na alocação de memória à medida que processos entram e saem da memória

Regiões sombreadas correspondem a regiões de memória não utilizadas naquele instante


Alocação Dinâmica:Troca de Processos (ou Swapping)

Um processo residente na memória é levado para o disco (Swapped-Out), dando lugar a outro;

O processo Swapped-Out retorna à memória (Swapped-In), sem “perceber” o que ocorreu.

programa B

programa A

programa E

programa A

programa G

Sistema Operacional

Memória principal

programa H

programa E

programa A

B B

Swap InSwap Out

Sistema Operacional

programa B


Memória Extra

Alocação de espaço para uma área de dados em expansão

Alocação de espaço para uma pilha e uma área de dados, ambos em expansão


Gerenciamento de Memória com Mapas de Bits e Lista Encadeada

Parte da memória com 5 segmentos de processos e 3 segmentos de memória livre

pequenos riscos simétricos denotam as unidades de alocação

regiões sombreadas denotam segmentos livres Mapa de bits correspondente Mesmas informações em uma lista encadeada


Gerenciamento de Memóriacom Listas Encadeadas

Quatro combinações de vizinhança para o processo X em término de execução


Algoritmos de Alocação de Memória

Best-Fit (melhor ajuste): Worst-Fit (pior ajuste): First-Fit (primeiro ajuste): Next-Fit (próximo ajuste): Todos melhoram em performance se existirem listas

distintas para processos e espaços, embora o algoritmo fique mais complexo.

Listas ordenadas por tamanho de espaço melhoram a performance.


Modelagem de Multiprogramação

Utilização da CPU como uma função do número de processos na memória


Análise de Desempenho de Sistemas de Multiprogramação

Chegada de 4 jobs e suas necessidades de trabalho Utilização da CPU por até 4 jobs com 80% de espera por

E/S

Sequência de eventos entre a chegada e o término dos jobs

Note que os números mostram quanto tempo da CPU cada job obtém em cada intervalo


Memória Virtual

Técnica onde memória principal e secundária são combinadas de forma a “emular” uma memória de tamanho maior que a memória principal (real);

A memória secundária é usada como extensão da memória principal;

Permite um maior número de processos compartilhando a memória principal;

Não vincula o endereçamento dos programas aos endereços físicos da memória principal;

Programas não ficam mais limitados ao tamanho da memória principal disponível;

Minimiza o problema de fragmentação.


Memória Virtual

Espaço de Endereçamento:

Mapeamento

Memória VirtualEspaço de

Endereçamento Virtual

Memória PrincipalEspaço de

Endereçamento Real

Memória Secundária

Est

rutu

ra V

etor

ial


Memória Virtual

Mapeamento: Realizado por hardware + S.O. nos sistemas atuais,

através da MMU (Memory Management Unit - Unidade de Gerenciamento de Memória).

Cada processo com uma tabela de mapeamento própria.

No momento da execução, o endereço virtual é mapeado para o endereço físico, pois o processador só acessa endereços do espaço real;

Nas trocas de contexto, um registrador é responsável por indicar qual a tabela que deve ser utilizada.


Memória Virtual

Paginação:

Tabela de Páginas de A

Espaço Virtual do Processo A


Endereçamento Real


Espaço Virtualdo Processo B

Tabela de Páginas de B

Mem

óri

a V

irtu

al

Page Fault

Page In


Memória Virtual

Localização e função da MMU(Memory Management Unit)


Memória Virtual

Memória Virtual por Paginação: Memória Virtual e Real divididas em blocos de

mesmo tamanho (páginas); Páginas virtuais; Páginas reais ou frames;

As tabelas de páginas mapeiam os blocos de informações:

Quanto maior o bloco, menor o tamanho das tabelas;

Quanto maior o bloco, maior o tempo de transferência do bloco entre memória principal e secundária.


Memória Virtual

Memória Virtual por Paginação: Endereço Virtual = Nº da página virtual +

deslocamento; Um bit de validade (na tabela de páginas) indica se

a página já se encontra na memória principal ou não.

Taxa de Paginação = Nº de Page Fault em um intervalo de tempo.

Quando ocorre um page fault, o processo em questão passa ao estado de espera.


01

Validade

--2

End. do Frame

Memória Virtual

Endereçamento Virtual:

Tabela de Páginas de A

Espaço Virtual do Processo A


Endereçamento Real

Mem

óri

a V

irtu

al

2...1

Página virtual

067...

203deslocamento

2 203

Endereço Físico


Page In

SO


Memória Virtual Paginação

A relação entre endereços virtuais e endereços físicos de memória dada pela tabela de páginas


Tabelas de Páginas

Operação interna de uma MMU com 16 páginas de 4KB


Tabelas de Páginas

Entrada típica de uma tabela de páginas


Tabelas de Páginas

Tabelas de páginas muito grandes podem ser inviáveis Se armazenadas na MMU ocupariam

muito espaço; Se mantidas em memória, degradariam

o acesso à memória. Uma das soluções é a utilização de

tabelas de páginas em níveis.


Tabelas de Páginas

Endereço de 32 bits com 2 campos para endereçamento de tabelas de páginas

Tabelas de páginas com 2 níveis

Tabelas de páginas podem existir com diversos níveis, mas não é comprovada a eficiência de tabelas com mais de três níveis.


Memória Associativa ou TLB

TLB (translation lookaside buffer) para acelerar a paginação


Algoritmos de Substituição de Páginas

A falta de página força uma escolha Qual página deve ser removida para que seja

possível a alocação de espaço para a página a ser trazida para a memória?

Se a página escolhida foi modificada, deve primeiro ser salva se não tiver sido modificada é apenas sobreposta

Melhor não escolher uma página que está sendo muito usada provavelmente ela precisará ser trazida de volta em

pouco tempo


O Algoritmo Ótimo

Substitui a página necessária o mais tarde possível ótimo mas não realizável

Estimada através do registro do uso das páginas em execuções anteriores


Algoritmo NURNão Usada Recentemente

Cada página tem os bits Referenciada (R) e Modificada (M) Bits são colocados em 1 quando a página é

referenciada e modificada As páginas são classificadas

Classe 0: não referenciada, não modificada Classe 1: não referenciada, modificada Classe 2: referenciada, não modificada Classe 3: referenciada, modificada

NUR remove página aleatoriamente da classe de ordem mais baixa que não estiver vazia


Algoritmo FIFO

Mantém uma lista encadeada de todas as páginas A página mais antiga é colocada no início da

lista A página que chegou por último é colocada no

final da lista Na ocorrência de page fault

A página no início da lista é removida A nova página é adicionada no final da lista

Desvantagem A página há mais tempo na memória pode

estar sendo utilizada com muita freqüência


Algoritmo de Substituição de Página Segunda Chance (SC)

Operação do algoritmo segunda chance Listas de páginas em ordem FIFO Exemplo: estado da lista em situação de page fault no

instante 20, com o bit de Referenciação da página A em 1 (números representam instantes de carregamento das páginas na memória)


Algoritmo Relógio


Menos Recentemente Usada (MRU)

Assume que páginas usadas recentemente logo serão usadas novamente Retira da memória as páginas que há mais tempo

não são utilizadas Uma lista encadeada de páginas deve ser mantida

A página mais recentemente usada no início da lista, a menos usada no final da lista

A atualização da lista deve ser feita a cada referência à memória

Alternativamente manter contador em cada entrada da tabela de página Escolhe página com contador de menor valor Zera o contador periodicamente


O Algoritmo de Substituição de Página do Conjunto de Trabalho

O algoritmo do conjunto de trabalho


O Algoritmo de Substituiçãode Página WSClock

Operação

do Algoritmo WSClock


Políticas de Substituição de Páginas:

Seleção de qual, entre as diversas páginas alocadas deve ser liberada.

Necessidade de verificação se a página foi alterada (bit de modificação)

No caso da página liberada tiver sofrido modificação, esta deverá antes ser gravada no Arquivo de Paginação (page out).

Note que as páginas de código não podem ser modificadas, logo não sofrem page out.


Políticas de Substituição de Páginas:

Política de Substituição Local: Apenas as páginas do processo que gerou o page

fault são candidatas à relocação. Política de Substituição Global:

Todas as páginas de todos os processos são candidatas à relocação.

Algumas páginas nunca são candidatas à relocação, como por exemplo as do núcleo do S.O.


Políticas de Busca de Páginas

Determinação de quando uma página deve ser carregada para a memória. Paginação por demanda:

Transferência de páginas para memória principal quando são referenciadas.

Apenas as páginas necessárias são transferidas. Paginação antecipada:

Além da página referenciada, são carregadas outras páginas que também podem (ou não) ser referenciadas futuramente.

Economia de tempo na cópia do conjunto de páginas.

Risco de trabalho desnecessário.


Políticas de Alocação de Páginas:

Determina quantos frames cada processo pode manter na memória principal. Alocação Fixa:

Número máximo de frames (páginas) por processo. Caso o limite seja atingido, alguma página deve ser

descartada. O limite de páginas é determinado na criação do

processo. Limite de páginas mal dimensionado:

Se for pequeno: Muitos page faults; Degradação do sistema;

Se for grande: Espaço ocupado maior que o necessário; Reduz o grau de multiprogramação.


Políticas de Alocação de Páginas:

Alocação Variável: O número máximo de frames de um processo

pode variar em função de sua taxa de paginação.

Processos com alta taxa de paginação podem aumentar o seu limite máximo de frames.

Processos com baixa taxa de paginação podem ter os seus limites máximos de frames reduzido.


Políticas de Alocação XPolíticas de Substituição

Relacionamento entre as Políticas de Alocação e Políticas de Substituição de páginas. Alocação Fixa:

Substituição Local. Alocação Variável:

Substituição Global. Substituição Local.

O SO avalia a taxa de paginação de um processo e altera o seu limite máximo de frames.


Considerações sobre Tamanho de Página

Tamanho de página pequeno Vantagens

Menos fragmentação interna Menos programa não usados na memória

Desvantagens Os programas precisam de mais páginas,

tabelas de página maiores...


Política de Limpeza

Processo que executa em background, um daemon de paginação Inspeciona periodicamente o estado da

memória Quando apenas algumas molduras de

página estão disponíveis Seleciona páginas a serem removidas usando

um algoritmo de substituição


Espaços Separados de Instruções e Dados

Espaço de endereçamento únicoX

Espaços separados de instruções (I) e dados (D)


Páginas Compartilhadas

Dois processos que compartilham o mesmo código de programa e, por conseqüência, a mesma tabela de páginas para instruções


Segmentação

Espaço de endereçamento unidimensional com tabelas crescentes

Uma tabela pode atingir outra


Segmentação

Permite que cada tabela cresça ou encolha, independentemente


Implementação de Segmentação Pura

(a)-(d) Desenvolvimento de fragmentação externa (e) Remoção da fragmentação via compactação


Segmentação

programa A

Procedimento X

Memória principal

Função Y

Array A

Programa Principal

Programa Segmento;Var A: array... C: ...

Procedimento X;...End;

Function Y;...End;

Begin...End.

Variável C

...

S.O.


Segmentação

A Segmentação possui funcionamento análogo à Paginação.

Mapeamento: Os segmentos são mapeados através da

tabela de mapeamento de segmento (TMS); O Endereço virtual é formado pelo:

Número do segmento; Deslocamento dentro do segmento;


Segmentação com Paginação

Técnica onde os processos são divididos logicamente em Segmentos e cada segmento é dividido fisicamente em Páginas.

Endereço virtual é formado por: Número do segmento; Número de página dentro do segmento; Deslocamento dentro da página.

Documents

2009 1 - sistemas operacionais - aula 8 - memoria