Memória virtual

Na ciência da computação, o mecanismo de memória virtual foi desenvolvido na década de 1960 . Baseia-se no uso de tradução instantânea dos endereços (virtuais) vistos pelo software, em endereços físicos na RAM . A memória virtual permite:

Histórico

O artigo histórico de James Kilburn de 1962 descreve o primeiro computador com um sistema de gerenciamento de memória virtual paginado que usa um tambor como uma extensão da memória do núcleo de ferrite  : o Atlas .

Hoje, todos os computadores possuem um mecanismo de gerenciamento de memória virtual, exceto alguns supercomputadores ou sistemas de bordo em tempo real.

Memória virtual paginada

O princípio é o seguinte:

A tabela de páginas é indexada pelo número da página. Cada linha é chamada de “entrada na tabela de páginas ” ( entrada da tabela de páginas , abreviado PTE) e contém o número do quadro. Uma vez que a tabela de páginas pode estar localizada em qualquer lugar da memória, um registro especial (PTBR para Registrador Base da Tabela de Páginas ) mantém seu endereço.

Na prática, o mecanismo de tradução faz parte de um circuito eletrônico denominado MMU ( memory management unit ) que também contém parte da tabela de páginas, armazenada em uma memória associativa formada por registradores rápidos. Isso evita ter que consultar a tabela de páginas (na memória) para cada acesso à memória.

Aqui está um exemplo real de uma máquina cujo processador gera endereços virtuais de 32 bits, podendo acessar 4  GiB de memória. O tamanho da página é 4  KB . Deduz-se daí que o campo de deslocamento ocupa os 12  bits menos significativos e o campo de número de página os 20 bits mais significativos.

Observe a presença de um campo especial pertencente a cada PTE. Para simplificar, reduzimos a largura deste campo para um bit: o bit de validade . Se for 0, significa que o número do quadro é inválido. É necessário, portanto, adquirir uma técnica que possibilite a atualização deste PTE para torná-lo válido.

Podem ocorrer três casos:

  1. A entrada é válida: substitui o número da página para formar o endereço físico.
  2. A entrada na tabela da página é inválida. Neste caso, você deve encontrar um quadro livre na RAM e colocar seu número nesta entrada na tabela de páginas.
  3. A entrada na tabela de páginas é válida, mas corresponde a um endereço na memória de massa onde o conteúdo do quadro está localizado. Um mecanismo terá que trazer de volta esses dados para colocá-los na RAM.

Alocação sob demanda

Nos dois últimos casos, uma interrupção - chamada de página padrão (ou às vezes falha de página , tradução de falha de página em inglês ) é gerada pelo material e dá a mão ao sistema operacional. Este é o responsável por encontrar um frame disponível na memória principal para alocá-lo ao processo responsável por esta falha de página, e possivelmente recarregar o conteúdo deste frame com o conteúdo salvo na memória de massa (atualmente o disco rígido de um área chamada área de troca ou troca ).

Pode não haver mais frames livres na memória principal: esta está então 100% ocupada. Nesse caso, um algoritmo de paginação é responsável por escolher uma página de “vítima”. Esta página será imediatamente reatribuída ao processo de solicitação ou primeiro será salva no disco rígido e a entrada na tabela de páginas que se refere a ela será atualizada. A página da vítima pode muito bem pertencer ao processo que está com falta de espaço.

Abaixo estão listados alguns exemplos de algoritmos. A primeira linha corresponde à cadeia de referências , ou seja, a ordem em que o processo irá acessar as páginas. Presume-se que a memória principal seja composta por três quadros . O quadro da vítima aparecerá sublinhado. As falhas de página inicial não são contadas (são idênticas em número, independentemente do algoritmo escolhido).

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 2 7
0 0 0 0 4 0 0 0
1 1 3 3 3 1 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 4 4 4 0 0 0 7 7 7
0 0 0 3 3 3 2 2 2 1 1 1 0 0
1 1 1 0 0 0 3 3 3 2 2 2 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 4 4 4 0 1 1 1
0 0 0 0 0 0 3 3 3 0 0
1 1 3 3 2 2 2 2 2 7

Pode ser relativamente fácil encontrar casos patológicos que tornam um algoritmo inutilizável. Por exemplo, para o algoritmo LRU, este seria um programa que usa 5 páginas em um loop em uma máquina que possui apenas 4 quadros '. Ele usará primeiro os 4 primeiros quadros sequencialmente (1, 2, 3, 4), em seguida, ocorrerá uma falha de página e é a página 1, a mais antiga carregada, que será a vítima. As páginas usadas agora são (5, 2, 3, 4). Uma vez que o programa entra em loop, ele precisa da página 1 (continuação da página 5). Desta vez, a página da vítima é a página 2, substituída por 1: (5, 1, 3, 4), então (5, 1, 2, 4), (5, 1, 2, 3), etc. Uma falha de página é gerada em cada iteração ...

Anomalia de Belady

Intuitivamente, aumentar o número de quadros de página (ou seja, aumentar a memória principal) deve reduzir o número de falhas de página.

A anomalia de Belady (1970) é um contra-exemplo que mostra que isso não é absolutamente verdadeiro com o algoritmo FIFO , de fato o leitor poderá verificar por si mesmo que a sequência de referências (3, 2, 1, 0, 3, 2 , 4, 3, 2, 1, 0, 4) leva a

Nota  : o alcance desta curiosidade não deve ser exagerado. Certamente mostra que o algoritmo FIFO em geral não tem uma propriedade que se esperaria (adicionar memória reduz as falhas de página), mas não mostra que não a possui em média . E, de qualquer forma, o algoritmo FIFO nunca é usado para substituição de página.

Além disso, pode-se demonstrar que determinados algoritmos de substituição de página ( LRU por exemplo) não estão sujeitos a este tipo de anomalia.

Método de alocação em um sistema multiprogramado

Os métodos de seleção da página vítima mencionados acima podem ser aplicados às páginas pertencentes a um processo (fala-se então de "alocação local"), ou a todas as páginas e, portanto, a toda a memória (neste caso a técnica de alocação é dito ser “global”).

Em um sistema de alocação global, o tempo de execução de um processo pode variar muito de instância para instância porque o número de falhas de página não depende do próprio processo. Por outro lado, esse sistema permite que o número de executivos alocados em um processo evolua.

Compartilhando memória em um sistema paginado

O diagrama a seguir mostra três processos em execução, por exemplo, um editor de texto chamado Ed. As três instâncias estão todas localizadas nos mesmos endereços virtuais (1, 2, 3, 4, 5). Este programa utiliza duas áreas de memória distintas: as páginas que contêm o código, ou seja, as instruções que descrevem o programa, e a área de dados, o arquivo que está sendo editado. É suficiente manter as mesmas entradas na tabela de páginas para as três instâncias para compartilhar a área de código. Por outro lado, as entradas correspondentes às páginas de dados são distintas.

Proteção

Algumas proteções de bits são adicionadas a cada entrada na tabela de páginas. Portanto, podemos distinguir facilmente entre as páginas alocadas para o kernel, somente leitura, etc. Veja o exemplo abaixo.

Eficiência

Existem três problemas principais:

  1. O tamanho da tabela de páginas: para uma arquitetura em que 20 bits são reservados para o número da página, a tabela ocupará um mínimo de 4  Mio de memória (2 20 = 1 Mio de PTE, cada PTE tendo um comprimento de 4 bytes). Este problema é resolvido usando várias tabelas de página: o campo de número de página será dividido em vários, cada um indicando uma mudança para a tabela de nível mais baixo. O VAX e os Pentiums suportam dois níveis, o SPARC três, o Motorola 680x0 quatro… Você também pode segmentar a tabela de páginas.
  2. Tempo de acesso: estando a tabela de páginas localizada na memória, seriam necessários dois acessos à memória por solicitação do processador. Para superar esse problema, as entradas usadas com mais freqüência são mantidas em uma memória associativa ( memória cache ) chamada TLB para Translation Lookaside Buffer . Cada endereço virtual proveniente do processador é procurado no TLB; se houver uma correspondência, a entrada TLB é usada, caso contrário, uma interrupção é disparada e o TLB deve ser atualizado pela entrada da tabela de página armazenada na memória antes que a instrução infratora seja reiniciada. Todos os microprocessadores atuais possuem um TLB.
  3. Fenômeno de thrashing : quanto mais aumenta a taxa de multiprogramação , menos páginas cada processo é alocado. Depois de um tempo, o sistema fica sobrecarregado porque muitas falhas de página são geradas. O fenômeno do lixo aparece sempre que, em um sistema de armazenamento hierárquico, um dos níveis está sobrecarregado. Esse é o caso, por exemplo, se a memória cache for muito pequena. Nesse ponto, o incessante vaivém de dados para cima e para baixo na hierarquia reduzirá muito o desempenho do computador. É possível reduzir os efeitos desse comportamento adicionando recursos de hardware (adicionando memória), reduzindo a taxa de multiprogramação ou modificando a prioridade dos processos.

