В ядре фактически нужны три механизма выделения/освобождения памяти. Один из них предназначен для самого ядра; он работает с областями произвольного размера (для простоты -- кратного 8 или 16 для 32- и 64-разрядных систем соответственно). Память он берёт из заранее выделенных страниц, постоянно закреплённых в физическом ОЗУ (поскольку это куча самого ядра; в ней хранятся блоки управления задачами, устройствами и прочая внутрисистемная информация).
Два других механизма связаны с обслуживанием приложений и фактически являются частью менеджера виртуальной памяти. Первый из них ведает выделением/освобождением физических страниц памяти, относящихся к области, выделенной для приложений. Он должен уметь выделять как непрерывный набор страниц, так и страницы "россыпью" (это зависит от потребностей приложения и возможностей устройств ввода-вывода: непрерывная последовательность физических страниц на практике нужна лишь в том случае, если в них располагается буфер ввода-вывода для устройства, не умеющего обмениваться данными с несмежными областями памяти). Второй же механизм выделяет/освобождает области виртуальной памяти приложения, при этом выделение физических страниц может и не происходить. Когда приложение запрашивает выделение памяти под свои нужды, фактически это означает, что она запрашивает дополнительную виртуальную память, ну а физические страницы могут выделяться тогда, когда к этой памяти реально последует обращение.
Хранение информации о памяти выполняется по-разному в зависимости от того, что именно эта информация описывает и для чего она нужна. Для хранения информации о свободной памяти в системной куче резонно использовать саму свободную память. В простейшем случае получается следующая конструкция: 1) есть переменная, содержащая адрес первого свободного блока (фактически физический, поскольку память относится к ядру системы, где обычно применяется прямое отображение виртуальных адресов на физические); 2) есть цепочка свободных блоков с размером, кратным удвоенной разрядности адреса. По смещению 0 в каждом блоке хранится адрес следующего блока в цепочке, а сразу за ним -- длина этого блока (в байтах или в единицах, кратных адреса -- неважно, это технические детали; лично я предпочитаю иметь дело с байтами). В последнем блоке адрес следующего будет равен нулю. При запросе на выделение памяти из системной кучи соответствующая подпрограмма пробегается по этой цепочке блоков и выделяет тот, размер которого не меньше запрошенного (если размеры равны, он выделяется целиком, если выделяемый больше запрошенного, от него "откусывается" кусок нужного размера). При освобождении освобождаемый блок вставляется в цепочку, при этом нужно слить его с уже имеющимися блоками, если они окажутся смежными. В целом подпрограммы выделения/освобождения получаются довольно простыми и небольшими по объёму. Вот, например, текст обеих подпрограмм из моей оси для АРМа:
Код:
; ==============================================================================
;
; ВЫДЕЛЕНИЕ БЛОКА SQA
;
; ==============================================================================
;
; Эта подпрограмма находит в SQA свободный блок подходящего размера и выделяет
; его запросившей программе. При необходимости "откусывается" часть блока боль-
; шего размера.
;
; Реальный размер выделенного блока может превышать запрошенный, поскольку он
; всегда будет кратен 8. Необходимое изменение размера подпрограмма SQA_Get вы-
; полняет сама.
;
; На входе:
;
; - R1 - требуемый размер блока;
; - R8 - базовый адрес области переменных системы.
;
; На выходе:
;
; - C=1 - блок не выделен из-за недостатка объёма свободной SQA или её сильной
; фрагментации;
; - C=0 - блок успешно выделен;
; - R0 - адрес выделенного блока (всегда кратен 8);
; - R1 - реальный размер выделенного блока.
SQA_Get ROUT
add R1, R1, #7 ; Выравнивание длины на границу 8
bic R1, R1, #7
add R3, R8, #Free_SQA_List ; Адрес предыдущего FSQAB
; Поиск свободного блока подходящего размера.
10 ldr R0, [R3, #FSQAB_Next] ; Адрес текущего FSQAB
cmp R0, #0 ; Текущего блока нет - выделить не
jmpeq LR ; смогли, выход с установленным C
ldr R2, [R0, #FSQAB_Size] ; Размер текущего блока подходит для
subs R2, R2, R1 ; удовлетворения запроса?
movlo R3, R0 ; Нет, переход к следующему FSQAB
blo %B10
beq %F20
; Текущий блок больше запрошенного, "откусывание" нужного куска.
str R2, [R0, #FSQAB_Size] ; Сохранение размера остатка
adds R0, R0, R2 ; Адрес выделенного участка и одно-
jmp LR ; временно сброс флага C
; Текущий блок равен запрошенному, изъятие его из списка свободных.
20 ldr R2, [R0, #FSQAB_Next] ; Адрес следующего свободного FSQAB
str R2, [R3, #FSQAB_Next]
adds R2, R2, #0 ; Сброс флага C
jmp LR
; ==============================================================================
;
; ОСВОБОЖДЕНИЕ БЛОКА SQA
;
; ==============================================================================
;
; Эта подпрограмма возвращает в список свободных блоков SQA указанный блок. Если
; он граничит с другими соседними блоками, происходит их слияние в один более
; крупный блок.
;
; Реальный размер освобождаемого блока подпрограммой может быть увеличен, чтобы
; он стал кратен 8.
;
; Чтобы избежать неверного слияния с предыдущим блоком, адрес предыдущего на са-
; мом деле является адресом переменной Free_SQA_List, последняя размещается не-
; посредственно перед переменной Work_Flags, в которой младший бит всегда уста-
; новлен. Благодаря этому сумма адреса предыдущего блока (в данном случае пере-
; менной Free_SQA_List) и его длины (содержимого Work_Flags) никогда не может
; совпать с адресом освобождаемого блока: последний всегда кратен 8, а значит,
; его младший бит всегда равен нулю.
;
; На входе:
;
; - R0 - адрес освобождаемого блока (должен быть кратен 8);
; - R1 - размер освобождаемого блока;
; - R8 - базовый адрес области переменных системы.
SQA_Free ROUT
add R1, R1, #7 ; Выравнивание длины на границу 8
bic R1, R1, #7
add R3, R8, #Free_SQA_List ; Адрес предыдущего свободного блока
add R12, R0, R1 ; Адрес за освобождаемым блоком
; Поиск точки для вставки освобождаемого блока: следующий за ним блок
; должен иметь больший адрес, а предшествующий - меньший, чтобы обеспе-
; чить слияние блоков, когда это возможно.
20 ldr R2, [R3, #FSQAB_Next] ; Адрес следующего свободного блока
tst R2, R2 ; Он вообще существует?
beq %F30 ; Нет, последним будет освобождаемый
cmp R2, R12 ; Какой блок находится раньше?
movlo R3, R2 ; Следующий, он становится предыду-
blo %B20 ; щим; идём к следующему свободному
bhi %F30 ; Следующий после освобождаемого
; Следующий блок сразу за освобождаемым. Слияние их в один блок.
ldr R12, [R2, #FSQAB_Size] ; Вычисление длины объединённых
add R1, R1, R12 ; блоков
ldr R2, [R2, #FSQAB_Next] ; Новый следующий блок (несливаемый)
; Проверка на слияние освобождаемого блока с предыдущим.
30 ldr R12, [R3, #FSQAB_Size] ; Размер предыдущего блока
add R12, R3, R12 ; Адрес за концом предыдущего блока
cmp R12, R0 ; Надо ли сливать блоки?
beq %F40 ; Да
; Предыдущий и освобождаемый блоки не сливаются. Добавление освобождае-
; мого блока в список свободных.
str R0, [R3, #FSQAB_Next]
str R1, [R0, #FSQAB_Size]
str R2, [R0, #FSQAB_Next]
jmp LR
; Слияние освобождаемого с предыдущим.
40 str R2, [R3, #FSQAB_Next]
ldr R2, [R3, #FSQAB_Size]
add R2, R2, R1
str R2, [R3, #FSQAB_Size]
jmp LR
Аналогичным образом можно хранить данные о свободных страницах физической памяти; по большому счёту, даже подпрограммы могут быть теми же самыми, поскольку различается лишь адрес переменной, в которой хранится адрес первого свободного блока.
Понятное дело, что подобное управление памятью не является гиперэффективным, но оно очень простое и при этом полностью работоспособное. Фактически единственное, что полезно сделать для улучшения производительности, -- это заготовить отдельные списки свободных блоков определённых размеров, которые наиболее часто выделяются/освобождаются системой. В этом случае при поступлении запроса на такой блок можно будет выделить его очень быстро, если в соответствующем списке есть хотя бы один свободный блок, и лишь если его нет, тогда обращаться к общей программе, работающей с блоками произвольного размера. Но, думаю, заморачиваться с подобными оптимизациями есть смысл лишь при уже работающей системе.
А вот хранение информации о выделенной задаче виртуальной памяти, о правах доступа к ней, об отображении виртуальной памяти на физическую -- это отдельная история, причём там всё тесно связано с "идеологией" управления памятью в системе. Обсуждать одно в отрыве от другого просто смысла нет.
Вход
Регистрация
FAQ
Поиск
