Организация файлов и доступ к ним

Файловые системы

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

Введение

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

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

Основная идея использования внешней памяти состоит в следую­щем. ОС делит память на блоки фиксированного размера, например, 4096 байт. Файл, обычно представляющий собой неструктурированную после­довательность однобайтовых записей, хранится в виде последовательно­сти блоков (не обязательно смежных); каждый блок хранит целое число записей. В некоторых ОС (MS-DOS) адреса блоков, содержащих данные файла, могут быть организованы в связный список и вынесены в отдель­ную таблицу в памяти. В других ОС (Unix) адреса блоков данных файла хранятся в отдельном блоке внешней памяти (так называемом индексе или индексном узле). Этот прием, называемый индексацией, является наиболее распространенным для приложений, требующих произвольно­го доступа к записям файлов. Индекс файла состоит из списка элементов, каждый из которых содержит номер блока в файле и сведения о местопо­ложении данного блока. Считывание очередного байта осуществляется с так называемой текущей позиции, которая характеризуется смещением от начала файла. Зная размер блока, легко вычислить номер блока, содер­жащего текущую позицию. Адрес же нужного блока диска можно затем извлечь из индекса файла. Базовой операцией, выполняемой по отноше­нию к файлу, является чтение блока с диска и перенос его в буфер, нахо­дящийся в основной памяти.

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

Перечислим основные функции файловой системы:

1) Идентификация файлов. Связывание имени файла с выделенным ему пространством внешней памяти.

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

3) Обеспечение надежности и отказоустойчивости. Стоимость инфор­мации может во много раз превышать стоимость компьютера.

4) Обеспечение защиты от несанкционированного доступа.

5) Обеспечение совместного доступа к файлам, так чтобы пользовате­лю не приходилось прилагать специальных усилий по обеспечению синхронизации доступа.

6) Обеспечение высокой производительности.

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

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

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

Общие сведения о файлах

Имена файлов

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

Правила именования файлов зависят от ОС. Многие ОС поддержи­вают имена из двух частей (имя + расширение), например progr.c (файл, содержащий текст программы на языке Си) или autoexec.bat (файл, содержащий команды интерпретатора командного языка). Тип расширения файла позволяет ОС организовать работу с ним различных прикладных программ в соответствии с заранее оговоренными соглаше­ниями. Обычно ОС накладывают некоторые ограничения, как на исполь­зуемые в имени символы, так и на длину имени файла. В соответствии со стандартом POSIX, популярные ОС оперируют удобными для пользовате­ля длинными именами (до 255 символов).

Типы файлов

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

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

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

Файлы с точки зрения пользователя

файловый интерфейс. Эти объекты рассматриваются в других разделах данного курса.

Далее речь пойдет главным образом об обычных файлах.

Обычные (или регулярные) файлы реально представляют собой на­бор блоков (возможно, пустой) на устройстве внешней памяти, на кото­ром поддерживается файловая система. Такие файлы могут содержать как текстовую информацию (обычно в формате ASCII), так и произвольную двоичную (бинарную) информацию.

Текстовые файлы содержат символьные строки, которые можно рас­печатать, увидеть на экране или редактировать обычным текстовым реда­ктором.

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

Обычно прикладные программы, работающие с файлами, распозна­ют тип файла по его имени в соответствии с общепринятыми соглашени­ями. Например, файлы с расширениями .с, .pas, .txt — ASCII-файлы, файлы с расширениями .ехе — выполнимые, файлы с расширениями . obj, .zip- бинарные и т. д.

Атрибуты файлов

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

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

Организация файлов и доступ к ним

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

ОС поддерживают несколько вариантов структуризации файлов.

Последовательный файл

Простейший вариант — так называемый последовательный файл. То есть файл является последовательностью записей. Поскольку записи, как правило, однобайтовые, файл представляет собой неструктурирован­ную последовательность байтов.

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

Файл прямого доступа

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

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

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

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

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

Подобную логическую структуру имеют файлы во многих файловых системах, например в файловых системах ОС Unix и MS-DOS. ОС не осуществляет никакой интерпретации содержимого файла. Эта схема обеспечивает максимальную гибкость и универсальность. С помощью базовых системных вызовов (или функций библиотеки ввода/вывода) пользователи могут как угодно структурировать файлы. В частности, многие СУБД хранят свои базы данных в обычных файлах.

