Управление памятью с помощью связанных списков

Другим способом отслеживания памяти является ведение связанных списков распределенных и свободных сегментов памяти, где сегмент либо содержит процесс, либо является пустым пространством между двумя процессами.
Участок памяти, изображенный на рис. 3.6, а, представлен на рис. 3.6, в, как связанный список сегментов. Каждая запись в списке хранит обозначение, содержит сегмент «дыру» — hole (H) или процесс — process (P), адрес, с которого сегмент начинается, его длину и указатель на следующую запись.

В этом примере список сегментов составлен отсортированным по адресам. Преимущество такой сортировки заключается в том, что при завершении процесса или его свопинге на диск упрощается обновление списка. У завершившегося процесса есть, как правило, два соседа (за исключением тех случаев, когда он находился в верхних или нижних адресах памяти). Этими соседями могут быть либо процессы, либо пустые пространства, из чего можно составить четыре комбинации, показанные на рис. 3.7. На рис. 3.7, а обновление списка требует замены P на H. На рис. 3.7, б и в две записи объединяются в одну, и список становится на одну запись короче. На рис. 3.7, г объединяются три записи, и из списка удаляются уже две записи.

Поскольку запись в таблице процессов, относящаяся к завершающемуся процессу, будет, как правило, указывать на запись в списке именно для этого процесса, возможно, удобнее будет вести не односвязный список, как показано на рис. 3.6, в, а двусвязный список. Такая структура облегчит поиск предыдущей записи и определение возможности объединения.

Рис. 3.7. Четыре комбинации соседей для завершающегося процесса X



Когда процессы и пустые пространства содержатся в списке отсортированными по адресам, то для выделения памяти создаваемому процессу (или существующему процессу, загружаемому в результате свопинга с диска) могут быть использованы несколько алгоритмов. Предположим, что диспетчер памяти знает, сколько памяти нужно выделить. Простейший алгоритм называется «первое подходящее». Диспетчер памяти сканирует список сегментов до тех пор, пока не найдет пустое пространство подходящего размера. Затем пустое пространство разбивается на две части: одна для процесса и одна для неиспользуемой памяти, за исключением того статистически маловероятного случая, когда процесс в точности помещается в пустое пространство. «Первое подходящее» — это быстрый алгоритм, поскольку поиск ведется с наименьшими затратами времени.

Незначительной вариацией алгоритма «первое подходящее» является алгоритм «следующее подходящее». Он работает так же, как и «первое подходящее», за исключением того, что отслеживает свое местоположение, как только находит подходящее пустое пространство. При следующем вызове для поиска пустого пространства он начинает поиск в списке с того места, на котором остановился в прошлый раз, а не приступает к поиску с самого начала, как при работе алгоритма «первое подходящее». Моделирование работы алгоритма «следующее подходящее», выполненное Бэйсом (Bays, 1977), показало, что его производительность несколько хуже, чем алгоритма «первое подходящее».

Другой хорошо известный и широко используемый алгоритм — «наиболее подходящее». При нем поиск ведется по всему списку, от начала до конца, и выбирается наименьшее соответствующее пустое пространство. Вместо того чтобы разбивать большое пустое пространство, которое может пригодиться чуть позже, алгоритм «наиболее подходящее» пытается подыскать пустое пространство, близкое по размеру к необходимому, чтобы наилучшим образом соответствовать запросу и имеющимся пустым пространствам.

В качестве примера алгоритмов «первое подходящее» и «наиболее подходящее» вернемся к рис. 3.6. Если необходимо пространство в два единичных блока, то, согласно алгоритму «первое подходящее», будет выделено пустое пространство, начинающееся с адреса 5, а согласно алгоритму «наиболее подходящее», будет выделено пустое пространство, начинающееся с адреса 18.

Алгоритм «наиболее подходящее» работает медленнее, чем «первое подходящее», поскольку при каждом вызове он должен вести поиск по всему списку.

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

При попытке обойти проблему разбиения практически точно подходящих пространств памяти на память, отводимую под процесс, и небольшие пустые пространства можно прийти к идее алгоритма «наименее подходящее», то есть к неизменному выбору самого большого подходящего пустого пространства, чтобы вновь образующееся пустое пространство было достаточно большим для дальнейшего использования. Моделирование показало, что применение алгоритма «наименее подходящее» также далеко не самая лучшая идея.

