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

Обновлено: 25.01.2025

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

Рекомендуемые файлы

Тест по теме "Функции и многофайловые программы в Си"

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

2. Файлы прямого и последовательного доступа

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

Каждая файловая система – система управления файлами поддерживает некоторую иерархическую файловую структуру, включающую чаще всего неограниченное количество уровней иерархии в представлении внешней памяти.

Для каждого файла в системе хранится следующая информация:

· тип файла, размер записи, количество занятых физических блоков;

· базовый начальный адрес;

· ссылка на сегмент расширения;

· способ доступа (код защиты).

Для файлов с постоянной длиной записи адрес размещения записи с номером К может быть вычислен по формуле:

К=ВА+(К-1)*LZ+1,

где ВА – базовый адрес, LZ-длина записи.

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

Файлы с переменной длиной записи всегда являются файлами последовательного доступа. Они могут быть организованы двумя способами:

Конец записи отмечается специальным маркером.

В начале каждой записи записывается ее длина.

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

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

NZ = F ( K ),

где NZ – номер записи, К – значение ключа.

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

При организации доступа по ключу широко применяются индексные файлы.

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

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

· выбор хеш- функции;

· выбор метода разрешения коллизий.

3. Индексные файлы

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

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

В зависимости от организации индексной и основной областей различают 2 типа фалов: с плотным и неплотным индексом. Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются индексно-последовательными файлами.

4. Файлы с плотным индексом

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

Здесь значение ключа – это значение первичного ключа, а номер записи – это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.

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

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

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

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

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

Файлы с неплотным индексом

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

Значение ключа первой записи блока

Номер блока с этой записью

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

Пример заполнения основной и индексной областей, если первичным ключом являются целые числа.

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

При включении новая запись должна заноситься сразу в требуемый блок на требуемое место. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить требуемую запись, а потом этот блок считывается в ОП, затем в ОП корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, также как и в первом случае должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL-Server этот процент называется Full-factor и используется при формировании кластеризованных индексов. Кластеризованными называют те индексы, в которых исходные записи физически упорядочены по значениям первичного ключа. При внесении новой записи индексная область не корректируется. Количество обращений к диску при добавлении новой записи равно количеству обращений, необходимых для поиска соответствующего блока плюс одно обращение, которое требуется для занесения измененного блока на старое место.

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

На практике для создания индекса для некоторой таблицы БД пользователь указывает поле таблицы, которое требует индексации. Ключевые поля таблицы во многих СУБД, как правило, индексируются автоматически. Индексные файлы, создаваемые по ключевым полям таблицы, часто называют файлами первичных индексов. Индексы, создаваемых для не ключевых полей, называют вторичными индексами. Введение таких индексов не изменяет физического расположения записей таблицы, но влияет на последовательность просмотра записей. В некоторых СУБД, например, Access деление на первичные и вторичные индексы не производится. В этом случае используются автоматически создаваемые индексы и индексы, определяемые пользователем.

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

· вида содержимого в поле ключа записей индексного файла;

· типа используемых ссылок (указателей) на запись основной таблицы;

· метода поиска нужных записей.

5. Моделирование отношений 1:М на файловых структурах

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

Моделирование отношений 1:М с использованием однонаправленных указателей

В этом случае связываются 2 файла, например, Ф1 и Ф2, причем предполагается, что одна запись в файле Ф1 может быть связана с несколькими записями в файле Ф2. При этом файл Ф1 в этом комплексе условно называется основным, а файл Ф2 – подчиненным. Структура основного файла может быть представлена в виде 3 областей:

Ссылка-указатель на первую запись в подчиненном файле, с которой начинается цепочка записей файла Ф2, связанных с данной записью в файле Ф1

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

Таким образом, каждая запись подчиненного файла делится на 2 области: область указателя и область, содержащую собственно запись.

Структура записи подчиненного файла.

Указатель на следующую запись в цепочке

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

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

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

Рис. 13.1. Файл как последовательность записей переменной длины

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

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

Рис. 13.2. Пример организации индекса для последовательного файла

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Имена файлов

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

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

Типы файлов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 11.1. Файл как последовательность записей переменной длины

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

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

Рис. 11.2. Пример организации индекса для последовательного файла

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

