Como funciona a técnica de paginação?

Sistemas Operacionais
Capítulo 9
Gerência de Memória

9 � Gerência de Memória

9.1 � Introdução

• Na memória principal residem os programas em execução.
• Memória secundária são mecanismos de armazenamento permanente, são mais abundantes e baratas.
• Para um programa ser executado deve ser carregado na memória principal.
• Gerenciamento complexo em sistemas multiprogramáveis com múltiplos usuários utilizando-a eficientemente.

9.2 � Alocação Contígua Simples

• Implementada nos primeiros Sistemas Operacionais e ainda existentes em alguns sistemas monoprogramáveis.
• Memória dividida em duas partes, Sistema Operacional e programa do usuário.
• O programador tem controle sobre toda a memória principal, podendo acessar qualquer posição da memória, inclusive onde está residente o Sistema Operacional.
• Um mecanismo de proteção utilizado é delimitar a área do Sistema Operacional que delimita a área do mesmo.
• Fácil implementação e código reduzido, porém Ineficiência no uso do processador e da memória pois apenas um usuário pode dispor desse recurso.
• Programas limitados ao tamanho da memória disponível.
• Overlay (sobreposição) � Solução encontrada para dividir o programa em partes (módulos), de forma que pudessem executar independentemente uma da outra, utilizando uma mesma área de memória.
• A definição das áreas de Overlay são de responsabilidade do programador através de comandos específicos da linguagem utilizada.

9.3 � Alocação Particionada

• A eficiência da multiprogramação exige que vários programas estejam na memória ao mesmo tempo, vindo a necessidade de organização da memória.

9.3.1 � Alocação Particionada Estática:

• Divisão da memória em tamanhos fixos (partições) definidos na inicialização do Sistema em função dos programas que executariam no ambiente.
• A alteração do tamanho de uma partição necessita a inicialização do Sistema Operacional.
• Os programas só podiam executar em uma das partições, mesmo com outras disponíveis.
• Limitações impostas pelos compiladores e montadores que geravam apenas códigos absolutos.
• Posteriormente, evolução dos compiladores, linkers e loaders com geração de código realocável, sendo que os programas puderam ser carregados em qualquer partição (alocação particionada estática realocável).
• Surgimento da tabela de partições com informações de tamanho, uso e delimitações.
• Proteção da memória através de dois registradores, início e fim da partição.
• Os programas não preenchiam totalmente as partições onde eram carregados.
• Problemas de fragmentação.

9.3.2 � Alocação Particionada Dinâmica

• Aumento do grau de compartilhamento diminuindo o problema da fragmentação.
• Partições sem tamanho fixo, onde cada programa utiliza o espaço que necessita.
• Existe ainda o problema de fragmentação, conforme os programas vão terminando e deixando espaços cada vez menores.
• Soluções para resolver o problema de fragmentação:
• Primeira � Reunir os espaços adjacentes, produzindo um único espaço de tamanho maior.
• Segunda � Realocação de todas as partições ocupadas, eliminando todos os espaços entre elas (alocação dinâmica com realocação), porém, aumentando a complexibilidade do algoritmo e consumindo mais recursos do sistema.

9.3.3 � Estratégias para Escolha da Partição

• Função para determinar em qual partição livre um programa será carregado para execução.
• Função de evitar, ou diminuir, o problema da fragmentação antes que ele ocorra.
• O tamanho do programa é o fator mais importante para a adoção da melhor estratégia.
• Best-fit:
• Escolhe a melhor partição, ou seja, aquela que o programa deixa o menor espaço sem utilização.
• Lista de áreas livres alocada por tamanho, diminuindo o tempo de busca
• Desvantagem de deixar pequenas áreas não contíguas, aumentando o problema da fragmentação.
• Worst-fit:
• Escolhe a pior partição, ou seja, aquela que o programa deixa o maior espaço sem utilização.
• Diminui o problema de fragmentação, deixando espaços livres maiores que permitem a um maior número de programas utilizar a memória.
• First-fit:
• Escolhe a primeira partição livre de tamanho suficiente para carregar o programa
• Lista de áreas livres ordenada por endereços crescentemente.
• Grande chance de se obter uma grande partição livre nos endereços de memórias mais altos.
• Mais rápida e consome menos recursos do sistema.

