Sistemas Operacionais

Gerência de MemóriaIntrodução

Edson Morenoedson.moreno@pucrs.br

http://www.inf.pucrs.br/~emoreno

Slides baseados nas apresentações dos prof. Tiago Ferreto e Alexandra Aguiar

Conceitos básicos Memória principal

Central em sistemas de computador

CPU e sistema de I/O interagem com a memória

Conjunto de bytes ou palavras

Cada um com seu próprio endereço

CPU faz busca e armazenamento na memória

Cada programa deve ser carregado na memória para ser executado

Conceitos básicos Memória principal (cont.)

Uma palavra de memória

Conjunto de células que podem ser lidas ou escritas

Em geral é endereçada por byte

Possui dois registradores para as operações básicas:

Registrador de endereço de memória

Registrador intermediário (buffer)

Conceitos básicos

Memória principal (cont.)

Registrador de endereço de mémória

Contém o endereço de memória a realizar a operação

Endereço pode conter dado ou instrução

Registrador Intermediário (buffer)

Leitura: recebe a palavra da memória

Escrita: contém a informação a ser gravada na memória

Seletor

Seleciona o espaço da memória correspondente ao endereço

Registrador

de endereço

Memória

Sel

eto

r

0

1

2

3

4

N-2

N-1

…

Registrador

intermediário

Conceitos básicos

Requisitos de gerenciamento de memória

Relocação

Processo pode estar em qualquer posição da memória

Proteção

Processos tem de ter espaço reservado

Compartilhamento

Deve haver espaço comum entre processos

Organização lógica

Organização intemediária dada pela visão de hw e sw

Organização física

Organização a ser tomada para, por exemplo, transferência de

dados entre a memória secundária e a principal

Relocação

Quando o programa é carregado na memória o verdadeiro

(absoluto) endereço de memória é determinado

Um processo pode ocupar diferentes partições, ou seja,

diferentes locais absolutos da memória durante a execução

Conceitos básicos

Memória física:

Memória “real” do sistema implementada com CIs

Possui áreas reservadas (ex. vetor de interrupções)

Endereço físico:

Acessa posições da memória física

Memória lógica (virtual):

Memória que um processo pode acessar

Utiliza endereços lógicos

Necessita tradução dos endereços lógico para físicos

Espaço de endereçamento do processo

Conjunto de endereços que o processo pode acessar

Espaço de endereçamento

Unidade de gerenciamento de memória

MMU (Memory Management Unit)

Provê mecanismos básicos para gerência de memória

Proteção de acesso

Mapeamento de endereços lógicos em endereços físicos

Normalmente está junto ao processador

CPU sempre enxerga endereços lógicos

11

Conceitos básicos

MMU

Relocação

Requisitos: Proteção Funcionalidade

Evitar o acesso não desejado ou indevido de outros processos

Acesso pode alterar bytes armazenados no espaço do processo

Acesso pode ocorrer de forma acidental ou intencional

Processos não devem ser capazes de referenciar lugares damemória que pertencem a outro processo sem permissão

Impossível verificar endereços absolutos em tempo de compilação

Relocação torna imprevisível a localização do processo

Garante espaço limitado de endereçamento

Cada processo tem seu espaço de endereçamento

Verifica se endereço a ser acessado é válido

Recurso utilizado

Registradores de limite inferior e superior

Demarcam o início e o fim do espaço de endereçamento de um

processo

Funcionamento

se (endereço a ser acessado < registrador de limite inferior) então

gera interrupção - endereço ilegal

se (endereço a ser acessado > registrador de limite superior) então

gera interrupção - endereço ilegal

acessa memória[end]

Proteção de acesso

Recursos utilizados

Registradores base e limite

Todos programas são carregados com endereço inicial = 0

Funcionamento

se (endereço a ser acessado > registrador limite) então

gera interrupção - endereço ilegal

senão end = end + regbase

acessa memória[end]

Proteção de acesso

