Gerenciamento B ásico de Mem ória - hostel.ufabc.edu.brhostel.ufabc.edu.br/~marcelo.nascimento/BC1518/aulas/ufabc_SO_Aula8... · Roteiro Introdução Espaço de Endereçamento Lógico

Prof. Marcelo Z. do [email protected]

BC1518-Sistemas Operacionais

Gerenciamento BGerenciamento Báásico sico de Memde Memóóriaria

Aula 07Aula 07

RoteiroRoteiro� Introdução

� Espaço de Endereçamento Lógico vs. Físico

� Estratégias para escolha de uma partição

� Alocação contígua de Memória

� Swapping

� Paginação

� Segmentação

� Leituras sugeridas

� Exercícios29/03/09 2

IntroduIntroduççãoão

� Propósito geral de um sistema computacional éexecutar programas:

� Programa (código + dados) deve estar na

memória;

� Para garantir uso da CPU vários programas são colocados na memória (Multi-programação);

� Necessidade de uma política de gerenciamento da memória;

� Diferentes estratégias são aplicadas de acordo com requisitos, algoritmos e suporte de hardware.

29/03/09 3

IntroduIntroduççãoão� Memória:

Uma “longa matriz” de bytes => com seus

endereços:

Um processo quer ler dados deve especificar o endereço desejado.

� Instruções são buscadas na memória assim como os dados;

� O processador somente executa instruçõeslocalizadas na memória principal (não há acessodireto a disco).

� http://www.youtube.com/watch?v=mYbYGFWeG_Y29/03/09 4

IntroduIntroduççãoão

� Tendência atual do software� Lei de Parkinson: “Os programas se expandem para

preencher toda a memória disponível para eles”(adaptação);

� Gerenciador de memória: � Responsável por alocar e liberar espaços na memória

para os processos em execução;

� Responsável por gerenciar o chaveamento entre a memória principal e o disco rigído;

29/03/09 5

� Instruções pegam endereços de memória como argumento, mas não endereço de disco;

� Para garantir que cada processo tenha um espaço de memória separada:� O registrador de alocação contém o endereço base para

realizar a tradução;

Hardware BHardware Báásicosico

� Proteção ocorre quando o hardware da CPU compara os endereços gerados no modo usuário com os registradores;

� Qualquer tentativa de violar a região, uma trap éenviada para o monitor;

� O SO que carrega os registradores base e limite.

Hardware BHardware Báásicosico

8

EspaEspaçço de endereo de endereçço Logico e o Logico e FFíísicosico� Endereço Lógico

◦ Gerado pela CPU;◦ Também referenciado como endereço virtual;◦ Programas de usuário trabalham com endereço lógico, não vê o endereço físico real.

� Endereço Físico◦ Endereço que a unidade de memória trabalha.

9

EspaEspaçço de endereo de endereçço Logico e o Logico e FFíísicosico� Ambos são os mesmos se a criação dos endereços ocorrem em◦ Tempo de compilação ou◦ Tempo de carregamento

� Pode ser diferente se o endereço é criado em ◦ Tempo de execução◦ � necessidade de mapeamento de endereço lógico para físico

UnidadeUnidade de de GerenciamentoGerenciamento de de MemMemóóriaria (MMU)(MMU)

� Dispositivo que tem a função de mapear o endereço físico para um endereço virtual;

� Numa MMU, o valor no registrador realocado éadicionado em todos os endereços gerados por um usuário e enviado para memória;

� O programa de usuário trabalha com endereço lógico, ele nunca trabalha com endereço físico;

� Registrador base é chamado de registrador de realocação.

UnidadeUnidade de de GerenciamentoGerenciamento de de MemMemóóriaria (MMU)(MMU)

Carregamento dinâmicoCarregamento dinâmico

� Rotina não é carregada até ser chamada;

� Melhor utilização de espaço de memória, a rotina não utilizada nunca é carregada;

� Útil quando grande quantidade de código énecessário para tratar de casos que ocorrem com pouca frequência;

� Não exige suporte do sistema operacional, éresponsabilidade dos usuários.

Swapping (Troca de Swapping (Troca de processos)processos)� Técnica para resolver o problema da insuficiência

