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

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

Файл (file) - поименованная совокупность данных. С файлами возможно производить операции как с единым целым при помощи операторов: oткрыть(open), закрыть(close), создать(create), уничтожить(destroy), копировать(copy), переименовать(rename), вывести(list). Кроме того, возможны операции над отдельными компонентами файлов: прочитать(read), записать(write), обновить(update), вставить(insert), исключить(delete).

Организация файлов

Под организацией файлов понимается способ расположения записей во внешней памяти. Существуют следующие способы организации.

·  Последовательная - записи располагаются в физическом порядке, т. е. “следующая” запись - это запись, которая физически следует за предыдущей, здесь записи могут быть как фиксированной длины, так и переменной.

…

Записи фиксированной

длины

Записи переменной

длины

Указатели длины записи

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

1 2 3

k1 k2 k3

k1<k2<k3

Индексная таблица

Ключ Адрес

k1

k2

k3

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

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

Методы доступа

Операционные системы реализуют, как правило, различные методы доступа к файлам, которые можно сгруппировать в две категории:

·  методы доступа с очередями;

·  базисные методы доступа.

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

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

Характеристики файлов

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

·  Активность - определяется процентом записей файла, обрабатываемых в течение данного прогона.

·  Размер - определяет количество информации, хранящейся в файле.

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

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

Функции файловой системы

·  предоставление возможности создавать, модифицировать, уничтожать файлы;

·  контролируемое разделение файлов несколькими пользователями;

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

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

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

·  система должна предоставлять защиту информации в файлах от несанкционированнного доступа (возможность шифрования и дешифрования данных);

·  файловая система должна иметь “дружественный” интерфейс по отношению к пользователю.

Состав файловой системы

Файловая система, входящая в состав ядра ОС, как правило, содержит следующие средства:

·  Методы доступа, которые определяют конкретную организацию доступа к данным, хранящимся в файлах.

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

·  Средства управления внешней памятью, обеспечивающие распределение пространства внешней памяти для размещения файлов.

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

Размещение файлов в дисковой памяти

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

Связное распределение памяти

1 Свободен

2

3

4

5 Свободен

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

Несвязное распределение памяти

Распределение при помощи списков секторов

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

1

2 Свободен

3

4 Свободен

5

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

Недостатком же такого способа распределения памяти является увеличение накладных расходов для создания механизма обработки ссылок-указателей, а также возможное увеличение времени доступа.

Поблочное распределение памяти

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

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

Цепочка блоков

Каталог

Файл Местоположение Данные Данные Данные Nil

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

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

Цепочка индексных блоков

Каталог

Файл Местоположение

Цепочка индексных блоков

…

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

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

Каталог Таблица поблочного отображения файлов

Файл Местоположение

А 4

В 6 Таблица отображения

файлов

0
1
2
3 6
4 Nil
5
6 4
7
8
9

Физические блоки внешней памяти

Блок 0	Блок 1	Блок 2	Блок 3 А(1)	Блок 4 А(3)
Блок 5	Блок 6 А(2)	Блок 7	Блок 8	Блок 9

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

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