Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.344

Однако сегментация существенно отличается от разбиения на страницы в следующем: размер страниц фиксирован, а размер сегментов — нет. На рис. 6.8, а показан пример физической памяти, в которой изначально содержится 5 сегментов. Посмотрим, что происходит, если сегмент 1 удаляется, а сегмент 7, который меньше по размеру, помещается на его место. В результате получается конфигурация, изображенная на рис. 6.8, б. Между сегментом 7 и сегментом 2 оказывается неиспользованная («пустая») область. Затем сегмент 4 заменяется сегментом 5 (рис. 6.8, в), а сегмент 3 — сегментом 6 (рис. 6.8, г). Через некоторое время память разделится на ряд областей, одни из которых будут содержать сегменты, а другие — пустоты. Это называется внешней фрагментацией (поскольку неиспользованное пространство попадает не в сегменты, а в пустоты между ними, то есть процесс происходит вне сегментов). Иногда внешнюю фрагментацию называют поклеточной разбивкой (checkerboarding).

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

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

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

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

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