\section{Структуры файловых систем}

\subsection{Простые файловые системы}\label{FAT}

Наиболее простой файловой системой можно считать структуру, создаваемую
архиватором системы \sysname{UNIX} -- программой \verb"tar" (Tape ARchive
-- архив на [магнитной] ленте). Этот архиватор просто пишет файлы один за
другим, помещая в начале каждого файла заголовок с его именем и длиной.
Аналогичную структуру имеют файлы, создаваемые архиваторами типа
\verb"arj"; в отличие от них, \verb"tar" не упаковывает файлы.

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

Изменение же длины файла в середине архива или его стирание вообще 
превращается в целую эпопею.
Поэтому \verb"tar" используется для того, чтобы собрать файлы с диска в
некую единую сущность, например, для передачи по сети или для резервного
копирования, а для работы файлы обычно распаковываются на диск или другое
устройство с произвольным доступом.

Чтобы не заниматься при каждом новом поиске просмотром всего устройства,
удобнее всего разместить каталог в определенном месте, например в начале
ленты. Наиболее простую, из известных авторам, файловую систему такого
типа имеет ОС \sysname{RT-11}\footnote{Это единственная известная авторам
файловая система, которая с одинаковым успехом применяется как на лентах,
так и на устройствах с произвольным доступом. Все более сложные ФС,
обсуждаемые далее, используются только на устройствах произвольного
доступа. В наше время наиболее распространенный тип запоминающего 
устройства произвольного доступа -- это магнитный или оптический 
(реже - магнитооптический) диск, поэтому далее в тексте мы будем 
называть такие устройства просто дисками -- для краткости,
хотя такое сокращение и не вполне корректно.}
В этой ФС, как и во всех, обсуждаемых далее, место на диске или
ленте выделяется по блокам. Размер блока, как правило, совпадает с аппаратным
размером сектора (512 байт у большинства дисковых устройств), однако
многие ФС могут использовать логические блоки, состоящие из нескольких
секторов (так называемые кластеры).

Использование блоков и кластеров вместо адресации с точностью до байта
обусловлено двумя причинами. 

Во первых, у большинства устройств произвольного доступа доступ произволен 
лишь с точностью до сектора, то есть нельзя произвольно считать или записать 
любой байт -- нужно считывать или записывать весь сектор целиком. 
Именно поэтому в системах семейства \sysname{Unix} такие устройства
называются \termin{блочными}{block-oriented}.

Во-вторых, использование крупных адресуемых единиц позволяет резко 
увеличить адресуемое пространство. Так, используя 16-битный указатель, 
с точностью до байта можно адресовать всего 64к, но если в качестве 
единицы адресации взять 512-байтовый блок, то объем адресуемых данных 
сможет достигать 32 мегабайт; если же использовать кластер размером 32к, 
то можно работать с данными объемом до 2 Гб. Аналогично, 32-битовый 
указатель позволяет адресовать с точностью до байта 4Гб данных, то есть
уже далеко не каждый современный жесткий диск; зато если перейти к адресации
по блокам, то адресное пространство вырастет до 256Гб, что уже вполне
приемлемо практически для всех современных запоминающих устройств.

Таким образом, адресация по блокам и кластерам позволяет использовать
в системных структурах данных короткие указатели, что приводит к уменьшению
объема этих структур и к снижению накладных расходов. Под накладными расходами
в данном случае подразумевается не только освобождение дискового пространства,
но и ускорение доступа: структуры меньшего размера быстрее считываются,
в них быстрее производится поиск и т.д.
Однако увеличение объема кластера имеет оборотную сторону -- оно
приводит к так называемой внутренней фрагментации. 

Например, мы записываем в файл структуру данных объемом 624 байта,
Файл этот предполагается хранить на устройстве с 512-байтовым блоком.
В один блок наш файл не влезает, поэтому нужно выделять два блока.
Первый блок можно занять целиком, зато во втором блоке будет занято
всего 112 байт, а оставшиеся 400 байт не могут быть отданы другому 
файлу и оказываются потеряны. Это и называется внутренней фрагментацией.

