Реализация директорий. Совместно используемые файлы

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

Для доступа к файлу операционная система использует путь (pathname), сообщенный пользователем. Запись в директории связывает имя файла или имя поддиректории с блоками данных на диске (рис. 4.12.). В зависимости от способа выделения файлу блоков диска эта ссылка может быть номером первого блока или номером индексного узла. В любом случае обеспечивается связь символьного имени файла с данными на диске. Когда система открывает файл, она ищет его имя в директории. Затем из записи в директории или из структуры, на которую запись в директории указывает, извлекаются атрибуты и адреса блоков файла на диске. Эта информация помещается в системную таблицу и ее используют все последующие ссылки на данный файл. Атрибуты файла можно хранить в директории (рис. 4.13.), однако для организации совместного доступа к файлам их удобнее хранить в индексном узле (UNIX). Во всех случаях главная функция системы директорий – трансформировать символьное имя файла в информацию, необходимую, чтобы найти данные. Ниже приведены примеры реализации директорий в некоторых операционных системах.

	Рис. 4.12. Реализация директорий

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

Разряды 8 3 1 10 2 2 2 4
Имя файла	Расширение	Атрибуты	Резервное поле	Время	Дата	Номер первого блока	Размер

Рис. 4.13. Вариант записи в директории MS-DOS

Байты	2 14
Номер индексного узла	Имя файла

Рис. 4.14. Вариант записи в директории Unix

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

1. Линейный поиск (простейший). Директория просматривается с самого начала, пока не встретится нужное имя файла. Хотя это наименее эффективный способ поиска, оказывается, что в большинстве случаев он работает с приемлемой производительностью. Метод прост, но требует временных затрат. Для создания нового файла вначале нужно проверить директорию на наличие такого же имени. Если файл с таким именем в директории существует, то пользователь получает соответствующую информацию. Затем имя нового файла вставляется в конец директории. Для удаления файла также выполняется поиск его имени в списке, и запись помечается как неиспользуемая. Реальный недостаток данного метода – последовательный поиск файла. Информация о структуре директории используется часто, и неэффективный способ поиска заметен пользователям. Можно свести поиск к бинарному, если отсортировать список файлов. Однако это усложнит создание и удаление файлов, так как требуется перемещение большого объема информации.

2. Хеш-таблица. В данном методе имена файлов также хранятся в каталоге в виде линейного списка, но дополнительно используется хеш-таблица. Построенная на ее основе хеш-функция, позволяет по имени файла получить указатель на имя файла в списке, благодаря чему, можно существенно уменьшить время поиска. В результате хеширования могут возникать коллизии, то есть ситуаций, когда функция хеширования, примененная к разным именам файлов, дает одинаковый результат. Обычно имена таких файлов объединяются в связные списки, предполагая в дальнейшем осуществление в них последовательного поиска нужного имени файла. Выбор подходящего алгоритма хеширования позволяет свести к минимуму число коллизий. Достоинство: ускоренный в несколько раз поиск файлов. Недостаток: более сложное администрирование каталогов. Метод рекомендуется применять в тех случаях, когда ожидается, что каталоги будут содержать сотни и тысячи файлов.

3.Другие методы поиска. Например, организация поиска в каталогах файловой системы NTFS при помощи В -дерева, которое стало стандартным способом организации индексов в системах баз данных.

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

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

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

Первый метод. Информация о блоках диска, занимаемых файлом, содержится не в каталоге, а в специальной структуре данных (i -узле), связанных с файлом. Записи в каталогах содержат ссылки на эту структуру данных. Данное решение используется в операционной системе UNIX.

Второй метод. Пользователь 1 устанавливает связь с файлом пользователя 2. Операционная система создает в каталоге пользователя 1 новый файл типа link (связь), который содержит полное имя пути к связываемому файлу. Когда пользователь 1 нужно прочитать данные из связываемого файла, операционная система обращается к файлу типа link, считывает указанный в нем путь и открывает связанный файл. Данный метод называется символьным связыванием.

Каждый из перечисленных методов имеет свои недостатки. В первом случае возникает необходимость в поддержке счетчика ссылок на файл для реализации операции удаления файла. Например, в операционной системе UNIX счетчик является одним из атрибутов, хранящихся в индексном узле. Удаление файла одним из пользователей уменьшает количество ссылок на файл на 1. Реальное удаление файла происходит, когда число ссылок на файл станет равным 0.

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

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

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

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

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

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

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

- синхронизация с ожиданием – требование блокировки может привести к откладыванию процесса до того момента, когда это требование может быть удовлетворено;

- синхронизация без ожидания – процесс немедленно оповещается об удовлетворении требования блокировки или о невозможности ее удовлетворения в данный момент времени.

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

Дата добавления: 2014-01-03