Sistemas Operativos - web.fe.up.ptrma/SOPE/at/T11_12_13_14_15.pdf · Gestor de memória • gestor...

Sistemas OperativosGestão de memória

Rui Maranhão (rma@fe.up.pt)

Gestão de memória

• idealmente a memória seria

• grande

• rápida

• não volátil

• contudo, na realidade existem limitações físicas!

Portanto...

• hierarquia da memória

• pouca memória rápida (cara) - cache

• velocidade média - memória principal

• gigabytes de memória lenta - discos

• hierarquia gerida pelo gestor de memória

Gestor de memória

• gestor de memória faz parte do SO

• responsável por gerir de forma eficiente a memória

• manter informação sobre partes da memória em uso

• alojar (bem como remover) memória para processos quando necessário

Monoprogramação

Multiprogramação

• com partições fixas

•

Recursos: limitações

• recursos de um computador são limitados

• memória

• impressora

• CPU

• solução

• virtualização dos recursos

Memória virtual

• elimina restrição física imposta pelo tamanho da memória física

•

Gerir memória

• tipos de decisões que o sistema operativo tem de tomar em relação à memória principal

• reserva

• transferência

• substituição

Recolocação e protecção

• incerteza sobre o endereço de carregamento do programa

• endereço de variáveis, e das rotinas não pode ser absoluto

• um processo não pode sobrepor outro

• uso de valores de limites

• endereços adicionais à base

• endereços superiores ao limite são erros

Swapping

• a alocação de memória muda com

• processos que são carregados

• processos que são libertados

Swapping

• Alocação para segmento de dados crescente

• Alocação para segmento de dados e stack crescente

Libertar memória

• quando a memória é atribuída de forma dinâmica, o sistema operativo têm de gerir o processo

• 2 formas de manter o uso de memória

• bitmasks

• listas ligadas (free lists)

Gestão com bitmaps

• zona de memória com 5 processos e 3 “buracos”

• bitmap correspondente

• semelhante a uma lista ligada

Gestão com lista ligadas

Algoritmos de transferência

• Existem três situações em que é necessário transferir dados

• a pedido (on request)

• por necessidade (on demand)

• por antecipação (prefetching)

Swapping / paging

• quando é necessário libertar espaço na memória física o SO copia páginas para disco

• terminologia: swapping vs. paging

• granularidade

• minimizar latência: pre-fetching

• traz páginas antes de serem pedidas

Algoritmos de substituição segmentos

• possíveis critérios para decidir qual o processo a transferir para disco

• estado e prioridade

• tempo de permanência na memória principal

• dimensão do processo

Reserva de memória

• paginação (paging)

• muito simples, basta encontrar uma página livre numa Lista de Páginas Livres

• segmentação

• tamanho variável dos segmentos torna complexo a reserva do espaço

• libertação exige recompactar segmentos

Paging

• Em geral, os sistemas de memória virtual usam paging

•

Paging

• a relação entre endereços virtuais e físicos é dado por uma tabela

Paging

• operação da MMU com 16 páginas de 4KB

Paging - tornar mais rápido

• em sistemas de paginação

• o mapeamento entre os endereços de memória virtual e físicos tem de ser rápido

• se o endereços virtuais forem grandes, a tabela de páginas terá de ser grande

• algoritmo mais usado: translation lookaside buffers (TLB)

Rejeição de páginas

• um page fault origina

• decidir que página em memória rejeitar

• criar espaço para uma nova página

• uma página modificada tem de ser escrita

• convém rejeitar páginas frequentemente usadas

• para evitar overheads!

Rejeição de páginas

• situação óptima: rejeitar a página que será usada mais tarde

• impraticável

• aproximado por estimativa

• histórico de execuções

• também é impraticável. Porquê?

NRU

• cada página tem 1 bit de acesso e 1 de escrita

• páginas são classificadas

1. não acedida, não modificada

2. não acedida, modificada

3. acedida, não modificada

4. acedida, modificada

FIFO

• mantém uma lista de páginas em memória

• segundo a ordem que foram carregadas

• página no topo da lista é rejeitada

• desvantagem

• página há mais tempo em memória pode também ser a mais usada

Segunda oportunidade

• ordem FIFO

• se a página mais antiga tiver sido acedida, não é rejeitada

• é limpo o bit de acesso e colocada no fim da lista

Rejeição de páginas relógio

LRU

• menos usada recentemente (LRU)

• eficaz segundo o princípio de localidade

• latência associada à implementação

• utilização de um contador por página

• quando atingir um valor máximo, passa para a lista das livres (e/ou modificadas)

Working Set

• o conjunto de páginas usadas pelo processo corrente é designado de working set

• manter em memória páginas do processo que está a ser executado

WSClock

Rejeição de páginas

Algoritmo PropriedadesOptimo Inexequıvel. Padrao para comparacao.

NRU (nao usado recentemente) Aproximacao grosseira.FIFO Leva a rejeicao de paginas importantes.

Segunda Oportunidade Melhoramento do FIFO.Relogio Solucao realista.LRU Muito bom. Implementacao exacta difıcil.NRU Aproximacao grosseira do LRU.Aging Aproximacao boa e eficiente do LRU.

Working set Implementacao ineficiente.WSClock Aproximacao boa e eficiente.

Rejeição de páginas

Algoritmo PropriedadesOptimo Inexequıvel. Padrao para comparacao.

NRU (nao usado recentemente) Aproximacao grosseira.FIFO Leva a rejeicao de paginas importantes.

Segunda Oportunidade Melhoramento do FIFO.Relogio Solucao realista.LRU Muito bom. Implementacao exacta difıcil.NRU Aproximacao grosseira do LRU.Aging Aproximacao boa e eficiente do LRU.

Working set Implementacao ineficiente.WSClock Aproximacao boa e eficiente.

Rejeição de páginas

Algoritmo PropriedadesOptimo Inexequıvel. Padrao para comparacao.

NRU (nao usado recentemente) Aproximacao grosseira.FIFO Leva a rejeicao de paginas importantes.

Segunda Oportunidade Melhoramento do FIFO.Relogio Solucao realista.LRU Muito bom. Implementacao exacta difıcil.NRU Aproximacao grosseira do LRU.Aging Aproximacao boa e eficiente do LRU.

Working set Implementacao ineficiente.WSClock Aproximacao boa e eficiente.

Condição de Belady

• para a mesma sequência de referências, as substituições devem diminuir com o aumento de memória central

• e.g., LRU

• FIFO não obedece à condição...

Sistemas paginados

• aspectos de concepção de

• alocação local e global

• controlo de carga (thrashing)

• tamanho das páginas

• ...

Alocação

• como deverá ser a memória alocada entre os processos em execução?

•

Alocação

Controlo de carga

• mesmo usando bons algoritmos, pode ainda ocorrer thrashing

• quando frequência de page faults indica

• alguns processos precisam de mais memória

• mas nenhum pode ceder memória

Controlo de carga

• solução

• reduzir número de processos que competem por memória

• passar processos para disco e dividir as páginas que lhes estavam atribuídas

• rever grau de multi-programação

Tamanho de páginas

• determinado pelo hardware (geralmente)

• não existe um tamanho ideal

Tamanho de páginas

• Páginas pequenas

• menos fragmentação interna

• melhor adequação a várias estrutura de dados e código

• menos partes de programação não usados em memória

• mas, mais páginas (tabela de páginas maiores)

Tamanho de páginas

• Overhead devido às tabelas e à fragmentação

• overhead = ((s . e) / p) + (p / 2)

• s - tamanho médios dos processos (bytes)

• p - tamanho das páginas

• e - entrada na tabela de páginas

• Valor óptimo quando p = sqrt(2 . s . e)

Separação

• geralmente computadores têm um único endereço de memória para programas e estrutura de dados

• Se for suficiente grande, tudo funciona bem

• mas, é geralmente pequeno!

Páginas partilhadas

• em grandes sistemas multi-programados é comum vários utilizadores usarem o mesmo programa ao mesmo tempo

Bibliotecas partilhadas

• em sistemas operativos modernos, várias bibliotecas são partilhadas por vários processos

Limpeza

• paginação funciona melhor quando existem muitas páginas livres

• Portanto, mecanismos de ‘limpeza’ de páginas que não estar a ser utilizadas pode melhor a performance

