Оба алгоритма сокращают средний размер свободного фрагмента. Всякий раз, когда сегмент помещается в свободный фрагмент, превышающий по размеру этот сегмент, что бывает практически всегда (точные попадания очень редки), свободный фрагмент делится на две части. Одну часть занимает сегмент, а вторая часть превращается в новый свободный фрагмент, который по определению меньше, чем прежний. Без дефрагментации (превращения всех маленьких пустот в одну большую) оба алгоритма в конечном итоге приведут к заполнению памяти пустотами, слишком маленькими даже для самого мелкого сегмента.
Опишем один из таких процессов. Всякий раз, когда сегмент удаляется из памяти, а одна или обе соседние области этого сегмента — не сегменты, а пустоты, смежные пустоты можно объединить. Если на рис. 6.8, г удалить сегмент 5, то две соседние пустоты, объединившись с фрагментом размером 4 Кбайт, который занимал удаленный сегмент, дадут в результате свободный фрагмент размером уже 11 Кбайт.
В начале этого подраздела мы говорили о том, что реализовать сегментацию можно двумя способами: подкачкой сегментов и разбиением на страницы. До сих пор речь шла о подкачке. При таком подходе по необходимости между памятью и диском перемещаются целые сегменты. Второй способ реализации — разделить каждый сегмент на страницы фиксированного размера и вызывать их по требованию. В этом случае одни страницы сегмента могут находиться в памяти, а другие — на диске. Чтобы разбить сегмент на страницы, для каждого сегмента нужна отдельная таблица страниц. Поскольку сегмент представляет собой линейное адресное пространство, все варианты разбиения на страницы, которые мы до сих пор рассматривали, применимы к любому сегменту. Единственное отличие состоит в том, что каждый сегмент получает отдельную таблицу страниц.
MULTICS (Multiplexed Information and Computing Service — служба общей информации и вычислений) — это древняя операционная система, совмещающая сегментацию с разбиением на страницы. Она была разработана Массачусетсом технологическим институтом совместно с компаниями Bell Labs и General Electric [49, 155]. Адреса в MULTICS состоят из двух частей: номера сегмента и адреса внутри сегмента. Для каждого процесса существовал дескрипторный сегмент, содержащий дескрипторы каждого сегмента. При аппаратном получении виртуального адреса для нахождения дескриптора нужного сегмента номер сегмента использовался в качестве индекса в дескрипторном сегменте (рис. 6.9). Дескриптор указывал на таблицу страниц, что позволяло разбивать на страницы каждый сегмент обычным способом. Для повышения производительности недавно использованные сочетания сегментов и страниц помещались в ассоциативную память из 16 элементов. Операционная система MULTICS уже давно не применяется, но виртуальная память всех процессоров Intel, начиная с 386, очень похожа на эту систему.
Рис. 6.9. Преобразование составного MULTICS-адреса в адрес основной памяти
Виртуальная память Pentium 4
Pentium 4 имеет сложную систему виртуальной памяти, которая поддерживает вызов страниц по требованию, чистую сегментацию и сегментацию с разбиением на страницы. Виртуальная память состоит из двух таблиц: LDT (Local Descriptor Table — локальная таблица дескрипторов) и GDT (Global Descriptor Table — глобальная таблица дескрипторов). Каждая программа имеет собственную локальную таблицу дескрипторов, а единственная глобальная таблица дескрипторов разделяется всеми программами компьютера. Локальная таблица дескрипторов описывает локальные сегменты каждой программы (ее код, данные, стек и т. д.),