Требования к операционным системам реального времени. Типы операционных систем

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

Стандарты Wi-Fi Сегодня используются три стандарта беспроводных сетей: IEEE 802.11b, 802.11a и 802.11g. Современные ноутбуки чаще всего оснащаются поддержкой всех стандартов.802.11b – первый стандарт беспроводных сетей, поэтому он является самым медленным (скорость до 11 Мбит/с). Стандарты

Битва за стандарты Как следует из предшествующего изложения, со временем различия между клонами UNIX становились все более значительными. Во-первых, в основе существовавших её вариантов лежали разные базовые системы – SVR3, SVR4, 4BSD.Во-вторых, каждый разработчик считал своим

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Федеральное агентство по образованию

Кафедра автоматизированных систем управления

Системы реального времени

Введение

1. Операционные системы реального времени

1.1 Типы ОСРВ

1.2 Структура ОСРВ

1.3 Процессы, потоки, задачи

1.4 Планирование, приоритеты

1.5 Память

1.6 Прерывания

1.7 Часы и таймеры

2. Стандарты операционных систем реального времени

2.1 Стандарт POSIX

2.2 Стандарт DO-178B

2.3 Стандарт ARINC-653

2.4 Стандарт OSEK

2.5 Стандарты безопасности

3. Краткие характеристики распространённых операционных систем реального времени

3.2 QNX Neutrino RTOS

3.5 RTX (расширение реального времени для Windows NT)

3.6 INtime (расширение реального времени для Windows NT)

3.8 MicroWare OS-9

3.11 Nucleus RTOS

Заключение

Библиографический список

Введение

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

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

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

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

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

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

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

1. Операционные системы реального времени

Операционная система реального времени -- это тип операционной системы.

Есть много определений термина. Самые распространённые из них:

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

*Стандарт POSIX 1003.1 даёт определение: «Реальное время в операционных системах -- это способность операционной системы обеспечить требуемый уровень сервиса в определённый промежуток времени»;

*Операционная система, реагирующая в предсказуемое время на непредсказуемое появление внешних событий;

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

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

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

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

Мартин Тиммерман (директор компании «Real-Time Consult и Real-Time User"s Support International (RTUSI)», обеспечивающей аппаратно-программную поддержку и занимающейся разработкой проектов систем реального времени) сформулировал следующие необходимые требования для ОСРВ:

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

*операционная система должна обладать понятием приоритета для потоков;

*операционная система должна поддерживать предсказуемые механизмы синхронизации;

*операционная система должна обеспечивать механизм наследования приоритетов;

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

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

1.1 Типы ОСРВ

Принято различать системы мягкого (soft) и жесткого (hard) реального времени.

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

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

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

1.2 Структура ОСРВ

В течение последних 25-30 лет структура операционных систем (ОС) эволюционировала от монолитной к многослойной структуре ОС и далее к архитектуре клиент-сервер.

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

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

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

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

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

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

1.3 Процессы, потоки, задачи

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

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

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

1.4 Планирование, приоритеты

Главной проблемой в ОСРВ является планирование задач (scheduling), которое обеспечивало бы предсказуемое поведение системы при всех обстоятельствах. В связи с проблемами планирования в ОСРВ изучаются и развиваются два подхода - статические алгоритмы планирования (RMS - Rate Monotonic Scheduling) и динамические алгоритмы планирования (EDF - Earliest Deadline First).

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

*процесс должен быть завершен за время его периода;

*процессы не зависят друг от друга;

*каждому процессу требуется одинаковое процессорное время на каждом интервале;

*у непериодических процессов нет жестких сроков;

*прерывание процесса происходит за ограниченное время.

Процессы выполняются в соответствии с приоритетами. При планировании RMS предпочтение отдается задачам с самыми короткими периодами выполнения.

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

Во всех системах реального времени требуется политика планирования, управляемая дедлайнами (deadline-driven scheduling). Однако этот подход находится в стадии разработки.

Обычно в ОСРВ используется планирование с приоритетами, прерывающими обслуживание, которое основано на RMS. Приоритетное прерывание обслуживания (preemption) является неотъемлемой составляющей ОСРВ, т.к. в системе реального времени должны существовать гарантии того, что событие с высоким приоритетом будет обработано перед событием более низкого приоритета. Все это ведет к тому, что ОСРВ нуждается не только в механизме планирования на основе приоритетов, прерывающих обслуживание, но также и в соответствующем механизме управления прерываниями. Более того, ОСРВ должна быть способна запрещать прерывания, когда необходимо выполнить критический код, который нельзя прерывать. Длительность обработки прерываний должна быть сведена к минимуму.

ОСРВ должна обладать развитой системой приоритетов. Во-первых, это требуется потому, что система сама может рассматриваться как набор серверных приложений, подразделяющихся на потоки, и несколько высоких уровней приоритетов должно быть выделено системным процессам и потокам. Во-вторых, в сложных приложениях необходимо все потоки реального времени помещать на разные приоритетные уровни, а потоки не реального времени помещать на один уровень (ниже, чем любые потоки реального времени). При этом потоки не реального времени можно обрабатывать в режиме циклического планирования (RRS - round-robin scheduling), при котором каждому процессу предоставляется квант времени процессора, а когда квант заканчивается, контекст процесса сохраняется, и он ставится в конец очереди. Во многих ОСРВ для планирования задач на одном уровне используется RRS. Приоритетный уровень 0 обычно используется для холостого режима.

При планировании на основе приоритетов необходимо решить две обязательные проблемы:

*обеспечить выполнение процесса с наивысшим приоритетом,

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

Для борьбы с инверсией приоритетов в ОСРВ часто используется механизм наследования приоритетов, однако при этом приходится отказываться от планирования на основе RMS, поскольку приоритеты становятся динамическими.

1.5 Память

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

*Модель без защиты - системное и пользовательское адресные пространства не защищены друг от друга, используется два сегмента памяти: для кода и для данных, при этом от системы не требуется никакого управления памятью, не требуется MMU (memory management unit - специальное аппаратное устройство для поддержки управления виртуальной памятью);

*Модель защиты система/пользователь - системное адресное пространство защищено от адресного пространства пользователя, системные и пользовательские процессы выполняются в общем виртуальном адресном пространстве, при этом требуется MMU. Защита обеспечивается страничным механизмом защиты. Различаются системные и пользовательские страницы. Пользовательские приложения никак не защищены друг от друга. Процессор находится в режиме супервизора, если текущий сегмент имеет уровень 0, 1 или 2. Если уровень сегмента - 3, то процессор находится в пользовательском режиме. В этой модели необходимы четыре сегмента - два сегмента на уровне 0 (для кода и данных) и два сегмента на уровне 3. Механизм страничной защиты не добавляет накладных расходов, т.к. защита проверяется одновременно с преобразованием адреса, которое выполняет MMU; при этом ОС не нуждается в управлении памятью.

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

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

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

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

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

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

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

1.6 Прерывания

При описании управления прерываниями обычно различают две процедуры, а именно:

*программа обработки прерывания (ISR - interrupt servicing routine) - программа низкого уровня в ядре с ограниченными системными вызовами,

*поток обработки прерывания (IST - interrupt servicing thread) - поток уровня приложения, который управляет прерыванием, с доступом ко всем системным вызовам.

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

1.7 Часы и таймеры

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

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

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

Большинство ОСРВ оперируют относительным временем. Что-то происходит “до” и “после” некоторого другого события. В системе, полностью управляемой событиями, необходим часовой механизм (ticker), т.к. там нет квантования времени (time slicing). Однако, если нужны временные метки для некоторых событий или необходим системный вызов типа “ждать одну секунду”, то нужен тактовый генератор и/или таймер.

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

Реализации в ОСРВ других концептуальных абстракций подобны их реализациям в традиционных ОС.

2. Стандарты операционных систем реального времени

2.1 Стандарт POSIX

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

Наиболее ранним и распространенным стандартом ОСРВ является стандарт POSIX (IEEE Portable Operating System Interface for Computer Environments, IEEE 1003.1). Первоначальный вариант стандарта POSIX появился в 1990 г. и был предназначен для UNIX-систем, первые версии которых появились в 70-х годах прошлого века. Спецификации POSIX определяют стандартный механизм взаимодействия прикладной программы и операционной системы и в настоящее время включают набор более чем из 30 стандартов. Для ОСРВ наиболее важны семь из них (1003.1a, 1003.1b, 1003.1c, 1003.1d, 1003.1j, 1003.21, 1003.2h), но широкую поддержку в коммерческих ОС получили только три первых.

Несмотря на явно устаревшие положения стандарта POSIX и большую востребованность обновлений стандартизации для ОСРВ, заметного продвижения в этом направлении не наблюдается.

Стандарт POSIX был создан как стандартный интерфейс сервисов операционных систем. Этот стандарт дает возможность создавать переносимые приложения. Впоследствии этот стандарт был расширен особенностями режима реального времени.

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

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

Несмотря на то, что стандарт POSIX вырос из Unix"а, он затрагивает основополагающие абстракции операционных систем, а расширения реального времени применимы ко всем ОСРВ.

К настоящему времени стандарт POSIX рассматривается как семейство родственных стандартов: IEEE Std 1003.n (где n - это номер).

2.2 Стандарт DO-178B

Стандарт DO-178B, создан Радиотехнической комиссией по аэронавтике (RTCA, Radio Technical Commission for Aeronautics) для разработки программного обеспечения (ПО) бортовых авиационных систем.

Первая его версия была принята в 1982 г., вторая (DO-178A) - в 1985-м, текущая DO-178B - в 1992 г. Готовится принятие новой версии, DO-178C. Стандартом предусмотрено пять уровней серьезности отказа, и для каждого из них определен набор требований к программному обеспечению, которые должны гарантировать работоспособность всей системы в целом при возникновении отказов данного уровня серьезности

Данный стандарт определяет следующие уровни сертификации:

*А (катастрофический),

*В (опасный),

*С (существенный),

*D (несущественный)

*Е (не влияющий).

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

2.3 Стандарт ARINC-653

Стандарт ARINC-653 (Avionics Application Software Standard Interface) разработан компанией ARINC в 1997 г. Этот стандарт определяет универсальный программный интерфейс APEX (Application/Executive) между ОС авиационного компьютера и прикладным ПО.

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

2.4 Стандарт OSEK.

Стандарт OSEK/VDX является комбинацией стандартов, которые изначально разрабатывались в двух отдельных консорциумах, впоследствии слившихся. OSEK берет свое название от немецкого акронима консорциума, в состав которого входили ведущие немецкие производители автомобилей - BMW, Bosch, Daimler Benz (теперь Daimler Chrysler), Opel, Siemens и Volkswagen, а также университет в Карлсруэ (Германия). Проект VDX (Vehicle Distributed eXecutive) развивался совместными усилиями французских компаний PSA и Renault. Команды OSEK и VDX слились в 1994г.

Первоначально проект OSEK/VDX предназначался для разработки стандарта открытой архитектуры ОС и стандарта API для систем, применяющихся в автомобильной промышленности. Однако разработанный стандарт получился более абстрактным и не ограничивается использованием только в автомобильной индустрии.

Стандарт OSEK/VDX состоит из трех частей - стандарт для операционной системы (OS), коммуникационный стандарт (COM) и стандарт для сетевого менеджера (NM). В дополнение к этим стандартам определяется некий реализационный язык (OIL). Первым компонентом стандарта OSEK является стандарт для ОС, поэтому часто стандарт OSEK ошибочно воспринимается как стандарт ОСРВ. Хотя ОС и есть большая порция данного стандарта, мощность его состоит в интеграции всех его компонент.

2.5 Стандарты безопасности

В связи со стандартами для ОСРВ стоит отметить широко известный стандарт критериев оценки пригодности компьютерных систем (Trusted Computer System Evaluation Criteria - TCSEC). Этот стандарт разработан Министерством обороны США и известен также под названием "Оранжевая книга" (Orange Book - из-за цвета обложки).

В ряде других стран были разработаны аналогичные критерии, на основе которых был создан международный стандарт “Общие критерии оценки безопасности информационных технологий” (далее просто - Общие критерии) (Common Criteria for IT Security Evaluation, ISO/IEC 15408).

В "Оранжевой книге" перечислены семь уровней защиты:

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

*В3 - домены безопасности. Этот уровень предназначен для защиты систем от опытных программистов.

*В2 - структурированная защита. В систему с этим уровнем защиты нельзя допустить проникновение хакеров.

*В1 - мандатный контроль доступа. Защиту этого уровня, возможно, удастся преодолеть опытному хакеру, но никак не рядовым пользователям.

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

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

*D - минимальная защита. Этот нижний уровень защиты оставлен для систем, которые проходили тестирование, но не смогли удовлетворить требованиям более высокого класса.

3. Краткие характеристики наиболее распространённых операционных систем реального времени

3.1 VxWorks

Операционные системы реального времени семейства VxWorks корпорации «WindRiver Systems» предназначены для разработки программного обеспечения (ПО) встраиваемых компьютеров, работающих в системах жесткого реального времени.

Операционная система VxWorks имеет архитектуру клиент-сервер и построена в соответствии с технологией микроядра, т.е. на самом нижнем непрерываемом уровне ядра (WIND Microkernel) обрабатываются только планирование задач и управление их взаимодействием/синхронизацией. Вся остальная функциональность операционного ядра - управление памятью, вводом/выводом и пр. - обеспечивается на более высоком уровне и реализуется через процессы. Это обеспечивает быстродействие и детерминированность ядра, а также масштабируемость системы.

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

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

3.2 QNX Neutrino RTOS

Операционная система QNX Neutrino Real-time Operating System (RTOS) корпорации «QNX Software Systems» является микроядерной операционной системой, которая обеспечивает многозадачный режим с приоритетами.

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

QNX Neutrino RTOS состоит из ядра, планировщика процессов (process manager) и расширенных сервисов на уровне пользователя. Как истинная микроядерная операционная система, QNX Neutrino RTOS реализует в ядре ОС только наиболее фундаментальные сервисы, такие как передача сообщений, сигналы, таймеры, планирование потоков, объекты синхронизации. Все другие сервисы ОС, драйверы и приложения выполняются как отдельные процессы, которые взаимодействуют через синхронную передачу сообщений.

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

3.3 RTEMS

RTEMS (Real-Time Executive for Multiprocessor Systems) - это некоммерческая операционная система реального времени для глубоко встраиваемых систем.

Разработчик системы компания «OAR» (On-Line Applications Research Corporation, США). Система была создана по заказу министерства обороны США для использования в системах управления ракетными комплексами. Система разрабатывается для многопроцессорных систем на основе открытого исходного кода в противовес аналогичным системам с закрытым кодом. Система рассчитана на платформы MS-Windows и Unix (GNU/Linux, FreeBSD, Solaris, MacOS X).

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

*мультизадачная обработка;

*работа в гомогенных и гетерогенных системах;

*планирование, управляемое событиями, на основе приоритетов;

*планирование с монотонной скоростью;

*взаимодействие задач и синхронизация;

*приоритетное наследование;

*управление ответным прерыванием;

*распределение динамической памяти;

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

*переносимость на многие целевые платформы.

Привязка ОСРВ к аппаратуре производится с помощью специальной библиотеки подпрограмм BSP (board support package) и специализированных подпрограмм для различных архитектур.

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

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

3.4 ChorusOS

Операционная система ChorusOS - это масштабируемая встраиваемая ОС, широко применяемая в телекоммуникационной индустрии. В настоящее время этот бренд развивается и распространяется корпорацией «Sun Microsystems».

Для компоновки и развертывания ОС ChorusOS на конкретных телекоммуникационных платформах Sun Microsystems предлагает использовать среду разработки Sun Embedded Workshop. Корпорация Sun Microsystems представляет ОС ChorusOS как встраиваемую основу для Sun"овской сети, управляемой сервисами (Sun"s Service-Driven Network). В сочетании с широким набором сервисов, полной интеграцией ПО и аппаратуры, удобным администрированием и поддержкой Java-технологии, которая посвящена нуждам телекоммуникации, ОС ChorusOS дает возможность эффективно развертывать новые возможности и приложения, поддерживая надежность и функциональность современных сетей.

ОС ChorusOS поддерживает на одной аппаратной платформе широкий набор телекоммуникационных протоколов, унаследованных приложений, приложений режима реального времени и Java-технологии.

ОС ChorusOS моделирует три сорта приложений:

*POSIX-процессы составляют большинство приложений ChorusOS, эти приложения имеют доступ к POSIX API, нескольким POSIX-подобным расширенным API и небольшому числу ограниченных системных вызовов микроядра;

*Акторы ChorusOS - эти приложения выполняются над микроядром и ограничиваются API микроядра, акторы включают драйверы, события подсистем и протокольные стеки;

*Унаследованные приложения ChorusOS поддерживаются для совместимости с приложениями, разработанными для более ранних версий ChorusOS.

Архитектура ОС ChorusOS является многослойной, основанной на компонентах (component-based). Микроядро содержит минимальный набор компонентов, необходимых для функционирования ОС. Размер резидентной часть ядра составляет 10Kb.

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

ОС ChorusOS 5.0 лежит в основе операционной среды Solaris и поддерживает следующие целевые платформы:

*UltraSPARC II (CP1500 и CP20x0);

*Intel x86, Pentium;

*Motorola PowerPC 750 и семейство процессоров 74x0 (mpc7xx);

*Motorola PowerQUICC I (mpc8xx) и PowerQUICC II (mpc8260) (микроконтроллеры).

3.5 RTX (расширение реального времени для Windows NT)

Windows NT проектировалась и, в основном, используется как универсальная ОС. Однако на рынке систем реального времени четко прослеживается тенденция использовать Windows NT и ее расширения в специализированных системах. На это существует несколько причин:

*Windows NT проектировалась согласно современным технологиям построения ОС,

*программный интерфейс приложений (API) для Win32 стал де-факто стандартом для программистов,

*графический пользовательский интерфейс (GUI) стал настолько популярным, что другие ОС стараются обеспечить похожий интерфейс,

*доступно большое количество драйверов устройств,

*доступны многие мощные интегрированные среды разработки.

Сама по себе Windows NT не подходит для применения в системах реального времени, поскольку в ней слишком мало приоритетных уровней, отсутствует механизм наследования приоритетов. Для минимизации времени обработки прерываний (ISR) в Windows NT введена концепция отложенного вызова процедуры (DPC - deferred procedure call), приоритет которой выше, чем приоритет пользовательских и системных потоков, в то время как все DPC имеют одинаковый приоритет. Это приводит к тому, что все DPC ставятся в очередь FIFO, и DPC с высокоуровневым прерыванием сможет выполниться только после того, как все другие DPC, стоящие в очереди перед ней, будут выполнены. Такие ситуации ведут к непредсказуемым временам отклика, что несовместимо с требованиями к ОСРВ. Управление памятью в Windows NT основано на механизме виртуальной памяти. Это тянет за собой защиту памяти, трансляцию адресов и подкачку, которая неприемлема в ОСРВ.

Расширение реального времени RTX (Real-Time Extension) для ОС Windows NT (разработано корпорацией «VenturСom») позволяет создавать приложения для высокоскоростного управления с детерминированным временем реакции на внешние события.

RTX глубоко интегрировано в ядро Windows NT и для обеспечения необходимых функций использует сервис Windows NT и API WIN32. Ядро реального времени (nucleus) интегрировано в ядро NT (kernel). Каждый процесс RTX выполняется как драйвер устройства ядра NT, при этом процессы не защищены друг от друга. Такая реализация приводит к быстрому переключению контекста, но небезопасна с точки зрения конфиденциальности.

3.6 INtime (расширение реального времени для Windows NT)

Система INtime является расширением реального времени Windows, которое было разработано корпорацией «Radisys Corporation», а в настоящее время поддерживается корпорацией TenAsys.

INtime комбинирует возможности ОСРВ жесткого реального времени со стандартными ОС Windows, включая Windows XP, Windows XP Embedded, Windows 2000, Windows NT и Windows NT Embedded, не требуя дополнительной аппаратуры. INtime специально разработана под архитектуру процессора x86.

INtime, в отличие от RTX, слабо связана с NT. Архитектура INtime основана на механизме аппаратного обслуживания задач (hardware tasking), которое обеспечивается процессором Intel. Получается, что два ядра выполняются на одной аппаратуре. Поскольку они разделяют одну аппаратуру, потребовались некоторые модификации NT HAL. Такой подход позволяет защитить и отделить среду выполнения и область памяти от Windows. Внутри INtime каждый процесс приложения имеет свое собственное адресное пространство. Кроме того, ядро и приложения выполняются на разных приоритетных уровнях, что позволяет защитить их друг от друга.

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

3.7 LynxOS

Операционная система LynxOS RTOS (LynuxWorks, Inc.) является операционной системой жесткого реального времени, которая предназначена для специализированной и телекоммуникационной аппаратуры. Эта ОС является полностью детерминированной и обладает POSIX-, UNIX- и Linux-совместимостью. Областями применения ОС LynxOS являются также сложные системы безопасности.

Последняя выпущенная версия этого бренда ОС LynxOS-178 2.0 характеризуется производителем как коммерческая операционная система, обеспечивающая высокий уровень надежности и оперативности, необходимый для встраиваемых приложений с особыми требованиями к безопасности. В LynxOS-178 2.0 реализована поддержка интерфейса APEX (Application/EXecutive - интерфейс приложения/управляющей программы) спецификации ARINC-653. Это означает, что данная операционная система отвечает самым строгим требованиям к безопасности и надежности электронных систем для военной и гражданской авиации. Система LynxOS-178 2.0 полностью соответствует положениям уровня А спецификации DO-178B.

ОСРВ LynxOS-178 2.0 соответствует требованиям стандартов POSIX и ARINC-653, а также DO-178B, что означает гарантию переносимости прикладного кода встраиваемых систем, многократного использования созданных программ, а также соответствие самым строгим нормативам операционных систем с повышенными требованиями к безопасности. Использование LynxOS-178 2.0 позволяет применять любые ранее сертифицированные программы и разработки.

3.8 MicroWare OS-9

Операционная система реального времени OS-9 корпорации «Microware System» является многозадачной, многопользовательской операционной системой для встраиваемых приложений, работающих в режиме реального времени. Эта система предназначена для работы в таких системах, как мобильные телекоммуникационные устройства, встраиваемые терминалы доступа в Интернет, интерактивные цифровые телевизионные приставки.

OS-9 работает на таких процессорах, как Motorola 68K, ARM/StrongARM, Intel IXP1200 Network Processor, MIPS, PowerPC, Hitachi SuperH, x86 or Intel Pentium, Intel IXC1100 XScale.

Ядро OS-9 является масштабируемым, полностью вытесняемым, поддерживает функционирование до 65535 процессов, предоставляет 65535 уровней приоритета и обеспечивает работу до 255 пользователей. Ядро OS-9 содержит более 90 системных вызовов, которые дают возможность управлять динамическим режимом диспетчеризации, распределением памяти, межпроцессорной коммуникацией и т.д. - вплоть до управления встраиваемым в ядро ОС режимом экономичного потребления питания.

Корпорация Microware одной из первых лицензировала Java для встраиваемых приложений и является лидером по предложению разнообразных средств и приложений в рамках OS-9 для различных классов устройств.

В качестве интегрированной кросс-среды разработки приложений для OS-9 корпорация Microware разработала среду Hawk, которая функционирует на платформе MS Windows NT.

3.9 OSE RTOS

Операционная система реального времени OSE RTOS, разработанная в корпорации «ENEA», имеет ядро с приоритетным планированием. Это ядро сильно оптимизировано для обеспечения высокой производительности и достаточно компактно для использования во встраиваемых системах. OSE имеет архитектуру, управляемую сообщениями, с простыми системными вызовами. Передача сообщений в OSE служит концептуальным шлюзом в распределенных многопроцессорных встраиваемых системах. Задачи посылают сообщения друг другу напрямую через ОС без поддержки очередей, почтовых ящиков или других промежуточных механизмов. OSE RTOS поддерживает подкачку, дублирование, динамическое обновление кода и многие коммуникационные протоколы.

Архитектура OSE RTOS основана на многослойной модели.

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

В OSE RTOS разделение процессов понимаются как динамические и статические: статические процессы создаются ядром, когда система стартует, и существуют на всем протяжении существования системы, динамические процессы создаются и уничтожаются во время выполнения.

3.10 Windows CE

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

Windows CE имеет ограничение на физическую память - 512MB. Microsoft ввел это ограничение для того, чтобы Windows CE могла выполняться на большом диапазоне встраиваемых процессоров без проблем совместимости, поскольку некоторые из этих процессоров способны управлять физической памятью в 512MB. Windows CE реализует страничное управление виртуальной памятью. Размер страницы зависит от платформы, но, по возможности, используется размер в 4KB. Есть возможность запретить страничную организацию, что важно для систем реального времени. В этом режиме модуль перед выполнением целиком загружается в память. Тогда страничная подкачка (paging) не повлияет на выполнение приложения.

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

3.11 Nucleus RTOS

Операционная система Nucleus, разработанная корпорацией «Accelerated Technology», предназначена для встраиваемых приложений.

Nucleus является кросс-системой, т.е. программный продукт создается на одной программно-аппаратной платформе, а выполняется на другой.

ОСРВ Nucleus поставляется вместе с открытым кодом.

Ядро ОСРВ Nucleus, Nucleus PLUS, обеспечивает многозадачную обработку, является переносимым и масштабируемым. Ядро реализовано как библиотека функций на языке C.

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

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

Заключение

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

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

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

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

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

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

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

Библиографический список

1. Бурдонов И.Б., Косачёв А.С., Пономаренко В.Н. Операционные системы реального времени. Препринт: Института системного программирования РАН. Иркутск, 2006.

2. Олифер В.Г., Олифер Н.А. Сетевые операционные системы: Учебник для вузов. 2-е изд.- СПБ.: Питер, 2008. - 669 с.: ил.

3. www.ru.wikipedia.org

4. www.intuit.ru

Подобные документы

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

контрольная работа , добавлен 09.03.2013


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

реферат , добавлен 28.12.2007


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

курсовая работа , добавлен 17.12.2015


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

реферат , добавлен 11.12.2011


Обзор требований проблемной области. Особенности управления задачами. Исполнительные системы реального времени. Программирование на уровне микропроцессоров. Модели и методы предметной области. Реализация прототипа системы реального времени.

курсовая работа , добавлен 15.02.2005


Планирование задач в операционной системе реального времени. Основные виды планирования применительно к задачам реального времени. Выбор приемлемого алгоритма планирования при проектировании RTS. Статическое прогнозирование с использованием таблиц.

контрольная работа , добавлен 28.05.2014


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

курсовая работа , добавлен 19.01.2015


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

курсовая работа , добавлен 18.05.2014


Понятие и функции операционной системы. Основная особенность операционных систем реального времени. Работа с электронными таблицами. Фильтрация записей в таблице MS Excel. Установка пользовательского автофильтра в оборотную ведомость движения товаров.

контрольная работа , добавлен 21.11.2013


Сущность и принцип работы операционной системы, правила и преимущества ее использования. Возможности различных операционных систем, их сильные и слабые стороны. Сравнительная характеристика систем Unix и Windows NT, их потенциал и выполняемые задачи.

Отделение техники и технологий

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

Введение

1. Разработка интерфейса

2. Руководящие принципы

3. Парадигмы

1) Парадигмы интерфейса пользователя

2) Парадигмы пользователя

3) Парадигмы данных

4. Интерфейс системных вызовов

5. Реализация.

6. Структура системы

7. Многоуровневые системы

8. Экзоядра

9. Системы клиент-сервер

10. Расширяемые системы

11. Потоки ядра

12. Механизм и политика

13. Ортогональность

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

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

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

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

18. Косвенность

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

20. Рентабельность

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

22. Проверка на ошибки

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

24. Кэширование

25. Подсказки

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

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

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

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

30. Роль опыта

31. Тенденции и проектирование ОС

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

34. Параллельные и распределенные системы

35. Мультимедиа

Заключение

Введение

В среде разработчиков операционных систем ходит множество изустных преданий о том, что такое хорошо и что такое плохо, однако на удивление малое количество из этих историй записано. Наиболее важной книгой можно назвать классический труд Фреда Брукса, в котором автор делится своим опытом проектирования и реализации операционной системы IBM OS/360. Материал выпущенного к 20-летней годовщине издания был пересмотрен, к тому же в содержание книги было включено несколько новых глав. Вероятно, единственной книгой по операционным системам, в которой серьезно обсуждается тема проектирования.

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

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

Природа проблемы проектирования

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

Чтобы проект операционной системы был успешным, разработчики должны иметь четкое представление о том, чего они хотят. При отсутствии цели очень трудно принимать последующие решения. Чтобы этот вопрос стал понятнее, полезно взглянуть на два языка программирования, PL/I и С++. Язык PL/I был разработан корпорацией IBM в 60-е годы, так как поддерживать одновременно FORTRAN и COBOL и слушать при этом за спиной ворчание ученых о том, что Algol лучше, чем FORTRAN и COBOL вместе взятые, было невыносимо. Поэтому был создан комитет для создания нового языка, удовлетворяющего запросам всех программистов: PL/I. Этот язык обладал некоторыми чертами языка FORTRAN, некоторыми особенностями языка COBOL и некоторыми свойствами языка Algol. Проект потерпел неудачу, потому что ему недоставало единой концепции. Проект представлял собой лишь набор свойств, конфликтующих друг с другом, к тому же язык PL/I был слишком громоздким и неуклюжим, чтобы программы на нем можно было эффективно компилировать.

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

Чего же хотят разработчики операционных систем? Очевидно, ответ варьируется от системы к системе и будет разным для встроенных систем и серверных систем

Для универсальных операционных систем основными являются следующие четыре пункта:

1. Определение абстракций.

2. Предоставление примитивных операций.

3. Обеспечение изоляции.

4. Управление аппаратурой.

Ниже будет рассмотрен каждый из этих пунктов.

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

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

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

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

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

Почему так сложно спроектировать операционную систему?

Закон Мура гласит, что аппаратное обеспечение компьютера увеличивает свою производительность в 100 раз каждые десять лет. Никто, к сожалению, так и не сформулировал ничего подобного для программного обеспечения. Никто и не говорит, что операционные системы вообще совершенствуются с годами. В самом деле, можно утверждать, что некоторые из них даже стали хуже в определенных аспектах (таких как надежность), чем, например, операционная система UNIX Version 7 образца 70-х годов.

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

Во-первых, операционные системы стали крайне громоздкими программами. Никто в одиночку не может, засев за персональный компьютер на несколько месяцев, написать операционную систему. Все современные версии UNIX превосходят 1 млн строк исходного текста. Операционная система Windows 2000 состоит из 29 млн строк кода. Ни один человек на Земле не способен понять даже одного миллиона строк, не говоря уже о 29 миллионах. Если вы создаете продукт, который ни один из разработчиков не может даже надеяться понять целиком, не удивительно, что результаты часто оказываются далеки от оптимальных.

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

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

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

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

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

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

Разработка интерфейса

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

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

Руководящие принципы

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

Принцип 1. Простота.

Простой интерфейс легче понять и реализовать без ошибок. Всем разработчикам систем следует помнить эту знаменитую цитату французского летчика и писателя Антуана де Сент-Экзюпери:

Совершенство достигается не тогда, когда уже больше нечего добавить, а когда больше нечего убавить. Этот принцип утверждает, что лучше меньше, чем больше, по крайней мере, применительно к операционным системам. Другими словами, этот принцип может быть выражен следующей аббревиатурой, предлагающей программисту, в чьих мыслительных способностях возникают сомнения, не усложнять систему: KISS (Keep It Simple, Stupid).

Принцип 2. Полнота.

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

Другими словами, операционная система должна выполнять то, что от нее требуется, но не более того. Если пользователю нужно хранить данные, операционная система должна предоставлять для этого некий механизм. Если пользователям необходимо общаться друг с другом, операционная система должна предоставлять механизм общения и т. д. В своей речи по поводу получения награды Turing Award один из разработчиков систем CTSS и MULTICS Фернандо Корбато объединил понятия простоты и полноты и сказал:

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

Парадигмы

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

Реализация в первую очередь интерфейса системных вызовов представляет собой проектирование снизу вверх. Здесь вопросы заключаются в том, какие функции нужны программистам. В действительности для поддержки графического интерфейса пользователя требуется не так уж много специальных функций. Например, оконная система под названием X Windows, используемая в UNIX, представляет собой просто большую программу на языке С, которая обращается к клавиатуре, мыши и экрану с системными вызовами read и write. Оконная система X Windows была разработана значительно позже операционной системы UNIX, но для ее работы не потребовалось большого количества изменений в операционной системе. Это подтверждает тот факт, что система UNIX обладает полнотой в достаточной степени.

Парадигмы интерфейса пользователя.

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

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

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

Парадигмы исполнения.

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

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

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

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

Парадигмы данных.

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

Первая карта представляла собой инструкцию для оператора. Он должен был достать из шкафа бобину номер 781 и установить ее на накопителе 8. Вторая карта являлась командой операционной системе запустить только что откомпилированную с языка FORTRAN программу, отображая INPUT (означающий устройство чтения перфокарт) на логическую ленту 1, дисковый файл MYDATA на логическую ленту 2, принтер OUTPUT на логическую ленту 3, перфоратор PUNCH на логическую ленту 4 и физический накопитель на магнитной ленте ТАРЕ08 на логическую ленту 5.

Синтаксис языка FORTRAN позволяет читать и писать логические ленты. При чтении с логической ленты 1 программа получает ввод с перфокарт. При помощи записи на логическую ленту 3 программа может вывести результаты на принтер. Обращаясь к логической ленте 5, программа может читать и писать магнитную ленту 781 и т. д. Обратите внимание, что идея магнитной ленты представляла собой всего лишь парадигму (модель) для объединения устройства чтения перфокарт, принтера, перфоратора, дисковых файлов и магнитофонов. В данном примере только логическая лента 5 была физической лентой. Все остальное представляло собой обычные файлы для подкачки данных. Это была примитивная парадигма, но она была шагом в правильном направлении.

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

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

Операционная система Windows 2000 идет в использовании этой модели еще дальше, представляя все, что есть в системе, в виде объектов. Получив дескриптор файла, процесса, семафора, почтового ящика или другого объекта ядра, процесс может выполнять с этим объектом различные действия. Эта парадигма является еще более общей, чем используемая в UNIX, и значительно более общей, чем в FORTRAN.

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

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

Интерфейс системных вызовов

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

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

exec(name. argp. envp);

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

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

Разумеется, пытаясь использовать один-единственный системный вызов для всех случаев жизни, легко дойти до крайностей. Для создания процесса в операционной системе UNIX требуется два системных вызова: fork, за которым следует exec. У первого вызова нет параметров; у второго вызова три параметра. Для сравнения: у вызова Win32 API для создания процесса, CreateProcess, 10 параметров, один из которых представляет собой указатель на структуру с дополнительными 18 параметрами. Давным-давно следовало задать вопрос: «Произойдет ли катастрофа, если мы опустим что-нибудь из этого?» Правдивый ответ должен был звучать так: «В некоторых случаях программист будет вынужден совершить больше работы для достижения определенного эффекта, зато мы получим более простую, компактную и надежную операционную систему». Конечно, человек, предлагающий версию с этими 10 + 18 параметрами, мог добавить: «Но пользователи любят все эти возможности». Возразить на это можно было бы так: «Еще больше им нравятся системы, которые используют мало памяти и никогда не ломаются». Компромисс, заключающийся в большей функциональности за счет использования большего объема памяти, по крайне мере, виден невооруженным глазом и ему можно дать оценку (так как стоимость памяти известна). Однако трудно оценить количество дополнительных сбоев в год, которые появятся благодаря внедрению новой функции. Кроме того, неизвестно, сделали бы пользователи тот же выбор, если им заранее была известна эта скрытая цена. Этот эффект можно резюмировать первым законом программного обеспечения Таненбаума:

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

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

Простота является не единственным принципом, которым следует руководствоваться при разработке системных вызовов. Следует также помнить о фразе, сказанной Б. Лэмпсоном в 1984 году: Не скрывай мощь.

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

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

С другой стороны, некоторые протоколы удаленного доступа к файлам не требуют соединений. Например, протокол NFS не требует соединений, как было показано в главе 10. Каждый вызов NFS является независимым, поэтому файлы не открываются до их чтения или записи, разумеется, файлы не нужно закрывать после чтения или записи. Всемирная паутина также не требует соединений: чтобы прочитать web-страницу, вы просто запрашиваете ее. Не требуется никаких предварительных настроек (TCP-соединение все-таки требуется, но оно представляет собой более низкий уровень протокола; протокол HTTP, используемый для доступа к самой web-странице, не требует соединений).

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

Другой вопрос, возникающий при проектировании интерфейса системных вызовов, заключается в его открытости. Список системных вызовов, определяемых стандартом POSIX, легко найти. Эти системные вызовы поддерживаются всеми системами UNIX, как и небольшое количество других вызовов, но полный список всегда публикуется. Корпорация Microsoft, напротив, никогда не публиковала список системных вызовов Windows 2000. Вместо этого публикуются функции интерфейса Win32 API, а также вызовы других интерфейсов; эти списки содержат огромное количество библиотечных вызовов (более 13 000 в Windows 2000), но только малое их число является настоящими системными вызовами. Аргумент в пользу открытости системных вызовов заключается в том, что программистам становится известна цена использования функций. Функции, исполняемые в пространстве пользователя, выполняются быстрее, чем те, которые требуют переключения в режим ядра. Закрытость системных вызовов также имеет свои преимущества, заключающиеся в том, что в результате достигается гибкость в реализации библиотечных процедур. То есть разработчики операционной системы получают возможность изменять действительные системные вызовы, сохраняя при этом работоспособность прикладных программ.

Реализация

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

Структура системы

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

Многоуровневые системы

Разумный подход, установившийся с годами, заключается в создании многоуровневых систем. Система THE, разработанная Э. Дейкстрой, была первой многоуровневой системой. У операционных систем UNIX (см. рис. 10.2) и Windows 2000 также есть многоуровневая структура, но уровни в них в большей степени представляют собой способ описания системы, чем фактический руководящий принцип, использованный при ее построении.

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

На уровне 4 мы обнаружим драйверы устройств, каждый из которых работает как отдельный поток, со своим состоянием, счетчиком команд, регистрами и т. д., возможно (но не обязательно), в адресном пространстве ядра. Такое устройство может существенно упростить структуру ввода-вывода, потому что когда возникает прерывание, оно может быть преобразовано в системный вызов unlock на мьютексе и обращение к планировщику, чтобы (потенциально) запустить новый готовый поток, который был блокирован мьютексом. Этот подход используется в системе MINIX, но в операционных системах UNIX, Linux и Windows 2000 обработчики прерываний реализованы как независимая часть системы, а не потоки, которые сами могут управляться планировщиком, приостанавливаться и т. д. Поскольку основная сложность любой операционной системы заключается во вводе-выводе, заслуживает внимания любой способ сделать его более удобным для обработки и более инкапсулированным.

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

Экзоядра

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

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

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

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

Системы клиент-сервер

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

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

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

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

Главная проблема такого подхода, и проблема микроядер вообще, заключается в снижении производительности, вызываемом дополнительными переключениями контекста. Однако практически вся работа по созданию микроядер была выполнена много лет назад, когда центральные процессоры были значительно медленнее. Сегодня не так уж много приложений, использующих каждую каплю мощности процессора, которые не могут смириться с малейшей потерей производительности. В конце концов, когда работает текстовый редактор или web-браузер, центральный процессор простаивает около 90 % времени. Если операционная система, основанная на микроядре, превращает систему с процессором, работающем на частоте 900 МГц, в надежную систему, аналогичную по производительности системе с частотой 800 МГц, мало кто из пользователей станет жаловаться. Большинство пользователей были просто счастливы всего несколько лет назад, когда приобрели свой предыдущий компьютер с потрясающей тогда частотой процессора в 100 МГц.

Расширяемые системы

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

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

Потоки ядра

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

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

Механизм и политика

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

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

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

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

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

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

Ортогональность

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

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

Понятие ортогональности также встречается в операционных системах в различных формах. Одним из примеров является системный вызов 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, потребуется выполнить следующие обращения к диску:

Чтобы просто определить номер 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, занявшийся впоследствии научной деятельностью, рассматривает вопрос, почему так трудно построить большую операционную систему . Когда большинство программистов встречаются с его утверждением, что специалисты, работающие над большими проектами, могут за год произвести всего лишь 1000 строк отлаженного кода, они удивляются, не прилетел ли профессор Брукс из космоса, с планеты Баг. В конце концов, большинство из них помнит, как они создавали программу из 1000 строк всего за одну ночь. Как же этот объем исходного текста может составлять годовую норму для любого программиста, чей IQ превышает 50?

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

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

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

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

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

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

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

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

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

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

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

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

Роль опыта

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

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

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

Это наблюдение отчетливо видно на примере пары систем 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 страниц. Работать с обычными таблицами страниц такого размера будет непросто, поэтому потребуется другое решение. Возможно использование инвертированных таблиц страниц, однако также предлагались и другие идеи . В любом случае появление 64-разрядных операционных систем создает новую большую область исследований.

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

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

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

Параллельные и распределенные системы

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

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

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

Мультимедиа

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

Что следует оптимизировать?

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

Вот правдивая история о том, как оптимизация принесла больше вреда, чем пользы. Один из студентов автора (имени студента мы здесь называть не будем) написал программу mkfs для системы MINIX. Эта программа создает пустую файловую систему на только что отформатированном диске. На оптимизацию этой программы студент затратил около 6 месяцев. Когда он попытался запустить эту программу, оказалось, что она не работает, после чего потребовалось еще 6 дополнительных месяцев на ее отладку. На жестком диске эту программу, как правило, запускают всего лишь один раз, при установке системы. Она также только раз запускается для каждого гибкого диска – после его форматирования. Каждый запуск программы занимает около 2 с. Даже если бы работа неоптимизированной версии занимала 1 мин, то затрата такого большого времени на оптимизацию столь редко используемой программы являлась бы непроизводительным расходованием ресурсов.

Лозунг, применимый к оптимизации производительности, мог бы звучать так: лучшее – враг хорошего

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

Литература:

Кузнецов Ю.В. «Теория операционных систем».