Операционные системы. Теория и практика. Замятин А.В. - 129 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

129
Например, непрерывное выделение использовано в ОС IBM/CMS,
RSX-11 (для исполняемых файлов).
Основная проблема, в связи с которой этот способ мало распро-
странен – трудности в поиске места для нового файла. В процессе экс-
плуатации диск представляет собой некоторую совокупность свобод-
ных и занятых фрагментов. Проблема непрерывного расположения мо-
жет рассматриваться как частный случай более общей проблемы выде-
ления n блоков из списка свободных фрагментов. Наиболее распро-
страненные стратегии решения этой проблемы – выбор первого подхо-
дящего по размеру блока (англ. first fit), наиболее подходящего, т.е. того,
при размещении в котором наиболее тесно (англ. best fit), и наименее
подходящего, т.е. выбирается наибольший блок (англ. worst fit).
Способ характеризуется наличием существенной внешней фраг-
ментации (в большей или меньшей степени – в зависимости от размера
диска и среднего размера файла). Кроме того, непрерывное распределе-
ние внешней памяти не применимо до тех пор, пока не известен макси-
мальный размер файла. Иногда размер выходного файла оценить легко
(при копировании), но чаще – трудно. Если места не достаточно, то
пользовательская программа может быть приостановлена, предполагая
выделение дополнительного места для файла при последующем переза-
пуске. Некоторые ОС используют модифицированный вариант непре-
рывного выделения: «основные блоки файла» + «резервные блоки». Од-
нако с выделением блоков из резерва возникают те же проблемы, так
как возникает задача выделения непрерывной последовательности бло-
ков диска теперь уже из совокупности резервных блоков.
Выделение связным списком. Метод распределения блоков в виде
связного списка решает основную проблему непрерывного выделения,
то есть устраняет внешнюю фрагментацию (рис. 39). Каждый файл –
связный список блоков диска. Запись в директории содержит указатель
на первый и последний блоки файла. Каждый блок содержит указатель
на следующий блок.
Файл А
Блок 0
Блок 1
Блок 2
Блок 3
Блок 0
Блок 1
Блок 2
Файл В
4 7 2 12 6 3 11
Адреса блоков диска
Рисунок 39 – Хранение файлов в связных списках дисковых блоков
Внешняя фрагментация для данного метода отсутствует. Любой
свободный блок может быть использован для удовлетворения запроса.

Страницы