Файловые системы, страница 2

Приведем алгоритм работы со свободным адреснымпространством (алгоритм поиска свободных блоков на диске).Если S_NFREE!=0, то выбирается блок из массиваS_FREE[S_NFREE]. Далее S_NFREE:=S_NFREE-1. В противномслучае, т.е., когдаS_NFREE=0, первый элемент массива S_FREEуказывает на блок, содержащий список еще 49 свободных блоков,который считывается в суперблок. Список всех свободных блоковзаканчивается в том случае, когда в первом элементе массива S_FREEпоявляется ноль (список исчерпан).При освобождении блоков соответствующие номера записываются вмассив S_FREE[S_NFREE+1] и S_NFREE:=S_NFREE+1.После достижения S_NFREE значения 50, содержимое массиваS_FREE копируется в свободный блок, а его адрес записывается вэлемент S_FREE[0].6S_NFREE0149…S_FREE:Номера свободных блоков0149…Номера свободных блоков0149…Номера свободных блоковРис.4 Список свободных блоков.В силу того, что суперблок практически всегда находится в памяти,имеется возможность быстро без обращения к диску занять до 49 свободныхблоков.

С другой стороны, освобождаемые блоки легко подсоединяются ксписку свободных. Рассмотренный алгоритм работы со свободнымпространством ФС предполагает, что первым использованным блоком из числасвободных будет последний освободившийся.Последняя область - область выгрузки (своппинга). Используется ОСдля размещения образов памяти откаченных процессов, а также дляразмещения процессов, файлы которых специфицированы t-битом.

Всовременных реализациях для области своппинга может быть организованаспециализированная ФС.1.3.2 Индексный дескриптор файла (ИД).ИД - это основной элемент, описывающий атрибуты файла. Каждыйфайл определяется ИД, который содержит всю необходимую информацию оданном файле. ИД состоит из некоторого количества полей, в частности: поле, содержащее биты, характеризующие тип файла, его привилегии и кодзащиты. Например, восьмеричная маска 040000 - означает, что файл являетсякаталогом, 060000 - означает, что это блок-ориентированный специальныйфайл, 000020 - дано разрешение на запись для владельца файла и так далее. поле, содержащее количество ссылок из каталогов к ИД.Отметим, что каталоги содержат список имен файлов и ссылки наИД. Одному ИД могут соответствовать несколько имен файлов (эти именамогут встречаться в произвольных местах ФС). Каждая новая ссылка к ИД,отмечается в данном поле, что позволяет ФС следить за занятостью файла. Вкорректной ФС должно быть полное соответствие между числом ссылок вданном поле и числом записей, относящихся к данному ИД.

Как только этотсчетчик становится равным нулю, ИД освобождается, а дисковоепространство может быть использовано для записи других файлов. два поля, предназначенных для определения привилегий доступа к файлу.Здесь содержатся коды идентификации пользователя и его группы,создавшей файл. поле, служащее для записи длины файла. поле, фиксирующее время последнего обращения к файлу.7 два поля, предназначенные для фиксации времени создания и последнеймодификации файла. поле, предназначенное для адресации данных файла на диске.Расположениефайла задается списком его блоков.

Это снимаетпроблемы непрерывных файловых систем, т.е. систем, где блоки файларасполагаются последовательно. Таким образом реально блоки файла могутбыть разбросаны по диску, но логически они образуют цепочку, содержащуювесь набор данных. Ключом, задающим подобное расположение служит списокиз 13 номеров блоков на диске, хранящихся в ИД. Первые десять указывают надесять блоков некоторого файла. Если файл занимает более 10 блоков, то 11элемент указывает на косвенный блок, содержащий до 128 адресовдополнительных блоков файла (это еще 70656 байт). Большие файлыиспользуют 12 элемент, который указывает на блок, содержащий 128указателей на блоки, каждый из которых содержит по 128 адресов блоковфайла.

Еще в больших файлах аналогично используется 13 элемент.Трехкратная косвенная адресация позволяет создавать файлы длиной(10+128+128*128+128*128*128)*512 байт. Таким образом, если файл меньше512 байт, то необходимо одно обращение к диску, если длина файла находитсяв пределах 512-70565 байт, то - два и так далее. Приведенный способадресации позволяет иметь прямой и быстрый доступ к файлам. Этавозможность также усиливается кэшированием диска, позволяющим хранить впамяти наиболее используемые блоки . Важно отметить, что при открытиифайла соответствующий ИД считывается в память и системе становятсядоступны все номера блоков данного файла. Кроме того, для одного и того жефайла, открываемого несколько раз, в памяти находится только один ИД.Система фиксирует число открытий данного файла и, когда этот счетчикобнуляется, резидентный образ ИД переписывается на диск. Если при этомизменений в файле не было и не модифицировался ИД, то запись невыполняется.