Величина потерь зависит от среднего размера файла на диске.
Грубая оценка состоит в том, что на каждый файл в среднем теряется 
полкластера, т.е. отношение занятого пространства к потерянному будет
$\frac{1}{2}\frac{Ns_{c}}{N\overline{l}}$, где $N$ -- количество файлов
на диске, $s_{c}$ -- размер кластера, а $\overline{l}$ -- средний размер
файла. Иными словами, потери будут равны $\frac{s_{c}}{2\overline{l}}$,
т.е. будут линейно расти с увеличением размера кластера.

Когда средний размер файла оказывается сравним с размером кластера,
наша формула теряет точность, но все равно дает хорошую оценку порядка
величины потерь. Так, если $s_{c} = \overline{l}$, наша формула
дает 50 \% потерь, что вполне согласуется со здравым смыслом:
если файл чуть короче кластера, теряется только это ``чуть'';
зато если файл чуть длиннее, то для него отводится два кластера и
второй кластер теряется почти весь. Точная величина потерь сейчас
уже определяется количеством файлов, которые ``чуть'' длиннее среднего.
Количество таких файлов вовсе не равно $\frac{1}{2}N$,
а зависит от распределения файлов по длине, но мы предпочитаем
оставить вывод точной формулы любопытному читателю.

Ряд современных файловых систем использует механизм, по английски
называемый \term{block suballocation}, то есть размещение частей блоков.
В этих ФС кластеры имеют большой размер, но есть возможность разделить
кластер на несколько блоков меньшего размера и записать в эти блоки
``хвосты'' от нескольких разных файлов. Это, безусловно, усложняет ФС,
но позволяет одновременно использовать преимущества, свойственные
и большим, и маленьким блокам. Поэтому ряд распространенных ФС,
например файловая система \sysname{Novell Netware 4.1} и 
\sysname{FFS} (известная также как \sysname{UFS} и \sysname{Berkley FS}),
используемая во многих системах семейства \sysname{Unix}, используют
этот механизм.

Но вернемся к простым файловым системам.
В \sysname{RT-11} каждому файлу выделяется непрерывная область на диске.
Благодаря этому в каталоге достаточно хранить адрес первого блока файла
и его длину, также измеренную в блоках. В \sysname{RT-11} поступили
еще проще: порядок записей в каталоге совпадает с порядком файлов
на диске, и началом файла считается окончание предыдущего файла.
Свободным участкам диска тоже соответствует запись в каталоге.
При создании файла система ищет первый свободный участок подходящего размера.

Фактически эта структура отличается от формата \verb"tar" только тем,
что каталог вынесен в начало диска, и существует понятие свободного
участка внутри области данных. Но эта простая организация имеет очень 
серьезные недостатки.
\begin{enumerate}
\item При создании файла программа должна указать его длину.
Часто это бывает затруднительно, например, при создании объектного
файла во время компиляции программы на языке высокого уровня.

Особенно неудобно оказывается увеличивать в размере уже созданный файл.
Точнее, это просто невозможно: вместо удлинения старого файла приходится
создавать файл новой длины и копировать содержимое старого файла в него.

\item При хаотическом создании и удалении файлов возникает
проблема фрагментации свободного пространства. Для ее решения существует
специальная программа \verb"SQUEESE" (сжать [диск]), которая переписывает
файлы так, чтобы объединить все свободные фрагменты. Эта программа требует
много времени, особенно для больших дисковых томов, и потенциально опасна:
если при ее исполнении произойдет сбой системы (а с машинами третьего
поколения такое случалось по нескольку раз в день), то значительная часть
данных будет необратимо разрушена.
\end{enumerate}

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

