Faculdade Pernambucana - FAPE Sistemas Operacionais Abertos

Faculdade Pernambucana - FAPE

Sistemas Operacionais Abertos

Gerenciamento de Memória A memória é um recurso que precisa ser

gerenciado com cuidado. Lei de Parkinson: “Os programas tendem a expandir até

ocupar toda a memória disponível para armazená-los” A maioria dos computadores tem um hierarquia de

memória, sendo função do SO coordenar como essas memórias são utilizadas.

A parte do SO responsável pela gerencia dessa hierarquia é o gerenciador de memória. Algumas funções:

Controla que partes da memória está em uso Aloca memória para processos Realiza o swap

Gerenciador Básico de Memória

Os sistemas de gerenciamento de memória podem ser divididos em duas classes:

Aqueles que movem processos de um lado para outro entre a MP e o disco durante a execução

Aqueles que não fazem a atividade anterior.

Monoprogramação sem Troca ou Paginação

O esquema mais simples de gerenciamento de memória é executar somente um programa por vez, compartilhando a memória entre esse programa e o SO.

Três maneiras simples de organizar memória com um sistema operacional e com um processo de usuário. Também existem outras possibilidades.


Gerenciador Básico de Memória Quando o sistema está organizado dessa maneira,

somente um processo por vez pode estar executando.

Multiprogramação com Partições Fixas

Para sistemas operacionais complexos é necessário compartilhamento de tempo.

Uso otimizado da CPU Pseudoparalelismo

A maneira mais fácil de alcançar a multiprogramação é simplesmente dividir a memória em n partições (possivelmente desiguais) ao iniciar o sistema.


(a) Partições fixas de memória com filas separadas para cada partição.(b) Partições fixas de memória com uma única fila de entrada

Gerenciador Básico de Memória A desvantagem de classificar os jobs de entrada em

filas separadas torna-se aparente quando a fila para uma partição grande está vazia, mas a fila para uma partição pequena está cheia.

Uma organização alternativa é manter uma única fila. Sempre que uma partição torna-se livre, o job mais próximo do

início da fila que se ajusta na partição vazia poderia ser carregado nela e executado.

Para não discriminar jobs pequenos, uma saída é dispor de pelo menos uma partição pequena ou estabelecendo uma regra que um job não pode ser ignorado k vezes.

Gerenciador Básico de Memória Sistemas com partições fixas definidas ao iniciar

foi utilizado em mainframes IBM OS/360. Hoje em dia, poucos SOs suportam esse modelo,

se é que algum suporta.

Gerenciador Básico de MemóriaRealocação e Proteção A multiprogramação introduz dois problemas

essenciais que devem ser resolvidos: realocação e proteção

Problema da realocação: Endereços dentro do arquivo binário (produzido pelo

linkeditor) precisam ser ajustados para serem acessados quando o programa for carregado nas partições (em virtude do deslocamento).

Endereço 100 na partição 1 é acessado no endereço 100K + 100. Se fosse na terceira partição seria 400K + 100

Gerenciador Básico de MemóriaRealocação e Proteção A realocação durante o carregamento não resolve

o problema da proteção. Um programa malicioso sempre pode construir uma nova

instrução e saltar para ela. Em sistemas multiusuários, é indesejável deixar um

processo ler ou gravar memória pertencente a outros usuários.

A solução que a IBM escolheu para proteger os 360 foi dividir a memória em blocos de 2KB e atribuir um código de proteção de 4 bits a cada bloco

Gerenciador Básico de MemóriaRealocação e Proteção O hardware do 360 interrompia qualquer tentativa,

por parte de um processo em execução, de acessar memória cujo código de proteção o impedia.

Uma solução alternativa para ambos os problemas, realocação e proteção, é equipar a máquina com dois registradores especiais de hardware, chamados registrador de base e registrador de limite.

Gerenciador Básico de MemóriaRealocação e Proteção Quando um processo é agendado, o registrador de

base é carregado com o endereço do início de sua partição, e o registrador de limite é carregado com o comprimento de sua partição.Ex:

Registrador de base = 100kCALL 100 transforma-se em CALL 100K + 100

O hardware protege os registradores de base e de limite para impedir que os programas de usuários os modifiquem.

Desde os 286 um esquema melhor foi adotado

Troca Com um sistema de lotes, organizar a memória em

partições fixas é simples e efetivo. Cada job é carregado em uma partição quando chega no

começo da fila e permanece na memória até que termine. Às vezes, não há memória principal suficiente para

armazenar todos os processos atualmente ativos, então os processos em excessos são mantidos no disco e trazidos de lá para execução dinamicamente.

Troca Duas abordagens dependendo do hardware

disponível: Troca – Permite trazer cada processo inteiro, executá-lo

