1.1 ИСТОРИЯ

В 1965 году фирма Bell Telephone Laboratories, объединив свои усилия с компанией General Electric и проектом MAC Массачусетского технологического института, приступили к разработке новой операционной системы, получившей название Multics [Organick 72]. Перед системой Multics были поставлены задачи - обеспечить одновременный доступ к ресурсам ЭВМ большого количества пользователей, обеспечить достаточную скорость вычислений и хранение данных и дать возможность пользователям в случае необходимости совместно использовать данные. Многие разработчики, впоследствии принявшие участие в создании ранних редакций системы UNIX, участвовали в работе над системой Multics в фирме Bell Laboratories. Хотя первая версия системы Multics и была запущена в 1969 году на ЭВМ GE 645, она не обеспечивала выполнение главных вычислительных задач, для решения которых она предназначалась, и не было даже ясно, когда цели разработки будут достигнуты. Поэтому фирма Bell Laboratories прекратила свое участие в проекте.

По окончании работы над проектом Multics сотрудники Исследовательского центра по информатике фирмы Bell Laboratories остались без "достаточно интерактивного вычислительного средства" [Ritchie 84a]. Пытаясь усовершенствовать среду программирования, Кен Томпсон, Дэннис Ричи и другие набросали на бумаге проект файловой системы, получивший позднее дальнейшее развитие в ранней версии файловой системы UNIX. Томпсоном были написаны программы, имитирующие поведение предложенной файловой системы в режиме подкачки данных по запросу, им было даже создано простейшее ядро операционной системы для ЭВМ GE 645. В то же время он написал на Фортране игровую программу "Space Travel" ("Космическое путешествие") для системы GECOS (Honeywell 635), но программа не смогла удовлетворить пользователей, поскольку управлять "космическим кораблем" оказалось сложно, кроме того, при загрузке программа занимала много места. Позже Томпсон обнаружил малоиспользуемый компьютер PDP-7, оснащенный хорошим графическим дисплеем и имеющий дешевое машинное время. Создавая программу "Космическое путешествие" для PDP-7, Томпсон получил возможность изучить машину, однако условия разработки программ потребовали использования кросс-ассемблера для трансляции программы на машине с системой GECOS и использования перфоленты для ввода в PDP-7. Для того, чтобы улучшить условия разработки, Томпсон и Ричи выполнили на PDP-7 свой проект системы, включивший первую версию файловой системы UNIX, подсистему управления процессами и небольшой набор утилит. В конце концов, новая система больше не нуждалась в поддержке со стороны системы GECOS в качестве операционной среды разработки и могла поддерживать себя сама. Новая система получила название UNIX, по сходству с Multics его придумал еще один сотрудник Исследовательского центра по информатике Брайан Керниган.

Несмотря на то, что эта ранняя версия системы UNIX уже была многообещающей, она не могла реализовать свой потенциал до тех пор, пока не получила применение в реальном проекте. Так, для того, чтобы обеспечить функционирование системы обработки текстов для патентного отдела фирмы Bell Laboratories, в 1971 году система UNIX была перенесена на ЭВМ PDP-11. Система отличалась небольшим объемом: 16 Кбайт для системы, 8 Кбайт для программ пользователей, обслуживала диск объемом 512 Кбайт и отводила под каждый файл не более 64 Кбайт. После своего первого успеха Томпсон собрался было написать для новой системы транслятор с Фортрана, но вместо этого занялся языком Би (B), предшественником которого явился язык BCPL [Richards 69]. Би был интерпретируемым языком со всеми недостатками, присущими подобным языкам, поэтому Ричи переделал его в новую разновидность, получившую название Си (C) и разрешающую генерировать машинный код, объявлять типы данных и определять структуру данных. В 1973 году система была написана заново на Си, это был шаг, неслыханный для того времени, но имевший огромный резонанс среди сторонних пользователей. Количество машин фирмы Bell Laboratories, на которых была инсталлирована система, возросло до 25, в результате чего была создана группа по системному сопровождению UNIX внутри фирмы.

В то время корпорация AT&T не могла заниматься продажей компьютерных продуктов в связи с соответствующим соглашением, подписанным ею с федеральным правительством в 1956 году, и распространяла систему UNIX среди университетов, которым она была нужна в учебных целях. Следуя букве соглашения, корпорация AT&T не рекламировала, не продавала и не сопровождала систему. Несмотря на это, популярность системы устойчиво росла. В 1974 году Томпсон и Ричи опубликовали статью, описывающую систему UNIX, в журнале Communications of the ACM [Thompson 74], что дало еще один импульс к распространению системы. К 1977 году количество машин, на которых функционировала система UNIX, увеличилось до 500, при чем 125 из них работали в университетах. Система UNIX завоевала популярность среди телефонных компаний, поскольку обеспечивала хорошие условия для разработки программ, обслуживала работу в сети в режиме диалога и работу в реальном масштабе времени (с помощью системы MERT [Lycklama 78a]). Помимо университетов, лицензии на систему UNIX были переданы коммерческим организациям. В 1977 году корпорация Interactive Systems стала первой организацией, получившей права на перепродажу системы UNIX с надбавкой к цене за дополнительные услуги (*), которые заключались в адаптации системы к функционированию в автоматизированных системах управления учрежденческой деятельностью. 1977 год также был отмечен "переносом" системы UNIX на машину, отличную от PDP (благодаря чему стал возможен запуск системы на другой машине без изменений или с небольшими изменениями), а именно на Interdata 8/32.

С ростом популярности микропроцессоров другие компании стали переносить систему UNIX на новые машины, однако ее простота и ясность побудили многих разработчиков к самостоятельному развитию системы, в результате чего было создано несколько вариантов базисной системы. За период между 1977 и 1982 годом фирма Bell Laboratories объединила несколько вариантов, разработанных в корпорации AT&T, в один, получивший коммерческое название UNIX версия III. В дальнейшем фирма Bell Laboratories добавила в версию III несколько новых особенностей, назвав новый продукт UNIX версия V (**), и эта версия стала официально распространяться корпорацией AT&T с января 1983 года. В то же время сотрудники Калифорнийского университета в Бэркли разработали вариант системы UNIX, получивший название BSD 4.3 для машин серии VAX и отличающийся некоторыми новыми, интересными особенностями. Основное внимание в этой книге концентрируется на описании системы UNIX версии V, однако время от времени мы будем касаться и особенностей системы BSD.

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

Система написана на языке высокого уровня, благодаря чему ее легко читать, понимать, изменять и переносить на другие машины. По оценкам, сделанным Ричи, первый вариант системы на Си имел на 20-40 % больший объем и работал медленнее по сравнению с вариантом на ассемблере, однако преимущества использования языка высокого уровня намного перевешивают недостатки (см. [Ritchie 78b], стр. 1965). Наличие довольно простого пользовательского интерфейса, в котором имеется возможность предоставлять все необходимые пользователю услуги. Наличие элементарных средств, позволяющих создавать сложные программы из более простых. Наличие иерархической файловой системы, легкой в сопровождении и эффективной в работе. Обеспечение согласования форматов в файлах, работа с последовательным потоком байтов, благодаря чему облегчается чтение прикладных программ. Наличие простого, последовательного интерфейса с периферийными устройствами. Система является многопользовательской, многозадачной; каждый пользователь может одновременно выполнять несколько процессов.

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

Простота и последовательность вообще отличают систему UNIX и объясняют большинство из вышеприведенных доводов в ее пользу.

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

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

(**) А что же версия IV? Модификация внутреннего варианта системы получила название "версия V".

1.2 СТРУКТУРА СИСТЕМЫ

1.2 СТРУКТУРА СИСТЕМЫ

На Рисунке 1.1 изображена архитектура верхнего уровня системы UNIX. Технические средства, показанные в центре диаграммы, выполняют функции, обеспечивающие функционирование операционной системы и перечисленные в разделе 1.5. Операционная система взаимодействует с аппаратурой непосредственно (***), обеспечивая обслуживание программ и их независимость от деталей аппаратной конфигурации. Если представить систему состоящей из пластов, в ней можно выделить системное ядро, изолированное от пользовательских

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

Файловая система UNIX характеризуется:

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

1.3.2 Среда выполнения процессов

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

Например, процесс, выполняющийся в программе, приведенной на Рисунке 1.4, запускает операцию fork, чтобы породить новый процесс. Новый процесс, именуемый порожденным процессом, получает значение кода завершения операции fork, равное 0, и активизирует операцию execl, которая выполняет программу copy (Рисунок 1.3). Операция execl загружает файл "copy", который предположительно находится в текущем каталоге, в адресное пространство порожденного процесса и запускает программу с параметрами, полученными от пользователя. В случае успешного выполнения операции execl управление в вызвавший ее процесс не возвращается, поскольку процесс выполняется в новом адресном пространстве (подробнее об этом в главе 7). Тем временем, процесс, запустивший операцию fork (родительский процесс), получает ненулевое значение кода завершения операции, вызывает операцию wait, которая приостанавливает его выполнение до тех пор, пока не закончится выполнение программы copy, и завершается (каждая программа имеет выход в конце главной процедуры, после которой располагаются программы стандартных библиотек Си, подключаемые в процессе компиляции). Например, если исполняемая программа называется run, пользователь запускает ее следующим образом:

run oldfile newfile Процесс выполняет копирование файла с именем "oldfile" в файл с именем "newfile" и выводит сообщение. Хотя данная программа мало что добавила к программе "copy", в ней появились четыре основных обращения к операционной системе, управляющие выполнением процессов: fork, exec, wait и exit.

1.3.3 Элементы конструкционных блоков

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

выводит список всех файлов текущего каталога на устройство (в файл) стандартного вывода, а команда

ls > output

переназначает выводной поток со стандартного вывода в файл "output" в текущем каталоге, используя вышеупомянутый системный вызов creat. Подобным же образом, команда

mail mjb < letter

открывает (с помощью системного вызова open) файл "letter" в качестве файла стандартного ввода и пересылает его содержимое пользователю с именем "mjb". Процессы могут переназначать одновременно и ввод, и вывод, как, например, в командной строке:

nroff -mm < doc1 > doc1.out 2> errors

где программа форматирования nroff читает вводной файл doc1, в качестве файла стандартного вывода задает файл doc1.out и выводит сообщения об ошибках в файл errors ("2>" означает переназначение вывода, предназначавшегося для файла с дескриптором 2, который соответствует стандартному файлу ошибок). Программы ls, mail и nroff не знают, какие файлы выбраны в качестве файлов стандартного ввода, стандартного вывода и записи сообщений об ошибках; командный процессор shell сам распознает символы "<", ">" и "2>" и назначает в соответствии с их указанием файлы для стандартного ввода, стандартного вывода и записи сообщений об ошибках непосредственно перед запуском процессов.

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

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

grep main a.c b.c c.c

где "main" - подстрока, поиск которой производится в файлах a.c, b.c и c.c с выдачей в файл стандартного вывода тех строк, в которых она содержится. Содержимое выводного файла может быть следующим:

a.c: main(argc,argv) c.c: /* here is the main loop in the program */ c.c: main()

Программа wc с необязательным параметром -l подсчитывает число строк в файле стандартного ввода. Командная строка

grep main a.c b.c c.c | wc -l

вызовет подсчет числа строк в указанных файлах, где будет обнаружена подстрока "main"; выводной поток команды grep поступит непосредственно на вход команды wc. Для предыдущего примера результат будет такой:

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

(****) Каталог "/bin" содержит большинство необходимых команд и обычно входит в число каталогов, в которых ведет поиск командный процессор shell.

1.3 ОБЗОР С ТОЧКИ ЗРЕНИЯ ПОЛЬЗОВАТЕЛЯ

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

1.4 ФУНКЦИИ ОПЕРАЦИОННОЙ СИСТЕМЫ

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

Управление выполнением процессов посредством их создания, завершения или приостановки и организации взаимодействия между ними. Планирование очередности предоставления выполняющимся процессам времени центрального процессора (диспетчеризация). Процессы работают с центральным процессором в режиме разделения времени: центральный процессор (*****) выполняет процесс, по завершении отсчитываемого ядром кванта времени процесс приостанавливается и ядро активизирует выполнение другого процесса. Позднее ядро запускает приостановленный процесс. Выделение выполняемому процессу оперативной памяти. Ядро операционной системы дает процессам возможность совместно использовать участки адресного пространства на определенных условиях, защищая при этом адресное пространство, выделенное процессу, от вмешательства извне. Если системе требуется свободная память, ядро освобождает память, временно выгружая процесс на внешние запоминающие устройства, которые называют устройствами выгрузки. Если ядро выгружает процессы на устройства выгрузки целиком, такая реализация системы UNIX называется системой со свопингом (подкачкой); если же на устройство выгрузки выводятся страницы памяти, такая система называется системой с замещением страниц. Выделение внешней памяти с целью обеспечения эффективного хранения информации и выборка данных пользователя. Именно в процессе реализации этой функции создается файловая система. Ядро выделяет внешнюю память под пользовательские файлы, мобилизует неиспользуемую память, структурирует файловую систему в форме, доступной для понимания, и защищает пользовательские файлы от несанкционированного доступа.

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

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

(*****) В главе 12 рассматриваются многопроцессорные системы; до того речь будет идти об однопроцессорной модели.

1.5.1 Прерывания и особые ситуации

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

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

1.5.2 Уровни прерывания процессора

1.5.2 Уровни прерывания процессора

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

1.5.3 Распределение памяти

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

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

1.5 ПРЕДПОЛАГАЕМАЯ АППАРАТНАЯ СРЕДА

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

Основные различия между этими двумя режимами:

В режиме задачи процессы имеют доступ только к своим собственным инструкциям и данным, но не к инструкциям и данным ядра (либо других процессов). Однако в режиме ядра процессам уже доступны адресные пространства ядра и пользователей. Например, виртуальное адресное пространство процесса может быть поделено на адреса, доступные только в режиме ядра, и на адреса, доступные в любом режиме. Некоторые машинные команды являются привилегированными и вызывают возникновение ошибок при попытке их использования в режиме задачи. Например, в машинном языке может быть команда, управляющая регистром состояния процессора; процессам, выполняющимся в режиме задачи, она недоступна. Процессы A B C D Я . . Я . З З .

Режим ядра

Режим задачи

1.6 ВЫВОДЫ

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

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

2.1 АРХИТЕКТУРА ОПЕРАЦИОННОЙ СИСТЕМЫ UNIХ

Как уже ранее было замечено (см. [Christian 83], стр.239), в системе UNIX создается иллюзия того, что файловая система имеет "места" и что у процессов есть "жизнь". Обе сущности, файлы и процессы, являются центральными понятиями модели операционной системы UNIX. На Рисунке 2.1 представлена блок-схема ядра системы, отражающая состав модулей, из которых состоит ядро, и их взаимосвязи друг с другом. В частности, на ней слева изображена файловая подсистема, а справа подсистема управления процессами, две главные компоненты ядра. Эта схема дает логическое представление о ядре, хотя в действительности в структуре ядра имеются отклонения от модели, поскольку отдельные модули испытывают внутреннее воздействие со стороны других модулей.

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

На рисунке совокупность обращений к операционной системе разделена на те обращения, которые взаимодействуют с подсистемой управления файлами, и те, которые взаимодействуют с подсистемой управления процессами. Файловая подсистема управляет файлами, размещает записи файлов, управляет свободным пространством, доступом к файлам и поиском данных для пользователей. Процессы взаимодействуют с подсистемой управления файлами, используя при этом совокупность специальных обращений к операционной системе, таких как open (для того, чтобы открыть файл на чтение или запись),close, read, write, stat (запросить атрибуты файла), chown (изменить запись с информацией о владельце файла) и chmod (изменить права доступа к файлу). Эти и другие операции рассматриваются в главе 5.

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

2.2.1 Обзор особенностей подсистемы управления файлами

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

open("/fs2/mjb/rje/sourcefile", 1);

ядро системы возвращает индекс для файла "/fs2/mjb/rje/sourcefile". Если процесс создает новый файл, ядро присваивает этому файлу неиспользуемый индекс. Индексы хранятся в файловой системе (и это мы еще увидим), однако при обработке файлов ядро заносит их в таблицу индексов в оперативной памяти.

Ядро поддерживает еще две информационные структуры, таблицу файлов и пользовательскую таблицу дескрипторов файла. Таблица файлов выступает глобальной структурой ядра, а пользовательская таблица дескрипторов файла выделяется под процесс. Если процесс открывает или создает файл, ядро выделяет в каждой таблице элемент, корреспондирующий с индексом файла. Элементы в этих трех структурах - в пользовательской таблице дескрипторов файла, в таблице файлов и в таблице индексов - хранят информацию о состоянии файла и о доступе пользователей к нему. В таблице файлов хранится смещение в байтах от начала файла до того места, откуда начнет выполняться следующая команда пользователя read или write, а также информация о правах доступа к открываемому процессу. Таблица дескрипторов файла идентифицирует все открытые для процесса файлы. На Рисунке 2.2 показаны эти таблицы и связи между ними. В системных операциях open (открыть) и creat (создать) ядро возвращает дескриптор файла, которому соответствует указатель в таблице дескрипторов файла. При выполнении операций read (читать) и write (писать) ядро использует дескриптор файла для входа в таблицу дескрипторов и, следуя указателям на таблицу файлов и на таблицу индексов, находит информацию в файле. Более подробно эти информационные структуры рассматриваются в главах 4 и 5. Сейчас достаточно сказать, что использование этих таблиц обеспечивает различную степень разделения доступа к файлу.

2.2.2 Процессы

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

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

С практической точки зрения процесс в системе UNIX является объектом, создаваемым в результате выполнения системной операции fork. Каждый процесс, за исключением нулевого, порождается в результате запуска другим процессом операции fork. Процесс, запустивший операцию fork, называется родительским, а вновь созданный процесс - порожденным. Каждый процесс имеет одного родителя, но может породить много процессов. Ядро системы идентифицирует каждый процесс по его номеру, который называется идентификатором процесса (PID). Нулевой процесс является особенным процессом, который создается "вручную" в результате загрузки системы; после порождения нового процесса (процесс 1) нулевой процесс становится процессом подкачки. Процесс 1, известный под именем init, является предком любого другого процесса в системе и связан с каждым процессом особым образом, описываемым в главе 7.

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

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

Для программы, приведенной на Рисунке 1.3, текст исполняемого файла представляет собой сгенерированный код для функций main и copy, к определенным данным относится переменная version (вставленная в программу для того, чтобы в последней имелись некоторые определенные данные), а к неопределенным - массив buffer. Компилятор с языка Си для системы версии V создает отдельно текстовую секцию по умолчанию, но не исключается возможность включения инструкций программы и в секцию данных, как в предыдущих версиях системы.

Ядро загружает исполняемый файл в память при выполнении системной операции exec, при этом загруженный процесс состоит по меньшей мере из трех частей, так называемых областей: текста, данных и стека. Области текста и данных корреспондируют с секциями текста и bss-данных исполняемого файла, а область стека создается автоматически и ее размер динамически устанавливается ядром системы во время выполнения. Стек состоит из логических записей активации, помещаемых в стек при вызове функции и выталкиваемых из стека при возврате управления в вызвавшую процедуру; специальный регистр, именуемый указателем вершины стека, показывает текущую глубину стека. Запись активации включает параметры передаваемые функции, ее локальные переменные, а также данные, необходимые для восстановления предыдущей записи активации, в том числе значения счетчика команд и указателя вершины стека в момент вызова функции. Текст программы включает последовательности команд, управляющие увеличением стека, а ядро системы выделяет, если нужно, место под стек. В программе на Рисунке 1.3 параметры argc и argv, а также переменные fdold и fdnew, содержащиеся в вызове функции main, помещаются в стек, как только встретилось обращение к функции main (один раз в каждой программе, по условию), так же и параметры old и new и переменная count, содержащиеся в вызове функции copy, помещаются в стек в момент обращения к указанной функции.

2.2 ВВЕДЕНИЕ В ОСНОВНЫЕ ПОНЯТИЯ СИСТЕМЫ

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

2.3 СТРУКТУРЫ ДАННЫХ ЯДРА

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

2.4 УПРАВЛЕНИЕ СИСТЕМОЙ

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

2.5 ВЫВОДЫ И ОБЗОР ПОСЛЕДУЮЩИХ ГЛАВ

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

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

В остальных частях главы детально описываются подсистемы, изображенные на Рисунке 2.1, а также взаимодействие между ними, начиная с подсистемы управления файлами и включая подсистему управления процессами. В следующей главе рассматривается буфер сверхоперативной памяти (кеш) и описываются алгоритмы управления буфером, используемые в главах 4, 5 и 7. В главе 4 рассматриваются внутренние алгоритмы файловой системы, включая обработку индексов, структуру файлов, преобразование имени пути в индекс. В главе 5 рассматриваются системные операции, которые, используя приведенные в главе 4 алгоритмы, обращаются к файловой системе, т.е. такие, как open, close, read и write. Глава 6 имеет дело с понятием контекста процесса и его адресным пространством, а глава 7 рассматривает системные операции, связанные с управлением процессами и использующие алгоритмы главы 6. Глава 8 касается планирования выполнения процессов, в главе 9 обсуждаются алгоритмы распределения памяти. Глава 10 посвящена драйверам устройств, рассмотрение которых до того откладывалось, чтобы прежде объяснить связь драйвера терминала с управлением процессами. В главе 11 представлено несколько форм взаимодействия процессов. Наконец, в последних двух главах рассматриваются вопросы, связанные с углубленным изучением особенностей системы, в частности, особенности многопроцессорных систем и распределенных систем.

2.6 УПРАЖНЕНИЯ

1. Рассмотрим следующий набор команд:

grep main a.c b.c c.c > grepout & wc -1 < grepout & rm grepout &

Амперсанд (символ "&") в конце каждой командной строки говорит командному процессору shell о том, что команду следует выполнить на фоне, при этом shell может выполнять все командные строки параллельно. Почему это не равноценно следующей командной строке?

grep main a.c b.c c.c | wc -1

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

remove(gp) struct queue *gp; { gp - > forp - > backp = gp - > backp; gp - > backp - > forp = gp - > forp; gp - > forp = gp - > backp = NULL; }

Рассмотрим три случая:

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

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

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

3.1 ЗАГОЛОВКИ БУФЕРА

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

Информация в буфере соответствует информации в одном логическом блоке диска в файловой системе, и ядро распознает содержимое буфера, просматривая идентифицирующие поля в его заголовке. Буфер представляет собой копию дискового блока в памяти; содержимое дискового блока отображается в буфер, но это отображение временное, поскольку оно имеет место до того момента, когда ядро примет решение отобразить в буфер другой дисковый блок. Один дисковый блок не может быть одновременно отображен в несколько буферов. Если бы два буфера содержали информацию для одного и того же дискового блока, ядро не смогло бы определить, в каком из буферов содержится текущая информация, и, возможно, возвратило бы на диск некорректную информацию. Предположим, например, что дисковый блок отображается в два буфера, A и B. Если ядро запишет данные сначала в буфер A, а затем в буфер B, дисковый блок будет содержать данные из буфера B, если в результате операций записи буфер заполнится до конца. Однако, если ядро изменит порядок, в котором оно копирует содержимое буферов на диск, на противоположный, дисковый блок будет содержать некорректные данные.

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

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

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

3.2 СТРУКТУРА ОБЛАСТИ БУФЕРОВ (БУФЕРНОГО ПУЛА)

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

3.3 МЕХАНИЗМ ПОИСКА БУФЕРА

Как показано на Рисунке 2.1, алгоритмы верхнего уровня, используемые ядром для подсистемы управления файлами, инициируют выполнение алгоритмов управления буферным кешем. При выборке блока алгоритмы верхнего уровня устанавливают логический номер устройства и номер блока, к которым они хотели бы получить доступ. Например, если процесс хочет считать данные из файла, ядро устанавливает, в какой файловой системе находится файл и в каком блоке файловой системы содержатся данные, о чем подробнее мы узнаем из главы 4. Собираясь считать данные из определенного дискового блока, ядро проверяет, находится ли блок в буферном пуле, и если нет, назначает для него свободный буфер. Собираясь записать данные в определенный дисковый блок, ядро проверяет, находится ли блок в буферном пуле, и если нет, назначает для этого блока свободный буфер. Для выделения буферов из пула в алгоритмах чтения и записи дисковых блоков используется операция getblk (Рисунок 3.4).

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

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

Обсудим каждый случай более подробно.

Осуществляя поиск блока в буферном пуле по комбинации номеров устройства и блока, ядро ищет хеш-очередь, которая бы содержала этот блок. Просматривая хеш-очередь, ядро придерживается списка с указателями, пока (как в первом случае) не найдет буфер с искомыми номерами устройства и блока. Ядро проверяет занятость блока и в том случае, если он свободен, помечает буфер "занятым" для того, чтобы другие процессы (**) не смогли к нему обратиться. Затем ядро удаляет буфер из списка свободных буферов, поскольку буфер не может одновременно быть занятым и находиться в указанном списке. Если другие процессы попытаются обратиться к блоку в то время, когда его буфер занят, они приостановятся до тех пор, пока буфер не освободится. На Рисунке 3.5 показан первый случай, когда ядро ищет блок 4 в хеш-очереди, помеченной как "блок 0 модуль 4". Обнаружив буфер, ядро удаляет его из списка свободных буферов, делая блоки 5 и 28 соседями в списке.

3.4 ЧТЕНИЕ И ЗАПИСЬ ДИСКОВЫХ БЛОКОВ

Теперь, когда алгоритм выделения буферов нами уже рассмотрен, будет легче понять процедуру чтения и записи дисковых блоков. Чтобы считать дисковый блок (Рисунок 3.13), процесс использует алгоритм getblk для поиска блока в буферном кеше. Если он там, ядро может возвратить его немедленно без физического считывания блока с диска. Если блок в кеше отсутствует, ядро приказывает дисководу "запланировать" запрос на чтение и приостанавливает работу, ожидая завершения ввода-вывода. Дисковод извещает контроллер диска о том, что он собирается считать информацию, и контроллер тогда передает информацию в буфер. Наконец, дисковый контроллер прерывает работу процессора, сообщая о завершении операции ввода-вывода, и программа обработки прерываний от диска возобновляет выполнение приостановленного процесса; теперь содержимое дискового блока находится в буфере. Модули, запросившие информацию данного блока, получают ее; когда буфер им уже не потребуется, они освободят его для того, чтобы другие процессы получили к нему доступ.

3.5 ПРЕИМУЩЕСТВА И НЕУДОБСТВА БУФЕРНОГО КЕША

Использование буферного кеша имеет, с одной стороны, несколько преимуществ и, с другой стороны, некоторые неудобства.

Использование буферов позволяет внести единообразие в процедуру обращения к диску, поскольку ядру нет необходимости знать причину ввода-вывода. Вместо этого, ядро копирует данные в буфер и из буфера, невзирая на то, являются ли данные частью файла, индекса или суперблока. Буферизация ввода-вывода с диска повышает модульность разработки программ, поскольку те составные части ядра, которые занимаются вводом-выводом на диск, имеют один интерфейс на все случаи. Короче говоря, упрощается проектирование системы. Система не накладывает никаких ограничений на выравнивание информации пользовательскими процессами, выполняющими ввод-вывод, поскольку ядро производит внутреннее выравнивание информации. В различных аппаратных реализациях часто требуется выравнивать информацию для ввода-вывода с диска определенным образом, т.е. производить к примеру двухбайтное или четырехбайтное выравнивание данных в памяти. Без механизма буферизации программистам пришлось бы заботиться самим о правильном выравнивании данных. По этой причине на машинах с ограниченными возможностями в выравнивании адресов возникает большое количество ошибок программирования и, кроме того, становится проблемой перенос программ в операционную среду UNIX. Копируя информацию из пользовательских буферов в системные буферы (и обратно), ядро системы устраняет необходимость в специальном выравнивании пользовательских буферов, делая пользовательские программы более простыми и мобильными. Благодаря использованию буферного кеша, сокращается объем дискового трафика и время реакции и повышается общая производительность системы. Процессы, считывающие данные из файловой системы, могут обнаружить информационные блоки в кеше и им не придется прибегать ко вводу-выводу с диска. Ядро часто применяет "отложенную запись", чтобы избежать лишних обращений к диску, оставляя блок в буферном кеше и надеясь на попадание блока в кеш. Очевидно, что шансы на такое попадание выше в системах с большим количеством буферов. Тем не менее, число буферов, которые можно заложить в системе, ограничивается объемом памяти, доступной выполняющимся процессам: если под буферы задействовать слишком много памяти, то система будет работать медленнее в связи с тем, что ей придется заниматься подкачкой и замещением выполняющихся процессов. Алгоритмы буферизации помогают поддерживать целостность файловой системы, так как они сохраняют общий, первоначальный и единственный образ дисковых блоков, содержащихся в кеше. Если два процесса одновременно попытаются обратиться к одному и тому же дисковому блоку, алгоритмы буферизации (например, getblk) параллельный доступ преобразуют в последовательный, предотвращая разрушение данных. Сокращение дискового трафика является важным преимуществом с точки зрения обеспечения хорошей производительности или быстрой реакции системы, однако стратегия кеширования также имеет некоторые неудобства. Так как ядро в случае отложенной записи не переписывает данные на диск немедленно, такая система уязвима для сбоев, которые оставляют дисковые данные в некорректном виде. Хотя в последних версиях системы и сокращен ущерб, наносимый катастрофическими сбоями, основная проблема остается: пользователь, запрашивающий выполнение операции записи, никогда не знает, в какой момент данные завершат свой путь на диск (****). Использование буферного кеша требует дополнительного копирования информации при ее считывании и записи пользовательскими процессами. Процесс, записывающий данные, передает их ядру и ядро копирует данные на диск; процесс, считывающий данные, получает их от ядра, которое читает данные с диска. При передаче большого количества данных дополнительное копирование отрицательным образом отражается на производительности системы, однако при передаче небольших объемов данных производительность повышается, поскольку ядро буферизует данные (используя алгоритм getblk и отложенную запись) до тех пор, пока это представляется эффективным с точки зрения экономии времени работы с диском.

(****) Стандартный набор операций ввода-вывода в программах на языке Си включает операцию fflush. Эта функция занимается подкачиванием данных из буферов в пользовательском адресном пространстве в рабочую область ядра. Тем не менее пользователю не известно, когда ядро запишет данные на диск.

3.6 ВЫВОДЫ

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

Ядро идентифицирует нужный ему блок по номеру логического устройства и номеру блока. Алгоритм getblk просматривает буферный кеш в поисках блока и, если буфер присутствует и свободен, блокирует буфер и возвращает его. Если буфер заблокирован, обратившийся к нему процесс приостанавливается до тех пор, пока буфер не освободится. Механизм блокирования гарантирует, что только один процесс в каждый момент времени работает с буфером. Если в кеше блок отсутствует, ядро назначает блоку свободный буфер, блокирует и возвращает его. Алгоритм bread выделяет блоку буфер и при необходимости читает туда информацию. Алгоритм bwrite копирует информацию в предварительно выделенный буфер. Если при выполнении указанных алгоритмов ядро не увидит необходимости в немедленном копировании данных на диск, оно пометит буфер для "отложенной записи", чтобы избежать излишнего ввода-вывода. К сожалению, процедура откладывания записи сопровождается тем, что процесс никогда не уверен, в какой момент данные физически попадают на диск. Если ядро записывает данные на диск синхронно, оно поручает драйверу диска передать блок файловой системе и ждет прерывания, сообщающего об окончании ввода-вывода.

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

3.7 УПРАЖНЕНИЯ

1. Рассмотрим функцию хеширования применительно к Рисунку 3.3. Наилучшей функцией хеширования является та, которая единым образом распределяет блоки между хеш-очередями. Что Вы могли бы предложить в качестве оптимальной функции хеширования? Должна ли эта функция в своих расчетах использовать логический номер устройства?

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

*3. В алгоритме getblk ядро должно повысить приоритет прерывания работы процессора так, чтобы блокировать прерывания до проверки занятости блока. (Это не показано в тексте.) Почему?

4. В алгоритме brelse ядро помещает буфер в "голову" списка свободных буферов, если содержимое буфера неверно. Если содержимое буфера неверно, должен ли буфер появиться в хеш-очереди?

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

*6. Если несколько процессов оспаривают буфер, ядро гарантирует, что ни один из них не приостановится навсегда, но не гарантирует, что процесс не "зависнет" и дождется получения буфера. Переделайте алгоритм getblk так, чтобы процессу было в конечном итоге гарантировано получение буфера.

7. Переделайте алгоритмы getblk и brelse так, чтобы ядро следовало не схеме замещения буферов, к которым наиболее долго не было обращений, а схеме "первым пришел - первым вышел". Повторите то же самое со схемой замещения редко используемых буферов.

8. Опишите ситуацию в алгоритме bread, когда информация в буфере уже верна.

*9. Опишите различные ситуации, встречающиеся в алгоритме breada. Что произойдет в случае следующего выполнения алгоритма bread или breada, когда текущий блок прочитан с продвижением? В алгоритме breada, если первый или второй блок отсутствует в кеше, в дальнейшем при проверке правильности содержимого буфера предполагается, что блок мог быть в буферном пуле. Как это может быть?

10. Опишите алгоритм, запрашивающий и получающий любой свободный буфер из буферного пула. Сравните этот алгоритм с getblk.

11. В различных системных операциях, таких как umount и sync (глава 5), требуется, чтобы ядро перекачивало на диск содержимое всех буферов, которые помечены для "отложенной записи" в данной файловой системе. Опишите алгоритм, реализующий перекачку буферов. Что произойдет с очередностью расположения буферов в списке свободных буферов в результате этой операции? Как ядро может гарантировать, что ни один другой процесс не подберется к буферу с пометкой "отложенная запись" и не сможет переписать его содержимое в файловую систему, пока процесс перекачки приостановлен в ожидании завершения операции ввода-вывода?

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

4.1.1 Определение

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

Идентификатор владельца файла. Права собственности разделены между индивидуальным владельцем и "групповым" и тем самым помогают определить круг пользователей, имеющих права доступа к файлу. Суперпользователь имеет право доступа ко всем файлам в системе. Тип файла. Файл может быть файлом обычного типа, каталогом, специальным файлом, соответствующим устройствам ввода-вывода символами или блоками, а также абстрактным файлом канала (организующим обслуживание запросов в порядке поступления, "первым пришел - первым вышел"). Права доступа к файлу. Система разграничивает права доступа к файлу для трех классов пользователей: индивидуального владельца файла, группового владельца и прочих пользователей; каждому классу выделены определенные права на чтение, запись и исполнение файла, которые устанавливаются индивидуально. Поскольку каталоги как файлы не могут быть исполнены, разрешение на исполнение в данном случае интерпретируется как право производить поиск в каталоге по имени файла. Календарные сведения, характеризующие работу с файлом: время внесения последних изменений в файл, время последнего обращения к файлу, время внесения последних изменений в индекс. Число указателей на файл, означающее количество имен, используемых при поиске файла в иерархии каталогов. Указатели на файл подробно рассматриваются в главе 5. Таблица адресов на диске, в которых располагается информация файла. Хотя пользователи трактуют информацию в файле как логический поток байтов, ядро располагает эти данные в несоприкасающихся дисковых блоках. Дисковые блоки, содержащие информацию файла, указываются в индексе. Размер файла. Данные в файле адресуются с помощью смещения в байтах относительно начала файла, начиная со смещения, равного 0, поэтому размер файла в байтах на 1 больше максимального смещения. Например, если пользователь создает файл и записывает только 1 байт информации по адресу со смещением 1000 от начала файла, размер файла составит 1001 байт. В индексе отсутствует составное имя файла, необходимое для осуществления доступа к файлу.

4.1.2 Обращение к индексам

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

номер блока = ((номер индекса - 1) / число индексов в блоке) + + начальный блок в списке индексов где операция деления возвращает целую часть частного. Например, предположим, что блок 2 является начальным в списке индексов и что в каждом блоке помещаются 8 индексов, тогда индекс с номером 8 находится в блоке 2, а индекс с номером 9 - в блоке 3. Если же в дисковом блоке помещаются 16 индексов, тогда индексы с номерами 8 и 9 располагаются в дисковом блоке с номером 2, а индекс с номером 17 является первым индексом в дисковом блоке 3.

4.1.3 Освобождение индексов

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

4.1 ИНДЕКСЫ

4.2 СТРУКТУРА ФАЙЛА ОБЫЧНОГО ТИПА

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

4.3 КАТАЛОГИ

Из главы 1 напомним, что каталоги являются файлами, из которых строится иерархическая структура файловой системы; они играют важную роль в превращении имени файла в номер индекса. Каталог - это файл, содержимым которого является набор записей, состоящих из номера индекса и имени файла, включенного в каталог. Составное имя - это строка символов, завершающаяся пустым символом и разделяемая наклонной чертой ("/") на несколько компонент. Каждая компонента, кроме последней, должна быть именем каталога, но последняя компонента может быть именем файла, не являющегося каталогом. В версии V системы UNIX длина каждой компоненты ограничивается 14 символами; таким образом, вместе с 2 байтами, отводимыми на номер индекса, размер записи каталога составляет 16 байт.

4.4 ПРЕВРАЩЕНИЕ СОСТАВНОГО ИМЕНИ

4.4 ПРЕВРАЩЕНИЕ СОСТАВНОГО ИМЕНИ ФАЙЛА (ПУТИ ПОИСКА) В ИДЕНТИФИКАТОР ИНДЕКСА

Начальное обращение к файлу производится по его составному имени (имени пути поиска), как в командах open, chdir (изменить каталог) или link. Поскольку внутри системы ядро работает с индексами, а не с именами путей поиска, оно преобразует имена путей поиска в идентификаторы индексов, чтобы производить доступ к файлам. Алгоритм namei производит поэлементный анализ составного имени, ставя в соответствие каждой компоненте имени индекс и каталог и в конце концов возвращая идентификатор индекса для введенного имени пути поиска (Рисунок 4.11).

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

4.5 СУПЕРБЛОК

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

Суперблок состоит из следующих полей:

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

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

4.6 НАЗНАЧЕНИЕ ИНДЕКСА НОВОМУ ФАЙЛУ

Для выделения известного индекса, то есть индекса, для которого предварительно определен собственный номер (и номер файловой системы), ядро использует алгоритм iget. В алгоритме namei, например, ядро определяет номер индекса, устанавливая соответствие между компонентой имени пути поиска и именем в каталоге. Другой алгоритм, ialloc, выполняет назначение дискового индекса вновь создаваемому файлу.

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

4.7 ВЫДЕЛЕНИЕ ДИСКОВЫХ БЛОКОВ

Когда процесс записывает данные в файл, ядро должно выделять из файловой системы дисковые блоки под информационные блоки прямой адресации и иногда под блоки косвенной адресации. Суперблок файловой системы содержит массив, используемый для хранения номеров свободных дисковых блоков в файловой системе. Сервисная программа mkfs ("make file system" - создать файловую систему) организует информационные блоки в файловой системе в виде списка с указателями так, что каждый элемент списка указывает на дисковый блок, в котором хранится массив номеров свободных дисковых блоков, а один из элементов массива хранит номер следующего блока данного списка.

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

Если процесс записывает в файл большой объем информации, он неоднократно запрашивает у системы блоки для хранения информации, но ядро назначает каждый раз только по одному блоку. Программа mkfs пытается организовать первоначальный связанный список номеров свободных блоков так, чтобы номера блоков, передаваемых файлу, были рядом друг с другом. Благодаря этому повышается производительность, поскольку сокращается время поиска на диске и время ожидания при последовательном чтении файла процессом. На Рисунке 4.18 номера блоков даны в настоящем формате, определяемом скоростью вращения диска. К сожалению, очередность номеров блоков в списке свободных блоков перепутана в связи с частыми обращениями к списку со стороны процессов, ведущих запись в файлы и удаляющих их, в результате чего номера блоков поступают в список и покидают его в случайном порядке. Ядро не предпринимает попыток сортировать номера блоков в списке.

4.8 ДРУГИЕ ТИПЫ ФАЙЛОВ

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

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

4.9 ВЫВОДЫ

Индекс представляет собой структуру данных, в которой описываются атрибуты файла, в том числе расположение информации файла на диске. Существует две разновидности индекса: копия на диске, в которой хранится информация индекса, пока файл находится в работе, и копия в памяти, где хранится информация об активных файлах. Алгоритмы ialloc и ifree управляют назначением файлу дискового индекса во время выполнения системных операций creat, mknod, pipe и unlink (см. следующую главу), а алгоритмы iget и iput управляют выделением индексов в памяти в момент обращения процесса к файлу. Алгоритм bmap определяет местонахождение дисковых блоков, принадлежащих файлу, используя предварительно заданное смещение в байтах от начала файла. Каталоги представляют собой файлы, которые устанавливают соответствие между компонентами имен файлов и номерами индексов. Алгоритм namei преобразует имена файлов, с которыми работают процессы, в идентификаторы индексов, с которыми работает ядро. Наконец, ядро управляет назначением файлу новых дисковых блоков, используя алгоритмы alloc и free.

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

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

4.10 УПРАЖНЕНИЯ

1. В версии V системы UNIX разрешается использовать не более 14 символов на каждую компоненту имени пути поиска. Алгоритм namei отсекает лишние символы в компоненте. Что нужно сделать в файловой системе и в соответствующих алгоритмах, чтобы стали допустимыми имена компонент произвольной длины?

2. Предположим, что пользователь имеет закрытую версию системы UNIX, причем он внес в нее такие изменения, что имя компоненты теперь может состоять из 30 символов; закрытая версия системы обеспечивает тот же способ хранения записей каталогов, как и стандартная операционная система, за исключением того, что записи каталогов имеют длину 32 байта вместо 16. Если пользователь смонтирует закрытую файловую систему в стандартной операционной среде, что произойдет во время работы алгоритма namei, когда процесс обратится к файлу?

*3. Рассмотрим работу алгоритма namei по преобразованию имени пути поиска в идентификатор индекса. В течение всего просмотра ядро проверяет соответствие текущего рабочего индекса индексу каталога. Может ли другой процесс удалить (unlink) каталог? Каким образом ядро предупреждает такие действия? В следующей главе мы вернемся к этой проблеме.

*4. Разработайте структуру каталога, повышающую эффективность поиска имен файлов без использования линейного просмотра. Рассмотрите два способа: хеширование и n-арные деревья.

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

*6. В идеальном случае в файловой системе не должно быть свободных индексов с номерами, меньшими, чем номер "запомненного" индекса, используемый алгоритмом ialloc. Как случается, что это утверждение бывает ложным?

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

5.1 OPEN

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

fd = open(pathname,flags,modes);

где pathname - имя файла, flags указывает режим открытия (например, для чтения или записи), а modes содержит права доступа к файлу в случае, если файл создается. Системная функция open возвращает целое число (*), именуемое пользовательским дескриптором файла. Другие операции над файлами, такие как чтение, запись, позиционирование головок чтения-записи, воспроизведение дескриптора файла, установка параметров ввода-вывода, определение статуса файла и закрытие файла, используют значение дескриптора файла, возвращаемое системной функцией open.

Ядро просматривает файловую систему в поисках файла по его имени, используя алгоритм namei (см. Рисунок 5.2). Оно проверяет права на открытие файла после того, как обнаружит копию индекса файла в памяти, и выделяет открываемому файлу запись в таблице файлов. Запись таблицы файлов содержит указатель на индекс открытого файла и поле, в котором хранится смещение в байтах от начала файла до места, откуда предполагается начинать выполнение последующих операций чтения или записи. Ядро сбрасывает это смещение в 0 во время открытия файла, имея в виду, что исходная операция чтения или записи по умолчанию будет производиться с начала файла. С другой стороны, процесс может открыть файл в режиме записи в конец, в этом случае ядро устанавливает значение смещения, равное размеру файла. Ядро выделяет запись в личной (закрытой) таблице в адресном пространстве задачи, выделенном процессу (таблица эта называется таблицей пользовательских дескрипторов файлов), и запоминает указатель на эту запись. Указателем выступает дескриптор файла, возвращаемый пользователю. Запись в таблице пользовательских файлов указывает на запись в глобальной таблице файлов.

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

5.2 READ

Синтаксис вызова системной функции read (читать):

number = read(fd,buffer,count)

где fd - дескриптор файла, возвращаемый функцией open, buffer - адрес структуры данных в пользовательском процессе, где будут размещаться считанные данные в случае успешного завершения выполнения функции read, count - количество байт, которые пользователю нужно прочитать, number - количество фактически прочитанных байт. На Рисунке 5.5 приведен алгоритм read, выполняющий чтение обычного файла. Ядро обращается в таблице файлов к записи, которая соответствует значению пользовательского дескриптора файла, следуя за указателем (см. Рисунок 5.3). Затем оно устанавливает значения нескольких параметров ввода-вывода в адресном пространстве процесса (Рисунок 5.6), тем самым устраняя необходимость в их передаче в качестве параметров функции. В частности, ядро указывает в качестве режима ввода-вывода "чтение", устанавливает флаг, свидетельствующий о том, что ввод-вывод направляется в адресное пространство пользователя, значение поля счетчика байтов приравнивает количеству байт, которые будут прочитаны, устанавливает адрес пользовательского буфера данных и, наконец, значение смещения (из таблицы файлов), равное смещению в байтах внутри файла до места, откуда начинается ввод-вывод. После того, как ядро установит значения параметров ввода-вывода в адресном пространстве процесса, оно обращается к индексу, используя указатель из таблицы файлов, и блокирует его прежде, чем начать чтение из файла.

5.3 WRIТЕ

Синтаксис вызова системной функции write (писать):

number = write(fd,buffer,count);

где переменные fd, buffer, count и number имеют тот же смысл, что и для вызова системной функции read. Алгоритм записи в обычный файл похож на алгоритм чтения из обычного файла. Однако, если в файле отсутствует блок, соответствующий смещению в байтах до места, куда должна производиться запись, ядро выделяет блок, используя алгоритм alloc, и присваивает ему номер в соответствии с точным указанием места в таблице содержимого индекса. Если смещение в байтах совпадает со смещением для блока косвенной адресации, ядру, возможно, придется выделить несколько блоков для использования их в качестве блоков косвенной адресации и информационных блоков. Индекс блокируется на все время выполнения функции write, так как ядро может изменить индекс, выделяя новые блоки; разрешение другим процессам обращаться к файлу может разрушить индекс, если несколько процессов выделяют блоки одновременно, используя одни и те же значения смещений. Когда запись завершается, ядро корректирует размер файла в индексе, если файл увеличился в размере.

5.4 ЗАХВАТ ФАЙЛА И ЗАПИСИ

В первой версии системы UNIX, разработанной Томпсоном и Ричи, отсутствовал внутренний механизм, с помощью которого процессу мог бы быть обеспечен исключительный доступ к файлу. Механизм захвата был признан излишним, поскольку, как отмечает Ричи, "мы не имеем дела с большими базами данных, состоящими из одного файла, которые поддерживаются независимыми процессами" (см. [Ritchie 81]). Для того, чтобы повысить привлекательность системы UNIX для коммерческих пользователей, работающих с базами данных, в версию V системы ныне включены механизмы захвата файла и записи. Захват файла - это средство, позволяющее запретить другим процессам производить чтение или запись любой части файла, а захват записи - это средство, позволяющее запретить другим процессам производить ввод-вывод указанных записей (частей файла между указанными смещениями). В упражнении 5.9 рассматривается реализация механизма захвата файла и записи.

5.5 УКАЗАНИЕ МЕСТА В ФАЙЛЕ, ГДЕ

5.5 УКАЗАНИЕ МЕСТА В ФАЙЛЕ, ГДЕ БУДЕТ ВЫПОЛНЯТЬСЯ ВВОД-ВЫВОД - LSEEК

Обычное использование системных функций read и write обеспечивает последовательный доступ к файлу, однако процессы могут использовать вызов системной функции lseek для указания места в файле, где будет производиться ввод-вывод, и осуществления произвольного доступа к файлу. Синтаксис вызова системной функции:

position = lseek(fd,offset,reference);

где fd - дескриптор файла, идентифицирующий файл, offset - смещение в байтах, а reference указывает, является ли значение offset смещением от начала файла, смещением от текущей позиции ввода-вывода или смещением от конца файла. Возвращаемое значение, position, является смещением в байтах до места, где будет начинаться следующая операция чтения или записи. Например, в программе, приведенной на Рисунке 5.10, процесс открывает файл, считывает байт, а затем вызывает функцию lseek, чтобы заменить значение поля смещения в таблице файлов величиной, равной 1023 (с переменной reference, имеющей значение 1), и выполняет цикл. Таким образом, программа считывает каждый 1024-й байт файла. Если reference имеет значение 0, ядро осуществляет поиск от начала файла, а если 2, ядро ведет поиск от конца файла. Функция lseek ничего не должна делать, кроме операции поиска, которая позиционирует головку чтения-записи на указанный дисковый сектор. Для того, чтобы выполнить функцию lseek, ядро просто выбирает значение смещения из таблицы файлов; в последующих вызовах функций read и write смещение из таблицы файлов используется в качестве начального смещения.

5.6 CLOSЕ

Процесс закрывает открытый файл, когда процессу больше не нужно обращаться к нему. Синтаксис вызова системной функции close (закрыть):

close(fd);

где fd - дескриптор открытого файла. Ядро выполняет операцию закрытия, используя дескриптор файла и информацию из соответствующих записей в таблице файлов и таблице индексов. Если счетчик ссылок в записи таблицы файлов имеет значение, большее, чем 1, в связи с тем, что были обращения к функциям dup или fork, то это означает, что на запись в таблице файлов делают ссылку другие пользовательские дескрипторы, что мы увидим далее; ядро уменьшает значение счетчика и операция закрытия завершается. Если счетчик ссылок в таблице файлов имеет значение, равное 1, ядро освобождает запись в таблице и индекс в памяти, ранее выделенный системной функцией open (алгоритм iput). Если другие процессы все еще ссылаются на индекс, ядро уменьшает значение счетчика ссылок на индекс, но оставляет индекс процессам; в противном случае индекс освобождается для переназначения, так как его счетчик ссылок содержит 0. Когда выполнение системной функции close завершается, запись в таблице пользовательских дескрипторов файла становится пустой. Попытки процесса использовать данный дескриптор заканчиваются ошибкой до тех пор, пока дескриптор не будет переназначен другому файлу в результате выполнения другой системной функции. Когда процесс завершается, ядро проверяет наличие активных пользовательских дескрипторов файла, принадлежавших процессу, и закрывает каждый из них. Таким образом, ни один процесс не может оставить файл открытым после своего завершения.

5.7 СОЗДАНИЕ ФАЙЛА

Системная функция open дает процессу доступ к существующему файлу, а системная функция creat создает в системе новый файл. Синтаксис вызова системной функции creat:

fd = creat(pathname,modes);

где переменные pathname, modes и fd имеют тот же смысл, что и в системной функции open. Если прежде такого файла не существовало, ядро создает новый файл с указанным именем и указанными правами доступа к нему; если же такой файл уже существовал, ядро усекает файл (освобождает все существующие блоки данных и устанавливает размер файла равным 0) при наличии соответствующих прав доступа к нему (***). На Рисунке 5.12 приведен алгоритм создания файла.

5.8 СОЗДАНИЕ СПЕЦИАЛЬНЫХ ФАЙЛОВ

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

mknod(pathname,type and permissions,dev)

где pathname - имя создаваемой вершины в иерархической структуре файловой системы, type and permissions - тип вершины (например, каталог) и права доступа к создаваемому файлу, а dev указывает старший и младший номера устройства для блочных и символьных специальных файлов (глава 10). На Рисунке 5.13 приведен алгоритм, реализуемый функцией mknod при создании новой вершины.

5.9 СМЕНА ТЕКУЩЕГО И КОРНЕВОГО КАТАЛОГА

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

Алгоритм chdir (Рисунок 5.14) изменяет имя текущего каталога для процесса. Синтаксис вызова системной функции chdir:

chdir(pathname);

где pathname - каталог, который становится текущим для процесса. Ядро анализирует имя каталога, используя алгоритм namei, и проверяет, является ли данный файл каталогом и имеет ли владелец процесса право доступа к каталога. Ядро снимает с нового индекса блокировку, но удерживает индекс в качестве выделенного и оставляет счетчик ссылок без изменений, освобождает индекс прежнего текущего каталога (алгоритм iput), хранящийся в пространстве процесса, и запоминает в этом пространстве новый индекс. После смены процессом текущего каталога алгоритм namei использует индекс в качестве начального каталога при анализе всех имен путей, которые не берут начало от корня. По окончании выполнения системной функции chdir счетчик ссылок на индекс нового каталога имеет значение, как минимум, 1, а счетчик ссылок на индекс прежнего текущего каталога может стать равным 0. В этом отношении функция chdir похожа на функцию open, поскольку обе функции обращаются к файлу и оставляют его индекс в качестве выделенного. Индекс, выделенный во время выполнения функции chdir, освобождается только тогда, когда процесс меняет текущий каталог еще раз или когда процесс завершается.

Процессы обычно используют глобальный корневой каталог файловой системы для всех имен путей поиска, начинающихся с "/". Ядро хранит глобальную переменную, которая указывает на индекс глобального корня, выделяемый по алгоритму iget при загрузке системы. Процессы могут менять свое представление о корневом каталоге файловой системы с помощью системной функции chroot. Это бывает полезно, если пользователю нужно создать модель обычной иерархической структуры файловой системы и запустить процессы там. Синтаксис вызова функции:

chroot(pathname);

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

5.10 СМЕНА ВЛАДЕЛЬЦА И РЕЖИМА ДОСТУПА К ФАЙЛУ

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

chown(pathname,owner,group) chmod(pathname,mode)

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

5.11 STAT И FSTАТ

Системные функции stat и fstat позволяют процессам запрашивать информацию о статусе файла: типе файла, владельце файла, правах доступа, размере файла, числе связей, номере индекса и времени доступа к файлу. Синтаксис вызова функций:

stat(pathname,statbuffer); fstat(fd,statbuffer);

где pathname - имя файла, fd - дескриптор файла, возвращаемый функцией open, statbuffer - адрес структуры данных пользовательского процесса, где будет храниться информация о статусе файла после завершения выполнения вызова. Системные функции просто переписывают поля из индекса в структуру statbuffer. Программа на Рисунке 5.33 иллюстрирует использование функций stat и fstat.