1

Gerenciamento de Memória Capítulo 4

2

Roteiro: •  Introdução e Motivação para Memória Virtual

(VM) •  Overlays: Gerenciamento na Idade da Pedra •  Paginação por demanda (Demand Paging) •  Espaço de Endereçamento Virtual •  Área de Swap •  Políticas de Reposição de Páginas •  Aspectos de Implementação

Introdução •  Importante função de um S.O. é gerenciar o recurso

memória principal principal (mem. física, RAM, core) •  Acesso à memória RAM é rápido, poucos ciclos de CPU

(p.ex. DDR4-SDRAM leva 5 nanosegundos em uma CPU de 3.7 GHz = 18.5 ciclos)

•  Memória principal: um recurso relativamente caro e limitado (1GB p/ PC aprox. R$ 45)

•  Tamanho dos programas aumentou muito (Chrome 200MB, Slack: 300 MB): melhor GUI, mais funções e menos otmizações L

•  Um S.O. usa memória secundária (disco) para armazenar dados que “não cabem” na memória principal

•  Acesso a essa memória secundária é ordens de grandeza mais lenta (1-15 milisegundos, ou 106 mais lento que acesso a RAM) 3

Introdução •  Papel do Subsistema Gerenciador de Memória (GM) é

de mover dados entre a memória principal e a secundária de forma transparente

•  Como se o sistema dispusesse de muito mais memória do que apenas a RAM

4

Introdução •  O Ger.Memória interage com uma componente de

hardware: Memory Management Unit (MMU) •  A MMU é responsável por buscar e armazenar dados na

memória principal, na posição certa •  A MMU traduz endereços lógicos (do programa

executável) para endereços físicos (da memória RAM)

5

Duas MMUs

6

Duas MMUs competem pelo acesso á memória principal.

Ausência de qualquer GM •  Mono-programação: Um único programa na

memória principal, carregado com endereço inicial conhecido;

•  Sem qualquer tradução de endereços; os endereços do executável são endereços físicos da memória RAM;

•  Linking é muito mais simples, pois referências a outros módulos podem ser calculadas estaticamente

•  Assim era nos primeiros computadores (anos 50-60), PCs (anos 70) e atualmente em sistemas embarcados, de tempo real, micro-controladores.

7

Existem processadores sem MMU? •  Praticamente todos de 8 ou 16 bits

–  PIC18 (8 bits Microchip) –  CC430 (16 bits RISC, Texas Instruments) –  XAP4 (16 bits, Cambridge Consultants)

•  Vários de 32 bits: –  Cortex-M0 (32 bits ARM) –  Cortex-M3 (32 bits ARM)

Usados em sistemas embarcados: Equipamentos médicos e hospitalares, Controle Industrial, Sistema Interconectado no Carro, Eletrônicos, Equipamentos de Segurança.

8

Em praticamente todo equipamento inteligente que executa um único programa de controle.

Monoprogramação

9

Principais Problemas: •  Tamanho de programas fica limitado ao tamanho da RAM •  Só é possível executar um único processo por vez. Se

este faz E/S, a CPU irá esperar ociosa. Toda concorência somente usando threads.

•  Portanto, para computadores de propósito geral (incluindo smartphones e tablets), multi-programação é essencial!!

ende

reço

s

a) o processo na mem. alta b) o núcleo na mem. alta c) núcleo e drivers nas extremidades da memória

Requisitos de um GM 1.  Executar programas que sejam maiores do que o tamanho da

RAM 2.  Permitir que mais de um programa execute ao mesmo tempo

(concorrentemente) 3.  Permitir que programas parcialmente carregados possam

inciar a execução (isso reduz o tempo de início do programa) 4.  Permitir programas re-alocáveis, que possam executar em

qualquer parte da memória RAM e possam ser movidos de um lugar para outro

5.  Permitir que processos possam solicitar mais memória ao longo de suas execuções.

6.  Livrar o programador da tarefa de alocar e desalocar recursos de memória (exceto, demandas específicas: malloc)

7.  Permitir o compartilhamento de código e dados entre processos 10

Memória Virtual Todos esses requisitos são atendidos pelo conceito de memória virtual. •  Dá a ilusão ao programa de que dispõe de muito mais

memória do que a memória RAM disponível •  Introduz o conceito de Espaço de Endereçamento

(Address Space), que difere do espaço ocupado na RAM

