Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем
Подождите немного. Документ загружается.
221
• замок (lock) разделяемого доступа;
• режим обработки;
• режим буферизации;
• текущее положение файлового курсора;
• идентификация устройства, на котором расположен файл;
• информация, зависящая от типа файла.
Так, например, при подключении тома к ФС в виде ветви общего
дерева каталогов, в памяти создается дескриптор для псевдокаталога,
которым представлен подключенный том. Этот дескриптор содержит
признак, описывающий его как "точку монтирования", и ссылку на
элемент специальной системной таблицы монтирования. Элемент же
таблицы содержит описание тома и указатели как на корневой каталог
тома, так и обратно – на "точку монтирования", что позволяет проходить
эту точку при движении по дереву в обоих направлениях.
Очевидно, что некоторые поля дескриптора должны изменяться
автоматически при работе с файлом. Все изменения, выполненные в
дескрипторе в ходе работы с открытым файлом, запоминаются в его копии
на внешней памяти при выполнении системного вызова close.
Обычно ОС предоставляют также в составе своего API тот или иной
набор системных вызовов, сводящихся к двум типам: getFileInfo,
setFileInfo – получить или установить информацию о файле.
Выполнение вызовов этой группы позволяет прочитать/записать значения
отдельных полей файловых дескрипторов.
УПРАВЛЕНИЕ ДОСТУПОМ
В некоторых ОС одной из важнейших функций базовой ФС является
контроль за доступом пользователей к файлам. Мы говорим "в некоторых",
так как в ряде ОС проблема контроля доступа решается на общесистемном
уровне и доступ к файлам – ее частный случай. Такие ОС рассматриваются
222
нами в главе 10, здесь же мы остановимся на случае, когда доступ к файлам
контролируется базовой ФС, и рассмотрим его на примере ОС Unix.
В Unix возможны следующие режимы доступа к файлам: r – чтение,
w – запись, x – выполнение. Возможны также их комбинации.
Пользователи подразделяются на следующие категории:
• владелец – пользователь, который создал файл;
• группа – пользователи, входящие в ту же группу, что и владелец
файла;
• все остальные пользователи.
Для каждого файла определяется допустимый режим доступа для
каждой из этих трех групп. Так, например, если для файла доступ
закодирован в виде:
rwxr-x--x,
то это означает, что владелец имеет право читать, писать и выполнять файл
(rwx), остальные члены группы владельца имеют право читать и
выполнять файл (r-x), все другие пользователи – только исполнять (--x).
Идентификатор владельца и группы владельца входят в состав
файлового дескриптора. Для кодировки прав доступа достаточно трех 3-
битных позиционных кодов, которые также включаются в дескриптор.
Каждая активизация файлового дескриптора базовой ФС включает в
себя проверку прав доступа. В ходе проверки определяется идентификатор
владельца процесса, открывающего файл. Этот идентификатор
сравнивается с идентификатором владельца файла и с идентификатором
группы владельца файла. В зависимости от результатов сравнения
определяется категория пользователя, открывающего файл, и выбирается
соответствующий 3-битный код доступа. Режим доступа, запрашиваемый
при открытии, сравнивается с кодом доступа и при несоответствии их
происходит отказ в доступе.
223
Как мы отмечали выше, с точки зрения базовой ФС, каталоги
практически ничем не отличаются от файлов, следовательно, все, что
говорилось выше о правах доступа применимо и к каталогам.
Поскольку логическая ФС при поиске обращается к базовой ФС для
чтения информации из каталогов, а базовая ФС производит при этом
проверку прав доступа, то файл может быть доступен для данного
пользователя только, если для него доступны все подкаталоги, входящие в
путь к файлу.
Как определяется доступ к алиасам и косвенным файлам? Что
касается алиасов, то ответ зависит от того, связываются ли права доступа с
именем или с файлом. До сих пор мы говорили о том, что права доступа
хранятся в файловом дескрипторе, поскольку физическому файлу
соответствует единственный файловый дескриптор, права доступа к файлу
по всем алиасам будут одинаковы. Возможно, однако, хранение прав
доступа не в дескрипторе, а в элементе каталога, в этом случае разные
алиасы могут обеспечивать разные права доступа к одному файлу.
Возможны два варианта реализации прав доступа к косвенному файлу. В
первом варианте в псевдодескрипторе, содержащем ссылку, указываются
права доступа, как для обычного файла, при соответствии конкретного
режима доступа этим правам проверка прав доступа заканчивается. Во
втором случае проверка прав доступа продолжается и для всех каталогов,
входящих в путь, указанный в ссылке.
7.6. Физическая структура файлов
До этого уровня ФС оперировала с виртуальными адресами в файле –
относительными номерами байт или записей. Уровень физической
структуры выполняет перевод реальных адресов в физические адреса на
носителе. На этот уровень ложатся все задачи, связанные с управлением и
распределением реальной внешней памяти. Внешняя память может
включать в себя как устройства произвольного доступа (в дальнейшем –
224
диски), так и устройства последовательного доступа (в дальнейшем –
ленты). Мы сосредоточимся здесь только на дисковой памяти, имея в виду
то обстоятельство, что задачи управления памятью на лентах составляют
лишь узкое подмножество задач, возникающих при управлении дисками.
Несколько принципиально важных положений являются общими для
любых способов управления дисковой памятью.
1) Дисковая память состоит из блоков, являющихся единицами
распределения дискового пространства (например, секторов). Каждый
блок имеет уникальный номер (адрес), его идентифицирующий. В каждый
блок может быть записана любая информация достаточно сложной
структуры, в том числе и содержащая ссылки на другие блоки.
2) Каждый физический диск описывается дескриптором диска,
который содержит информацию о количестве и размере блоков на диске и
о свободном пространстве на диске. Дисковый дескриптор записывается на
известное заранее место на диске (чаще всего – в первый блок).
3) Каждый файл в составе своего дескриптора имеет план своего
размещения (layout) на физическом пространстве диска.
4) Информация, записываемая на диск, может быть избыточной для
обеспечения возможности ее восстановления при сбоях.
5) Дисковое пространство распределяется блоками фиксированной
длины. Даже в тех дисковых архитектурах, которые допускают
чтение/запись блоками переменной длины, размер единицы
распределения, как правило, все равно фиксирован, например, дорожка.
Возможно объединение в единицу распределения нескольких смежных
блоков, такой прием носит название кластеризации (clastering), а порции
распределения, состоящие из нескольких блоков, называются кластерами.
Кластеризация может быть как симметричной – с заранее установленным
размером кластера, так и асимметричной – с размером кластера,
выбираемым для каждого распределения.
225
6) Поиск на диске управляющих структур ФС и свободных блоков
может оказаться слишком времяемким. Поэтому те управляющие
структуры, обращение к которым происходит наиболее часто, обычно
копируются в оперативную память. Это создает дополнительные
проблемы, связанные с надежностью функционирования ОС. При крахе
системы изменения в управляющих структурах могут быть не перенесены
из кеша на внешнюю память. Специальные системные процессы ОС
обычно обеспечивают периодическое (например, раз в минуту) сохранение
управляющих структур на внешней памяти.
Выше мы указывали на наличие в файловом дескрипторе плана
размещения файла. Отметим, что поскольку дескриптор представляет
собой одинаковую для всех файлов структуру данных, то размер его
должен быть фиксированным. Не во всех случаях план размещения файла
может иметь фиксированную длину. Если не удается добиться
фиксированной длины плана, то переменная его часть может быть
вынесена из файлового дескриптора. Вид представления плана зависит от
способа распределения файлам дисковой памяти.
Распределение дисковой памяти может быть классифицировано как
смежное или не смежное. В первом случае файлу распределяется
непрерывный участок внешней памяти, во втором – файл может быть
разбросан по пространству диска.
Смежное распределение весьма привлекательно по нескольким
причинам. Во-первых, план размещения в этом случае получается
простейшим: он состоит только из номера начального блока и количества
блоков. Во-вторых, и это более важно, смежное размещение обеспечивает
высокую степень локализации обращений к дорожкам при обработке
файла и, следовательно, высокую эффективность обмена.
Однако, и недостатки смежного распределения более чем серьезны.
Во-первых, как и при распределении оперативной памяти блоками
226
переменной длины, здесь возникают все проблемы фрагментации
пространства памяти (внешних дыр). Во-вторых, такое распределение
требует, чтобы необходимый размер дискового пространства указывался
при создании файла – эта информация не всегда может быть предоставлена
пользователем, создающим файл. В-третьих, расширение файла за пределы
установленного размера невозможно – для файлов с длительным сроком
существования эта проблема может стать критической. Перечисленные
недостатки могут быть не радикально преодолены, но могут быть
несколько сглажены, если допустить, чтобы файл занимал не один, а
несколько участков дискового пространства. При создании такого файла
задаются требования к размеру первичного и вторичного распределения.
Файлу выделяется непрерывный участок памяти в соответствии с
первичным размером. Если далее оказывается, что файл не помещается в
первичный участок, ему выделяется дополнительный участок (экстент –
extent), размер которого задается требованием ко вторичному
распределению. Экстент занимает непрерывную область на диске, но
необязательно смежную с первичным участком. Затем может быть
выделен второй экстент и т.д. План файла в его дескрипторе в этом случае
представляется массивом пар "начальный адрес – длина", каждый элемент
которого соответствует одному экстенту. Размер этого массива в
дескрипторе ограничивает допустимое число экстентов.
Очевидно, что смежное распределение является негибким. Это в
первую очередь послужило причиной полного отказа от него в ОС Unix и в
MS DOS. Однако, в связи с увеличением объемов дисковых накопителей
вопросы повышения эффективности обмена приобретают все большее
значение и локализация файлов является хорошим средством повышения
этой эффективности. В последнее время наметилась тенденция к
размещению файлов в смежных областях диска, пусть даже и в рамках
227
несмежной модели распределения (см., например описание ФС HPFS,
NTFS, Veritas, JFS в Части II).
Практически все системы, использующие несмежную модель, имеют
в своем наборе утилит такие, которые производят реорганизацию дисков,
переписывая файлы таким образом, чтобы они располагались в смежных
блоках.
Несмежное распределение допускает, чтобы файл состоял из
большого числа участков (отдельных блоков) и план файла должен
описывать размещение каждого из блоков файла. Можно выделить три
основных подхода к представлению плана файла в несмежной модели:
• списки блоков;
• карта размещения;
• списки указателей на блоки.
Метод списков блоков предполагает, что в файловом дескрипторе
содержится только указатель на первый выделенный файлу блок. В самом
блоке на фиксированном месте содержится указатель на второй блок, во
втором – на третий и т.д. Таким образом, блоки выстраиваются в
односвязный линейный список. С учетом того, что список располагается
на внешней памяти, этот метод может применяться только для файлов с
последовательным доступом.
Метод карты размещения хорошо известен программистам в MS DOS
по Таблице размещения файлов FAT. ФС для каждого диска поддерживает
таблицу, каждая строка которой описывает один блок на диске. В списки
связываются не сами блоки, а соответствующие им элементы карты. Карта
размещения обеспечивает достаточно простой и эффективный метод
управления распределением, но сосредоточение информации о размещении
всех файлов в одной структуре данных делает эту структуру узким местом
ФС с точки зрения безопасности.
Метод списков указателей на блоки предполагает наличие для
каждого файла перечня номеров блоков, ему распределенных. Этот
228
перечень записывается в отдельный блок, специально выделяемый для
этой цели, а файловый дескриптор содержит указатель на этот блок. Если в
блоке не хватает места для всего перечня, то последний в нем номер
адресует блок, содержащий продолжение перечня и т.д. При применении
этого метода "в чистом виде" список блоков, как всякий линейный список,
может обрабатываться только последовательно, доступ к блокам файла,
имеющим большие виртуальные номера, может быть значительно
замедлен. Поэтому на практике применяются различные модификации
этого метода. Классическим примером такого подхода является ФС s5
первых версий ОС Unix [33].
Учет дискового пространства, выделенного файлу (план размещения),
ведется в s5 следующим образом. Как показали исследования, на любом
носителе всегда есть большое число файлов, объем которых не превышает 1
Кбайт. Для таких файлов нет никакой необходимости выделять отдельные
блоки для размещения плана, а тем более – увязывать эти блоки в какие-
либо списки. Поэтому непосредственно в файловом дескрипторе содержится
массив из 10 номеров первых блоков файла. При размере блока 512 байт
первые 5 Кбайт файла адресуются непосредственно из файлового
дескриптора. Одиннадцатый элемент этого массива содержит адрес блока, в
котором записано еще 128 номеров следующих блоков файла. Таким
образом, доступ к следующим 64 Кбайтам файла производится путем
косвенной адресации из дескриптора через этот блок адресов. Двенадцатый
элемент содержит адрес блока, в котором записано еще 128 номеров блоков,
каждый из которых адресует еще 128 блоков данных файла – это
обеспечивает доступ к следующим 8 Мбайтам путем двухуровневой
косвенной адресации. Наконец, тринадцатый элемент массива в дескрипторе
обеспечивает доступ через трехуровневую косвенную адресацию еще к 2
Гбайтам файла. Структура плана размещения показана на рисунке 7.4.
229
Рисунок 7.4 Размещение файла в файловой системе s5
Другой аспект распределения дисковой памяти – учет свободного
пространства на диске. Как и для учета размещения файлов, здесь
применяются либо карта дискового пространства, либо списки свободных
блоков.
В случае, если размещение файлов отслеживается картой
размещения, на этой же карте могут быть отображены и свободные блоки.
Если же используются различные механизмы отслеживания размещения и
учета свободного пространства, то карта свободной памяти может состоять
из однобитовых элементов со значением 0 – свободен, 1 – занят. Поиск
свободного участка заданного размера сводится к поиску в карте цепочки
нулевых бит заданной длины. Если для системы имеет значение выделение
дисковой памяти непрерывными участками, то состояние дискового
пространства может отображаться в двух или более картах разного
230
"масштаба". Наряду с обязательной картой свободных блоков – самой
"мелкомасштабной" может существовать карта свободных дорожек и карта
свободных цилиндров. Наличие "крупномасштабных" карт позволяет
ускорить поиск больших непрерывных свободных участков.
Списки свободных блоков организуются точно так же, как и списки
блоков, принадлежащих файлу. Дескриптор диска содержит указатель на
начало списка свободных блоков. Последовательная природа списка не
оказывает влияния на эффективность его обработки, так как список
свободных блоков может обрабатываться по дисциплине LIFO – выборка
блока происходит из начала списка, и новый свободный блок также
добавляется в начало списка. Изящный пример работы со свободными
блоками показывает та же ФС s5, пример относится к категории "ленивых
политик", свойственных этой ОС Unix.
В дескрипторе диска (суперблоке) содержится массив из 10 номеров
свободных блоков. Поскольку суперблок в процессе работы хранится в
оперативной памяти, первые 10 свободных блоков могут быть выбраны без
обращений к внешней памяти. Если этот "запас" свободных блоков
исчерпан, то используется последний элемент этого массива, который
ссылается на свободный блок, содержащий еще 10 номеров свободных
блоков. Эти новые номера заново заполняют массив в суперблоке и т.д.
При необходимости включить в список новые свободные блоки их номера
сохраняются в массиве суперблока, пока в нем есть свободные места. Если
же свободные места исчерпаны, номера свободных записываются в
свободный блок на внешней памяти, который включается в список, а
массив в суперблоке освобождается.