The design of the UNIX Operating System 80 страница
Директории в ОС Unix
Структура директории проста. Каждая запись содержит имя файла и номер его индексного узла (см. рис.12.8). Вся остальная информация о файле (тип, размер, время модификации, владелец и т. д. и номера дисковых блоков) находится в индексном узле.
Рис. 12.8. Вариант записи в директорииUnix
В более поздних версиях Unix форма записи претерпела ряд изменений, например имя файла описывает-ся структурой. Однако суть осталась прежней.
|
|
|
Поиск в директории
Список файлов в директории обычно не является упорядоченным по именам файлов. Поэтому правиль-ный выбор алгоритма поиска имени файла в директории имеет большое влияние на эффективность и на-дежность файловых систем.
Линейный поиск
Существует несколько стратегий просмотра списка символьных имен . Простейшей из них является ли-нейный поиск. Директория просматривается с самого начала, пока не встретится нужное имя файла. Хотя это наименее эффективный способ поиска, оказывается, что в большинстве случаев он работает с прием-лемой производительностью. Например , авторы Unix утверждали, что линейного поиска вполне доста-точно. По-видимому, это связано с тем, что на фоне относительно медленного доступа к диску некоторые задержки, возникающие в процессе сканирования списка, несущественны.
|
|
|
|
|
|
Метод прост, но требует временных затрат. Для создания нового файла вначале нужно проверить дирек-торию на наличие такого же имени. Затем имя нового файла вставляется в конец директории (если, разу-меется, файл с таким же именем в директории не существует, в противном случае нужно информировать
|
|
|
| Основы операционных систем | 117 |
пользователя). Для удаления файла нужно также выполнить поиск его имени в списке и пометить запись как неиспользуемую.
Реальный недостаток данного метода - последовательный поиск файла. Информация о структуре дирек-тории используется часто, и неэффективный способ поиска будет заметен пользователями. Можно свести поиск к бинарному, если отсортировать список файлов. Однако это усложнит создание и удаление фай-лов, так как требуется перемещение большого объема информации.
Хеш-таблица
Хеширование (см. например , [Ахо, 2001]) - другой способ, который может использоваться для размеще-ния и последующего поиска имени файла в директории. В данном методе имена файлов также хранятся в каталоге в виде линейного списка, но дополнительно используется хеш-таблица. Хеш-таблица , точнее построенная на ее основе хеш-функция, позволяет по имени файла получить указатель на имя файла в списке. Таким образом, можно существенно уменьшить время поиска.
В результате хеширования могут возникать коллизии, то есть ситуации, когда функция хеширования, примененная к разным именам файлов, дает один и тот же результат. Обычно имена таких файлов объе-диняют в связные списки, предполагая в дальнейшем осуществление в них последовательного поиска нужного имени файла. Выбор подходящего алгоритма хеширования позволяет свести к минимуму число коллизий . Однако всегда есть вероятность неблагоприятного исхода , когда непропорционально большо-му числу имен файлов функция хеширования ставит в соответствие один и тот же результат. В таком случае преимущество использования этой схемы по сравнению с последовательным поиском практиче-ски утрачивается.
Другие методы поиска
Дата добавления: 2021-01-21; просмотров: 126; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!