Gestão de Memória

1. Conceitos Básicos2. Swapping3. Memória Virtual4. Algoritmos de substituição de páginas5. Modelação de algoritmos de substituição de páginas6. Questões no desenho de sistemas de paginação7. Questões na implementação8. Segmentação

12/16/2002 Sistemas Operativos 2001/2002 2

Organização de um Sistema Operativo

System Call Handler

File System 1 ... File System m

Virtual memory

Driver 1 Driver 2 ... Driver n

Threads, thread scheduling, thread synchronization

Interrupt handling, context switching, MMU

Hide the low-level hardware

12/16/2002 Sistemas Operativos 2001/2002 3

GestãoGestão de de MemóriaMemória

Idealmente, programadores querem memória– Rápida– Grande– Não volátil

Hierarquia de tipos de memória– Cache - Pequena porção de memória rápida e cara – Memória principal - Média velocidade, médio preço – Armazenamento em disco – gigabytes de memória lenta e barata

Gestor de memória gere a hierarquia de memórias.

Objectivos do capítulo: investigar as diferentes tipos de gestão de memóriaObjectivos do capítulo: investigar as diferentes tipos de gestão de memória

12/16/2002 Sistemas Operativos 2001/2002 4

Gestão de MemóriaMonoprogramação sem swapping nem paging

0xFF..0xFF..

Três modos simples de organizar memória - um sistema operativo com um processo de um utilizador

Mainframes; Minicomputers

Mainframes; Minicomputers

Palmtops; embeddedsystems

Palmtops; embeddedsystems

Modelo inicial dos PC’scom MSDOS (BIOS)

Modelo inicial dos PC’scom MSDOS (BIOS)

SO na RAM

Programa de

utilizador

SO na ROM

Programa de

utilizadorSO na RAM

0xFF..Drivers em ROM

Programa de

utilizador

0 0 0

12/16/2002 Sistemas Operativos 2001/2002 5

Gestão de MemóriaMultiprogramação com partições fixas

800 K 800 K

Partições fixas de memória– Filas de entrada separadas para

cada partição– Uma única fila de entrada

Sistema Operativo

Partição 1

Partição 2

Partição 3

Partição 4800 K700 K

400 K

100 K

200 K

Sistema Operativo

Partição 1

Partição 2

Partição 4

Partição 3

800 K700 K

400 K

200 K

100 K

Desvantagem:– Pode ser posto numa queue pequena

demais– Uma queue pode estar cheia, com

partições livres

12/16/2002 Sistemas Operativos 2001/2002 6

Gestão de MemóriaProblemas que se colocam : Re-alocação e Protecção

Não pode ter a certeza onde é que o programa vai ser carregado em memória (Re-alocação)– O endereço de memória das variáveis e rotinas de código não pode

ser absoluto– Tem que se menter o programa fora da partição de outros processos

Usar os valores base e limite (Proteccção)– Endereços são mapeados, usando um valor base, por forma a

mapear endereços físicos– Endereços superiores ao limite físico estão errados– Sempre que o processo é escolhido para correr, base e limite

também são carregados

12/16/2002 Sistemas Operativos 2001/2002 7

SwappingSwappingTempo

Batch Systems:

-batch é carregado em memória

-Fica em memória até terminar

-Precisa de espaço em memória para suportar processo e manter CPU ocupado.

Batch Systems:

-batch é carregado em memória

-Fica em memória até terminar

-Precisa de espaço em memória para suportar processo e manter CPU ocupado.

Sistemas interactivos:

- usam time sharing

- processos em excesso têm de ser gravados em disco

Sistemas interactivos:

- usam time sharing

- processos em excesso têm de ser gravados em disco

Sistema Operativo

A

Sistema Operativo

Sistema Operativo

Sistema Operativo

Sistema Operativo

Sistema Operativo

Sistema Operativo

B

A A

B

C

B

C C

B

D D

C C

A

D

12/16/2002 Sistemas Operativos 2001/2002 8

Swapping

Alocação de memória muda com a entrada e saída de processos de memória

Duas estratégias– Swapping – programa todo em memória. Carregado de