temporariamente e, então, devolvê-lo ao disco Memória virtual – Permite que os programas executem

mesmo quando estão apenas parcialmente na memória.

Troca

As alterações de alocação de memória enquanto os processos entram e saem da memória. As regiões sombreadas correspondem à memória não-utilizada

Troca A flexibilidade de usar partições variáveis

introduzem uma maior complexidade na tarefa de alocar e desalocar memória.

Quando a troca cria múltiplas lacunas na memória, é possível juntar todas elas em um grande espaço, movendo todos os processos para baixo o máximo possível (compactação de memória).

Quanta memória deve ser alocada para um processo?

Se possuir tamanho fixo, a memória é o tamanho indicado Senão, a técnica é mais apurada.

Troca Se existir uma lacuna adjacente ao processo, ela pode ser

alocada e oferecida ao processo. Se não existir, o processo em crescimento terá de ser

movido para uma lacuna maior ou um ou mais processos terão de ser enviados para o disco para criar essa lacuna.

Por fim, se o processo não pode crescer na memória, e a área de troca no disco está cheia, o processo deverá esperar ou ser eliminado.

Se é esperado que a maioria dos processos crescerá ao executar, provavelmente é uma boa idéia alocar uma pequena memória extra sempre que se fizer a troca ou mover-se um processo

Troca

(a) Alocando espaço para um segmento de dados crescente. (b) Alocando espaço para uma pílha e para um segmento de dados crescente

TrocaGerenciamento de Memória com Mapas de bits. Quando a memória é atribuída dinamicamente,o

sistema operacional deve gerenciá-la. Duas maneiras de monitorar o uso de memória:

Mapas de bits e listas livres Mapa de bits

A memória é dividida em unidades de alocação, talvez tão pequenas quanto algumas palavras e talvez tão grandes quanto vários kilobytes.

Correspondendo a cada unidade de alocação há um bit no mapa de bits,que é 0 se a unidade está livre, e 1 se estiver ocupada (ou vice-versa)

(a) Uma parte da memória com cinco processos e três lacunas. Os traços menores mostram as unidades de alocação de memória. As regiões sombreadas (0 no mapa de bits) estão livres. (b) O mapa de bits correspondente. (c) As mesmas informações como uma lista.

TrocaGerenciamento de Memória com Mapas de bits.

TrocaGerenciamento de Memória com Mapas de bits. O tamanho da unidade de alocação é uma

importante questão de projeto. Quanto menor a unidade de alocação maior o mapa de

bits (e vice-versa). Uma memória de 32n bits utilizará n bits de mapa usando

uma unidade de alocação de 4 bytes. A pesquisa no mapa de bits por uma lacuna de k

bits 0 consecutivos para acomodar um processo é uma atividade lenta.

TrocaGerenciamento de Memória com Listas

Encadeadas Consiste numa lista encadeada dos segmentos de

memória alocados e livres, onde um segmento é um processo ou uma lacuna entre dois processos.

Um processo que termina normalmente tem dois vizinhos (exceto quando está na parte superior da memória)

A eliminação de um processo leva a quatro combinações:


Encadeadas

Quatro Combinações de Vizinho para o Processo Terminante X.


Encadeadas Quando os processos e as lacunas são mantidos

em uma lista classificada por endereço, vários algoritmos podem ser utilizados para alocar memória para um processo recentemente criado ou trocado para a memória.

Algoritmo do primeiro ajuste: Varre a lista de segmentos até encontrar uma memória

que seja suficientemente grande. Ao achar, a lacuna é dividida em um espaço para o processo e em um outra para a memória não-utilizada.


Encadeadas Algoritmo do próximo ajuste:

Semelhante ao primeiro ajuste com exceção de que ele monitora a posição em que ele está sempre que encontra uma lacuna adequada. Na próxima vez em que é chamado a pesquisa não começará do início da lista e sim a partir do lugar que ele deixou da última vez. Desempenho ligeiramente inferior ao do algoritmo do primeiro ajuste


Encadeadas Algoritmo do melhor ajuste:

Pesquisa na lista inteira e pega a melhor lacuna que seja adequada.

Mais lento que o primeiro ajuste. Algoritmo do pior ajuste:

Sempre pegar a maior lacuna disponível de modo que a lacuna resultante seja suficientemente grande para ser útil.


Encadeadas Todos os 4 algoritmos podem ser acelerados

mantendo-se listas separadas para processos e para lacunas.

Listas de lacunas podem ser classificadas por tamanho tornando o algoritmo do melhor ajuste mais rápido.

As próprias lacunas podem ser utilizadas para guardar informações armazenadas na lista de lacunas (economia de memória)

Outro algoritmo de alocação: ajuste rápido


Encadeadas Ajuste rápido

Mantém listas separadas para alguns dos tamanhos exigidos mais comuns.

Tabela com n entradas em que a primeira é um ponteiro para a cabeça de um lista de lacunas de 4K, a segunda para lista de 8K, a terceira para lista de 12 K,etc.

Problema da fragmentação e custo associado para desfragmentar.

Memória Virtual As memória dos primeiros computadores eram

pequenas e caras. O PDP-1 tinha uma memória de 4096 palavras, de 18 bits

cada uma. Memória usada para abrigar tanto o SO quanto os programas de usuários.

Muitas vezes, o programador era obrigado a usar algoritmos mais lentos porque o melhor algoritmo não cabia na memória

Memória Virtual A solução tradicional para a questão da falta de

espaço de memória foi utilizar o conceito de memória secundária.

O programa era dividido em partes, chamadas overlays, que cabiam na memória disponível.

Cada overlay era carregado do disco para a memória, segundo a seqüência do programa, e executado.

O programador era responsável por gerenciar todo o processo de overlays sem qualquer ajuda do computador.

Memória Virtual Algumas tarefas do programador:

Dividir o programa em overlays. Decidir onde cada overlay devia ser armazenado na

memória secundária. Programar o transporte do overlay da memória secundária

para a memória principal e vice-versa.

Fica claro que a gerência do overlay era muito trabalhosa.

Memória Virtual Em 1961 foi criado um método para processar

overlay automaticamente, sem que o programador nem precisasse saber da sua existência. Esse método é conhecido como Memória Virtual.

A definição de overlays evoluiu para o conceito de memória virtual.

No início da década de 70, a memória virtual estava disponível na grande maioria dos computadores.

Memória Virtual Atualmente existem sistemas sofisticados de

memória virtual. Implementações:

Paginação

Segmentação

Segmentação com paginação.

Memória Virtual - Paginação Paginação é uma técnica utilizada por muitos

sistemas de memória virtual. Endereços gerados por programas são chamados endereços

virtuais e formam o espaço de endereço (endereçamento) virtual.

Em computadores sem memória virtual o endereço virtual é colocado diretamente no barramento de memória e corresponde diretamente a um endereço real ou físico

Com memória virtual, os endereços virtuais não vão diretamente para o barramento de memória, e sim para a Unidade de Gerenciamento de Memória (Memory Management Unit – MMU).

A posição e a função da MMU

Memória Virtual - Paginação A MMU é um hardware que mapeia os endereços virtuais em

endereços físicos de memória.

A relação entre endereços virtuais e endereços físicos de memória é dada pela tabela de páginas.

Memória Virtual - Paginação

Memória Virtual - Paginação Na paginação, o espaço de endereço virtual é

dividido em unidades chamadas páginas. Já a memória principal (física) é dividida em molduras de páginas.

As páginas e as molduras de página têm sempre o mesmo tamanho.

Com 64K de espaço de endereçamento virtual (16 bits) e 32K de memória física, temos 16 páginas virtuais e 8 molduras de página considerando uma página de 4K.

As transferências entre memória e disco são sempre em unidades de uma página.

Memória Virtual - Paginação Na figura anterior, ao utilizar a instrução MOVE

REG, 0, ocorre o seguinte: O endereço virtual 0 é enviado para a MMU. A MMU vê que esse endereço virtual cai na página 0

(0 a 4095), que de acordo com seu mapeamento é a moldura de página 2 (8192 a 12287)

Assim, transforma o endereço para 8192 e coloca o endereço 8192 no barramento.

O que acontece se o programa tentar utilizar uma página não-mapeada:

MOVE REG, 32780

Memória Virtual - Paginação O endereço corresponde ao byte 12 dentro da página

virtual 8 (iniciando em 32768). A MMU nota que a página não está mapeada e gera uma

interrupção, passado a CPU para o SO Tal interrupção é chamada falta/falha de página O SO seleciona uma moldura de página pouco utilizada e

grava o seu conteúdo de volta no disco. Então, ele busca a página que acabou de ser referenciada e

carrega-a na moldura de página que acabou de ser liberada Por fim, altera o mapa e reinicia a instrução interrompida.

A Operação interna da MMU com 16 páginas de 4K


Funcionamento da MMU convertendo o endereço virtual 8192 em 24580

Memória Virtual - PaginaçãoTabelas de Páginas Para realizar o mapeamento entre a pagina e sua

respectiva moldura é utilizada uma tabela chamada tabela de páginas.

Ela armazena o número da moldura de página correspondente a página virtual.

Apresenta um bit que indica se a página está ou não na memória (bit presente/ausente)