•  O programa executando na CPU gera referências a uma memória virtual (Espaço de Endereçamento), e esses endereços logicos são então traduzidos para endereços físicos.

•  Essa tradução é feita pela MMU - várias vezes para cada instrução de máquina

•  GM e núcleo precisam interagir com a MMU para garantir que a tradução seja feita corretamente. 11

Exemplo: Instruções com Endereçamento Indireto

12

Memória Virtual Tudo que é bom tem seu preço… •  Tabelas de tradução (de end-lógicoè end-físico)

precisam ser mantidas pelo GM e o núcleo; isso consome memória do sistema

•  O custo de tempo da tradução é somado ao tempo de acesso à memória,

•  Especialmente, se a parte acessada não está na memória RAM, pois envolverá leitura do disco!

•  Atividades do GM consomem aprox 10% do tempo de um sistema normal. Em casos extremos pode chegar até 70-90% 13

Memória Virtual

14

Fonte: Fabián Bustamante

Gerenciamento de Memória na idade da pedra

15

Overlays •  Versões iniciais do UNIX executavam em um

PDP-11 (16 bits, memória para os processos: 128 KB)

•  Software overlay: reuso de partes de memória quando não são mais necessárias. Exemplo: código de incialização do sistema podeia ser sobre-escrito, ou tabelas em diferentes fases da compilação

•  O programador tinha que decompor seu código em segmentos e indicar quais segmentos podiam sobre-escrever outros

•  Isso resolve o problema de espaços de evdereçamento > RAM

16

Overlays

17

•  Segmento root fica sempre residente na RAM.

•  O tamanho da Overlay Region deve ser o tamanho do maior overlay.

•  Assim que é feita uma referência a um novo overlay este é copiado para a memória.

•  Se houvesse chamadas entre os overlays, execução ficaria extremamente lenta

Overlays

Overlays – Exemplo Compilador

18 80K

Swapping •  Processos eram carregados em espaços contíguos de RAM •  Apenas um pequeno número de processos “cabia” na memória

principal para serem executados concorrentemente •  Sempre que um processo fosse suspenso ou fazia uma E/S de

longa duração, era copiado para uma área de swap (uma partição do disco sem Sistema de Arquivos)

•  Área de swap para cada processo é alocada no momento da criação do processo (para garantir que tem espaço)

19

20

Swapping: Exemplo

Fig.: Sequência de alocação de memória usando swapping para 4 processos.

Carregamento de processos de tamanhos diferentes e em diferentes

regiões de memória pode causar: –  fragmentação de memória: acúmulo de pequenas regiões de

memória não utilizada –  Realocação para “de-fragmentacão de memória” é processo custoso

21

Gerenciamento de espaços disponíveis

Fig: Ocupação da memória com 5 processos e 3 lacunas usando Bit Map e Lista encadeada

Idéia: dividir a memória em unidades de alocação de n bytes (1 KB no Minix) e representar a ocupação de (livre/ocupado) de lotes de unidades usando um bit map ou então uma lista encadeada

Bit Map: armazenamento compacto e simples, mas busca por determinado tamanho de lote livre pode envolver análise de várias palavras (no bit map)

Lista ligada : cada nó contém o endereço inicial e o tamanho de uma partição ocupada ou livre

Gerenciamento de Memória Virtual

Introduzido pelo UNIX 3BSD em 1980 para um VAX de 32 bits (= espaço de endereçamento de 4GB). A partir daí, todas as versões do UNIX tiveram GM baseado em Demand Paging Ideia principal: •  Espaço de endereçamento dos procesos e memória RAM são

logicamente divididos em páginas de mesmo tamanho (2X bytes) •  Endereços virtuais (lógicos) do processo são decompostos pela MMU

em um número de página (indice de página) e um offset •  Cada página só é carregada para um quadro de página (page frame)

da RAM quando ela é acessada •  Permite que processos executem mesmo se estão apenas

parcialmente na RAM •  Quando não está na RAM, a página tem uma cópia na área de Swap

22

Politicas de Carregamento de páginas •  Paginação por demanda (Demand paging)

–  Somente quando é feita uma referência para um endereço na página

–  Pode acontecer várias vezes para uma instrução (p.ex. endereçamento indireto de 1 ou 2 operandos)

–  Instrução é re-executada quando todas as páginas necessárias estão na RAM

