Совместно используемые файлы

Использование кэширования результатов поиска файлов для ускорения поиска файла.

Ускорение поиска файлов

Если каталог очень большой (несколько тысяч файлов), последовательное чтение каталога мало эффективно.

12.3.2.1 Использование хэш-таблицы для ускорения поиска файла.

Алгоритм записи файла:

· Создается хэш-таблица в начале каталога, с размером n (n записей).

· Для каждого имени файла применяется хэш-функция, такая, чтобы при хэшировании получалось число от 0 до n-1.

· Исследуется элемент таблицы соответствующий хэш-коду.

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

· Если используется, то создается связный список, объединяющие все описатели файлов с одинаковым хэш-кодом.

Алгоритм поиска файла:

· Имя файла хэшируется

· По хэш-коду определяется элемент таблицы

· Затем проверяются все описатели файла из связного списка и сравниваются с искомым именем файла

· Если имени файла в связном списке нет, это значит, что файла нет в каталоге.

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

Алгоритм поиска файла:

· Проверяется, нет ли имени файла в кэше

· Если нет, то ищется в каталоге, если есть, то берется из кэша

Такой способ дает ускорение только при частом использовании одних и тех же файлов.

Иногда нужно чтобы файл присутствовал в разных каталогах.

Link (связь, ссылка) - с ее помощью обеспечивается присутствие файла в разных каталогах.

А - совместно используемый файл.

Такая файловая система называется ориентированный ациклический граф (DAG, Directed Acyclic Graph).

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

Есть два решения этой проблемы:

1. Использование i-узлов, в каталогах хранится только указатель на i-узел. Такие ссылки называются жесткими ссылками.

2. При создании ссылки, в каталоге создавать реальный Link-файл, новый файл содержит имя пути к файлу, с которым он связан. Такие ссылки называются символьными ссылками.

12.4.1 Жесткие ссылки

Может возникнуть проблема, если владелец файла удалит его (и i-узел тоже), то указатель, каталога содержащего ссылку, будет указывать на не существующий i-узел. Потом может появиться i-узел с тем же номером, а значит, ссылка будет указывать на не существующий файл.

Поэтому в этом случае при удалении файла i-узел лучше не удалять.

Файл будет удален только после того, как счетчик будет равен 0.

Иллюстрация проблемы, которая может возникнуть

12.4.2 Символьные ссылки

Удаление файла не влияет на ссылку, просто по ссылке будет не возможно найти файл (путь будет не верен).

Удаление ссылки тоже никак не скажется на файле.

Но возникают накладные расходы, чтобы получить доступ к i-узлу, должны быть проделаны следующие шаги:

· Прочитать файл-ссылку (содержащий путь)

· Пройти по всему этому путь, открывая каталог за каталогом

Дата добавления: 2014-01-06