Se o bit presente/ausente for 0 uma interrupção é gerada, passando a CPU para o SO. Senão, o MMU gera o endereço físico.

Memória Virtual - Paginação Tabela de Página.

O endereço virtual é dividido em um número de página virtual e um deslocamento

O número de página virtual funciona como um índice na tabela de página para achar a moldura de página se houver.

O propósito da tabela de páginas é mapear páginas virtuais em molduras de página.

Duas questões importantes devem ser encaradas: A tabela de páginas pode ser extremamente grande O mapeamento deve ser rápido.


Tabela grande Com endereços de 32 bits teremos teremos 4G de

endereços Com páginas de 4k teremos 1 milhão de páginas

resultando em 1 milhão de entradas na tabela de páginas.

Rapidez no mapeamento Cada referência à memória deve ser feito o

mapeamento virtual para físico Cada instrução pode ser necessário 2 ou mais

referências à memória.


Para otimizar o desempenho, o projeto mais simples é ter uma única tabela de páginas consistindo em uma matriz de rápidos registradores de hardware.

O problema é o custo No outro extremo a tabela de páginas pode estar

inteiramente na memória principal.

(a) Um endereço de 32 bits com dois campos de tabela de páginas. (b) Tabelas de páginas de dois níveis

Memória Virtual Paginação

Tabela de Páginas Multinível

Tabelas de páginas multinível evita oproblema de ter páginas muito grandes na memória.

Tabela de páginas para o topo dos 4M de memória

Memória Virtual - Paginação O segredo para tabela de páginas multinível é

evitar manter todas as tabelas de página na memória todo o tempo.

Mais níveis podem ser explorados mas a complexidade aumentaria

O arranjo exato de uma entrada é altamente dependente de máquina, mas os tipos de informações presentes são grosseiramente os mesmos de máquina para máquina.

32 bits é um tamanho comum

Uma entrada típica de tabela de páginas


Memória Virtual - Paginação TLBs – Translation Lookaside Buffers

Na maioria dos esquemas de paginação as tabelas de páginas são mantidas na memória em virtude de seu tamanho

A solução é baseada na observação de que a maioria dos programas tende a fazer um grande número de referências a um pequeno número de páginas, e não o contrário

A solução foi equipar computadores com pequeno dispositivo de hardware para mapear endereços virtuais em endereços físicos sem passar pela tabela de página.

Essse dispositivo é chamado de TLB ou memória associativa.

Um TLB para acelerar a paginação



Funcionamento: Quando um endereço virtual é apresentado para a MMU

para tradução, o hardware primeiro verifica se seu número de página virtual está presente no TLB, comparando com todas as entradas simultaneamente (em paralelo)

Se uma coincidência válida for localizada, e o acesso não violar os bits de proteção, a moldura de página será tomada diretamente do TLB, sem passar pela tabela de páginas.

Pode ocorrer falha de proteção na leitura.


Se o número da página virtual não estiver no TLB, a MMU detecta a falta e faz uma pesquisa rotineira na tabela de páginas.

Em seguida, a MMU expulsa uma das entradas na TLB e a substitue pela página recém pesquisada.

Gerenciamento por Software do TLB No passado o gerenciamento de TLB é feito por hardware

(MMU). Entretanto, algumas páginas modernas fazem todo o gerenciamento de páginas por software

Memória Virtual - Paginação Nessas máquinas as entradas de TLB são explicitamente

carregadas pelo SO. Quando uma falta de TLB ocorre, em vez de a MMU

simplesmente ir para a tabela de páginas localizar e buscar a referência de página necessária, ela apenas gera uma falha de TLB e joga o problema para o SO.

Memória Virtual - PaginaçãoTabelas de Páginas Invertidas. Com 32 bits de endereçamento com 4k por tamanho de página

teremos 1 milhão de entradas na tabela de páginas. A tabela de página deve ter no mínimo 4MB

Com 64 bits com 4k por tamanho de página, é necessário 1015 bytes para a tabela de página (valor inaceitável para armazenar)

Solução: tabela de página invertida. O número de entradas na tabela é o número de molduras e não o

número de páginas. Com 64 bits de endereço e 4K por página é preciso só de 8192

entradas. Cada entrada monitora qual (processo, página virtual) está localizado

na moldura de página.

Memória Virtual - Paginação Problema da abordagem: a tradução virtual para físico

torna-se muito mais difícil. A solução é utilizar o TLB

Em uma falta de página a tabela invertida precisa ser pesquisada.

As tabelas de páginas invertidas são atualmente utilizadas em algumas estações de trabalho IBM e HP e vão se tornar mais comuns à medida que as máquinas de 64 bits difundirem-se

Documents

Faculdade Pernambucana - FAPE Sistemas Operacionais Abertos