Gerência de Memória Principal ARQUITETURAS DE COMPUTADORES II César A. Marcon, César De Rose e Fernando Moraes

Gerência de Memória Principal

ARQUITETURAS DE COMPUTADORES II

César A. Marcon, César De Rose e Fernando Moraes

2 / 55

Índice

1. Introdução

3. Endereçamento Contíguo

4. Endereçamento Não-contíguo

2. Histórico da Gerência de Memória

3 / 55

Introdução à Gerência da Memória Principal

• Sistema monoprogramado memória principal dividida em duas partes– Uma para SO

– Outra para programa em execução

• Sistema multiprogramado memória de programa é dividida entre vários processos

• SO divide memória dinamicamente Gerência de memória• Gerência de memória eficiente é vital para sistemas multiprogramados

– Motivo• Se poucos processos estiverem na memória processador ficará parado

esperando por operações de E/S

– Solução• Técnica de gerência aumenta número de processos na memória,

aumentando utilização do processador

4 / 55

Gerência da Memória Principal (hierarquia)

• Memória principal (MP) é mais um nível da hierarquia de memória– Princípio da gerência igual a outros níveis de memória

• Dados mais usados são trazidos para MP para diminuir tempo médio de acesso ao nível mais baixo, neste caso o disco

5 / 55

Índice

1. Introdução




6 / 55

Histórico e Técnicas de Gerência de Memória Principal

• Memórias RAM eram empregada como área temporária para acelerar o acesso aos dados

• Recurso caro na época• Tamanho reduzido (poucos Kbytes)

– Muitos programas não cabiam na memória junto com seu ambiente de execução (interpretador, bibliotecas, etc.)

• Gerência de MP não utiliza mesmas técnicas que gerência de caches por 2 motivos– Evolução Histórica

• Idéia de memória como área de armazenamento temporário de dados é anterior ao conceito de cache

– Diferentes Características• Tamanho e tempo de acesso da MP são muito maiores que das

caches• Ao contrário das caches parte da gerência pode ser feita em SW• Unidades de gerência possuem a identificação do processo dono (pode

ser utilizado na estratégia de gerência)

7 / 55

Gerência de Memória em Sistemas Monoprogramados

• Objetivo– Permitir que programas maiores que a memória pudessem executar

• Primeiras estratégias baseadas em overlays (sobreposição)– Responsabilidade total do programador

– Programador dividia programa em partes que podiam executar autonomamente na memória (overlay)

• No final dessas partes era colocado código responsável pela carga da próxima parte que iria sobrepor– Endereços antigos não são mais necessários

• Programador tinha controle total da memória– Responsável pela troca das partes

• Programa escrito de forma a evitar quebras em muitas partes– A troca tinha um alto custo

8 / 55

Gerência de Memória em Sistemas Multiprogramados

• Multiprogramação trouxe dificuldades– Gerência de overlays deve possibilitar vários programas

executando concorrentemente mesmo que estes somados não coubessem na memória

– Gerência de overlays de cada programa não podia interferir na dos outros programas

• Necessário que agente externo seja responsável pela gerência

• Responsabilidade de gerenciar memória passou do usuário para monitor residente, mas tarde chamado de SO

9 / 55

1. O que você entende por gerência de memória principal? Existe(m) alguma(s) diferença(s) quando comparado com a gerência de memória cache? Qua(l/is)?

2. Para que servia a gerência de memória em máquinas monoprogramadas? Descreva como eram os primeiros modelos de gerenciamento de memória.

3. Quem normalmente é responsável pela gerência de memória nas máquinas atuais?

4. Explique a técnica de overlay. Para que era utilizada a mesma? Qual problema da mesma?

5. Supondo que o custo de memórias não fosse considerado, o que seria melhor, ter uma hierarquia com milhares de níveis ou um pequeno conjunto de níveis? Qual o problema de ter vários níveis? Qual o problema de não ter níveis?

6. Porque a gerência de memória principal pode ser feita em SW, enquanto que a gerência de memórias cache deve ser feita em HW?

Exercícios

10 / 55

Índice

1. Introdução


3 / 4. Endereçamento da Memória Principal

11 / 55

Endereçamento a Memória Principal

• Problema– Como endereços de um programa são usados para acessar posições da

MP?

• Solução– Modos de endereçamento

• Endereçamento Contíguo– Programa é carregado inteiro em uma única área de memória contígua

• Endereçamento Não-Contíguo– Quebra programa em pedaços carregados em áreas distintas de memória

– Vantagens• Não há necessidade de respeitar qualquer ordem• Melhora aproveitamento da memória menor fragmentação externa pelo

aproveitamento de lacunas

– Desvantagens• Gerência de memória fica mais trabalhosa

12 / 55

Índice

1. Introdução




13 / 55

Endereçamento Contíguo

• Existem duas formas de endereçamento para gerência de memória em áreas contíguas– Direto– Relativo

• Endereçamento Direto– Endereços do programa são usados diretamente no acesso à

memória principal– Endereços são definidos durante a compilação/ligação ou carga

• Endereçamento Relativo– Endereços do programa são relativos, devendo ser definidos em

tempo de execução– Endereços são definidos na hora do acesso

14 / 55

Índice

1. Introdução




3.1. Endereçamento Direto

3.2. Endereçamento Relativo

15 / 55

Endereçamento Contíguo Direto

• Endereço aponta para posição na memória que está definida e não pode ser alterada

16 / 55

Endereçamento Contíguo Direto (multiprogramação)

• Na multiprogramação este endereçamento pode gerar conflitos no acesso à memória Posição do programa na memória definida sem conhecimento do que estava alocado

• Programas só podem ser carregados na memória se seus espaços de endereçamento são disjuntos

17 / 55 Endereçamento Contíguo Direto (multiprogramação - geração do endereço na carga)

• Espaço de endereçamento de um programa inicia sempre em 0 e pode ser facilmente relocados na carga pelo carregador

• Problemas– A conversão dos endereços pode atrasar consideravelmente a operação de carga– O programa não pode ser mudado de lugar durante a sua execução impede

compactação e swap

18 / 55

Índice

1. Introdução




3.1. Endereçamento Direto

3.2. Endereçamento Relativo

19 / 55

Endereçamento Contíguo Relativo

• Alternativa mais flexível endereço montado somente no acesso– Espaço de endereçamento lógico inicia em 0– Processador possui reg. de endereçamento base contém base do endereço físico

dos programas– Endereço real é montado com a base somada ao endereço relativo do programa em

cada acesso à memória

• Programa pode ser trocado de lugar na memória em tempo de execução

20 / 55

Índice

1. Introdução




21 / 55

Endereçamento Não-Contíguo

• Programa é dividido em pedaços carregados em áreas distintas de memória

• Conversão dinâmica de endereços– Ao acessar a memória, endereços lógicos são convertidos em

físicos– Implementada em HW (mais rápido). Exemplo: MMU (Memory

Manager Unit)

• Três formas de endereçamento– Paginação

• Unidade de gerência de memória física quebrada em frames com tamanho fixo

– Segmentação• Unidade de gerência de memória física quebrada em segmentos com tamanho

variável

– Segmento-paginação• Combinação dos endereçamentos acima

22 / 55

• Problema diretamente relacionado com gerência de MP• Fragmentação resulta em desperdício de memória• Tipos de fragmentação

– Fragmentação Interna• Quando ocorre

– Quando usada unidade de gerência de tamanho fixo (Ex: página)

• Como ocorre– Requisição não exatamente divisível pela unidade é arredondada para

cima resulta unidade alocada mas não completamente ocupada

– Fragmentação Externa • Quando ocorre

– Quando usada unidade de gerência de tamanho variável (Ex: segmento)

• Como ocorre– Seqüência de alocações e liberações

– Conseqüência• Requisição de usuário pode ser negada apesar de existir memória livre

Fragmentação de Memória

23 / 55

Fragmentação interna Fragmentação externa

Fragmentação de Memória

Página 1 Programa 1

Programa 2

Programa 1

Programa 3

Programa 2

Fragmento

Fragmento

Página 2

Página 3

Página 4

Página 5

Página 6

Segmento 1 (Programa 1)

( Segmento 2 (Programa 2)

Segmento 3 (P1)

Segmento 4 (Programa 3)

Fragmento

Fragmento

Fragmento

24 / 55

Índice

1. Introdução




4.2. Endereçamento Segmentado

4.1. Endereçamento Paginado

4.3. Endereçamento Segmento-Paginado

4.4. Otimização do Endereçamento Não-contíguo

25 / 55

Endereçamento Não-Contíguo Paginado

• Frames com tamanho fixo (2k, 4k, ou 8k)

• Endereçamento lógico do programa quebrado em páginas do mesmo tamanho dos frames

• Quando processo é executado todas suas páginas são carregadas para frames livres da memória (qualquer página em qualquer frame livre)

26 / 55 Endereçamento Não-Contíguo Paginado(conversão de endereços)

• Bits usados para d determinam tamanho dos frames

• Bits usados para p determinam número máximo de páginas de um processo

• Bits de f determinam total de frames da MP– f é obtido com a divisão da MP pela página– Exemplo: MP de 4 Gbyte (232) com páginas de 1 Kbyte (210 p=10 bits) resulta em

22 bits para f (222 4 Mframes na MP)


• Unidade de gerência de tamanho fixo gera fragmentação interna

• Tabela de páginas converte páginas em frames (1 tabela por processo)

• Tabela de páginas pode ser armazenada em– Registradores rápido mas limita tamanho da tabela

– Memória principal (área do sistema) lento, são necessários dois acessos (1 tabela + 1 dado) pode ter tamanho ilimitado

– TLB (Translation Lookaside Buffer) área de memória associativa usada como cache para as conversões mais efetuadas

• Situa-se entre processador e cache

• Tamanho da página– Pequena menor fragmentação interna, tabela de páginas fica maior

– Grande maior fragmentação interna, tabela de páginas fica menor

• Tabela de Frames (Frame Table)– Controle dos frames livres (para alocação e substituição de páginas)


• Tabela de frames para todo sistema– Tamanho fixo número de frames da MP é conhecido tamanho da memória /

tamanho da página– Procura por first-“found” (qualquer lacuna serve para qualquer página)– Possui campos adicionais para controle da política de troca de páginas (LRU, LFU)

• Quando processos terminam suas páginas na tabela de frames são marcadas como livres

• É possível compartilhar frames entre vários processos (leitura)– Fácil de implementar com várias tabelas de página apontando para mesmo frame– Controle adicional Verificar quando frame compartilhado pode ser desalocado

• Vantagens/Desvantagens

29 / 55

Índice

1. Introdução








30 / 55

Endereçamento Não-Contíguo Segmentado

• Não divide memória física Pode alocar unidade em qualquer posição

• Unidade de gerência com tamanho variável denominada segmento

• Segmento definido pelo usuário ou compilador– Endereços de um mesmo segmento estão relacionados– Gerência de memória mais preocupada com a visão do usuário– Exemplo de segmentos: dados, código, pilha

• Quando processo é executado, todos seus segmentos são carregados para memória (em qualquer posição livre)

31 / 55 Endereçamento Não-Contíguo Segmentado (conversão de endereços)

• Número de bits de d determina tamanho máximo dos segmentos

• Número de bits de s determina número máximo de segmentos de um processo

• Deslocamento do endereço lógico é comparado com tamanho do segmento (tabela de segmentos) Evita invasões de segmentos vizinhos

– Este teste não era necessário no endereçamento paginado pela limitação do número de bits

32 / 55

• Unidade de gerência variável Gera fragmentação externa– Compactação da memória necessária devido alta fragmentação externa

• É possível compartilhar segmentos entre vários processos (leitura)– Fácil implementar com várias tabelas de segmento apontando para mesma

área de memória

• Tabela de Segmentos aponta base do segmento na MP e verifica se deslocamento está dentro do limite do segmento

• Tabela de segmentos pode ser armazenada igual a paginação– Registradores, MP, TLB

• Tabela de Alocação controla quais lacunas estão livres• Uma tabela de alocação para todo o sistema de tamanho variável

– Número de áreas da MP é inicialmente 1 (toda a memória)

– Ao longo da gerência pode variar com a inclusão de áreas ocupadas

– Liberação de segmentos pode resultar na junção de vários segmentos e na diminuição do número de entradas da tabela

Endereçamento Não-Contíguo Segmentado (conversão de endereços)

33 / 55 Endereçamento Não-Contíguo Segmentado (Vantagens e Desvantagens)

34 / 55

Endereçamento do 8086 (16 bits)

• 20 bits para endereçamento 1 MB limitará o DOS

• Não implementa memória cache ou virtual, tão pouco mecanismos de proteção

• Endereço– lógico

• 16 bits para o segmento (code, data, stack, extra)

• 16 bits para o offset

– físico• 20 bits (1MB)

• Segmentos de até 64 KB

• 4 segmentos ativos por vez endereça até 256 KB por vez

• Segmentos contínuos, sobrepostos (parcial ou totalmente) e disjuntos

• Composição do endereço

– segmento deslocado para direita 4x + offset• Exemplo: LÓGICO FÍSICO

segmento 456A 456A0offset 1620 + 1620

46CC0

35 / 55

Endereçamento do 80286 (16 bits)

• Função de gerenciamento de memória (MMU) integrado no chip• Processador multi-usuário / multi-tarefa• Gerenciamento de memória

– Segmentos• Não precisam estar necessariamente na MP• Em caso de page-fault gera uma interrupção

• Limite estabelecido na criação do segmento (segurança)• Descritor do segmento (8 bytes) Tamanho e privilégio• Tabela global

– Informações do SO Compartilhada por todas as tarefas

• Tabela local– Informações relativas às tarefas

36 / 55

Endereçamento do 80286 (modos de endereçamento)

“Seletor” “Offset”

16 bits 16 bits

descritor

16

13

1

2

TI

RPL

índice

TABELA(global ou

local)

16

24

24

ENDEREÇOFÍSICO

ENDEREÇO LÓGICO

• Endereço físico– 224 16 MB

• Endereço lógico– 230 1 GB por tarefa

• Modo real– Igual ao 8086 20 bits

• Modo protegido– TI: table indicator (global ou local)

– RPL: request privilege level (SO)

– Espaço de endereçamento de tarefas• Uma tabela: 213 * 216 = 2 29

– 213 tamanho da tabela– 216 tamanho do segmento

• Assim– Global + Local = 229 + 229 = 230

1GB por tarefa

37 / 55 Endereçamento Não-Contíguo Segmentado(386 a Pentium)

• Modo protegido– Flat: 1 só segmento de 4GB

• Modo Virtual 8086– Emula o 8086 / permite rodar aplicações 8086 utilizando mais de 1MB

Seletor “Offset”

operando

32

32

ENDEREÇOFÍSICO

4GB(max)

16

1432acessos

limiteend. ini.

TABELA

De 8 até 64k

38 / 55

Índice

1. Introdução








39 / 55

Endereçamento Não-Contíguo Segmento-Paginado

• Combinação entre segmentação e paginação– Do mapeamento segmentado aproveita visão lógica de memória próxima do usuário– Do mapeamento paginado aproveita a gerência de memória mais simples

• Usuário aloca segmentos e estes são mapeados em grupo de páginas

• Memória física quebrada em frames de tamanho fixo, como na paginação. Porém existe informação das páginas que compõem cada segmento

• Unidade de gerência de tamanho fixo gera fragmentação interna

• Tabela de Segmentos usada para obter base da tabela de páginas do segmento desejado (uma por processo)

• Tabela de páginas usada para converter páginas de cada segmento em frames (uma tabela por segmento de cada processo)

• Tabela de Frames usada para controle dos frames livres– Uma tabela de frames para todo sistema– Tamanho fixo Número de frames da MP é conhecido (tamanho da memória /

tamanho da página)– Procura por first-“found” (qualquer lacuna serve para qualquer página)

• Quando processos morrem suas páginas na tabela de frames são marcadas como livres

40 / 55 Endereçamento Não-Contíguo Segmento-Paginado (conversão de endereços)

• Seqüência de acesso1. Número do segmento fornece na tabela de segmentos a base da tabela de páginas

deste segmento

2. Número da página e base da tabela de páginas fornece frame correspondente

3. Número do frame e deslocamento dentro dele fornece acesso à memória

41 / 55 Endereçamento Não-Contíguo Segmento-Paginado (Vantagens e Desvantagens)

42 / 55

• First fit– Pega o primeiro segmento livre que tem tamanho suficiente para a requisição de

memória– Rápido, mas gera muita segmentação– Tende a deixar a memória com diversos buracos de tamanho médio

Endereçamento Não-Contíguo Segmento-Paginado (Algoritmos para Alocação de Segmento na Memória)

43 / 55

• Next fit– Pega o próximo livre a partir do último– Requer um ponteiro que armazena a última posição alocada– É uma variação do first fit, que utiliza melhor toda a memória


44 / 55

• Best fit – Pesquisa a lista de memória inteira, procurando o segmento livre que mais se aproxima

do tamanho desejado– Para a pesquisa se encontra um segmento que atende exatamente ao tamanho

desejado– Normalmente deixa a memória com vários grandes buracos e pequenos buracos


45 / 55

• Worst fit– Pesquisa o maior segmento livre– O algoritmo privilegia a existência de segmentos grandes


46 / 55

• Buddy– Divide a memória em segmentos pares– Tipicamente implementado com algoritmos para árvore binárias Linux– Minimiza em muito a fragmentação externa, mas aumenta a fragmentação interna– Número máximo de compactações igual a log2(u) – log2(l)

Onde• u: é o tamanho máximo do segmento• l: é o tamanho do menor segmento


47 / 55

Índice

1. Introdução








48 / 55

Otimização do Endereçamento Não-Contíguo (TLB)

• Problema– Tabelas de páginas e de segmento ficam tão grandes que precisam ser

armazenadas na memória– Cada acesso à MP necessita no mínimo outro acesso para obtenção das tabelas

Reduz consideravelmente velocidade de acesso à MP

• Solução– TLB (Translation Lookaside Buffer) Memória associativa que acelera a conversão

• TLB funciona como cache guardando conversões mais usada

• Procura é feita em paralelo em todas posições

• Características– Tamanho da linha 4-8 bytes (pode conter segmento, página e frame)– Número de linhas 24-1024

• Exemplo: TLB de um Pentium III possui 32 linhas– Hit-time 1 ciclo, Miss-Penalty 10-30 ciclos– Hit-ratio aproximadamente 99%– Como pode ser tão alto?

• Devido a localidade dos acessos!!!

49 / 55

Exemplo de Utilização (Segmento-Paginado )

• TLB é consultada em paralelo ao acesso das tabelas. Se hit retorna frame desejado

• Se miss a consulta as tabelas é feita normalmente e o frame obtido é colocado na TLB no lugar da conversão menos recentemente utilizada (LRU)

50 / 55

Layout do Processador Pentium

Aproximadamente 40% do chip dedicado à cache

51 / 55

1. Quais são os dois grandes conjuntos de endereçamento da memória principal? Caracterize cada um deles.

2. Quem é responsável pela escolha do endereçamento da memória principal em uma determinada arquitetura? Justifique a possibilidade ou não da tarefa ser a responsável. Faça o mesmo para o SO e para o processador.

3. Explique porque o endereçamento direto para a multiprogramação pode não funcionar se a decisão dos endereços for feita durante a compilação/ligação. Qual a conseqüência de tomar a decisão durante a carga?

4. O que difere o endereço contíguo direto e realocação na carga com o endereçamento contíguo relativo?

5. Qual é a principal característica da gerência de memória não contígua? Como ela é realizada (qual mecanismo)? Quais são as técnicas?

6. Diferencie os métodos de paginação e de segmentação, mostrando as vantagens e desvantagens de cada um. Mostre como fica a fragmentação de memória em cada método

7. Em um sistema paginado, qual seria o tamanho da área para armazenar a tabela de tradução de endereços se utilizássemos: (a) RAM, (b) Memória associativa. Considere a seguinte estrutura de endereçamento:a) Endereço virtual: 4 GBytes;b) Endereço físico: 8 MBytes;c) Número de páginas: 2e10.

