КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Использование кэширования результатов поиска файлов для ускорения поиска файла
Использование хэш-таблицы для ускорения поиска файла. Реализация длинных имен файлов Примеры 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; Просмотров: 602; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |