Организация
Доступ к информации, находящейся в файле, обычно выполняется в два этапа. На первом этапе по имени файла определяется его расположение, а на втором этапе (который не нужен, если файл является программой, подлежащей исполнению) выполняется поиск либо определенной физической записи по ее позиции в файле, либо логической записи по ключу или по содержимому одного или нескольких полей данных.
Каждый файл, известный операционной системе, должен иметь некоторое глобальное имя, уникальное во всей системе. Это имя может присваиваться файлу системой посредством комбинации имени файла, задаваемого пользователем, с уникальным идентификатором самого пользователя, либо (в однопроцессорных системах) со временем создания файла.
При поиске файла необходимо по неуникальному локальному имени, указанному в процессе, определить его физическое размещение. Определение уникального глобального имени, соответствующего этому локальному имени, часто осуществляется во время планирования на основе информации, указанной в командах системе, но иногда откладывается на момент открытия файла (командной ОТКРЫТЬ), если часть информации до этого момента недоступна. Затем это имя ищется в каталоге, в котором каждому глобальному имени сопоставлено физическое расположение файла.
Для каталога редко используется простая линейная организация, так как элементы каталога часто меняются. Более того, множество имен файлов, по которым осуществляется поиск элемента каталога, далеко не плотно. Поэтому для каталогов небольших размеров удобно использовать функцию расстановки.
Для больших каталогов используется многоуровневая древовидная организация, обеспечивающая уникальность имен и облегчающая поиск. При этом уникальность на верхних уровнях обеспечивается системой, а на нижних уровнях - пользователем. Каждая составная часть имени определяет ветвь, по которой следует перейти на следующий уровень дерева. Например, имя /выч/405/функц/квадр может обозначать программу для решения квадратных уравнений. Каждая вершина каталога рассматривается как некоторый справочник соответствующего уровня. Справочники на самом нижнем, листовом, уровне содержат только указатели на файлы. Элемент справочника на любом другом уровне указывает либо на файл, либо на справочник следующего, более низкого уровня. Полное имя файла, таким образом, - это имя пути к данному файлу от корневого справочника.
На каждом уровне могут быть использованы разные таблицы и разные методы поиска, исходя из предполагаемой длины справочника данного уровня. Для многоуровневого каталога независимо от того, имеет ли он древовидную структуру или нет, не требуется, чтобы все справочники были расположены друг за другом. Однако эффективность требует, чтобы высшие уровни каталога были доступными оперативно. Уровни, которые ссылаются только на автономные файлы, могут находиться на тех же самых носителях, что и сами файлы.
Некоторые системы, например Multics и UNIX, связывают с каждым процессом некоторый текущий (или “рабочий”) справочник. Имена других справочников в поддереве текущего справочника определяются просто именем пути в этом поддереве. Справочники вне данного поддерева можно получить либо двигаясь от корня дерева, либо следуя по ветви в обратном направлении. Например, в системе MS-DOS “..” обозначает имя предыдущего справочника.
Рис. 3.1.
Если пользователь знает или может получить имя файла другого пользователя, то этим файлом можно пользоваться совместно. Получив однажды это имя, последующий доступ к файлу можно осуществлять через суперпозицию произвольных связей в структуре дерева. На рис. 3.2 приведен пример, где ссылки на один и тот же файл или один и тот же справочник имеются в нескольких справочниках.
Другой способ совместного использования файлов заключается во введении так называемых “двухуровневых” файлов. Локальному имени файла ставится в соответствие некоторое уникальное глобальное имя, указатель на которое заносится в справочник пользователя Этот подход гораздо легче реализуется для каталога с функцией расстановки, чем для каталога с древовидной структурой.
Сегментация, рассмотренная ранее как метод управления оперативной памятью, служит также и для управления файлами. Файлы рассматриваются как сегменты, и даже нет необходимости отличать их от других сегментов. Неуникальность имен файлов не порождает никаких проблем, так как конфликт имен разрешается с помощью номера таблицы сегментов текущего процесса, находящегося в регистре таблиц сегментов. При, этом устраняется явный перевод локального имени файла в глобальное имя. Более того, совместное использование файла реализуется записью одного и того же номера сегмента в таблицы сегментов разных пользователей независимо от того, осуществляется ли ссылка на совместно используемый файл посредством одного и того же имени или посредством разных имен. Каталог составляется путем объединения всех таблиц сегментов, и при этом не требует для работы специальных подпрограмм.
Рис. 3.2.
В системе Multics файлы фактически являются сегментами, не отличающимися от прочих сегментов. Каталог всех сегментов системы имеет вид дерева, все вершины которого, за исключением листьев, являются сегментами справочников. В системе OS/360-370 множество файлов организовано в виде дерева с произвольными ветвлениями и глубиной. Система UNIX использует такое же дерево, но различает три типа файлов: простые файлы на дисках, справочники, имеющие древовидную структуру, и специальные файлы, сопоставленные устройствам ввода/вывода. Последние позволяют осуществлять операции ввода/вывода, используя просто имя соответствующего файла.
Рис. 3.3.
