Распределение памяти элементами фиксированного размера
Каждый элемент фиксированного размера занимает N слов (единиц памяти). Вся куча разбивается на известное число элементов.
Один из возможных способов учета памяти в куче с элементами фиксированного размера - маркировка. При использовании такого метода каждый свободный элемент кучи маркируется специальной константой, следовательно, нет необходимости строить дополнительные структуры данных для хранения информации об имеющихся свободных элементах: при запросе на выделение блока памяти достаточно просмотреть последовательно элементы, для определения первого промаркированного в качестве свободного элемента. При освобождении блока памяти система записывает в него маркер. Недостатками такого метода являются его неэффективность (требуется выполнять последовательный поиск свободного элемента) и необходимость выделения в качестве маркера специальной константы.
Второй способ является более эффективным и универсальным (его также можно использовать для управления памятью, распределяемой блоками переменного размера). Для учета памяти ОС организует список свободного пространства (связный список свободных блоков памяти).
Для организации этого списка за пределами кучи резервируется фиксированная ячейка памяти, которая будет служить головой списка (в нее записывается указатель на первый свободный блок памяти). Каждый элемент списка представляет собой свободный блок памяти, при освобождении блока он включается в список, а для организации связи с другими блоками в свободном элементе выделяется фиксированное поле, в которое заносится указатель на следующий элемент списка (следующий свободный блок памяти).
|
|
|
При получении запроса на выделение блока памяти ОС распределяет элемент кучи, ссылка на который записана в голове списка (первый элемент списка), а в голову заносится значение ссылки на следующий за ним элемент списка (это значение выбирается из соответствующего поля выделенного по запросу блока). При освобождении блока памяти ссылка на соответствующий элемент заносится в голову списка, а элемент, стоявший в списке первым, становится следующим за освобожденным блоком в линейном списке.
| Оперативная память | Оперативная память | Оперативная память | Оперативная память | ||||||||
    Голова
| Голова | Голова | Голова | ||||||||
| Начало кучи | Начало кучи | Начало кучи | Начало кучи | ||||||||
   Второй
| Первый | ||||||||||
 Третий
| ¨ | Второй | ¨ | Первый | ¨ | Второй | ¨ | ||||
| Первый | |||||||||||
| Первый | |||||||||||
| а | б | в | г |
|
|
|
Рис.3.14 Изменение состояния кучи:
а) исходное состояние;
б) состояние после выполнения первого запроса;
в) состояние после выполнения второго запроса;
г) состояние после освобождения одного блока памяти из числа ранее выделенных
На рис.3.14 показано изменение состояния списка свободных блоков кучи в результате выполнения операций распределения и освобождения памяти. Заштрихованы свободные элементы кучи.
При распределении памяти блоками фиксированного размера ОС может легко реализовать соответствующий механизм, но этот метод приводит к неэффективному использованию памяти: если запрашивается блок меньшего размера, то часть памяти выделенного по запросу элемента кучи простаивает (т.е. имеет место фрагментация).
Фрагментация памяти существует в любой ВС независимо от организации ее памяти. Однако возможность выделения блоков памяти различных по размеру позволила бы использовать память более эффективно.
|
|
|
Дата добавления: 2016-01-05; просмотров: 18; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!