Организация каталога в виде произвольного (простого) графа

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

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

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

 

Рисунок 13.6 - Организация каталога в виде произвольного (простого) графа

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

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

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

Проблемы защиты файлов

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

Надежность достигается за счет копирования файлов. Многие компьютерные системы включают в свой состав специальные программы, которые автоматически (или по команде оператора) копируют дисковые файлы на устройства резервного копирования.

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

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

Для многопользовательских систем, однако, нужны иные механизмы.

Типы доступа

Необходимость защиты файлов непосредственно вытекает из возможности доступа к ним. В системах, которые не разрешают доступ к файлам другим пользователям, защита не нужна. То есть только крайность в запретах полностью решает проблему защиты.

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

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

Могут контролироваться различные типы доступа, например:

­ read – читать информацию из файла;

­ write – писать информацию в файл;

­ execute – исполнить программу, хранящуюся в файле;

­ append – дописать информацию в конец файла;

­ delete – удалить файл;

­ list – получить перечень атрибутов файла.

Могут контролироваться и другие операции, например, переименование, редактирование, копирование файлов. Однако в большинстве систем эти высокоуровневые функции реализуются как системные программы, выполняющие системные вызовы низкого уровня. Защита же предусматривается на низком уровне.

Может быть предложено много различных механизмов защиты. У каждой схемы есть как достоинства, так и недостатки, которые должны быть учтены при выборе схемы в каждом конкретном случае. Небольшой компьютерной системе, которая используется ограниченной группой разработчиков, не нужны те же механизмы защиты, что и большой корпоративной системе.

Списки прав доступа

Наиболее общий подход к защите файлов от несанкционированного использования – сделать доступ зависящим от идентификатора пользователя, то есть связать с каждым файлом или директорией список прав доступа (access control list), где перечислены имена пользователей и типы разрешенных для них способов доступа к файлу. Любой запрос на выполнение операции сверяется с таким списком. Основная проблема реализации данного способа заключается в том, что список может быть длинным. Чтобы разрешить всем пользователям читать файл, необходимо всех их внести в список. У такой техники есть два нежелательных следствия:

- Конструирование подобного списка может оказаться сложной задачей, особенно если мы не знаем заранее пользователей системы.

- Запись в директории должна иметь переменный размер (включать список потенциальных пользователей).

Для решения этих проблем создают классификации пользователей, например, в ОС Unix все пользователи разделены на три группы:

- Владелец (Owner);

- Группа (Group) – набор пользователей, разделяющих файл и нуждающихся в типовом способе доступа к нему;

- Остальные (Other).

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

Другие подходы к защите

Еще один подход к решению проблемы защиты состоит в установке пароля на каждый файл. Поскольку доступ к компьютерной системе часто контролируется паролем, доступ к каждому файлу контролируется по той же схеме. Если пароли назначаются случайным образом и часто изменяются, такой подход дает высокую эффективность защиты файлов. Однако применение паролей с этой целью имеет ряд недостатков. Во-первых, число паролей, которые необходимо помнить пользователю, становится слишком большим, что делает такой подход непрактичным. Во вторых, если использовать один пароль для всех файлов, то как только он будет расшифрован, вся файловая система становится доступной. Некоторые системы, например TOPS-20, для решения этой проблемы позволяют пользователю ассоциировать пароль с подкаталогом, а не с отдельным файлом. Система IBMVS/CMS, позволяет задать три пароля для каждого минидиска – для доступа по чтению, записи и одновременного доступа к файлам с нескольких рабочих мест (multiwrite).

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

Контрольные вопросы

1. Что такое файл? Какими атрибутами он характеризуется?

2. Какие операции можно выполнять над файлами?

3. Опишите известные вам методы доступа к файлам.

4. Что такое индекс? В чем состоит эффективность применения индексов?

5. Что такое каталог? Какие операции можно выполнять над каталогами?

6. Приведите характеристики известных вам логических структур каталогов.

7. Какую иерархическую структуру имеют файловые системы ОС UNIX?

8. Зачем нужны ссылки? Какие бывают ссылки?