Лекция 11
Глава 8. Управление внешней памятью
1. Файлы. Иерархия данных Организация файлов. Методы доступа. Характеристики файлов.
2. Файловая система. Функции файловой системы. Состав файловой системы. Файловая система UNIX. Размещение файлов в дисковой памяти.
Литература
· [Дейтел 87] Введение в операционные системы. М."Мир",1987.
· [Кейлингерт 85] Элементы операционных систем, М."Мир", 1985.
· [Кейслер 86] Проектирование операционных систем для малых ЭВМ, М."Мир", 1986.
· [Колин 75] Введение в операционные системы, М."Мир", 1975.
· [Цикритзис 77] Операционные системы, М."Мир", 1977.
Файлы
Иерархия данных
Нижний уровень иерархии составляют битовые комбинации , с помощью которых создаются практически любые элементы данных. На следующем уровне находятся байты и символы (например, для “аски” ASCII-кода 8-битовые комбинации). Более крупной структурой являются поля : алфавитные, цифровые или алфавитно-цифровые, а группа взаимосвязанных полей образует записи. Записи могут быть объединены в файлы, а группы взаимосвязанных файлов составлять базу данных..
Битовые комбинации
Байты
Символьные наборы
Поля
Записи
Файлы
Базы данных
Файл (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
· Прямая - доступ к записям осуществляется произвольно по их физическим адресам на запоминающем устройстве прямого доступа.
· Библиотечная - это по сути файл, состоящий из последовательных подфайлов, где каждый последовательный подфайл называется элементом, или членом файла. Начальный адрес каждого такого элемента хранится в директории файла. Библиотечные (секционированные) файлы наиболее часто используются для хранения программных библиотек или библиотек макросов.
Методы доступа
Операционные системы реализуют, как правило, различные методы доступа к файлам, которые можно сгруппировать в две категории:
· методы доступа с очередями;
· базисные методы доступа.
Методы доступа с очередями применяются в тех случаях, когда последовательность обработки записей можно предвидеть, например при последовательной и индексно-последовательной организациях. В этих методах предусматривается упреждающая буферизация и планирование операций ввода-вывода. Кроме того, эти методы обеспечивают автоматическое блокирование и деблокирование записей.
Базисные методы доступа применяются обычно в случаях, когда последовательность обработки записей предвидеть нельзя, в частности при прямом или произвольном доступе. Базисными методами читаются и записываются физические блоки, блокирование и деблокирование, при необходимости, определяет сам пользователь.
Характеристики файлов
· Изменчивость - указывает на частоту внесения в файл новых записей и удаление старых. Когда частота мала, файл называют статичным, а когда велика - динамичным или изменчивым файлом.
· Активность - определяется процентом записей файла, обрабатываемых в течение данного прогона.
· Размер - определяет количество информации, хранящейся в файле.
Файловая система
Файловая система - это часть общей системы управления памятью (см. Структура ядра ОС), назначение которой сводится в основном к управлению файлами, хранящимися во внешней памяти, а также к контролируемому разделению информации между пользователями.
Функции файловой системы
· предоставление возможности создавать, модифицировать, уничтожать файлы;
· контролируемое разделение файлов несколькими пользователями;
· предоставление пользователю возможности задания различной структуры файлов и возможности управления передачей информации между файлами;
· в системе должны быть предусмотрены средства обеспечения сохранности и восстановления информации в файлах;
· система должна обеспечивать независимость файлов от внешних устройств, т. е. пользователям должна быть предоставлена возможность обращения к файлам с использованием символических имен;
· система должна предоставлять защиту информации в файлах от несанкционированнного доступа (возможность шифрования и дешифрования данных);
· файловая система должна иметь “дружественный” интерфейс по отношению к пользователю.
Состав файловой системы
Файловая система, входящая в состав ядра ОС, как правило, содержит следующие средства:
· Методы доступа, которые определяют конкретную организацию доступа к данным, хранящимся в файлах.
· Средства управления файлами, обеспечивающие хранение файлов, обращение к ним, коллективное использование и защиту.
· Средства управления внешней памятью, обеспечивающие распределение пространства внешней памяти для размещения файлов.
· Средства обеспечения целостности файлов, которые гарантируют сохранность информации файла.
Файловая система UNIX
Рассмотрим файловую систему на примере UNIX. Как уже отмечалось, основной функцией файловой системы является распределение дискового пространства на именованные учестки - файлы. Некоторые системы поддерживают разнотипные файлы с соответствующими методами доступа (прямой, индексный, индексно-последовательный и т. п.). в UNIX этого нет. Ее файловая система чрезвычайно проста, и файлы представляют собой просто последовательности байтов. Иногда к ним обращаются как к текстовым или двоичным данным, но различаются они лишь содержимым, а не структурой и методом доступа. В современных условиях это вовсе не недостаток, так как в этом случае система становится универсальной - не делается никаких предположений о внутренней структуре данных файла, и доступ к любому внешнему устройству, а также к другому процессу осуществляется как к обычному файлу.
Для пользователя, успевшего поработать с MS DOS или Windows иерархичнось файловой системы UNIX , которая строится в виде сети, не представляет ничего удивительного, за исключением, может быть того, что сняты все ограничения на длину имени файла. В UNIX имеется три вида файлов, доступ к которым идентичен:
· обычные дисковые файлы;
· каталоги;
· специальные файлы
Обычные файлы размещаются на диске и содержат информацию, которую в них заносит пользователь. Файлами также являются готовые к исполнению программы, объектные модули и т. д. Система не накладывает никаких ограничений на внутреннюю структуру информации, хранимой в файле. Структурой информации управляет пользователь, а не система. С точки зрения UNIX обычный файл является бесструктурным массивом байтов с прямым доступом. Однако, текстовые файлы в UNIX принято форматировать в виде строк произвольной длины, отделенных друг от друга символами перевода строки.
Каталоги в общеупотребительном смысле - это просто папки, где хранятся файлы, сгруппированные по какому-либо произвольному признаку, например текстовые документы, выполнимые программы, библиотеки и библиотечные модули, исходные тексты программ и т. д. В свою очередь, группы каталогов могут образовывать в логическом смысле том с главным корневым каталогом, на который может быть смонтирована та или иная файловая система. Каталоги содержат информацию о файлах. В том числе их имена, размеры, методы доступа, режимы и типы.
Поскольку каталоги содержат важную информацию о файлах, они защищены механизмами ОС. В отличие от обычного файла для записи и чтения информации из файла-каталога требуются системные привилегии. Во всех других отношениях, с точки зрения ОС, это такой же обычный файл.
Внутренняя структура каталога весьма простая: для каждого файла или другого каталога нижнего уровня создается запись. Организованная в структуру следующего содержания:
Struct {
Int inodе; /*индексный дескриптор*/
Char name;/*имя файла*/
}
Здесь inodе содержит номер индексного дескриптора, в котором сосредоточена информация о типе файла (каталог, обычный файл или специальный файл), о коде его защите, длине, дате и времени создания, а также о расположении данных файла на диске. Существует по одному дескриптору на каждый файл, и именно с ними работает файловая система.
Структура каталогов
2 байта 14 байт
Номер индексного дескриптора Имя файла Структура записи каталога UNIX
(16 байт)
 |  |  |
Имя файла Расширение Атрибуты Резервные Структура записи каталога
MS DOS (32 байта)
Резервные Время Дата Номер первого Размер
блока
Каталоги могут непосредственно содержать значения характеристик файлов, как это сделано в файловой системе MS DOS, или ссылаться на таблицы, содержащие эти характеристики, как это реализовано в ОС UNIX. Каталоги могут организовывать иерархическую структуру за счет того, что каталоги более низкого уровня могут входить в каталоги более высокого уровня. Иерархия каталогов может быть деревом или сетью. Каталоги образуют дерево, если файлу разрешено входить только в один каталог, и сеть - если файл может входить сразу в несколько каталогов. В MS DOS каталоги образуют древовидную структуру, а в UNIX - сеть.
Логическая организация файловой системы
Одноуровневая Дерево (иерархия MS DOS)
 |  |
 |  |
Сеть (иерархия UNIX)
 |
Дескриптор файла
Введение понятия дескриптор файла позволяет отделить имя файла, с которым оперирует пользователь от специфических данных с которым работает ОС. Такой подход чрезвычайно гибок и позволяет манипулировать внешним представлением иерархии файлов, не перемещая самих файлов.
В частности, весьма просто один и тот же файл поместить в разные каталоги. Создав в них соответствующие именные ссылки на этот файл. Но никуда его физически не перемещая. Файл может иметь одно и то же имя в разных каталогах или имена-синонимы, но ссылаться они будут на один и тот же индексный дескриптор, который является ключом для доступа к данным файла.
Каждая новая ссылка из каталогов к индексному дескриптору отмечается в специальном его поле. Это позволяет файловой системе следить за занятостью файла: как только счетчик станет равным нулю, индексный дескриптор освобождается, а дисковое пространство может быть использовано для записи других файлов.
Индексные дескрипторы
1 13 22
root
 |  |
 | |
p
prog1 bin 1 .. 1
22 prog1 137 proc
p1
13 bin 98 p1
proc
77 p2 22 myprog
myprog
 |
рис. 17 Фрагмент файловой системы и содержание каталогов
root и bin
Каталог root является корневым каталогом тома и потому имеет индексный дескриптор с номером 1. Файлы с именами. и.. в каталоге root ссылаются сами на себя, т. к. каталога более высокого уровня нет. Интересно то, что имена myprog и prog1 ссылаются на один и тот же индексный дескриптор, т. е. на один и тот же файл.
Файлы и каталоги представляют собой, таким образом, логическую структуру файловой системы UNIX, которую можно представить в виде перевернутого дерева, имеющего один корень и множество ветвей. Каждая ветвь такого дерева является каталогом, а каждый листок на конкретной ветви - файлом каталога. Ветви ствола называются “родительсткими” каталогами по отношению к каталогам и файлам, которые они содержат внутри себя, и наоборот, каталоги и файлы, которые расположены на основных ветвях, называются “дочерними” каталогами и файлами по отношению к каталогам, в которых они содержатся.
Специальные файлы. В UNIX все внешние устройства рассматриваются как файлы, допуская производить над собой обычные файловые операции, соответственно интерфейс к драйверам устройств оформлен для пользователя как обращение к файлу, называемому специальным файлом. Каждому подключенному устройству, например терминалу, дискам, печатающему устройству и т. д. соответствует минимум один специальный файл.
Когда программа пользователя выполняет записи в такой специальный файл, ОС перехватывает их и направляет на соответствующее внешнее устройство. При чтении данных из этого файла в действительности они принимаются с соответствующего внешнего устройства. Пользовательская программа не должна учитывать особенности работы устройства ввода-вывода. Для этой цели и служат специальные файлы, которые выполняют функции интерфейса между компонентами ядра ОС (драйверы) и прикладными программами общего назначения.
Система обнаруживает отличие обычного файла от специального только после того, как будет проанализирован соответствующий индексный дескриптор, на который ссылается запись в каталоге. Индексный дескриптор специального файла содержит информацию о классе устройства, его типе и номере.
Класс устройств. Некоторые устройства ввода-вывода работают посимвольно, другие поблочно. Типичным примером устройства с посимвольным обменом может служить терминал. Компьютер осуществляет обмен данными с терминалом в побайтовом режиме. Специальные файлы, обеспечивающие связь с устройствами такого типа, называют байт-ориентированными.
Для блочных устройств характерен обмен большими блоками информации, чтобы ускорить обмен и сделать его более эффективным. Так работают все дисковые устройства, которые называются блочными, а специальные файлы, обслуживающие их - блок-ориентированными.
Тип и номер устройств. Специальные файлы не содержат какой-либо символьной информации, поэтому в каталоге их длина не указывается. Для специальных файлов в поле длины помещаются главный и дополнительный номера соответствующих устройств. Первый из них определяет тип устройства, второй - идентифицирует его среди однотипных. Так UNIX может обслуживать несколько десятков терминалов, каждый из них должен иметь свой собственный специальный файл, поэтому наличие главного и дополнительного номеров позволяет установить требуемое соответствие между устройством и таким файлом.
Таким образом специальные файлы служат средством унификации ввода-вывода в ОС.
Размещение файлов в дисковой памяти
Размещение файлов в дисковой памяти во многом похоже на распределение памяти при мультипрограммировании с переменными разделами. Заметим, что в процессе работы системы, дисковое пространство подвержено фрагментации, в связи с чем, размещение файлов приходится осуществлять по разбросанным блокам. Очевидно, возможно использовать уже рассмотренный нами способ “сбора мусора”, однако это не всегда бывает эффективно.
Связное распределение памяти
1 Свободен |
|
3 |
4 |
5 Свободен |
2
Связное распределение памяти предполагает, что каждому файлу отводится одна непрерывная область внешней памяти. Одним из достоинств этого метода является то, что последовательные логические записи размещаются, как правило, физически рядом, что позволяет повысить скорость доступа. Достаточно просто в этом случае и реализовать каталоги, т. к. для каждого файла необходимо хранить только начальный адрес и длину файла. Недостатком такого подхода к распределению памяти является то, что после уничтожения файлов и возвращении, занимаемого ими ресурса в список свободных, вновь размещаемые файлы должны укладываться в существующие свободные области. Таким образом мы здесь сталкиваемся с теми же проблемами, что и при фрагментации в системах мультипрограммирования с переменными разделами - необходимость объединения свободных соседних участков памяти. Кроме того, при работе с динамично меняющимися размерами файлов этот способ может оказаться нерациональным.
Несвязное распределение памяти
Распределение при помощи списков секторов
В этом случае память рассматривается как набор индивидуальных секторов. Файлы состоят из секторов, которые могут находиться в различных местах внешней памяти. Секторы, принадлежащие одному файлу, содержат ссылки-указатели друг на друга, образующие список. В списке свободного пространства содержатся все свободные секторы внешней памяти.
|
2 Свободен |
|
4 Свободен |
|
1
3
5При необходимости увеличения размера файла, соответствующий процесс запрашивает дополнительное количество секторов из числа свободных, а при уменьшении размера, освободившиеся секторы возвращаются в список свободных. Таким образом, удается избежать необходимости уплотнения памяти.
Недостатком же такого способа распределения памяти является увеличение накладных расходов для создания механизма обработки ссылок-указателей, а также возможное увеличение времени доступа.
Поблочное распределение памяти
Вариант поблочного распределения совмещает в себе элементы связного и несвязного распределения, в этом случае память распределяется не индивидуальными секторами, а блоками смежных секторов, причем при выделении новых блоков система стремится выбирать свободные блоки, как можно ближе к уже существующим блокам файла. При каждом обращении к файлу вначале определяется соответствующий блок, а затем соответствующий сектор в рамках этого блока.
Реализация поблочного распределения памяти может осуществляться при помощи цепочек блоков, цепочек индексных блоков и таблиц отображения.
Цепочка блоков
Каталог
 | ||
| | |
Файл Местоположение Данные Данные Данные Nil
В схеме с цепочками блоков строка в каталоге указывает на первый блок файла, далее каждый блок фиксированной длины, входящий в состав файла, содержит две части: собственно данные и указатель следующего блока. Минимально выделяемая единица памяти - это блок фиксированного размера.
Очевидно, что для нахождения конкретной записи в файле, необходимо просмотрев цепочку, найти соответствующий блок, а затем в блоке необходимую запись. Поскольку блоки могут быть разбросаны по всему диску, то этот процесс может занимать много времени. Для сокращения времени доступа можно цепочки делать с двунаправленными ссылками, что дает возможность просматривать цепочку в обоих направлениях.
Цепочка индексных блоков
Каталог
 |
Файл Местоположение
Цепочка индексных блоков
|
 |
 |
|
 |
|
…
При использовании цепочки индексов, указатели помещаются в отдельные индексные блоки с фиксированным числом элементов. Каждая строка-статья содержит идентификатор записи и указатель на эту запись, если для описания файла требуется более чем один индексный блок, то организуется цепочка таких блоков. Главное достоинство этого метода перед цепочкой блоков в том, что при поиске нужного блока достаточно просмотреть только индексную цепочку.
Главный недостаток такой схемы в том, что для вставки дополнительных записей может потребоваться полная перестройка структуры индексных блоков.
Каталог Таблица поблочного отображения файлов
|
Файл Местоположение
А 4
В 6 Таблица отображения
файлов
0 |
1 |
2 |
|
|
5 |
|
7 |
8 |
9 |
3 6
4 Nil
6 4Физические блоки внешней памяти
Блок 0 | Блок 1 | Блок 2 | Блок 3 А(1) | Блок 4 А(3) |
Блок 5 | Блок 6 А(2) | Блок 7 | Блок 8 | Блок 9 |
В схеме с таблицами поблочного отображения вместо указателей используются номера блоков. Обычно номера легко преобразуются в фактические адреса. Используется таблица отображения файлов, в которой содержатся по одной строке на каждый блок диска. Строка в каталоге пользователя указывает на строку таблицы отображения, соответствующей первому блоку данного файла. Каждая строка таблицы отображения содержит номер следующего блока данного файла. Таким образом, можно все блоки файла находить последовательно просматривая строки таблицы отображения файлов. В тех строках таблицы, которые соответствуют последним блокам файлов, обычно устанавливается пустой указатель Nil. В некоторых строках таблицы указывается признак “свободен”, указывающий на то, что данный блок может быть выделен по очередному запросу.
Главное достоинство подобной схемы состоит в том, что по таблице отображения файлов можно судить о физическом соседстве блоков.