Requisitos: Compartilhamento

Funcionalidade

Permitir a vários processos que acessem uma mesma porção de

memória

Casos de emprego de compartilhamento

Processos que são cópias do mesmo programa

Acessam o mesmo trecho de código, sem replicações na memória

Permite reduzir a quantidade de memória alocada

Processos que cooperam

É importante que compartilhem uma mesma estrutura de dados

Compartilhamento deve ser provido sem descuidar da proteção

Requisitos: Organização lógica Caracteríticas do hardware

Memória é organizada linearmente (geralmente)

Sequencia de bytes/palavras

Característica do software

Programas são escritos em módulos Módulos podem ser escritos e compilados independentemente

A cada módulo pode-se aplicar diferentes níveis de proteção

Imutáveis: Apenas leitura, apenas execução

Mutáveis: Permite escrita

Emprego da organização permite

Escrita e compilação de módulos independentes

Diferentes graus de proteção

Compartilhamento de módulos entre processos

Requisitos: Organização física

Funcionalidade

Garantir o fluxo de processos entre as memórias principal e

secundária

Responsabilidade:

Não pode ser deixada ao programador

Memória disponível pode ser insuficiente para a carga de um processo

Solução por parte do programador partiria da exploração de overlaying

o Overlay: uso de um mesmo espaço de memória para diferentes

módulos e dados, carregados conforme necessário

Dinamicidade em ambientes de multiprogramação causa imprevisibilidade

Em tempo de compilação o programador não sabe

o Quanto espaço terá disponível em memória

o Onde terá espaço disponível na memória

Cenário

Existe um único processo em execução na memória

Permite o uso de toda a parte que resta da memória

Esquema mais simples possível

A memória é dividida

Sistema operacional

Processo do usuário

Monoprogramação

Formas de organizar a memória

Monoprogramação

Existem vários processos na memória

Coexistência de processos

Aptos à executar

Em execução

Multiprogramação

Particionamento da memória

Dá suporte à multiprogramação

Permite aumentar a utilização do processador

Para tirar vantagem da multiprogramação,

vários processos precisam estar na memória

Partições fixas

Memória dividida em partições de tamanhos fixos Tamanhos podem ser os mesmos ou não

Quando programa é carregado Entra em uma fila de processos para utilizar uma partição

livre

O número máximo de processos concorrentes é baseadono número de partições

Exemplo: Particionamento de uma máquina com 32 KBytes de memória 4KBytes: processos pequenos 6KBytes: processos médios 12KBytes: processos grandes 10KBytes: kernel

Partições fixas Problema:

Tamanho do processo a ser carregado e otamanho da partição não são

equivalentes

Consequência

Fragmentação interna:

Ocorre quando o tamanho da partição é maior que o tamanho do processo

Espaço que sobra dentro da partição quando processo é alocado na partição

Fragmentação externa:

Detectado quando existem partições livres que, se combinadas, poderiam ser

usadas por um processo que está aguardando

Proposta de solução para fragmentações

Emprego de partições de tamanhos distintos, mas fixos

Diminui ambos problemas

Mas não resolve completamente

Exemplo da figura

Processos de até 16M podem ser acomodados

Processos menores podem ser acomodados nas partições menores,

reduzindo a fragmentação interna

Partições fixas

Partições fixas

Algoritmo de alocação

Partições de tamanho equivalentes

Trivial: Havendo espaço disponível, aloca-se para o processo em carga

Partições de tamanho equivalentes

Pode associar cada processo com a menor partição na qual ele cabe

Processos devem ser alocados de tal maneira que minimizem o

desperdício de memória em cada partição

Pode-se empregar uma fila para cada tamanho de partição

Garante a redução/eliminação da ocorrência de fragmentação interna

Pode causar mal uso de partições

o Partições maiores não utilizadas poderiam ser alocadas para

processos menores

Pode-se empregar uma única fila para todas as partições

No caso de não existência de de espaço, swap pode ser requerido

