\chapter[Реализация многопроцессности]{Реализация многопроцессности
на традиционных (однопроцессорных) компьютерах}

\section{Кооперативная многопроцессность}\label{ProcessSwitch}\label{CoopMT}

	По-видимому, самой простой реализацией многопроцессной системы
была бы библиотека подпрограмм, которая определяет следующие объекты:
\begin{description}
\item[\verb"struct Process;"] В тексте будет обсуждаться,
что должна представлять собой эта структура.

\item[\verb"Process * processCreate(void (*processBody)(void));"]
Создать процесс, исполняющий функцию processBody.

\item[\verb"void processSwitch();"]
Вызывается изнутри процесса. Эта функция приостанавливает
   текущий процесс и активизирует очередной процесс,
   готовый к исполнению.

\item[\verb"void processExit();"] Вызывается изнутри процесса.
Эта функция прекращает исполнение текущего процесса.
\end{description}

	Сейчас мы не обсуждаем методов синхронизации процессов и
взаимодействия между ними. Нас интересует только вопрос: что же мы должны
сделать, чтобы переключить процессы?

	Функция \verb"processSwitch" называется \term{диспетчером процессов}
или \termin{планировщиком}{scheduler} и ведет себя следующим образом:
\begin{itemize}
\item Она передает управление на следующий активный процесс.
\item Текущий процесс остается активным, и через некоторое время
снова получит управление.
\item При этом он получит управление так, как будто
\verb"processSwitch" представляла собой обычную функцию и возвратила
управление в точку, из которой она была вызвана.
\end{itemize}

\note{	Очевидно, что функцию \verb"processSwitch" нельзя честным образом
реализовать на языке высокого уровня, вроде \progname{C}, потому что это
должна быть функция, которая {\bf не возвращает [немедленно] управления
в ту точку, из которой она была вызвана}.
Она вызывается из одного процесса, а передает управление в другой.}

	Самым простым вариантом, казалось бы, будет простая передача
управления на новый процесс, например командой безусловной
передачи управления по указателю. При этом весь описатель процесса
(\verb"struct Process") будет состоять только из адреса, на который
надо передать управление. Беда только в том, что этот вариант
не будет работать.

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

	Поэтому мы приходим к следующему варианту:
\begin{itemize}
\item Каждый процесс имеет свой собственный стек вызовов.
\item При создании процесса выделяется область памяти под его стек,
и указатель на эту область помещается в дескриптор процесса.
\item Регистр-указатель стека (Stack Pointer -- \verb"SP") процесса
настраивается на эту область.
\item \verb"processSwitch" сохраняет указатель стека текущего процесса
в его дескрипторе и восстанавливает \verb"SP" из дескриптора
следующего активного процесса. При этом, когда функция
\verb"processSwitch" выполняет оператор \verb"return", она автоматически
возвращает управление в то место, из которого она была вызвана
{\it в этом процессе}, потому что адрес возврата сохраняется в стеке.
\end{itemize}

	Если система программирования предполагает, что при вызове функции
должны сохраняться определенные регистры\footnote{Как, например, C-компиляторы
для \machname{Intel 80x86} сохраняют при вызовах регистры \verb"SI" и
\verb"DI" (\verb"ESI/EDI" в \machname{i386})}, то они также
сохраняются в стеке. Поэтому предложенный нами вариант также будет
автоматически сохранять и восстанавливать все необходимые регистры.

	Понятно, что кроме стека процесса, \verb"struct Process" должна
содержать еще некоторые поля. Как минимум, она должна содержать указатель
на следующий активный процесс.
Система должна хранить указатели на текущий процесс и на конец списка.
При этом \verb"processSwitch" переставляет текущий процесс в конец списка,
а текущим делает следующий за ним в списке. Все вновь активизируемые процессы
также ставятся в конец списка.
При этом список не обязан быть двунаправленным, ведь мы извлекаем
элементы только из начала, а добавляем только в конец.
Подобным образом работает микропрограммная
реализация планировщика в транспьютерах.

	Часто в литературе такой список называют \termin{очередью процессов}%
{process queue}. Такая очередь присутствует во всех известных
авторам реализациях многопроцессных систем.
Кроме того, очереди процессов используются и при организации очередей
ожидания различных событий, например, при реализации семафоров Дийкстры.

	Планировщик, основанный на \verb"processSwitch", то есть на принципе
переключения процессов по инициативе активного процесса, реализован
в ряде экспериментальных и учебных систем.
Этот же принцип, называемый \term{кооперативной многопроцессностью},
реализован в библиотеках языков \progname{Simula 67} и \progname{Modula-2}.
\sysname{MS~Windows~3.x} также имеют средство для организации кооперативного
переключения задач -- системный вызов \verb"taskIdle" или, как это называется
в \sysname{MS~Windows}, \verb"GetNextEvent".

\note{Часто кооперативные процессы называют не процессами, а сопрограммами --
ведь они не переключаются принудительно, а вызывают друг друга. Единственное
отличие такого вызова от вызова подпрограммы состоит в том, что такой вызов
не иерархичен -- вызванная программа может вновь передать управление
исходной и остаться при этом активной.}

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

	С другой стороны, кооперативная многопроцессность имеет и серьезные
недостатки.

{\bf Во-первых,} необходимость включать в программу вызовы \verb"processSwitch"
усложняет программирование вообще и перенос программ из однопроцессных или
иначе организованных многопроцессных систем в частности.

Особенно неприятно требование регулярно вызывать \verb"processSwitch"
для вычислительных программ. Чаще всего такие программы исполняют
относительно короткий внутренний цикл, скорость работы которого определяет
скорость всей программы. Для ``плавной'' многозадачности необходимо
вызывать \verb"processSwitch" изнутри этого цикла. Делать вызов на каждом
цикле нецелесообразно, поэтому необходимо будет написать что-то вроде:

{\samepage
\begin{example}
\begin{verbatim}

int counter; // Переменная-счетчик.

  while{condition) {

    // Вызывать processSwitch каждые rate циклов.
    counter++;
    if (counter % rate == 0) processSwitch();

    .... // Собственно вычисления
  }
\end{verbatim}
\end{example}
}

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

{\bf Во-вторых,} злонамеренный процесс может захватить управление и никому
не отдавать его. Просто не вызывать \verb"processSwitch", и все.
Это может произойти не только из-за злых намерений, но и просто по ошибке.
Поэтому такая схема оказывается непригодна для многопользовательских
систем и часто не очень удобна для интерактивных однопользовательских.

{\small
Почему-то большинство коммерческих программ для \sysname{MS~Windows},
в том числе и продаваемые самой фирмой \entname{MicroSoft}, недостаточно
используют вызов \verb"GetNextEvent". Вместо этого такие программы
монопольно захватывают процессор и рисуют известные всем пользователям
этой системы ``песочные часы''. В это время система никак не реагирует
на запросы и другие действия пользователя, кроме нажатия кнопок
\verb"RESET" или \verb"CTRL-ALT-DEL".
}

{\bf В-третьих,} такая схема непригодна для систем реального времени.
Действительно, система реального времени обязана давать
{\it гарантированное} время реакции на внешнее событие.
Кооперативная система не обладает таким свойством, потому что никак не
может воздействовать на время, проходящее между вызовами \verb"processSwitch"
из пользовательской программы.

\note{Простой анализ показывает, что кооперативные многопроцессные
системы пригодны только для учебных проектов или ситуаций, когда программисту
на скорую руку необходимо склепать многопроцессное ядро. Вторая ситуация
кажется несколько странной -- зачем для серьезной работы может потребоваться
быстро склепанное ядро, если существует много готовых систем реального
времени, а также общедоступных (freeware или public domain) в виде
исходных текстов реализаций таких ядер?}

\section{Вытесняющая многопроцессность}

Все вышесказанное подводит нас к идее вызывать \verb"processSwitch"
не из пользовательской программы, а каким-то иным способом.
Например, повесить вызов такой функции на прерывание от системного
таймера.

Тогда мы получим следующую схему:
\begin{itemize}
\item Каждому процессу выделяется квант времени.
\item Если процесс не освободил процессор в течение этого кванта, то его
снимают и переставляют в конец очереди. При этом все готовые к исполнению
процессы более или менее равномерно получают управление.
\end{itemize}

Этот механизм, называемый \term{time slicing} или \term{разделение времени},
реализован в микрокоде транспьютера и практически во всех современных ОС,
включая и \sysname{OS/2}. Общим названием для всех методов переключения
задач по инициативе системы является термин \termin{вытесняющая}{preemptive}
многопроцессность. Таким образом, вытесняющая многопроцессность
противопоставляется кооперативной, где переключение происходит только
по инициативе самой задачи. Разделение времени является частным случаем
вытесняющей многопроцессности, но используется чаще всего.

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

В системе реального времени мы можем объявить процессы, которым
надо быстро реагировать, высокоприоритетными и на этом успокоиться.
Однако мы не можем так поступить с интерактивными программами в
многопользовательской или потенциально многопользовательской, как
\sysname{UNIX} на настольной машине типа \machname{AT/386} или
\machname{Sun} системе.

	Из психологии восприятия известно,
что человек начинает ощущать задержку ответа при величине этой задержки
около 100 мс. Поэтому в системах разделенного времени, рассчитанных
на интерактивную работу, квант обычно выбирают равным десяткам миллисекунд.
В старых системах, ориентированных на пакетную обработку вычислительных
задач, таких как \sysname{ОС ДИСПАК} на \machname{БЭСМ-6}, квант может
достигать десятых долей секунды или даже секунд. Это повышает эффективность
системы, но делает невозможной -- или, по крайней мере, неудобной --
интерактивную работу.

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

Действительно, пользовательская
программа может быть не готова к переключению. Например, она может в данный
момент использовать какой-то из регистров, который не сохраняется при
вызовах. Поэтому, например, обработчики аппаратных прерываний
сохраняют в стеке {\it все} используемые ими регистры. Кстати\ellipsis
Если наша функция \verb"processSwitch" будет сохранять в стеке все
регистры, то будет происходить именно то, чего мы хотим.
\verb"processSwitch" вызывается по прерыванию, сохраняет регистры
текущего процесса в текущем стеке, переключается на стек нового процесса,
восстанавливает из его стека его регистры, и новый процесс получает
управление так, будто и не терял его.

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

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

Для реализации вытеснения достаточно сохранить контекст текущего процесса
и загрузить контекст следующего активного процесса в очереди.
Необходимо предоставить также и функцию переключения процессов
по инициативе текущего процесса, аналогичную \verb"processSwitch".
Это нужно для реализации межпроцессной синхронизации. Чаще всего,
однако, вместо \verb"processSwitch" система предоставляет высокоуровневые
примитивы синхронизации, например семафоры или функции
\verb"send/receive" микроядра\footnote{Концепция микроядра подробнее
обсуждается в разделе \ref{ukernel}.}.
Вызов \verb"processSwitch" оказывается скрыт внутри таких
высокоуровневых функций.

\note{Легко понять, что вытесняющий планировщик с разделением времени
ненамного сложнее кооперативного планировщика -- и тот, и другой
реализуются несколькими десятками строк на ассемблере.
В работе \cite{VAX1} приводится полный ассемблерный текст приоритетного
планировщика системы \sysname{VAX/VMS} занимающий одну страницу%
\footnote{Авторам неизвестно, как публикация этого текста соотносится
с авторскими правами фирмы \entname{DEC}.}.}

	Понятно, что у современных процессоров, имеющих десятки регистров общего
назначения и виртуальную память, контекст процесса будет измеряться сотнями байт.
Например, у процессора \machname{VAX} контекст процессора состоит из 64
32-разрядных слов, т.е. 256 байт. При этом \machname{VAX} имеет только 16
регистров общего назначения, а большая часть остальных регистров так или
иначе относится к системе управления виртуальной памятью.

{\small
	На этом основано решающее преимущество транспьютера перед процессорами
традиционных и RISC архитектур. Дело в том, что транспьютер не имеет
диспетчера памяти, и у него вообще очень мало регистров.
В худшем случае, при переключении процессов должно сохраняться
7 32-разрядных регистров. В лучшем случае сохраняются только два регистра --
счетчик команд и статусный регистр. Кроме того, перенастраивается регистр
\verb"wptr",
который выполняет по совместительству функции указателя стека,
базового регистра сегмента статических данных процесса и указателя на
дескриптор процесса.

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

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

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

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

Все это вместе представляет собой довольно нетривиальную и красивую
конструкцию, о которой подробнее нужно читать в литературе, посвященной
этому предмету (\cite{InsideT}, \cite{CompilerGuide}).

	Благодаря такой организации транспьютер не имеет равных себе по
времени реакции на внешнее событие. На первый взгляд, микропрограммная
реализация такой довольно сложной конструкции, как планировщик,
снижает гибкость системы. В действительности, в современных системах
планировщики реализуются довольно стандартным образом, и реализация,
выполненная в транспьютере, очень близка к этому стандарту, известному
как \termin{микроядро}{microkernel}.
Кроме того, аппаратная схема взаимодействия между процессами по линкам
является достаточно мощной, и на ее основе можно смоделировать практически
любой другой механизм, например те же семафоры Дийкстры.
А все возможные накладные расходы будут скомпенсированы очень высокой
производительностью базовой системы.
}

\section{Планировщики с приоритетами}

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

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

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

	Отчасти похожим образом организован планировщик системы
\sysname{VAX/VMS}. Он имеет 32 приоритетных очереди, из которых старшие
16 называются процессами реального времени, а младшие -- разделенного.
При этом процесс реального времени исполняется всегда, когда готов к
исполнению, и в системе нет более приоритетных процессов. В этом смысле
ОС и процессы разделенного времени также вынуждены полагаться на его
порядочность. Поэтому привилегия
запускать такие процессы контролируется администратором системы.

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

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

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

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

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

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

	Предпочтительными для системы будут те программы, которые захватывают
процессор на короткое время и быстро отдают его, переходя в состояние
ожидания внешнего или внутреннего события. Поэтому таким процессам система
стремится присвоить более высокий приоритет. Если программа
ожидает завершения запроса на обращение к диску, то это также выгодно для
системы -- ведь на большинстве машин чтение и запись на диск
происходит параллельно с работой центрального процессора. \machname{IBM PC}
с контроллером \machname{IDE} или \machname{MFM} в этом смысле представляет
собой досадное исключение.

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

	При этом наиболее высокий приоритет автоматически получают
интерактивные задачи и программы, занятые интенсивным вводом-выводом.
Поэтому процессор часто оказывается свободен,
и управление получают низкоприоритетные вычислительные задания.
Поэтому системы \sysname{UNIX} и \sysname{VAX/VMS} даже при
очень высокой загрузке обеспечивают как приемлемое время реакции для
интерактивных программ, так и приемлемое астрономическое время исполнения
для пакетных заданий.
А благодаря возможности создавать процессы реального времени%
\footnote{Из ОС семейства \sysname{Unix} процессы реального времени бывают
только в \sysname{System V Release 4} и \sysname{HURD}.}
эти же ОС можно использовать и в задачах реального времени,
вроде управления атомным реактором.

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

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

{\small
	Любопытно реализовано динамическое изменение приоритета в
\sysname{OS-9}. Там каждый процесс имеет
статически\footnote{Вообще-то, процесс может повысить или понизить
свой приоритет, исполнив соответствующий системный вызов. Но система по
собственной инициативе никогда не меняет его.} определенный приоритет,
и \termin{возраст}{age} -- количество просмотров очереди с того
момента, когда этот процесс в последний раз получал управление.
Обе эти характеристики представлены 16-разрядными беззнаковыми числами.
При этом управление каждый раз получает процесс с наибольшей суммой
статического приоритета и динамически изменяющегося возраста. Если у двух
процессов такие суммы равны, то берется процесс с б\`ольшим приоритетом.
Если у них равны и приоритеты, то берется тот, который оказался ближе к
началу очереди.

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

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

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

	Стандарт \standname{POSIX} практически не накладывает ограничений на
организацию распределения приоритетов между программами. Однако наследие
ОС \sysname{UNIX} привело к тому, что в него введена команда \verb"nice" --
запустить программу с заданным приоритетом. При этом заданный приоритет
может быть только ниже приоритета запускающей задачи.

	Такая команда неявно предполагает наличие схемы динамического
распределения приоритетов, аналогичной вышеописанной. При этом
все известные авторам системы, полностью реализующие стандарт
\standname{POSIX},
(Системы семейства \sysname{Unix} и \sysname{VMS} для \machname{VAX} и
\machname{Alpha}) в действительности реализуют именно такую схему.
Отличие между \sysname{UNIX}'ами и \sysname{VMS} в этом плане состоит
только в том, что обычный \sysname{Unix} не имеет понятия процесса
реального времени.

\section[Системы с микроядром]{Монолитные системы и системы с микроядром}
\label{ukernel}

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

{\small
Те из читателей, кто занимался разработкой вирусов или \verb"TSR" для
\sysname{MS/DR~DOS}, должны быть хорошо знакомы с этой проблемой.
Вопреки хакерскому фольклору, нереентерабельность ядра \sysname{DOS}
связана вовсе не с переустановкой указателя стека при входе в обработчик
прерывания \verb"21h", а именно с тем, что ядро работает с разделяемыми
данными.
}

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

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

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

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

В наше время такая архитектура называется \term{монолитным ядром}.
Она является непосредственным потомком однопроцессных или кооперативно
многопроцессных ОС, создававшихся в конце 50-х -- начале 60-х,
и оформилась еще до того, как теоретики разработали удобные методы
синхронизации и взаимодействия процессов.

Основным недостатком монолитного ядра является вовсе не то, что это
``старая'' архитектура. Такая структура вполне приемлема для ОС
общего назначения -- большинство систем семейства \sysname{Unix}
и \sysname{OS/2} более или менее успешно е\"е используют.

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

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

{\small
Те, кто хорошо знаком с \sysname{MS/DR~DOS}, прочитав предыдущий
абзац, сразу же произнесут ответ -- \termin{DOS Busy flag}{флаг занятости ДОС}.
В нашей ситуации было бы правильнее назвать его
\termin{``Kernel Busy''}{Ядро занято}.
Речь идет о флаговой переменной, которая имеет значение \verb"TRUE",
если ядро в данный момент активно, и \verb"FALSE" все остальное время.
Пользовательская программа может получить значение флага специальным
реентерабельным системным вызовом (в \sysname{DOS} этот вызов
не был документирован вплоть до веpсии \sysname{5.0}, хотя впервые он
появился в \sysname{DOS 3.0}).

Используя этот механизм, программа РВ перед исполнением
любого системного вызова должна проверить ``Kernel Busy flag''.
Если флаг равен \verb"FALSE", то можно исполнять вызов.
Если же он равен \verb"TRUE"\ellipsis

Мы не будем детально обсуждать вопрос о том, что могла бы сделать
программа, если \verb"Kernel Busy flag" окажется равен \verb"TRUE".
Например, она могла бы скопировать сегмент данных ядра в свой внутренний
буфер, сбросить флаг, исполнить вызов и скопировать данные ядра обратно.
Пользователи ``нормальных'' ОС пришли бы в ужас от такого предложения,
хотя это довольно часто используемая техника реализации \verb"TSR"-программ
для \verb"DOS".
Более подробное обсуждение вариантов увело бы нас слишком далеко от
основной темы.
}

В первом приближении эта проблема была решена в системах типа \sysname{RT-11}.
В этой системе обращения к нереентерабельным модулям, например к подсистеме
ввода/вывода, реализованы не как вызовы, а как установка запроса в очередь.
То есть, обработка запроса начинается не сразу же после вызова, а, возможно,
через некоторое время. Поэтому мы можем поставить запрос в очередь
практически в любой момент, в том числе и во время
исполнения обработчика запросов.

\note{
Мы не можем ставить запрос во время других
операций над этой же очередью -- но время извлечения/вставки элемента
из/в очередь равно времени исполнения трех-четырех команд, а в \machname{VAX}
эта операция делается всего одной командой.
На это время можно просто запретить прерывания.
}

Более или менее похожая техника реализована во многих других ОС реального
времени и общего назначения, например в \sysname{OS-9}, \sysname{RSX-11}
и \sysname{VMS}. Развитие этой идеи и согласование ее с концепцией
гармонически взаимодействующих процессов, привело в 80-е годы к архитектуре,
известной как \termin{микроядро}{microkernel}.

Микроядро состоит из планировщика и базовых средств передачи данных
между процессами и синхронизации. В качестве таких средств могут быть
предоставлены всего четыре базовые функции:
\begin{description}
\item[\verb"port\_t create(options, ...);"] Создать порт для передачи/приема данных.
В транспьютере такой порт называется \term{линком}.
\item[\verb"int send(port\_t to, void * what, size\_t how\_much);"]
Передать в порт блок данных заданного размера.
\item[\verb"int receive(port\_t from, void * where, size\_t how\_much);"]
Получить из порта блок данных заданного размера.
Если данных еще нет, программа-получатель будет ожидать их готовности.
\item[\verb"void delete(port\_t port);"] Удалить ненужный порт.
\end{description}

Набор параметров у функций может изменяться. В первую очередь это касается
параметров функций \verb"send/receive". В нашем примере порт представляет
собой неструктурированнный поток данных, позволяющий обмениваться
сообщениями произвольного размера. В некоторых реализациях размер сообщения
может быть фиксированным. Возможны и более интересные конструкции, например,
аналоги механизма \term{рандеву} языка \progname{Ada}.

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

Микроядро получило свое название не только из-за малого количества функций,
но и из-за того, что его реализация очень компактна -- около 10 Кбайт кода
для процессора \machname{80x86}; для CISC-процессоров с рациональной
архитектурой типа \machname{MC680x0} чуть поменьше, для RISC -- чуть
побольше. В транспьютере полноценное микроядро реализовано микропрограммно,
то есть операция \verb"send" и все варианты операции \verb"receive" являются
командами процессора.

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

\note{
Сами процедуры \verb"send" и \verb"receive", разумеется, являются
нереентерабельными, но время их исполнения очень мало. На это время можно
просто запретить прерывания.
}

Строго говоря, различие между монолитными и микроядерными ОС не столь
велико, как может показаться. Дело в том, что практически все ОС имеют
в составе ядра асинхронные подсистемы, в первую очередь -- подсистему
ввода/вывода (см. раздел \ref{async_drv}).
Даже в однопроцессной \sysname{MS~DOS} дисковые кэши
типа \verb"SMARTDRV.EXE" осуществляют обмен с диском асинхронно.

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

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

Однако реальная ценность всех этих оптимизаций невелика.
Самой быстрой ОС для машин на основе процессоров \machname{i80x86}
является микроядерная система реального времени \sysname{QNX},
намного превосходящая по субъективной скорости, времени переключения
процессов и удельным накладным расходам такие монолитные ОС,
как \sysname{OS/2} и \sysname{Windows~NT}.

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

Это упрощает разработку ОС ``с нуля'', но может резко усложнить
переработку существующей системы под микроядерную архитектуру.
Это сильно зависит от структурированности кода исходной системы.

{\small Так, \entname{Unix System Laboratories} успешно переделали монолитное
ядро \sysname{UNIX System V R3} в микроядерную систему \sysname{System V R4}.
А фирма \entname{IBM}, пытаясь преобразовать монолитное ядро \sysname{OS/2}
в микроядерную систему \sysname{Workplace OS} (\sysname{WPOS}) для
\machname{PowerPC}, столкнулась с проблемами, существование которых были
вынуждены признать даже официальные представители фирмы.
}

Кроме того, архитектура микроядра резко упрощает разработку ОС для
многопроцессорных машин с общей памятью и для распределенных
многомашинных систем, не имеющих общей физической памяти.
Все, что нам нужно -- это создать на каждом процессоре (каждой машине)
копию микроядра и научиться передавать сообщения между ними.
В случае многомашинной системы сообщения могут передаваться по локальной или
даже глобальной сети. При этом пользовательские программы могут вообще не
заметить перехода к многомашинной конфигурации -- все сообщения передаются
теми же командами \verb"send" и \verb"receive", изменяется только команда
создания порта. Именно так реализовано межмашинное взаимодействие в
системе \sysname{QNX}.

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

{\small
Например, \sysname{Windows~NT} предоставляет три различных набора системных
вызовов -- Unixоподобный интерфейс POSIX-подсистемы,
интерфейс, совместимый с \sysname{MS~Windows~3.x},
известный как Win16-подсистема или \progname{WOW} (Windows~On Windows),
и оригинальный 32-разрядный системный интерфейс, во многом похожий
по структуре на \sysname{Windows~3.x}, но более богатый и изощренный,
известный как Win32-подсистема. При этом программы в POSIX-подсистеме
не могут запускать программы Win16 и Win32 и практически не могут
взаимодействовать с ними.
}

Первой из известных авторам коммерческих ОС, последовательно реализующих
архитектуру микроядра, была система \sysname{QNX}. Эта система имеет микроядро
размером около 10 Кбайт, реализующее передачу сообщений между процессами
как в пределах одной машины, так и между машинами в локальной сети.
В качестве сетевого протокола могут использоваться \protname{X.25},
\protname{SNA}, \protname{TCP/IP} или собственный сетевой протокол.

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

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

Микроядро использует ряд других современных и будущих ОС, например,
\sysname{UNIX System V R4}, \sysname{Workplace OS} фирмы \entname{IBM},
проект \sysname{HURD} и разрабатываемая новая версия \sysname{BSD UNIX}.

Напротив, система \sysname{Windows~NT} фирмы \entname{MicroSoft}, по
признанию ее разработчиков, не является полностью микроядерной.
К сожалению, авторы не смогли понять на основе общедоступной документации,
какова же ее архитектура и чем она отличается от монолитной ОС, с одной
стороны, и микроядра -- с другой.

Существует несколько общедоступных (\term{public domain}) реализаций
многопроцессорного микроядра, например, разработанное в Университете Беркли
микроядро \sysname{Mach}.
Системы \sysname{WPOS} и \sysname{HURD} разрабатываются именно на основе
этого ядра.
