2011. Машбук (1114722), страница 55
Текст из файла (страница 55)
Данное решение выглядит эффективнеепредыдущего. Во-первых, в этом решении весь блок используется полностью дляхранения содержимого файла. Во-вторых, при открытии файла можно составить списокблоков данного файла и, следовательно, осуществлять прямой доступ. Заметим, что длямаксимальной эффективности необходимо, чтобы эта таблица целиком размещалась воперативной памяти, но для современных дисков, имеющих огромные объемы, данная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 Координация использования пространства внешней памятиС точки зрения организации использования пространства внешней памятифайловой системой, существует несколько аспектов, на которые необходимо обратитьвнимание. Первый момент связан с проблемой выбора размера блока файловой системы.Задача определения оптимального размера блока не имеет четкого решения. Еслифайловая система предоставляет возможность квотировать размер блока, то надоучитывать, что больший размер блока ведет к увеличению производительности файловойсистемы (поскольку данные файла оказываются локализованными на жестком диске, изчего следует, что при доступе снижается количество перемещений считывающейголовки).
Но недостатком является то, что чем больше размер блока, тем вышевнутренняя фрагментация, а, следовательно, возникает неэффективность использованияпространства ВЗУ (если, блок имеет размер, например, 1024 байт, а файл занимает 1 байт,то теряются 1023 байта). Альтернативой являются блоки меньшего размера, которыеснижают внутреннюю фрагментацию, но при выборе меньшего размера блокаповышаются накладные расходы при доступе к файлу в связи фрагментация файла подиску.Еще одна проблема, на которую стоит обратить внимание, — это проблема учетасвободных блоков файловой системы. Здесь тоже существует несколько подходоврешения, среди которых нельзя выбрать наилучший: каждый из подходов имеет своидостоинства и недостатки.Первый подход заключается в том, что вся совокупность свободных блоковпомещается в единый список, т.е. номера свободных блоков образуют связный список,210который располагается в нескольких блоках файловой системы.
Для более эффективнойработы первый блок, содержащий начальную часть списка, должен располагаться в ОЗУ,чтобы файловая система могла к нему оперативно обращаться. Заметим, что список можетдостигать больших размеров: если размер блока 1 Кбайт, т.е. его можно представить ввиде 256 четырехбайтных слов, то такой блок может содержать в себе 255 номеровсвободных блоков и одну ссылку на следующий блок со списком, тогда для жесткогодиска, емкостью 16 Гбайт, потребуется 16794 блока. Но размер списка не столь важен,поскольку по мере использования свободных блоков этот список сокращается, при этомосвобождающиеся блоки, хранившие указанный список, ничем не отличаются от другихсвободных блоков файловой системы, а значит, их можно использовать для храненияфайловых данных.Вторая модель основана на использовании битовых массивов. В этом случаекаждому блоку файловой системе ставится в соответствие двоичный разряд,сигнализирующий о незанятости данного блока.
Для организации данной моделинеобходимо подсчитать количество блоков файловой системы, рассчитать количестворазрядов массива, а также реализовать механизм пересчета номера разряда в номер блокаи наоборот. Заметим, что операция пересчета достаточно трудоемка, к тому же эта модельтребует выделения под массив стационарного ресурса: так, для 16-ти гигабайтногожесткого диска потребуется 2048 блоков для хранения битового массива.4.1.9 Квотирование пространства файловой системыКак отмечалось выше, файловая система должна обеспечивать контрольиспользования двух видов системных ресурсов — это регистрация файлов в каталогах(т.е. контроль количества имен файлов, которое можно зарегистрировать в каталоге) иконтроль свободного пространства (чтобы не возникла ситуация, когда один процессзаполнил все свободное пространство, тем самым не давая другим пользователямвозможность сохранять свои данные).
Для решения поставленных задач в файловойсистеме вводятся квотирование имен (т.е. числа) файлов и квотирование блоков(Рис. 113).В общем случае модель квотирования может иметь два типа лимитов: жесткий игибкий. Для каждого пользователя при его регистрации в системе определяются два типаквот. Жесткий лимит — это количество имен в каталогах или количество блоковфайловой системы, которое пользователь превзойти не может: если происходитпревышение жесткого лимита, работа пользователя в системе блокируется.