9.4 � Swapping

• Tenta resolver o problema de insuficiência da memória para todos os usuários.
• Aloca espaço para programas que esperam por memória livre para serem processados.
• O sistema escolhe um programa residente, que é levado da memória para o disco (swap out), retornando posteriormente para a memória principal (swap in) como se nada tivesse ocorrido.
• Problema da realocação dos programas. O loader realocável permite que um programa seja colocado em qualquer posição da memória, porém a realocação é realizada no momento do carregamento.
• Mecanismo ineficiente em função do tempo gasto para carregamento.
• Uma alternativa é esperar que a região de memória usada pelo programa na ocasião do seu primeiro carregamento esteja disponível.
• Realocação Dinâmica:
• É a melhor solução, uma implementação no hardware dos computadores, permitindo que a realocação seja realizada durante a execução do programa.
• Realizada através de um registrador especial denomidado registrador de alocação, que recebe o endereço inicial da região da memória que o programa irá ocupar no momento do carregamento do programa na memória.
• Toda vez que ocorrer uma referência a algum endereço, o endereço contido na instrução será somado ao conteúdo do registrador, gerando assim, o endereço físico.
• Essencial para a implementação de um sistema multiprogramável.
• Permitiu um maior throughput através de um maior compartilhamento da memória.
• Mais eficiente para programas onde existiam poucos usuários competindo por memória e em ambientes que trabalhavam com aplicações pequenas.
• Seu maior problema é o elevado custo das operações de entrada/saída (swapped in/out).

9.5 � Memória Virtual

• Combina memória principal e secundária;
• Impressão da memória ser muito maior do que é;
• Desvinculação do endereçamento feito pelo programa dos endereços físicos da memória principal;
• Procura minimizar o problema de fragmentação da memória.

9.4.1 � Espaço de Endereçamento Virtual

• Conceito próximo a vetores em linguagens de alto nível;
• Referência a um componente do vetor sem preocupação com a posição da memória onde o dado está;
• Programa no ambiente de memória virtual não faz referência a endereços físicos de memória (endereços reais), mas apenas a endereços virtuais;
• Mapeamento � é a tradução do endereço virtual para o físico;
• Espaço de endereçamento virtual � é o conjunto de endereços virtuais que os processos podem endereçar.
• Espaço de endereçamento real � é o conjunto de endereços reais.
• Apenas parte do programa pode estar residente na memória em um determinado instante;
• O Sistema Operacional utiliza a memória secundária como uma extensão da memória principal.

9.5.2 � Mapeamento

• Mecanismo que transforma os endereços virtuais em endereços reais;
• Todo programa  precisa estar no espaços de endereçamento real para poder ser referenciado ou executado;
• Atualmente, o mapeamento é realizado via hardware junto com o Sistema Operacional, de forma a não comprometer seu desempenho e torná-lo transparente aos usuários e suas aplicações;
• A maioria das aplicações tende a fazer referência a um reduzido número de páginas, logo, somente uma pequena fração da tabela de páginas é necessária.
• Memória associativa ou Translation Lookside Buffer � Hardware especial para mapear endereços virtuais para endereços físicos sem a necessidade de acesso à tabelas de páginas;
• Quando um programa está em execução, existe uma tabela de mapeamento do processo no qual o programa executa. Se outro programa for executado no contexto de outro processo, o sistema deve passar a referenciar a tabela do novo processo. Toda vez que há mudança de contexto, o registrador é atualizado com o endereço da nova tabela.

9.5.3 � Paginação

• Técnica de gerência de memória onde o espaço de endereçamento virtual e o espaço de endereçamento real são divididos em blocos do mesmo tamanho (páginas);
• Páginas virtuais no espaço virtual e páginas reais ou frames (molduras) no espaço real;
• Todo mapeamento é realizado a nível de página, através de tabelas de páginas, em que cada página virtual do processo possui uma entrada na tabela ETP;
• Paginação por demanda  é quando as páginas dos processos são transferidas da memória secundária para a principal apenas quando são referenciadas.
• Paginação Antecipada é o carregamento de páginas na memória antecipadamente, sendo que o sistema tenta prever as páginas que serão necessárias à execução do programa.
• ALGORÍTMO DA PAGINAÇÃO.

