Язык С


         

Пример - распределитель памяти


В главе 5 мы написали бесхитростный вариант функции ALLOC. Вариант, который мы напишем теперь, не содержит огра- ничений: обращения к функциям ALLOC и FREE могут перемежать- ся в любом порядке; когда это необходимо, функция ALLOC об- ращается к операционной системе за дополнительной памятью. Кроме того, что эти процедуры полезны сами по себе, они так- же иллюстрируют некоторые соображения, связанные с написани- ем машинно-зависимых программ относительно машинно-независи- мым образом, и показывают практическое применение структур, объединений и конструкций TYPEDEF. Вместо того, чтобы выделять память из скомпилированного внутри массива фиксированного размера, функция ALLOC будет по мере необходимости обращаться за памятью к операционной системе. Поскольку различные события в программе могут тре- бовать асинхронного выделения памяти, то память, управляемая ALLOC, не может быть непрерывной. В силу этого свободная па- мять хранится в виде цепочки свободных блоков. Каждый блок включает размер, указатель следующего блока и саму свободную память. Блоки упорядочиваются в порядке возрастания адресов памяти, причем последний блок (с наибольшим адресом) указы- вает на первый, так что цепочка фактически оказывается коль- цом. При поступлении запроса список свободных блоков просмат- ривается до тех пор, пока не будет найден достаточно большой блок. Если этот блок имеет в точности требуемый размер, то он отцепляется от списка и передается пользователю. Если же этот блок слишком велик, то он разделяется, нужное количест- во передается пользователю, а остаток возвращается в свобод- ный список. Если достаточно большого блока найти не удается, то операционной системой выделяется новый блок, который включается в список свободных блоков; затем поиск возобнов- ляется. Освобождение памяти также влечет за собой просмотр сво- бодного списка в поиске подходящего места для введения осво- божденного блока. Если этот освободившийся блок с какой-либо стороны примыкает к блоку из списка свободных блоков, то они объединяются в один блок большего размера, так что память не становится слишком раздробленной. Обнаружить смежные блоки просто, потому что свободный список содержится в порядке возрастания адресов.



Содержание  Назад  Вперед