de memória:

� antes: O programa ficava na memória até o fim da sua execução, enquanto os outros esperavam por memória livre.

� swapping: O sistema retira temporariamente um programa da memória, coloca-o no disco (swapp out), para a entrada de outro.

29/03/09 13

� Exemplo: Algoritmo de alternância circular � Quando o quantum expirar, o gerenciador de memória

começará a descarregar o processo que acabou e carregará outro processo para o espaço da memória liberada.

29/03/09 14

Exemplo: Escalonamento porprioridade:

•Alta prioridade alocamémoria e baixa éeliminado dessa área

Swapping (Troca de Swapping (Troca de processos)processos)

� Pode ocorrer de duas maneiras:

� Com partições fixas:

� Cada vez que um processo é bloqueado, ele é retirado dando o lugar a outro;

� Não é interessante porque aspartições fixas tendem a desperdiçar espaços de memória;

� Com partições variáveis:

� Tamanho e número de partições variam com os processos;

� Otimiza a utilização da memória, mas é mais complicado na alocação e liberação da memória;

29/03/09 15

Swapping (Troca de Swapping (Troca de processos)processos)

AlocaAlocaçção de Memão de Memóóriaria

� Tipos básicos de gerenciamento:

� Alocação não contígua: com chaveamento (Multiprogramação):

� Processos são movidos entre a memória principal e o disco;

�artifício usado para resolver o problema da falta de memória;

�Se existe MEMÓRIA PRINCIPAL suficiente não há necessidade de se ter divisões;

� Contígua: não há chaveamento entre processos;29/03/09 16

Sem troca de Processos - Contíguo� Sem chaveamento entre processos: gerenciamento mais simples;

� Desvantagem: apenas um processo na memória;

29/03/09 17

USUÁRIO

0

0xFFF...

RAM

S.O.

S.O.ROM

USUÁRIO

DRIVERS

USUÁRIO

S.O.

ROM

RAM

(a) (b) (c)

RAM

Palmtop

MS-DOS

AlocaAlocaçção de Memão de Memóóriaria

AlocaAlocaçção de Memão de Memóória ria ––PartiPartiçções fixasões fixas� Múltiplos processos sendo executados;

� Eficiência da CPU;

� Dividir a memória em n partições;

� N processos na memória;

� Ocorria de modo manual => quando o sistema era inicializado;

29/03/09 18

AlocaAlocaçção de Memão de Memóória ria --PartiPartiçções fixasões fixas

29/03/09 19

Memória Principal

Sistema Operacional

2 Kb

5 Kb

8 Kb

Partição 1Partição

Tabela de partições

Tamanho

1 2 Kb

2 5 Kb

3 8 Kb

Partição 2

Partição 3Programas a serem executados:

AE

3 Kb

D

6 Kb

C

1 Kb

B

4 Kb 2 Kb


29/03/09 20

Partição 4

Partição 1

S.O.

Partição 2

Partição 3

0

800 k

700 k Partição 4

Partição 1

S.O.

Partição 2

Partição 3

0

Fila de entrada

Partição está cheia OS/360 (IBM)


� Tabela de Alocação de Partições: área livre e ocupada pelos processos.

29/03/09 21

Memória Principal

Sistema Operacional

1

2

3

Programa C

Área livre

Programa B

Partição Tamanho Livre

1 2 Kb Não

2 5 Kb Sim

3 8 Kb Não


� Vantagem:�Multiprogramação: Partições fixas.

� Desvantagens:�Utilização parcial das partições fixas�Concomitante criação de espaços ociosos:

� fragmentação interna – programa é carregado em uma partição um pouco maior que o necessário.

29/03/09 22


� Fragmentação Interna

29/03/09 23

Memória Principal

Sistema Operacional

1 Kb

3 Kb

5 Kb

Programa C

Programa A

Programa E

BD

6 Kb 4 Kb


� Pergunta: Descreva os benefícios e desvantagens de tamanhos de partições grandes e pequenos.

29/03/09 24

• Partições maiores permitem que programas grandes executem, mas resultam em fragmentação interna para programas pequenos.

