Организация дискового пространства. Управление внешней памятью

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

При работе с блоками фиксированного размера большое значение имеет размер блока. В некоторых системах (например, UNIX) размер блока может быть задан при форматировании. При небольшом размере блока каждый файл будет содержать много блоков. Так как чтение блока осуществляется с задержками на поиск и вращение головок, то файл будет читаться медленно. Большие блоки обеспечивают более высокую скорость обмена с диском, но вследствие внутренней фрагментации (каждый файл занимает целое число блоков и в среднем половина последнего блока пропадает) снижается процент полезного дискового пространства. Исследования, проведенные в области размера блоков файла, показали, что оптимальный размер блока составляет: 512 байт, 1 Кбайт, 2 Кбайта.

После выбора размера блока следует выбрать метод учета свободных и занятых блоков. В современных операционных системах наибольшее распространение получили два метода.

Метод 1: учет при помощи организации битового вектора (массива или бит карты, bit map, bit vector). Каждый блок представлен одним битом, принимающим значение 0 – занят или 1 – свободен. В оперативной памяти возможно хранение одного блока, если организовано обращение к диску за другим блоком, когда текущий блок переполняется. Выделяемые файлу блоки располагаются близко друг к другу, в результате чего для доступа к файлу затрачивается меньше времени на перемещение блока головок. Главное преимущество этого подхода – проста и эффективность при нахождении первого свободного блока или n последовательных блоков на диске. Метод используется в Apple Macintosh, многие компьютеры, например, семейств Intel и Motorola имеют инструкции манипулирования битами, которые могут быть использованы для этой цели. Данный метод эффективен, если битовый вектор помещается в памяти целиком, что возможно только для небольших дисков. Например, диск размером 4 Гбайт с блоками по 4 Кбайт нуждается в таблице размером 128 Кбайт для управления свободными блоками. Если битовый вектор становится большим, то для ускорения поиска в нем его разбивают на регионы и организуют структуры данных, содержащие сведения о количестве свободных блоков для каждого региона.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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