Работа всех четырех алгоритмов может быть ускорена за счет ведения отдельных списков для процессов и пустых пространств. При этом все усилия этих алгоритмов сосредоточиваются на просмотре списков пустых пространств, а не списков процессов. Неизбежной ценой за это ускорение распределения памяти становится дополнительное усложнение и замедление процедуры ее освобождения, поскольку освободившийся сегмент должен быть удален из списка процессов и внесен в список пустых пространств.

Если для процессов и пустых пространств ведутся разные списки, то для более быстрого обнаружения наиболее подходящих свободных мест список пустых пространств должен сортироваться по размеру. Когда при работе алгоритма «наиболее подходящее» поиск пустых пространств ведется от самых маленьких до самых больших, то при обнаружении подходящего пространства становится понятно, что найденное пространство является наименьшим, в котором может быть выполнено задание, следовательно, оно и есть наиболее подходящее. Дальнейший поиск, как при системе, использующей один список, уже не потребуется. При использовании списка пустых пространств, отсортированного по размеру, алгоритмы «первое подходящее» и «наиболее подходящее» работают с одинаковой скоростью, а алгоритм «следующее подходящее» теряет смысл.

Когда список пустых пространств ведется отдельно от списка процессов, можно провести небольшую оптимизацию. Вместо того чтобы создавать отдельный набор структур данных для обслуживания списка пустых пространств, как это сделано на рис. 3.6, в, можно хранить информацию в самих пустых пространствах. В первом слове каждого пустого пространства может содержаться размер этого пространства, а второе слово может служить указателем на следующую запись. Элементы списка, показанного на рис. 3.6, в, для которых требуются три слова и один бит (Р/Н), больше не нужны.

Еще один алгоритм распределения памяти называется «быстро искомое подходящее». Его использование предусматривает ведение отдельных списков для некоторых наиболее востребованных искомых размеров. К примеру, у него может быть таблица из п записей, в которой первая запись является указателем на вершину списка пустых пространств размером 4 Кбайт, вторая — указателем на список пустых пространств размером 8 Кбайт, третья — указателем на список пустых пространств размером 12 Кбайт и т. д. Пустые пространства размером, скажем, 21 Кбайт могут быть помещены либо в список пустых пространств размером 20 Кбайт, либо в специальный список пустых пространств с нечетным размером.

При использовании алгоритма «быстро искомое подходящее» поиск пустого пространства требуемого размера выполняется исключительно быстро, но в нем имеется недостаток, присущий всем системам, сортирующим пустые пространства по размеру, а именно когда процесс завершается или выгружается процедурой свопинга, слишком много времени тратится на то, чтобы определить, можно ли высвобождаемое пространство объединить с соседними. Если не проводить объединение, то память очень быстро окажется разбитой на большое количество небольших по размеру пустых фрагментов, в которых не смогут поместиться процессы.

3.3.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Управление памятью с помощью связанных списков:

  1. 9.11. С ПОМОЩЬЮ ПАМЯТИ
  2. Судебно-психологическая экспертиза по делам о происшествиях, связанных с управлением техникой.
  3. Статья 400. Посягательство на жизнь защитника или представителя лица в связи с деятельностью, связанной с оказанием правовой помощи
  4. Номер один в списке неправильных действий
  5. ПРЕДСТАВЛЕНИЕ ПАМЯТИ
  6. укрепление памяти
  7. Статья 1040. Обращение взыскания на имущество, переданное в управление, по требованию кредитора установщика управления
  8. ТЕОРИЯ ПАМЯТИ
  9. Гигиена памяти.
  10. V. 2. 5. Структура парциального хранилища памяти.
  11. Сила памяти
  12. Роль памяти и воображения
  13. В психологии различают четыре типа памяти.
  14. V. 2. МОДЕЛЬ ПАРЦИАЛЬНОГО ХРАНИЛИЩА ПАМЯТИ ЧЕЛОВЕКА
  15. следующие виды памяти