Пишем свою операционную систему. Менеджер физической памяти
Доброго времени суток!
Сегодня в этом выпуске мы напишем реализацию менеджера физической памяти. Его задача - найти N свободных физических страниц, пометить их как занятые и отдать адрес первой. А также обратную операцию - пометка блока физических страниц как свободных. Мне известно 4 различных алгоритма:
1) Стек страниц. Создаётся специальная структура данных - массив физических адресов, количество элементов равно количеству страниц физической памяти. При 32-битном адресе это
будет лишь 1/1024 всей памяти. Когда нужна очередная страница достаётся верхняя страница стека, когда какая-то страница не нужна, она кладётся на верх стека. Это самый быстрый и простой алгоритм, но он имеет существенный недостаток - невозможность выделения блока последовательных страниц. А между тем это очень нужно драйверам - устройства-то не знают ничего про страничную адресацию.
2) Битовая карта страниц. Аналогично битовой карте в ListFS. Битовая карта занимает 1/32768 физической памяти.
Из минусов следует отметить то, что это достаточно медленный вариант, а для оперативной памяти немаловажна скорость выделения (для блоков на жёстком диске такой алгоритм вполне приемлем). К тому же появляются трудности, если память представляет собой не непрерывный блок адресов, а то и вовсе может динамически добавляться.
3) Линейный список регионов памяти. Можно создать массив, в котором будет содержаться начало, конец и тип (занято/свободно) участков памяти. Этот вариант обладает
наибольшей скоростью, но достаточно сложен в реализации - список во время работы системы постоянно меняет свою длину и надо как-то освобождать и выделять память под него самого.
4) Двунаправленный связанный список, располагающийся на свободных страницах памяти. Этот вариант немного медленнее третьего, зато обладает достаточной гибкостью и простотой. Суть в том, что в начале свободного блока физической памяти создаётся структура, в которой есть адрес предыдущего свободного блока, адрес
следующего и размер текущего блока. С помощью temp_map_page мы можем получить доступ к заголовку любого из блоков. Максимальная сложность alloc_phys_pages - O(N) (N - количество разрозненных свободных блоков). free_phys_pages должен не просто помечать блок как свободный, но и дефрагментировать блоки памяти - если перед и/или после свободного блока памяти впритык существует ещё один их следует объединить. Для упрощения задачи можно поддерживать упорядоченность блоков по возрастанию адресов, тогда сложность
free_phys_pages будет так же O(N).
Мы будем использовать последний метод, потому что это разумный компромисс между скоростью, гибкостью и простотой. К тому же не требует дополнительной памяти на свои структуры, что тоже хорошо.
Физический адрес первого свободно блока хранится в переменной free_phys_memory_pointer. Список двунаправленный для упрощения удаления и добавления элементов. Он ещё будет и кольцевым, чтобы не делать лишних проверок на NULL.
В первую очередь опишем структуру заголовка
блока памяти (размер блока будем хранить в страницах, заодно, пусть некорректным физическим адресом будет -1, а не 0):
Теперь можно написать функцию выделения нового блока памяти из списка свободных:
phyaddr alloc_phys_pages(size_t count) {
if (free_page_count < count) return -1;
phyaddr result = -1;
if (free_phys_memory_pointer != -1) {
phyaddr cur_block = free_phys_memory_pointer;
do {
temp_map_page(cur_block);
if (((PhysMemoryBlock*)TEMP_PAGE)->size == count) {
phyaddr next = ((PhysMemoryBlock*)TEMP_PAGE)->next;
phyaddr prev = ((PhysMemoryBlock*)TEMP_PAGE)->prev;
temp_map_page(next);
((PhysMemoryBlock*)TEMP_PAGE)->prev = prev;
temp_map_page(prev);
((PhysMemoryBlock*)TEMP_PAGE)->next = next;
if (cur_block == free_phys_memory_pointer) {
free_phys_memory_pointer = next;
if (cur_block == free_phys_memory_pointer) {
free_phys_memory_pointer = -1;
}
}
result = cur_block;
break;
} else if (((PhysMemoryBlock*)TEMP_PAGE)->size > count) {
((PhysMemoryBlock*)TEMP_PAGE)->size -= count;
result = cur_block + (((PhysMemoryBlock*)TEMP_PAGE)->size << PAGE_OFFSET_BITS);
break;
}
cur_block = ((PhysMemoryBlock*)TEMP_PAGE)->next;
} while (cur_block != free_phys_memory_pointer);
if (result != -1) {
free_page_count -= count;
}
}
return result;
}
Функция работает достаточно просто - если список свободных блоков пуст, либо общий объём свободной памяти меньше нужного, то она тут же возвращает -1, иначе же начинает перебирать все свободные блоки. Если попадается блок, который равен по размеру запрошенному, то его адрес возвращается в качестве результата, а сам блок удаляется из списка (рассматривается вариант, когда это был первый блок в списке, тогда надо изменить free_phys_memory_pointer, а также когда в списке больше не осталось элементов).
Иначе, если блок был больше искомого, от его конца отрезается нужное число страниц и возвращается базовый адрес такого блока. Если в результате поиска блок нужного размера так и не был найден (хотя суммарно все регионы и подходят по размеру, но нет ни одного непрерывного блока нужной длинны), то функция завершается, возвращая -1. Для запросов небольшого количества страниц (чаще всего требуется 1 страница) эта функция вернётся уже после первой итерации цикла поиска.
Функция free_phys_pages сложнее, потому
что её не только нужно вставить блок в нужное место в списке, но и по возможности слить его с другими. Возможно три варианта соседства блоков:
1) Новый блок после другого. Создавать новый блок не нужно, лишь увеличить size предыдущего. 2) Новый блок перед другим. Следует удалить следующий блок, а при создании предыдущего указать size больше. 3) Новый блок окружён двумя. Следует удалить следующих блок, а размер предыдущего увеличить на сумму размеров освобождаемого блока и следующего за ним.
Обработку
этих ситуаций упростит упорядоченность списка блоков по базовым адресам.
Теперь мы можем легко и просто управлять физической памятью - выделять блоки страниц, проецировать их, освобождать. Теперь необходимо придумать, как распоряжаться виртуальной памятью. Задачей менеджера виртуальной памяти будет являться управление виртуальным адресном пространстве на уровне страниц: Возможно, лучше понять, что я имею ввиду, поможет пара прототипов функций:
alloc_virt_pages: as - адресное пространство, в котором производится работа. Структура AddressSpace может содержать дополнительную информацию (нужную для поиска свободных страниц). У каждого процесса в системе свой AddressSpace (всегда нижние 2 ГБ), плюс у ядра свой AddressSpace общий для всех каталогов страниц (верхние 2 ГБ). Возвращённый функцией адрес
должен принадлежать региону от as->start до as->end, либо NULL в случае ошибки. vaddr - Желаемый виртуальный адрес. Если равен NULL, функция должна найти сама свободный виртуальный адрес, куда можно примонтировать count страниц (это и есть самое сложное - как искать лучше), иначе функция должна спроецировать страницы по этому адресу при условии, что он не выходит за пределы AddressSpace (as->start <= vaddr < as->end) и на этом месте ничего не примонтировано до этого вызова. paddr
- Желаемый физический адрес. Например, драйвер может захотеть примонтировать страницу 0xB8000 для работы с текстовым экраном. Если равно -1, функция должна вызвать alloc_phys_pages(count) и использовать его результат (если не произойдёт ошибки выделения памяти, тогда придётся вернуть NULL и ничего не проецировать). count - Количество страниц для проецирования. flags - Атрибуты доступа для проецирования. Аналогично одноимённому параметры map_pages.
free_virt_pages: as - Аналогично
alloc_virt_pages. vaddr - Виртуальный адрес блока страниц, который следует освободить. Должен принадлежать адресному пространству as и быть не равен NULL. count - Количество страниц для освобождения. flags - Флаги освобождения. Позволяет запретить функции освобождать страницы без флага PAGE_USER. Нужно для того, чтобы не дать приложению уничтожить системные структуры.
Вот так. Свои предложения по механизму хранения свободных страниц и их поиска, можете присылать мне на почту: kiv.apple@gmail.com.
До встречи! ;-)