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

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

Реализация длинных имен файлов

Примеры i-узла

Преимущества:

· Быстродействие - имея i-узел можно получить информацию о всех блоках файла, не надо собирать указатели.

· Меньший объем, занимаемый в памяти. В память нужно загружать только те узлы, файлы которых используются.

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

Такие узлы используются в UNIX.

-10.5 Реализация каталогов

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

В зависимости от системы это может быть:

· дисковый адрес всего файла (для непрерывных файлов)

· номер первого блока (связные списки)

· номер i-узла

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

Также она хранит атрибуты файлов.

Варианты хранения атрибутов:

· В каталоговой записи (MS-DOS)

· В i-узлах (UNIX)

Варианты реализации каталогов

-10.5.1 Реализация длинных имен файлов

Раньше операционные системы использовали короткие имена файлов, MS-DOS до 8 символов, в UNIX Version 7 до 14 символов. Теперь используются более длинные имена файлов (до 255 символов и больше).

Методы реализации длинных имен файлов:

· Просто выделить место под длинные имена, увеличив записи каталога. Но это займет много места, большинство имен все же меньше 255.

· Применить записи с фиксированной частью (атрибуты) и динамической записью (имя файла).

Второй метод можно реализовать двумя методами:

· Имена записываются сразу после заголовка (длина записи и атрибутов)

· Имена записываются в конце каталога после всех заголовков (указателя на файл и атрибутов)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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