Прикладное программирование

Последний подход с некоторыми модификациями используется в традиционных файловых системах ОС UNIX s5 и ufs. Для сокращения объема адресной информации прямой способ адресации сочетается с косвенным. В стандартной на сегодняшний день для UNIX файловой системе ufs используется следующая схема адресации кластеров файла. Для хранения адреса файла выделено 15 полей, каждое из которых состоит из 4 байт. Если размер файла меньше или равен 12 кластерам, то номера этих кластеров непосредственно перечисляются в первых двенадцати полях адреса. Если кластер имеет размер 8 Кбайт (максимальный размер кластера, поддерживаемого в ufs), то таким образом можно адресовать файл размером до 8192x12 98 304 байт.

Если размер файла превышает 12 кластеров, то следующее 13е поле содержит адрес кластера, в котором могут быть расположены номера следующих кластеров файла. Таким образом, 13й элемент адреса используется для косвенной адресации. При размере в 8 Кбайт кластер, на который указывает 13й элемент, может содержать 2048 номеров следующих кластеров данных файла и размер файла может возрасти до 8192 (12+2048)=16 875 520 байт.

Если размер файла превышает 12+2048 = 2060 кластеров, то используется 14е поле, в котором находится номер кластера, содержащего 2048 номеров кластеров, каждый из которых хранит 2048 номеров кластеров данных файла. Здесь применяется уже двойная косвенная адресация. С ее помощью можно адресовать кластеры в файлах, содержащих до 8192 (12+2048+2048²) = 3,4376610¹⁰ байт. И, наконец, если файл включает более 12+2048+2048² = 4 196 364 кластеров, то используется последнее 15е поле для тройной косвенной адресации, что позволяет задать адрес файла, имеющего следующий максимальный размер:

8192 (12+2048+2048²+2048³)=7,040310¹³байт.

Таким образом, файловая система ufs при размере кластера в 8 Кбайт поддерживает файлы, состоящие максимум из 70 триллионов байт данных, хранящихся в 8 миллиардах кластеров. Для задания адресной информации о максимально большом файле требуется: 15 элементов по 4 байта (60 байт) в центральной части адреса плюс 1+(1+2048)+(1+2048+2048²) = 4 198 403 кластера в косвенной части адреса. Несмотря на огромную величину, это число составляет всего около 0,05 % от объема адресуемых данных.

Файловая система ufs поддерживает дисковые кластеры и меньших размеров, при этом максимальный размер файла будет другим. Используемая в более ранних версиях UNIX файловая система s5 имеет аналогичную схему адресации, но она рассчитана на файлы меньших размеров, поэтому в ней используется 13 адресных элементов вместо 15.

Метод перечисления адресов кластеров файла задействован и в файловой системе NTFS, используемой в ОС Windows NT/2000. Здесь он дополнен достаточно естественным приемом, сокращающим объем адресной информации: адресуются не кластеры файла, а непрерывные области, состоящие из смежных кластеров диска. Каждая такая область, называемая отрезком (run) или экстентом (extent), описывается с помощью двух чисел: начального номера кластера и количества кластеров в отрезке. Так как для сокращения времени операции обмена ОС старается разместить файл в последовательных кластерах диска, то в большинстве случаев количество последовательных областей файла будет меньше количества кластеров файла и объем служебной адресной информации в NTFS сокращается по сравнению со схемой адресации файловых систем ufs/s5.

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

5.5 Физическая организация FAT

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

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

Основная копия FAT содержит информацию о размещении файлов и каталогов на диске.

Резервная копия FAT.

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

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

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

Таблица FAT (как основная копия, так и резервная) состоит из массива индексных указателей, количество которых равно количеству кластеров области данных. Между кластерами и индексными указателями имеется взаимно однозначное соответствие - нулевой указатель соответствует нулевому кластеру и т. д.

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

кластер свободен (не используется);

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

последний кластер файла;

дефектный кластер;

резервный кластер.

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

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

Таким образом, создается связный список всех кластеров файла. В начальный период после форматирования файлы будут размещаться в последовательных кластерах области данных, однако после определенного количества удалений файлов кластеры одного файла окажутся в произвольных местах области данных, чередуясь с кластерами других файлов. Размер таблицы FAT и разрядность используемых в ней индексных указателей определяется количеством кластеров в области данных. Для уменьшения потерь из-за фрагментации желательно кластеры делать небольшими, а для сокращения объема адресной информации и повышения скорости обмена наоборот чем больше, тем лучше. При форматировании диска под файловую систему FAT обычно выбирается компромиссное решение и размеры кластеров выбираются из диапазона от 1 до 128 секторов, или от 512 байт до 64 Кбайт. Очевидно, что разрядность индексного указателя должна быть такой, чтобы в нем можно было задать максимальный номер кластера для диска определенного объема. Существует несколько разновидностей FAT, отличающихся разрядностью индексных указателей, которая и используется в качестве условного обозначения: FAT12, FAT16 и FAT32. В файловой системе FAT12 используются 12разрядные указатели, что позволяет поддерживать до 4096 кластеров в области данных диска, в FAT16 16разрядные указатели для 65 536 кластеров и в FAT32 32разрядные более чем для 4 миллиардов кластеров.

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

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

Файловые системы FAT12 и FAT16 оперировали с именами файлов, состоящими из 12 символов по схеме «8.3». В версии FAT16 операционной системы Windows NT был введен новый тип записи каталога «длинное имя», что позволяет использовать имена длиной до 255 символов, причем каждый символ длинного имени хранится в двухбайтном формате Unicode. Имя по схеме «8.3», названное теперь коротким (не нужно путать его с простым именем файла, также называемого иногда коротким), попрежнему хранится в 12байтовом поле имени файла в записи каталога, а длинное имя помещается порциями по 13 символов в одну или несколько записей, следующих непосредственно за основной записью каталога. Каждый символ в формате Unicode кодируется двумя байтами, поэтому 13 символов занимают 26 байт, а оставшиеся 6 отведены под служебную информацию. Таким образом у файла появляются два имени короткое, для совместимости со старыми приложениями, не понимающими длинных имен в Unicode, и длинное, удобное в использовании. Файловая система FAT32 также поддерживает короткие и длинные имена.

Файловые системы FAT12 и FAT16 получили большое распространение благодаря их применению в операционных системах MSDOS и Windows 3.x самых массовых операционных системах первого десятилетия эры персональных компьютеров. По данной причине эти файловые системы поддерживаются сегодня и другими ОС, такими, как UNIX, OS/2, Windows NT/2000 и Windows 95/98. Однако изза постоянно растущих объемов жестких дисков, а также возрастающих требований к надежности эти файловые системы быстро вытесняются как системой FAT32, впервые появившейся в Windows 95 OSR2, так и файловыми системами других типов.

5.6 Физическая организация s5 и ufs

В этом разделе вместо термина «кластер» будет использоваться термин «блок», как это принято в файловых системах UNIX.

Файловые системы s5 (получившие название от System V, родового имени нескольких версий ОС UNIX, разработанных в Bell Labs компании AT&T) и ufs (UNIX File System) используют очень близкую физическую модель. Это не удивительно, так как система ufs является развитием системы s5. Файловая система ufs расширяет возможности s5 по поддержке больших дисков и файлов, а также повышает ее надежность.

Раздел диска, где размещается файловая система, делится на четыре области:

загрузочный блок;

суперблок (superblock) содержит самую общую информацию о файловой системе: размер файловой системы, размер области индексных дескрипторов, число индексных дескрипторов, список свободных блоков и список свободных индексных дескрипторов, а также другую административную информацию;

область индексных дескрипторов (inode list) - содержит набор индексных дескрипторов, перенумерованных в порядке расположения их номеров;

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

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

Индексный дескриптор в s5 имеет размер 64 байта и содержит данные о типе файла, адресную информацию, привилегии доступа к файлу и некоторую другую информацию:

идентификатор владельца файла;

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

права доступа к файлу;

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

число ссылок на данный индексный дескриптор, равный количеству псевдонимов файла;

адресная информация (структура адреса рассмотрена выше в разделе «Физическая организация и адресация файла»);

размер файла в байтах.

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

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

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

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

Определение физического адреса этого файла включает следующие этапы.

1. Прежде всего просматривается корневой каталог с целью поиска первой составляющей символьного имени home. Определяется номер (в данном примере 11) индексного дескриптора каталога, входящего в корневой каталог. Адрес корневого каталога известен системе.

2. Из области индексных дескрипторов считывается дескриптор с номером 11. Начальный адрес дескриптора определяется на основании известных системе номера начального сектора области индексных дескрипторов и размера индексного дескриптора. Из индексного дескриптора 11 определяется физический адрес каталога /home.

3. Просматривается каталог /home с целью поиска второй составляющей символьного имени stud2. Определяется номер индексного дескриптора каталога /home/stud2 (в данном случае 36).

4. Считывается индексный дескриптор 36, определяется физический адрес /home/stud2.

5. Просматривается каталог /home/stud2, определяется номер индексного дескриптора файла labrab.doc (в данном случае 131).

6. Из индексного дескриптора 131 определяются номера блоков данных, а также другие характеристики файла /home/stud2/labrab.doc.

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

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

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

5.7 Физическая организация NTFS

Файловая система NTFS была разработана в качестве основной файловой системы для ОС Windows NT в начале 90х годов с учетом опыта разработки файловых систем FAT и HPFS (основная файловая система для OS/2), а также других существовавших в то время файловых систем.

Основными отличительными свойствами NTFS являются:

поддержка больших файлов и больших дисков объемом до 2⁶⁴ байт;

восстанавливаемость после сбоев и отказов программ и аппаратуры управления дисками за счет ведения журнала (журналирование);

высокая скорость операций, в том числе и для больших дисков;

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

гибкая структура, допускающая развитие за счет добавления новых типов записей и атрибутов файлов с сохранением совместимости с предыдущими версиями ФС;

устойчивость к отказам дисковых накопителей;

поддержка длинных символьных имен;

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

5.7.1 Структура тома NTFS

В отличие от разделов FAT и s5/ufs все пространство тома NTFS представляет собой либо файл, либо часть файла. Основой структуры тома NTFS является главная таблица файлов (Master File Table, MFT), которая содержит по крайней мере одну запись для каждого файла тома, включая одну запись для самой себя (рис 5. 11). Каждая запись MFT имеет фиксированную длину, зависящую от объема диска, 1,2 или 4 Кбайт. Для большинства дисков, используемых сегодня, размер записи MFT равен 2 Кбайт, который мы далее будем считать размером записи по умолчанию.

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

В Windows NT логический раздел принято называть томом. Весь том NTFS состоит из последовательности кластеров, что отличает эту файловую систему от рассмотренных ранее, где на кластеры делилась только область данных. Порядковый номер кластера в томе NTFS называется логическим номером кластера (Logical Cluster Number, LCN). Файл NTFS также состоит из последовательности кластеров, при этом порядковый номер кластера внутри файла называется виртуальным номером кластера (Virtual Cluster Number, VCN).

Базовая единица распределения дискового пространства для файловой системы NTFS непрерывная область кластеров, называемая отрезком. В качестве адреса отрезка NTFS использует логический номер его первого кластера, а также количество кластеров в отрезке k, то есть пара (LCN, k). Таким образом, часть файла, помещенная в отрезок и начинающаяся с виртуального кластера VCN, характеризуется адресом, состоящим из трех чисел: (VCN, LCN, k).

Для хранения номера кластера в NTFS используются 64разрядные указатели, что дает возможность поддерживать тома и файлы размером до 2⁶⁴ кластеров. При размере кластера в 4 Кбайт это позволяет использовать тома и файлы, состоящие из 64 миллиардов килобайт.

Загрузочный блок тома NTFS располагается в начале тома, а его копия в середине тома. Загрузочный блок содержит стандартный блок параметров BIOS, количество блоков в томе, а также начальный логический номер кластера основной копии MFT и зеркальную копию MFT.

Далее располагается первый отрезок MFT, содержащий 16 стандартных, создаваемых при форматировании, записей о системных файлах NTFS. Назначение этих файлов описано в табл. 1.

Таблица 1

№	Имя	Описание
0	$MFT	Сам MFT
1	$MFTmirr	Зеркальная копия первых трех записей MFT
2	$LogFile	Список транзакций, который используется для восстановления файловой системы после сбоев
3	$Volume	Имя тома, версия NTFS и другая информация о томе
4	$AttrDef	Таблица имен, номеров и описаний атрибутов
5	$.	Индекс корневого каталога
6	$Bitmap	Битовая карта кластеров
7	$Boot	Загрузочный сектор раздела
8	$BadClus	Файл плохих кластеров
9	$Quota	Таблица квот
10	$Upcase	Таблица преобразования регистра символов для кодировки Unicode
11 15	Зарезервированы для будущего использования	Не используется

5.7.2 Структура файлов NTFS

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

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

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

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

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

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

Системный набор включает следующие атрибуты:

Attribute List (список атрибутов) список атрибутов, из которых состоит файл; содержит ссылки на номер записи MFT, где расположен каждый атрибут; этот редко используемый атрибут нужен только в том случае, если атрибуты файла не умещаются в основной записи и занимают дополнительные записи MFT;

File Name (имя файла) этот атрибут содержит длинное имя файла в формате Unicode, а также номер входа в таблице MFT для родительского каталога; если этот файл содержится в нескольких каталогах, то у него будет несколько атрибутов типа File Name; этот атрибут всегда должен быть резидентным;

MSDOS Name (имя MSDOS) этот атрибут содержит имя файла в формате 8.3;

Version (версия) атрибут содержит номер последней версии файла;

Security Descriptor (дескриптор безопасности) этот атрибут содержит информацию о защите файла: список прав доступа (Access Control List - ACL) и поле аудита, которое определяет, какого рода операции над этим файлом нужно регистрировать;

Volume Version (версия тома) версия тома, используется только в системных файлах тома;

Volume Name (имя тома) имя тома;

Data (данные) - содержит обычные данные файла;

MFT bitmap (битовая карта MFT) этот атрибут содержит карту использования блоков на томе;

Index Root (корень индекса) корень Вдерева, используемого для поиска файлов в каталоге;

Index Allocation (размещение индекса) нерезидентные части индексного списка Вдерева;

Standard Information (стандартная информация) этот атрибут хранит всю остальную стандартную информацию о файле, которую трудно связать с каким-либо из других атрибутов файла, например, время создания файла, время обновления и другие.

Файлы NTFS в зависимости от способа размещения делятся на небольшие, большие, очень большие и сверхбольшие.

Небольшие файлы (small). Если файл имеет небольшой размер, то он может целиком располагаться внутри одной записи MFT, имеющей, например, размер 2 Кбайт. Небольшие файлы NTFS состоят по крайней мере из следующих атрибутов:

стандартная информация (SI standard information);

имя файла (FN file name);

данные (Data);

дескриптор безопасности (SD security descriptor).

Из-за того что файл может иметь переменное количество атрибутов, а также из-за переменного размера атрибутов нельзя наверняка утверждать, что файл уместится внутри записи. Однако обычно файлы размером менее 1500 байт помещаются внутри записи MFT (размером 2 Кбайт).

Большие файлы (large). Если данные файла не помещаются в одну запись MFT, то этот факт отражается в заголовке атрибута Data, который содержит признак того, что этот атрибут является нерезидентным, то есть находится в отрезках вне таблицы MFT. В этом случае атрибут Data содержит адресную информацию (LCN, VCN, k) каждого отрезка данных.

5.7.3 Каталоги NTFS

Каждый каталог NTFS представляет собой один вход в таблицу MFT, который содержит атрибут Index Root. Индекс содержит список файлов, входящих в каталог. Индексы позволяют сортировать файлы для ускорения поиска, основанного на значении определенного атрибута. Обычно в файловых системах файлы сортируются по имени. NTFS позволяет использовать для сортировки любой атрибут, если он хранится в резидентной форме. Имеются две формы хранения списка файлов.

Небольшие каталоги (small indexes). Если количество файлов в каталоге невелико, то список файлов может быть резидентным в записи в MFT, являющейся каталогом.

Для резидентного хранения списка используется единственный атрибут Index Root. Список файлов содержит значения атрибутов файла. По умолчанию - это имя файла, а также номер записи MTF, содержащей начальную запись файла. Большие каталоги (large indexes). По мере того как каталог растет, список файлов может потребовать нерезидентной формы хранения. Однако начальная часть списка всегда остается резидентной в корневой записи каталога в таблице MFT. Имена файлов резидентной части списка файлов являются узлами так называемого Вдерева (двоичного дерева). Остальные части списка файлов размещаются вне MFT. Для их поиска используется специальный атрибут Index Allocation, представляющий собой адреса отрезков, хранящих остальные части списка файлов каталога. Одни части списков являются листьями дерева, а другие являются промежуточными узлами, то есть содержат наряду с именами файлов атрибут Index Allocation, указывающий на списки файлов более низких уровней.

Узлы двоичного дерева делят весь список файлов на несколько групп. Имя каждого файлаузла является именем последнего файла в соответствующей группе. Считается, что имена файлов сравниваются лексикографически, то есть сначала принимаются во внимание коды первых символов двух сравниваемых имен. При этом имя считается меньшим, если код его первого символа имеет меньшее арифметическое значение. При равенстве кодов первых символов сравниваются коды вторых символов имен и т. д. Например, файл f1.exe, являющийся первым узлом двоичного дерева (поле IR), имеет имя, лексикографически большее имен avia.exe, az.exe,... , emax.exe, образующих первую группу списка имен каталога. Соответственно файл ltr.exe имеет наибольшее имя среди всех имен второй группы, а все файлы с именами, большими ltr.exe, образуют третью и последнюю группу.

Поиск в каталоге уникального имени файла, которым в NTFS является номер основной записи о файле в MFT, по его символьному имени происходит следующим образом. Сначала искомое символьное имя сравнивается с именем первого узла в резидентной части индекса. Если искомое имя меньше, то это означает, что его нужно искать в первой нерезидентной группе, для чего из атрибута Index Allocation извлекается адрес отрезка (VCNj, LCNj, Kj), хранящего имена файлов первой группы. Среди имен этой группы поиск осуществляется прямым перебором имен и сравнением до полного совпадения всех символов искомого имени с хранящимся в каталоге именем. При совпадении из каталога извлекается номер основной записи о файле в MFT и остальные характеристики файла берутся уже оттуда. Если же искомое имя больше имени первого узла резидентной части индекса, то его сравнивают с именем второго узла, и если искомое имя меньше, то описанная процедура применяется ко второй нерезидентной группе имен, и т. д. В результате вместо перебора большого количества имен (в худшем случае всех имен каталога) выполняется сравнение с гораздо меньшим количеством имен узлов и имен в одной из групп каталога. Если одна из групп каталога становится слишком большой, то ее также делят на группы, последние имена каждой новой группы оставляют в исходном нерезидентном атрибуте Index Root, а все остальные имена новых групп переносят в новые нерезидентные атрибуты типа Index Root (на рисунке этот случай не показан). К исходному нерезидентному атрибуту Index Root добавляется атрибут размещения индекса, указывающий на отрезки индекса новых групп. Если теперь при поиске искомого имени в нерезидентной части индекса первого уровня какоелибо сравнение показывает, что искомое имя оказывается меньше, чем одно из хранящихся там имен, то это говорит о том, что в данном атрибуте точного сравнения имени уже быть не может и нужно перейти к подгруппе имен следующего уровня дерева.

Вопросы для самопроверки

151. На какие области разбивает файловая система FAT логический раздел диска?

152. Укажите основную информационную составляющую файловой системы NTFS.

153. Что является основной компонентой файла в NTFS?

154. Для каких целей в NTFS используется информация об узлах B-дерева?

Контрольные вопросы

155. Какому параметру соответствует количество индексных указателей в таблице FAT?

156. Какое максимальное количество кластеров может поддерживать файловая система FAT16?

157. Возможна ли ситуация, при которой можно надежно восстано-вить файл?

158. Как в терминах ОС UNIX принято называть информационную структуру, в которой хранятся характеристики файла?

159. Чем является индексный дескриптор с точки зрения идентифика-ции файла?

160. Может ли файл в ОС UNIX иметь более одного символьного

имени?

161. Какая базовая единица дискового пространства используется для хранения информации в NTFS?

162. Какое количество стандартных записей содержит первый отрезок MFT?

163. Какие поля содержатся в атрибуте файла?

164. На какие типы делят файлы в NTFS в зависимости от способа их размещения?

165. Какая информация содержится в поле Data больших файлов?

166. Какую информацию содержит атрибут Index Root?

167. Какие атрибуты связаны с конкретным файлом в каталожной записи?

5.8 Контроль доступа к файлам

5.8.1 Доступ к файлам как частный случай доступа к разделяемым ресурсам

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

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

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

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

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

Различают два основных подхода к определению прав доступа.

Избирательный доступ имеет место, когда для каждого объекта сам владелец может определить допустимые операции с объектами. Этот подход называется также произвольным (от discretionary - предоставленный на собственное усмотрение) доступом, так как позволяет администратору и владельцам объектов определить права доступа произвольным образом, по их желанию. Между пользователями и группами пользователей в системах с избирательным доступом нет жестких иерархических взаимоотношений, то есть взаимоотношений, которые определены по умолчанию и которые нельзя изменить. Исключение делается только для администратора, по умолчанию наделяемого всеми правами.

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

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

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

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

5.8.2 Механизм контроля доступа

Каждый пользователь и каждая группа пользователей обычно имеют символьное имя, а также уникальный числовой идентификатор. При выполнении процедуры логического входа в систему пользователь сообщает свое символьное имя и пароль, а операционная система определяет соответствующие числовые идентификаторы пользователя и групп, в которые он входит. Все идентификационные данные, в том числе имена и идентификаторы пользователей и групп, пароли пользователей, а также сведения о вхождении пользователя в группы хранятся в специальном файле (файл /etc/passwd в UNIX) или специальной базе данных (в Windows NT).

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

Для файловых объектов этот список может включать следующие операции:

создание файла;

уничтожение файла;

открытие файла;

закрытие файла;

чтение файла;

запись в файл;

дополнение файла;

поиск в файле;

получение атрибутов файла;

установка новых значений атрибутов;

переименование;

выполнение файла;

чтение каталога;

смена владельца;

изменение прав доступа.

Набор файловых операций ОС может состоять из большого количества элементарных операций, а может включать всего несколько укрупненных операций. Приведенный выше список является примером первого подхода, который позволяет весьма тонко управлять правами доступа пользователей, но создает значительную нагрузку на администратора. Пример укрупненного подхода демонстрируют операционные системы семейства UNIX, в которых существуют всего три операции с файлами и каталогами: читать (read, r), писать (write, w) и выполнить (execute, x). Хотя в UNIX для операций используется всего три названия, в действительности им соответствует гораздо больше операций. Например, содержание операции выполнить зависит от того, к какому объекту она применяется. Если операция выполнить файл интуитивно понятна, то операция выполнить каталог интерпретируется как поиск в каталоге определенной записи. Поэтому администратор UNIX, по сути, располагает большим списком операций, чем это кажется на первый взгляд.

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

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

Практически во всех операционных системах матрица прав доступа хранится «по частям», то есть для каждого файла или каталога создается так называемый список управления доступом (Access Control List, ACL), в котором описываются права на выполнение операций пользователей и групп пользователей по отношению к этому файлу или каталогу. Список управления доступа является частью характеристик файла или каталога и хранится на диске в соответствующей области, например в индексном дескрипторе inode файловой системы ufs. He все файловые системы поддерживают списки управления доступом, например, его не поддерживает файловая система FAT, так как она разрабатывалась для однопользовательской однопрограммной операционной системы MSDOS, для которой задача защиты от несанкционированного доступа не актуальна.

Обобщенно формат списка управления доступом можно представить в виде набора идентификаторов пользователей и групп пользователей, в котором для каждого идентификатора указывается набор разрешенных операций над объектом. Говорят, что список ACL состоит из элементов управления доступом (Access Control Element, АСЕ), при этом каждый элемент соответствует одному идентификатору. Список ACL с добавленным к нему идентификатором владельца называют характеристиками безопасности.

