Сведите к минимуму количество ошибок страниц за счет обмена шлейфом

Предположим, что размер страницы составляет 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;

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


operating-system memory-management page-fault
person HARUN SASMAZ    schedule 06.05.2020    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

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 просто работает; Я уверен, что ты справишься намного лучше.

person mevets    schedule 07.05.2020
comment
Что такое значение NWORKING_SET? Это предопределено в библиотеке? - person HARUN SASMAZ; 07.05.2020
comment
Я думаю, вы сказали 512 в своем исходном посте. Рабочий набор - это разговорное название количества активных страниц, используемых процессом. Опять же, вы можете сделать намного лучше, чем этот небольшой набросок. - person mevets; 07.05.2020

arrow_upward
0
arrow_downward

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

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

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

person Brendan    schedule 07.05.2020