disco para memória

– Virtual Memory – Só parte do programa é carregado para memória

12/16/2002 Sistemas Operativos 2001/2002 9

SwappingExemplo com segmentos

Alocação de espaço para segmentos que podem crescerAlocação de espaço para segmentos de stack e data

Sistema Operativo

Espaço livre

Espaço livre

Sistema Operativo

A

B

B stack

B data

B code

Espaço livre

Em uso

A stack

A data

A code

Espaço livre

Em uso

12/16/2002 Sistemas Operativos 2001/2002 10

SwappingGestão de memória com bit Maps

Exemplo de parte de memória com 5 processos e 3 espaços livre.Exemplos de gestão com bit Maps e com Listas.

12/16/2002 Sistemas Operativos 2001/2002 11

SwappingGestão de memória com listas ligadas

Antes de X terminar Depois de X terminar(a) torna-seA X B A B

(b) torna-seA X A

Listas ligadas: ligação dupla ou simples?Algoritmos de busca: First-Fit, Next-Fit, Best-Fit,Worst-Fit,Quick-Fit

(c) torna-seX B B

(d) torna-seX

12/16/2002 Sistemas Operativos 2001/2002 12

Memória VirtualMemória Virtual

Memória física é limitadaProgramas necessitam de mais memóriaSolução a nível da aplicação: divisão do programa em blocos distintosProgramador tinha de retirar e carregar em memória os blocos (o SO não intervinha)

Como simular a existência de mais memória do que a que existe realmente?

12/16/2002 Sistemas Operativos 2001/2002 13

Memória VirtualPaginação

CPU envia endereço virtual para MMU

Posição e função da MMU

Memória Control. Discos

CPU

MemoryManagement

Unit Barramento

12/16/2002 Sistemas Operativos 2001/2002 14

Memória VirtualPaginação

A relação entre endereços virtuais e endereços físicos( Page Table )

12/16/2002 Sistemas Operativos 2001/2002 15

Memória VirtualTabela de Páginas Simples

Operações Internas da MMU com 16 páginas de 4KB

12/16/2002 Sistemas Operativos 2001/2002 16

Memória VirtualTabelas de Páginas de vários níveis

Endereços a 32 bits

Page Tables de dois níveis

12/16/2002 Sistemas Operativos 2001/2002 17

Memória VirtualEstrutura de uma Page Table

Cache inibido Modificado Presente/Não Presente

Page frame number

Referênciado Protegido

Page table entry

12/16/2002 Sistemas Operativos 2001/2002 18

Memória VirtualTLBs – Translation Lookaside Buffers

Acelera o paging75RW1861114RW1860145R X021150R X019162RW1129129RW1130138R X020131RW11401

Page frameProtectionModifiedVirtual pageValid

12/16/2002 Sistemas Operativos 2001/2002 19

Memória VirtualPage Tables Invertidas

– Comparação de uma page table tradicional com uma page tableinvertida

12/16/2002 Sistemas Operativos 2001/2002 20

Algoritmos de substituição de páginasAlgoritmos de substituição de páginas

Falhas de páginas (page fault) força a uma escolha– Que página deve ser removida– Arranja espaço para uma nova página

Páginas modificadas devem ser salvas– Não modificadas sobrepor

Não se deve escolher uma página usada com frequência– Voltará a ser reposta brevemente

12/16/2002 Sistemas Operativos 2001/2002 21

Algoritmo Óptimo de substituição de páginas

Substituir página necessária o mais tarde possível

– Óptimo, mas não realista

Estimar ...

– Fazendo registo das páginas usadas na última vez que o

processo correu

– Óptimo, mas impraticável.

12/16/2002 Sistemas Operativos 2001/2002 22

Algoritmo de substituição de páginas Not Recently Used (NRU)

Cada página tem: Reference Bit, Modified Bit– Bits são alterados quando a página é referenciada, modificada

Páginas são classificadas– Classe 0: Not referenced, not modified– Classe 1: Not referenced, modified– Classe 2: referenced, not modified– Classe 3: referenced, modified

NRU remove página, aleatoriamente, da classe mais baixa não vazia.