•  Pré-paginação: –  Carrega na RAM várias páginas consecutivas do

espaço de endereçamento (em setores vizinhos na partição de swap)

–  As páginas adicionais podem não ser necessárias (referenciadas no futuro próximo)

23

Memória Virtual

24

Espaço de Endereçamento do Processo E suas páginas

Memória física com Quadro de páginas (page frames)

Partição de Paginação (ou swapping) Paginas

O Espaço de Endereçamento Virtual

É composto dos seguintes “segmentos”: –  Text (Execute-only) –  Dados Inicializados (p.ex. strings, const) –  Dados não inicializados (variáveis globais) –  Pilha (controlada pelo runtime) –  Heap (alocado com malloc) –  Shared libraries (Execute-only) –  Shared memory

•  Text, shared libraries e shared memory são compartilhados por processos

•  Na prática, cada segmento têm sua tabela de tabela de páginas.

25

Paginação Por Demanda

26

Page-fault

Swap area

Page Fault: passo-a-passo Sempre que o endereço acessado “cai” em uma página que não está na RAM: Etapas: 1.  Trap para o núcleo do S.O. (salva o contexto) 2.  Escolhe algum quadro de página para ser substituido

(sobre-escrito) 3.  Possivelmente precisa copiar conteúdo do frame para

partição de swap/paginação 4.  Requisita uma leitura de disco para ler a página requisitada

(E/S bastante demorado) -> aloca CPU para outro processo 5.  Chega a interrpção do disco (E/S da paginação finalizada) 6.  Atualiza a tabela de páginas do processo 7.  Coloca o processo na fila de prontos 8.  Eventualmente aloca CPU para o proceso (carrega o

contexto da CPU) 27

29

Controle de acesso Além do número do quadro, cada entrada da Tabela de πáginas contém bits para o tipo de acesso permitido:

Exemplo: R: somente-leitura W: leitura-e-escrita X: somente-execução • se tipo do acesso viola o permitido, a MMU gera a interrupção “violação de acesso de memória” • a validade de uma operação sob um endereço lógico pode ser testada em paralelo com a tradução para o endereço físico correspondente

.

30

Entrada da Tabela de Páginas

Resumo dos campos/flags: •  Caching: se faz sentido guardar essa entrada da TP no cache •  Referenced: se houve acesso a algum endereço da página nos

últimos ∆t •  Modified: se houve acesso de escrita a algum endereço da página

nos últimos ∆t •  Protection: Controle de acesso (como visto antes) •  Present: se página está na memória RAM •  Número do quadro na memória física (page frame number)

31

Tabela de Páginas Possíveis implementações da Tabela de Páginas (TP): 1) TP em registradores da CPU dedicados, que são carregados através de

instruções privilegiadas (ex. DEC PDP-11)‏ Vantagem: não necessita de MMU e tradução é veloz Desvantagem: número de entradas é pequeno (tipicamente 16-256)‏

2) TP é mantida em memória principal (do núcleo)

- mantém-se um registrador com o endereço inicial da tabela é PTBR + #página_virtual Vantagem:

•  possibilita tabelas de páginas arbitrariamente grandes •  a troca de contexto envolve somente PTBR

Desvantagem: •  tempo de acesso à memória duplica, devido ao acesso inicial à tabela

de páginas

32

Tabela de Páginas Possíveis implementações (cont.): 3) utilização de um Translation Look-aside Buffer (TLB)

- TLB = vetor associativo que permite comparação paralela com suas entradas (de 8 - 128 entradas) - é usado como um cache das entradas da TabPaginas recentemente acessadas (è princípio de localidade)‏ - quando uma página lógica não possui uma entrada no TLB (TLB miss): * acesssa-se a TabPaginas e coloca-se a entrada no TLB * se a página está em memória, operacão é completada; senão gera-se uma interrpção Page-fault Obs: cada troca de contexto, o TLB precisa ser zerado Vantagem: tradução rápida Desvantagem: requer gerenciamento do conteúdo do TLB (substituição de entradas)

33

Translation Look-aside Buffer (TLB)

A razão de (TLB hits/acessos à memória) determina a eficiência da tradução e é usada para calcular o tempo médio de acesso à memória

Razão de TLB hits depende do tamanho do TLB e da estratégia de troca de entradas

•  Pagina é comparada com todas as entradas do TLB ao mesmo tempo