• Partições pequenas reduzem a quantidade de fragmentação interna e aumenta o nível da multiprogramação, permitindo que mais programas residam na memória ao mesmo tempo, mas limita o tamanho do programa.

� O processo recebe apenas o volume de memória que requisita quando é carregado para processamento;

29/03/09 25

Memória PrincipalMemória Principal

Sistema OperacionalSistema Operacional

4 Kb

1 Kb

3 Kb

5 Kb

2 Kb

15 Kb

Programa C

Programa B

Programa A

Programa EBA

2 Kb

E

3 Kb

C

1 Kb 4 Kb

AlocaAlocaçção de Memão de Memóória ria --PPartiartiçções Dinâmicasões Dinâmicas

� Fragmentação Externa

29/03/09 26

Memória Principal

Sistema Operacional

4 Kb

3 Kb

5 Kb

Programa C

Programa A

D

6 Kb


� Solução para a Fragmentação Externa

29/03/09 27


Sistema OperacionalSistema Operacional

8 Kb

4 Kb

3 Kb

5 Kb5 Kb

Programa C

Programa APrograma A

Espaços livresadjacentes

são reunídos


� Solução para a Fragmentação Externa

29/03/09 28


Sistema Operacional

Relocação

Sistema Operacional

4 Kb

3 Kb

12 Kb

5 Kb

Programa C

Programa C

Programa A

Programa A

Realocaçãodinámica


EstratEstratéégias para escolha gias para escolha da partida partiççãoão

� Para evitar ou diminuir o problema da fragmentação;

� São propostos 3 técnicas na alocação dinâmica: � Best-fit:

�Escolhe a melhor segmento, ou seja, aquela em que o programa deixa o menor espaço sem utilização;

�A tendência é que a memória fique cada vez mais com pequenas áreas livres não contíguas

29/03/09 29

� Best-fit:

29/03/09 30

Memória Principal

Sistema Operacional

4 Kb

3 Kb

5 Kb

Programa C

Programa A

F

1 Kb

Sistema Operacional

2 Kb

Programa C

Programa F

Programa A

Área livre

(a) B

est-f

it


� Worst-fit:�Escolhe o pior segmento, ou seja, aquela em que o programa deixa o maior espaço sem utilização;

�Deixando espaços maiores, a tendência épermitir que um maior número de programas utilize a memória, diminuindo o problema da fragmentação.

29/03/09 31


� Worst-fit:

29/03/09 32

Memória Principal

Sistema Operacional

4 Kb

3 Kb

5 Kb

Programa C

Programa A

F

1 Kb

Sistema Operacional

4 Kb

Programa C

Programa A

Área livre

Programa F(b) Worst-fit


� First-fit:�escolhe o primeiro segmento livre que seja suficiente para carregar o programa.

�É a estratégia mais rápida entre elas.

29/03/09 33


29/03/09 34

Memória Principal

Sistema Operacional

4 Kb

3 Kb

5 Kb

Programa C

Programa A

F

1 Kb

Sistema Operacional

3 Kb

Programa C

Programa A

Área livre

Programa F

(c) First-fit


� Vinculação de endereços feita em execution timefaz com que endereços físicos e lógicos se diferenciem:� Esquema de tradução é necessário.

� O mapeamento de endereços em tempo de execução é feita pela MMU (Memory Management Unit);� Mapeamento permite escolher entre os métodos

diferentes de alocação de memória (Paginação, segmentação).

� O registrado base (base register) => chamado de relocation register.

29/03/09 35

ProteProteçção e Mapeamento ão e Mapeamento da Memda Memóóriaria

� O registrador de relocação contém o endereço base para realizar a tradução.

� É adicionado a todo endereço gerado por um processo de usuário no momento em que este éenviado à memória.


29/03/09 37

Endereço base


Gerenciamento de memGerenciamento de memóória ria com Mapa de Bitscom Mapa de Bits� O SO deve gerenciar a memória atribuída de

forma dinâmica;� Duas técnicas são empregadas:

� Gerenciamento de memória com listas encadeadas

� Técnica com Mapa de Bits:� Memória é dividida em unidades de alocação => kbytes;� Cada unidade corresponde a um bit no mapa:

0 - livre1 – ocupado

29/03/09 38

39

a) 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 livresb) Mapa de bits correspondentec) Mesmas informações em uma lista encadeada

Gerenciamento de memGerenciamento de memóória ria com Mapa de Bitscom Mapa de Bits

Gerenciamento de memória com listas encadeadas:

� Cada item da lista encadeada construída tem 2 estados (P - processo, H - livre):

� Endereço de início� Comprimento � Ponteiro para próximo item

� Quando termina um determinado processo => junta o espaço liberado com seus vizinhos.

29/03/09 40

Gerenciamento de memGerenciamento de memóória ria com Mapa de Bitscom Mapa de Bits

41

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

Gerenciamento de memGerenciamento de memóória ria com Lista Encadeadacom Lista Encadeada

42

PaginaPaginaçção: Alocaão: Alocaçção de ão de memmemóória não contria não contííguoguo

� Processo é alocado na memória onde há espaço disponível;

� Divide a memória física com tamanho de blocos fixos denominado quadros (definidos pelo hardware).◦ O tamanho da página é uma potência de 2, variando de 512 bytes até 16 MB

◦ O S.O. guarda todos os quadros livres

� Divide a memória lógica em blocos do mesmo tamanho chamado de página.◦ Para executar um programa com tamanho de n páginas, énecessário encontrar n páginas livre para carregá-lo.

◦ Configura uma tabela de páginas para traduzir o endereço lógico em endereço físico

43

EsquemaEsquema de de tradutraduççãoão de de EndereEndereççoo

� O endereço gerado pela CPU é dividido em :

◦ Número de Página (p) – usado como um indice dentro de uma tabela de páginas a qual contém o endereço base de cada página na memória física

◦ Página offset – deslocamento (d) – combinada com endereço base define o endereço de memória física que é enviado para unidade de memória

◦ Para um dado espaço de endereço lógico 2m e tamanho de página 2n

page number page offset

p d

m - n n

44


45


46

ExemploExemplo de de PPááginaginaççãoão

Tamanho da página = 4 bytesTamanho da memória = 8 páginas = 32 bytesEndereço lógico 0:página = 0/4 = 0, offset = 0%4 = 0mapeado � quadro 5 + offset 0 �endereço físico 20

Endereço lógico 13:

página = 13/4 = 3, offset = 13%4 = 1mapeado � quadro 2 + offset 1 �endereço físico 9

47

QuadrosQuadros LivresLivres

Before allocation After allocation

Todo o processo deve ter sua própria tabela de página

48

ImplementaImplementaççãoão dada tabelatabela de de ppááginasginas

� Tabela de página é guardada na memória principal◦ Registrador de base da tabela de páginas (PTBR) aponta para a tabela de página;

◦ Page-table length register – PRLR => indica o tamanho da tabela de página.

� Mas qual a desvantagem de guardar a tabela de páginas na memória?◦ Todo acesso a instruções requer dois acessos a memória: um para tabela de página e outro para as instruções.

49

ImplementaImplementaççãoão dada tabelatabela de de ppááginasginas� Solução:

� Usar uma cache especial, menor, de pesquisa rápidachamada Tranlation Look-aside Buffer (TLB)

� É uma memória associativa de alta velocidade

� Cada entrada da TLB consistem em duas partes◦ Uma chave e um valor

� Quando recebe um item, o item é comparado com todas as chaves.◦ Atualmente: Intel Pentium Core i7 - com 512 entradas

50

PaginaPaginaççãoão com TLBcom TLB

Falha

51

ProteProteççãoão

� Proteção de memória é realizada pela proteção dos bits associadas a cada quadro.

� Esses bits costumam ser mantidos na tabela de páginas ◦ Um bit pode definir uma página como sendo de leitura/escrita ou somente leitura

� Outro bit (valid-invalid) pode ser usado◦ “valid” indica onde a página esta no espaço do endereço do processo, isto é, uma página válida para acesso

◦ “invalid” indica que a página não está no espaço de endereço do processo

52

O bit Valid (v) or Invalid (i) O bit Valid (v) or Invalid (i) nana tabelatabela de de ppááginagina

53

EstruturaEstrutura de de tabelatabela de de ppááginagina

� A maioria dos sistemas computadorizados modernos admite um grande espaço de endereço;

� Nesse contexto, a própria tabela de página se torna excessivamente grande;

� Uma solução é usar um algoritmo de paginação com dois níveis, em que a própria tabela de página também é paginada:◦ Exemplo: máquina de 32 bits => 20 bits ficam para páginas e 12 para deslocamento

Número da página descolcamento

pi p2 d

54


55

• O SO cria a tabela de página externa e a página databela de página.


56

EstruturaEstrutura de de tabelatabela de de ppááginagina• Em um espaço de endereçamento lógico de 64 bits, o esquema de endereço em 2 níveis não é maisadequado

• Usa-se um esquema de 3 níveis.

57

TabelaTabela de de ppááginagina invertidainvertida

� Uma entrada para cada quadro da memória física;� A entrada consiste no endereço virtual da páginaarmazenado nesse local da memória física com informações sobre o precesso que possui essapágina.

GerenciamentoGerenciamento de de MemMemóóriariaSegmentaSegmentaççãoão� Esquema de gerenciamento de memória que suportavisão do usuário da memória.

� Diferente da paginação?

◦ Difere fundamentalmente da paginação, onde o programa é dividido em páginas de iguaistamanhos que muitas vezes contêm instruções de mais de um módulo de programa.

06/04/09 58

Segmentação:

� Aproveita a modularidade do programa: a memórianão é dividida em tamanhos fixos e sim conforme a estruturação do programa.

� Isso permite que os programas sejam divididoslogicamente em sub-rotinas e estruturas de dados e colocados em blocos de informações na memória.

06/04/09 59

GerenciamentoGerenciamento de de MemMemóóriariaSegmentaSegmentaççãoão

Compilador cria segmentos:� As variáveis globais;

� Chamadas de procedimento que armazenaparâmetros e endereços de retorno;

� A porção do código para cada procedimento oufunção;

� As variáveis locais do procedimento ou função;

06/04/09 60


1

2

4

1

4

2

3

Espaço do usuário Espaço de memória física


06/04/09 62

Pilha

Árvorede Parse

Livre

Constantes

FonteTabela

de Símbolos

Tarefa: Compilação

Espaço de EndereçamentoVirtual

Tabelade

SímbolosFonte

Constantes0k

20k

0k0k0k

12k

02k

Pilha

12k

Segmentos (0-3)


63

ArquiteturaArquitetura de de SegmentaSegmentaççãoão

� Tabela de segmento – mapeia o endereço físico; cada tabela é composta por:◦ base – contém o endereço físico inicial onde o segmento reside na memória

◦ limite – especifica o tamanho do segmento

� Segment-table base register (STBR) aponta para a localização da tabela de segmento na memória

� Segment-table length register (STLR) indica o número de segmento usado por um programa;

número do segmento s é legal se s < STLR

� Segmentação – Proteção:

◦ Cada segmento representa uma porção semântica do programa – segmentos que são instruções, enquanto outros são dados.

◦ Os segmentos de instruções podem ser definidos como somente de leitura ou de execução;

◦ O hardware de mapeamento verifica o bit de proteção associado com cada entrada na tabela de segmentos para evitar acesso ilegal.

06/04/09 64

GerenciamentoGerenciamento de de MemMemóóriariaVirtual Virtual -- SegmentaSegmentaççãoão

65


66


� Segmentação:

◦ Problemas encontrados => embora haja espaço namemória, não há espaço contínuo:� Política de re-alocação: um ou mais blocos são realocadospara abrir espaço contínuo (pode criar fragmentaçãoexterna);

◦ Necessidade:� Política de compactação: para que todos os espaçossejam compactados;

� Política (bloquear): fila de espera;� Política de troca: substituição de segmentos;

06/04/09 67


◦ Técnica de gerenciamento onde o endereçamentológico é divido em segmentos e, por sua vez, cadasegmento é dividido fisicamente em páginas.

◦ O endereço virtual é formado pelo nº do segmento(NSV), um nº da página (NPV) dentro dessesegmento e um deslocamento dentro da página.

