Gerenciamento de Memória Virtual em Sistemas Operacionais

Estruturas de Hardware e Controle de Memória

• Todas as referências à memória dentro de um processo são endereços lógicos a serem traduzidos em endereços físicos durante a execução.
• Um processo pode ser dividido em várias partes (páginas ou segmentos) e não precisam ser contíguos durante a execução.
  • Isto é possível pela combinação de tradução dinâmica de endereços e o uso de tabelas de página ou segmento.

Execução de um Programa e Gerenciamento de Memória

• O sistema operacional carrega para a memória principal apenas alguns fragmentos do programa, incluindo o fragmento que contém o início do programa.
• O conjunto residente do processo é a parte do processo que está, de fato, na memória principal.
• Se o processador encontra um endereço que não está na memória principal, ele gera uma interrupção.
• O sistema operacional coloca o processo interrompido em estado bloqueado.

• O fragmento do processo que causou a falha é trazido para a memória principal, para o qual o sistema operacional:
  • Emite uma solicitação de leitura de E/S para o disco.
  • Emite outro processo para ser executado enquanto a operação de E/S é concluída.
  • Quando a transação de E/S é concluída, uma interrupção é emitida, e o sistema operacional modifica o estado do processo para Pronto.

Vantagens da Memória Virtual

• Mais processos podem ser mantidos na memória principal.
  • Apenas alguns fragmentos do processo são carregados na memória principal.
  • Utilização mais eficiente do processador.

Pelo menos um processo, dos muitos que estão na memória principal, estará no estado Pronto.

• É possível que um processo seja maior que a memória principal total.
  • Com a paginação ou segmentação baseada em memória virtual, o programador não precisa se preocupar se seu programa é muito grande.

Tipos de Memória (Execução)

• Memória Real
  • Memória Principal
• Memória Virtual
  • Permite a efetiva multiprogramação.
  • Remove as restrições de memória principal para o usuário.

Debulha (Thrashing)

• Se um fragmento é ejetado imediatamente antes do uso, ele deve ser trazido de volta quase imediatamente.
• Muitas trocas levam à debulha (thrashing).
• O processador consome mais tempo trocando fragmentos do que executando as instruções do usuário.

Princípio da Localidade (Proximidade)

• As referências aos dados e ao programa dentro de um processo tendem a se agrupar.
• Por curtos períodos de tempo, apenas alguns fragmentos do processo serão necessários.
• Previsões inteligentes sobre quais partes de um processo serão necessárias no futuro próximo.

Suporte Necessário para Memória Virtual

• O hardware deve suportar paginação e segmentação.
• O sistema operacional deve incluir software para gerenciar a movimentação de páginas ou segmentos entre memória principal e secundária.

Página (Page)

• Cada processo tem sua própria tabela de páginas.
• Cada entrada na tabela de páginas contém o número do quadro da página correspondente na memória principal.
• Um bit é necessário para indicar se a página está na memória principal ou não.
• Outro bit é usado para indicar se o conteúdo da página foi modificado desde que ela foi carregada na memória principal. Se não houver alteração, não é necessário atualizar a página quando ela é substituída.

Tabelas de Páginas

• Existe uma tabela de páginas por processo.
• Algumas tabelas podem ocupar uma grande quantidade de memória principal.
• As tabelas de páginas são armazenadas na memória virtual.
• Quando um processo está em execução, pelo menos parte de sua tabela de páginas deve estar na memória principal.

Buffer de Tradução de Endereços (TLB)

• Cada referência à memória pode gerar dois acessos à memória:
  • Para a entrada da tabela de páginas.
  • Para obter os dados desejados.
  • Para resolver este problema, a maioria dos esquemas de memória virtual usa um cache de entradas especiais da tabela de páginas, chamado Buffer de Tradução de Endereços (Translation Lookaside Buffer - TLB).
• Contém as entradas da tabela de páginas usadas mais recentemente.
• Dado um endereço virtual, o processador examina a TLB.
• Se a entrada da tabela de páginas estiver presente, ele obtém o número do quadro e, assim, o endereço real.
• Se não for encontrado, o processador usa o número da página como um índice para procurar na tabela de páginas do processo.
• Se encontrar o bit de presença ativo, isso indica que a página está na memória principal e o processador pode obter o número do quadro e, portanto, o endereço físico.
• O processador atualiza a TLB.
• Por outro lado, se o bit de presença não estiver ativo, isso significa que a página não está na memória principal, o que é chamado de falha de página.

Tamanho da Página

• Quanto menor o tamanho da página, menor a fragmentação interna.
• Quanto menor a página, maior o número de páginas necessárias por processo.
• Mais páginas significam mais tabelas de páginas.
• Com quadros de página grandes, a maioria das tabelas estará na memória virtual.
• As características físicas da maioria dos dispositivos de armazenamento secundário são adequadas para tamanhos de página maiores.
• Com um tamanho de página pequeno, um maior número de páginas pode estar disponível na memória principal.
• Depois de um tempo, todas as páginas na memória contêm algumas das referências recentes do processo. Portanto, as falhas de página serão menores.
• Ao aumentar o tamanho da página, ela pode conter referências a posições distantes recentemente, aumentando o risco de falha de página.
• Tamanhos de página diferentes oferecem maior flexibilidade no uso da TLB.
• Páginas maiores podem ser atribuídas a instruções do programa.
• Páginas de tamanho pequeno podem ser atribuídas a uma pilha de execução.

Segmentação

• A segmentação permite ao desenvolvedor considerar a memória como se fosse constituída por vários espaços de endereço.
• Os segmentos podem ter tamanhos diferentes, mesmo de forma dinâmica.
• Os endereços de memória consistem no número do segmento e no deslocamento.
• Simplifica o gerenciamento de estruturas de dados em crescimento.
• Permite modificar e recompilar partes do programa de forma independente.
• Permite o compartilhamento de dados entre processos.
• Permite proteção.

Tabela de Segmentos

• Cada entrada da tabela contém o endereço inicial do segmento na memória principal e seu comprimento.
• Contém um bit, indicando que o segmento já está na memória principal.
• Contém um bit que indica se o segmento foi modificado desde que foi carregado na memória principal.
• Contém outros bits de controle: proteção ou compartilhamento.

Combinação de Paginação e Segmentação

• Aproveita as vantagens da paginação e segmentação.
  • Cada segmento pode ser dividido em páginas de tamanho fixo.
  • Associado a cada processo, há uma tabela de segmentos e várias tabelas de páginas.

Proteção e Compartilhamento

• Uso de um sistema de anéis de proteção.
• Anéis interiores têm mais privilégios.
• Um programa pode acessar apenas os dados dos anéis de mesmo nível ou de anéis menos privilegiados.
• Um programa pode fazer chamadas para os serviços que residem no mesmo anel ou em anéis com maiores privilégios.

Políticas do Sistema Operacional na Memória Virtual

• O projeto de gerenciamento de memória em um sistema operacional depende de três áreas:
  • Se as técnicas de memória virtual são usadas ou não.
  • Uso da segmentação e paginação.
  • Os algoritmos para gerenciamento de memória.

Os dois primeiros itens dependem da plataforma de hardware disponível. O terceiro ponto é o domínio do software do sistema operacional.

Algoritmos para Gerenciamento de Memória

• Desempenho: visa minimizar as falhas de página.
  • Quando ocorre uma falha de página, há uma sobrecarga de software.

O sistema operacional deve:

Substituir páginas.

Agendar outro processo para execução.

• A probabilidade de se referir a uma página ausente é mínima.

Política de Leitura (Fetch Policy)

• Relacionada à decisão de quando carregar uma página na memória principal.
  • Paginação por Demanda

A página é trazida para a memória somente quando há uma referência a uma posição nela.

Quando um processo é executado pela primeira vez, haverá muitas falhas.

• Pré-leitura de Páginas (Page Pre-fetching)

Carrega páginas que ainda não foram referenciadas devido a uma falha de página.

Se as páginas são carregadas sequencialmente da memória secundária, é mais eficiente trazer um bloco de páginas contíguas.

• A pré-leitura de páginas não deve ser confundida com a troca (swapping). Quando um processo é descarregado da memória e passa para o estado de suspensão, todas as páginas residentes também são removidas.

Políticas de Posicionamento (Placement Policy)

• Determina onde uma parte do processo residirá na memória principal.
• Para a segmentação pura: best-fit, first-fit e next-fit.
• Na combinação de segmentação com paginação, a localização é irrelevante.

Políticas de Substituição (Replacement Policy)

• Seleciona a página a ser substituída ao carregar uma nova página.
• Objetivo: Substituir a página que tem a menor chance de ser referenciada no futuro próximo.
• Tenta prever o futuro com base no passado.

Bloqueio de Quadros (Frame Locking)

• Restrição da política de substituição.
  • Quando um quadro é bloqueado, a página carregada neste quadro não pode ser substituída.
• O núcleo do sistema operacional e estruturas de controle em pontos-chave são bloqueados.
• Um bit de bloqueio é associado a cada quadro.

Algoritmos de Substituição

• Política Ótima (Optimal Policy)
  • Seleciona para substituir a página que terá que esperar a maior quantidade de tempo até ser referenciada.
  • O sistema operacional requer um conhecimento preciso dos eventos futuros.
  • Serve como um padrão para comparar outros algoritmos.
• Política Menos Recentemente Usada (Least Recently Used - LRU).
  • Substitui a página que não foi referenciada há mais tempo.
  • Pelo princípio da localidade, é a página que será menos provável de ser referenciada em um futuro próximo.
  • Para a execução, seria necessário identificar cada página no momento de sua última referência, o que envolve uma sobrecarga.
• Política Primeiro a Entrar, Primeiro a Sair (First-In, First-Out - FIFO).
  • Trata os quadros atribuídos a um processo como um buffer circular.
  • As páginas são removidas da memória de acordo com a técnica de rotação.
  • Simples de implementar.
  • Substitui a página que está há mais tempo na memória.
  • Amplamente utilizado quando os dados são carregados e removidos várias vezes.
• Política do Relógio (Clock Policy)
  • Requer um bit adicional associado a cada quadro, chamado bit de uso.
  • Quando uma página é carregada pela primeira vez em um quadro na memória, o bit de uso é desmarcado (definido como 0).
  • Ao se referir à página, o bit é definido como 1.
  • Quando é hora de substituir uma página, o primeiro quadro encontrado com o bit de uso em 0 é substituído.
  • Durante a pesquisa, todos os bits de uso que são 1 são alterados para 0.
• Páginas em Buffer.
  • Usa a política FIFO.
  • A página substituída é atribuída a uma das duas listas:

Páginas livres: se não tiver sido modificada.

Páginas modificadas.

• A página não é fisicamente movida da memória principal, apenas sua entrada na tabela de páginas é apagada.

Gerenciamento do Conjunto Residente

• Tamanho do Conjunto Residente.
  • O sistema operacional deve decidir a quantidade de memória principal a ser atribuída a um determinado processo.

Quanto menor o número de quadros atribuídos a um processo, maior o número de processos que podem estar na memória principal.

Se houver um pequeno número de páginas, a taxa de falha de página é maior.

A alocação de memória adicional para um determinado processo não terá grandes efeitos sobre a porcentagem de falhas de página.

• Alocação Fixa.
  • Atribui ao processo um número fixo de quadros.
  • Se uma falha de página ocorre, uma página do processo deve ser substituída pela página necessária.
• Alocação Variável.
  • Permite que o número de quadros atribuídos mude.
  • Caso haja muitas falhas de página, mais quadros serão atribuídos.

Grau de Substituição

• O escopo de uma estratégia de substituição pode ser classificado como local ou global.
  • Global: Considera todas as páginas da memória como candidatas à substituição.
  • Local: Considera apenas as páginas do processo que causou a falha.

Controle de Carga (Load Control)

• Determina o número de processos que podem estar na memória principal.
• Pode haver poucos processos na memória; às vezes, todos podem estar bloqueados e passar muito tempo em troca (swapping).
• Por outro lado, pode haver muitos processos na memória, aumentando a possibilidade de falhas de página. O resultado é a debulha (thrashing).

Suspensão de Processos

• Se o objetivo é reduzir o grau de multiprogramação, um ou mais processos residentes na memória principal devem ser suspensos.
  • Processos com menor prioridade.
  • Processos com muitas falhas de página.
  • Último processo ativado.
  • Processo com o menor conjunto residente.
  • O processo mais antigo.
  • Processo com os maiores tempos de execução restantes.

• Benefícios do Uso de Memória Virtual

  • Melhor utilização do processador.
  • Remove a limitação de tamanho no desenvolvimento de software.
  • Tradução de endereço lógico em endereço real durante a execução.

Isso permite que processos estejam em qualquer posição da memória principal e mudem de localização ao longo do tempo.

• Divide um processo em fragmentos.

Não é necessário que esses fragmentos estejam localizados de forma contígua.

Não é necessário que todos os fragmentos estejam na memória principal.

• As abordagens básicas são paginação e segmentação de memória virtual.
• Um esquema de gerenciamento de memória requer suporte de hardware e software.
  • Hardware: Fornece o processador.

Tradução de Endereços Virtuais.

Geração de uma interrupção quando há falha de página.

• Software: Algoritmos para o gerenciamento de memória.
• Questões de design relacionadas ao suporte de gerenciamento de memória em sistemas operacionais:
  • Política de Leitura.
  • Políticas de Posicionamento.
  • Políticas de Substituição.
  • Gerenciamento do Conjunto Residente.
  • Políticas de Quitação.
  • Controle de Carga.