Разработка операционных систем

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

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

Другое применение ортогональности - разделение понятий процесса и потока в Windows 2000. Процесс представляет собой контейнер для ресурсов, не более и не менее. Поток представляет собой объект планирования. Когда один процесс получает дескриптор от другого процесса, не имеет значения, сколько потоков у него есть. Когда планировщик выбирает поток, не важно, какому процессу он принадлежит. Эти понятия ортогональны.

Наш последний пример ортогональности возьмем из операционной системы UNIX. Создание процесса происходит здесь в два этапа: при помощи системных вызовов fork и exec. Создание нового адресного пространства и заполнение его новым образом памяти в данном случае разделены, что позволяет выполнить определенные действия между этими этапами. В операционной системе Windows 2000 эти два этапа нельзя разделить, то есть концепции создания нового адресного пространства и его заполнения новым образом памяти не являются ортогональными в этой системе. Последовательность системных вызовов clone и exec в системе Linux является еще более ортогональной, так как в данном случае возможно еще более детальное управление этими действиями. Общее правило может быть сформулировано следующим образом: наличие небольшого количества ортогональных элементов, которые могут комбинироваться различными способами, позволяет создать небольшую простую и элегантную систему.

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

Имена, создаваемые для использования их людьми, представляют собой символьные строки формата ASCII или Unicode и, как правило, являются иерархическими. Так, иерархия отчетливо видна на примере путей файлов, например, путь /usr/ast/books/mos2/chap-12 состоит из имен каталогов, поиск которых следует начинать в корневом каталоге. Адреса URL также являются иерархическими. Например, URL www.cs.vu.nl/~ast/ указывает на определенную машину (www) определенного факультета (cs) определенного университета (vu) определенной страны (nl). Участок URL после косой черты обозначает определенный файл на указанной машине, в данном случае по умолчанию это файл www/index.html в домашнем каталоге пользователя ast. Обратите внимание, что URL (а также адреса DNS вообще, включая адреса электронной почты) пишутся «задом наперед», начинаясь с нижнего уровня дерева, в отличие от имен файлов, начинающихся с вершины дерева. На это можно взглянуть и по-другому, если положить дерево горизонтально. При этом в одном случае дерево будет начинаться слева и расти направо, а в другом случае, наоборот, будет начинаться справа и расти влево.

Часто используется двухуровневое именование: внешнее и внутреннее. Например, к файлам всегда можно обратиться по имени, представляющему собой символьную строку. Кроме этого, почти всегда существует внутреннее имя, используемое системой. В операционной системе UNIX реальным именем файла является номер его i-узла. Имя в формате ASCII вообще не используется внутри системы. В действительности это имя даже не является уникальным, так как на файл может указывать несколько ссылок. А в операционной системе Windows 2000 в качестве внутреннего имени используется индекс файла в таблице MFT. Работа каталога заключается в преобразовании внешних имен во внутренние.

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

Время связывания

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

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

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

Языками программирования часто поддерживаются различные виды связывания для переменных. Глобальные переменные связывает с конкретным виртуальным адресом компилятор. Это пример раннего связывания. Локальным переменным процедуры виртуальные адреса назначаются (в стеке) во время выполнения процедуры. Это пример промежуточного связывания. Переменным, хранящимся в куче (память для которых выделяется при помощи процедуры malloc в программах на языке С или процедуры new в программах на языке Java), виртуальный адрес назначается только на время их фактического использования. Это пример позднего связывания.

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

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

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

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

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

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

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

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

Реализация системы сверху вниз и снизу вверх

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

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

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

Если над проектом работает большая команда программистов, тогда альтернативный подход заключается в том, чтобы сначала создать детальный проект всей системы, после чего распределить задачи по написанию отдельных модулей среди различных групп программистов. Каждая группа независимо тестирует собственную работу. Когда все модули готовы, они объединяются и тестируются совместно. Недостаток такого подхода заключается в том, что если изначально ничто не работает, очень трудно определить, который модуль создан правильно, а какой содержит ошибки и какая группа программистов неверно поняла, чего ей следует ожидать от других модулей. Тем не менее такой метод часто применяется при наличии большого количества программистов, чтобы максимально использовать распараллеливание работ по конструированию системы.

Полезные методы.

Итак, мы только что обсудили некоторые абстрактные идеи, применяющиеся при проектировании и конструировании операционных систем. Теперь мы рассмотрим несколько конкретных методов, полезных при реализации систем. Разумеется, существует также множество других методов, но объем книги не позволяет нам рассмотреть все методы.

Скрытие аппаратуры

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

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

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

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

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

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

Однако другие различия, такие как различия в центральных процессорах, не могут быть скрыты при помощи единого двоичного кода, определяющего при загрузке тип процессора. Один из способов решения данной проблемы состоит в использовании условной трансляции единого исходного кода. В исходных файлах для различных конфигураций используются определенные флаги компиляции, позволяющие получать из единого исходного текста различные двоичные файлы в зависимости от центрального процессора, длины слова, блока MMU и т. д. Представьте себе операционную систему, которая должна работать на компьютерах с процессорами Pentium и UltraSPARC, требующих различных программ инициализации. В зависимости от значения константы CPU, определяемой в заголовочном файле config.h, будет выполняться либо один тип инициализации, либо другой. Поскольку в двоичном файле содержится только один вариант программы, потери эффективности не происходит.

В качестве второго примера предположим, что нам требуется тип данных Register, который должен состоять из 32 бит на компьютере с процессором Pentium и 64 бит на компьютере с процессором UltraSPARC. Этого можно добиться при помощи условного кода в листинге 12.3,6 (при условии, что компилятор воспринимает тип int, как 32-разрядное целое, а тип long - как 64-разрядное). Как только это определение дано (возможно, в заголовочном файле, включаемом во все остальные исходные файлы), программист может просто объявить переменные типа Register и быть уверенным, что эти переменные имеют правильный размер.

Разумеется, заголовочный файл config.h должен быть определен корректно. Для процессора Pentium он может выглядеть примерно так:

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

Некоторые читатели могут удивиться, почему переменные CPU и WORD_LENGTH управляются различными макросами. В определении константы Register можно сделать ветвление программы, устанавливая ее значение в зависимости от значения константы CPU, то есть устанавливая значение константы Register равной 32 бит для процессора Pentium и 64 бит для процессора UltraSPARC. Однако эта идея не слишком удачна. Что произойдет, если позднее мы соберемся переносить систему на 64-разрядный процессор Intel Itanium? Для этого нам пришлось бы добавить третий условный оператор, для процессора Itanium. При том, как это было сделано, нужно только добавить строку в файл config.h для процессора Itanium.

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

Косвенность

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

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

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

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

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

Повторное использование

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

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

Реентерабельность

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

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

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

Метод грубой силы

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

Проверка на ошибки прежде всего

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

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

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

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

Многие системы страдают подобными «заболеваниями» в форме утечки памяти. Довольно часто программы обращаются к процедуре malloc, чтобы получить память, но забывают позднее обратиться к функции free, чтобы освободить ее. Вся память системы постепенно исчезает, пока система не зависает.

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

Производительность

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

Кэширование

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

Мы уже наблюдали использование кэша в файловой системе, где он хранит некоторое количество недавно использовавшихся блоков диска, что позволяет избежать обращения к диску при чтении блока. Однако кэширование может также применяться и для других целей. Например, обработка путей к файлам отнимает удивительно много процессорного времени. Рассмотрим снова пример из системы UNIX.Чтобы найти файл /usr/ast/mbox, потребуется выполнить следующие обращения к диску:

1. Прочитать i-узел корневого каталога (i-узел 1).

2. Прочитать корневой каталог (блок 1).

3. Прочитать i-узел каталога /usr (i-узел 6).

4. Прочитать каталог /usr (блок 132).

5. Прочитать i-узел каталога /usr/ast (i-узел 26).

6. Прочитать каталог /usr/ast (блок 406).

Чтобы просто определить номер i-узла искомого файла, нужно как минимум шесть раз обратиться к диску. Если размер файла меньше размера блока (например, 1024 байт), то, чтобы прочитать содержимое файла, нужно восемь обращений к диску.

В некоторых операционных системах обработка путей файлов оптимизируется при помощи кэширования пар (путь, i-узел).

Когда файловая система должна найти файл по пути, обработчик путей сначала обращается к кэшу и ищет в нем самую длинную подстроку, соответствующую обрабатываемому пути. Если обрабатывается путь /usr/ast/grants/stw, кэш отвечает, что номер i-узла каталога /usr/ast равен 26, так что поиск может быть начат с этого места и количество обращений к диску может быть уменьшено на четыре. Недостаток кэширования путей состоит в том, что соответствие имени файла номеру его i-узла не является постоянным. Представьте, что файл /usr/ast/mbox удаляется и его i-узел используется для другого файла, владельцем которого может быть другой пользователь. Затем файл /usr/ast/mbox создается снова, но на этот раз он получает i-узел с номером 106. Если не предпринять специальных мер, запись кэша будет указывать на неверный номер i-узла. Поэтому при удалении файла или каталога следует удалять из кэша запись, соответствующую этому файлу, а если удаляется каталог, то следует удалить также все записи для содержавшихся в этом каталоге файлов и подкаталогов*.

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

Подсказки

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

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

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

Использование локальности

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

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

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

Оптимизируйте общий случай

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

В качестве первого примера рассмотрим вхождение в критическую область. В большинстве случаев процессу будет удаваться вход в критическую область, особенно если внутри этой области процессы не проводят много времени. Операционная система Windows 2000 использует это преимущество, предоставляя вызов Win32 API EnterCriticalSection, который является атомарной функцией, проверяющей флаг в режиме пользователя (с помощью команды процессора TSL или ее эквивалента). Если тест проходит успешно, процесс просто входит в критическую область, для чего не требуется обращения к ядру. Если же результат проверки отрицательный, библиотечная процедура выполняет на семафоре операцию down, чтобы заблокировать процесс. Таким образом, в нормальном случае обращение к ядру не требуется.

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

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

Управление проектом

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

Мифический человеко-месяц

В своей классической книге Фред Брукс, один из разработчиков системы OS/360, занявшийся впоследствии научной деятельностью, рассматривает вопрос, почему так трудно построить большую операционную систему [44, 46]. Когда большинство программистов встречаются с его утверждением, что специалисты, работающие над большими проектами, могут за год произвести всего лишь 1000 строк отлаженного кода, они удивляются, не прилетел ли профессор Брукс из космоса, с планеты Баг. В конце концов, большинство из них помнит, как они создавали программу из 1000 строк всего за одну ночь. Как же этот объем исходного текста может составлять годовую норму для любого программиста, чей IQ превышает 50?

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

1/3 планирование;

1/6 кодирование;

1/4 тестирование модулей;

1/4 тестирование системы.

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

Заголовком книги Брукс обращает внимание читателя на собственное утверждение о том, что люди и время не взаимозаменяемы. Такой единицы, как человеко-месяц, в программировании не существует. Если в проекте участвуют 15 человек, и на всю работу у них уходит 2 года, то отсюда не следует, что 360 человек справятся с этой работой за один месяц, и вряд ли 60 человек выполнят эту работу за 6 месяцев.

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

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

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

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

Недостаток введения в проект новых людей состоит в том, что их необходимо обучать, модули нужно делить заново, чтобы их число соответствовало числу программистов, требуется провести множество собраний, чтобы скоординировать работу отдельных групп и программистов и т.д. Абдель-Хамид и Мэдник [1] получили экспериментальное подтверждение этого закона. Слегка фривольный вариант закона Брукса звучит так: Если собрать девять рожениц в одной комнате, то они не родят через один месяц.

Роль опыта

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

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

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

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

Тенденции в проектировании операционных систем

Предсказывать всегда трудно, особенно будущее. Например, в 1899 году Чарльз Дьюэл, возглавлявший тогда Бюро патентов США, предложил тогдашнему президенту США Мак-Кинли ликвидировать патентное бюро (а также и рабочее место Чарльза Дьюэла!), поскольку, как он писал, «все, что можно было изобрести, уже изобретено». Тем не менее прошло всего несколько лет, и на пороге патентного бюро показался Томас Эдисон с заявками на электрические лампы, фонограф и кинопроектор. Сменим батарейки в нашем кристальном шаре и попытаемся угадать, что станет с операционными системами в ближайшем будущем.

Операционные системы с большим адресным пространством

По мере того как на смену 32-разрядным машинам приходят 64-разрядные, становится возможным главное изменение в строении операционных систем. 32-разрядное адресное пространство на самом деле не так уж велико. Если попытаться разделить 232 байт на всех жителей Земли, то каждому достанется менее одного байта. В то же время 264 примерно равно 2?1019. При этом каждому жителю планеты в 64-разрядном адресном пространстве можно выделить фрагмент размером в 3 Гбайт.

Что можно сделать с адресным пространством в 2?1019 байт? Для начала мы можем отказаться от концепции файловой системы. Вместо этого все файлы можно постоянно хранить в памяти (виртуальной). В конце концов, в ней достаточно места для более чем миллиарда полнометражных фильмов, сжатых до 4 Гбайт. Другая возможность заключается в использовании перманентных объектов. Объекты могут создаваться в адресном пространстве и храниться в нем до тех пор, пока не будут удалены все ссылки на объект, после чего сам объект автоматически удаляется. Такие объекты будут сохраняться в адресном пространстве даже после выключения и перезагрузки компьютера. Чтобы заполнить все 64-разрядное адресное пространство, нужно создавать объекты со скоростью 100 Мбайт/с в течение 5000 лет. Разумеется, для хранения такого количества данных потребуется очень много дисков, но впервые в истории ограничивающим фактором стали физические возможности дисков, а не адресное пространство.

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

Еще один системный аспект, который придется пересмотреть при введении 64-разрядных адресов, это виртуальная память. При 264 байт виртуального адресного пространства и 8-килобайтных страницах у нас будет 251 страниц. Работать с обычными таблицами страниц такого размера будет непросто, поэтому потребуется другое решение. Возможно использование инвертированных таблиц страниц, однако также предлагались и другие идеи [321]. В любом случае появление 64-разрядных операционных систем создает новую большую область исследований.

Сеть

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