9.5.3.1 � Working Set

• Problemas:
• Paginação exigem operações de E/S (que deve ser evitado) quando um processo faz referência a uma página que não se encontra na memória;
• O Sistema Operacional deve se preocupar em ter um certo número de páginas na memória que reduza ao máximo a taxa de paginação dos processos e não prejudique os demais processos que desejam acesso a memória.
• Observações:
• Quando um programa começa a ser executado, percebe-se uma elevada taxa de page faults (páginas que não se encontram na memória), que se estabiliza com o decorrer de sua execução.
• Localidade é a tendência que existe em um programa de fazer referências a posições de memória de forma quase uniforme, ou seja, instruções próximas.
• A partir da observação da localidade Denning formulou o modelo de working set.
• Working Set de um processo é o conjunto de páginas referenciadas por ele durante determinado intervalo de tempo, ou, segundo Denning, é o conjunto de páginas constantemente referenciadas pelo processo, devendo permanecer na memória principal para que execute de forma eficiente, evitando a elevada taxa de paginação (thrashing).
• Sempre que um processo é criado, todas as suas páginas estão na memória secundária.
• O Working Set deve Ter um limite máximo de páginas permitidas.

9.5.3.2 � Realocação de Páginas

• Problema em decidir quais páginas remover da memória principal.
• O Sistema Operacional deve considerar se uma página foi ou não modificada antes de liberá-la para outro processo, caso contrário, possíveis dados armazenados na página serão perdidos.
• Sempre que uma página é alterada, um bit de modificação é alterado de 0 para 1, informando que a página foi alterada.
• Melhor estratégia de realocação é escolher uma página que não será referenciada num futuro próximo. Tarefa difícil para o Sistema Operacional.
• Principais estratégias usadas pelos sistemas operacionais para realocação de páginas:
• Aleatória (random):
•  Não utiliza nenhum critério de seleção.
•  Consome menos recursos do sistema.
•  Raramente é utilizada.
•  First-In-First-Out (FIFO):
•  A página que primeiro foi utilizada será a primeira a ser escolhida.
•  Implementação bastante simples.
•  Necessário apenas uma fila. 
•  Least-Recently-Used (LRU):
•  Seleciona a página utilizada menos recentemente, ou seja, a que está há mais tempo sem ser referenciada.
•  Estratégia boa, mas pouco implementada;
•  Grande overhead causado pela atualização, em cada página referenciada, do momento do último acesso, além do algoritmo de busca dessas páginas. 
•  Not-Recently-Used (NRU):
•  Escolha da página que não foi recentemente utilizada (semelhante ao LRU).
•  Flag de referência � indica quando a página foi referenciada ou não.
•  Inicialmente, todas as páginas estão com o flag = 0, à medida que as páginas são referenciadas, o flag é modificado para 1. 
•  Last-Frequently-Used (LFU):
•  Escolhe a página menos referenciada.
•  Existe um controle do número de referências feitas às páginas.
•  É escolhida a página que o contador tem o menor número de referências.
•  Problema � As páginas que entrarem mais recentemente no working set serão as que estarão com o menor número no contador.

9.5.3.3 � Tamanho da Página

• Paginação leva a uma menor fragmentação, pois apenas poderá haver fragmentação na última página.
• A fragmentação é conseqüência do tamanho da página.
• Páginas pequenas, tabelas de mapeamento maiores, maior taxa de paginação e aumento do número de acesso à memória secundária, porém, menor fragmentação.
• Tamanho da página associado ao hardware e varia de sistema para sistema, norlamente entre 512 bytes e 64 kb.

9.5.4 � Segmentação