• page daemon

Pré-paginação

• paginação a pedido conduz a um número elevado de faltas de páginas

• pré-paginação: tentativa de eliminar faltas de páginas

• carregar para a memória mais páginas do que a necessárias

• Será uma boa ideia?

Estrutura de um programa

• a paginação é transparente para ao programador

• mas deve ser tido em conta!

• por exemplo:

•

Estrutura de um programa

• selecção cuidadosa das estruturas de dados pode reduzir o número de faltas de páginas

• stack - boa localidade de referência

• hash tables - má localidade de referência

• apontadores - tende a introduzir má localidade

Aspectos de implementação

• SO intervém 4 vezes na paginação

• criação do processo

• execução do processo

• na page fault

• fim de execução do processo

Aspectos de implementação

• tratamento da page fault

• o HW interrompe o kernel

• são salvaguardados os registos

• SO determina a página virtual necessária

• SO valida endereço e procura page frame

• se a página foi alterada escreve-a para disco

Backup de instruções

Fixação de páginas

• Alguns frames podem ser “fechados” (locked)

• páginas não poderão ser substituídas!

• Exemplos

• kernel (estruturas de dados), processos com tempos de execução críticos, buffers de I/O

Paging-out

Segmentação

Segmentação

Segmentação vs. Paging

Fragmentação

•

Reserva de segmentos

• best-fit (o menor possível)

• worst-fit (o maior possível)

• first-fit (o primeiro possível)

• next-fit (o primeiro possível a seguir ao anterior)

Critérios de escolha de blocos livres: Algoritmo buddy

• A memória livre é devidida em blocos de dimensão b^n

• se b=2, buddy binário

• para satisfazer um pedido de dimensão D, percorre-se a lista à procura de um bloco de dimensão 2^k tal que 2^k-1 < D <= 2^k

• se não for encontrado procura-se um de 2^k+1 que será dividido em duas partes iguais (buddies)

• um deles será dividido até se encontrar um de dimensão 2^k

• se possível, na libertação um bloco é recombinado com o seu buddy

• consegue-se um bom equilibrio entre o tempo de procura e a fragmentação interna e externa

UNIXGestão de memória

Unix - gestão de memória

• Unix, implementação sobre arquitecturas diferentes

• dois grupos de implementação

• segmentação com swapping

• paginação

Transferência (Swapping)

• arquitecturas segmentadas

• regiões carregadas contiguamente

• transfere para disco processos bloqueados

• existem 4 situações que provocam transf.

• fork, brk (expande segmento), crescimento da stack, carregar processos que estavam swap-out

Swapper

• processo que efectua as transferências de segmentos entre memória principal e secundária

• área especial do disco reservado para os segmentos retirados de memória

Paginação

• um processo têm inicialmente 3 regiões

• código, dados, e stack

• cada região tem uma tabela de páginas

Tabela paginação/descritores de blocos de disco

Significado dos campos

• P - present

• R - referenced

• M - modificada

• C/W - copy-on-write

• PROT - bits de protecção

• Idade - algoritmo de page stealer

• end. físico da page frame

• num do bloco e num dispositivo

• tipo - swap, demand fill, demand zero

Tabela pfdata

• permite a gestão eficaz das páginas de memória física

• indexada pelo número de página física

• contém

• estado da página

• contador com número de processos

• número de device e block

Substituição de páginas

• aproximação ao algoritmo LRU

• idade da página é mantida na PTE

• page-stealer é acordado quando o número de páginas livres desce abaixo do limite

• percorre as PTE incrementando a idade

• se página for referenciada, idade é anulada

• se página atingir certa idade, marca-a para ser transferida

Criação de um processo

• fork: duplica os segmentos do processo

• não é feita cópia física de memória

• cria nova tabela de regiões para o filho

• dá-lhe a mesma região de código

• copia as regiões de dados e pilha

• percorre PTE do pai e actualiza pfdata e coloca a 1 o bit copy on write

• antes duma página ser escrita

• o sistem copia-a para uma nova página que aloca

• preenche a PTE do processo onde ocorreu a falta com o endereço físico

• só se copia páginas que foram modificadas

fork

Tratamento de copy-on-write