Добавлен: 29.10.2018
Просмотров: 48125
Скачиваний: 190
366
Глава 4. Файловые системы
Подобно i-узлу на рис. 4.10 i-узлы системы UNIX содержат некоторые атрибуты, ко-
торые содержат размер файла, три указателя времени (создания, последнего доступа
и последнего изменения), идентификатор владельца, группы, информацию о защите
и счетчик указывающих на этот i-узел записей в каталогах. Последнее поле необходимо
для установления связей. При добавлении к i-узлу новой связи счетчик в i-узле уве-
личивается на единицу. При удалении связи счетчик в i-узле уменьшается на единицу.
Когда значение счетчика достигает нуля, i-узел освобождается, а дисковые блоки воз-
вращаются в список свободных блоков.
Для учета дисковых блоков файла используется общий принцип, показанный на
рис. 4.10, позволяющий работать с очень большими файлами. Первые 10 дисковых
адресов хранятся в самом i-узле, поэтому для небольших файлов вся необходимая ин-
формация содержится непосредственно в i-узле, считываемом с диска в оперативную
память при открытии файла. Для файлов большего размера один из адресов в i-узле пред-
ставляет собой адрес блока диска, называемого однократным косвенным блоком. Этот
блок содержит дополнительные дисковые адреса. Если и этого недостаточно, использу-
ется другой адрес в i-узле, называемый двукратным косвенным блоком и содержащий
адрес блока, в котором хранятся адреса однократных косвенных блоков. Если и этого
мало, используется трехкратный косвенный блок. Полная схема показана на рис. 4.28.
Рис. 4.28. I-узел UNIX
При открытии файла файловая система по предоставленному имени файла должна
найти его блоки на диске. Рассмотрим, как происходит поиск по абсолютному имени
/usr/ast/mbox
. В этом примере будет использоваться файловая система UNIX, хотя для
всех иерархических каталоговых систем применяется в основном такой же алгоритм.
Сначала файловая система определяет местоположение корневого каталога. В системе
UNIX его i-узел размещается в фиксированном месте на диске. По этому i-узлу система
4.5. Примеры файловых систем
367
определяет местоположение корневого каталога, который может находиться в любом
месте диска, в данном примере — в блоке 1.
Затем файловая система считывает корневой каталог и ищет в нем первый компонент
пути,
usr
, чтобы определить номер i-узла файла
/usr
. Определить местоположение
i-узла по его номеру несложно, поскольку у каждого из них есть свое фиксированное
место на диске. По этому i-узлу файловая система определяет местоположение ката-
лога для
/usr
и ищет в нем следующий компонент,
ast
. Найдя описатель
ast
, файловая
система получает i-узел для каталога
/usr/ast
. По этому i-узлу она может найти сам
каталог и искать в нем файл
mbox
. При этом i-узел файла
mbox
считывается в память
и остается там, пока файл не будет закрыт. Процесс поиска показан на рис. 4.29.
Рис. 4.29. Этапы поиска /usr/ast/mbox
Поиск по относительным именам путей ведется так же, как и по абсолютным, с той лишь
разницей, что алгоритм начинает работу не с корневого, а с рабочего каталога. В каждом
каталоге есть элементы «.» и «..», помещаемые в каталог в момент его создания. Элемент
«.» содержит номер i-узла текущего каталога, а элемент «..» — номер i-узла родитель-
ского каталога. Таким образом, процедура, ведущая поиск файла
../dick/prog.c
, просто
находит «..» в рабочем каталоге, разыскивает в нем номер i-узла родительского каталога,
в котором ищет описатель каталога
dick
. Для обработки этих имен не требуется никакого
специального механизма. Что касается системы каталогов, она представляет собой обык-
новенные ASCII-строки, ничем не отличающиеся от любых других имен. Единственная
тонкость в том, что элемент «..» в корневом каталоге указывает на сам этот каталог.
4.5.3. Файловые системы компакт-дисков
Давайте в качестве последнего примера файловой системы рассмотрим системы, ко-
торые используются на компакт-дисках. Это очень простые системы, поскольку они
были разработаны для носителей, предназначенных только для чтения данных. Кроме
368
Глава 4. Файловые системы
всего прочего, в них не отслеживаются свободные блоки, поскольку файлы на компакт-
дисках не могут освобождаться или добавляться после того, как диск был произведен.
Далее мы рассмотрим основной тип файловой системы компакт-дисков и два расши-
рения этого типа. Хотя компакт-диски в настоящее время уже устарели, они все же
отличаются простотой, и файловые системы, используемые на DVD- и Blu-ray-дисках,
основаны на тех файловых системах, которые использовались на компакт-дисках.
Через несколько лет после появления первого компакт-диска был представлен записы-
ваемый компакт-диск — CD-R (CD Recordable). В отличие от простого компакт-диска,
на него можно было добавлять файлы после первой записи, но они просто добавлялись
к концу записываемого компакт-диска. Файлы никогда не удалялись (хотя каталог мог
быть обновлен, чтобы скрыть существующие файлы). С появлением этой файловой
системы «только для добавления» основные свойства не изменились. В частности,
все свободное пространство представляло собой один непрерывный участок в конце
компакт-диска.
Файловая система ISO 9660
Наиболее распространенный международный стандарт ISO 9660 для файловых систем
компакт-дисков был принят в 1988 году. По сути, каждый компакт-диск, имеющийся
сейчас на рынке, совместим с этим стандартом, а иногда и с теми расширениями, кото-
рые будут рассмотрены чуть позже. Одна из целей принятия этого стандарта — сделать
каждый компакт-диск читаемым на любом компьютере, независимо от использующего-
ся порядка следования байтов и независимо от используемой операционной системы.
Это привело к тому, что на файловую систему были наложены некоторые ограничения,
чтобы она могла читаться в среде слабых операционных систем, использовавшихся в то
время (например, в MS-DOS).
У компакт-диска отсутствуют концентрические цилиндры, имеющиеся у магнитных
дисков. Вместо них используется одна протяженная спираль с записью битов в линей-
ной последовательности (хотя возможность перемещения головок поперек спирали со-
хранилась). Биты на протяжении этой спирали разбиты на логические блоки (которые
называют также логическими секторами) по 2352 байта. Некоторые из них предназна-
чены для преамбул, коррекции ошибок и других служебных данных. Полезная часть
каждого логического блока занимает 2048 байт. Когда компакт-диск используется для
музыкальных записей, на нем имеются начальные, конечные и промежуточные пустые
места, которые не используются для компакт-дисков с данными. Зачастую позиция
блока на спирали приводится в минутах и секундах. Ее можно преобразовать в номер
линейного блока, используя соотношение 1 с = 75 блоков.
Стандарт ISO 9660 поддерживает также наборы компакт дисков до 2
16
–1 компакт-
диска в наборе. Отдельный компакт-диск также может быть разбит на несколько
логических томов (разделов). Но далее мы сконцентрируемся на стандарте ISO 9660
для одного не разбитого на разделы компакт-диска.
Каждый компакт-диск начинается с 16 блоков, чья функция не определена стандартом
ISO 9660. Производитель компакт-диска может использовать эту область для программы
самозагрузки, позволяющей компьютерам запускаться с компакт-диска, или в каких-
нибудь других целях. Далее следует один блок, содержащий основной описатель тома,
в котором хранится некоторая общая информация о компакт-диске. В нее включены
идентификатор системы (32 байта), идентификатор тома (32 байта), идентификатор
4.5. Примеры файловых систем
369
издателя (128 байт) и идентификатор того, кто подготовил данные (128 байт). Произ-
водитель диска может заполнить эти поля по своему усмотрению, за исключением того,
что в них для обеспечения совместимости с различными платформами должны быть
буквы в верхнем регистре, цифры и весьма ограниченное количество знаков препинания.
Основной описатель тома содержит также имена трех файлов, в которых могут храниться
краткий обзор, уведомление об авторских правах и библиографическая информация
соответственно. Кроме того, в этом блоке содержатся определенные ключевые числа,
включающие размер логического блока (как правило, 2048, однако в определенных
случаях могут использоваться более крупные блоки, размер которых равен степеням
числа 2, например 4096, 8192 и т. д.), количество блоков на компакт-диске, а также дата
создания и дата окончания срока службы диска. И наконец, основной описатель тома
также содержит описатель корневого каталога, что позволяет найти этот каталог на
компакт-диске (то есть определить номер блока, содержащего начало каталога). Из этого
каталога можно получить местоположение всех остальных элементов файловой системы.
Помимо основного описателя тома компакт-диск может содержать дополнительный
описатель тома. В нем хранится информация, подобная той, что хранится в основном
описателе, но сейчас нас это интересовать не будет.
Что касается корневого и всех остальных каталогов, то они состоят из переменного ко-
личества записей, последняя из которых содержит бит, который помечает ее последней.
Сами по себе записи каталогов также имеют переменную длину. Каждая запись катало-
га состоит из 10–12 полей, некоторые из них имеют ASCII-формат, а остальные — фор-
мат двоичного числа. Двоичные поля кодируются дважды, один раз в формате прямого
порядка байтов (используемого, к примеру, на машинах Pentium), а второй — в формате
обратного порядка байтов (используемого, к примеру, на машинах SPARC). Таким об-
разом, 16-разрядное число использует 4 байта, а 32-разрядное — 8 байт.
Использование подобного избыточного кодирования было обусловлено стремлением
не ущемить при разработке стандарта ничьих интересов. Если бы стандарт навязывал
прямой порядок байтов, то представители компаний, в чьей продукции использовался
обратный порядок байтов, почувствовали бы себя гражданами второго сорта и не при-
няли бы этот стандарт. Таким образом, эмоциональная составляющая компакт-дисков
может быть подсчитана и измерена в килобайтах потерянного пространства.
Формат записи каталога стандарта ISO 9660 показан на рис. 4.30. Поскольку запись
каталога имеет переменную длину, первое поле представлено байтом, сообщающим
о длине записи. Чтобы избежать любой неопределенности, установлено, что в этом
байте старший бит размещается слева.
Записи каталогов могут дополнительно иметь расширенные атрибуты. Если такая
возможность используется, то во втором байте указывается длина расширенных
атрибутов.
Затем следует номер начального блока самого файла. Файлы хранятся в виде непре-
рывной череды блоков, поэтому размещение файла полностью определяется началь-
ным блоком и размером, который содержится в следующем поле.
Дата и время записи компакт-диска хранятся в следующем поле в отдельных байтах
для года, месяца, дня, часа, минуты, секунды и часового пояса
1
. Летоисчисление для
1
Точнее, дата и время создания файла. — Примеч. ред.
370
Глава 4. Файловые системы
Рис. 4.30. Запись каталога в стандарте ISO 9660
компакт-дисков начинается с 1900 года, а это значит, что компакт-диски подвержены
проблеме 2156 года, поскольку за 2155 годом для них последует год 1900. Если бы от-
счет велся с 1988 года (когда был принят стандарт), то проблема была бы отложена до
2244 года и в запасе было бы еще 88 лет.
Поле флажков содержит несколько битов разного назначения, включая бит скрытия
записи в выводах каталога (свойство, позаимствованное у MS-DOS), бит, позволяю-
щий отличить запись, относящуюся к файлу, от записи, относящейся к каталогу, бит,
позволяющий использовать расширенные атрибуты, и бит, помечающий последнюю
запись в каталоге. В этом поле имеются и несколько других битов, но здесь они рас-
сматриваться не будут. Следующее поле относится к чередующимся частям файлов,
но в простейшей версии ISO 9660 это свойство не используется, поэтому далее оно
рассматриваться не будет.
Следующее поле сообщает, на каком компакт-диске расположен файл. Допускается,
чтобы запись каталога на одном компакт-диске ссылалась на файл, расположенный
на другом компакт-диске набора. Таким образом, появляется возможность создания
главного каталога на первом компакт-диске набора, в котором содержится список всех
файлов на всех компакт-дисках всего набора.
Поле, помеченное на рис. 4.26 буквой L, задает размер имени файла в байтах. Сразу за
ним следует само имя файла, которое состоит из основного имени, точки, расширения,
точки с запятой и двоичного номера версии (1 или 2 байта). В основном имени и рас-
ширении могут использоваться буквы в верхнем регистре, цифры от 0 до 9 и символ
подчеркивания. Все остальные символы запрещены, чтобы обеспечить возможность
обработки любого имени файла на любом компьютере. Основное имя может содержать
до восьми символов, а расширение — до трех. Этот выбор был продиктован необхо-
димостью сохранения совместимости с MS-DOS. Имя файла может фигурировать
в каталоге несколько раз, если только каждый экземпляр отличается номером версии.
Последние два поля присутствуют не всегда. Поле Дополнение используется для того,
чтобы каждая запись каталога составляла четное количество байтов и можно было
выровнять числовые поля последующих записей по двухбайтовым границам. Если
требуется дополнение, то используется нулевой байт. И наконец, у нас есть поле, ис-
пользуемое системой. Его функции и размер не определены, за исключением того, что
в нем должно быть четное количество байтов. В разных системах оно используется
по-разному. К примеру, в системах Macintosh в нем хранятся флажки Finder.
Записи в каталоге, за исключением первых двух, идут в алфавитном порядке. Первая
запись предназначена для самого каталога. А вторая — для его родительского каталога.