Операционная система UNIX

3. Операционная система UNIX.

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

В середине 60-х годов в Bell Laboratories фирмы AT&T проводились исследования и разработка одной из первых операционных систем в современном ее понимании - операционной системы Multix. Эта операционная система обладала свойствами операционной системы разделения времени, многопользовательской системы, а также в этой системе были предложены основные решения по организации файловых систем, в частности, была предложена иерархическая древообразная файловая система. От этой разработки через некоторое время получила начало операционная система UNIX. Одна из историй разработки этой системы говорит о том, что на фирме был ненужный компьютер PDP-7 с очень малоразвитым программным обеспечением и требовалась машина, которая позволяла бы организовывать комфортную работу пользователя, в частности, обработку текстовой информации. Известная группа людей - это Кен Томпсон и Деннис Ритчи, занялись разработкой новой операционной системы. Другой вариант этой истории гласит о том, что якобы они занимались реализацией некоторой игры и те средства, которые были им доступны, оказались неудобны - тогда они решили поиграть с этой машиной. В результате появилась операционная система UNIX.

Особенностью этой системы являлось то, что она была первой системной программой, которая была написана с использованием языка, отличного от машинного языка (ассемблера). Для целей написания этого системного программного обеспечения, в частности, операционной системы UNIX, также проводились работы, которые начинались от языка BCPL. Из него был образован язык B, который оперировал с машинными словами. Далее абстракция машинных слов - BN, и наконец язык Си. С 1983 года операционная система UNIX (ее первоначальная версия) была переписана на язык Си, и получилось, что около 90% операционной системы было написано на языке высокого уровня, не зависящем от архитектуры машины, а 10% этой системы были написаны на ассемблере. В эти десять процентов вошли наиболее критичные по времени части операционной системы.

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

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

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

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

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

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

Начнем рассмотрение конкретных свойств операционной системы.

Файловая система. Организация файлов. Работа с файлами.

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

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

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

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

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

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

В любой системе принято разбиение пространства ВЗУ на некоторые области данных, которые называются блоками. Размер логического блока является фиксированным атрибутом операционной системы. В операционной системе UNIX размеры блока определяет некоторый параметр, который может меняться в зависимости от версии системы. Для определенности будем говорить, что логический блок ВЗУ равен 512 байт.

Представим адресное пространство СВЗУ в виде последовательности блоков. Нулевой блок СВЗУ - это блок начальной загрузки, или блок, в котором находится программный загрузчик. Размещение этого блока в нулевом блоке СВЗУ определяется аппаратно, потому что аппаратный загрузчик обращается всегда именно к нулевому блоку. Это последний компонент файловой системы, который зависит от аппаратуры.

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

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

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

1.   Поле, определяющее тип файла (каталог или нет).

2.   Поле кода защиты.

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

4.   Длина файла в байтах.

5.   Статистика: поля, характеризующие дату и время создания и т.п.

6.   Поле адресации блоков файлов.

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

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

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

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

Список (массив) свободных блоков файлов состоит из пятидесяти элементов и занимает 100 байтов. В буфере, состоящем из пятидесяти элементов, записаны номера свободных блоков пространства блоков памяти. Эти номера записаны со второго элемента по сорок девятый. Первый элемент массива содержит номер последней записи в этом массиве. Нулевой элемент этого списка содержит ссылку на блок пространства блоков файлов, в котором этот список продолжен, и т.д.

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

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

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

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

Лекция №8

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

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

1.   Поле, определяющее тип файла (каталог или нет).

2.   Поле кода защиты.

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

4.   Длина файла в байтах.

5.   Статистика: поля, характеризующие дату и время создания и т.п.

6.   Поле адресации блоков файлов.

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

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

В том случае, если файл еще больше, то используется двенадцатый элемент поля адресации. Он содержит номер блока, в котором содержится 128 записей о номерах блоков, содержащих по 128 номеров блоков файловой системы, т. е. здесь используется двойная косвенность. Если файл еще больше, то используется тринадцатый элемент и используется тройная косвенность (аналогично двойной, но добавляется еще один уровень). Предельный размер файла (при размере блока 512) будет равен (128 + 128² + 128³) * 512 байт = 1Гб + 8Мб + 64Кб > 1Гб.

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

 

Блоки файлов. Размер пространства блоков файлов определен однозначным образом за счет информации в суперблоке.

 

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

Итак, мы с вами рассмотрели структуру файловой системы и ее организацию на системном устройстве. Как любая системная конструкция, структура файловой системы и связанные с ней алгоритмы работы просты настолько, чтобы при работе с ними накладные расходы не выходили за пределы разумного. Файловая система UNIX-а при реальной работе заведомо оптимальнее файловой системы Windows NT (сравните даты разработок!!!), за счет простоты и оптимизации, которая встречается на каждом шагу.

Каталоги

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

В каталоге А содержаться файлы В, С и D, несмотря на то, что файлы В и С могут быть как файлами, так каталогами, а файл D является каталогом.

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

При создании каталога в нем всегда создаются две записи: запись на специальный файл с именем «.» (точка), с которым ассоциирован индексный дескриптор самого каталога, и файл «..» (две точки), с которым ассоциируется индексный дескриптор (ИД) родительского каталога. Для нашего примера каталог А имеет, например, ИД с номером 7, а каталог D имеет ИД с номером 5. Файл F имеет ИД №10, файл G имеет ИД №101. В этом случае файл-каталог D будет иметь следующее содержимое:

Имя	№ИД
«.»		5	Первая запись - запись на самого себя.
«..»		7	Вторая запись - на родителя (каталог А).
«F»		10	Далее перечислены файлы, которые находятся в этом каталоге.
«G»		101	Вот таким будет содержимое каталога D.

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

Теперь схематически рассмотрим, как могут использоваться полные имена и структура каталогов. В системе, в каждый момент времени работы пользователя определен текущий каталог, то есть каталог и весь путь от корня, связанный с этим каталогом, который по умолчанию подставляется ко всем именам файлов, не начинающихся с символа «/». Если текущий каталог D, то можно говорить просто о файлах F и G, а если надо добраться до файла В, то необходимо использовать полное имя или специальный файл «..», т.е., в данном случае, конструкцию «../В». Мы ссылаемся на файл «..» - это означает, что нужно прочесть ИД родителя и по нему добраться до содержимого каталога А. Затем в файле-каталоге А надо выбрать строку с именем В и определить ИД файла В, а затем произвести открытие файла. Вся эта операция довольно трудоемка, однако учитывая то, что файлы открываются не часто, это не будет сказываться на скорости работы системы.

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

Специальные файлы устройств

Мы уже знаем два типа файлов: файлы-каталоги и рабочие файлы, в которых хранятся данные. Есть третья разновидность - файлы устройств. Эта разновидность характеризуется типом, указанным в ИД. Содержимого у файлов устройств нет, а есть только ИД и имя. В ИД указывается информация о том, какой тип устройства ассоциирован с этим файлом: байт-ориентированное устройство или блок-ориентированное устройство. Байт-ориентированное устройство - это то устройство, обмен с которым осуществляется по одному байту (например, клавиатура). Блок-ориентированное устройство - это устройство, с которым обмен может осуществляться блоками.

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

Организация обмена данными с файлами

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

1.   open - Открытие имеющегося файла. Одним из параметров этой функции является строка с именем файла, а возвращает она некоторое число, которое называется дескриптором файла. В теле процесса пользователя, а также в данных, ассоциированных с этим процессом, размещается (кроме кода и данных, разумеется) некоторая служебная информация, в частности, таблица файловых дескрипторов. Она, как и все таблицы в системе UNIX, позиционная, т.е. номер дескриптора соответствует номеру записи в этой таблице. С файловым дескриптором (ФД) ассоциировано имя файла и все необходимые атрибуты для работы с ним. Номера ФД уникальны в пределах одного процесса. Есть аналогичная функция create - функция открытия нового файла.