% vim:aw:textwidth=75
\documentclass[a4paper,12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[koi8-r]{inputenc}
\usepackage[russian]{babel}
\usepackage{indentfirst}
%\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[dvips]{graphicx}
\usepackage{wrapfig}
\usepackage[rflt]{floatflt}
%\setlength{\voffset}{-1in}
%\setlength{\topmargin}{1cm}
%\setlength{\textheight}{24.6cm}
%\setlength{\textwidth}{16cm}
\setlength{\hoffset}{0.5cm}
\sloppy
\setlength{\textheight}{625pt}
\title{Исследование характеристик планировщиков для встроенных
  микропроцессорных систем}
\begin{document}
%\pagestyle{empty}
%\section*{Титульная страница}
%\clearpage
%\section*{Задание}
%\clearpage
%\section*{Аннотация}
%\clearpage
%\section*{Annotation}
%\clearpage
%\pagestyle{plain}
\setcounter{page}{6}
%\enlargethispage{3\baselineskip}
\setlength{\textheight}{555pt}
\tableofcontents

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

\subsection{Общие сведения о планировщиках}
\subsubsection{Задачи планирования}
Во времена систем пакетной обработки, использовавших отображение
содержимого перфокарт на магнитной ленте в качестве устройства ввода,
алгоритм планирования был прост: запустить следующую задачу на ленте. С
появлением систем с разделением времени (time-sharing) алгоритм
планирования усложнился, поскольку теперь несколько задач одновременно
ожидали обслуживания. На некоторых мэйнфреймах до сих пор совмещаются
системы пакетной обработки и службы разделения времени. В результате
планировщик должен решать, запустить ли следующим пакетное задание или
предоставить процессор интерактивному пользователю за терминалом. Поскольку
время процессора является в такой системе дефицитным ресурсом, хороший
планировщик может существенно изменить ощущаемую пользователем
производительность работы и, следовательно, степень удовлетворения
пользователя. Поэтому много усилий было потрачено на разработку умных и
эффективных алгоритмов планирования.

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

\subsubsection{Обоснование целесообразности применения}
Типичная встроенная вычислительная система должна решать множество задач
одновременно, например:
\begin{itemize}
\item следить за показаниями датчиков
\item выполнять требуемые алгоритмом вычисления
\item оказывать управляющее воздействие на объект управления
\item обеспечивать интерактивное взаимодействие с оператором
\end{itemize}

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

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

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

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

У этого подхода есть такие достоинства как:
\begin{itemize}
\item малый размер кода
\item независимость от программ третьих лиц (при использовании готового
планировщика)
\item снижение требований количеству ОЗУ, ПЗУ и вычислительным ресурсам
\end{itemize}
Однако среди недостатков у него:
\begin{itemize}
\item{проблемы обеспечения сложных требований по времени}
\item{расширение функциональности приводит к значительному увеличению
сложности}
\item{сложность оценки временных интервалов работы системы в связи с
взаимозависимостями между функциями}
\end{itemize}

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

\subsection{Категории алгоритмов планирования}
В различных средах требуются различные алгоритмы планирования. Это связано
с тем, что различные операционные системы и различные приложения
ориентированы на разные задачи. Другими словами, то, для чего следует
оптимизировать планировщик, различно в разных системах. Можно выделить три
среды:
\begin{enumerate}
\item Системы пакетной обработки данных
\item Интерактивные системы
\item Системы реального времени
\end{enumerate}

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

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

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

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

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

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

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

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

Внешние события, на которые система должна реагировать, можно разделить на
\emph{периодические} (возникающие через регулярные интервалы времени) и
\emph{непериодические} (возникающие непредсказуемо). Возможно наличие
нескольких периодических потоков событий, которые система должна
обрабатывать. В зависимости от времени, затрачиваемого на обработку каждого
из событий, может оказаться, что система не в состоянии своевременно
обработать все события. Если в систему поступает $m$ периодических событий,
событие с номером $i$ поступает с периодом $P_i$, и на его обработку уходит
$C_i$ секунд работы процессора, все потоки могут быть своевременно
обработаны только при выполнении условия
$$
\sum_{i=1}^m \frac{C_i}{P_i} \leqslant 1 \textrm{.}
$$

Системы реального времени, удовлетворяющие этому условию, называются
поддающимися планированию или \emph{планируемыми}.

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

%\subsubsection{<<Мягкое>> (soft) реальное время}
%\subsubsection{<<Жесткое>> (hard) реальное время}
\subsubsection{Алгоритмы планирования для интерактивных систем}
\paragraph{Циклическое планирование}
Одним из наиболее старых, простых, справедливых и часто используемых
является алгоритм \emph{циклического планирования}. Каждому процессу
предоставляется некоторый интервал времени процессора, так называемый
\emph{квант} времени. Если к концу кванта времени процесс все еще работает,
он прерывается, а управление передается другому процессу. Разумеется, если
процесс блокируется или прекращает работу раньше, переход управления
происходит в этот момент. Реализация циклического планирования проста.
Планировщику нужно всего лишь поддерживать список процессов в состоянии
готовности. Когда процесс исчерпал свой лимит времени, он отправляется в
конец списка.

Единственным интересным моментом этого алгоритма является длина кванта.
Переключение с одного процесса на другой занимает некоторое время~---
необходимо сохранить и перезагрузить кэш памяти и~т.п. Представим, что
\emph{переключение процессов} или \emph{переключение контекста}, как его
иногда называют, занимает 1~мс, включая переключение карт памяти,
перезагрузку кэша и~т.п. Пусть размер кванта установлен в 4~мс. В таком
случае 20\% процессорного времени уйдет на администрирование~--- это
слишком много.

Для увеличения эффективности назначим размер кванта, скажем, 100~мс. Теперь
пропадает только 1\% времени. Но представьте, что будет в системе с
разделением времени, если 10 пользователей одновременно нажмут клавишу
возврата каретки. В список будет занесено 10 процессов. Если процессор был
свободен, первый процесс будет запущен немедленно, второму придется ждать
100~мс, и~т.д. Последнему процессу, возможно, придется ждать целую секунду,
если все остальные не блокируются за время кванта. Большинству
пользователей секундная задержка вряд ли понравится.

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

Вывод можно сформулировать следующим образом: слишком малый квант приведет
к частому переключению процессов и небольшой эффективности (за счет
\emph{накладных расходов}), но слишком большой квант может привести к
медленному реагированию на короткие интерактивные запросы. Значение кванта
около 20--50~мс (при \emph{стоимости} переключения 4~мс) часто является
разумным компромиссом.

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

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

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

Система может динамически назначать приоритеты для достижения своих целей.
Например, некоторые процессы сильно ограничены возможностями устройств
ввода-вывода и большую часть времени проводят в ожидании завершения
операций ввода-вывода. Когда бы ни потребовался процессор такому процессу,
его следует немедленно предоставить, чтобы процесс мог начать следующий
запрос ввода-вывода, который будет выполняться параллельно с вычислениями
другого процесса. Если заставить процесс, ограниченный возможностями
устройств ввода-вывода, длительное время ждать доступа к процессору, он
будет неоправданно долго находиться в памяти. Простой алгоритм обслуживания
процессов, ограниченных возможностями устройств ввода-вывода, состоит в
установке приоритета, равного $1/f$, где $f$~--- часть использованного в
последний раз кванта. Процесс, использовавший всего 1~мс из 50~мс кванта,
получит приоритет~50, процесс, использовавший 25~мс, получит приоритет~2, а
процесс, использовавший весь квант, получит приоритет~1.

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

\paragraph{Несколько очередей}
Один из первых приоритетных планировщиков был реализован в системе CTSS
(compatible time-shared system). Основной проблемой системы CTSS было
слишком медленное переключение процессов, поскольку в памяти компьютера
IBM~7094 мог находиться только один процесс. Каждое переключение означало
выгрузку текущего процесса на диск и считывание нового процесса с диска.
Разработчики CTSS быстро сообразили, что эффективность будет выше, если
процессам, ограниченным возможностями процессора, выделять больший квант
времени, чем если предоставлять им небольшие кванты, но часто. С одной
стороны, это уменьшит количество перекачек из памяти на диск, с другой~---
приведет к ухудшению времени отклика. В результате было разработано решение
с классами приоритетов. Процессам класса с высшим приоритетом выделялся
один квант, процессам следующего класса~--- два кванта, следующего~---
четыре кванта и~т.д. Когда процесс использовал все отведенное ему время, он
перемещался на класс ниже.

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

\paragraph{<<Самый короткий процесс --- следующий>>}
Поскольку алгоритм <<Кратчайшая задача~--- первая>> минимизирует среднее
оборотное время в системах пакетной обработки, хотелось бы использовать его
и в интерактивных системах. В известной степени это возможно. Интерактивные
процессы чаще всего следуют схеме <<ожидание команды, исполнение команды,
ожидание команды, исполнение команды\ldots>>. Если рассматривать выполнение
каждой команды как отдельную задачу, можно минимизировать общее среднее
время отклика, запуская первой самую короткую задачу. Единственная проблема
состоит в том, чтобы понять, какой из ожидающих процессов самый короткий.

Один из методов оценивается на оценке длины процесса, базирующейся на
предыдущем проведении процесса. При этом запускается процесс, у которого
оцененное время самое маленькое. Допустим, что предполагаемое время
исполнения команды равно $T_0$ и предполагаемое время следующего запуска
равно $T_1$. Можно улучшить оценку времени, взяв взвешенную сумму этих
времен: $aT_0 + (1-a)T_1$. Выбирая соответствующее значение $a$, мы можем
заставить алгоритм оценки быстро забывать о предыдущих запусках или,
наоборот, помнить о них в течении долгого времени. Взяв $a=1/2$, мы получим
серию оценок:
$$
T_0, T_0/2+T_1, T_0/4 + T_1/4 + T_2/2,T_0/8 + T_1/8 + T_2/4 + T_3/2.
$$

После трех запусков вес $T_0$ в оценке уменьшится до $1/8$.

Метод оценки следующего значения серии через взвешенное среднее предыдущего
значения и предыдущей оценки часто называют \emph{старением}. Этот метод
применим во многих ситуациях, где необходима оценка по предыдущим
значениям. Проще реализовать старение при $a=1/2$. На каждом шаге нужно
лишь добавить к текущей оценке новое значение и разделить сумму пополам
(сдвинув вправо на 1~бит).

\paragraph{Гарантированное планирование}
Принципиально другим подходом к планированию является предоставление
пользователям реальных обещаний и затем их выполнение. Вот одно обещание,
которое легко произнести и легко выполнить: если вместе с вами процессором
пользуются $n$ пользователей, вам будет предоставлено $1/n$ мощности
процессора. И в системе с одним пользователем и $n$ запущенными процессами
каждому достанется $1/n$ циклов процессора.

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

\paragraph{Лотерейное планирование}
Хотя идея обещаний пользователям и их выполнения хороша, но ее трудно
реализовать. Для более простой реализации предсказуемых результатов
используется другой алгоритм, называемый \emph{лотерейным планированием}.

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

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

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

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

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

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

\paragraph{Алгоритм планирования RMS}
Классическим примером статического алгоритма планирования реального времени
для прерываемых, периодических процессов является алгоритм RMS (Rate
Monotonic Scheduling~--- планирование с приоритетом, пропорциональным
частоте). Этот алгоритм может использоваться для процессов, удовлетворяющих
следующим условиям:
\begin{enumerate}
\item каждый периодический процесс должен быть завершен за время его
периода;
\item ни один процесс не должен зависеть от любого другого процесса;
\item каждому процессу требуется одинаковое процессорное время на каждом
интервале;
\item у непериодических процессов нет жестких сроков;
\item прерывание процесса происходит мгновенно, без накладных расходов.
\end{enumerate}

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

\paragraph{Алгоритм планирования EDF}
Другим популярным алгоритмом планирования является алгоритм EDF (Earliest
Deadline First~--- процесс с ближайшим сроком завершения в первую очередь).
Алгоритм EDF представляет собой динамический алгоритм, в отличие от
предыдущего алгоритма не требующий от процессов периодичности. Он также не
требует и постоянства временных интервалов использования центрального
процессора. Каждый раз, когда процессу требуется процессорное время, он
объявляет о своем присутствии и о своем сроке выполнения задания.
Планировщик хранит список процессов, сортированный по срокам выполнения
заданий. Алгоритм запускает первый процесс в списке, то есть тот, у
которого самый близкий по времени срок выполнения. Когда новый процесс
переходит в состояние готовности, система сравнивает его срок выполнения со
сроком выполнения со сроком текущего процесса. Если у нового процесса
график более жесткий, он прерывает работу текущего процесса.

Одно из преимуществ использования EDF по сравнению с RMS обусловлено тем,
что использование статических приоритетов работает только при не слишком
высокой загруженности центрального процессора. Было показано, что алгоритм
RMS гарантированно работает в любой системе периодических процессов при
условии
$$
\sum_{i=1}^m \frac{C_i}{P_i} \leqslant m\left( 2^{1/m} - 1\right).
$$

Для 3, 4, 5, 10, 20 и 100 процессов максимальная разрешенная загруженность
процессора составляет 0.780, 0.757, 0.743, 0.718, 0.705 и 0.696. При
$m\to\infty$ значение максимальной загруженности процессора асимптотически
стремится к $\ln2$.

Алгоритм EDF, напротив, всегда работает с любым набором процессов, для
которого возможно планирование. Коэффициент загруженности центрального
процессора для алгоритма EDF может достигать 100\%. Платой за это является
использование более сложного алгоритма.

\section{Описание алгоритмов планирования в распространенных планировщиках}
\subsection{Планировщик из состава FreeRTOS}
Для хранения информации о задачах FreeRTOS использует несколько
очередей, в частности очередь для задач, находящихся в состоянии
ожидания, очередь для задач, ожидающих перевода в состояние готовых к
исполнению, и массива очередей с задачами, готовыми к
исполнению. Число элементов этого массива равно числу приоритетов,
используемых программистом, и задается в конфигурационном файле
проекта. Выбор типа планирования также задается в этом
конфигурационном файле; эти параметры не могут быть изменены во время
исполнения.

\subsubsection{Добровольное планирование}
В каждом процессе программист должен предусмотреть точки вызова планировщика,
причем время между этими вызовами не должно быть слишком большим, так
как в противном случае переключение контекстов будет происходить
слишком редко, и некоторые процессы могут не успеть выполнить в срок
возложенные на них задачи. Активация планировщика осуществляется вызовом
функции \texttt{vPortYield}, которая для порта на ATMega
(AVR-микроконтроллер фирмы Atmel) имеет следующий вид:
\begin{verbatim}
/*
 * Manual context switch.  The first thing we do is save
 * the registers so we
 * can use a naked attribute.
 */
void vPortYield( void ) __attribute__ ( ( naked ) );
void vPortYield( void )
{
        portSAVE_CONTEXT();
        vTaskSwitchContext();
        portRESTORE_CONTEXT();

        asm volatile ( "ret" );
}
\end{verbatim}
В ней \texttt{portSAVE\_CONTEXT} и \texttt{portRESTORE\_CONTEXT} являются
платформо-зависимыми макросами для сохранения контекста процессов
(текущих значений регистров и др.), а \texttt{vTaskSwitchContext}~---
платформо-независимая функция, осуществляющая планирование:
\begin{verbatim}
void vTaskSwitchContext( void )
{
...
        /* Find the highest priority queue that contains ready
        tasks. */
        while( listLIST_IS_EMPTY(
               &( pxReadyTasksLists[ uxTopReadyPriority ] ) ) )
        {
                --uxTopReadyPriority;
        }

        /* listGET_OWNER_OF_NEXT_ENTRY walks through the list,
        so the tasks of the
        same priority get an equal share of the processor time. */
        listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB,
                &( pxReadyTasksLists[ uxTopReadyPriority ] ) );
...
}
\end{verbatim}
Данная функция реализует довольно простой алгоритм: начиная с самого
большого приоритета (\texttt{uxTopReadyPriority} изменяется при
добавлении процесса в очередь готовых к исполнению, поэтому почти всегда
содержит максимальное значение приоритета для процессов, готовых к
исполнению) ищется непустая очередь с процессом в состоянии
готовности. Макрос \texttt{listGET\_OWNER\_OF\_NEXT\_ENTRY} осуществляет
последовательную выборку элементов из очереди.

Из данного описания видно, что если в каждый момент времени
хотя бы один высокоприоритетный процесс находится в
состоянии готовности, то низкоприоритетные процессы никогда не получат
управления (за исключением случая, когда приоритет владеющего
мьютексом низкоприоритетного процесса временно повышается).
\subsubsection{Preemption}
Для реализации вытесняющей многозадачности используется следующий
механизм: один из системных таймеров настраивается на генерацию
прерывания заданное число раз в секунду, обработчик прерывания для
ATMega выглядит следующим образом:
\begin{verbatim}
#if configUSE_PREEMPTION == 1

        /*
         * Tick ISR for preemptive scheduler.  We can use a naked
         * attribute as
         * the context is saved at the start of vPortYieldFromTick().
         * The tick
         * count is incremented after the context is saved.
         */
        void SIG_OUTPUT_COMPARE1A( void ) __attribute__ ( ( signal,
                naked ) );
        void SIG_OUTPUT_COMPARE1A( void )
        {
                vPortYieldFromTick();
                asm volatile ( "reti" );
        }
#else     

        /*
         * Tick ISR for the cooperative scheduler.  All this does is
         * increment the
         * tick count.  We don't need to switch context, this can only
         * be done by
         * manual calls to taskYIELD();
         */
        void SIG_OUTPUT_COMPARE1A( void ) __attribute__ ( ( signal ) );
        void SIG_OUTPUT_COMPARE1A( void )
        {
                vTaskIncrementTick();
        }
#endif
...
/*      
 * Context switch function used by the tick.  This must be identical to 
 * vPortYield() from the call to vTaskSwitchContext() onwards.  The only
 * difference from vPortYield() is the tick count is incremented as the
 * call comes from the tick ISR.
 */     
void vPortYieldFromTick( void ) __attribute__ ( ( naked ) );
void vPortYieldFromTick( void )
{
        portSAVE_CONTEXT();
        vTaskIncrementTick();
        vTaskSwitchContext();
        portRESTORE_CONTEXT();

        asm volatile ( "ret" );
}
\end{verbatim}
Таким образом, по каждому прерыванию в случае использования
\emph{preemption} вызывается функция \texttt{vPortYieldFromTick},
аналогичная \texttt{vPortYield}, но включающая в себя увеличение
счетчика тактов (который, в свою очередь, выполняет проверку
наступления событий и может перевести к переводу процессов из
состояния ожидания в состояние готовности к исполнению, переместив их
в соответствующую очередь). Сам алгоритм планирования остается
неизменным.

\subsubsection{Оценка сложности O() алгоритма}
Так как переменная \texttt{uxTopReadyPriority} в подавляющем
большинстве случаев уже содержит приоритет готового к исполнению
процесса, а структура очереди предусматривает указатель для
последовательного обхода всех элементов, время работы планировщика
не будет зависеть от числа задач и будет фиксированным, то есть
$O(1)$.

Можно также отметить, что добавление процесса в очередь готовых к
исполнению также производится за фиксированное (причем весьма малое)
время:
\begin{verbatim}
#define prvAddTaskToReadyQueue( pxTCB ) { \
    if( pxTCB->uxPriority > uxTopReadyPriority )
        { \
                uxTopReadyPriority = pxTCB->uxPriority; \
        } \
    vListInsertEnd( ( xList * ) &( pxReadyTasksLists[
      pxTCB->uxPriority ] ), &( pxTCB->xGenericListItem ) ); \
}
\end{verbatim}
Здесь функция \texttt{vListInsertEnd} не сортирует лист, а добавляет
элемент в конец, так, что он исполнится после всех уже имеющихся в
списке.

Из рассмотрения исходного кода FreeRTOS можно сделать вывод, что
разработчикам удалось создать гибкую, легко портируемую систему, с
довольно малыми накладными расходами на планирование, при этом имеющую
довольно богатые возможности (в частности, \emph{priority
  inheritance}, наследование приоритетов, необходимое для корректной
работы мьютексов).

\subsection{Планировщик AvrX}
\emph{AvrX}~--- легковесная ОС реального времени для
AVR-микроконтроллеров. В ее состав входит планировщик, поддерживающий
до 16 уровней приоритета; процессы с одинаковым приоритетом
исполняются по очереди, планируясь добровольно; процесс с большим
приоритетом вытесняет процесс с меньшим.

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

AvrX написана на ассемблере, но ее можно применять и для написания
проектов на C. Для полной функциональности требуется всего от 700 до
1000 слов программной памяти. Время обработки системного тика~--- 234
процессорных циклов.

Планировщик AvrX работает следующим образом: для восстановления
контекста используется функция \texttt{Epilog}, которая переключает
стек на процесс, находящийся первым в очереди готовых к исполнению:
\begin{verbatim}
; _Epilog
;
; Restore previous context (kernel or user).
...
        ldi     Zl, lo8(AvrXKernelData)
        ldi     Zh, hi8(AvrXKernelData)
        BeginCritical
...
        ldd     Yh, Z+RunQueue+NextH
        ldd     Yl, Z+RunQueue+NextL
        std     Z+Running+NextH, Yh
        std     Z+Running+NextL, Yl   ; Update current running task
        adiw    Yl, 0
        breq    _IdleTask

        ldd     Xh, Y+PidSP+NextH
        ldd     Xl, Y+PidSP+NextL
        out     _SFR_IO_ADDR(SPL), Xl
        out     _SFR_IO_ADDR(SPH), Xh         ; 20 cycles
...
\end{verbatim}
Таким образом, алгоритм планирования работает за фиксированное время,
не зависящее от количества процессов, т.е. за $O(1)$. Естественно, для
работы такого алгоритма очередь \texttt{RunQueue} должна быть
соответственно отсортирована, что происходит в функции
\texttt{\_QueuePid}:
\begin{verbatim}
; _QueuePid
;
; Takes a PID and inserts it into the run queue.  The run queue is sorted
; by priority.  Lower numbers go first.  If there are multiple tasks
; of equal
; priority, then the new task is appended to the list of equals (round
; robin)
...
        _FUNCTION(_QueuePid)

