Использование кэширования результатов поиска файлов для ускорения поиска файла.
Использование хэш-таблицы для ускорения поиска файла.
Реализация длинных имен файлов
Примеры 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 (связь, ссылка) - с ее помощью обеспечивается присутствие файла в разных каталогах.