� O nº do segmento aponta para uma entrada na tabela de segmentos, que por sua vez aponta para uma tabela de páginas.

06/04/09 68

GerenciamentoGerenciamento de de MemMemóóriariaVirtual Virtual –– SegmentaSegmentaççãoão com com PaginaPaginaççãoão

◦ Para programador: sua aplicação continua sendomapeada por segmentos de tamanhos diferentes, emfunção das subrotinas e estruturas definidas no programa.

◦ O sistema trata cada segmento com um conjunto de páginas de mesmo tamanho, mapeadas por uma tabelade páginas associada ao segmento.

◦ Um segmento não precisa estar contíguo na memóriaprincipal, eliminando o programa de fragmentaçãoexterna.� Exemplo: Arquitetura Pentium segue esse modelo

06/04/09 69

GerenciamentoGerenciamento de de MemMemóóriariaVirtual Virtual –– SegmentaSegmentaççãoão com com PaginaPaginaççãoão

70

ExemploExemplo: Intel Pentium: Intel Pentium� Suporta:

◦ Segmentação e segmentação com paginação

� A CPU gera o endereço lógico:◦ Que são dados à unidade de segmentação;

� A unidade produz um endereço linear para cada endereço lógico.

� O enderço linear é dado à unidade de paginação, que por sua vez gera o endereço físico na memória;◦ Essas unidades foram o equivalente a unidade de gerência MMU.

71

� Tamanho máximo do segmento: 4 GB

�Número máximo de segmentos por processo é 16 KB.�8 K privados �mantidas na tabela de descritor local

�8 K compartilhado �mantidados na tabela de descritor global

SegmentaSegmentaççãoão: Intel : Intel PentiumPentium

72

� Tamanho da página :� 4 KB � paginação em 2

níveis ou� 4 MB � páginação em

um nível;�Os 10 bits mais alta

ordem referencia o diretório de página

p1

p2

d

PaginaPaginaççãoão: Intel Pentium: Intel Pentium

Linux com Paginação em 3 Níveis

No Pentium, tamanho do diretório do meio = 0

74

SumSumááriorio� CPU gera endereço lógico

� Alocação de memória contíguo

� Primeiro, Melhor ou Pior Ajuste

� Paginação: alocação não contíguo de memória

� Segmentação: tamanho variável de acordo com a

visao de usuário

� Segmentação e Paginação no Pentium

Leituras Sugeridas

� Silberschatz, A., Galvin, P. B. Gagne, G. Sistemas Operacionais com Java. 7º edição. Editora Campus, 2008 .

� TANENBAUM, A. Sistemas Operacionais Modernos. Rio de Janeiro: Pearson, 3 ed. 2010

Acesse o link abaixo:

http://hostel.ufabc.edu.br/~marcelo.nascimento/

Obrigado!!!

Nota de Aula

ExercExercíícioscios1 - Suponha um sistema de 128 Kb de memória principal e que utilize

um sistema operacional de 64 Kb que implemente alocação particionada estática realocável. Considere também que o sistema foi implementado em três partições: P1(8Kb), P2(24Kb) e P3(32Kb). Calcule a fragmentação interna da memória principal após a carga de três programas: PA, PB e PC.A)P1->PA(6 Kb); P2->PB(20Kb); P3->PC(28Kb);B) P1->PA(4 Kb); P2->PB(16 Kb); P3->PC(26Kb);C)P1->PA(8 Kb); P2->PB(24Kb); P3->PC(32Kb);

2 – Considere o exercício anterior, seria possível executar quatro programas concorrentemente utilizando apenas a técnica de alocação de particionamento estática realocável? Se for possível, como? Considerando ainda o mesmo exercício, seria possível executar um programa de 36 Kb? Se for possível, como?

3 – O que é fragmentação interna e fragmentação externa? Qual o tipo de fragmentação apresentado no método de gerenciamento de partições fixas?

29/03/09 77

Documents

Gerenciamento B ásico de Mem ória - hostel.ufabc.edu.brhostel.ufabc.edu.br/~marcelo.nascimento/BC1518/aulas/ufabc_SO_Aula8... · Roteiro Introdução Espaço de Endereçamento Lógico