В. Столлингс - Операционные системы (1114679), страница 122
Текст из файла (страница 122)
Пожалуй, наиболее опТутим этот эффект в однопользовательской системе, но может существенно влиять и на совместно используемую систему. Для решения данной проблемы некоторые системы периодически производят уплотнение файлов (рис. 12.10). Индексированное размещение решает ряд проблем непрерывного и цепочечного размещения файлов. В этом случае в таблице размещения Файлов имеется отдельный одноуровневый индекс для каждого файла. Индекс содержит по одной записи для каждой порции файла.
Обычно индексы файла физически не хранятся в виде части таблицы размещения файлов; вместо этого индексы файла сохраняются в отдельном блоке„и в элементе таблицы размещения файла имеется указатель на этот блок. Размещение может основываться как на блоках Фиксированного размера (рис.
12.11), так и на блоках переменного размера Таблица размещения Файлов % с Таблица размещения Файлов рис. . 12.12). Поблочное расположение исключает внешнюю фрагментацию, в то |рамн мя как размещение по порциям переменного размера повышает степень ло.„ализации.
В любом случае время от времени может выполняться уплотнение файлов, которое позволяет уменьшить размер индекса при размещении с пор~иями переменной длины (но не при блочном распределении). Индексированное ,замещение поддерживает как последовательный, так и прямой доступ к файлу ~ потому является наиболее популярным видом Файлового размещения. Рис. 12.10. Цепочечное размещение файлов (после дефрагментации) Рис. 12.11. Индексированное размещение с порциями блоков Рис. 12.12.
Индексированное размещение с порциями переменного размера Управление свободным пространством Так же, как требуется управление пространством, выделяемым файлам, должно быть управляемым и пространство, которое в текущий момент не выделено ни одному файлу. Применяя любую из описанных выше технологий размещения файлов, нужно знать, какие блоки на диске доступны. Для этого в дополнение к таблице размещения Файлов нам необходима таблица дискового размещения. Рассмотрим ее возможные реализации. Битовые таблицы Д Этот метод использует вектор, содержащий по одному биту для каждого блока диска.
Каждый ноль соответствует свободному блоку, а каждая единыца — используемому. Например, для представленной на рис. 12.7 схемы необходим вектор длиной 35 бит, имеющий значение 00111000011111000011111111111011000 Одно из преимуществ битовой таблицы состоит в относительной простоте поиска одного свободного блока нли непрерывной группы свободных блоков. Второе преимущество — ее наименьший размер из всех возможных представлений. Однако даже такая таблица может оказаться внушительного размера. Объем памяти в байтах. необходимой для битовой карты, определяется следующим образом: Размер лиска в байтах 3 х Размер блока файловой системы Так, для диска объемом 16 Гбайт с блоками размером 512 байт битовая таблица займет около 4 Мбайт. Можем ли мы выделить под битовую таблицу ч Мбайт основной памятия Если да, то поиск в таблице может осуществляться без обращений к диску.
Однако даже при современных объемах памяти 4 Мбайт — это слишком много для одной Функции. Альтернативой является перенесение битовой таблицы на диск. Однако на диске для 4-Мбайтовой битовой таблицы понадобится около 8000 дисковых блоков. Мы не можем затрачивать усилия на поиск в таком объеме дискового пространства всякий раз при необходимости найти один блок. Но даже если битовая таблица размещена в основной памяти, то полный поиск в таблице может снизить производительность файловой системы до недопустимого уровня. Это особенно проявляется в случаях, когда диск практически заполнен, и свободными на нем остаются лишь несколько блоков. Соответственно, большинство файловых систем, использующих битовые таблицы, поддерживают вспомогательные структуры данных, резюмирующие содержимое поддиапазонов битовой таблицы.
Например, таблицу можно логически разделить на несколько поддиапазонов одинакового размера. Сводная таблица может включать информацию о количестве свободных блоков для каждого поддиапазона и наибольшем непрерывном блоке. При потребности в некотором количестве последовательных блоков файловая система может просканировать сводную таблицу для поиска соответствующего поддиапазона, а затем произвести конкретный поиск в нем. Цепочки свободных порций Свободные порции могут быть связаны в цепочки с использованием указателей и значений длины каждой свободной порции. Этот метод приводит к незначительным накладным расходам, поскольку нет необходимости в таблице дискового размещения — требуется только указать начало цепочки и длину первой порции. Этот способ подходит для всех методов Файлового размещения.
Если размещение происходит поблочно, то осуществляется выбор свободного блока в вершине цепочки и соответствующее изменение указателя на начало цепочки и значения длины. При размещении порциями переменной длины можно использовать алгоритм первого подходящего — извлекая по одному из цепочки заголовки порций до нахождения подходящей для нас. Описанный метод обладает и недостатками. После использования в течение некоторого времени диск становится довольно фрагментированным и "' большое число порций может иметь длину, сравнимую с одиночным блоком. Заметьте также, что при каждом размещении блока до того, как записывать в него данные, требуется произвести чтение блока для определения указате-;.
ля на следующий за ним свободный блок, который теперь будет первым в цепочке. Если при файловой операции необходимо сразу разместить большое количество отдельных блоков, это значительно замедлит процедуру создания „:: Файла. Точно так же расходуется очень много времени и при удалении высокофрагментированных файлов. Индексирование При индексировании свободное пространство рассматривается как файл (как и при размещении файлов, здесь используется индексная таблица)- Для ~ффективной работы индексы должны базироваться на порциях переменного размера, а не на блоках. Поэтому каждой свободной порции на диске соответствует один элемент в таблице.
Такой подход обеспечивает эффективную поддержку всех методов размещения файлов. Список свободных блоков В этом методе каждому блоку присваивается порядковый номер, а список номеров всех свободных блоков содержится в зарезервированной области дик~ В зависимости от размера диска для сохранения одного номера блока требуетс уется 24 или 32 бит.
Поэтому размер списка свободного блока в 24 или 32 раза болыпе размера соответствующей битовой таблицы и, таким образом, он должен хра ниться на диске, а не содержаться в основной памяти. Несмотря на это, предло женный метод довольно неплох. Рассмотрим следующие положения. 1. Дисковое пространство, отводимое под список свободных блоков, занимает меньше 1% общего пространства диска. При использовании 32-битовой нумерации блоков расход составляет 4 байт на каждый 512-байтовый блок.
2. Несмотря на то что список свободных блоков слишком велик для хранения в основной памяти, есть два эффективных метода хранения небольшой части списка в основной памяти. а. Список может рассматриваться как стек, первые несколько тысяч элементов которого содержатся в основной памяти. При размещении нового блока он извлекается из вершины стека (содержащейся в основной памяти). Аналогично, при освобождении блока его номер возвращается в стек. Передача данных между частями стека в основной памяти и на диске происходит только тогда, когда часть стека в основной памяти становится либо переполненной, либо пустой.
Поэтому число обращений к диску сведено к минимуму. б. Список может быть организован в виде очереди; в основной памяти находится несколько тысяч ее элементов — как из вершины, так и из хвоста очереди. Блок размещается путем извлечения первой записи из вершины очереди, а освобождается путем добавления его номера в конец очереди. Передача данных между диском и основной памятью происходит только в том случае, когда размещенная в основной памяти часть вершины очереди освобождается или когда хвост очереди в основной памяти переполняется.
В любой из описанных стратегий можно использовать Фоновый поток, который будет заниматься сортировкой списка в основной памяти с целью облегчения непрерывного распределения. Нид8жнОсть Рассмотрим следующий сценарий. 1. Пользователь А производит запрос на размещение для добавления информации к существующему Файлу.
2. Запрос принимается, и таблицы дискового и файлового размещения записей обновляются в основной памяти, но не на диске. 3. В системе происходит сбой и последующая перезагрузка. 4. Пользователь Б производит запрос на размещение файла, и Файл размещается в пространстве, перекрывающемся с последним размещением по запросу пользователя А. Глава 12 Уцрнвлени~ фяилями Пользователь А обращается к выделенной ему ранее (а теперь занятой пользователем Б) порции с использованием ссылки, сохраненной в файле пользователя А. Проблема возникает из-за того, что для повышения эффективности система ржала - . а копию таблицы дискового размещения в основной памяти.
Чтобы ,отвратить ошибки такого типа, при запросе на размещение файла следует олнпть ряд действий. Заблокировать таблицу дискового размещения на диске. Это предотвратит внесение изменений в таблицу другими пользователями до завершения обработки данного запроса. Выполнить поиск доступного пространства в таблице дискового размещения. Предполагается, что копия таблицы дискового размещения всегда содержится в основной памяти. Если это не так, то сначала таблица должна быть считана в основную память. Распределить пространство, обновить таблицу дискового размещения в памяти и на диске.
При цепочечиом дисковом размещении следует также обновить указатели на диске. Обновить таблицу размещения Файлов в основной памяти и на диске. Деблокировать таблицу дискового размещения. Этот метод предохраняет от ошибок, но при частом распределении малень-:",. ; порций приводит к существенному снижению производительности. Чтобы ' ньшить этот эффект, можно использовать пакетную схему размещения. В", и случае для размещения выделяется пакет свободных порций на диске. Со- '1.' етствующие порции на диске помечаются как используемые. Пакетное раз- ...„ цение может происходить в основной памяти. При исчерпании пакета обнов- ' тся таблица размещения файлов на диске и происходит выделение нового па- '...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