Однако, отчасти похожее решение было реализовано в \sysname{MS~DOS}
и \sysname{DR~DOS}. Эти системы создают на диске таблицу, называемую
\termint{FAT}{File Allocation Table}{таблица размещения файлов}.
В этой таблице каждому блоку, предназначенному для хранения данных,
соответствует 12-битовое значение.
Если блок свободен, то значение будет нулевым. Если же блок принадлежит
файлу, то значение будет равно {\bf адресу следующего блока этого файла}.
Если это последний блок в файле, то значение будет \verb"0xFFF". Существует
также специальный код для обозначения \termin{плохого}{bad} блока,
не читаемого из-за дефекта физического носителя.
В каталоге хранится номер первого блока и длина файла, измеряемая в байтах.

Емкость диска при использовании 12-битной \verb"FAT" оказывается ограничена 
4096-ю блоками (2Мб), что приемлемо для дискет, но совершенно не годится для 
жестких дисков и других устройств большой емкости. На таких устройствах 
\sysname{DOS} использует \verb"FAT" с 16-битовыми элементами. На совсем 
уж больших (более 32 мегабайт) дисках \sysname{DOS} выделяет пространство 
не блоками, а \term{кластерами} из нескольких блоков.
Эта файловая система так и называется -- \sysname{FAT}.

Такая файловая система очень проста и имеет одно серьезное достоинство:
врожденную \termin{устойчивость к сбоям}{fault tolerance}, но об этом ниже.

В то же время она имеет и ряд серьезных недостатков.

Первый недостаток состоит в том, что при каждой операции
над файлами система должна обращаться к \verb"FAT". Это приводит к частым
перемещениям головок дисковода и в результате к резкому снижению
производительности. Действительно, исполнение программы \verb"arj" на одной
и той же машине под \sysname{MS~DOS} и под \sysname{DOS}-эмулятором систем
\sysname{Unix} или \sysname{OS/2} различается по скорости почти в 1.5 раза.
Особенно это заметно при архивировании больших каталогов.

Использование дисковых кэшей, а особенно помещение \verb"FAT"
в оперативную память, существенно ускоряет работу,
хотя обычно \verb"FAT" кэшируется только на чтение
ради устойчивости к сбоям.

Но здесь мы сталкиваемся со специфической проблемой:
чем больше диск, тем больше у него \verb"FAT",
соответственно, тем больше нужно памяти: у тома \sysname{Novell Netware 3.12}%
размером 1.115 Гбайт с размером кластера 4 кбайта размер \verb"FAT"
достигает мегабайта\footnote{Легко понять, что \sysname{Netware} использует
\verb"FAT" с 32-разрядными элементами.
При 16-разрядном элементе \verb"FAT" дисковый том такого объема
с таким размером кластера просто невозможен.}.
При монтировании такого тома \sysname{Netware}
занимает под \verb"FAT" и кэш каталогов около 6 Мбайт памяти.

Для сравнения, \sysname{Netware 4} использует block suballocation, поэтому
там можно относительно безнаказанно увеличивать объем кластера и нет 
необходимости делать кластер таким маленьким. Для дисков такого объема
\sysname{Netware 4} устанавливает размер кластера 16 килобайт, что
приводит к уменьшению всех структур данных в 4 раза.

Понятно, что для \sysname{MS~DOS}, которая умеет адресовать всего
1 Мбайт (1088 кбайт, если разрешен \verb"HMA"), хранить
такой \verb"FAT" в памяти целиком просто невозможно.

Поэтому разработчики фирмы \entname{MicroSoft} пошли другим путем:
они ограничили разрядность элемента \verb"FAT" 16 битами.
При этом размер таблицы не может превышать 128 кбайт, что вполне терпимо.
Зато вся файловая система может быть разбита только на 64 К блоков.
В старых версиях \sysname{MS~DOS} это приводило к невозможности
создавать файловые системы размером более 32 Мбайт.
В версиях старше 3.11 появилась возможность объединять блоки в кластеры.
Например, на дисках размером от 32 Мбайт до 64 Ммбайт кластер будет
состоять из 2 блоков и иметь размер 1 кбайт. На дисках размером
128-265 Мбайт кластер будет уже размером 4 кбайта, и т.д.