Princípio da localidade

O comportamento dos programas não é caótico: o programa é iniciado, ele chama funções (ou partes do código) que por sua vez chamam outras, etc. Cada uma dessas chamadas define uma região. É provável que o programa passe muito tempo sendo executado em algumas regiões: este é o princípio da localidade. O mesmo princípio pode ser aplicado a páginas que contêm dados.

Em outras palavras, um programa freqüentemente acessa um pequeno conjunto de páginas, e esse conjunto de páginas muda lentamente com o tempo.

Se conseguirmos manter na memória esses espaços frequentemente acessados, reduzimos as chances de ver um programa começar a jogar na lixeira , ou seja, reivindicar páginas que acabaram de ser removidas dele.

O conjunto de  trabalho: espaço de trabalho

Podemos definir um parâmetro, Δ, que é o número de referências às páginas acessadas pelo processo durante um determinado período de tempo. A figura abaixo mostra o valor do espaço de trabalho em dois momentos diferentes:

O valor de Δ deve ser escolhido com cuidado: muito pequeno não cobre o espaço nominal de trabalho do processo; muito grande inclui páginas desnecessárias. Se Δ for igual ao infinito, ele cobre todo o programa, é claro.

Para um único processo, podemos representar graficamente como a memória é alocada a ele e visualizar os espaços de trabalho:

As “bandejas” são áreas onde não há falha de página: o espaço alocado é grande o suficiente para conter todos os frames de que o processo precisa por um tempo relativamente longo. As falhas de página ocorrem na parte ascendente da transição, enquanto a memória é liberada quando a curva volta para o próximo espaço de trabalho: a zona de equilíbrio.

Cabe ao sistema operacional implementar os algoritmos para que o valor de Δ seja ótimo para que a taxa de multiprogramação e o uso da unidade central sejam maximizados. Em outras palavras: evite jogar no lixo . Se a soma dos espaços de trabalho de cada processo for maior que o número de frames disponíveis, necessariamente haverá colapso.

Prepagination

Uma das vantagens da memória virtual é que ela pode iniciar a execução de um programa assim que sua primeira página de código for carregada na memória. A pré-paginação carregará não apenas a primeira página, mas as próximas, que têm uma probabilidade muito alta de serem acessadas.

Tamanho da página para alguns computadores

Aqui é indicado em bits, o espaço endereçável total, a largura dos campos, o número da página e o deslocamento.
Máquina Espaço endereçável Campos de número de página Campos de "deslocamento"
Atlas 11 9
PDP-10 9 9
IBM-370 13 ou 12 11 ou 12
Pentium Pro 12 ou 20 20 ou 12
Alpha 21064 13 30

Exemplo

Os endereços são codificados em 32  bits (4  GiB de espaço total) O tamanho da página é de 1  KiB (codificado em 10  bits ). As entradas na tabela de páginas são neste formato: 3 3 2 2 2 2 2 1 0 7 3 2 1 0 0 +---+------+-----+---+---+---+------------------------------------------------+ | V | PROT | | N | M | U | NDP | +---+------+-----+---+---+---+------------------------------------------------+

Os campos M, U, N e NDP são válidos apenas se o bit V for 1. Quando V for 0, o campo NDP contém o endereço no disco rígido onde a página está localizada.

O campo PROT deve ser interpretado da seguinte forma (o valor do campo é dado em binário em 4 bits):
Valor Proteção
0000 Sem acesso
1000 Leitura para o kernel
1100 Ler / escrever para o kernel
1010 Leitura de usuário e kernel
1110 Leitura do usuário, leitura / gravação do kernel
1111 Leitura / gravação de usuário e kernel

Bit 24, N ( N oculto), significa que a página não está armazenada em cache e o sistema deve ler ou gravar diretamente de ou para a memória.

O M ( M odificado) bit é modificado pelo hardware se o conteúdo da página é modificado.

O bit U ( U tilisée) indica se a página foi lida ou gravada por um processo. É útil, em associação com os outros, para determinar o Conjunto de Trabalho de um processo (veja acima).

Segmentação

