Организация каталога в виде графа без циклов

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

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

Древовидная структура запрещает такую форму разделения файлов и каталогов. Она возможна только при организации каталогов в виде ациклического графа. При этом один и тот же файл может находиться сразу в двух каталогах. Ациклический граф является обобщением дерева (см. рис. 13.5).

Рисунок 13.5 - Организация каталога в виде графа без циклов

Существует много способов реализации такой структуры. В общем случае, применяемом во многих реализациях UNIX, для разделения файлов и каталогов для разделения файлов и каталогов создается специальная строка в каталоге, называемая ссылкой. Ссылка – это указатель на существующий файл или каталог.

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

Другой подход к реализации разделяемых файлов – дублирование всей информации о них в обоих каталогах (физическая или жесткая ссылка). Главная проблема – поддержание идентичности соответствующих строк в каталогах при изменении атрибутов файла.

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

Кроме того, проблемы возникнут и при удалении файлов. Когда следует освободить место, занимаемое разделяемым файлом? Если его удалить сразу, как только один из пользователей попытался это сделать, то могут возникнуть висячие ссылки (на несуществующие файлы), А это очень опасно.

В системах, в которых разделение реализуется символическими ссылками, ситуация в некотором смысле проще. Удаление ссылки не приводит к удалению файла, удаляется только ссылка. Если удаляется файл, на который имеются ссылки, то освобождается дисковое пространство, учетная запись в каталоге, а ссылки остаются. Их необходимо удалять, но это очень сложно, так как, чтобы их найти, требуется полный обход файловой системы. Альтернативный подход – оставлять ссылки до первого их использования. В момент, когда задана ссылка на несуществующий файл, можно принять решение об удалении ссылки. В ОС UNIX символические ссылки при удалении файла остаются, и их актуальность – проблема пользователя. Он должен удалять такие ссылки вручную.

Возможно применение и другого подхода к удалению – сохранять файл до тех пор, пока все ссылки не будут удалены. Для реализации этого подхода необходим некоторый механизм, определения последней удаляемой ссылки. Можно, например, поддерживать список ссылок на файл. Файл удаляется, когда список пуст. Проблемой для реализации является переменный и, возможно, большой размер этого списка. На практике достаточно не вести список ссылок, а лишь подсчитывать их число. В OC UNIX такой подход применяется для жестких ссылок. MS DOS механизм ссылок не поддерживает вообще.