\sysname{Windows 95} использует защищенный режим процессора \machname{x86},
поэтому адресное пространство там намного больше одного мегабайта.
Разработчкик фирмы \entname{Microsoft} решили воспользоваться этим и
реализовали версию \sysname{FAT} с 32-битовым элементом таблицы -- 
так называемый \sysname{FAT32}. Однако дисковый кэш \sysname{Windows 95}
не стремился удержать весь \verb'FAT' в памяти; вместо этого \verb'FAT'
кэшировался на общих основаниях, наравне с пользовательскими данными.
Поскольку работа с файлами большого (больше одного кластера) объема 
требует прослеживания цепочки элементов \verb'FAT', а соответствующие
блоки таблицы могут не попадать в кэш, то производительность резко падает.
В сопроводительном файле \sysname{Microsoft} признает, что производительность
\sysname{FAT32} на операциях последовательного чтения и записи
может быть в полтора раза ниже, чем у кэшированного \sysname{FAT16}.

Реализация \sysname{FAT32} распространялась в виде патча к 
\sysname{Windows 95}, но новая ФС не вызвала энтузиазма у пользователей.
Авторам не известно ни одного случая практического применения этой ФС,
да и сама фирма \sysname{Microsoft} не очень активно занимается ее 
продвижением.

В качестве итога можно сказать, что при использовании \sysname{FAT}
на больших дисках мы вынуждены делать выбор между низкой 
производительностью, чудовищными по современным меркам
требованиями к оперативной памяти или большим размером кластера,
который приводит к большим потерям из-за внутренней фрагментации.

Например, у одного из авторов на локальном диске
емкостью 210 Мбайт (кластер 4 кбайта) терялось около 10 Мбайт, т.е. около 5 \%
емкости диска.  
Средний размер файла был около 20 кбайт в основном за счет пакета
\progname{emTeX}, который содержит несколько сотен коротких файлов.
По приведенной в начале этого пункта формуле можно оценить, что при 
том же среднем размере файла на диске емкостью 1 Гбайт терялось бы 
40 \% пространства\ellipsis.

Нужно отметить, впрочем, что более характерный средний размер файла на
современных персоналках ближе к 64 - 128 кбайтам, поэтому потери
в большинстве случаев не так катастрофически велики.
На гигабайтном разделе будет, таким образом, теряться ``всего лишь''
около 10 \%. Действительно,
размер кластера равен 16 кбайтам, и потери по нашей формуле будут
$16K/2*64K = 1/8 = 0.125 \approx 0.1$. Но на диске объемом 4 Гбайта
мы опять получаем около 50 \% потерь!

При современных темпах развития электроники и падения цен на нее
четырехгигабайтные диски для персоналок станут в ближайшие несколько
лет реальностью. А если учесть скорость роста размеров коммерческих
прикладных программ (программы из пакета \progname{MicroSoft Office}
занимают по нескольку десятков мегабайт каждая), то такие диски
быстро станут остро необходимыми.

В свете всего этого сложно оправдать решение фирмы \entname{MicroSoft} 
использовать в новой ОС \sysname{Windows 95} старую файловую систему с 
небольшими изменениями для поддержки длинных имен файлов. Ведь для 
эффективного управления большими объемами данных необходимо что-то 
более сложное, чем \sysname{FAT}.

\subsection{``Сложные'' файловые системы}\label{HPFS}\label{inodes}

Структуры ``сложных'' файловых систем отличаются большим разнообразием,
однако можно выделить несколько общих идей.

Обычно файловая система начинается с заголовка, или, как это называется
в системах семейства \sysname{Unix}, \termin{суперблока}{superblock}.
Суперблок хранит информацию о размерах дискового тома, отведенного под
ФС, указатели на начала системных структур данных и другую информацию,
зависящую от типа ФС. Например, для статических структур может храниться их
размер. Часто суперблок содержит также \term{магическое число}
-- идентификатор типа файловой системы. Аналог суперблока существует даже в
\sysname{FAT} -- это так называемая \termin{загрузочная запись}{boot record}.

