Реализация сегментации. 
Машинно-зависимые свойства операционных систем

Если страницы имеют фиксированный размер, то сегменты нет.

У сегментов так же, как и у страниц, существует проблема фрагментации.

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

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

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

Однако сегментация существенно отличается от разбиения на страницы в следующем: размер страниц фиксирован, а размер сегментов — нет.

На рис. 6.8, а показан пример физической памяти, в которой изначально содержится 5 сегментов. Посмотрим, что происходит, если сегмент 1 удаляется, а сегмент 7, который меньше по размеру, помещается на его место. В результате получается конфигурация, изображенная на рис. 6.8, б. Между сегментом 7 и сегментом 2 оказывается неиспользованная («пустая») область.

Затем сегмент 4 заменяется сегментом 5 (рис. 6.8, в), а сегмент 3 — сегментом 6 (рис. 6.8, г). Через некоторое время память разделится на ряд областей, одни из которых будут содержать сегменты, а другие — пустоты. Это называется внешней фрагментацией (поскольку неиспользованное пространство попадает не в сегменты, а в пустоты между ними, то есть процесс происходит вне сегментов). Иногда внешнюю фрагментацию называют поклеточной разбивкой (checkerboarding).

Посмотрим, что произойдет, если программа обратится к сегменту 3, когда память фрагментирована (см. рис. 6.8, г). Общее пространство пустот составляет 10 Кбайт, и, хотя это больше, чем нужно для сегмента 3, сегмент 3 туда не помещается, так как пространство разбито на маленькие фрагменты. Вместо этого приходится сначала удалять другой сегмент.

Чтобы избежать подобной ситуации, нужно каждый раз при появлении пустого пространства перемещать следующие сегменты ближе к адресу 0, удаляя таким образом это пустое пространство (точнее, «сдвигая» его к концу памяти). Есть и другой способ. Можно подождать, пока внешняя фрагментация не станет серьезно влиять на процессы (когда на долю пустот придется больше некоторого процента от всего объема памяти), и только после этого выполнить уплотнение. На рис. 6.8, д показано, как память будет выглядеть после уплотнения.

Рис. 3. Динамика внешней фрагментации (а, б, в, г); дефрагментация путем уплотнения (д)

Цель уплотнения памяти — собрать все маленькие пустоты в одно большое свободное пространство, в которое помещается один или несколько сегментов. Недостаток уплотнения состоит в том, что на этот процесс тратится некоторое время.

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

Цель этого алгоритма — не допустить использования большого свободного фрагмента, который может понадобиться позже для большого сегмента.

В другом популярном алгоритме список пустот просто просматривается по кругу и выбирается первый же свободный фрагмент, по размеру подходящий для данного сегмента. Удивительно, но последний алгоритм с точки зрения общей производительности работает гораздо лучше, чем алгоритм оптимальной подгонки, поскольку последний порождает очень много маленьких пустот [114].

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

Опишем один из таких процессов. Всякий раз, когда сегмент удаляется из памяти, а одна или обе соседние области этого сегмента — не сегменты, а пустоты, смежные пустоты можно объединить. Если на рис. 6.8, г удалить сегмент 5, то две соседние пустоты, объединившись с фрагментом размером 4 Кбайт, который занимал удаленный сегмент, дадут в результате свободный фрагмент размером уже 11 Кбайт.

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

MULTICS (Multiplexed Information and Computing Service — служба общей информации и вычислений) — это древняя операционная система, совмещающая сегментацию с разбиением на страницы. Она была разработана Массачусетсом технологическим институтом совместно с компаниями Bell Labs и General Electric [49, 155]. Адреса в MULTICS состоят из двух частей: номера сегмента и адреса внутри сегмента. Для каждого процесса существовал дескрипторный сегмент, содержащий дескрипторы каждого сегмента. При аппаратном получении виртуального адреса для нахождения дескриптора нужного сегмента номер сегмента использовался в качестве индекса в дескрипторном сегменте (рис. 6.9). Дескриптор указывал на таблицу страниц, что позволяло разбивать на страницы каждый сегмент обычным способом. Для повышения производительности недавно использованные сочетания сегментов и страниц помещались в ассоциативную память из 16 элементов. Операционная система MULTICS уже давно не применяется, но виртуальная память всех процессоров Intel, начиная с 386, очень похожа на эту систему.

Рис. 4. Преобразование составного MULTICS-адреса в адрес основной памяти