Exercícios

52 / 55

8. Faça um diagrama explicando o modo de tradução de endereços segmento-paginados. Qual o problema deste método? Qual a solução?

9. O que você entende por fragmentação de memória? Qual a classificação usual de fragmentação de memória? Explique e compare cada uma delas. Faça um desenho ilustrativo de como seria cada fragmentação

10. Compare a técnica de gerência de memória paginada com a gerência segmentada em relação à fragmentação gerada, alocação de unidades e substituição de unidades?

11. Faça um diagrama explicando o modo de tradução de endereços segmento-paginados. Qual o problema deste método? Qual a solução?

12. Onde podem ficar as tabelas de páginas e frames? O que pode ser feito para aumentar o desempenho? Compare as vantagens e desvantagens de cada opção

13. Desenhe como fica a conversão de endereços na gerência de memória segmento-paginada e descreva os passos de uma conversão

14. Faça uma tabela com o número de tabelas de páginas, tabelas de segmentos, tabelas de frames e tabelas de gerência de memória para as três técnicas de gerência de memória vistas em aula.

Exercícios

53 / 55

15. O que são TLBs? Para que servem?16. Faça um fluxograma (use a imaginação!) correspondente ao acesso a um

endereço lógico, mostrando o que ocorrem em caso de:a) TLB miss / TLB hitb) Cache miss / Cache hitc) Page fault / Page hit