Указанные особенности существенно влияют на эффективностьфайловой системы.Индексный дескрипторАдресное поле10 111…10…12811…1288…1…128…12813128…128128112…Рис.5 Адресация данных файла.…128…8Отметим, что алгоритм для поиска свободных ИД в массиве S_INODE,суперблока, похож на алгоритм для поиска свободных блоков на диске.Отличие состоит в том, что после исчерпания массива, он дополняется путемлинейного поиска свободных ИД в блоке, где хранятся свободные ИД.

Т.е. непроисходит считывание заранее подготовленных записей. Это оправдано, ибосоздание и удаление файла происходит гораздо реже, нежели занятие иосвобождение новых блоков файла.1.4. Основные типы файлов и их свойства.1.4.1. Предварительное замечание.Система не накладывает на информацию, хранимую в файле, никакихограничений или структурных требований.1.4.2. Рабочие файлы.Данные файлы размещаются на диске и содержат ту информацию,которую занес в него пользователь или которая получилась в результате работыкоманд системы, трансляторов, редакторов и так далее. Все файлы так илииначе - двоичные. При этом в зависимости от интерпретации файл можетсодержать исходный текст программы, главу книги , готовый к исполнениюкод, словом все, что необходимо сохранить для дальнейшего использования.Важно то, что тип файла определяется не файловой системой.1.4.3.

Каталоги.Каталог - это файл, осуществляющий связь между именами файлов исобственно файлами, создавая тем самым структуру ФС. В каталог могутвходить имена рабочих файлов, каталоги и специальные файлы.Выше говорилось, что существует соглашение об именовании файла,т.е. полное имя представляет собой путь от корневого каталога через именакаталогов до требуемого файла.

При создании каталога в нем образуются двастандартных файла. Имя файла ‘.’в каждом каталоге связано с самимкаталогом, а имя ‘..’ с родительским каталогом. С помощью имени ‘..‘,имеющемся в каждом каталоге, можно сделать шаг вверх в иерархии ФС.Каталог считается пустым если он содержит только эти два файла.Внутреннее устройство каталога представляет собой массив cтруктур,состоящих из двух элементов. Первый элемент - номер индексногодескриптора, а второе - имя файла. Таким образом, каталог - это массив,состоящий из списка имен файлов и ссылок на ИД.Видно, что при такой реализации имя файла “отделено” от других егоатрибутов.

Это позволяет, в частности, один и тот же файл внести в несколькокаталогов. При этом данный файл может иметь разные имена в разныхкаталогах, но ссылаться они будут на один и тот же ИД, который являетсяключом для доступа к данным файла. При обсуждении понятия ИД говорилось,что каждая новая ссылка к ИД отмечается в специальном поле. Рассмотримпример, иллюстрирующий связь файлов с каталогами (рис.6-7).9RootTextUsr UnixProg.c PeterBinBinDevLibРис.6 Фрагмент файловой системыИндексные дескрипторы… 17111211737614...textusrunixbindev… 2117125193421...peterbinlibprog.cРис.

7. Связь файлов с каталогами.В приведенном примере необходимо подчеркнуть следующие моменты.Первый - ИД с номером 1 всегда содержит атрибуты корневого каталога.Файлы с именами “.” и “..” в каталоге root ссылаются на ИД с номером 1, т.е.сами на себя. Имена text и prog.c ссылаются на один и тот же ИД, т.е.

на одини тот же файл. В частности, если задать команду удаления файлаrm prog.c,то реально произойдет удаление не файла, а строки в соответствующемкаталоге (т.е. связи). Если задать далее командуrm text,то произойдет ликвидация последней связи, а, следовательно, ИД и самогофайла. Далее, как отмечалось выше, ИД объявляются свободными, а блоки,занятые данными файла, объявляются свободными.Траектория, которая задается полным именем, представляет собойпереходы между каталогами и ИД. Рассмотрим, к примеру, полное имя ‘../а/b’.Это имя есть путь из текущего каталога в его родительский каталог, далее вподкаталог ‘а’ родительского каталога и , наконец, к файлу с именем ‘b’ изкаталога ‘а’.