| Предыдущий раздел | Оглавление | Следующий раздел |
5.3.3. Реализация каталогов
При открытии файла операционная система для определения местоположения соответствующей файлу записи каталога на диске использует предоставленное пользователем имя файла. Запись каталога содержит информацию, которая необходима для осуществления поиска занятых данным файлом блоков на физическом диске. Данная информация зависит от используемой схемы размещения файлов и может быть или дисковым адресом файла, или номером первого блока файла, или номером i-узла. Основной функцией системы каталогов во всех возможных случаях является формирование информации из полученного от пользователя имени файла, которая позволит определить местоположение необходимых данных.
Каждая файловая система использует различные атрибуты файлов, например, время последнего изменения файла или имя владельца файла.
Эти атрибуты требуют хранения. В качестве самого очевидного места хранения атрибутов может выступать непосредственно сама запись каталога.
Многие системы так и делают. Такой вариант представлен на рис. 5.8 а. Данная простая конструкция предполагает, что каталог представлен в
виде списка фиксированного размера записей. Каждая запись соответствует определенному конкретному файлу и содержит фиксированной длины имя
файла, структуру, хранящую атрибуты файла, а также один или несколько дисковых адресов, которые сообщают о местоположении соответствующих файлу
блоков на физическом диске.
Системы, которые используют i-узлы, сохраняют атрибуты файлов в самих i-узлах. Запись каталога в таком случае может быть сокращена до имени файла и номера i-узла. Такой вариант представлен на рис. 5.8, б. Этот метод обладает некоторыми преимуществами перед методом размещения атрибутов в записи каталога.
Подавляющее большинство современных операционных систем выполняют поддержку длинных имен файлов с переменной длиной. Предел длины имени файла, как правило, составляет 255 символов.
Все рассмотренные способы размещения файлов и подходы к организации каталогов предполагают, что поиск в каталогах имени файла будет происходить линейно. Линейный поиск выполняется достаточно медленно в каталогах с большой вложенностью. Для ускорения поиска предлагается использовать в каждом каталоге свою хэш-таблицу. Если размер данной таблицы будет равен n, то при добавлении нового имени файла в каталог оно будет хэшироваться в некоторое число от 0 до n – 1, например, операцией деления длины имени файла на n и взятия остатка от деления. Альтернативным способом является суммирование слов, которые составляют имя файла, и деление на n получившейся суммы.
В любом случае будет просматриваться соответствующий полученному хэш-коду элемент таблицы. В данный элемент, если он не используется, будет помещен указатель на запись о файле. Данные записи находятся после хэш-таблицы. При занятом элементе таблицы будет создан связанный список, который объединяет все записи о файлах, которые имеют одинаковые хэш-коды, а заголовок полученного списка записывается в элемент таблицы.
Когда будет производиться поиск некоторого файла, будет выполняться та же последовательность действий. Имя файла сначала хэшируется, чтобы выбрать запись из хэш-таблицы. После чего проверяются все записи в цепочке, заголовок которых присутствует в элементе таблицы, на наличие имени файла. Если нужного имени файла в данной цепочке нет, то и в данном каталоге файла с таким именем нет.
Скорость поиска при использования хэш-таблицы существенно увеличивается. Недостатком же такого подхода к поиску имен файлов можно считать усложнение администрирования. Для тех систем, в которых возможно применение содержащих сотни или тысячи файлов каталогов, применение хэш-таблиц было бы наиболее эффективным.
Кэширование результатов поиска является другим способом ускорения поиска в больших каталогах. Поиск начинается с проверки кэша на наличие в нем нужного имени файла. Если искомое имя там присутствует, то расположение файла немедленно определяется. Кэширование может быть наиболее эффективным, когда результаты поиска ограничиваются только относительно небольшим количеством файлов.
| Предыдущий раздел | Оглавление | Следующий раздел |