Практически все современные ФС разделяют список свободных
блоков и структуры, отслеживающие размещение файлов. Чаще всего
вместо списка свободных блоков используется битовая карта, в которой
каждому блоку соответствует один бит: занят/свободен. В свою очередь,
список блоков для каждого файла обычно связан с управляющей структурой файла.

На первый взгляд, такую структуру кажется естественным  хранить в
каталоге, но их обычно выносят в отдельные структуры, часто собранные
в специальные таблицы описателей файлов -- таблицу \term{инодов},
\term{метафайл} и т.д. Такое решение уменьшает объем каталога и,
соответственно, ускоряет поиск файла по имени. К тому же многие ФС 
сортируют записи в каталоге по имени файла, также с целью ускорения 
поиска. Понятно, что сортировка записей меньшего размера происходит
быстрее.

{\small
В файловой системе \sysname{HPFS}, используемой в \sysname{OS/2}
и \sysname{Windows~NT}, каждая запись в каталоге содержит имя файла
и указатель на \termin{fnode}{файловую запись}. Каталоги в этой ФС 
организованы в виде B-деревьев и отсортированы по именам файлов.

Файловая запись занимает один блок на диске и содержит список так называемых
\termin{extents}{``расширений''}\footnote{У этого термина нет приемлемого 
русского аналога. В переводах документации по \sysname{OS/360} 
(\sysname{ОС ЕС}) так и писали: \term{экстент}.}.
Каждый экстент описывает непрерывную последовательность дисковых блоков,
выделенных файлу. Он задает начальный блок такой последовательности и ее длину.
Вместо списка свободных блоков используется битовая карта
диска, в которой каждому блоку соответствует один бит: занят/свободен.

Нужно отметить, что идея экстентов далеко не нова: аналогичная структура
используется в некоторых версиях \sysname{Unix} с начала 80-х годов,
а истоки этой идеи теряются в глубине 60-х.

Файловая запись размешается перед началом первого экстента файла, хотя это и
не обязательно. Она занимает один блок (512 байт) и может содержать до десяти
описателей экстентов. Кроме того, она содержит информацию о времени создания 
файла, его имени и \term{расширенных атрибутах}\footnote{Подробнее о 
расширенных атрибутах см. в разделе \ref{resource_fork}.}. Если для списка 
экстентов или расширенных атрибутов места не хватает, то для них также 
выделяются экстенты. В этом случае экстенты размещаются в виде B-дерева
для ускорения поиска. Максимальное количество экстентов в файле не 
ограничено ничем, кроме размера диска.

Пользовательская программа может указать размер файла при его создании.
В этом случае система сразу попытается выделить место под файл так, чтобы
он занимал как можно меньше экстентов. Если программа не сообщила размера
файла, используется значение по умолчанию. Фактически, HPFS размещает место
под файл по принципу \termin{worst fit}{наименее подходящего}, начиная
выделение с наибольшего непрерывного участка свободного пространства.
В результате фрагментированными оказываются только файлы, длина которых
увеличивалась во много приемов или же те, которые создавались при почти
заполненном диске. При нормальной работе файл редко занимает больше
3 - 4 экстентов.

Ещ\"е одно любопытное последствие стратегии \term{worst fit} заключается в
том, что пространство, освобожденное стертым файлом, обычно
используется не сразу. Отмечались случаи, когда файл на активно используемом
диске удавалось восстановить через несколько дней после стирания.

Экстенты открытых файлов и карта свободных блоков во время работы
размещаются в ОЗУ, поэтому производительность такой ФС в большинстве
ситуаций намного (в 1.5 - 2 раза и более) выше, чем у \sysname{FAT} без кэша,
при вполне приемлемых требованиях к памяти и размере кластера 512 байт.

Понятно также, что структура \sysname{HPFS} упрощает произвольный доступ
к файлу: вместо прослеживания цепочки блоков нам нужно проследить цепочку
экстентов, которая гораздо короче.

Более подробное описание структуры \sysname{HPFS} можно найти в статье
\cite{PCMagHPFS}. Среди пользователей \sysname{OS/2} считается
целесообразным форматировать все разделы емкостью более 128М под
\sysname{HPFS}, поскольку при этом выигрывается как скорость, так
и эффективность использования дискового пространства;
кроме того, исчезает необходимость в дефрагментации и появляется
возможность создавать файлы и каталоги с длинными именами,
не укладывающимися в модель \verb"8.3", принятую в \sysname{MS~DOS}.
}