Другие формы организации файлов

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

Первый шаг в структурировании — хранение файла в виде последова­тельности записей фиксированной длины, каждая из которых имеет внутрен­нюю структуру. Операция чтения производится над записью, а операция записи переписывает или добавляет запись целиком. Ранее использовались записи по 80 байт (это соответствовало числу позиций в перфокарте) или по 132 символа (ширина принтера). В ОС СР/М файлы были последова­тельностями 128-символьных записей. С введением CRT-терминалов дан­ная идея утратила популярность.

Другой способ представления файлов — последовательность записей переменной длины, каждая из которых содержит ключевое поле в фиксиро­ванной позиции внутри записи (см. рис. 11.1). Базисная операция в дан­ном случае — считать запись с каким-либо значением ключа. Записи могут располагаться в файле последовательно (например, отсортированные по значению ключевого поля) или в более сложном порядке. Метод доступа по значению ключевого поля к записям последовательного файла называ­ется индексно-последовательным.

В некоторых системах ускорение доступа к файлу обеспечивается конструированием индекса файла. Индекс обычно хранится на том же

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

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

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

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

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

Операции над файлами

Операционная система должна предоставить в распоряжение пользо­вателя набор операций для работы с файлами, реализованных через сис­темные вызовы. Чаще всего при работе с файлом пользователь выполняет не одну, а несколько операций. Во-первых, нужно найти данные файла и его атрибуты по символьному имени, во-вторых, считать необходимые атрибуты файла в отведенную область оперативной памяти и проанализи­ровать права пользователя на выполнение требуемой операции. Затем сле­дует выполнить операцию, после чего освободить занимаемую данными файла область памяти. Рассмотрим в качестве примера основные файло­вые операции ОС Unix.

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

• Удаление файла и освобождение занимаемого им дискового про­странства.

• Открытие файла. Перед использованием файла процесс должен его открыть. Цель данного системного вызова — разрешить системе про­анализировать атрибуты файла и проверить права доступа к нему, а также считать в оперативную память список адресов блоков файла для быстрого доступа к его данным. Открытие файла является проце­дурой создания дескриптора или управляющего блока файла. Деск­риптор (описатель) файла хранит всю информацию о нем. Иногда, в соответствии с парадигмой, принятой в языках программирования, под дескриптором понимается альтернативное имя файла или указа­тель на описание файла в таблице открытых файлов, используемый при последующей работе с файлом. Например, на языке Си операция открытия файла fd=open(pathname, flags,modes) ; возвращает дескриптор f d, который может быть задействован при выполнении операций чтения ( read (fd, buffer, count) ;) или записи.

• Закрытие файла. Если работа с файлом завершена, его атрибуты и адреса блоков на диске больше не нужны. В этом случае файл нужно закрыть, чтобы освободить место во внутренних таблицах файловой системы.

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

• Чтение данных из файла. Обычно это делается с текущей позиции. Пользователь должен задать объем считываемых данных и предоста­вить для них буфер в оперативной памяти.

• Запись данных в файл с текущей позиции. Если текущая позиция

находится в конце файла, его размер увеличивается, в противном

случае запись осуществляется на место имеющихся данных, которые, таким образом, теряются.

Есть и другие операции, например переименование файла, получение атрибутов файла и т. д.

Существует два способа выполнить последовательность действий над файлами.

В первом случае для каждой операции выполняются как универсаль­ные, так и уникальные действия (схема stateless). Например, последова­тельность операций может быть такой: open, readl, close, ... open, read2, close, ... open, read3, close.

Альтернативный способ — это когда универсальные действия выпол­няются в начале и в конце последовательности операций, а для каждой промежуточной операции выполняются только уникальные действия. В этом случае последовательность вышеприведенных операций будет вы­глядеть так: open, readl, ... read2, ... read3, close.

Большинство ОС использует второй способ, более экономичный и быстрый. Первый способ более устойчив к сбоям, поскольку результаты каждой операции становятся независимыми от результатов предыдущей операции; поэтому он иногда применяется в распределенных файловых системах (например, Sun NFS).

Не нашли, что искали? Воспользуйтесь поиском по сайту: