Операционные системы 2011 (1114689), страница 56
Текст из файла (страница 56)
Чтобы несколько упростить эту задачу, зачастую используюттакой прием: при создании файла к запрошенному объему добавляют некотороеколичество свободного пространства (например, 10% от запрошенного объема), но этотже прием ведет к увеличению внутренней фрагментации. Еще одной немаловажнойпроблемой является фрагментация свободного пространства. Файловые системы,реализующие данную модель хранения файла, являются деградирующими: в ходеэксплуатации фрагментация свободного пространства увеличивается, и в итоге на дискеимеется множество мелких свободных участков, имеющих очень большой суммарныйобъем, но из-за своего небольшого размера эти участки использовать не представляетсявозможным.
Для разрешения этой проблемы необходимо запускать процесс компрессии(дефрагментации), который занимается тем, что сдвигает файлы с учетомзарезервированного для каждого файла «запаса», «прижимая» их друг к другу. Этаоперация трудоемкая, продолжительная и опасная, поскольку при перемещении файлавозможен сбой.206Name1Name3Name2Name5Name4Name7………Name6Рис. 107. Модель непрерывных файлов.Следующей моделью является модель файлов, имеющих организациюсвязанного списка (Рис. 108). В этой модели файл состоит из блоков, каждый из которыхвключает в себя две составляющие: данные, хранимые в файле, и ссылка на следующийблок файла. Эта модель также является достаточно простой, достаточно эффективной приорганизации последовательного доступа, а также эта модель решает проблемуфрагментации свободного пространства (за исключением блочной фрагментации).
Сдругой стороны, обозначенная модель не предполагает прямого доступа: чтобыобратиться к i-ому блоку, необходимо последовательно просмотреть все предыдущие.Также эта модель предполагает фрагментацию файла по диску, т.е. содержимое файламожет быть рассредоточено по всему дисковому пространству, а это означает, что припоследовательном считывании содержимого файла добавляется значительнаямеханическая составляющая, снижающая эффективность доступа. И еще однимнедостатком данной модели является то, что в каждом блоке присутствует и системная, ипользовательская информация. Возможна ситуация, что при необходимости считатьданные, объемом в один логический блок, реально происходит чтение двух блоков.…ййй1 блокфайла2 блокфайла0 блокфайлаα1α2α3Kй блокфайлаαkРис.
108. Модель файлов, имеющих организацию связанного списка.Другой подход иллюстрирует модель, основанная на использовании т.н. таблицыразмещения файлов (File Allocation Table — FAT, Рис. 109). В этой моделиоперационная система создает программную таблицу, количество строк в которойсовпадает с количеством блоков файловой системы, предназначенных для храненияпользовательских данных.
Также имеется отдельный каталог (или система каталогов), вкотором для каждого имени файла имеется запись, содержащая номер начального блока.Соответственно, таблица размещения имеет позиционную организацию: i-ая строкатаблицы хранит информацию о состоянии i-ого блока файловой системы, а, кроме того, вней указывается номер следующего блока файла. Чтобы получить список блоковфайловой системы, в которых хранится содержимое конкретного файла, необходимо поимени в указанном каталоге найти номер начального блока, а затем, последовательнообращаясь к таблице размещения и извлекая из каждой записи номер следующего блока,возможно построение искомого списка.
Данное решение выглядит эффективнеепредыдущего. Во-первых, в этом решении весь блок используется полностью дляхранения содержимого файла. Во-вторых, при открытии файла можно составить списокблоков данного файла и, следовательно, осуществлять прямой доступ. Заметим, что длямаксимальной эффективности необходимо, чтобы эта таблица целиком размещалась воперативной памяти, но для современных дисков, имеющих огромные объемы, данная207таблица будет иметь большой размер (например, для 60-ти гигабайтного раздела и блоков,размером 1 килобайт, потребуется 60 000 000*4(байта) = 240 мегабайт), что являетсяодним из недостатков рассматриваемой модели.
Другим недостатком являетсяограничение на размер файла в силу ограниченности длины списка блоков,принадлежащих данному файлу.0Ø1523Начальныйблок файла14506……k–1Номера блоковфайловой системыРис. 109. Таблица размещения файлов (FAT).Следующая модель — модель организации файловой системы с использованиемт.н. индексных узлов (дескрипторов). Принцип модели состоит в том, что в атрибутыфайла добавляется информация о номерах блоков файловой системы, в которыхразмещается содержимое файла.
Это означает, что при открытии файла можно сразуполучить перечень блоков. Соответственно, необходимость использования FAT-таблицыотпадает, зато, с другой стороны, при предельных размерах файла размер индексногодескриптора становится соизмеримым с размером FAT-таблицы.
Для разрешения этойпроблемы существует два принципиальных решения. Во-первых, это тривиальноеограничение на максимальный объем файла. Во-вторых, это построение иерархическойорганизации данных о блоках файла в индексном дескрипторе. В последнем случаевводятся иерархические уровни представления информации: часть (первые N) блоковперечисляются непосредственно в индексном узле, а оставшиеся представляются в видекосвенной ссылки. Это решение имеет следующие преимущества. Нет необходимости вразмещении в ОЗУ информации всей FAT-таблицы обо всех файлах системы.
В памятиразмещаются атрибуты, связанные только с открытыми файлами. При этом индексныйдескриптор имеет фиксированный размер, а файл может иметь практически«неограниченную» длину.4.1.6 Модели реализации каталоговСуществуют несколько подходов организации каталогов (Рис. 110). Во-первых,каталог может представляться в виде таблицы, у которой в одной колонке находятсяимена файлов, а в остальных — все атрибуты. Эта модель хороша тем, что всенеобходимые данные оперативно доступны, но размер записи в таблице каталога, да исама таблица, может быть большой (например, из-за большого числа атрибутов), чтовлечет за собой долгий поиск в каталоге. Другой подход заключается в том, что каталог208также представляется в виде таблицы, в которой один столбец хранит имена, а в другомхранится ссылка на системную таблицу, содержащую атрибуты соответствующего файла.Этот подход имеет дополнительное преимущество, заключающееся в том, что для разныхтипов файлов можно иметь различный набор атрибутов.Name1АтрибутыName1Name2АтрибутыName2Name3Атрибуты………Атрибутыфайла Name1……Атрибутыфайла Name2…Рис.
110. Модели организации каталогов.Одной из проблем при организации каталогов является проблема длины имени.Изначально эта проблема решалась достаточно просто: имя файла было ограниченошестью или восемью символами. В современных системах разрешается присваиватьфайлам достаточно длинные имена. И, как следствие, встает иная проблема: дляэффективной работы с каталогом необходимо, чтобы информация в каталогах хранилась всжатом виде, в т.ч. и имена файлов должны быть короткими. О некоторых решенияхданной проблемы речь пойдет ниже при обсуждении файловой системы ОС Unix.4.1.7 Соответствие имени файла и его содержимогоЕще один момент, на который стоит обратить внимание при рассмотренииорганизации файловых систем, — это проблема соответствия между именем файла исодержимым этого файла.Как отмечалось выше, у любого файла есть имя как отдельная характеристикафайла или же как один из атрибутов файла.
В различных файловых системах по-разномурешается указанная проблема соответствия имени и содержимого файла. Первыйочевидный подход заключается в том, что устанавливается взаимнооднозначноесоответствие, т.е. для каждого содержимого файла в системе существует единственноеимя, ассоциированное с этим содержимым, и обратно — для каждого имени существуетединственное содержимое.На сегодняшний день почти все современные файловые системы позволяютнарушать это взаимнооднозначное соответствие путем предоставления возможностиустановления для одного и того же содержимого файла двух и более имен. При этом,существует несколько моделей организации данного подхода.Первая модель — это симметричное (или равноправное) именование. В этомслучае с одним и тем же содержимым ассоциируется группа имен, каждое из которыхравноправное.
Это означает, что посредством любого из имен, ассоциированных с даннымсодержимым, можно выполнить все операции, и они будут выполнены одинаково. Такаямодель реализована в некоторых файловых системах посредством установления т.н.жесткой связи (Рис. 111). В этом случае среди атрибутов есть счетчик имен,ссылающихся на данное содержимое. Уничтожая файл с одним из этих имен,производится следующий порядок действий. Файловая система уменьшает счетчик именна единицу; если счетчик обнулился, то в этом случае удаляется содержимое, иначефайловая система удаляет только указанное имя файла из соответствующего каталога.Заметим, что при такой организации древовидность файловой системы (древовидностьразмещения файлов) нарушается, поскольку имена, ассоциированные с одним и тем же209содержимым, можно разместить в разных узлах дерева, т.е.
произвольных каталогахфайловой системы. Но сохраняется древовидность именования файлов.Name1Атрибуты файлаNameCount = 2СодержимоефайлаName2Рис. 111. Пример жесткой связи.Следующая модель организации — это «мягкая» ссылка, или символическая связь(хотя здесь лучше бы подошло название символьной связи, Рис. 112). Данное именованиеявляется несимметричным, суть его заключается в следующем. Пусть существуетсодержимое файла, с которым жесткой связью ассоциировано некоторое имя (Name 2).
Кэтому файлу теперь можно организовать доступ через файл-ссылку. Это означает, чтосоздается еще один файл некоторого специального типа (типа файл-ссылка), в атрибутахкоторого указывается его тип и то, что он ссылается на файл с именем Name2. Теперьможно работать с содержимым файла Name2 посредством косвенного доступа через файлссылку. Но некоторые операции с файлом-ссылкой будут происходить иначе.
Например,если вызывается операция удаления файла-ссылки, то удаляется именно файл-ссылка, а нефайл с именем Name2. Если же явно удалить файл Name2, то в этом случае файл-ссылкаокажется висячей ссылкой.Name1СодержимоефайлаName2Рис. 112. Пример символической связи.4.1.8 Координация использования пространства внешней памятиС точки зрения организации использования пространства внешней памятифайловой системой, существует несколько аспектов, на которые необходимо обратитьвнимание. Первый момент связан с проблемой выбора размера блока файловой системы.Задача определения оптимального размера блока не имеет четкого решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
