1. Способы учета использования динамической памяти

В процессе перехода многозадачных операционных систем (ОС) от систем с фиксированными разделами к системам с переменными (непостоянными) разделами перед ОС стала задача учета, управления и отслеживания изменений, происходящих при запуске и остановке процессов. Ещё больше эта проблема усугубилась, когда ОС стала предоставлять процессам возможность выделять память из «кучи», то есть в общем случае иметь раздел памяти, размер которого не был постоянен, а мог увеличиваться во время работы процесса.

Существует два способа, которыми ОС может учитывать использование памяти: списки блоков памяти и битовые карты памяти.

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

рис. 1. Пример схемы занятости оперативной памяти
с соответствующей информацией в виде списка блоков

Как правило, список блоков бывает упорядочен по адресу начала блока, что упрощает объединение соседних блоков при освобождении занятого (в этом случае необходимо проанализировать только два соседних элемента списка по отношению к освобождаемому).

Битовая карта памяти. При использовании этого метода учета памяти, вся оперативная память системы условно делиться на участки равного размера (например, 64 байта), после чего состояние занят/свободен для каждого участка может быть описано логической переменной, то есть одним битом. ОС выделяет соответствующий массив данных размера (размер-памяти / размер-блока + 7) / 8 байт, где каждый бит соответствует одному блоку. Так, для ситуации, изображенной на рис. 1., и, предполагая, что минимальный блок памяти, учитываемый битовой картой, составляет 8 байт, двоичный массив будет выглядеть как 11111111100111000000001111111000000.

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

рис. 2. Хранение служебной информации перед
занятыми участками (без соблюдения масштаба участков)