Но за эти преимущества приходится платить неустойчивостью к сбоям%
\footnote{Проблема устойчивости к системным сбоям обсуждается в разделе
\ref{FaultTolerance}.}.
В отличие от ДОС, спонтанные развалы системы с последующим зависанием
в \sysname{OS/2} случаются относительно редко, даже при запуске программ,
заведомо содержащих ошибки (как при разработке или тестировании прикладного
программного обеспечения). С другой стороны, на практике ``неустойчивость''
приводит лишь к тому, что после аварийной перезагрузки автоматически
запускается программа починки ФС, что увеличивает время перезагрузки
в несколько раз; реальный же риск потерять данные при сбое не выше,
а как показывает практика, даже существенно ниже, чем при использовании
\sysname{FAT}, поэтому игра явно стоит свеч.

Наиболее интересна структура файловых систем в ОС семейства \sysname{Unix}.
В этих ФС каталог не содержит почти никакой информации о файле.
Там хранится только имя файла и номер его \termint{инода}{i-node}{по-видимому,
сокращение от index node: индексная запись}. Иноды всех файлов
в данной ФС собраны в таблицу, которая так и называется: таблица инодов.
В ранних версиях \sysname{Unix} таблица инодов занимала
фиксированное пространство в начале устройства; в современных файловых
системах эта таблица разбита на участки, распределенные по диску.

{\small
Например, в файловой системе \sysname{BSD Unix} \sysname{FFS} (Fast File
System -- быстрая файловая система), которая в \sysname{Unix SVR4}
называется просто \sysname{UFS} (Unix File System), диск разбит на
группы цилиндров. Каждая группа цилиндров содержит копию
суперблока, битовую карту свободных блоков для данного участка и
таблицу инодов для файлов, расположенных в пределах
этого участка. Такая распределенная структура имеет два преимущества:
\begin{itemize}
\item Ускорение доступа к системным структурам данных. Когда системные
данные расположены вблизи от блоков пользовательских данных, уменьшается
расстояние, на которое перемещаются головки дисковода.

\item Повышенная устойчивость к сбоям носителя. При повреждении участка
поверхности диска теряется только небольшая часть системных данных.
Даже потеря суперблока не приводит к потере структуры файловой системы.
\end{itemize}
}

Инод хранит информацию о самом файле и его размещении на диске.
Информационная часть инода может быть получена системным вызовом
\verb"int stat(const char * fname, struct stat * buf);".
Формат структуры \verb"stat" описан во многих руководствах по языку
\sysname{C}, ОС \sysname{UNIX} и стандарту \standname{POSIX}, например в
работе \cite{RedPOSIX}. Эта структура содержит:
\begin{description}
\item[тип файла.] Исследуя это поле, можно понять, является данный
объект файлом данных или специальным файлом. В этом же поле закодированы
права доступа к файлу;
\item[идентификаторы] хозяина файла и группы, к которой хозяин принадлежит;
\item[времена:]{\ }
   \begin{itemize}
	\item создания файла,
	\item последней модификации файла,
	\item последнего доступа к файлу;
   \end{itemize}
\item[длину файла.] Для специальных файлов это поле часто имеет другой смысл;
\item[идентификатор файловой системы,] в которой расположен файл;
\item[количество связей файла.] Это поле заслуживает отдельного обсуждения.
\end{description}

Структура, описывающая физическое размещение файла по диску, недоступна
пользовательским программам.
Собственно, формат этой структуры может быть не очень элегантен.
Например, в файловой системе \sysname{Veritas} это список экстентов,
похожий на \sysname{HPFS}; в файловых системах \sysname{s5}, \sysname{Xenix} 
и \sysname{FFS} это массив из 13 чисел, задающих номера
физических блоков файла. Если файл в \sysname{s5} содержит более
десяти блоков (т.е. его длина больше 5 кбайт), то предпоследние три
указателя обозначают не блоки данных, а так называемые \termin{косвенные
блоки}{indirection blocks}, в которых хранятся указатели на следующие
блоки данных и, возможно, на следующие косвенные блоки.