•  Se entrda encontrada (TLB hit) e não é necesseario acessar TP

•  Se não, (TLB miss), TP precisa ser consultada.

35

Tabela de Páginas de 2 níveis Resolve o problema de manter

grandes tabelas de página na memória (para todos os processos).

Ideia: A própria tab. de páginas é paginada (guarda apenas as partes da TabPagina cujo mapeamento esteja sendo usado).

Dois níveis: tabela raiz (de 1o. nível) e TabelaPagina de 2o. nível

A tabela raiz contém os ponteiros para essas partes da TabPaginas .

Offset = 12 bits Tam. página= 4K 32 bits page number è 220 entries!

Tab.Paginas raiz Tab.Paginas 2o. nivel

43

Algoritmos de Substituição de Páginas A cada page-fault: •  o gerenciador de memória aloca um quadro de páginas

para a página requisitada e •  precisa escolher qual página (de um quadro de

páginas) deve ser removida da memória. O algoritmo de substituição de páginas determina qual

página deve ser descartada e para isso usa as informações estatísticas contidas nas tabelas de páginas.

Nessa seleção deve levar em conta que: –  uma página modificada precisa ser copiada para disco,mas

uma não-modificada pode ser sobreescrita –  não é boa idéia tirar uma página que “está em uso”, pois ela

terá que ser carregada em breve

44

Algoritmo de substituição ideal •  Substitui a página que não será mais acessada,

ou então acessada no futuro mais distante –  Infelizmente, não é viável na prática, pois exigiria um

conhecimento sobre todos os acessos futuros

•  Usado apenas em simulações para avaliar o quanto os algoritmos concretos diferem do algoritmo ideal

Seq. de referência (indices de página)

45

Algoritmo Página não recentemente Utilizada (Not Recently Used - NRU)

•  Cada página tem um bit de Referência (R) e de Modificação (M): –  Bits são setados sempre que página é acessada ou modificada –  Pagina é carregada com permissão somente para leitura e M=0. –  No primeiro acesso para escrita, o mecanismo proteção notifica o

núcleo, que seta M=1, e troca para permissão de escrita –  A cada interrupção do relógio, seta-se R = 0

•  Páginas são classificadas em 4 categorias 1)  Não referenciada, não modificada 2)  Não referenciada, modificada 3)  referenciada, não modificada 4)  referenciada, modificada

•  NRU escolhe primeiro qualquer página (em ordem descencente de categoria)

Razão da prioridade de categoria #2 sobre #3: É melhor manter páginas sendo referenciadas, do que modificadas mas pouco referenciadas.

46

Algoritmo FIFO de substituição

•  Manter uma lista ligada de todas as páginas na ordem em que foram carregadas na memória

•  A página (mais antiga), no início da fila, é a primeira ser descartada

•  Principal Vantagem:

–  Simplicidade de implementação. •  Principal Desvantagem:

–  Não leva em conta se uma página está sendo frequentemente acessada ou não.

–  Por exemplo: a página mais antiga )a ser descartada) pode estar sendo acessada com alta frequência.

47

Algoritmo da Segunda Chance •  É uma variante do algoritmo FIFO que leva em conta

acessos recentes às páginas: •  Funcionamento:

–  Páginas são mantidas em lista circular FIFO (ordenada por momento de carregamento)

–  Inspciona-se a página no começo da lista: –  Se página mais antiga possui bit R=0, ela é removida. –  Se tiver bit R=1, o bit é zerado, e a página é colocada no final da

fila,. Ou seja: dá se uma 2a chance.

R=1

R=0

A página é tratada como se fosse carregada recentemente.

Página carregada mais recentemente.

Página carregada há mais tempo.

48

Algoritmo do Relógio

Todas as páginas carregadas estão em uma lista circular. Dois ponteiros giram em sentido horário •  O Primeiro ponteiro zera o bit de referência ( R) e o de modificacão

(M) •  Segundo ponteiro verifica um pouco depois se esses bits estão

setados. •  Obs: foi o algoitmo usado originalmente na MV do UNIX

50

Algoritmo “Menos recentemente utilizada” Least Recently Used (LRU)

Assume que páginas usadas recentemente, deverão ser usadas em breve novamente.

Princípio básico: descartar a página que ficou sem acesso durante o maior periodo de tempo.

Exemplo: em memória física de 3 frames A Implementação ideal, porém impraticável:

–  Manter a lista de páginas, onde as páginas no final da lista são as mais recentes

–  É inviável pois demandaria uma manipulação da lista a cada acesso de memória!!

51

Algoritmo “Menos recentemente utilizada” Least Recently Used (LRU)

•  Alternativa (necessita de apoio de hardware): –  usar um contador que é incrementado por hardware a cada acesso à

memória –  Cada vez que uma página é acessada, atualiza este contador na

entrada da TP correspondente –  Na hora da substituição, escolhe a página (ou moldura de página)

que está com o menor contador

52

LRU com Hardware especial Manipular uma matriz n x n (para n entradas na TP) com o registro de

acessos recentes (linha i = contador da página i) Idéia: Ao acessar página i preencha toda linha i com bit 1 e, em seguida,

toda coluna i com bit 0. A página mais antiga é aquela com menor valor.

Acesso Pág. 0

Acesso Pág. 1

Acesso Pág. 2 Acesso Pág. 3 Acesso Pág. 2 Acesso Pág. 1

Acesso Pág. 0 Acesso Pág. 3 Acesso Pág. 3 Acesso Pág. 2

53

Algoritmo do envelhecimento (Aging): Simulando LRU em Software

Manter um contador para cada página; •  Vetor de bits, onde bit I registra se página Pi foi acessada durante

último período de tempo (cada tick de relógio): •  faz-se um shift de um bit para a direita no contador de cada página e

adiciona-se o R-bit como bit mais significativo no contador •  Desvantagem: o vetor precisa ter tantos bits quanto houver de page

frames

Vetor de bits atualizado periodicamente

Cada page frame tem um contador

54

Principais limitações do Algoritmo do Envelhecimento (comparado ao LRU)

•  Quando duas páginas possuem o mesmo valor de contador (de idade), não há como saber qual delas foi acessada por último (no último período de tempo)

•  Os contadores de idade têm um número finito de bits. Portanto quando o valor atinge 0, não há como distinguir se a última referência ocorreu há apenas n ticks do relógio ou há muito mais tempo.

èNormalmente, basta contador com 8 bits e períodos de 20 ms entre ticks. Se uma página não foi acessada a 160 ms, provavelmente não é mais relavente.

t Pag.X Pag.Y

período

55

Least Frequently Used (LFU) Mantém-se uma estatística sobre a frequência de acesso a

cada página, e escolhe-se a página com menor frequência.

Desvantagem: requer um contador de acessos para cada página e as operações de divisão e de comparação da média poder ser onerosos

56

Ultra-paginação (“Thrashing”) Fenômeno que ocorre quando o gerenciador de memória

fica sobrecarregado com transferência de páginas entre memória RAM e disco (swap).

Alta taxa de faltas de página: ocorre quando um processo possui muito menos páginas na memória do que o seu conjunto de páginas em uso.

# de páginas na memória

taxa de falta de páginas (page fault)

2 3 4 5 6 7 8 9 10 11

57

O Conjunto de páginas em uso

•  O conjunto de uso (working set) é o conjunto das páginas acessadas pelas k referências mais recentes. O sistema de paginação deve gerenciar este conjunto usando envelhecimento.

•  Quando um processo é escolhido para execução seu working-set pode ser pré-paginado (em vez de fazer paginação por demanda)‏

A maioria dos processsos apresenta uma localidade de referência (a cada momento, acessa apenas uma fração pequena de suas páginas).

Tamanho do “working set” no instante t

t

# páginas

58

O Working Set •  Working set W(t, Δ) é o conjunto de páginas

referenciadas no intervalo (t - Δ, t) •  O tamanho do working set muda dependendo do grau de

localidade dos acessos a memória •  Nos períodos de maior dispersão dos acessos, há

acessos a mais páginas, e o working set fica maior.

•  O Working set é uma aproximação do que o processo irá

acessar no futuro próximo, e indica quais páginas devem permanecer na RAM.

59

Algoritmo de substituição baseado no working set Mantém-se um contador virtual de tempo e periodicamente, atualiza-

se o contador em cada página que tenha o bit R=1.Working Set consiste das páginas com contador dentro da janela de tempo [t- τ, t]

Se R=0, não é feita autalização. Se (R==0 && age ≤ τ ) avança com tempo virtual e depois verifica novamente. Descarta-se páginas com R=0 e mais antigas do que τ.