Распределение памяти блоками переменного размера
При управлении памятью, распределяемой блоками переменного размера, также может быть использована маркировка блоков и представление свободных блоков в виде списка, но каждый свободный элемент кучи при этом должен иметь дополнительное поле для размещения информации о своем размере. Кроме того, для отслеживания информации о свободных блоках памяти в куче может быть использован метод близнецов (память распределяется блоками, размер которых кратен степеням 2, причем для блоков одинакового размера строятся отдельные списки). Однако чаще всего для управления памятью используется организация связных линейных списков свободных блоков памяти.
Управление кучей, память в которой распределяется блоками переменного размера, усложняется, так как для выполнения запроса на распределение памяти требуется найти свободный блок памяти подходящего размера путем просмотра списка свободных блоков. Для определения того, какой блок памяти может быть выделен по запросу для размещения кода программы или данных, используются различные стратегии выделения памяти:
¨ стратегия наиболее подходящего (из списка свободных выделяется блок памяти максимально близкий по размеру к запрашиваемому и в ответ на запрос выделяется весь блок или его часть (если блок распределяется не полностью, то его “остаток” включается в список свободных блоков));
¨ стратегия первого подходящего (в списке находится первый подходящий по размеру свободный блок памяти и выделяется в ответ на запрос целиком или частично);
|
|
|
¨ стратегия наименее подходящего (выделяется блок или часть блока максимального размера из всех блоков, находящихся в списке).
Последняя стратегия используется из предположения о том, что после выделения части блока его оставшаяся свободной часть окажется достаточно большой для распределения по новым запросам, в то время как при использовании первой стратегии “остатки” могут быть очень небольшими по размеру и могут оказаться непригодными для дальнейшего использования.
Выбор стратегии влияет на уровень фрагментации памяти в куче и на быстроту поиска блока памяти для распределения по запросу (в MS-DOS используется три стратегии выделения памяти: поиск от начала, оптимальный поиск, поиск от конца).
Связные списки свободных блоков памяти строятся по определенным правилам (их элементы упорядочиваются по размерам или по базовым адресам). При упорядочении блоков в порядке возрастания их размеров первый подходящий по размеру блок в списке окажется и наиболее подходящим. Если блоки в списке упорядочены по убыванию их размеров, то при выделении первого блока из списка реализуется последняя стратегия. Для реализации алгоритмов уплотнения памяти удобно было бы упорядочивать блоки в списках по их базовым адресам.
Дата добавления: 2016-01-05; просмотров: 14; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!