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.
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.
Nenhum comentário:
Postar um comentário