OSDev

Я уже делал несколько вариантов менеджеров памяти, но никак не могу выбрать наиболее рациональный вариант. Мой требования:
1) Чтобы не очень сложно было реализовать на Ассемблере
2) Чтобы поддерживал многозадачность
3) Чтобы можно было выделять несколько смежных страниц (нужно иногда драйверам)
Мои варианты реализации:
1) Стек страниц (противоречит 3 пункту)
2) Битовая карта страниц
3) Связанный список блоков страниц. Причём вся служебная информация хранится на самих пустых страницах. Самый сложный в реализации алгоритм.
Как лучше всего сделать менеджер физических страниц?

Именно пункт 3 :) Он отнюдь не так сложен, как кажется на первый взгляд. Надо только не забыть в освобождении страниц реализовать слияние нескольких блоков в один, когда такое возможно. Реализация подпрограмм выделения и освобождения на ассемблере потребует в сумме порядка 100-200 инструкций, не больше.

Для устаревших устройств драйверам иногда еще нужно выделять память в определенном месте. Я использую стек страниц, но резервирую для драйверов первый мег физ. памяти и управляю им с помощью битовой карты (для работы с этой памятью используется спец. набор функций, манипулирующих физическими адресами из данного диапазона). Стек страниц имеет двойное дно - фиксированное и подвижное - ниже подвижного дна располагаются обнуленные страницы (при выделении обнуленных страниц образовавшиеся "дыры" сразу заполняются страницами из вершины стека). Когда основной стек полностью пуст, есть возможность (условная компиляция) использовать для распределения его страницы - для нынешних объемов ОЗУ это дополнительные 2-4 мега памяти.

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

Можно попробовать 1 вариант (который противоречит п.3), но для выделения именно смежных страниц использовать дополнительную функцию, которая будет выбирать из стека смежные страницы. Будут 2 разные функции, одна для выделения простых блоков, но быстро, и вторая для смежных, но медленнее.

Последовательно просматривать весь стек крайне неэффективно. Нужна дополнительная структура для быстрого поиска.

Например индексирование, как в базах данных. Нужен массив такой же длинны, как и сам стек. Порядковый номер элемента будет соответствовать адресу, а его значение указывать на положение страницы в стеке.

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

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

Ну так стек -- это ж структура "первым пришёл-первым ушёл", чем отличается от обычного списка. Поэтому лично мне неясно, зачем здесь вообще стек и как его можно использовать для управления памятью (если не через задницу).

Ну так как раз то, что нужно ;)