Файл — это набор сгруппированных данных, которому дали имя и записали на физическом носителе. У файлов есть атрибуты, которые говорят операционной системе, как с ними работать. Для организации сохранённых файлов используются абстрактные модели. Наибольшее распространение получили иерархические модели — деревья директорий (папок) и файлов.

Как это понять

Файлы

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

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

С появлением магнитных лент для хранения данных стали использовать другую модель — последовательность записей переменной длины. Считать с магнитной ленты данные или записать их на неё можно только последовательно (последовательный доступ). Файлом стали называть часть магнитной ленты с записанными на неё данными. Программисты должны были знать, с какого и по какое место на ленте записаны их данные.

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

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

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

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

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

Практически в любой операционной системе работа с файлами осуществляется по похожему сценарию:

Открытие файла (начало сессии);
Работа с содержимым файла и его атрибутами;
Закрытие файла (окончание сессии).

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

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

open — открытие сессии работы с файлом / создание нового файла;
close — закрытие сессии работы с файлом;
read / write — читать / писать в файл относительно положения указателя чтения / записи;
delete — удалить файл;
seek — позиционирование указателя чтения / записи;
rename — переименование файла;
read_attributes / write_attributes — чтение / модификация атрибутов файла.

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

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

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

Один из методов решения коллизий — запретить создавать файлы с одинаковыми именами.

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

Продолжением одноуровневых файловых систем являются системы с фиксированным количеством уровней. Такие файловые системы используются на маршрутизаторах и телевизорах.

Самой успешной моделью файловой системы является иерархическая модель. Она произвела настоящую революцию в хранении данных. Иерархическая система подразумевает существование дерева данных с узлами трёх типов:

корневая директория (каталог, папка) — специальный узел дерева;
обычная директория (каталог, папка) — обычные узлы дерева;
файлы — листья дерева.

Такая структура позволяет хранить файлы в разных директориях. Полное имя файла состоит из пути до файла в дереве директорий и имени файла. Таким способом обеспечивается уникальность имён. Файлы с одинаковыми именами не создают коллизии, если хранятся в разных директориях.

Один уровень иерархии от другого отделяется особым символом (например, / для Unix-подобных систем и \ для операционных систем на базе Windows). Поддерживаются и относительные имена файлов, из которых можно сформировать полное имя путём конкатенации (сложения строк) имени директории и относительного имени.

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

Модуль 8. Управление данными

Тема 15. Способы доступа и организации файлов. Распределение файлов на диске

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

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

Существует три способа доступа к данным, расположенным во внешней памяти:

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

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

Прямой - непосредственно по ключу или физическому адресу записи.

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

Записи располагаются в физическом порядке и обеспечивают доступ в физической последовательности. Таким образом, для обработки записи с номером N+1 необходимо последовательно обратиться к записям с номером 1, 2,….,N. Это универсальный способ организации файла периферийного устройства. Используется так же для организации входного/выходного потока.

Индексно-последовательный.

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

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

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

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

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

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

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

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

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

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

Рисунок 1. Коэффициент блокирования 7

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

1.Трековый, в котором весь диск подразделяется на треки (дорожки) фиксированной длины, на которых размещаются блоки переменного размера. Адресом блока является тройка:

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

2.Секторный, в котором диск разбивается на блоки фиксированного размера, обычно кратного 256 байтам. Адресом блока является его порядковый номер на носителе.

Работа с дисковой памятью включает в себя 4 основные процедуры:

Инициализация тома (форматирование).
Выделение и освобождение памяти файлу.
Уплотнение внешней памяти (дефрагментация).
Копирование, восстановление томов для обеспечения целостности.

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

Выделение и освобождение места для файлов на томе аналогично стратегии размещения ОП.

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

Популярным способом, используемым, например, в файловой системе FAT операционной системы MS-DOS, является использование связанного списка индексов. С каждым блоком (кластером) связывается некоторый элемент - индекс. Индексы располагаются в отдельной области диска (в MS-DOS это таблица FAT). Если некоторый блок распределен файлу, то индекс этого блока содержит номер следующего блока данного файла. При этом для каждого файла в каталоге имеется поле, в котором отмечается номер начального индекса для кластера, входящего в файл. Последний индекс содержит специальный маркер конца файла. Такая физическая организация сохраняет все достоинства предыдущего способа и снимает отмеченный недостаток: для доступа к произвольному месту файла достаточно прочитать только блок индексов, отсчитать нужное количество блоков файла по цепочке и определить номер нужного блока.

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

Читайте также: