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

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

Со всем этим тесно связан вопрос: где следует хранить атрибуты? Каждая файловая система работает с различными атрибутами файлов, такими как имя владельца файла
и время создания, и их нужно где-то хранить. Одна из очевидных возможностей заключается в хранении их непосредственно в записи каталога. Именно так некоторые системы и делают. Этот вариант показан на рис. 4.11, а. В этой простой конструкции каталог состоит из списка записей фиксированного размера, по одной записи на каждый файл, в которой содержатся имя файла (фиксированной длины), структура атрибутов файла, а также один или несколько дисковых адресов (вплоть до некоторого максимума), сообщающих, где находятся соответствующие файлу блоки на диске.

Структура данных, содержащая атрибуты

Для систем, использующих i-узлы, имеется возможность хранить атрибуты в самих i-узлах. При этом запись каталога может быть укорочена до имени файла и номера i-узла. Этот вариант изображен на рис. 4.11, б. Позже мы увидим, что этот метод имеет некоторые преимущества перед методом размещения атрибутов в записи каталога.

До сих пор мы предполагали, что файлы имеют короткие имена фиксированной длины. В MS-DOS у файлов имелось основное имя, состоящее из 1-8 символов, и необязательное расширение имени, состоящее из 1-3 символов. В UNIX версии 7 имена файлов состояли из 1-14 символов, включая любые расширения. Но практически все современные операционные системы поддерживают длинные имена переменной длины. Как это может быть реализовано?

Проще всего установить предел длины имени файла — как правило, он составляет 255 символов, — а затем воспользоваться одной из конструкций, показанных на рис. 4.11, отводя по 255 символов под каждое имя. Этот подход при всей своей простоте ведет к пустой трате пространства, занимаемого каталогом, поскольку такие длинные имена бывают далеко не у всех файлов. Из соображений эффективности нужно использовать какую-то другую структуру.

Один из альтернативных подходов состоит в отказе от предположения о том, что все записи в каталоге должны иметь один и тот же размер. При таком подходе каждая запись в каталоге начинается с порции фиксированного размера, обычно начинающейся с длины записи, за которой следуют данные в фиксированном формате, чаще всего включающие идентификатор владельца, дату создания, информацию о защите и прочие атрибуты. Следом за заголовком фиксированной длины идет часть записи переменной длины, содержащая имя файла, каким бы длинным оно ни было (рис. 4.12, а), с определенным для данной системы порядком следования байтов в словах (например, для SPARC — начиная со старшего). В приведенном примере

показаны три файла: project-budget, personnel и foo. Имя каждого файла завершается специальным символом (обычно 0), обозначенным на рисунке перечеркнутыми квадратиками. Чтобы каждая запись в каталоге могла начинаться с границы слова, имя каждого файла дополняется до целого числа слов байтами, показанными на рисунке закрашенными прямоугольниками.

Рис. 4.12. Два способа реализации длинных имен в каталоге: а — непосредственно в записи;

б — в общем хранилище имен (куче)


Недостаток этого метода состоит в том, что при удалении файла в каталоге остается промежуток произвольной длины, в который описатель следующего файла может и не поместиться. Эта проблема по сути аналогична проблеме хранения на диске непрерывных файлов, только здесь уплотнение каталога вполне осуществимо, поскольку он полностью находится в памяти. Другая проблема состоит в том, что какая-нибудь запись каталога может разместиться на нескольких страницах памяти и при чтении имени файла может произойти ошибка отсутствия страницы.

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

При всех рассмотренных до сих пор подходах к организации каталогов, когда нужно найти имя файла, поиск в каталогах ведется линейно, от начала до конца. Линейный поиск в очень длинных каталогах может выполняться довольно медленно. Ускорить поиск поможет присутствие в каждом каталоге хэш-таблицы. Пусть размер такой таблицы будет равен п. При добавлении в каталог нового имени файла оно должно хэшироваться в число от 0 до п - 1, к примеру, путем деления его на п и взятия остатка. В качестве альтернативы можно сложить слова, составляющие имя файла, и получившуюся сумму разделить на п или сделать еще что-либо подобное[13].

В любом случае просматривается элемент таблицы, соответствующий полученному хэш-коду. Если элемент не используется, туда помещается указатель на запись о файле. Эти записи следуют сразу за хэш-таблицей. Если же элемент таблицы уже занят, то создается связанный список, объединяющий все записи о файлах, имеющих одинаковые хэш-коды, и заголовок этого списка помещается в элемент таблицы.

При поиске файла производится такая же процедура. Для выбора записи в хэш-таблице имя файла хэшируется. Затем на присутствие имени файла проверяются все записи в цепочке, чей заголовок помещен в элементе таблицы. Если искомое имя файла в этой цепочке отсутствует, значит, в каталоге файла с таким именем нет.

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

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

4.3.4.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Реализация каталогов:

  1. Чудо, связанное с каталогом «Nightingale-Conant»
  2. Глава 6. Реализация права
  3. 4.2. Реализация
  4. 4. Реализация прав по ипотеке
  5. 3.3. Дальнейшая реализация проекта
  6. РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ
  7. 10. Реализация заложенного имущества
  8. Механизм реализации личности
  9. Статья 591. Реализация предмета залога
  10. Практическая реализация.
  11. Практическая реализация.
  12. Практическая реализация.
  13. Основные психологические функции и инструментарий их реализации.
  14. 6.3. Примеры практической реализации метода анализа утверждений
  15. 6.3. Примеры практической реализации метода анализа утверждений
  16. 6.1. Понятие и формы реализации права
  17. 3. Реализация прав, вытекающих из залога
  18. 14.2. Реализация моделей клеточных автоматов на ЭВМ