Одним из типов поиска являются задачи по распределению памяти (наиболее характерны они при создании ОС), однако во многих прикладных алгоритмах эти задачи возникают при создании прикладных программ, работающих с большим объемом данных. Если до начала обработки полный объем данных, которые подлежат обработке, неизвестен, то используется общий подход для распределения областей этой памяти согласно заданным требованиям.
Дана фиксированная область памяти, задача заключается в том, чтобы занимать и освобождать меньшие области памяти большой областью, без выхода за границы памяти. При распределении памяти проверяются наибольшие свободные области. Обычно эти области малы для размещения в них всех данных, и, следовательно, память становится фрагментной. Имеются следующие способы уменьшения фрагментности.
Первое возможное размещение. Последовательно просматриваются области памяти, пока не найдется первая, достаточная для размещения. Вся область организована в список и упорядочена по адресам (рис. 7.3).
Рис. 7.3 — Схема распределения памяти
Поиск в этом списке осуществляется последовательно до тех пор, пока не будет найдена достаточно большая область для размещения данных. Тогда эта область изымается из списка, а на это место помещается меньшая свободная область — оставшаяся незанятая часть исключенной области. С помощью этого метода легко освобождать ранее занятые области памяти. С этой целью просматривается список, как только он будет упорядочен по адресам, то нетрудно найти место, чтобы пометить освобожденную область памяти. Соседние адреса — смежные в списке, поэтому легко объединить две свободные области в одну, большую по размеру.
Данный способ самый простой, однако поскольку занятие области памяти осуществляется после нахождения первой области, достаточной для размещения данных, память становится фрагментной.
Наилучшее размещение. Последовательно просматриваются все области, выбирается наименьшая область, размер которой больше или равен требуемому объему для размещения данных. В этом случае области связываются друг с другом по размеру, а не по адресам. Алгоритм размещения-освобождения аналогичен первому возможному размещению. Однако в этом случае стратегия размещения приводит к меньшей фрагментности, потому что используется область наименьшего размера для размещения данных. Однако так как свободная область не упорядочена по адресам, алгоритм объединения двух свободных областей в область большего объема довольно сложен.
Сопрягаемые области памяти. Областями памяти являются N цепочек размером 2N каждая. Если область размером 2K отсутствует, а имеется свободная область размером 2K+1, то она разбивается на две сопрягаемые области размером 2K. После того как области освободятся, они рассматриваются как области размером 2K, которые можно объединить в область размером 2K+1.