Добавлен: 29.10.2018
Просмотров: 48117
Скачиваний: 190
4.4. Управление файловой системой и ее оптимизация
351
как непосредственно, так и в нижележащих поддеревьях каталогов. После этого этапа
битовый массив приобретает вид, показанный на рис. 4.22, б. Следует заметить, что
каталоги 10, 11, 14, 27, 29 и 30 теперь уже не помечены, поскольку ниже этих каталогов
не содержится никаких измененных элементов. Они не будут сохраняться в резервной
копии. В отличие от них каталоги 5 и 6, несмотря на то что сами они не подверглись
изменениям, будут заархивированы, поскольку понадобятся для восстановления
сегодняшних изменений на новой машине. Для повышения эффективности первый
и второй этапы могут быть объединены в одном проходе дерева.
К этому моменту уже известно, какие каталоги и файлы нужно архивировать. Все они
отмечены на рис. 4.22, б. Третий этап состоит из сканирования i-узлов в порядке их
нумерации и архивирования всех каталогов, помеченных для архивации. Эти каталоги
показаны на рис. 4.22, в. В префиксе каждого каталога содержатся его атрибуты (вла-
делец, метки времени и т. д.), поэтому они могут быть восстановлены. И наконец, на
четвертом этапе также архивируются файлы, помеченные на рис. 4.22, г, в префиксах
которых также содержатся их атрибуты. На этом архивация завершается.
Рис. 4.22. Битовые массивы, используемые алгоритмом логической архивации
Восстановление файловой системы с архивного диска не представляет особого труда.
Для начала на диске создается пустая файловая система. Затем восстанавливается
самая последняя полная резервная копия. Поскольку первыми на резервный диск
попадают каталоги, то все они восстанавливаются в первую очередь, задавая основу
файловой системы, после чего восстанавливаются сами файлы. Затем этот процесс
повторяется с первым инкрементным архивированием, сделанным после полного
архивирования, потом со следующим и т. д.
Хотя логическая архивация довольно проста, в ней имеется ряд хитростей. К примеру,
поскольку список свободных блоков не является файлом, он не архивируется, значит,
после восстановления всех резервных копий он должен быть реконструирован зано-
во. Этому ничего не препятствует, поскольку набор свободных блоков является всего
лишь дополнением того набора блоков, который содержится в сочетании всех файлов.
Другая проблема касается связей. Если файл связан с двумя или несколькими каталога-
ми, нужно, чтобы файл был восстановлен только один раз, а во всех каталогах, которые
должны указывать на него, появились соответствующие ссылки.
352
Глава 4. Файловые системы
Еще одна проблема связана с тем обстоятельством, что файлы UNIX могут содержать
дыры. Вполне допустимо открыть файл, записать в него всего несколько байтов, пере-
местить указатель на значительное расстояние, а затем записать еще несколько байтов.
Блоки, находящиеся в промежутке, не являются частью файла и не должны архивиро-
ваться и восстанавливаться. Файлы, содержащие образы памяти, зачастую имеют дыру
в сотни мегабайт между сегментом данных и стеком. При неверном подходе у каждого
восстановленного файла с образом памяти эта область будет заполнена нулями и, со-
ответственно, будет иметь такой же размер, как и виртуальное адресное пространство
(например, 2
32
байт или, хуже того, 2
64
байт).
И наконец, специальные файлы, поименованные каналы (все, что не является настоя-
щим файлом) и им подобные никогда не должны архивироваться, независимо от того,
в каком каталоге они могут оказаться (они не обязаны находиться только в каталоге
/dev
). Дополнительную информацию о резервном копировании файловой системы
можно найти в трудах Червенака (Chervenak et al., 1998), а также Звиски (Zwicky, 1991).
4.4.3. Непротиворечивость файловой системы
Еще одной проблемой, относящейся к надежности файловой системы, является обе-
спечение ее непротиворечивости. Многие файловые системы считывают блоки, вносят
в них изменения, а потом записывают их обратно на носитель. Если сбой системы
произойдет до того, как записаны все модифицированные блоки, файловая система
может остаться в противоречивом состоянии. Особую остроту эта проблема приоб-
ретает, когда среди незаписанных блоков попадаются блоки i-узлов, блоки каталогов
или блоки, содержащие список свободных блоков.
Для решения проблемы противоречивости файловых систем на многих компьютерах
имеются служебные программы, проверяющие их непротиворечивость. К примеру,
в системе UNIX есть fsck, а в системе Windows — sfc (и другие программы). Эта утилита
может быть запущена при каждой загрузке системы, особенно после сбоя. Далее будет
дано описание работы утилиты fsck. Утилита sfc имеет ряд отличий, поскольку работает
на другой файловой системе, но в ней также действует общий принцип использования
избыточной информации для восстановления файловой системы. Все средства про-
верки файловых систем работают над каждой файловой системой (разделом диска)
независимо от всех остальных файловых систем.
Могут применяться два типа проверки непротиворечивости: блочный и файловый.
Для проверки блочной непротиворечивости программа создает две таблицы, каждая
из которых состоит из счетчика для каждого блока, изначально установленного в нуль.
Счетчики в первой таблице отслеживают количество присутствия каждого блока в фай-
ле, а счетчики во второй таблице регистрируют количество присутствий каждого блока
в списке свободных блоков (или в битовом массиве свободных блоков).
Затем программа считывает все i-узлы, используя непосредственно само устройство,
при этом файловая структура игнорируется и возвращаются все дисковые блоки на-
чиная с нулевого. Начиная с i-узла можно построить список всех номеров блоков, ис-
пользуемых в соответствующем файле. Как только будет считан номер каждого блока,
увеличивается значение его счетчика в первой таблице. Затем программа проверяет
список или битовый массив свободных блоков, чтобы найти все неиспользуемые блоки.
Каждое появление блока в списке свободных блоков приводит к увеличению значения
его счетчика во второй таблице.
4.4. Управление файловой системой и ее оптимизация
353
Если у файловой системы нет противоречий, у каждого блока будет 1 либо в первой,
либо во второй таблице (рис. 4.23, а). Но в результате отказа таблицы могут принять
вид, показанный на рис. 4.23, б, где блок 2 отсутствует в обеих таблицах. Он будет фи-
гурировать как пропавший блок. Хотя пропавшие блоки не причиняют существенного
вреда, они занимают пространство, сокращая емкость диска. В отношении пропавших
блоков принимается довольно простое решение: программа проверки файловой систе-
мы включает их в список свободных блоков.
Рис. 4.23. Состояния файловой системы: а — непротиворечивое; б — с пропавшим блоком;
в — с блоком, дважды фигурирующим в списке свободных блоков;
г — с блоком, дважды фигурирующим в данных
Другая возможная ситуация показана на рис. 4.23, в. Здесь блок 4 фигурирует в списке
свободных блоков дважды. (Дубликаты могут появиться, только если используется имен-
но список свободных блоков, а не битовый массив, с которым этого просто не может про-
изойти.) Решение в таком случае тоже простое: перестроить список свободных блоков.
Хуже всего, если один и тот же блок данных присутствует в двух или нескольких
файлах, как случилось с блоком 5 (рис. 4.23, г). Если какой-нибудь из этих файлов
354
Глава 4. Файловые системы
удаляется, блок 5 помещается в список свободных блоков, что приведет к тому, что один
и тот же блок будет используемым и свободным одновременно. Если будут удалены
оба файла, то блок попадет в список свободных блоков дважды.
Приемлемым действием программы проверки файловой системы станет выделение
свободного блока, копирование в него содержимого блока 5 и вставка копии в один из
файлов. При этом информационное содержимое файлов не изменится (хотя у одного
из них оно почти всегда будет искаженным), но структура файловой системы во всяком
случае приобретет непротиворечивость. При этом будет выведен отчет об ошибке, по-
зволяющий пользователю изучить дефект.
Вдобавок к проверке правильности учета каждого блока программа проверки файловой
системы проверяет и систему каталогов. Она также использует таблицу счетчиков, но
теперь уже для каждого файла, а не для каждого блока. Начиная с корневого каталога
она рекурсивно спускается по дереву, проверяя каждый каталог файловой системы.
Для каждого i-узла в каждом каталоге она увеличивает значение счетчика, чтобы оно
соответствовало количеству использований файла.
Вспомним, что благодаря жестким связям файл может фигурировать в двух и более
каталогах. Символические ссылки в расчет не берутся и не вызывают увеличения
значения счетчика целевого файла.
После того как программа проверки все это сделает, у нее будет список, проиндексиро-
ванный по номерам i-узлов, сообщающий, сколько каталогов содержит каждый файл. За-
тем она сравнивает эти количества со счетчиками связей, хранящимися в самих i-узлах.
Эти счетчики получают значение 1 при создании файла и увеличивают свое значение
при создании каждой жесткой связи с файлом. В непротиворечивой файловой системе
оба счетчика должны иметь одинаковые значения. Но могут возникать два типа ошибок:
счетчик связей в i-узле может иметь слишком большое или слишком маленькое значение.
Если счетчик связей имеет более высокое значение, чем количество элементов каталогов,
то даже если все файлы будут удалены из каталогов, счетчик по-прежнему будет иметь
ненулевое значение и i-узел не будет удален. Эта ошибка не представляет особой важ-
ности, но она отнимает пространство диска для тех файлов, которых уже нет ни в одном
каталоге. Ее следует исправить, установив правильное значение счетчика связей в i-узле.
Другая ошибка может привести к катастрофическим последствиям. Если два элемента
каталогов имеют связь с файлом, а i-узел свидетельствует только об одной связи, то при
удалении любого из элементов каталога счетчик i-узла обнулится. Когда это произой-
дет, файловая система помечает его как неиспользуемый и делает свободными все его
блоки. Это приведет к тому, что один из каталогов будет указывать на неиспользуемый
i-узел, чьи блоки в скором времени могут быть распределены другим файлам. Решение
опять-таки состоит в принудительном приведении значения счетчика связей i-узла
в соответствие с реально существующим количеством записей каталогов.
Эти две операции, проверка блоков и проверка каталогов, часто совмещаются в целях
повышения эффективности (то есть для этого требуется только один проход по всем
i-узлам). Возможно проведение и других проверок. К примеру, каталоги должны иметь
определенный формат, равно как и номера i-узлов и ASCII-имена. Если номер i-узла
превышает количество i-узлов на диске, значит, каталог был поврежден.
Более того, у каждого i-узла есть режим использования (определяющий также права
доступа к нему), и некоторые из них могут быть допустимыми, но весьма странными,
к примеру 0007, при котором владельцу и его группе вообще не предоставляется ника-
4.4. Управление файловой системой и ее оптимизация
355
кого доступа, но всем посторонним разрешаются чтение, запись и исполнение файла.
Эти сведения могут пригодиться для сообщения о том, что у посторонних больше
прав, чем у владельцев. Каталоги, состоящие из более чем, скажем, 1000 элементов,
также вызывают подозрения. Если файлы расположены в пользовательских каталогах,
но в качестве их владельцев указан привилегированный пользователь и они имеют
установленный бит SETUID, то они являются потенциальной угрозой безопасности,
поскольку приобретают полномочия привилегированного пользователя, когда выпол-
няются любым другим пользователем. Приложив небольшие усилия, можно составить
довольно длинный список технически допустимых, но довольно необычных ситуаций,
о которых стоит вывести сообщения.
В предыдущем разделе рассматривалась проблема защиты пользователя от аварийных
ситуаций. Некоторые файловые системы также заботятся о защите пользователя от
него самого. Если пользователь намеревается набрать команду
rm *.o
чтобы удалить все файлы, оканчивающиеся на
.o
(сгенерированные компилятором
объектные файлы), но случайно набирает
rm * .o
(с пробелом после звездочки), то команда rm удалит все файлы в текущем каталоге,
а затем пожалуется, что не может найти файл
.o
. В MS-DOS и некоторых других си-
стемах при удалении файла устанавливается лишь бит в каталоге или i-узле, помечая
файл удаленным. Дисковые блоки не возвращаются в список свободных блоков до
тех пор, пока в них не возникнет насущная потребность
1
. Поэтому, если пользователь
тут же обнаружит ошибку, можно будет запустить специальную служебную программу,
которая вернет назад (то есть восстановит) удаленные файлы. В Windows удаленные
файлы попадают в Корзину (специальный каталог), из которой впоследствии при не-
обходимости их можно будет извлечь
2
. Разумеется, пока они не будут реально удалены
из этого каталога, пространство запоминающего устройства возвращено не будет.
4.4.4. Производительность файловой системы
Доступ к диску осуществляется намного медленнее, чем доступ к оперативной памя-
ти. Считывание 32-разрядного слова из памяти может занять 10 нс. Чтение с жесткого
диска может осуществляться на скорости 100 Мбит/с, что для каждого 32-разрядного
1
В случае файловых систем FAT-12 и FAT-16 для MS-DOS это не совсем верно: блоки (кла-
стеры), занимавшиеся файлом, отмечаются в FAT как свободные, но запись файла в каталоге
с потерей первого имени файла сохраняется до момента ее использования новым файлом
в данном каталоге. По сохранившимся в записи файла указателю на первый блок и размеру
файла его можно полностью восстановить, если он не был фрагментирован и освободившие-
ся блоки еще не заняты другими файлами. Иначе возможно лишь частичное восстановление
или же оно вообще невозможно. — Примеч. ред.
2
Это верно по умолчанию при удалении файлов средствами Проводника Windows. Однако его
поведение может быть изменено средствами настройки операционной системы или сторон-
ними программами. Для других программ поведение также может различаться: например,
оболочка командной строки cmd.exe удаляет файлы напрямую, не сохраняя их в Корзине.
Некоторые программы могут предоставлять выбор способа удаления файлов.