Планирование задач в операционных системах реального времени

6 июня 2018

В своем блоге Колин Уоллс (Colin Walls), эксперт в области микроэлектроники и встроенного ПО компании Mentor Graphics, рассказывает о типах планировщиков, используемых в операционных системах реального времени. Представляем перевод этой статьи.

---

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

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

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

Обобщая, я могу выделить пять типов планировщика.

«Выполнение до завершения» (Run to completion, RTC)

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

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

«Карусель» (Round robin, RR)

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

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

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

«Квант времени» (Time slice [TS])

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

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

Временной интервал с фоновой задачей (TSBG)

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

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

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

Планировщик задач по приоритетам (Priority, PRI)

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

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

В коммерческих ОСРВ, таких как ОСРВ Nucleus, обычно используется схема планирования приоритетов, но допускается выполнение нескольких задач на каждом уровне приоритета. Затем используется механизм «кванта времени» для распределения процессорного времени между несколькими «готовыми» задачами с одинаковым уровнем приоритета.

Источник: https://www.mentor.com/embedded-software/blog/post/task-scheduling-with-a-real-time-operating-3de6a26f-7b84-4401-bf95-d5efa81c795d

Об авторе: Колин Уоллс уже более тридцати лет работает в сфере электронной промышленности, значительную часть времени уделяя встроенному ПО. Сейчас он — инженер в области встроенного ПО в Mentor Embedded (подразделение Mentor Graphics). Колин Уоллс часто выступает на конференциях и семинарах, автор многочисленных технических статей и двух книг по встроенному ПО. Живет в Великобритании.
Профессиональный блог Колина: http://blogs.mentor.com/colinwalls,
e-mail: colin_walls@mentor.com

Теги: ОСРВ, RTOS, планировщик