The design of the UNIX Operating System 76 страница
Кроме того, непрерывное распределение внешней памяти неприменимо до тех пор, пока неизвестен мак-симальный размер файла. Иногда размер выходного файла оценить легко (при копировании). Чаще, од-нако, это трудно сделать, особенно в тех случаях, когда размер файла меняется. Если места не хватило, то пользовательская программа может быть приостановлена с учетом выделения дополнительного места для файла при последующем рестарте . Некоторые ОС используют модифицированный вариант непре-рывного выделения - основные блоки файла + резервные блоки. Однако с выделением блоков из резерва возникают те же проблемы, так как приходится решать задачу выделения непрерывной последовательно-сти блоков диска теперь уже из совокупности резервных блоков.
|
|
|
Единственным приемлемым решением перечисленных проблем является периодическое уплотнение со-держимого внешней памяти , или "сборка мусора", цель которой состоит в объединении свободных уча-стков в один большой блок. Но это дорогостоящая операция, которую невозможно осуществлять слиш-ком часто.
|
|
|
Таким образом, когда содержимое диска постоянно изменяется, данный метод нерационален. Однако для стационарных файловых систем,например для файловых систем компакт-дисков,он вполне пригоден.
|
|
|
Связный список
Внешняя фрагментация - основная проблема рассмотренного выше метода - может быть устранена за счет представления файла в виде связного списка блоков диска. Запись в директории содержит указатель на первый и последний блоки файла (иногда в качестве варианта используется специальный знак конца файла - EOF). Каждый блок содержит указатель на следующий блок (см. рис. 12.2).
|
|
|
| Основы операционных систем | 111 |
Рис. 12.2. Хранение файла в виде связного списка дисковых блоков
Внешняя фрагментация для данного метода отсутствует. Любой свободный блок может быть использо-ван для удовлетворения запроса. Заметим, что нет необходимости декларировать размер файла в момент создания. Файл может расти неограниченно.
Связное выделение имеет, однако, несколько существенных недостатков.
Во-первых, при прямом доступе к файлу для поиска i -го блока нужно осуществить несколько обращений к диску, последовательно считывая блоки от 1 до i-1, то есть выборка логически смежных записей, кото-рые занимают физически несмежные секторы, может требовать много времени. Здесь мы теряем все пре-имущества прямого доступа к файлу.
Во-вторых , данный способ не очень надежен. Наличие дефектного блока в списке приводит к потере ин-формации в оставшейся части файла и потенциально к потере дискового пространства, отведенного под этот файл.
Наконец , для указателя на следующий блок внутри блока нужно выделить место, что не всегда удобно. Емкость блока, традиционно являющаяся степенью двойки (многие программы читают и пишут блоками по степеням двойки), таким образом, перестает быть степенью двойки, так как указатель отбирает не-сколько байтов.
Поэтому метод связного списка обычно в чистом виде не используется.
Таблица отображения файлов
Одним из вариантов предыдущего способа является хранение указателей не в дисковых блоках, а в ин-дексной таблице в памяти, которая называется таблицей отображения файлов (FAT - file allocation table) (см. рис. 12.3). Этой схемы придерживаются многие ОС (MS-DOS, OS/2, MS Windows и др.)
По-прежнему существенно, что запись в директории содержит только ссылку на первый блок. Далее при помощи таблицы FAT можно локализовать блоки файла независимо от его размера. В тех строках табли-цы, которые соответствуют последним блокам файлов, обычно записывается некоторое граничное значе-ние, например EOF.
Дата добавления: 2021-01-21; просмотров: 105; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!