Наиболее интересная особенность \sysname{Unix}-овых ФС состоит не в этом.
Внимательный читатель, возможно, заметил, что инод не содержит имени файла.
С другой стороны, он содержит счетчик \termin{связей}{links}
-- ссылок на этот файл из каталогов.
Т.е. на один и тот же инод можно ссылаться из различных каталогов
или из одного каталога под различными именами. Иными словами,
\begin{center}
{\bf один и тот же файл в этих ФС может иметь несколько различных имен.}
\end{center}
Именно это и имелось в виду, когда говорилось, что структура каталогов в
ОС \sysname{UNIX} не обязана являться деревом.

Это свойство предоставляет неоценимые возможности для организации
иерархии каталогов, но имеет и некоторые оборотные стороны.
\begin{enumerate}
\item Создание нескольких связей для каталога потенциально опасно -- оно
может привести к возникновению кольца, в котором каталог является своим
собственным подкаталогом. Отслеживать такую ситуацию сложно, поэтому
разработчики ОС \sysname{UNIX} запретили создавать дополнительные имена для
каталогов.

\item Удаление файла превращается в проблему: чтобы удалить файл, нужно
проследить все его связи. Поэтому \sysname{UNIX} не имеет средств для
удаления файла, а имеет только системный вызов \verb"unlink" -- удалить
связь. Когда у файла не остается связей, он действительно удаляется.

Этот подход вполне разумен, но также имеет неожиданную оборотную сторону:
поскольку теперь стирание файла -- это операция не над файлом, а над
каталогом, то {\bf для удаления файла не нужно иметь никаких прав доступа
к нему. Достаточно иметь право записи в каталог}. Одно из самых
неприятных последствий состоит в том, что нельзя защитить индивидуальный файл
от стирания: либо вы закрываете на запись весь каталог и не можете
ни удалить в нем любой другой файл, ни создать новый; либо вы открываете
его на запись и тогда можете стереть ваш драгоценный файл по ошибке.

\item Такие связи (называемые еще {\it жесткими} связями), как легко понять,
могут создаваться только в пределах одной файловой системы, поскольку каждая
ФС имеет собственную таблицу инодов, и соответственно собственную
их нумерацию.
\end{enumerate}

Последнее обстоятельство резко уменьшает полезность жестких связей для
организации иерархии каталогов. Эта проблема была осознана еще в 70-е гг.,
и программисты из группы \entname{BSD} придумали интересное новое понятие --
символическую связь.

Символическая связь представляет собой специальный файл. Вместо блоков данных
инод такого файла содержит текстовую строку -- {\it имя того файла, с
которым создана связь}. Это может быть файл на другой файловой системе,
в том числе и на такой, которая сама по себе не поддерживает ни жестких,
ни символических связей, например, \sysname{FAT}, \sysname{HPFS} или файловом
сервере \sysname{Novell Netware}. Такого файла может и вообще не существовать,
например потому, что его уже удалили, или потому, что файловая система, в
которой он находится, не смонтирована, или просто потому, что имя было задано
неправильно.
Тогда попытки открыть символическую связь будут завершаться неуспехом
с кодом ошибки ``файла не существует''.

Единственным недостатком символических связей является их относительно
низкая \termin{дуракоустойчивость}{fool-tolerance}: глупый пользователь
может не распознать ситуации, когда символическая связь указывает в никуда.
Зато они обеспечивают полную свободу в размещении и именовании файлов.

{\small
Пример из жизни:
На двух \sysname{Unix}-системах с именами \verb"orasrv" и \verb"Indy"
установлен один и тот же программный продукт: редакторная система
\progname{GNU Emacs}. Бинарные загрузочные модули для этих систем
различаются, но большая часть \progname{Emacs} -- это файлы на языке
\progname{Emacs Lisp}, которые с одинаковым успехом могут использоваться
обеими системами. Поэтому у администратора системы возникает
желание использовать одну копию lisp-файлов.

При этом \progname{Emacs} установлен таким образом, что он ищет все свои
lisp-файлы в каталоге \verb"/usr/local/lib/emacs/19.27/lisp".
Изменение этого каталога потребовало бы частичной переустановки продукта.
Но его не надо менять! Мы просто подмонтируем на машине \verb"orasrv"
каталог \verb"/" машины \verb"Indy" как \verb"/fs/Indy", и исполняем
следующие команды:

\begin{example}
\small\begin{verbatim}

cd /usr/local/lib/emacs/19.27 # перейти в заданный каталог
rm -Rf lisp       # стереть каталог lisp со всем содержимым
ln -s /fs/Indy/usr/local/lib/emacs/19.27/lisp lisp
# создать символическую связь с именем lisp c соответствующим
# каталогом на машине Indy
\end{verbatim}
\end{example}

Вся операция вместе с ее планированием занимает около двух минут.
Освобождается около 9 Мбайт дискового пространства. \progname{Emacs}
ничего не замечает, и работает без всяких проблем.

Через неделю у администратора возникает идея, что для удобства
администрирования неплохо было бы монтировать с \verb"orasrv" не всю файловую
систему \verb"Indy", а только ее каталог \verb"/home". За чем дело стало:
переносим на \verb"Indy" каталог \verb"lisp" в каталог
\verb"/home/emacs/19.27/lisp"; создаем в старом каталоге символическую
связь с новой; редактируем файл \verb"/etc/mnttab" на машине \verb"orasrv"
так, чтобы с \verb"Indy" монтировалась только \verb"/home"; меняем
символическую связь каталога \verb"lisp" на машине \verb"orasrv".
Заставляем \verb"orasrv" подмонтировать диски в соответствии с новым
\verb"/etc/mnttab". Готово.

Операция занимает чуть больше двух минут, потому что нужно переносить девять
мегабайт с одной файловой системы на другую. \progname{Emacs} опять ничего не
замечает и снова работает без всяких проблем. Администратор счастлив. Все
довольны.

Сравните это описание с впечатлениями пользователя, который пытается
переместить с одного ДОС-овского драйва на другой пакет \progname{CorelDRAW!}
или любую другую программу, которая при установке записывает в свою
конфигурацию полное имя каталога, в который ее ставили\ellipsis
}

Символические связи уникальны для систем семейства \sysname{Unix}.
Напротив, эквиваленты жестких связей существуют в других ОС. Фактически
жесткие связи можно создавать в любой ФС, где каталоги содержат ссылки
на централизованную базу данных вместо самого дескриптора файла.

Например, в файловой системе \sysname{VAX/VMS} данные о размещении
файлов на диске хранятся в специальном \termin{индексном}{index} файле;
каталоги же хранят только индексы записей в этом файле.
Основное отличие этой структуры от принятой в \sysname{Unix}
состоит в том, что вместо статической таблицы или набора таблиц
используется динамическая таблица, пространство под которую выделяется
тем же методом, что и для пользовательских файлов.
Этот же подход реализован в файловой системе
\sysname{NTFS}, используемой в \sysname{Windows NT}, но там индексный
файл называется \termin{метафайлом}{metafile}. Несколько более подробное
описание структуры \sysname{NTFS} приводится в статье \cite{PCMagNTFS}.

\sysname{VAX/VMS} и \sysname{Windows NT} позволяют создавать
дополнительные имена для файлов, хотя в \sysname{VMS} утилиты починки
ФС выдают предупреждение, обнаружив такое дополнительное имя.
Все имена файла в этих ФС обязаны находиться в одной файловой системе.
Кроме того, операция удаления файла в \sysname{VMS} ведет себя не так,
как в \sysname{Unix}: применение операции удаления к любому из имен
приводит к удалению самого файла, даже если существовали и другие имена.


