Bom pessoal, acho que vamos, finalmente, chegar ao fim (pelo menos como eu havia pensado) desta série de artigos sobre os elementos básicos de funcionamento dos sistemas de computação. Este último tópico, sobre memória virtual, vai ser dividido em duas partes. Na primeira parte vamos ver como virtualizar, do ponto de vista dos programas de aplicação, o endereçamento de instruções e operandos na memória via
address translation. Na segunda parte vamos ver o algoritmo mais comum para administrar a alocação da memória real aos vários processos em execução sob controle do
kernel do sistema operacional:
demand paging.
Address translation
Pois bem. Para nossa primeira parte vamos precisar, assim como no caso do
compartilhamento do tempo do processador, de uma mãozinha do
hardware (e/ou do microcódigo) do processador. Este auxílio vem na forma da automação do processo de
address translation, que calcula o endereço real de memória correspondente ao endereço virtual de uma instrução ou operando de instrução (e, em princípio, todas as referências a endereços de instrução ou de operandos de instrução são considerados virtuais).
O espaço de enderaçamento (
address space) virtual, conforme visto pelos programas de aplicação, é um bloco contínuo de bytes de memória, cada byte identiicado por um endereço binário. Para efeito de exemplo vamos supor que estamos trabalhando coom um processador com endereços de memória de 32 bits. Então o espaço de endereçamento visualizado pelos programas de aplicação tem a aparência mostrada na figura abaixo (endereços binários expressos pelos seus equivalentes em hexadecimal).
Este
address space virtual é dividido logicamente em páginas (
pages) de tamanho fixo. No nosso caso de exemplo vamos supor que cada página tenha 4K bytes de tamanho. Então a visão lógica do
address space virtual repartido em páginas fica como mostrado na próxima figura.
Então podemos ver que um endereço virtual tem uma estrutura lógica, com os 12 bits menos significativos (correspondentes aos 3 dígitos hexadecimais menos significativos) representando o
deslocamento (
displacement) em relação ao início da página, e com os 20 bits mais significativos (os 5 dígitos hexadecimais mais significativos) identificando o
número da página (
page number).
Por questões de ordem prática (minimizar a quantidade de memória usada pelo
kernel para representar o mapa da memória virtual, que tende a ser uma tabela esparsa), a maioria dos processadores inclui mais um degrau no processo de address translation, considerando o número da página dividido logicamente em duas partes: número do segmento (
segment number) e número da página. Assumindo que, no nosso caso de exemplo, o número da página tenha 12 bits e o número do segmento tenha 8 bits, a estrutura lógica do nosso endereço virtua de exemplo será da seguinte forma:
A memória real (aquela que está fisicamente instalada na máquina e que, geralmente, é bem menor que o address space virtual - 4G bytes no nosso exemplo) também é dividida logicamente em
frames (molduras) com o mesmo tamanho das páginas do address space virtual (4K bytes no nosso caso de exemplo).
O objetivo desta estruturação lógica é, obviamente, permitir que haja um "descasamento" entre a localização física real de um byte na memória e a sua localização lógica do ponto de vista do programa de aplicação, e que esta localização física possa ser modificada, mesmo durante a execução do programa.
Para isto o kernel mantém uma tabela inicial chamada
tabela de segmentos (
segment table) cuja localização (
segment table address) é armazenada em um local específico da memória real acessado pelo mecanismo de
address translation do hardware. Cada entrada da
segment table contém o endereço do início da
tabela de páginas (
page table) associada àquele segmento do
address space virtual. No jargão técnico de programação o conteúdo de cada entrada na segment table é denominado um
ponteiro (
pointer) para a localização da
page table associada ao segmento. No nosso caso de exemplo cada entrada da
segment table tem, portanto, 4 bytes (32 bits) de tamanho.
Cada entrada de uma
page table, por sua vez, contém o
número do frame (
frame number) - com 20 bits no nosso caso de exemplo - onde aquela página virtual está fisicamente armazenada. Cada entrada nas
page tables tem de acomodar, além do
frame number, mais três bits de controle. Então, arredondando para um número inteiro de bytes, no nosso caso exemplo o tamanho de uma entrada na
page table é de: 20 bits do
frame number + 3 bits de controle + 1 bit de arredondamento = 24 bits (3 bytes). A figura abaixo representa esquematicamente estas estruturas de dados criadas e mantidas pelo
kernel.
Então, vejamos quando e como ocorre o processo de
address translation. O quando é fácil: sempre que é necessário executar um acesso à memória. Isto corresponde às fases de
instruction fetch,
operand fetch,
result store e
load interrupt vector address into program counter, conforme a versão mais recente apresentada no
artigo anterior desta série.
O como é assim. Todo endereço virtual é separado nos seus componentes:
segment number,
page number e
displacement. Com estes componentes, e com os demais dados na segment table e nas page tables, efetua-se o cálculo do endereço real conforme mostrado na figura abaixo
Isto nos mostra como o endereço virtual é usado para calcular o endereço real correspondente, mas nada dissemos, ainda, sobre como gerenciar a alocação dos
frames da memória real aos diversos processos em execução sob controle do
kernel. Este é o papel do algoritmo que veremos a seguir.
Demand paging
Quando o kernel recebe uma requisição para iniciar um processo ele precisa alocar memória para o(s) programa(s) deste novo processo dentro do
address space virtual. Isto é feito alocando-se o número apropriado de páginas virtuais livres contíguas nas
page tables. Isto pode ser feito localizando-se nas
page tabes já criadas entradas com o bit de controle V (
valid) igual a zero, significando que aquelas páginas estão inválidas (portanto livres); ou então podem ser acrescentadas novas entradas na
segment table (até o limite do tamanho do
address space virtual) e suas respectivas
page tables. Em qualquer caso, a partir deste momento estas páginas são consideradas válidas (em uso), e os seus bits V são tornados iguais a 1.
Depois é feita a associação dos frames da memória real às páginas da memória virtual. Para isto o kernel mantém uma lista dos frames livres, conhecida como
free list. Para cada página virtual alocada é retirada uma entrada da
free list, o seu
frame number é colocado na entrada correspondente da
page table e o conteúdo da página, caso exista, é copiado para a memória real e para um arquivo externo de baixa latência de acesso (tipicamente em disco magnético) conhecido como
arquivo de páginas (
page file)
Durante o processo de alocação da memória real pode acontecer de não haver entradas suficientes na
free list para satisfazer à necessidade de alocação do novo processo. Esta é uma das situações onde ocorre uma
falta de página (
page fault). A outra situação onde isto pode ocorrer é durante a sequência normal de execução dos processos, como veremos adiante.
Para solucionar a falta de página o
kernel tem que fazer o "reabastecimento" da
free list (
free list replenishment). Antes de explicar como isto é feito temos que entender o significado e a utilização dos outros dois bits de controle (R e C) nas entradas das
page tables.
Toda vez que ocorre uma referência (
fetch) a uma instrução ou a um operando contido em uma página, então o seu bit R (
reference) é ligado (tornado igual a 1). Periodicamente o
kernel desliga (torna iguais a zero) os bits R de todas as páginas. Desta forma páginas que tenham o bit R desligado são páginas que não sofreram referência pelo seu processo pelo menos desde a últia vez em que todos os bits R foram desligados pelo
kernel.
Toda vez que ocorre uma alteração (
store) do conteúdo de uma página então o kernel liga o seu bit C (
change) para indicar que o conteúdo desta página na memória real não é mais igual à sua cópia armazenada no
page file. Este bit é desligado sempre que uma página é carregada em um
frame de memória real, na alocação inícial dos processos ou na solução do segundo tipo de ocorrência dos
page faults.
Assim a estratégia para localizar páginas favoráveis para reabastecer a
free list é:
- Liberar (desligando o bit V) primeiro as páginas que tiverem o bit R igual a zero (não referenciadas recentemente) e o bit C igual a zero (não modificadas desde a sua carga na memória real). Como a cópia destas páginas no page file ainda é válida, elas podem ser reaproveitadas sumariamente;
- Se ainda forem necessárias mais páginas que as recuperadas pelo passo anterior, a próxima opção é liberar as páginas que tenham R=0 e C=1. Neste caso antes de reaproveitar o frame é necessário atualizar a cópia da página no page file, porque ela já sofreu alterações;
- Caso sejam necessárias mais páginas ainda, a última opção (e a mais danosa à performance) é selecionar páginas com R=1 e C=1, atualizando a cópia da página no page file antes do reaproveitamento do frame.
Repare que as páginas liberadas desta forma pertencem a processos ativos. Portanto é provável que, em algum momento futuro, um processo tente acessar uma de sua páginas e ela tenha sido liberada (esteja com o bit V igual a zero). Este é o segundo caso pissível de ocorrência de
page fault. Só que, neste caso, só é necessário encontrar um
frame livre para acomodar a página faltante. Se a
free list estiver vazia então o
frame para acomodar a página faltante é selecionado com a mesma estratégia descrita acima.
Porque este algoritmo funciona? Desde que o volume de operações de I/O sobre o
page file - conhecidas simplesmente como
paging, ou
page-in e
page-out - não seja muito elevado, então o fato observado experiementalmente é que apenas as páginas mais referenciadas de cada processo (conhecidas como o
active page set do processo) tendem a ficar na memória real. Claro que o ideal é que o sistema não tenha que fazer
paging. Como isto raramente é viável economicamente (embora o preço decrescente dos chips de memória estejam alterando isto), um dos fatores críticos de performance do sistema é determinar até que ponto é tolerável a ocorrência de
paging.
Múltiplos address spaces virtuais e compartilhamento de código
Para terminar este assunto só precisamos abordar dois detalhes.
O primeiro é justamente o que viabiliza a construção de sistemas operacionais onde cada um dos seus "processos" é um ambiente computacional virtual completo. Para isso o que precisamos, essencialmente, é permitir que cada processo acredite ter um
address space virtual inteiro só para ele. Para conseguir isso basta criar uma
segment table (e
page tables associadas) para cada processo, e adaptar o cálculo de
address translation a este fato.
O segundo detalhe é que neste tipo de ambiente é muito fácil fazer que múltiplos processos compartilhem segmentos da memória real entre eles. Basta fazer com que as respectivas entradas das
segment tables de cada processo apontem para o mesmo conjunto de
page tables, ou que entradas de page table de cada processo referenciem o mesmo
frame number. Isto é especialmente útil se o sistema tive que executar instâncias de um mesmo programa em múltiplos processos distintos. Neste caso alocam-se páginas distintas para acomodar os operandos de cada instância, enquanto as instruções do programa podem ser mantidas em uma única instância física, mas referenciada como instâncias distintas nas
segment e
page tables dos processos.
Por ora é só. A menos que alguém tenha algum pedido específico, encerro esta série de artigos sobre sistemas de computação por aqui.
