Какая структура данных обычно используется для реализации таблицы фреймов?

Question

Мне нужно реализовать таблицу кадров для проекта операционных систем, чтобы отслеживать, какие кадры в физической памяти (не страницах виртуальной памяти) используются или свободны.Одна из важных вещей - это выбор структуры данных для таблицы фреймов.По вашему опыту, как обычно реализуются таблицы фреймов с точки зрения структуры данных, которую они используют?В моем случае записи должны содержать указатели на кадры в физической памяти.Вы бы порекомендовали использовать массив, список, хэш-таблицу или что-то еще целиком?

Answer 1

Как в Windows, так и в Linux используется массив структур, где каждый элемент массива описывает фрейм страницы физического адресного пространства.Таким образом, если всего имеется 128 страниц, то массив будет содержать 128 структур.

В Windows этот массив называется базой данных PFN.Каждая структура описывает состояние фрейма (распределенного или свободного) и обычно включает в себя один или несколько физических адресов тех записей таблицы страниц, которые сопоставляются с ним.Чтобы сделать поиск свободных кадров более эффективным, чем просто линейное сканирование массива, каждый элемент содержит указатель на следующий элемент того же состояния.Таким образом, в основном есть связанный список свободных фреймов.

В Linux массив называется mem_map , и для каждого узла NUMA в системе существует один такой массив.