Вычисление количества ошибок страницы для 2-го массива

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

Вопрос:

Рассмотрим двумерный массив A: int A [] [] = new int [100] [100]; где A [0] [0] находится в местоположении 200 в системе с постраничной памятью со страницами размером 200. Небольшой процесс, который манипулирует матрицей, находится на странице 0 (местоположение от 0 до 199). Таким образом, каждый выбор команды будет со страницы 0. Для двух страничных фреймов количество ошибок страницы генерируется следующими циклами инициализации массива, используя замену LRU и предполагая, что первый кадр страницы содержит процесс, а другой изначально пуст?

А:

for (int j=0;j<100;j++)
   for (int i=0; i<100; i++)
     A[i][j] = 0;

В:

for(int i=0; i<100; i++)
  for (int j=0; j<100; j++)
      A[i][j] = 0;

Правильный ответ: a: 100 x 50 = 5000 b: 50

Я несколько понимаю первую часть. Всего 50 страниц. (10000/200 = 50), и каждый раз, когда j изменяется, возникает ошибка страницы. В общей сложности 100 ошибок страницы... но почему это умножается на 50? и почему вторая - 50?

Спасибо!!

Ответ 1

Предположим, что ваши системы выделили два фрейма для вашего процесса, так что 200 * sizeof(int) матрицы можно сохранить в памяти за раз. И распределение для матрицы происходит в Строчный порядок заказов.

В первом цикле A:

for (int j=0;j<100;j++)
   for (int i=0; i<100; i++)
     A[i][j] = 0;

ячейки памяти доступа к контуру для матричного столбца, такие как:

A[0][0], A[2][0], A[3][0], ...A[0][2], A[0][3], A[0][4], ......
  ^        ^         ^   
      row changes,

На каждой итерации Строка изменяется, а выделение находится в строке, и каждая строка занимает одну страницу. поэтому код A приведет к сбою страницы для каждого альтернативного доступа A [i] [j], так что общее количество ошибок страницы равно 100 * 100/2) = 5000.

Где второй код B::

for(int i=0; i<100; i++)
  for (int j=0; j<100; j++)
      A[i][j] = 0;

ячейки памяти доступа к контуру для матричной строки на каждой итерации, например:

A[0][0], A[0][5], A[0][6],...,A[1][0], A[1][7], A[1][8],...,A[2][0], A[2][9],
     ^        ^        ^  
  column changes, row are same

Доступ к строке мудрый (изменения столбцов при чтении строки чтения изменяются только после 100 просмотров). Одна строка загружается со временем, поэтому ошибка страницы возникает при изменении строки (для внешнего цикла) и для каждого доступа к альтернативной строке ошибка страницы происходит так, что количество ошибок страницы = 100/2 = 50.

мы можем понять это другими способами:
В строке major, Number of times index changes, нам нужна новая страница для доступа, потому что количество страниц мало, это ошибка страницы при каждом изменении альтернативного индекса в первом индексе строки цикла. 100 * 100 раз, где, как в изменении индекса строки цикла B 100 раз, так что повреждение ошибки страницы в A/B = 100 * 100/100 = 100, и если число ошибок страницы происходит в = 50,00, то в B количество ошибок страницы = 50,00/100 = 50.

Аналогичным образом вы можете рассчитать количество ошибок страниц для Order-major order и потому, что матрица имеет равное количество строк и результат cols будут одинаковыми,

Аналогичный пример приведен в моей книге:
Загрузить pdf: книга операционной системы Galvin Прочтите главу 9: Раздел виртуальной памяти: 9.9.5. Структура программы.

Ответ 2

Таким образом, всего 50 страниц в массиве 2-х, хранящихся либо по строкам, либо по столбцу.

Если вы храните страницы по строкам и получаете доступ к ним по строкам, вы снова и снова будете обращаться к одной и той же странице до тех пор, пока не перейдете на следующую страницу, так что вы переключаете страницы (вызывая ошибку страницы) всего 50 раз потому что там 50 страниц.

Если вы храните страницы по строкам и получаете доступ к ним по столбцам (или тире), вы получаете элемент с одной страницы, переключаете страницы, получаете один с другой страницы, переключаете страницы и т.д. все еще проходит через 50 страниц, но вы переключаете 100 раз для каждой страницы.

Изображение вашего чтения. Если вы читаете по одной странице за раз, вы можете перевернуть страницу один раз для каждой страницы. Если вы прочтете одну строку на каждой странице, начните сначала и прочитайте вторую строку, третью строку и т.д., Вам придется перелистывать всю бумагу снова и снова, для каждой строки на странице (при условии, что все страницы имеют одинаковый номер таких строк, как массив)... каждый раз, когда вы поворачиваете страницу, это ошибка страницы.

Ответ 3

Давайте посмотрим на надуманный, но информативный пример. Предположим, что страницы 128 слов в размере. Рассмотрим программу C, функция которой должна инициализироваться до 0 каждый элемент массива 128 на 128. Следующий код типичен:

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

Ответ 4

Ключ здесь - посмотреть, как выглядят все обращения к массиву при чтении с адресов линейной памяти. Для того, чтобы ответ имел смысл, необходимо принять строчный (C) порядок. Проблема также оставила единицы, которые мы будем считать байтами (поэтому A должно быть проведено в 1-байтных типах).

char *B = &(A[0][0]); (memory address 200)

Доступ к A[i][j] теперь эквивалентен B[i*100 + j] или *(200 + i*100+j) (порядок строк). В память могут поместиться две страницы. Один берется программой (байты 0-199 - также конвенция С). Другой - для доступа к A, который охватывает 100 * 100 байт /(200 байт/страница) = 50 страниц.

Так как 0-199 всегда находится в памяти, другая страница будет адресовать n * 200 to (n + 1) * 200-1, где n - некоторое целое число, соответствующее 2 строкам A за раз.

Наконец, при ошибке страницы наименее недавно использованный алгоритм (LRU) просто прочитал инструкцию со страницы 0-199, поэтому всегда удалял бы страницу, содержащую старую часть A, для чтения новой части A ( когда n изменяется, каждые 2 строки).

Итак, вы можете легко понять, что происходит, читая строки из 100x100-матрицы - каждые две строки меняют страницу, и это повторяется 100x во внешнем цикле (слева направо в строке). Это приводит к 100-кратным ошибкам страницы.

В реальном мире вы можете отслеживать ошибки страниц с помощью команд Linux или getrusage.