В приведенном на рисунке примере процесс, который выступает от имени пользователя с идентификатором 3 и групп с идентификаторами 14, 52 и 72, пытается выполнить операцию записи (W) в файл. Файлом владеет пользователь с идентификатором 17. Операционная система, получив запрос на запись, находит характеристики безопасности файла (на диске или в буферной системной области) и последовательно сравнивает все идентификаторы процесса с идентификатором владельца файла и идентификаторами пользователей и групп в элементах АСЕ. В данном примере один из идентификаторов группы, от имени которой выступает процесс, а именно 52, совпадает с идентификатором одного из элементов АСЕ. Так как пользователю с идентификатором 52 разрешена операция чтения (признак W имеется в наборе операций этого элемента), то ОС разрешает процессу выполнение операции.

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

5.8.3 Организация контроля доступа в ОС UNIX

В ОС UNIX права доступа к файлу или каталогу определяются для трех субъектов:

владельца файла (идентификатор User ID, UID);

членов группы, к которой принадлежит владелец (Group ID, GID);

всех остальных пользователей системы.

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

User Group Other

rwx r-х r--

Здесь r, w и х обозначают операции чтения, записи и выполнения соответственно. Именно в таком виде выводит информацию о правах доступа к файлам команда просмотра содержимого каталога ls la. Суперпользователю UNIX все виды доступа позволены всегда, поэтому его идентификатор (он имеет значение 0) не фигурирует в списках управления доступом.

С каждым процессом UNIX связаны два идентификатора: пользователя, от имени которого был создан этот процесс, и группы, к которой принадлежит данный пользователь. Эти идентификаторы носят название реальных идентификаторов пользователя: Real User ID, RUID и реальных идентификаторов группы: Real Group ID, RGID. Однако при проверке прав доступа к файлу используются не эти идентификаторы, а так называемые эффективные идентификаторы пользователя: Effective User ID, EUID и эффективные идентификаторы группы: Effective Group ID, EGID.

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

В ОС UNIX случаи, когда процесс выполняет системный вызов ехес запуска приложения, хранящегося в некотором файле, связаны с заменой процессом исполняемого кода. В рамках данного процесса начинает выполняться новый код, и если в характеристиках безопасности этого файла указаны признаки разрешения смены идентификаторов пользователя и группы, то происходит смена эффективных идентификаторов процесса. Файл имеет два признака разрешения смены идентификатора - Set User ID on execution (SUID) и Set Group ID on execution (SGID), которые разрешают смену идентификаторов пользователя и группы при выполнении данного файла.

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

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

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

Вопросы для самопроверки

168. Файлы и принтеры - это единственный разделяемый ресурс, до-ступ к которым контролируется операционной системой?

169. Каким образом пользователи осуществляют доступ к разделяемым ресурсам?

170. Одинаковы ли допустимые наборы операций для различных разделяемых ресурсов?

171. Какие основные подходы к определению прав доступа Вам известны?

172. В чем отличие реальных и эффективных идентификаторов пользователей и групп пользователей, используемых в ОС UNIX?

Контрольные вопросы

173. Является ли владелец разделяемого ресурса единственным субъектом, который может выполнять с объектом любые допустимые операции?

174. Существует ли система жестких иерархических отношений при избирательном методе доступа?

175. Существует ли система жестких иерархических отношений при мандатном методе доступа?

176. Какие операции с файлами и каталогами определены в ОС Unix?

177. Какое количество уровней работы с операциями над файлами реализовано в Windows NT?

178. Как называют список, связанный с файлами и каталогами, описывающий права пользователей и групп пользователей на выполнение операций с файлом или каталогом?

179. Укажите файловую систему, поддерживаемую ОС Windows NT, в которой список управления доступом не используется.

180. Для каких трех субъектов в ОС UNIX определяют права доступа к файлу?

181. Какое число признаков включает характеристика безопасности файлов в ОС UNIX?

182. Может ли модель файла, как универсальная модель разделяемого ресурса в ОС UNIX, применяться для контроля доступа к другим ресурсам, например терминалам, принтерам, разделяемым сегментам памяти?

5.8.4 Организация контроля доступа в ОС Windows NT

Система управления доступом в ОС Windows NT отличается высокой степенью гибкости, которая достигается за счет большого разнообразия субъектов и объектов доступа, а также детализации операций доступа.

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

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

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

...