| Предыдущий раздел | Оглавление | Следующий раздел |
4.3.2. Управление памятью с помощью связанных списков
Ведение связанных списков свободных и распределенных сегментов памяти также используется для отслеживания памяти. Конкретный сегмент может содержать процесс или незанятое пространство. Связанный список сегментов для конкретного участка памяти (рис. 4.3, а) изображен на рис. 4.3, в. Записи в списке хранят обозначение свободных пространств H или процессов P, также адрес начала сегмента, длину сегмента и указатель на следующую запись.
В данном примере представленный список сегментов отсортирован по адресам. Такая сортировка упрощает обновление списка при завершении процесса или его перемещении на диск. Когда процесс завершается, то из его соседей (процессов или пустых пространств) можно составить четыре комбинации, которые представлены на рис. 4.4. Обновление списка, которое требует замены P на H, представлено на рис. 4.4, а. Две записи объединяются в одну на рис. 4.4, б. На рис. 4.4, в, список сокращается на одну запись. Объединение трех записей изображено на рис. 4.4, г.
Более удобно вести двусвязный список, так как запись для завершающегося процесса в таблице процессов обычно указывает на запись в списке, соответствующую именно этому процессу. Использование двусвязного списка облегчает и поиск предыдущей записи, и определение возможности объединения.
Для выделения памяти запускаемому процессу или загружаемому с диска с использованием свопинга существующему процессу при условии, что список процессов и пустых пространств отсортирован по адресам, могут использоваться несколько алгоритмов. Допустим, что диспетчеру памяти известен объем выделяемой памяти. Простейшим алгоритмом является так называемый алгоритм «первое подходящее», при котором список сегментов сканируется диспетчером памяти до тех пор, пока не найдется незанятое пространство нужного размера. После чего незанятое пространство разделяется на две части, одна из которых будет использоваться для процесса, а другая для неиспользуемой памяти, если процесс не помещается точно в найденное пространство, что очень маловероятно. Алгоритм «Первое подходящее» выполняется достаточно быстро, так как поиск требует небольших затрат времени.
Алгоритм «следующее подходящее» является вариацией предыдущего алгоритма. Он работает по тому же принципу, что и алгоритм «первое подходящее», но следит за местоположением своего поиска, запоминая его при нахождении подходящего незанятого пространства. При следующем вызове алгоритм начинает поиск с того места списка, где он закончил работу в прошлый раз.
Широко используемым алгоритмом является алгоритм «наиболее подходящее». Он производит поиск по всему списку и выбирает наименьшее подходящее по размерам незанятое пространство. Чтобы не разделять большое незанятое пространство, которое возможно в дальнейшем пригодится для более требовательных процессов, данный алгоритм пытается подыскать наиболее близкое по размеру незанятое пространство. Из-за того, что при каждом вызове необходимо вести поиск по всему списку, алгоритм «наиболее подходящее» выполняется медленнее, чем описанные выше алгоритмы. Однако его применение может привести к еще более неэффективному использованию памяти из-за стремления алгоритма заполнить память, при котором остаются небольшие незанятые пространства, которые не подойдут большинству загружаемых процессов. Более протяженные незанятые пространства остаются после прохода алгоритма «первое подходящее».
Попытка обойти проблему разделения пространств памяти на отводимую под процесс полезную память и небольшие бесполезные незанятые пространства привела к идее алгоритма «наименее подходящее». Данный алгоритм выбирает самое большое подходящее незанятое пространство, чтобы после перемещения в него процесса оставшееся незанятое пространство оставалось достаточно большим для многих других процессов.
Кроме того, ведение отдельных списков для процессов и незанятых пространств может ускорить выполнение представленных четырех алгоритмов. Основные усилия данных алгоритмов при этом будут сосредоточены на исследовании списка пустых пространств. Однако ускорение распределения памяти неизбежно приводит к дополнительным затратам при ее освобождении, так как сегмент, из которого был выгружен процесс, должен удаляться из списка процессов и вноситься в список незанятых пространств. Чтобы увеличить скорость обнаружения подходящих незанятых мест, список свободных пространств сортируется по размеру.
Для распределения памяти используется еще один алгоритм, который называется «быстро искомое подходящее». Этот алгоритм использует отдельные списки для наиболее востребованных размеров памяти. При использовании данного алгоритма поиск необходимого пространства производится очень быстро, но и он имеет недостаток, который есть у всех систем, где свободные пространства сортируются по размеру. При завершении процесса или выгрузки его посредством процедуры свопинга большое время затрачивается на определение возможности объединения полученного пространства с соседними. Без объединения память очень быстро фрагментируется, то есть разбивается на большое количество небольших свободных фрагментов, неподходящих для размещения большинства процессов.
| Предыдущий раздел | Оглавление | Следующий раздел |