• Técnica de gerência de memória, onde os programas são divididos logicamente e em sub-rotinas e estruturas de dados e colocados em blocos de informações na memória
• Segmentos � blocos de tamanhos diferentes com seu próprio espaço de endereçamento.
• Segmentação X Paginação � Paginação com partes de tamanho fixo e segmentos com blocos de tamanhos variados e permite uma relação entre a lógica do programa e sua divisão na memória.
• Cada entrada na tabela de segmentos possuí o endereço do segmento na memória física, informações sobre o tamanho do segmento, sua proteção e se ele está na memória ou não.
• O Sistema Operacional mantém uma tabela com as áreas livres e ocupadas da memória.
• A escolha da área livre a ser ocupada por um processo a ser carregado na memória pode ser a mesma utilizada no item Alocação Particionada Dinâmica (best-fit, worst-fit ou first-fit).
• Apenas os segmentos referenciados são transferidos para a memória real.
• Os programas devem ser bem modularizados para uma maior eficiência.
• Existe também o problema da fragmentação e o problema da complexibilidade.

9.5.5 � Segmentação com Paginação

• Permite a divisão lógica dos programas e segmentos e, cada segmento é dividido fisicamente em páginas.
• Um endereço é formado pelo número do segmento, pelo número de página, contida nesse segmento, e pelo deslocamento dentro dessa página.
• O endereço físico é obtido somando-se a posição inicial do frame e o deslocamento.

9.5.6 � Proteção

• Necessária para impedir que um processo, ao acessar uma página/segmento do sistema, a modifique ou mesmo tenha acesso a ela.
• No esquema de memória virtual, cada processo tem sua própria tabela de mapeamento e a tradução dos endereços é realizada pelo sistema, impedindo assim, que um processo tenha acesso a áreas de memória de outros processos, a não ser que tenham compartilhamento explícito.
• A proteção deve ser realizada em nível de cada página/segmento na memória, utilizando-se as entradas da tabela de mapeamento, com alguns bits especificando permissões a cada uma das páginas/segmentos.

9.5.7 � Compartilhamento de Memória

• Bastante útil para programas de código reentrante.
• Bastante simples implementação do compartilhamento de código e dados entre vários processos, bastando que as entradas das tabelas de páginas/segmentos apontem para as mesmas páginas/segmentos na memória principal.
• Reduz o número de programas na memória principal e aumenta o número de usuários compartilhando o mesmo recurso.
• Segmentação X Paginação em relação ao compartilhamento:
• O compartilhamento de segmentos é mais simples que o de páginas, pois as tabelas de segmentos mapeiam estruturas lógicas, como sub-rotinas e estruturas de dados.
• Enquanto o mapeamento de um vetor necessita de várias entradas na tabela de páginas, na tabela de segmentos é necessária apenas uma única entrada.
• O segmento pode variar seu tamanho durante a execução com o crescimento de um vetor, por exemplo, na paginação, isso implica na alocação de novas páginas.

9.5.8 � Swapping em Memória Virtual

• Quando existem novos processos que desejam ser processados e não existe memória real suficiente, o sistema seleciona um ou mais processos que deverão sair da memória para ceder espaço aos novos processos.
• Os critérios mais utilizados para a escolha são a prioridade,  escolhendo processos de melhor prioridade, e o estado do processo, selecionando os processos que estão no estado de espera.

9.5.9 � Thrashing

• É a excessiva transferência de páginas/segmentos entre a memória principal e a memória secundária. Problema existente tanto em paginação quanto a segmentação.
• Na paginação:
• A nível de processo:
• o working set de um processo pode ser pequeno demais para acomodar as páginas constantemente acomodadas referenciadas por ele, a solução é aumentar o tamanho do working set.
• O thrashing também pode ocorrer pela não obediência do conceito da localidade, ou seja, o programa faz referência a comandos/dados localizados em páginas fora do working set do processo e a solução para isso é reescrever a aplicação.
• A nível de sistema:
• o trashing ocorre quando existem mais processos competindo por memória que espaço disponível.
• O primeiro passo é a redução do tamanho dos working set dos processos, mas isso pode levar o thrashing a nível de processo.
• Na segmentação:
• Em nível de processo, quando a trasferência de segmentos é excessiva devido a modularização extrema do programa não seguindo o conceito da modularidade.
• Em nível de sistema é semelhante ao caso da paginação.
• Em qualquer caso, se existem mais processos para serem executados que a memória real disponível, a única solução é expandir a memória principal.
• Este problema ocorre em todos os sistemas que possuem um mecanismo de gerência de memória.

[voltar]

Como funciona a paginação?

O que é sistema de paginação?

O que é memória virtual por paginação?

O que é paginação sob demanda?