12/16/2002 Sistemas Operativos 2001/2002 23

Algoritmo de substituição de páginas - FIFO

Mantém uma lista ligada de todas as páginas

– Pela ordem em que chegam à memória

Páginas no inicio da lista são substituídas

– Página à cabeça é a que está à mais tempo em memória

– Página na cauda é a mais recente

Desvantagem

– Não tem em conta se a página é ou não muito utilizada

12/16/2002 Sistemas Operativos 2001/2002 24

Algoritmo de substituição de páginas “Second Chance”

Página carregada

mais recentemente

0 3 7 8 12 14 15 18Primeira página

carregadaA HB C D E F G

Operações do algoritmo– Páginas ordenadas em FIFO– Lista se a falha ocorre no instante 20, A tem o bit R activado

AC D E F G HA é tratada como uma

página carregada

recentemente

3 7 8 12 14 15 18 20Tempo em que foram carregadas B

12/16/2002 Sistemas Operativos 2001/2002 25

Algoritmo de substituição de páginas “The Clock”

AL B

K Quando ocorre uma falha de página, a página para a qual o ponteiro aponta é inspeccionada.

A acção a tomar depende do bit R:

-R=0: Remover a página e avançar ponteiro

-R=1: Limpar R e avançar ponteiro

Quando ocorre uma falha de página, a página para a qual o ponteiro aponta é inspeccionada.

A acção a tomar depende do bit R:

-R=0: Remover a página e avançar ponteiro

-R=1: Limpar R e avançar ponteiro

C

J D

I E

H FG

12/16/2002 Sistemas Operativos 2001/2002 26

Last Recently Used (LRU)

Assume que as páginas usadas recentemente voltarão a ser usadas em breve– Deitar fora as páginas não usadas à muito tempo

Tem de manter uma lista ligada de páginas– Mais recentemente usados à cabeça, menos à cauda– Actualizar a lista cada vez que a memória é referenciada

Como opção, manter um contador em cada entrada page table– Escolher a página com o menor valor do contador– Periodicamente fazer reset ao contador (colocar a 0)

12/16/2002 Sistemas Operativos 2001/2002 27

Algoritmo baseado em hardware-Aging

0 1 1 100 1 2 3

Página

0 0 1 10 1 2 3

Página

0 0 0 10 1 2 3

Página

0 0 0 00 1 2 3

Página

0 0 0 00 1 2 3

Página

0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 010 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 0 120 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 03

(a) (b) (c) (d) (e)

0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 01 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 01 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 01 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0

(f) (g) (h) (i) (j)

LRU usando matrizes – páginas referenciadas por ordem: 0,1,2,3,2,1,0,3,2,3

12/16/2002 Sistemas Operativos 2001/2002 28

Algoritmo em Software - AGING

– Notar que existem 6 páginas para 5 ticks de clock

1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0

10000000

00000000

10000000

00000000

10000000

10000000

11000000

10000000

01000000

00000000

11000000

01000000

11100000

11000000

00100000

10000000

01100000

10100000

11110000

01100000

00100000

01000000

10110000

01010000

Bits R para páginas 0-5

em t3

Bits R para páginas 0-5

em t2

Bits R para páginas 0-5

em t1

Bits R para páginas 0-5

em t0

Bits R para páginas 0-5

em t4

Página

011110000

1 10110000

2 10001000

3 00100000

4 01011000

5 00101000

12/16/2002 Sistemas Operativos 2001/2002 29

Algoritmo de substituição de páginas Working Set

12/16/2002 Sistemas Operativos 2001/2002 30

Algoritmo de substituição de páginas “WSClock”

12/16/2002 Sistemas Operativos 2001/2002 31

Algoritmo de substituição de páginas - Resumo

Boa eficiênciaWSClockDificil de implementarWorking SetEficiente que se aproxima do LRUAgingFraca aproximação do LRULFUExcelente, dificil de implementarLRURealistaClockMelhorias ao FIFOSegunda hipotese

Pode retirar páginas importantesFIFOPouco eficienteNRUNão é possivel (referência)ÓptimoComentárioAlgoritmo