Система виртуальной памяти, таблица страниц и TLB

Question

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

Рассмотрим следующую программу на C:

int X[N];
int i;
int step = M; // M is some predefined constant
for (i = 0; i < N; i += step) X[i] = X[i] + 1;

Если эта программа запускается на компьютере с размером страницы 4 КБ и TLB из 64 записей, то какие значения M и N приведут к пропуску TLB при каждом выполнении внутреннего цикла?

Может кто-нибудь дать мне несколько советов, как мне решить эту проблему?

Answer 1

Это просто. Сначала вы должны понять, что именно делает TLB? Подсказка в том, что это кеш, который поможет перевести virtual address в physical address, Итак, вы знаете, что размер страницы составляет 4 Кбайт. Так что если есть массив, скажем, бесконечной длины. Вы обращаетесь к нему от 0 до бесконечности в цикле for. Первый доступ к массиву X[0] вызовет промах TLB и загрузит первый TLB. тогда для следующих 4095 обращений он не будет пропущен, поскольку он присутствует в TLB(помните, что это потому, что размер страницы составляет 4096 = 4 КБ). Тогда следующий адрес - X[4096], что приведет к пропуску TLB. Таким образом, вы видите, что для каждых 4096 приращений адресов у вас будет пропуск TLB. Так что мы уверены, что M = 4096/sizeof(int),

Теперь вы также знаете, что у вас есть кэш TLB с 64 записями. Таким образом, после загрузки 64 записей TLB у вас будет полный TLB. Чтобы загрузить 65-ю запись, вам придется удалить первую запись. (обратите внимание, что могут быть разные механизмы замещения. Здесь мы предполагаем, что это какой-то простой механизм). Таким образом, после загрузки 65-й записи первая запись при доступе к X[0] была удалена. Поэтому, если вы попытаетесь получить доступ к X[0], произойдет промах TLB, заменив запись, необходимую для X[4096], и так далее. Так что вам нужен размер 64 * 4096 = 256 KBytes, чтобы полностью использовать кэш TLB. Однако вы хотите иметь промах TLB для каждого шага. Таким образом, для TLB-кэша с 64 записями вам нужен размер массива, который будет эквивалентен 65 записям. таким образом N = 65 * 4096 / sizeof(int),

Надеюсь, что это дает некоторые советы!

Answer 2

Промах TLB происходит, когда виртуальный адрес страницы отсутствует в TLB.

Имея TLB из 64 записей, если вы предварительно полностью заполнили его виртуальными адресами 0*4096, 1 ​​*4096, 2*4096, ..., 63*4096 (вы заполняете его, обращаясь к памяти на соответствующих страницах), а затем запросить доступ по виртуальному адресу от 64 * 4096 до 64*4096+4095, этот доступ вызовет пропадание TLB (поскольку 64 * 4096 еще не находится в TLB).

Затем, если запись, в которой теперь хранится адрес 64 * 4096 (после пропуска TLB, выселение одной из 64 записей и ее замена виртуальным адресом 64 * 4096 и соответствующим ему физическим адресом) ранее имел виртуальный адрес 0 * 4096, то доступ к памяти по виртуальному адресу от 0 до 4095 вызовет еще одну ошибку TLB (поскольку запись для виртуального адреса 0 * 4096 была исключена из TLB и заменена записью для VA 64*4096).

Основываясь на этом поведении TLB, вы должны придумать M а также N это будет соответствовать требованию.