Схема с переменными разделами

В принципе, система свопинга может базироваться на фиксированных разделах. Более эффективной представляется схема динамического распределения или схема с переменными разделами, которая может использоваться и в тех случаях, когда все процессы целиком помещаются в памяти, то есть в отсутствие свопинга. В этом случае вначале вся память свободна и не разделена заранее на разделы. Вновь поступающей задаче выделяется строго необходимое количество памяти, не более. После выгрузки процесса память временно освобождается. По истечении некоторого времени память представляет собой переменное число разделов разного размера (рис. 25). Смежные свободные участки могут быть объединены.

Рис. 25. Динамика распределения памяти между процессами (серым цветом показана неиспользуемая память).

В какой раздел помещать процесс? Наиболее распространены три стратегии.

1. Стратегия первого подходящего (First fit). Процесс помещается в первый подходящий по размеру раздел.

2. Стратегия наиболее подходящего (Best fit). Процесс помещается в тот раздел, где после его загрузки останется меньше всего свободного места.

3. Стратегия наименее подходящего (Worst fit). При помещении в самый большой раздел в нем остается достаточно места для возможного размещения еще одного процесса.

Моделирование показало, что доля полезно используемой памяти в первых двух случаях больше, при этом первый способ несколько быстрее. Попутно заметим, что перечисленные стратегии широко применяются и другими компонентами ОС, например для размещения файлов на диске.

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

Этот метод более гибок по сравнению с методом фиксированных разделов, однако ему присуща внешняя фрагментация – наличие большого числа участков неиспользуемой памяти, не выделенной ни одному процессу. Выбор стратегии размещения процесса между первым подходящим и наиболее подходящим слабо влияет на величину фрагментации. Любопытно, что метод наиболее подходящего может оказаться наихудшим, так как он оставляет множество мелких незанятых блоков.

Статистический анализ показывает, что пропадает в среднем 1/3 памяти! Это известное правило 50% (два соседних свободных участка в отличие от двух соседних процессов могут быть объединены).

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

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

Смежное размещение является простейшим и предполагает, что в памяти, начиная с некоторого начального адреса, выделяется один непрерывный участок адресного пространства.

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

Уменьшить фрагментацию памяти при мультипрограммировании с фиксированными разделами (MFT) можно, если загрузочные модули создаются в перемещаемых адресах. Такой модуль может быть загружен в любой свободный раздел после соответствующей настройки.

При мультипрограммировании с трансляцией в перемещаемых адресах имеются две причины фрагментации. Первая – размер загруженного процесса меньше размера, занимаемого разделом (внутренняя фрагментация), вторая – размер процесса в очереди больше размера свободного раздела, и этот раздел ос­тается свободным (внешняя фрагментация).

Для защиты памяти при мультипрограммировании с фиксированным количеством разделов необходимы два регистра. Первый – регистр верхней границы (наименьший адрес), второй регистр нижней границы (наибольший адрес) –рис. 26. 27.

Рис. 26. Режим мультипрограммирования с фиксированным количеством разделов (фрагментация памяти)

Рис. 27. Регистры границ для MFT.

Прежде чем программа в разделе N начнет выполняться, ее граничные адреса загружаются в соответствующие регистры. В процессе работы программы все формируемые ею адреса контролируются на удовлетворение неравенства а < Адр. < б.

При выходе любого адреса программы за отведенные ей границы работа программы прерывается.

Мультипрограммирование с переменными разделами (multiprogramming with a variable number of tasks – MVT) предполагает разделение памяти на разделы и использование загрузочных модулей в перемещаемых адресах, однако границы разделов не фиксируются.

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

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

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

Уплотнением памяти называется перемещение всех занятых разделов по адресному пространству памяти таким образом, чтобы свободный фрагмент занимал одну связную область (рис. 28).

 

Рис.28. Режим уплотнения памяти

 

На практике реализация уплотнения памяти сопряжена с усложнением операционной системы и обладает следующими недостатками:

- в тех случаях, когда мультипрограммная смесь неоднородна по отношению к размерам программ, возникает необходимость в частом уплотнении, что расходует ресурс процессорного времени и компенсирует экономию ресурса памяти;

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

Основные стратегии заполнения свободного раздела. Рассмотренные методы мультипрограммирования предполагают наличие входной очереди (очередей) к разделам основной памяти.