Сведите к минимуму количество ошибок страниц на l oop обмен - PullRequest
Новая
       66

Сведите к минимуму количество ошибок страниц на l oop обмен

0 голосов
/ 06 мая 2020

Предположим, что размер страницы составляет 1024 слова, и каждая строка хранится на одной странице. Если ОС выделяет для программы 512 кадров и использует алгоритм замены страниц LRU, каково будет количество ошибок страниц в следующих программах? 

int A[][] = new int[1024][1024];

Program 1:
for (j = 0; j < A.length; j++)
    for (i = 0; i < A.length; i++) 
        A[i][j] = 0;

Program 2:
for (i = 0; i < A.length; i++)
    for(j = 0; j < A.length; j++) 
        A[i][j] = 0;

Я предполагаю, что перенос страниц по строкам лучше, чем по столбцам, однако я не могу поддержать свое утверждение. Можете ли вы помочь мне подсчитать количество ошибок страниц?

Ответы [ 2 ]

0 голосов
/ 07 мая 2020

Для второй программы; ЦП обращается к первым int в строке, вызывая сбой страницы, затем обращается к другим int в строке, когда страница уже присутствует. Это означает, что (если строки начинаются на границах страницы) вы получите ошибку страницы для каждой строки, плюс, вероятно, один при первом запуске кода программы, плюс, возможно, еще один, когда стек программы используется впервые (и еще один, если массив не выравнивается по границе страницы); что, вероятно, срабатывает до 1026 или 1027 ошибок страниц.

Для первой программы; CPU обращается к первому int в строке, вызывая отказ страницы; но к тому времени, когда он обращается ко второму int в той же строке, страница была исключена (стала «наименее использованной» и заменена другой страницей). Это означает, что при доступе к массиву вы получите 1024 * 1024 страниц с ошибками (плюс одна для кода программы, стека и т. Д. c). Это, вероятно, сработает до 1048578 ошибок страниц (если начало массива выровнено по «sizeof(int)»).

Однако; все это предполагает, что компилятор ничего не смог оптимизировать. На самом деле весьма вероятно, что любой компилятор, который стоит использовать, преобразовал бы обе программы во что-то более похожее на "memset(array, 0, sizeof(int)*1024*1024);", которое выполняет последовательные записи (возможно, записывает несколько int за одну большую запись, если базовый процессор поддерживает большие записи Это означает, что обе программы, вероятно, вызовут 1026 или 1027 страниц с ошибками.

0 голосов
/ 07 мая 2020

Один из способов ответить на этот вопрос - симуляция. Вы можете изменить свои циклы, чтобы выводить адрес назначения, а не устанавливать его на ноль: 

printf("%p\n", &A[i][j]);

Затем напишите вторую программу, которая имитирует размещение страницы, чтобы она выполняла что-то вроде: 

    uintptr_t h;
    uintptr_t work[NWORKING_SET] = {0};
    int lru = 0;
    int fault = 0;
    while (gethex(&h)) {
        h /= pagesize;
        int i;
        for (i = 0; i < NWORKING_SET && work[i] != h; i++) {
        }
        if (i == NWORKING_SET) {
              work[lru] = h;
              fault++;
              lru = (lru+1) % NWORKING_SET;
        }
   }
   printf("%d\n", fault);

Имея эту программу, вы можете попробовать несколько стратегий обхода. PS: мой lru просто работает; Я уверен, что у тебя получится намного лучше.

...