Partições fixas

Vantagens Provêem esquema simples para gerenciamento

Requerem baixo desperdício de tempo de processamento do sistemaoperacional

Desvantagens O número de processos ativos é limitados pelo número de partiçoes

Partiçoes são definidas durante o tempo de geração do sistema

Processos muito pequenos não usam o espaço eficientemente

Em ambos os métodos (tamanhos iguais ou diferentes)

Técnica em “desuso” atualmente IBM OS/MFT empregava tal técnica

MFT: Multiprogramming with a fixed number of Tasks

Partições fixas

Partições variáveis/dinâmicas

Objetivo:

Superar dificuldades do uso de partições fixas

Partições de tamanhos e quantidade distintos

Tamanho das partições é ajustado dinamicamente

Processo carregado na memória ocupa o espaço referente ao seu tamanho

SO contém lista de espaços livres na memória física

Mapa de bits ou lista encadeada

Fragmentação Externa

Memória externa a todos os processos

é fragmentada

Pode ser resolvido com compactação

OS move os processos

Permite juntar áreas livres

Consome tempo e gasta tempo de CPU

OS (8M)

P1

(20M)

P2

(14M)

P3

(18M)

Empty

(56M)

Empty (4M)

P4(8M)

Empty (6M)

P2

(14M)

Empty (6M)

Partições variáveis

Partições variáveis

Alocação de partições

Sistema operacional deve decidir qual bloco livre será associado

a um processo

Algoritmos de alocação

Best-fit

First-fit

Next-fit

Worst-fit

Partições variáveis Best-fit Escolhe-se a partição onde o processo deixa o menor espaço sem utilização Escolhe o bloco cujo tamanho é o mais próximo do requisitado

Nesse algoritmo Desempenho ruim quando todos os blocos tem de ser avaliados

Objetivo é garantir a melhor escolha de partição livre

Otimização

A lista de áreas livres está ordenada por tamanho

Diminuindo o tempo de busca por uma área desocupada.

Desvantagem do algoritmo Escolha da partição mais aproximada resulta em pequenas partições livres

Tendência é ter grande quantidade de pequenas áreas livres não-contíguas

Aumentando o problema da fragmentação.

Solução pode ser o emprego de Compactação de memória Pode ser necessária mais frequentemente

Partições variáveis Worst-fit

Escolhe-se a partição onde o processo deixa o maior espaço sem utilização

Escolhe o maior espaço livre na memória

Nesse algoritmo

A lista de áreas livres deve estar ordenada por tamanho para otimizar busca

Comparado ao best-fit

Reduz (não elimina) o problema da fragmentação

Partições variáveis First-fit

Busca por espaço livre

Varre a memória do início

Escolhe o primeiro bloco disponível que seja grande o suficiente

Método tenta primeiro utilizar as áreas livres de endereços mais baixos

Boa chance de se obter uma grande partição livre nos endereços mais altos

Algoritmo mais rápido dos três (best / worst / first)

A lista de áreas livres está ordenada por endereços crescentemente

Consome menos recursos para a busca

Next-fit

Similar ao First-fit

Diferença está na busca, que ocorre a partir do endereço da última posição alocada

Exercícios

1) Considere um sistema cuja gerência de memória é feita através de

partições variáveis. Nesse momento, existem as seguintes

lacunas: 10k, 4k, 20k, 18k, 7k, 9k, 12k e 13k, nessa ordem.

Quais espaços serão ocupados pelas solicitações: 5k, 10k e 6k,

nessa ordem, se:

a) First-fit for utilizado?

b) Next-fit for utilizado?

c) Best-fit for utilizado?

d) Worst-fit for utilizado?

37

Resposta 1Lacunas: 10k, 4k, 20k, 18k, 7k, 9k, 12k e 13k

Solicitações: 5k, 10k e 6k

First-fit:

* 5k, 4k, 20k, 18k, 7k, 9k, 12k e 13k

