Раздел 3 машинно-независимые свойства операционных систем

1. Работа с файлами

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

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

Файловая система (ФС) – это часть операционной системы, включающая в себя:

1. совокупность всех файлов на диске;

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

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

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

Типы файлов

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

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

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

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

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

Иерархическая структура файловой системы

В древовидной структуре каждый файл является листом. Каталог самого верхнего уровня называется корневым каталогом или корнем (root).

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

Граф, описывающий иерархию каталогов, может быть деревом или сетью. Каталоги образуют дерево, если файлу разрешено входить сразу в несколько каталогов (рисунок 3.1, б), и сеть – если файл может входить сразу в несколько каталогов (рисунок 3.1, в).

Рисунок 3.1, а – Иерархия файловой системы с одноуровневой организацией.

Рисунок 3.1, б - Иерархия файловой системы, образующая дерево.

Рисунок 3.1, в - Иерархия файловой системы, образующая сеть.

Логическая организация файловой системы

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

Файловая система может использовать два способа доступа к логическим записям:

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

Рисунок 3.2, а – Последовательный или неиндексированный способ логической организации файла.

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

Рисунок 3.2, б - Прямой или индексированный способ логической организации файла.

Физическая организация файловой системы

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

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

На каждой стороне каждой пластины размечены тонкие концентрические кольца – дорожки (traks), на которой сохраняются данные. Количество их зависит от типа диска. Нумерация дорожек начинается с 0 от внешнего края к центру. При вращении диска считывающая головка считывает или записывает двоичные данные на магнитную дорожку.

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

Головки перемещаются над поверхностью диска дискретными шагами (каждый шаг соответствует сдвигу на одну дорожку). Запись на диск осуществляется благодаря способности головки менять магнитные свойства дорожек.

Рисунок 3.3 – Схема устройства жесткого диска.

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

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

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

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

Физическая организация файла – это способ размещения файла на диске.

Основными критериями эффективности физической организации файлов являются:

1. скорость доступа к данным;

2. объем адресной информации файла;

3. степень фрагментированности дискового пространства;

4. максимально возможный размер файла.

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

Рисунок 3.4, а – Физическая организация файла при непрерывном размещении.

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

Рисунок 3.5, б – Физическая организация файла при связанном списке кластеров.

Связанный список индексов (применяется в FAT) показано на рисунке 2.19, в. Это некоторая модификация предыдущих способов. С каждым кластером диска связывается некоторый элемент – индекс. Индексы располагаются в отдельной области диска – MS-DOS это таблица FAT (File Allocation Table), занимающая один кластер. Когда память свободна, все индексы занимают нулевое значение. Достоинства: минимальный объем адресной информации, отсутствие фрагментации, отсутствие проблем при изменении размера. Преимущества: для доступа к произвольному кластеру файла достаточно только прочитать секторы диска, содержащие таблицу индексов, отсчитать нужное количество кластеров по цепочке и определить номер нужного кластера; данные заполняются кластером целиком.

Рисунок 3.5, в – Физическая организация файла при связанном списке индексов.

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

Рисунок 3.5, г – Физическая организация файла при перечислении номеров кластеров.

В стандартной на сегодняшний день для UNIX файловой системе ufs использу­ется следующая схема адресации кластеров файла. Для хранения адреса файла выделено 15 полей, каждое из которых состоит из 4 байт (показано на рисунке 3.6 ). Если размер файла меньше или равен 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,43766 x l0¹⁰ байт.

И наконец, если файл включает более 12+2048+2048² = 4 196 364 кластеров, то используется последнее 15-е поле для тройной косвенной адресации, что позво­ляет задать адрес файла, имеющего следующий максимальный размер:

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

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

Метод перечисления адресов кластеров файла задействован и в файловой системе NTFS, используемой в ОС Windows NT/2000.

Рисунок 3.6 – Схема адресации файловой системы ufs.

Файловые операции, контроль доступа к файлам

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

При любых операциях над файлами ОС необходимо выполнить следующие универсальные действия:

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

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

3. на основании характеристик файла проверить права пользователя на выполнение запрошенной операции;

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

ОС может выполнять последовательность действий над файлами двумя способами, представленными на 3.7, а и б:

1. для каждой операции выполняются как универсальные так и уникальные действия. Эта схема называется схемой без запоминания состояния операций (stateless). Такой способ более устойчив к сбоям в работе системы. Применяется в распределенных системах;

Рисунок 3.7, а – Способ выполнения файловых операций без запоминания состояния операции (stateless).

2. все универсальные действия выполняются в начале и в конце последовательности операции, а для каждой промежуточной операции выполняются только уникальные действия. Это более экономичный и быстрый способ.

Рисунок 3.7, б – Второй способ выполнения файловых операций.

Файлы – это частный вид разделяемых ресурсов, доступ к которым ОС должна контролировать.

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

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

У каждого объекта доступа есть владелец. Владельцем может быть как отдельный пользователь, так группа пользователей.

Существуют два основных подхода к определению прав доступа:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В общем случае права доступа могут быть описаны матрицей прав доступа (показана на рисунке 3.8), называемой списком управления доступом (Access Control List, ACL).

Имена пользователей			Имена файла
		Modem.txt	Win.exe	Class.dbf	Unix.ppt
	Kira	Читать	Выполнять	–	Выполнять
	Genua	Читать	Выполнять	–	Выполнять Читать
	Nataly	Читать	–	–	Выполнять Читать
	Viktor	Читать писать	–	Создать	–

Рисунок 3.8 – Матрица прав доступа.

Формат списка управления доступом можно представить в виде набора идентификаторов пользователей и групп пользователей, в котором для каждого идентификатора указывается набор разрешенных операций над объектом. Значит, список ACL состоит из элементов управления доступом (Access Control Elements, ACE), при этом каждый элемент состоит из одного идентификатора.

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

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

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

При установ­ке блокировки можно задать два режима работы системного вызова:

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

2. асинхронный вызов и с немедленным возвратом в такой си­туации с сообщением отрицательного результата.

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

В UNIX существуют два режима действия блокировок:

1. консультативный (ad­visory);

2. обязательный (mandatory).

Примеры файловых систем

Файловая система FAT (представлена на рисунке 3.9) поддерживает всего два типа файлов: обычный файл и каталог.

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

1. загрузочный сектор;

2. основная копия FAT;

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

4. корневой каталог;

5. область данных.

Рисунок 3.9 – Физическая структура файловой системы FAT.

Файловые системы FAT12 и FAT16 получили большое распространение после их применении в ОС MS-DOS и Windows 3.x. на сегодняшний день эти файловые системы поддерживаются и другими ОС, например UNIX, OS/2, Windows NT и Windows 95/98.

Файловая система NTFS (представлена на рисунке 3.10) была разработана в качестве основной файловой системы для ОС Windows NT в начале 90-х годов.

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

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

2. восстанавливаемость после сбоев и отказов программ и аппаратуры управле­ния дисками;

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

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

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

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

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

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

Рисунок 3.10 – Структура тома NTFS