Quantas falhas de página este programa precisa?

Question

Conceitos do sistema operacional diz

Let’s look at a contrived but informative example. Assume that pages are 128 words in size. Consider a C program whose function is to initialize to 0 each element of a 128-by-128 array. The following code is typical:

int i, j;
int[128][128] data;
for (j = 0; j < 128; j++)
for (i = 0; i < 128; i++)
data[i][j] = 0;

Notice that the array is stored row major; that is, the array is stored data[0][0], data[0][1], · · ·, data[0][127], data[1][0], data[1][1], · · ·, data[127][127]. For pages of 128 words, each row takes one page. Thus, the preceding code zeros one word in each page, then another word in each page, and so on. If the operating system allocates fewer than 128 frames to the entire program, then its execution will result in 128 × 128 = 16,384 page faults.

A frase em destaque significa que, ao inicializar cada elemento da matriz, ocorre uma falha de página e, após a substituição da página e a inicialização do elemento, a página é imediatamente removida da RAM?

"o sistema operacional aloca menos de 128 quadros para todo o programa" não significa necessariamente que "o sistema operacional aloca um único quadro a todo o programa". Então, por que o texto está tão certo de que a página mais recente é movida para fora da RAM imediatamente após ser acessada?

Suponha que o SO aloque "n", que é menor que 128, quadros para o programa. É possível manter apenas páginas "n-1", ou seja, linhas na RAM, e usar a página restante para todas as falhas e substituições de página? Assim, o número total de falhas de página pode ser reduzido de 128 * 128 para (n-1) + (128- (n-1)) * 128?

    

Answer 1

Then why is the text so sure that the most recent page is moved out of RAM immediately after being accessed?

Normalmente, será a página acessada pelo menos recentemente que será expulsa, mas isso leva ao comportamento patológico descrito. Na primeira vez através do loop interno, os primeiros quadros n são paginados; então, quando a página n + 1 precisa ser paginada, a página 1 é paginada, o que garante que todas as páginas precisem ser paginadas em todas as etapas o loop.

No entanto, esse cenário é realmente improvável. Se o sistema está totalmente carente de RAM (físico e swap), o kernel irá matar um programa para liberar alguma memória; dado o comportamento do programa de teste, é improvável que seja o candidato. Se o sistema for apenas carente de RAM física, o kernel trocará páginas ou reduzirá seus caches; se trocar páginas, é improvável que ele segmente o programa de teste. Em ambos os casos, o programa de teste terá RAM suficiente para caber em seu conjunto de trabalho. Se você tentar de alguma forma privar o programa de teste apenas (por exemplo, aumentando seu conjunto de trabalho para dominar a memória do sistema), é mais provável, na prática, vê-lo ser morto com um SIGSEGV do que você verá continuamente o seu conjunto de trabalho dentro e fora. (Isso é bom, é um experimento de pensamento em um livro de texto. Aprenda os princípios resultantes, não tente necessariamente aplicar o exemplo na prática).

Can it just keep "n-1" pages i.e. rows in RAM, and use the remaining one page for all the page faults and replacements?

poderia , mas seria incomum para o sistema fazer isso; Como o sistema saberá como serão os futuros padrões de acesso à memória? De modo geral, você verá um despejo de LRU, portanto, o loop exibirá um comportamento patológico conforme descrito acima.

Se você quiser brincar com isso, corrija o programa para que ele corresponda ao tamanho de 4KB de uma página (como usado no x86; suponho que o Linux esteja em x86 de 64 bits aqui) e, na verdade, compile:

int main(int argc, char **argv) {
  int i, j;
  int data[128][1024];
  for (j = 0; j < 1024; j++)
    for (i = 0; i < 128; i++)
      data[i][j] = 0;
}

Em seguida, execute-o usando /usr/bin/time , que mostrará o número de falhas de página:

0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 1612maxresident)k
0inputs+0outputs (0major+180minor)pagefaults 0swaps

Esse tipo de manipulação de matriz causará mais problemas com despejos de linha de cache do que com falhas de página na prática.