17. Faça um desenho de como se encaixam as várias hierarquias de memória, considerando cache L1 e L2, memória principal e disco, para um modo de endereçamento segmento-paginado com TLB

18. De pesos de 1 (maior) a 5 (menor) para:

Exercícios

TLB Cache L2 Registradores Memória Principal Disco

Capacidade

Velocidade

Custo

54 / 55

19. (POSCOMP 2008 - 53) Analise as seguintes afirmativasI. O gerenciamento de operações de entrada e saída permite o

compartilhamento de periféricos entre múltiplos processos.

II. O gerenciamento de memória depende do hardware, mais especificamente da MMU (Memory Management Unit) para definir se partições, paginação ou segmentação podem ser usadas.

III. Os sistemas operacionais de tempo compartilhado não necessitam de interrupções para sua implementação.

IV. O algoritmo FIFO (First In, First Out) de escalonamento de processos é inerentemente preemptivo.

A análise permite concluir quea) Apenas as afirmativas I e II são verdadeiras.

b) Apenas as afirmativas I, II e III são verdadeiras.

c) Apenas as afirmativas I, II e IV são verdadeiras.

d) Apenas as afirmativas II e IV são verdadeiras.

e) Nenhuma das afirmativas é verdadeira.

Exercícios

55 / 55

19. (POSCOMP 2008 - 53) Analise as seguintes afirmativasI. O gerenciamento de operações de entrada e saída permite o

compartilhamento de periféricos entre múltiplos processos.

II. O gerenciamento de memória depende do hardware, mais especificamente da MMU (Memory Management Unit) para definir se partições, paginação ou segmentação podem ser usadas.

III. Os sistemas operacionais de tempo compartilhado não necessitam de interrupções para sua implementação.

IV. O algoritmo FIFO (First In, First Out) de escalonamento de processos é inerentemente preemptivo.

A análise permite concluir quea) Apenas as afirmativas I e II são verdadeiras.

b) Apenas as afirmativas I, II e III são verdadeiras.

c) Apenas as afirmativas I, II e IV são verdadeiras.

d) Apenas as afirmativas II e IV são verdadeiras.

e) Nenhuma das afirmativas é verdadeira.

Resposta de Exercícios

Documents

Gerência de Memória Principal ARQUITETURAS DE COMPUTADORES II César A. Marcon, César De Rose e Fernando Moraes