_QueuePid:                              ; Kernel entry point only
        mov     Zl, p1l
        mov     Zh, p1h
        ldi     tmp1, lo8(-1)

        ldd     tmp0, Z+PidState          ; Xh = Priority & Flags
        andi    tmp0, (BV(SuspendBit) | BV(IdleBit)) ; if marked
                                             ; Suspended or idle
        brne    _qpSUSPEND

        push    Yl              ; 9/13/04
        push    Yh              ; 9/13/04

        ldd     tmp2, Z+PidPriority
        ldi     Yl, lo8(AvrXKernelData+RunQueue)
        ldi     Yh, hi8(AvrXKernelData+RunQueue)
        in      tmp0, _SFR_IO_ADDR(SREG)
        cli             ; 9/13/04
_qp00:
        inc     tmp1                    ; Tmp1 = counter of insertion
                                        ; point.
        mov     Zl, Yl                  ; 0 = head of run queue.
        mov     Zh, Yh
        ldd     Yl, Z+PidNext+NextL
        ldd     Yh, Z+PidNext+NextH     ; Z = current, X = Next
        adiw    Yl, 0
        breq    _qp01                   ; End of queue, continue
        ldd     tmp3, Y+PidPriority
        cp      tmp2, tmp3
        brsh    _qp00                   ; Loop until pri > PID to
                                        ; queue
_qp01:
        std     Z+NextH, p1h
        std     Z+NextL, p1l    ; Prev->Next = Object
        mov     Zh, p1h
        mov     Zl, p1l
        std     Z+NextH, Yh     ; Object->Next = Next
        std     Z+NextL, Yl
        pop     Yh              ; 9/13/05
        pop     Yl              ; 9/13/04
        mov     r1l, tmp1
        out     _SFR_IO_ADDR(SREG), tmp0
        ret                     ; 9/13/04
\end{verbatim}
Для экономии памяти для очередей применяется простой однонаправленный
список, поэтому при добавлении процесса в очередь требуется двигаться
от головы списка до тех пор, пока не будут пройдены все процессы с
приоритетом большим или равным добавляемому. Следовательно если
$n$~--- число процессов в очереди с приоритетом большим или равным
добавляемому, то время исполнения такого алгоритма пропроционально
$n$, т.е. сложность этого алгоритма $O(n)$.

\section{Методика исследования}
\subsection{Выбор критериев оценки для данного исследования}
\subsection{Детали практической реализации эксперимента}

\section{Результаты испытаний}
\subsection{FreeRTOS}
\subsection{AvrX}

\section{Выводы}
\subsection{Зависимость оптимальной схемы планирования от специфики задачи}
\subsection{Зависимость оптимальной схемы планирования от имеющихся
   аппаратных ресурсов}
\subsection{Возможные модификации/оптимизации планировщиков}
\subsection{Тенденции в развитии планировщиков}

\begin{thebibliography}{99}
\bibitem{tanenbaum} Таненбаум Э.: \emph{Современные операционные системы.
2-е изд.}~--- СПб.: Питер, 2002.
\bibitem{tanenbaum-os} Таненбаум Э., Вудхалл А.: \emph{Операционные
системы: разработка и реализация}~--- СПб.: Питер, 2006.
\bibitem{sauermann} Dr. J\"urgen Sauermann, Melanie Thelen: \emph{Concepts
and Implementation of Microkernels for Embedded Systems} (доступна для
  скачивания, например, с \emph{http://ihtik.lib.ru/dreamhost\_electrotehn\_4janv2007.html})
\bibitem{freertos-doc} Richard Barry: \emph{Official FreeRTOS
  documentation}~--- \emph{http://www.freertos.org/}
\bibitem{avrx-doc} Larry Barello: \emph{Official AvrX
  documentation}~--- \emph{http://www.barello.net/avrx/Theory.htm}
\end{thebibliography}

\end{document}

