Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Часть 1 Основные понятия
3.2.1 Введение в ОС
Все компьютерные приложения нуждаются в хранении и обновлении информации. Возможности оперативной памяти для хранения информации ограничены. Во-первых, оперативная память обычно теряет свое содержимое после отключения питания, а во-вторых, объем обрабатываемых данных зачастую превышает ее возможности. Кроме того, информацию желательно иметь в виде, независимом от процессов. Поэтому принято хранить данные на внешних носителях (обычно это диски) в единицах, называемых файлами. В большинстве компьютерных систем предусмотрены устройства внешней (вторичной) памяти, большой емкости, на которых можно хранить огромные объемы данных. Однако характеристики доступа к таким устройствам существенно отличаются от характеристик доступа к основной памяти. Чтобы повысить эффективность использования этих устройств, был разработан ряд специфичных для них структур данных и алгоритмов
История систем управления данными во внешней памяти начинается еще с магнитных лент, но современный облик они приобрели с появлением магнитных дисков. До этого каждая прикладная программа сама решала проблемы именования данных и структуризации данных во внешней памяти. Это затрудняло поддержание на внешнем носителе нескольких архивов долговременно хранимой информации. Историческим шагом явился переход к использованию централизованных систем управления файлами. Система управления файлами берет на себя распределение внешней памяти, отображение имен файлов в адреса внешней памяти и обеспечение доступа к данным.
Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы организовать эффективную работу с данными, хранящимися во внешней памяти и обеспечить пользователю удобный интерфейс при работе с этими данными. Организовать хранение информации на магнитном диске непросто. Это требует хорошего знания устройства контроллера диска, особенностей работы с его регистрами и.т. д. (этим обычно занимается компонент системы ввода-вывода ОС, называемый драйвером диска). Для того чтобы избавить пользователя компьютера от сложностей взаимодействия с аппаратурой и была придумана ясная абстрактная модель файловой системы. Операции записи или чтения файла концептуально проще, чем низкоуровневые операции работы с устройствами.
Основная идея использования внешней памяти состоит в следующем. ОС делит ее на блоки фиксированного размера, например, 4096 байт. С точки зрения пользователя каждый файл состоит из набора индивидуальных элементов, называемых записями (например, характеристика какого-нибудь объекта). Каждый файл хранится в виде определенной последовательности блоков (не обязательно смежных); каждый блок хранит целое число записей. В некоторых ОС (MS-DOS) адреса блоков, содержащих данные файла, могут быть организованы в связный список и вынесены в отдельную таблицу в памяти. В других ОС (Unix), адреса блоков данных файла хранятся в отдельном блоке внешней памяти (так называемом индексе или индексном узле). Этот прием называется индексацией и является наиболее распространенным для приложений, требующих произвольного доступа к записям файлов. Индекс файла состоит из списка элементов, каждый из которых содержит номер блока в файле и указание о местоположении данного блока. В современных ОС файлы обычно представляют собой неструктурированную последовательность байтов (длина записи равна 1) и считывание очередного байта осуществляется с так называемой текущей позиции, которая характеризуется смещением от начала файла. Зная размер блока, легко вычислить номер блока, содержащего текущую позицию. Адрес же нужного блока диска можно затем извлечь из индекса файла. Базовой операцией, выполняемой по отношению к файлу, является чтение блока с диска и перенос его в буфер, находящийся в основной памяти.
Файловая система позволяет при помощи системы справочников (каталогов, директорий) связать уникальное имя файла с блоками вторичной памяти, содержащими данные файла. Иерархическая структура каталогов, используемая для управления файлами, является другим примером индексной структуры. В этом случае каталоги или папки играют роль индексов, каждый из которых содержит ссылки на свои подкаталоги. С этой точки зрения вся файловая система компьютера представляет собой большой индексированный файл.
Понятие «файловая система» включает:
Файлы управляются ОС. То, как они структурированы, поименованы, используются, защищены, реализованы - одна из главных тем проектирования ОС.
Перечислим основные функции файловой системы:
Иногда говорят, что файл - поименованный набор связанной информации, записанной во вторичную память. Для большинства пользователей файловая система - наиболее видимая часть ОС. Она предоставляет механизм для он-лайнового хранения и доступа, как данным, так и программам ОС для всех пользователям системы. С точки зрения пользователя файл - минимальная величина внешней памяти, то есть данные, записанные на диск должны быть в составе какого-нибудь файла.
Важный аспект организации файловой системы - учет стоимости операций взаимодействия с вторичной памятью. Процесс считывания блока диска состоит из позиционирования считывающей головки над дорожкой, содержащей требуемый блок, ожидания, пока требуемый блок сделает оборот и окажется под головкой и собственно считывания блока. Для этого требуется значительное время (десятки миллисекунд). В современных компьютерах обращение к диску примерно в 100000 медленнее, чем обращение к памяти. Таким образом, критерием вычислительной сложности алгоритмов, работающих с внешней памятью, является количество обращений к диску.
В данной главе рассмотрены вопросы структуры, именования, защиты файлов, операции, разрешенные над файлами, организация файлового архива. Проблемы выделения дискового пространства, обеспечения производительной работы файловой системы и ряд других, интересующие дизайнеров системы, вынесены в следующую главу.
3.2.2 Имена файлов
Файлы - абстрактные объекты. Они предоставляют пользователям возможность сохранять информацию, скрывая от него детали того, как и где она хранится и то, как диски в действительности работают. Вероятно, одна из наиболее важных характеристик любого абстрактного механизма - способ именования объектов, которыми он управляет. Когда процесс создает файл, он дает файлу имя. После завершения процесса файл продолжает существовать и через свое имя может быть доступен другим процессам.
Многие ОС поддерживают имена из двух частей (имя+расширение), например progr.c(файл, содержащий текст программы на языке Си) или autoexec.bat (файл, содержащий команды интерпретатора командного языка). Тип расширения файла позволяет ОС организовать работу с ним различных прикладных программ в соответствии с заранее оговоренными соглашениями.
Обычно ОС накладывают некоторые ограничения, как на используемые в имени символы, так и на длину имени. Например, в ОС Unix учитывается регистр при вводе имени файла (case sensitive), а в MS-DOS - нет. В популярной файловой системе FAT длина имен ограничивается известной схемой 8.3 (8 символов - собственно имя, 3 символа - расширение имени). Современные файловые системы, как правило, поддерживают более удобные для пользователя длинные символьные имена файлов. Так, в соответствии со стандартом POSIX, в ОС UNIX допускаются имена длиной до 255 символов, та же самая длина устанавливается для имен файлов и в ОС Windows NT для файловой системы NTFS.
3.2.3 Структура файлов
Как уже говорилось, программист воспринимает файл в виде набора логических записей. Логическая запись - это наименьший элемент данных, которым может оперировать программа при обмене с внешним устройством. Даже если физический обмен с устройством осуществляется большими единицами (обычно блоками), операционная система обеспечивает программисту доступ к отдельной логической записи.
ОС поддерживают несколько вариантов структуризации файлов.
Первый из них, файл, как неструктурированная последовательность байтов. Например, в файловых системах ОС UNIX и MS-DOS файл имеет простейшую логическую структуру - последовательность однобайтовых записей.
ОС не осуществляет никакой интерпретации этих байтов. Тем не менее, ОС с файловыми системами данного типа должны поддерживать, по крайней мере, одну структуру - выполняемый файл - для запуска программ. Этой схеме присущи максимальная гибкость и универсальность. Используя базовые системные вызовы (или функции библиотеки ввода/вывода), пользователи могут, как угодно структурировать файлы. В частности, многие СУБД хранят свои базы данных в обычных файлах.
Первый шаг в структурировании - хранение файла в виде последовательности записей фиксированной длины, каждая из которых имеет внутреннюю структуру. Центральная идея этой схемы - операция чтения проводится над записью и операция записи - переписывает или добавляет запись целиком. Ранее были записи по 80 байт (соответствовало числу позиций в перфокарте) или по 132 символа (ширина принтера). В ОС CP/M файлы были последовательностями 128-символьных записей. С введением CRT терминалов эта идея утратила популярность.
Третий способ представления файлов - последовательность записей переменной длины, каждая из которых содержит ключевое поле в фиксированной позиции внутри записи. Базисная операция в данном случае - считать запись с каким-либо значением ключа. Записи могут располагаться в файле последовательно (например, будучи отсортированы по значению ключевого поля) или в более сложном порядке.
Рис. 3.2.1. Файл, как последовательность записей переменной длины
Использование индексов файлов, хранящих адреса записей, позволяет обеспечить быстрый доступ к отдельной записи (индексно-последовательная организация, см. также раздел 11.5). При добавлении новой записи в файл, место, куда ее поместить будет определено не пользователем, а операционной системой. Такой способ применяется в больших мэйнфреймах для коммерческих процессов обработки данных.
3.2.4 Типы и атрибуты файлов
Важный аспект дизайна файловой системы и ОС - следует ли поддерживать и распознавать типы файлов. Если да, то это может помочь правильному функционированию ОС, например не допустить вывода на принтер бинарного файла.
К типам файлов, поддерживаемых современными ОС, относят регулярные (обычные) файлы и директории. Обычные (регулярные) файлы содержат пользовательскую информацию. Директории (справочники, каталоги) - системные файлы, поддерживающие структуру файловой системы. В каталоге содержится перечень файлов, входящих в него, и устанавливается соответствие между файлами и их характеристиками (атрибутами). Мы будем рассматривать директории ниже.
Напомним, что хотя внутри подсистемы управления файлами обычный файл представляется в виде набора блоков внешней памяти, для пользователей обеспечивается представление файла в виде линейной последовательности байтов. Такое представление позволяет использовать абстракцию файла при работе с внешними устройствами, при организации межпроцессных взаимодействий и т.д. Поэтому, иногда к файлам приписывают другие объекты ОС, например, специальные символьные файлы и специальные блочные файлы, именованные каналы и сокеты, имеющие файловый интерфейс. Эти объекты рассмотрены в других разделах данного курса.
Далее, главным образом, речь пойдет об обычных файлах.
Обычные (или регулярные) файлы реально представляют собой набор блоков (возможно, пустой) на устройстве внешней памяти, на котором поддерживается файловая система. Такие файлы могут содержать как текстовую информацию (обычно в формате ASCII), так и произвольную двоичную информацию.
Обычные регулярные файлы бывают - ASCII и бинарные.
ASCII файлы содержат строки текста, которые можно распечатать, увидеть на экране или редактировать обычным текстовым редактором.
Другой тип файлов - бинарные файлы, означает, что это не ASCII файлы. Обычно они имеют некоторую внутреннюю структуру. Например, выполнимый Unix файл имеет пять секций: заголовок, текст, данные, биты реаллокации и символьную таблицу. ОС выполняет файл, только если он имеет нужный формат. Другим примером бинарного файла может быть архивный файл.
Типизация файлов не слишком строгая.
Обычно прикладные программы, работающие с файлами, распознают тип файла по его имени в соответствии с общепринятыми соглашениями. Например, файлы с расширениями .c, .pas, .txt - ASCII файлы, файлы с расширениями .exe - выполнимые, файлы с расширениями .obj, .zip - бинарные и т.д.
Помимо имени ОС часто связывают с каждым файлом и другую информацию, например дату модификации, размер и т.д. Эти другие характеристики файлов называются атрибутами. Список атрибутов может варьироваться от одной ОС к другой. Он может включать: атрибуты защиты, пароль, имя создателя, флаги скрытости, архивности, системности, бинарности, тип доступа, длину записи, позицию ключа, время, дату, размер и т.д.
Эта информация обычно хранится в структуре директорий (см. раздел реализация директорий) или других структурах, обеспечивающих доступ к данным файла.
3.2.5 Доступ к файлам
Для использования информации, хранимой в файлах, она должна быть считана в память компьютера. Есть несколько способов доступа к файлам.
Ранние ОС давали только один способ доступа - последовательный (модель ленты). Записи считывались в порядке поступления. Текущая позиция считывания могла быть возвращена к началу файла (rewind). Вместе с магнитными барабанами и дисками появились файлы с прямым (random) доступом. Для специфицирования места, с которого надо начинать чтение используются два способа: с начала, или с текущей позиции, которую дает операция seek.
Последовательный доступ базируется на модели ленты и работает как на устройствах последовательного доступа, так и прямого. Это наиболее общая модель. Организация прямого доступа существенна для многих приложений, например, для систем управления базами данных.
Не все системы поддерживают оба (последовательный и прямой) метода доступа. Последовательный доступ легко эмулировать при помощи прямого, однако реализация прямого доступа через последовательный была бы очень неэффективной.
Помимо прямого и последовательного существуют и другие методы доступа. Обычно они включают конструирование индекса файла и базируются на прямом методе доступа. Для поиска записи вначале происходит обращение к индексу, где находится указатель на нужную запись.
Предположим, что имеется большой файл, содержащий разнообразные сведения о студентах, состоящих из записей с несколькими полями, и возникает задача организации быстрого поиска по одному из полей, например по фамилии студента.
Рис. 3.2.2 Пример организации индекса для последовательного файла
Рис. иллюстрирует решение данной проблемы - организацию индексно-последовательного метода доступа к фалу.
Способ выделения дискового пространства при помощи индексных узлов, применяемый в ряде ОС (Unix и ряде других, см. следующую главу) может служить другим примером организации индекса.
В этом случае ОС использует древовидную организацию блоков, при которой блоки, составляющие файл, являются листьями дерева, а каждый внутренний узел содержит указатели на множество блоков файла. Для больших файлов индекс может быть слишком большим. В этом случае создают индекс для индексного файла (блоки промежуточного уровня или блоки косвенной адресации).
3.2.6 Операции над файлами.
Операционная система должна предоставить в распоряжение пользователя набор операций для работы с файлами, реализованных через системные вызовы. Чаще всего при работе с файлом пользователь выполняет не одну, а несколько операций. Во-первых, нужно найти данные файла и его атрибуты по его символьному имени, во-вторых, считать необходимые атрибуты файла в отведенную область оперативной памяти и проанализировать права пользователя на выполнение требуемой операции. Затем выполнить операцию, после чего освободить занимаемую данными файла область памяти. Рассмотрим в качестве примера основные файловые операции ОС Unix:
Существует два способа выполнить последовательность действий над файлами [30]:
В первом случае для каждой операции выполняются как универсальные, так и уникальные действия (схема stateless). Например, последовательность операций может быть такой: open, read1, close, ... open, read2, close, ... open, read3, close.
Альтернативный способ, это когда универсальные действия выполняются в начале и в конце последовательности операций, а для каждой промежуточной операции выполняются только уникальные действия. В этом случае последовательность вышеприведенных операций будет выглядеть так: open, read1, ... read2, ... read3, close.
Большинство ОС использует второй способ, как более экономичный и быстрый. Первый способ более устойчив к сбоям, поскольку результаты каждой операции становятся независимыми от результатов предыдущей операции, поэтому он иногда применяется в распределенных системах (например, Sun NFS).
3.2.7 Директории. Логическая структура файлового архива.
Количество файлов на компьютере может быть большим. Отдельные системы хранят тысячи файлов, занимающие сотни гигабайтом диска. Эффективное управление этими данными подразумевает наличие в них четкой логической структуры. Все современные файловые системы поддерживают многоуровневое именование файлов за счет поддержания во внешней памяти дополнительных файлов со специальной структурой - каталогов (или директорий).
Каждый каталог содержит список каталогов и/или файлов, содержащихся в данном каталоге. Каталоги имеют один и тот же внутренний формат, где каждому файлу соответствует одна запись в файле директории.
Рис. 3.2.3 Директории. (а) Атрибуты внутри записи в директории. (б) Атрибуты в другой структуре
Когда система открывает файл, она ищет имя файла в директории. Затем извлекаются атрибуты и адреса блоков файла на диске или непосредственно из записи в директории или из структуры, на которую запись в директории указывает. Эта информация помещается в системную таблицу в главной памяти. Все последующие ссылки на этот файл используют эту информацию.
Число директорий зависит от системы. В ранних ОС имелась только одна корневая директория, затем появились директории для пользователей (по одной директории на пользователя). В современных ОС используется произвольная структура дерева директорий.
Таким образом, файлы на диске образуют иерархическую древовидную структуру (см. рис. 3.2.4).
Рис. 3.2.4 Древовидная структура файловой системы
Существует несколько эквивалентных способов изображения дерева, структура перевернутого дерева, приведенного на рис. 3.2.4, наиболее популярна. Верхнюю вершину называют корнем. Если элемент дерева не может иметь потомков, он называется терминальной вершиной или листом (в данном случае является файлом). Не листовые вершины - справочники или каталоги, содержат списки листовых и не листовых вершин. Путь от корня к файлу однозначно определяет файл.
Внутри одного каталога имена листовых файлов уникальны. Имена файлов, находящихся в разных каталогах могут совпадать. Для того чтобы однозначно определить файл по его имени (избежать коллизии имен) принято именовать файл полным именем (pathname), которое состоит из списка имен вложенных каталогов, по которому можно найти путь от корня к файлу, плюс имя файла в каталоге, непосредственно содержащем данный файл. Таким образом, имя включает цепочку имен - путь к файлу, например /usr/ast/mailbox . Это так называемое абсолютное имя. Такие имена уникальны. Компоненты пути разделяют символами "/" (слеш) в Unix или обратными слешами в MS-DOS (в Multics - ">").
Другой способ задания имени - относительный путь к файлу. Он использует концепцию рабочей или текущей директории, которая входит в состав окружения (environment) процесса, работающего с данным файлом. Например, в ОС Linux рабочая директория является частью структуры данных процесса. Тогда к файлам в такой директории можно ссылаться только по имени, при этом поиск файла будет осуществляться в рабочей директории. Это удобнее, но по существу то же самое, что и абсолютная форма.
Для получения доступа к файлу и локализации его блоков система должна выполнить навигацию по каталогам. Рассмотрим для примера путь /usr/linux/progr.c. Алгоритм одинаков для всех иерархических систем. Сначала в фиксированном месте на диске находится корневая директория. Затем находится компонент пути usr, т.е. в корневой директории ищется файл /usr. Исследуя этот файл, система понимает, что данный файл является каталогом, и блоки данных данного файла рассматривает как список файлов и ищет следующий компонент linux в нем. Из строки для linux находится файл, соответствующий компоненту usr/linux/. Затем также находится компонент progr.c, который затем открывается, заносится в таблицу открытых файлов и сохраняется в ней до закрытия файла.
Отклонение от типовой обработки компонентов pathname может возникнуть в том случае, когда этот компонент является не обычным каталогом с соответствующим ему индексным узлом и списком файлов, а служит точкой монтирования другого файлового архива к данной файловой системе. Этот случай рассмотрен в следующей главе.
Многие прикладные программы работают с файлами, находящимися в текущей директории, не указывая явным образом ее имени. Это дает возможность пользователю возможность произвольным образом именовать каталоги, содержащие различные программные пакеты. Для реализации этой возможности в большинстве ОС, поддерживающих иерархическую структуру директорий, используется обозначение '.' - для текущей директории и '..' - для родительской.
Задание пути к файлу в файловых системах некоторых ОС отличаются тем, с чего начинается эта цепочка имен. В этом отношении есть несколько вариантов. В некоторых системах управления файлами требуется, чтобы каждый архив файлов (полное дерево справочников) целиком располагался на одном диске (или логическом диске, разделе физического дискового пакета, представляемом с помощью средств операционной системы как отдельный диск). В этом случае полное имя файла начинается с имени дискового устройства, на котором установлен соответствующий диск (буквы диска). Например, c:\util\nu\ndd.exe. Такой способ именования используется в файловых системах фирм DEC и Microsoft
В других системах (Multics) вся совокупность файлов и каталогов представляет собой единое дерево. Сама система, выполняя поиск файлов по имени, начиная с корня, требовала установки необходимых дисков.
В ОС Unix предполагается наличие нескольких архивов файлов, каждый на своем разделе, один из которых считается корневым. После запуска системы можно "смонтировать" корневую файловую систему и ряд изолированных файловых систем в одну общую файловую систему.
Технически это производится с помощью заведения в корневой файловой системе специальных пустых каталогов (см. также следующую главу). Специальный системный вызов "mount" ОС UNIX позволяет подключить к одному из этих пустых каталогов корневой каталог указанного архива файлов. После монтирования общей файловой системы именование файлов производится так же, как если бы она с самого начала была централизованной. Задачей ОС является беспрепятственный проход точки монтирования при получении доступа к файлу по цепочке имен. Если учесть, что обычно монтирование файловой системы производится при раскрутке системы, то пользователи ОС UNIX обычно и не задумываются об исходном происхождении общей файловой системы.
.8 Операции над директориями
Так же, как и в случае файлов, система обязана обеспечить пользователя набором операций, необходимых для работы с директориями, реализованных через системные вызовы. Несмотря на то, что директории, это файлы, логика работы с ними отличается от логики работы с обычными файлами и определяется природой этих объектов, предназначенных поддерживать структуру файлового архива. Совокупность системных вызовов для управления директориями зависит от особенностей конкретной ОС. Рассмотрим в качестве примера некоторые системные вызовы ОС Unix.
Имеется также ряд других системных вызовов, например, связанных с защитой информации.
3.2.9 Защита файлов.
Информация в компьютерной системе должна быть защищена как от физического разрушения (reliability), так и от несанкционированного доступа (protection).
Здесь мы коснемся отдельных аспектов защиты, связанных с контролем доступа к файлам.
3.2.9.1 Контроль доступа к файлам
Наличие в системе многих пользователей предполагает организацию контролируемого доступа к файлам. Выполнение любой операции над файлом должно быть разрешено только в случае наличия у пользователя соответствующих привилегий. Обычно контролируются следующие операции: Read, Write, Execute, Append, Delete, List
Другие операции, например, копирование файлов или их переименование также могут контролироваться. Однако они чаще реализуются через перечисленные. Так, операцию копирования файлов можно представить как операцию чтения и последующую операцию записи.
3.2.9.2 Списки прав доступа
Наиболее общий подход к защите файлов от несанкционированного использования - сделать доступ зависящим от идентификатора пользователя, то есть связать с каждым файлом или директорией список прав доступа (access control list), где перечислены имена пользователей и типы разрешенных для них способов доступа к файлу. Любой запрос на выполнение операции сверяется с таким списком. Основная проблема реализации такого способа - список может быть длинным. Чтобы разрешить всем пользователям читать файл, необходимо всех их внести в список. У этой техники есть два нежелательных следствия:
Конструирование такого списка может быть сложной задачей, особенно если мы не знаем заранее список пользователей системы.
Запись в директории должна теперь иметь переменный размер (включать список потенциальных пользователей).
Для решения этих проблем создают классификации пользователей, например, в ОС Unix все пользователи разделены на три группы:
3.2.10 Резюме
Итак, файловая система, есть набор файлов и директорий и операций над ними. Имена, структуры, файлов, способы доступа к ним и их атрибуты - важные аспекты дизайна файловой системы. Большинство современных ОС поддерживает иерархическую систему каталогов или директорий с возможным вложением директорий. Безопасность файловой системы - одна из важнейших концепций ОС.
Часть 2 Реализация файловой системы
3.2.11 Интерфейс файловой системы.
Как уже говорилось, файловая система должна организовать эффективную работу с данными, хранящимися во внешней памяти и предоставить пользователю возможности для запоминания и выборки данных в нем.
Для организации хранения информации на диске пользователь вначале обычно выполняет его форматирование, выделяя на нем место для структур данных, которые описывают состояние файловой системы в целом. Затем пользователь создает нужную ему структуру каталогов (или директорий), которые по существу являются списками вложенных каталогов и собственно файлов. И, наконец, заполняет дисковое пространство файлами, приписывая их тому или иному каталогу. Таким образом, ОС должна предоставить в распоряжение пользователя совокупность сервисов традиционно реализованных через системные вызовы, которые обеспечивают:
Кроме того, файловые службы могут решать проблемы проверки и сохранения целостности файловой системы, проблемы повышения производительности и ряд других.
Прежде чем приступить к описанию работы отдельных файловых операций, необходимо рассмотреть ключевые алгоритмы и структуры данных, которые обеспечивают функционирование файловой системы.
3.2.12 Общая структура файловой системы
Система хранения данных на дисках может быть структурирована следующим образом (см. рис. 3.2.5).
Нижний уровень - оборудование. Это в первую очередь, магнитные диски с подвижными головками - основные устройства внешней памяти, представляющие собой пакеты магнитных пластин (поверхностей), между которыми на одном рычаге двигается пакет магнитных головок. Шаг движения пакета головок является дискретным и каждому положению пакета головок логически соответствует цилиндр магнитного диска. Цилиндры делятся на дорожки (треки), а каждая дорожка размечается на одно и то же количество блоков (секторов), таким образом, что в каждый блок можно записать по максимуму одно и то же число байтов. Следовательно, для произведения обмена с магнитным диском на уровне аппаратуры нужно указать номер цилиндра, номер поверхности, номер блока на соответствующей дорожке и число байтов, которое нужно записать или прочитать от начала этого блока. Таким образом, диски могут быть разбиты на блоки фиксированного размера, и можно непосредственно получить доступ к любому блоку (организовать прямой доступ к файлам).
Непосредственно с устройствами (дисками) взаимодействует часть ОС, называемая система ввода-вывода (см. соответствующую главу). Система ввода-вывода (она состоит из драйверов устройств и обработчиков прерываний для передачи информации между памятью и дисковой системой) предоставляет в распоряжение более высокоуровневого компонента ОС - файловой системы используемое дисковое пространство в виде непрерывной последовательности блоков фиксированного размера. Система ввода-вывода имеет дело с физическими блоками диска, которые характеризуются адресом, например, диск 2, цилиндр 75, сектор 11. Файловая система имеет дело с логическими блоками, каждый из которых имеет номер (от 0 или 1 до N). Размер этих логических блоков файла совпадает или кратен размеру физического блока диска и может быть задан равным размеру страницы виртуальной памяти, поддерживаемой аппаратурой компьютера совместно с операционной системой.
В структуре системы управления файлами можно выделить базисную подсистему, которая отвечает за выделение дискового пространства конкретным файлам, и более высокоуровневую логическую подсистему, которая использует структуру дерева директорий для предоставления модулю базисной подсистемы необходимой ей информации исходя из символического имени файла. Она также ответственна за авторизацию доступа к файлам (см. главу Безопасность ОС).
Рис. 3.2.5 Блок схема файловой системы
В современных ОС далее принято разбивать диски на логические диски (это также низкоуровневая операция), иногда называемые разделами (partitions). Бывает, что наоборот объединяют несколько физических дисков в один логический диск (например, как это можно сделать в ОС Windows NT). На каждом разделе можно иметь свою независимую файловую систему. Поэтому в дальнейшем изложении мы будем игнорировать проблему физического выделения пространства для файлов и считать, что каждый раздел представляет собой отдельный (виртуальный) диск. Собственно диск содержит иерархическую древовидную структуру, состоящую из набора файлов, каждый из которых является хранилищем данных пользователя, и каталогов или директорий (то есть файлов, которые содержат перечень других файлов, входящих в состав каталога), которые необходимы для хранения информации о файлах системы.
Стандартный запрос на открытие (open) или создание (creat) файла поступает от прикладной программы к логической подсистеме. Логическая подсистема, используя структуру директорий, проверяет права доступа и вызывает базовую подсистему для получения доступа к блокам файла. После этого файл считается открытым, содержится в таблице открытых файлов, прикладная программа получает в свое распоряжение дескриптор (или handle в системах Microsoft) этого файла. Дескриптор файла является ссылкой на файл в таблице открытых файлов и используется в запросах прикладной программы на чтение-запись из этого файла. Запись в таблице открытых файлов указывает через систему аллокации блоков диска на блоки данного файла. Если к моменту открытия файл уже используется другим процессом, то есть содержится в таблице открытых файлов, то, после проверки прав доступа к файлу может быть организован совместный доступ. При этом новому процессу также возвращается дескриптор - ссылка на файл в таблице открытых файлов. Далее в тексте подробно проанализирована работа наиболее важных системных вызовов.
3.2.13 Структура файловой системы на диске.
Прежде чем рассмотреть структуру данных файловой системы на диске необходимо рассмотреть алгоритмы выделения дискового пространства и способы учета свободной и занятой дисковой памяти.
3.2.13.1 Методы выделения дискового пространства
Ключевой вопрос реализации способ связывания файлов с блоками диска. В ОС используется несколько методов выделения файлу дискового пространства. Для каждого метода сведения о локализации блоков данных файла можно извлечь из записи в директории, соответствующей символьному имени файла.
Выделение непрерывной последовательностью блоков
Простейший способ - хранить каждый файл, как непрерывную последовательность блоков диска. При непрерывном расположении файл характеризуется адресом и длиной (в блоках). Файл, стартующий с блока b, занимает затем блоки b+1, b+2, ... b+n-1.
Эта схема имеет два преимущества. Во-первых, ее легко реализовать, т.к. выяснение местонахождения файла сводится к вопросу, где находится первый блок. Во-вторых, она обеспечивает хорошую производительность, т.к. целый файл может быть считан за одну дисковую операцию.
Непрерывное выделение используется в ОС IBM/CMS, в ОС RSX-11 (для выполняемых файлов) и в ряде других.
Основная проблема, вследствие чего этот способ мало распространен - трудно найти место для нового файла. В процессе эксплуатации диск представляет собой некоторую совокупность свободных и занятых фрагментов. Проблема непрерывного расположения может рассматриваться как частный случай более общей проблемы выделения n блоков из списка свободных дыр. Наиболее распространенные стратегии решения этой проблемы - first fit, best fit и worst fit (ср. с проблемой выделения памяти). Таким образом, метод страдает от внешней фрагментации, в зависимости от размера диска и среднего размера файла, в большей или меньшей степени.
Кроме того, непрерывное распределение внешней памяти не применимо до тех пор, пока не известен максимальный размер файла. Иногда размер выходного файла оценить легко (при копировании). Чаще, однако, это трудно сделать. Если места не хватило, то пользовательская программа может быть приостановлена, предполагая выделение дополнительного места для файла при последующем рестарте. Некоторые ОС используют модифицированный вариант непрерывного выделения основные блоки файла + резервные блоки. Однако с выделением блоков из резерва возникают те же проблемы, так как возникает задача выделения непрерывной последовательности блоков диска теперь уже из совокупности резервных блоков.
Связный список
Метод распределения блоков в виде связного списка решает основную проблему непрерывного выделения, то есть устраняет внешнюю фрагментацию. Каждый файл - связный список блоков диска. Запись в директории содержит указатель на первый и последний блоки файла. Каждый блок содержит указатель на следующий блок.
Рис. 3.2.6 Хранение файла в виде связного списка дисковых блоков
Внешняя фрагментация для данного метода отсутствует. Любой свободный блок может быть использован для удовлетворения запроса. Заметим, что нет необходимости декларировать размер файла в момент создания. Файл может неограниченно расти.
Связное выделение имеет, однако, несколько существенных недостатков.
Во-первых, при прямом доступе к файлу для поиска i-го блока нужно осуществить несколько обращений к диску, последовательно считывая блоки от 1 до i-1, то есть выборка логически смежных записей, которые занимают физически несмежные секторы, может требовать много времени.
Прямым следствием этого является низкая надежность. Наличие дефектного блока в списке приводит к потере информации в остаточной части файла и, потенциально, к потере дискового пространства отведенного под этот файл.
Наконец, для указателя на следующий блок внутри блока нужно выделить место. Емкость блока, традиционно являющаяся степенью двойки (многие программы читают и пишут блоками по степеням двойки), таким образом, перестает быть степенью двойки, т.к. указатель отбирает несколько байтов.
Поэтому метод связного списка обычно не используется в чистом виде.
Связный список с использованием индекса
Недостатки предыдущего способа могут быть устранены путем изъятия указателя из каждого дискового блока и помещения его в индексную таблицу в памяти, которая называется FAT (file allocation table). Этой схемы придерживаются многие ОС (MS-DOS, OS/2, MS Windows и др.)
Рис. 3.2.7. Метод связного списка, с использованием таблицы в оперативной памяти
По-прежнему, существенно, что запись в директории содержит только ссылку на первый блок и т.о. можно локализовать файл независимо от его размера.
Минусом этой схемы может быть необходимость поддержки в памяти этой довольно большой таблицы.
Индексные узлы
Четвертый и последний метод выяснения принадлежности блока к файлу - связать с каждым файлом маленькую таблицу, называемую индексным узлом (i-node), которая перечисляет атрибуты и дисковые адреса блоков файла (см. рис 3.2.8).
Каждый файл имеет свой собственный индексный блок, который содержит адреса блоков данных. Запись в директории, относящаяся к файлу, содержит адрес индексного блока. По мере заполнения файла указатели на блоки диска в индексном узле принимают осмысленные значения.
Индексирование поддерживает прямой доступ к файлу, без ущерба от внешней фрагментации.
Рис. 3.2.8. Структура индексного узла
Первые несколько адресов блоков файла хранятся непосредственно в индексном узле, т.о. для маленьких файлов индексный узел хранит всю необходимую информацию, которая копируется с диска в память, в момент открытия файла. Для больших файлов один из адресов индексного узла указывает на блок косвенной адресации. Этот блок содержит адреса дополнительных блоков диска. Если этого недостаточно используется блок двойной косвенной адресации, который содержит адреса блоков косвенной адресации. Если и этого недостаточно используют блок тройной косвенной адресации.
Эту схему использует Unix (а также файловые системы HPFS, NTFS и др.). Такой подход позволяет при фиксированном, относительно небольшом размере индексного узла, поддерживать работу с файлами, размер которых может меняться от нескольких байт до нескольких гигабайт. Существенно, что для маленьких файлов используется только прямая адресация, обеспечивающая максимальную производительность.
3.2.13.2 Управление свободным и занятым дисковым пространством.
В современных ОС используется несколько способов учета используемого места на диске. Рассмотрим наиболее распространенные.
Учет при помощи организации битового вектора.
Часто список свободных блоков диска реализован в виде битового вектора (bit map или bit vector). Каждый блок представлен одним битом, принимающим значение 0 или 1, в зависимости от того занят он или свободен. Например, 00111100111100011000001 ....
Главное преимущество этого подхода - он относительно прост и эффективен при нахождении первого свободного блока, или n последовательных блоков на диске. Многие компьютеры имеют инструкции манипулирования битами, которые могут быть использованы для этой цели. Например, компьютеры семейств Intel и Motorola имеют инструкции, которые при помощи которых можно легко локализовать первый единичный бита в слове.
Описываемый метод учета свободных блоков используется в Apple Macintosh.
К сожалению, этот метод эффективен, только если битовый вектор помещается в памяти целиком, что возможно только для относительно небольших дисков. Например, диск размером 1.3 Гб с блоками по 512 байт нуждается в таблице размером 332К для управления свободными блоками.
Учет при помощи организации связного списка.
Другой подход - связать в список все свободные блоки, поддерживая указатель на первый свободный блок в специальном месте диска, попутно кэшируя в памяти эту информацию.
Эта схема не всегда эффективна. Для трассирования списка нужно сделать много обращений к диску. Однако к счастью нам необходим, как правило, только первый свободный блок.
Иногда прибегают к модификации подхода связного списка, организуя хранение адресов n свободных блоков в первом свободном блоке. Первые n-1 этих блоков действительно используются. Последний блок содержит адреса других n блоков. И т.д.
3.2.13.3 Размер блока
Размер логического блока играет важную роль. В некоторых системах (Unix) он может быть задан при форматировании. Небольшой размер блока будет приводить к тому, что каждый файл будет содержать много блоков. Чтение блока осуществляется с задержками на поиск и вращение, т.о. файл из многих блоков будет читаться медленно. Большие блоки обеспечивают более высокую скорость обмена с диском, но вследствие внутренней фрагментации (каждый файл занимает целое число блоков и в среднем половина последнего блока пропадает) снижается процент полезного дискового пространства.
В системах со страничной организацией памяти имеется сходная проблема с размером страницы.
Проведенные исследования показали, что большинство файлов имеет небольшой размер (в Unix приблизительно 85% файлов имеют размер менее 8 Кбайт и 48% - менее 1Кбайта).
Рис. 3.2.9 Определение оптимального размера блока.
На рис. 3.2.9 изображены две кривые: одна убывающая показывает степень утилизации диска (в процентах) с возрастанием размера блока, а вторая возрастающая скорость считывания информации. Они пересекаются в районе 3К. Обычный компромисс выбор блока размером 512 б, 1К, 2К.
3.2.13.4 Структура файловой системы на диске
Рассмотрение методов работы с дисковым пространством дает общее представление о совокупности служебных данных, необходимых для описания файловой системы. Структуры данных типовой файловой системы, например Unix, на одном из разделов диска, таким образом, может состоять из 4-х основных частей:
Рис. 3.2.10 Примерная структура файловой системы на диске.
В начале раздела находится суперблок, содержащий общее описание файловой системы, например:
Описанные структуры данных создаются на диске в результате его форматирования (например, утилитами format, makefs и др.). Их наличие позволяет обращаться к данным на диске как к файловой системе, а не как к обычной последовательности блоков.
В файловых системах современных ОС для повышения устойчивости поддерживается несколько копий суперблока. В некоторых версиях Unix суперблок включал также и структуры данных, управляющие распределением дискового пространства, в результате чего суперблок непрерывно подвергался модификации, что снижало надежность файловой системы в целом. Выделение структур данных, описывающих дисковое пространство, в отдельную часть является более правильным решением.
Массив индексных узлов (ilist) содержит список индексов, соответствующих файлам данной файловой системы. Размер массива индексных узлов определяется администратором при установке системы. Максимальное число файлов, которые могут быть созданы в файловой системе, определяется числом доступных индексных узлов.
В блоках данных хранятся реальные данные файлов. Размер логического блока данных может задаваться при форматировании файловой системы. Заполнение диска содержательной информацией предполагает использование блоков хранения данных для файлов директорий и обычных файлов и имеет следствием модификацию массива индексных узлов и данных, описывающих пространство диска. Отдельно взятый блок данных может принадлежать одному и только одному файлу в файловой системе.
3.2.14 Реализация директорий
Как уже говорилось, директория или каталог это файл, имеющий определенный тип и хранящий список входящих в него файлов или каталогов. Основная задача файлов-директорий поддержка иерархической древовидной структуры файловой системы. Запись в директории имеет определенный для данной ОС формат, зачастую неизвестный пользователю, поэтому блоки данных файла-директории заполняются не через операции записи, а при помощи специальных системных вызовов (например, создание файла).
Для доступа к файлу ОС использует путь (pathname), сообщенный пользователем. Запись в директории связывает имя файла или имя поддиректории с блоками данных на диске. В зависимости от системы эта ссылка может быть дисковым адресом целого файла (непрерывное расположение), номером первого блока (связанный список), или номером индексного узла. Во всех случаях главная функция системы директорий - трансформировать символьное имя файла в информацию, необходимую, чтобы найти данные.
Отдельная проблема способ хранения атрибутов файла. Иногда их хранят непосредственно в записи в директории. Для системы с индексными узлами можно хранить атрибуты в индексном узле, а не в записи в директории. Как мы увидим позже, этот метод имеет ряд преимуществ при организации совместного доступа к файлам.
Рассмотрим несколько конкретных примеров.
3.2.14.1 Примеры реализации директорий в некоторых ОС
Директории в ОС CP/M
В ОС CP/M только одна директория.
Каждая запись - строка содержит следующие поля: идентификатор собственника, имя файла, тип файла, поле extent, которое показывает, хватит ли для идентификации файла одной строки или нужны еще, число блоков, номера блоков. То есть адреса всех блоков файла перечислены в записи в директории!
Директории в ОС MS-DOS
В ОС MS-DOS типовая запись в директории имеет вид:
Рис. 3.2.11 Вариант записи в директории MS-DOS
В ОС MS-DOS, как и в большинстве современных ОС, директории могут содержать поддиректории (специфицируемые битом атрибута), что позволяет конструировать произвольное дерево директорий файловой системы.
Номер первого блока используется в качестве индекса в таблице FAT . Далее по цепочке могут быть найдены остальные блоки.
Директории в ОС Unix
Структура директории проста. Каждая запись содержит имя файла и номер его индексного узла. Вся остальная информация о файле (тип, размер, времен модификации, владелец и т. д. и номера дисковых блоков) находится в индексном узле.
Рис. 3.2.12. Вариант записи в директории Unix
3.2.14.2 Поиск в директории
Итак, директория - есть файл, имеющий специальный формат, состоящий из записей фиксированной длины, где каждая запись соответствует одному из обычных файлов или директорий, входящих в состав данной директории. Как правило, список файлов в директории оказывается не упорядоченным по именам файлов. Поэтому правильный выбор алгоритма поиска имени файла в директории имеет большое влияние на эффективность и надежность файловых систем.
Линейный поиск
Совокупность записей о файлах в директории является линейным списком символьных имен файлов. Существует несколько стратегий просмотра такого списка. Простейшей из них является линейный поиск. Директория просматривается с самого начала, пока не встретится нужное имя файла. Хотя это наименее эффективный способ поиска, оказывается, что в большинстве случаев он работает с приемлемой производительностью. Например, авторы Unix утверждали, что вполне достаточно линейного поиска. По-видимому, это связано с тем, что на фоне относительно медленного доступа к диску, некоторые задержки, возникающие в процессе сканирования списка несущественны.
Метод прост, но требует временных затрат. Для создания нового файла вначале нужно просканировать директорию на наличие такого же имени. Затем, имя нового файла вставляется в конец директории (если, разумеется, файл с таким же именем в директории не существует, в противном случае нужно информировать пользователя). Для удаления файла нужно также выполнить поиск его имени в списке и пометить запись как неиспользуемую.
Реальный недостаток данного метода - линейный поиск файла. Информация о структуре директории используется часто, и плохая реализация будет замечена пользователями. Можно свести поиск к бинарному, если отсортировать список файлов. Однако это усложнит создание и удаление файлов, так как требуется перемещения большого объема информации.
Хеш таблица
Хеширование (см. например, [13]) - другой способ, который может быть использован для размещения и последующего поиска имени файла в директории. В данном методе имена файлов также хранятся в каталоге в виде линейного списка, но дополнительно используются хеш таблица. Хеш таблица, точнее построенная на ее основе хеш-функция позволяет по имени файла получить указатель на имя файла в списке. Таким образом, можно существенно уменьшить время поиска.
В результате хеширования могут возникать коллизии, то есть ситуации, когда функция хеширования, примененная к разным именам файлов, дает один и тот же результат. Обычно имена таких файлов объединяют в связные списки, предполагая в дальнейшем осуществление в них последовательного поиска нужного имени файла. Выбор хорошего алгоритма хеширования позволяет свести к минимуму число коллизий. Однако всегда есть вероятность неблагоприятного исхода, когда непропорционально большому числу имен файлов функция хеширования ставит в соответствие один и тот же результат. В этом случае преимущество использования этой схемы по сравнению с последовательным поиском практически утрачиваются.
Другие методы поиска
Помимо описанных методов поиска имени файла в директории существуют и другие. В качестве примера можно привести организацию поиска в каталогах файловой системы NTFS при помощи, так называемого B-дерева, которое стало стандартным способом организации индексов в системах баз данных.
3.2.15 Монтирование файловых систем.
Как файл должен быть открыт перед использованием, так и файловая система, хранящаяся на разделе диска, должна быть смонтирована, чтобы стать доступной процессам системы.
Функция mount (монтировать) связывает файловую систему из указанного раздела на диске с существующей иерархией файловых систем, а функция umount (демонтировать) выключает файловую систему из иерархии. Функция mount, таким образом, дает пользователям возможность обращаться к данным в дисковом разделе как к файловой системе, а не как к последовательности дисковых блоков.
Процедура монтирования состоит в следующем. Пользователь (в Unix это суперпользователь) сообщает ОС имя устройства и место в файловой структуре (имя пустого каталога), куда нужно присоединить файловую систему (точка монтирования). Например, в ОС Unix системный вызов mount имеет вид: mount(special pathname,directory pathname,options), где special pathname - имя специального файла устройства (в общем случае имя раздела), соответствующего дисковому разделу с монтируемой файловой системой, directory pathname - каталог в существующей иерархии, где будет монтироваться файловая система (другими словами, точка или место монтирования), а options указывает, следует ли монтировать файловую систему "только для чтения" (при этом не будут выполняться такие функции, как write и creat, которые производят запись в файловую систему). Затем ОС проверяет, что устройство содержит действительную файловую систему ожидаемого формата с суперблоком, списком индексов и корневым индексом.
Некоторые ОС осуществляют монтирование автоматически, как только встретят диск в первый раз (жесткие диски на этапе загрузки, гибкие - когда они вставлены в дисковод), ОС ищет файловую систему на устройстве. Если файловая система на устройстве имеется, она монтируется на корневом уровне, при этом к цепочке имен абсолютного имени файла (pathname) добавляется буква раздела.
Рис. 3.2.13. Две файловые системы до монтирования
Рис.3.2.14. Общая файловая система после монтирования
Ядро поддерживает таблицу монтирования с записями о каждой монтированной файловой системе. В каждой записи содержатся информация о вновь смонтированном устройстве, в частности на буфер с его суперблоком и корневой каталог, а также информация о точке монтирования. Для устранения потенциально опасных побочных эффектов число ссылок (см. следующий раздел) на каталог точку монтирования должно быть равно 1. Занесение информации в таблицу монтирования производится немедленно, поскольку монтирующий процесс может приостановиться, следуя процедуре открытия устройства или считывая суперблок файловой системы, а другой процесс тем временем попытался бы смонтировать файловую систему.
Наличие в логической структуре файлового архива точек монтирования требует аккуратной реализации алгоритмов, осуществляющих навигацию по каталогам. Точку монтирования можно пересечь двумя способами: из файловой системы, где производится монтирование, в файловую систему, которая монтируется (в направлении от глобального корня к листу), и в обратном направлении. Алгоритмы поиска файлов должны предусматривать ситуации, в которых очередной компонент пути к файлу является точкой монтирования, когда вместо анализа индексного узла очередной директории приходится осуществлять обработку суперблока монтированной системы.
3.2.16 Связывание файлов.
Иерархическая организация, положенная в основу древовидной структуры файловой системы современных ОС, не предусматривает выражения отношений, в которых потомки связываются более чем с одним предком. Такая негибкость частично устраняется возможностью реализации связывания файлов или организации линков.
3.2.16.1 Организация связи между каталогом и разделяемым файлом
Рис. 3.2.14. Структура файловой системы с возможностью связывания файла с новым именем.
Ядро позволяет пользователю связывать каталоги, упрощая написание программ, требующих пересечения дерева файловой системы. Часто имеет смысл хранить под разными именами одну и ту же команду (выполняемый файл). Например, выполняемый файл традиционного текстового редактора ОС UNIX vi обычно может вызываться под именами ex, edit, vi, view и vedit файловой системы. Соединение между директорией и разделяемым файлом называется связью или ссылкой (link). Дерево файловой системы превращается в циклический граф.
Это удобно, но создает ряд дополнительных проблем.
Простейший способ реализовать связывание файла - просто дублировать информацию о нем в обеих директориях. При этом, однако, может возникнуть проблема совместимости, в случае, если владельцы этих директорий попытаются независимо друг от друга изменить содержимое файла. Например, если запись в директории о файле непосредственно содержит адреса дисковых блоков, как в ОС CP/M, копии тех же дисковых адресов должны быть сделаны и в другой директории, куда файл линкуется. Если один из пользователей делает добавление к файлу, новые блоки будут перечислены только у него в директории и не будут видны другому пользователю.
Проблема такого рода может быть решена двумя способами. Первый из них, так называемая жесткая связь. Если блоки данных файла перечислены не в директории, а в небольшой структуре данных (например, в индексном узле), связанной собственно с файлом, то второй пользователь может связаться непосредственно с этой, уже существующей структурой.
Альтернативное решение - создание нового файла, который содержит путь к связываемому файлу. Такой подход называется символической линковкой. При этом в соответствующем каталоге создается элемент, в котором имени связи сопоставляется некоторое имя файла (этот файл даже не обязан существовать к моменту создания символической связи). Для символической связи может создаваться отдельный индексный узел и даже заводиться отдельный блок данных для хранения потенциально длинного имени файла.
Каждый из этих методов имеет свои минусы. В случае жесткой связи возникает необходимость поддержки счетчика ссылок на файл, для корректной реализации операции удаления файла. Например, в Unix, такой счетчик является одним из атрибутов, хранимым в индексном узле. Удаление файла одним из пользователей уменьшает количество ссылок на файл на 1. Реальное удаление файла происходит, когда число ссылок на файл становится равным 0.
В случае символической линковки такая проблема не возникает, т.к. только реальный владелец имеет ссылку на индексный узел файла. Если собственник удаляет файл, то он разрушается, и попытки других пользователей работать с ним кончатся провалом. Удаление символического линка никак не влияет на файл. Проблема организации символической связи потенциальное снижение скорости доступа к файлу. Файл символического линка содержит путь к файлу, содержащий список вложенных директорий, для прохождения по которому необходимо осуществить несколько обращений к диску.
Символический линк имеет то преимущество, что он может использоваться для униформного доступа к файлам удаленных компьютеров, если, например, добавить к пути сетевой адрес удаленной машины.
Циклический граф структура более гибкая, нежели простое дерево, но работа с ней требует большой аккуратности. Одна из серьезных проблем со структурой циклического графа - гарантия того, что не возникает циклов при поиске файла. Поскольку теперь к файлу существует несколько путей, программа поиска файла может найти его на диске несколько раз. Простейшее практическое решение данной проблемы - ограничить число директорий при поиске. Полное устранение циклов довольно трудоемкая процедура, выполняемая специальными утилитами и связанная с многократной трассировкой директорий файловой системы.
3.2.17 Кооперация процессов при работе с файлами.
Когда различные пользователи работают вместе над проектом, они часто нуждаются в разделении файлов.
Разделяемый файл является разделяемым ресурсом. Как и в случае любого совместно используемого ресурса, процессы должны синхронизировать свой доступ к совместно используемым файлам, каталогам, чтобы избежать тупиковых ситуаций, дискриминации отдельных процессов и снижения производительности системы.
Например, если несколько пользователей одновременно редактируют какой-либо файл и не принято специальных мер, то результат будет непредсказуем и зависит от того, в каком порядке осуществлялись записи в файл. Между двумя операциями read одного процесса, другой процесс может модифицировать данные, что неприемлемо для многих приложений. Простейшее решение данной проблемы предоставить возможность одному из процессов захватить файл, то есть блокировать доступ к разделяемому файлу других процессов на все время, пока файл остается открытым для данного процесса. Однако это было бы не гибко и не соответствовало бы характеру поставленной задачи.
Основные способы средство временный захват процессом файла или записи (части файла между указанными позициями), а также блокировки отдельных структур ядра, отвечающих за работу с файлами. Так, в ОС Unix во время системного вызова, осуществляющего ту или иную операцию с файлом, как правило, происходит блокирование индексного узла, содержащего адреса блоков данных файла. Может показаться, что организация блокировок или запрета более чем одному процессу работать с файлом во время выполнения системного вызова является излишней, так как в подавляющем большинстве случаев выполнение системных вызовов и так не прерывается, то есть ядро работает в условиях невытесняющей многозадачности. Однако в данном случае это не совсем так. Операции чтения и записи занимают продолжительное время и лишь инициируются центральным процессором, а осуществляются по независимым каналам, поэтому установка блокировок на время системного вызова является необходимой гарантией атомарности операций чтения и записи.
Системный вызов, позволяющий установить и проверить блокировки на файл, является неотъемлемым атрибутом современных многопользовательских ОС. В принципе, было бы логично связать синхронизацию доступа к файлу как к единому целому с системным вызовом open (т.е., например, открытие файла в режиме записи или обновления могло бы означать его монопольную блокировку соответствующим процессом, а открытие в режиме чтения - совместную блокировку). Так поступают во многих операционных системах (начиная с ОС Multics). В ОС Unix это не так, что имеет исторические причины.
В первой версии системы Unix, разработанной Томпсоном и Ричи, механизм захвата файла отсутствовал. Применялся очень простой подход к обеспечению параллельного (от нескольких процессов) доступа к файлам: система позволяла любому числу процессов одновременно открывать один и тот же файл в любом режиме (чтения, записи или обновления) и не предпринимала никаких синхронизационных действий. Вся ответственность за корректность совместной обработки файла ложилась на использующие его процессы, и система даже не предоставляла каких-либо особых средств для синхронизации доступа процессов к файлу. Однако впоследствии, для того, чтобы повысить привлекательность системы для коммерческих пользователей, работающих с базами данных, в версию V системы были включены механизмы захвата файла и записи, базирующиеся на системном вызове fcntl.
Допускаются два варианта синхронизации: с ожиданием, когда требование блокировки может привести к откладыванию процесса до того момента, когда это требование может быть удовлетворено, и без ожидания, когда процесс немедленно оповещается об удовлетворении требования блокировки или о невозможности ее удовлетворения в данный момент времени.
Установленные блокировки относятся только к тому процессу, который их установил, и не наследуются процессами-потомками этого процесса. Более того, даже если некоторый процесс пользуется синхронизационными возможностями системного вызова fcntl, другие процессы по-прежнему могут работать с тем файлом без всякой синхронизации. Другими словами, это дело группы процессов, совместно использующих файл, - договориться о способе синхронизации параллельного доступа.
3.2.18 Надежность файловой системы.
Жизнь полна неприятных неожиданностей, а разрушение файловой системы зачастую более опасно, чем разрушение компьютера. Поэтому необходимо предпринимать специальные меры для сохранения структуры файловой системы на диске. Помимо очевидных решений, например, своевременное дублирование информации (backup), файловые системы современных ОС содержат специальные средства для поддержки собственной совместимости.
3.2.18.1 Целостность файловой системы.
Важный аспект надежной работы файловой системы контроль ее целостности. В результате файловых операций блоки диска могут считываться в память, модифицироваться и затем записываться на диск. Причем, многие файловые операции затрагивают сразу несколько объектов файловой системы. И, если, вследствие непредсказуемого останова системы, на диске будут сохранены изменения только для части этих объектов (нарушена атомарность файловой операции), файловая система на диске может быть оставлена в несовместимом состоянии. В результате могут возникнуть нарушения логики работы с данными, например, появиться потерянные блоки диска, которые не принадлежат ни одному файлу и, в то же время помечены как занятые или наоборот блоки, помеченные, как свободные, но в то же время занятые (на них есть ссылка в индексном узле) или другие нарушения.
В современных ОС предусмотрены меры, которые позволяют свести к минимуму ущерб от порчи файловой системы и, затем, восстановить ее целостность.
Очевидно, что для правильного функционирования файловой системы, значимость отдельных данных неравноценна. Искажение содержимого пользовательских файлов не приводит к серьезным (с точки зрения целостности файловой системы) последствиям, тогда как несоответствия в файлах, содержащих управляющую информацию (директории, индексные узлы, суперблок и т.п.), могут быть катастрофическими. Поэтому должен быть тщательно продуман порядок совершения операций со структурами данных файловой системы.
Рассмотрим, пример создания жесткой связи для файла. Для этого файловой системе необходимо выполнить следующие операции:
1. Создать новую запись в каталоге, указывающую на индексный узел файла
2. Увеличить счетчик связей в индексном узле
Если аварийный останов произошел между 1-й и 2-й операциями, то в каталогах файловой системе будут существовать два имени файла, адресующих индексный узел со значением счетчика связей, равному 1. если теперь будет удалено одно из имен, это приведет к удалению файла как такового. Если же порядок операций изменен и, как прежде, останов произошел между первой и второй операциями, файл будет иметь несуществующую жесткую связь, но существующая запись в каталоге будет правильной. Хотя это тоже является ошибкой, но ее последствия менее серьезны, чем в предыдущем случае.
Другим средством поддержки целостности является способ реализации файловой операции в виде транзакции, примерно как, как это делается в СУБД. Последовательность действий с объектами во время файловой операции протоколируется, и, если произошел останов системы, то, имея в наличии протокол, можно осуществить откат системы назад в исходное целостное состояние, в котором она пребывала до начала операции. Такого рода журналирование реализовано в NTFS.
Если же нарушение все же произошло, то для устранения проблемы несовместимости можно прибегнуть к утилитам (fsck, chkdsk, scandisk и др.), которые проверяют целостность файловой системы. Они могут запускаться после загрузки или после сбоя и осуществляют многократное сканирование разнообразных структур данных файловой системы в поисках противоречий.
Возможны также эвристические проверки. Например, нахождение индексного узла, номер, которого превышает их число на диске или нахождение в пользовательских директориях файлов принадлежащих суперпользователю.
3.2.18.2 Управление плохими блоками
Наличие плохих блоков на диске обычное дело. Под плохими блоками обычно понимают блоки диска, для которых вычисленная контрольная сумма считываемых данных не совпадает с хранимой контрольной суммой. Часто появляются в процессе эксплуатации. Иногда они уже имеются при поставке вместе со списком, т.к. очень затруднительно для поставщиков сделать диск полностью свободным от дефектов. Два решения проблемы плохих блоков - одно на уровне аппаратуры другое на уровне ядра ОС.
Первый способ - хранить список плохих блоков в контроллере диска. Когда контроллер инициализируется, он читает плохие блоки и замещает дефектный блок резервным, помечая отображение в списке плохих блоков. Все реальные запросы будут идти к резервному блоку. Следует иметь в виду, что при этом механизм подъемника (наиболее распространенный механизм обработки запросов к блокам диска) будет работать неэффективно. Дело в том, что существует стратегия очередности обработки запросов к диску (подробнее см. главу ввод-вывод). Стратегия диктует направление движения считывающей головки диска к нужному цилиндру. Обычно резервные блоки размещаются на внешних цилиндрах. Если плохой блок расположен на внутреннем цилиндре, и контроллер осуществляет подстановку прозрачным образом, то кажущееся движение головки будет осуществляться к внутреннему цилиндру, а фактическое к внешнему. Это является нарушением стратегии и, следовательно, минусом данной схемы.
Решение на уровне ОС может быть следующим. Во-первых, необходимо тщательно сконструировать файл, содержащий плохие блоки. Тогда они изымаются из списка свободных блоков. Затем нужно сделать так, чтобы к этому файлу не было обращений. Если это возможно, то проблема решена.
3.2.19 Производительность файловой системы
Наиболее типичная техника повышения скорости работы с диском кэширование. Обращение к диску обычно в 100000 раз медленнее, чем к памяти. (Обращение к памяти - несколько сотен наносекунд, а чтение блока с диска - десятки миллисекунд). За счет кэширования дисковой информации в памяти можно сократить число дисковых операций, храня часть блоков диска, к которым перед этим производились обращения, в специальной области памяти, именуемой буферным кэшем (cache). Это оказывается возможным вследствие присущего ОС свойству локальности (о свойстве локальности много говорилось в главах, посвященных описанию работы системы управления памятью).
Различные алгоритмы используются для управления кэшем, но наиболее общий - при запросах на чтение проверять находится ли соответствующий блок в буфер кэша, и если нет, то вначале считать его в буфер.
Аккуратная реализация кэширования требует решения нескольких проблем.
Во-первых, емкость буфера кэша ограничена. Когда блок должен быть загружен в заполненный буфер кэша, возникает проблема замещения блоков, то есть отдельные блоки должны быть удалены из него. Эта ситуация очень напоминает ситуацию с выталкиванием страниц памяти, и здесь используются те же алгоритмы, например, FIFO, Second Chance и LRU. Разница лишь в том, что ссылки кэша не столь часты, как ссылки на страницы памяти.
Замещение блоков должно осуществляться с учетом их важности для файловой системы. Блоки должны быть разделены на категории, например: блоки индексных узлов, блоки косвенной адресации, блоки директорий, заполненные блоки данных и т.д., и в зависимости от принадлежности блока к той или иной категории применять к ним разную стратегию замещения.
Во-вторых, поскольку кэширование использует механизм отложенной записи, при котором модификация буфера не вызывает немедленной записи на диск, серьезной проблемой является старение информации в дисковых блоках, образы которых находятся в буферном кэше. Несвоевременная синхронизация буфера кэша и диска может привести к очень нежелательным ситуациям в случае отказов оборудования или программного обеспечения. Поэтому стратегия и порядок отображения информации из кэша на диск должна быть тщательно продумана.
Так, блоки существенные для совместимости файловой системы (блоки индексных узлов, блоки косвенной адресации, блоки директорий), должны быть переписаны на диск немедленно, независимо от того в какой части LRU цепочки они находятся. Необходимо тщательно выбрать порядок такого переписывания.
В UNIX имеется для этого вызов SYNC, который заставляет все модифицированные блоки записываться на диск немедленно. Для периодической синхронизации содержимого кэша и диска запускается фоновый процесс-демон, который делает это через определенный промежуток времени (например, каждые 30 сек.). Кроме того, можно организовать синхронный режим работы с отдельными файлами, задаваемый при открытии файла, когда все изменения в файле немедленно сохраняются на диске.
В ОС MS-DOS, в отличие от Unix, принято записывать каждый модифицированный блок на диск как можно скорее. Следствие такой стратегии - удаление дискеты из UNIX системы без осуществления вызова SYNC почти всегда ведет к потере данных, тогда как у MS-DOS здесь проблем не возникает (в UNIX предполагается, что все диски жесткие и не вынимаются)
Кэширование - не единственный способ увеличения производительности системы. Другая важная техника - сокращение количества движений считывающей головки диска, за счет разумной стратегии размещения информации. Например, массив индексных узлов в Unix стараются разместить на средних дорожках. Также имеет смысл размещать индексные узлы поблизости от блоков данных, на которые они ссылаются и т.д.
3.2.20 Реализация некоторых операций над файлами.
В предыдущей главе перечислены основные операции над файлами. В данном разделе будет описан порядок работы некоторых системных вызовов для работы с файловой системой, следуя главным образом [1], с учетом совокупности введенных в данной главе понятий.
3.2.20.1 Системные вызовы, работающие с символическим именем файла.
Системные вызовы, связывающие pathname с дескриптором файла
Это функции создания и открытия файла. Например, в ОС Unix
fd = creat(pathname,modes);
fd = open(pathname,flags,modes);
Другие операции над файлами, такие как чтение, запись, позиционирование головок чтения-записи, воспроизведение дескриптора файла, установка параметров ввода-вывода, определение статуса файла и закрытие файла, используют значение полученного дескриптора файла.
Рассмотрим работу системного вызова open.
Логическая файловая подсистема просматривает файловую систему в поисках файла по его имени. Она проверяет права на открытие файла и выделяет открываемому файлу запись в таблице файлов. Запись таблицы файлов содержит указатель на индексный узел открытого файла. Ядро выделяет запись в личной (закрытой) таблице в адресном пространстве процесса, выделенном процессу (таблица эта называется таблицей пользовательских дескрипторов файлов), и запоминает указатель на эту запись. Указателем выступает дескриптор файла, возвращаемый пользователю. Запись в таблице пользовательских файлов указывает на запись в глобальной таблице файлов.
Рис. 3.2.15. Структуры данных после открытия файлов
Первые три пользовательских дескриптора (0, 1 и 2) именуются дескрипторами файлов: стандартного ввода, стандартного вывода и стандартного файла ошибок. Процессы в системе UNIX по договоренности используют дескриптор файла стандартного ввода при чтении вводимой информации, дескриптор файла стандартного вывода при записи выводимой информации и дескриптор стандартного файла ошибок для записи сообщений об ошибках.
Связывание файла
Системная функция link связывает файл с новым именем в структуре каталогов файловой системы, создавая для существующего индекса новую запись в каталоге. Синтаксис вызова функции link: link(source file name, target file name);
где source file name - существующее имя файла, а target file name - новое (дополнительное) имя, присваиваемое файлу после выполнения функции link.
Сначала ОС, определяет местонахождение индекса исходного файла и увеличивает значение счетчика связей в индексном узле. Затем ядро ищет файл с новым именем; если он существует, функция link завершается неудачно и ядро восстанавливает прежнее значение счетчика связей, измененное ранее. В противном случае ядро находит в родительском каталоге свободную запись для файла с новым именем, записывает в нее новое имя и номер индекса исходного файла.
Удаление файла
В Unix системная функция unlink удаляет из каталога точку входа для файла. Синтаксис вызова функции unlink: unlink(pathname);
Если удаляемое имя является последней связью файла с каким-либо каталогом, ядро в итоге освобождает все информационные блоки файла. Однако если у файла было несколько связей, он остается все еще доступным под другими именами.
Для того чтобы забрать дисковые блоки, ядро в цикле просматривает таблицу содержимого индексного узла, освобождая все блоки прямой адресации немедленно. Что касается блоков косвенной адресации, ядро освобождает все блоки, появляющиеся на различных уровнях косвенности, рекурсивно, причем в первую очередь освобождаются блоки с меньшим уровнем.
3.2.20.2 Системные вызовы, работающие с файловым дескриптором
Открытый файл может использоваться для чтения и записи последовательностей байтов. Для этого поддерживаются два системных вызова read и write, работающие с файловым дескриптором (или handle'ом в терминологии Microsoft), полученном при ранее выполненных системных вызовах open или creat.
Функции ввода-вывода из файла
Системный вызов read выполняет чтение обычного файла: number = read(fd,buffer,count);
где fd - дескриптор файла, возвращаемый функцией open, buffer - адрес структуры данных в пользовательском процессе, где будут размещаться считанные данные в случае успешного завершения выполнения функции read, count - количество байт, которые пользователю нужно прочитать, number - количество фактически прочитанных байт.
Синтаксис вызова системной функции write (писать): number = write(fd,buffer,count);
где переменные fd, buffer, count и number имеют тот же смысл, что и для вызова системной функции read. Алгоритм записи в обычный файл похож на алгоритм чтения из обычного файла. Однако если в файле отсутствует блок, соответствующий смещению в байтах до места, куда должна производиться запись, ядро выделяет блок, и присваивает ему номер в соответствии с точным указанием места в таблице содержимого индексного узла.
Обычное использование системных функций read и write обеспечивает последовательный доступ к файлу, однако процессы могут использовать вызов системной функции lseek для указания места в файле, где будет производиться ввод-вывод, и осуществления произвольного доступа к файлу. Синтаксис вызова системной функции: position = lseek(fd,offset,reference);
где fd - дескриптор файла, идентифицирующий файл, offset - смещение в байтах, а reference указывает, является ли значение offset смещением от начала файла, смещением от текущей позиции ввода-вывода или смещением от конца файла. Возвращаемое значение, position, является смещением в байтах до места, где будет начинаться следующая операция чтения или записи.
3.2.21 Современные архитектуры файловых систем
Современные ОС предоставляют пользователю возможность работать сразу с несколькими файловыми системами (Linux работает с Ext2fs, FAT и др.). Файловая система в традиционном понимании становится частью более общей многоуровневой структуры (см. рис. 12.12).
На верхнем уровне, на котором располагается так называемый диспетчер файловых систем (например, в Windows 95 этот компонент называется installable filesystem manager). Он связывает запросы прикладной программы с конкретной файловой системой.
Рис. 3.2.16. Архитектура современной файловой системы
Каждая файловая система (иногда говорят драйвер файловой системы) на этапе инициализации регистрируется у диспетчера, сообщая ему точки входа, для последующих обращений к данной файловой системе.
Та же идея поддержки нескольких файловых систем в рамках одной ОС может быть реализована по-другому, например, исходя из концепции виртуальной файловой системы. Виртуальная файловая система (vfs) представляет собой независимый от реализации уровень и опирается на реальные файловые системы (s5fs, ufs, FAT, NFS, FFS, Ext2fs). При этом возникают структуры данных виртуальной файловой системы, типа виртуальных индексных узлов vnode, которые обобщают индексные узлы конкретных систем .
3.2.22 Резюме
Реализация файловой системы связана с такими вопросами, как поддержка понятия логического блока диска, связывания имени файла и блоков его данных, проблемами разделения файлов и проблемами управления дискового пространства.
Наиболее распространенные способы выделения дискового пространства: непрерывное выделение, организация связного списка и система с индексными узлами.
Файловая система часто реализуется в виде слоеной модульной структуры. Нижние слои имеют дело с оборудованием, а верхние с символическими именами и логическими свойствами файлов.
Директории могут быть организованы различными способами и могут хранить атрибуты файла и адреса блоков файлов, а иногда для этого предназначается специальная структура (индексные узлы). Проблемы надежности и производительности файловой системы важнейшие аспекты ее дизайна.
Часть 3. Примеры файловых систем
3.2.23. Файловая система FAT
Аббревиатура FAT (file allocation table) означает «таблица размещения файлов». Этот термин относится к линейной табличной структуре со сведениями о файлах – именами файлов, их атрибутами и другими данными, определяющими местоположение файлов или их фрагментов в среде FAT. Элемент FAT определяет фактическую область диска, в котором хранится начало физического файла.
В файловой системе FAT логическое дисковое пространство любого логического диска делится на две области: системную область и область данных.
Системная область создается при форматировании и обновляется при манипулировании файловой структурой. Область данных содержит файлы и каталоги, подчиненные корневому, и доступна через пользовательский интерфейс. Системная область состоит из следующих компонентов: загрузочной записи; зарезервированных секторов; таблицы размещения файлов (FAT); корневого каталога.
Таблица размещения файлов представляет собой карту (образ) области данных, в которой описывается состояние каждого участка области данных. Область данных разбивается на кластеры. Кластер – один или несколько смежных секторов в логическом дисковом адресном пространстве (только в области данных). В таблице FAT кластеры, принадлежащие одному файлу (некорневому каталогу), связываются в цепочки. Для указания номера кластера в системе управления файлами FAT16 используется 16-битовое слово, следовательно, можно иметь до 216 = 65536 кластеров.
Кластер – минимальная адресуемая единица дисковой памяти, выделяемая файлу или некорневому каталогу. Файл или каталог занимает целое число кластеров. Последний кластер при этом может быть задействован не полностью, что приведет к заметной потере дискового пространства при большом размере кластера. Когда программа отправляет запрос к ОС с требованием предоставить ей содержимое какого-либо файла ОС, просматривает запись корневого каталога для этого файла, чтобы найти первый кластер этого файла, затем обращается к элементу FAT для данного кластера для определения следующего кластера в цепочке, повторяя этот процесс до тех пор пока не будет найден последний кластер файла. ОС точно определяет какие кластеры принадлежат данному файлу и в какой последовательности. Способ носит название цепочки FAT.
Так как FAT используется при доступе к диску очень интенсивно, она загружается в ОЗУ и находится там максимально долго.
Корневой каталог отличается от обычного каталога тем, что он размещается в фиксированном месте логического диска и имеет фиксированное число элементов. Поиск записей в корневом каталоге происходит линейно, т.е., чтобы найти нужную запись, ОС должна перебрать все записи последовательно друг за другом. Для каждого файла и каталога в файловой системе хранится информация в соответствии со следующей структурой:
Структура системы файлов является иерархической.
FAT32 является полностью независимой 32-разрядной файловой системой и содержит многочисленные усовершенствования и дополнения по сравнению с FAT16. Принципиальное отличие FAT32 заключается в более эффективном использовании дискового пространства: FAT32 использует кластеры меньшего размера, что приводит к экономии дискового пространства.
FAT32 может перемещать корневой каталог и использовать резервную копию FAT вместо стандартной. Расширенная загрузочная запись FAT32 позволяет создавать копии критических структур данных, что повышает устойчивость дисков к нарушениям структуры FAT по сравнению с предыдущими версиями. Корневой каталог представляет собой обычную цепочку кластеров, поэтому может находиться в произвольном месте диска, что снимает ограничение на размер корневого каталога.
Сравнение FAT16 и FAT32
|
Количество кластеров для адресации |
216 = 65 536 |
232 = 4 294 967 |
|
Максимальный размер кластера |
32 Кб |
4Кб (512 б) |
|
Максимально возможная емкость диска |
V<4G, реально до 2G |
2T |
|
Корневой каталог |
Строго определенный размер и место на диске |
Наращивание по необходимости – использование длинных имен файлов, занимающих несколько записей корневого каталога |
|
Работа с таблицами FAT |
Работа с одной из копий |
Работает с обоими таблицами для повышения отказоустойчивости |
Появилась в ОС Windows 3.11 и была предназначена для выполнения файлового ввода-вывода в защищенном режиме. С выходом Windows 95 добавляется поддержка длинных имен файлов. Позволяет работать с виртуальным дисковым пространством, являлась промежуточным звеном между FAT16 и FAT32.
Файловая система NTFS (New Technology File System) содержит ряд значительных усовершенствований и изменений, существенно отличающих ее от других файловых систем. С точки зрения пользователей файлы по-прежнему хранятся в каталогах, но работа на дисках большого объема в NTFS происходит намного эффективнее:
Основные характеристики файловой системы NTFS:
NTFS хорошо работает с большими массивами данных и большими томами. Максимальный размер тома (и файла) – 16 Эбайт. (1 Эбайт равен 2**64 или 16000 млрд. гигабайт.) Количество файлов в корневом и некорневом каталогах не ограничено. Поскольку в основу структуры каталогов NTFS заложена эффективная структура данных, называемая «бинарным деревом», время поиска файлов в NTFS не связано линейной зависимостью с их количеством.
Система NTFS обладает некоторыми средствами для самовосстановления и поддерживает различные механизмы проверки целостности системы, включая ведение журнала транзакций, позволяющий отследить по системному журналу файловые операции записи.
Файловая система NTFS поддерживает объектную модель безопасности и рассматривает все тома, каталоги и файлы как самостоятельные объекты NTFS. Права доступа к томам, каталогам и файлам зависит от учетной записи пользователя и той группы, к которой он принадлежит.
Файловая система NTFS обладает встроенными средствами сжатия, которые можно применять к томам, каталогам и файлам.