A segmentação fornece uma visão da memória que é mais consistente com a do usuário. Na verdade, este não (ou raramente!) Considera a memória como uma série de páginas, mas sim como espaços, ou regiões, destinadas a um uso particular, por exemplo: o código de um programa, os dados, a pilha, um conjunto de sub-rotinas, módulos, um array, etc. A segmentação reflete essa organização.

Cada objeto lógico será designado por um segmento. Em um segmento, o endereçamento será feito por meio de um deslocamento. O torque (segmento, deslocamento) será traduzido em um endereço de memória por meio de uma tabela de segmento contendo dois campos, limite e base . A base é o endereço inicial do segmento e limita o último endereço do mesmo segmento:

Problema de fragmentação

Os sistemas paginados têm um problema de fragmentação interna : o espaço é desperdiçado no final de uma página. Os sistemas segmentados têm um problema de fragmentação externa  : os espaços entre os segmentos são muito pequenos para acomodar novos fragmentos, de modo que o espaço é desperdiçado.

Ele pode ser recuperado compactando a memória, ou seja, movendo os segmentos - enquanto reflete essas alterações nas tabelas de segmentos - para que fiquem contíguos. No entanto, essa operação é cara.

Compartilhando segmentos

É possível compartilhar segmentos entre processos, conforme mostrado na figura abaixo, onde dois processos Ed1 e Ed2 compartilham o mesmo segmento de código (programa), mas possuem segmentos de dados separados de tamanhos diferentes.

Proteção em um sistema segmentado

Esta proteção será assegurada por bits adicionais acrescentados na tabela de segmentos, da mesma forma que para um sistema paginado.

Exemplo de microprocessadores com arquitetura de memória segmentada

O exemplo mais conhecido é o Intel 8086 e seus quatro registradores:

Os sucessores do 8086 também são segmentados:

Sistemas mistos paginados / segmentados

É possível misturar os dois modos anteriores:

  1. a paginação segmentada onde a tabela de páginas será segmentada. Em outras palavras, o número da página p do par (p, d) do endereço virtual será interpretado como um segmento (s, p '). Este sistema resolve o problema de tamanho da tabela de páginas.
  2. a segmentação paginada , onde cada segmento é numerado. Em outras palavras, o campo de deslocamento d do par (s, d) do endereço virtual será interpretado como um número de página e um deslocamento (p, d ').

Troca

Às vezes, é necessário excluir todas as páginas ou segmentos de um processo da memória principal. Nesse caso, o processo será dito como trocado , e todos os dados pertencentes a ele serão armazenados na memória de massa. Isso pode acontecer para processos inativos longos quando o sistema operacional precisa alocar memória para processos ativos. As páginas ou segmentos de código (programa) nunca serão trocados , mas simplesmente reatribuídos, pois podem ser encontrados no arquivo correspondente ao programa ( o arquivo executável ). Por esse motivo, o sistema operacional proíbe o acesso de gravação a um arquivo executável em uso; simetricamente, não é possível iniciar a execução de um arquivo enquanto ele está aberto para acesso de gravação por outro processo.

Compressão de memória virtual

A compactação de memória virtual pode melhorar o desempenho de um sistema de memória virtual. Essa técnica de gerenciamento de memória virtual usa compactação de dados para reduzir o tamanho ou o número de solicitações de paginação de e para o armazenamento auxiliar.

Em um sistema de compactação de memória virtual, as páginas são compactadas e armazenadas na memória física, normalmente RAM , ou enviadas compactadas para armazenamento auxiliar, como um disco rígido ou SSD . Em qualquer um dos casos, o intervalo de memória virtual cujo conteúdo foi compactado é inacessível, portanto, as tentativas de acessar as páginas compactadas acionam erros de página e invertem o processo de compactação (recuperando o armazenamento auxiliar e descompactando). A área de cobertura dos dados paginados é reduzida pelo processo de compactação e a memória RAM liberada é retornada ao pool de memória física disponível. No caso das páginas compactadas serem mantidas na memória RAM, as páginas compactadas obviamente ocupam menos espaço do que as páginas originais. No caso de as páginas compactadas serem mantidas no armazenamento auxiliar, a memória RAM é totalmente liberada e as operações de escrita e leitura na memória auxiliar são mais rápidas do que se as páginas não tivessem sido compactadas.

Referências

  1. Patente US 5559978

Veja também

Artigos relacionados

Bibliografia