* 5k, 4k, 10k, 18k, 7k, 9k, 12k e 13k

* 5k, 4k, 4k, 18k, 7k, 9k, 12k e 13k

Next-fit:

* 5k, 4k, 20k, 18k, 7k, 9k, 12k e 13k

* 5k, 4k, 10k, 18k, 7k, 9k, 12k e 13k

* 5k, 4k, 10k, 12k, 7k, 9k, 12k e 13k

Best-fit:

*10k, 4k, 20k, 18k, 2k, 9k, 12k e 13k

*(0k), 4k, 20k, 18k, 2k, 9k, 12k e 13k

*(0k), 4k, 20k, 18k, 2k, 3k, 12k e 13k

Worst-fit:

* 10k, 4k, 15k, 18k, 7k, 9k, 12k e 13k

* 10k, 4k, 15k, 8k, 7k, 9k, 12k e 13k

* 10k, 4k, 9k, 8k, 7k, 9k, 12k e 13k

Exercícios

2) Considere novamente um sistema cuja gerência de memória é

feita através de partições variáveis. Nesse momento, existem as

seguintes lacunas: 10k, 4k, 20k, 18k, 7k, 9k, 12k e 13k, nessa

ordem. Quais espaços serão ocupados pelas solicitações: 15k, 4k e

8k, nessa ordem, se:

a) First-fit for utilizado?

b) Next-fit for utilizado?

c) Best-fit for utilizado?

d) Worst-fit for utilizado?

Resposta 2Lacunas: 10k, 4k, 20k, 18k, 7k, 9k, 12k e 13k

Solicitações: 15k, 4k e 8k

First-fit:

* 10k, 4k, 5k, 18k, 7k, 9k, 12k e 13k

* 6k, 4k, 5k, 18k, 7k, 9k, 12k e 13k

* 6k, 4k, 5k, 10k, 7k, 9k, 12k e 13k

Next-fit:

* 10k, 4k, 5k, 18k, 7k, 9k, 12k e 13k

* 10k, 4k, 5k, 14k, 7k, 9k, 12k e 13k

* 10k, 4k, 5k, 14k, 7k, 1k, 12k e 13k

Best-fit:

* 10k, 4k, 20k, 3k, 7k, 9k, 12k e 13k

* 10k, 0k, 20k, 3k, 7k, 9k, 12k e 13k

* 10k, 0k, 20k, 3k, 7k, 1k, 12k e 13k

Worst-fit:

* 10k, 4k, 5k, 18k, 7k, 9k, 12k e 13k

* 10k, 4k, 5k, 14k, 7k, 9k, 12k e 13k

* 10k, 4k, 5k, 6k, 7k, 9k, 12k e 13k

Exercício• Um sistema utiliza alocação particionada dinâmica como

mecanismo de gerência de memória. O sistema operacional

aloca uma área de memória total de 50Kb e possui, inicialmente,

os processos da tabela a seguir:

• Realize as operações abaixo seqüencialmente, mostrando o estado

da memória após cada uma delas. Resolva a questão utilizando as

estratégias best-fit, worst-fit e first-fit.

a) alocar uma área para o programa D que possui 6 Kb;

b) liberar a área do programa A;

c) alocar uma área para o programa E que possui 4 Kb.

5 Kb Processo A

3 Kb Processo B

10 Kb Livre

6 Kb Processo C

26 Kb Livre

Buddy System

Alternativa aos particionamentos fixos e variáveis

Todo o espaço disponível é tratado como um único bloco 2U

Se requisição de tamanho s é tal que 2U-1 < s <= 2U

Todo o bloco é alocado

Senão, bloco é dividido em dois “buddies” iguais

Processo continua até que um menor bloco maior ou igual ao tamanho s

seja gerado

Exemplo

1 M

512 K

128 K

Processo A requesita 100 K

512 K

256 K 256 K

256 K

512 K

512 K128 KA

Exemplo

Árvore de representação do Buddy