Статья #3. Задачи и планирование
27 июня 2018Продолжаем серию переводов статей цикла Колина Уоллса об операционных системах реального времени.
Мы рассмотрели многозадачность, свойство операционной системы выполнять несколько квазинезависимых программ одновременно. Перед тем, как мы более подробно рассмотрим задачи, необходимо разобраться с терминами.
Мы используем слово «задача», несмотря на то, что оно не обладает точным значением. Другие термины, «поток» и «процесс», более специализированные, и следует разобраться, что они означают и чем отличаются.
Многие ОСРВ, применяемые во встраиваемых приложениях, используют многопоточную модель. Одновременно может выполняться несколько потоков, занимающих одно адресное пространство:
Это значит, что переключение контекста является, в первую очередь, переключением с одного набора регистров процессора на другой. Это просто и быстро. Потенциальная опасность заключается в том, что каждый поток имеет возможность обращаться к памяти, которая принадлежит другим потокам или самой ОСРВ.
Альтернативой является многопроцессная модель. Если выполняется несколько процессов, то у каждого процесса есть свое адресное пространство и нельзя обращаться к памяти, связанной с другими процессами или ОСРВ:
Это делает переключение контекста более сложным и затратным по времени, так как операционная система должна соответствующим образом настроить блок управления памятью, диспетчера памяти (англ. Memory Management Unit, MMU). Конечно, подобная архитектура возможна только при наличии процессора, который поддерживает MMU. Процессы поддерживаются «высокопроизводительными» ОСРВ и большинством десктопных ОС. Более того, каждый процесс может поддерживать разделение на несколько потоков, но это свойство редко используется в обычных встраиваемых приложениях.
Если доступен MMU, можно достичь компромисса:
Многие «потоковые» ОСРВ поддерживают MMU для защиты памяти от несанкционированного доступа. Таким образом, пока задача находится в контексте, «видны» только часть ее кода/данных и необходимые участки ОСРВ; остальные блоки памяти отключены, а попытка доступа вызовет нештатную ситуацию (для обычных людей)/исключение (для программистов). Это делает переключение контекста немного сложнее, но само приложение более безопасным. Такой режим можно назвать «Режим Защищенных Потоков» (Thread Protected Mode) или «Упрощенная модель процессов» (Lightweight Process Mode).
Планировщики
Как мы знаем, иллюзия одновременного исполнения задач достигается за счет выделения процессорного времени для выполнения каждой из задач. Это основная функция ядра. Способ распределения времени между задачами называется «планирование». Планировщик —программное обеспечение, которое определяет, какой следующей задаче передать управление. Логика планировщика и механизм, определяющий, когда и что должно выполняться, — алгоритм планирования. В этом разделе мы рассмотрим несколько алгоритмов планирования. Планирование задач — обширная тема, и ей посвящено множество книг. Мы предоставим необходимый минимум, чтобы понять, что конкретная ОСРВ может предложить в этом отношении.
Планировщик Run to Completion (RTC)
Планировщик RTC (run-to-completion – «выполнение до завершения») очень прост и расходует ресурсы минимально. Это идеальный сервис, если он соответствует требованиям приложения. Ниже график для системы, использующей планировщик RTC:
Планировщик по очереди вызывает функции верхнего уровня каждой задачи. Задача управляет процессором (прерывает его) до тех пор, пока функция верхнего уровня не выполнит оператор возврата return. Если ОСРВ поддерживает приостановку задач, то любые задачи, приостановленные в текущее время, не выполняются. Это тема рассматривается в статье ниже, см. «Приостановка задачи».
Большим преимуществом планировщика RTC, помимо простоты, является единый стек и портируемость кода (не требуется использование ассемблера). Минус в том, что задача может «занять» процессор, поэтому требуется тщательная разработка программы. Несмотря на то, что каждый раз задача выполняется с начала (в отличие от других планировщиков, которые позволяют начать работу с места остановки), можно добиться большей гибкости с помощью статических переменных «состояния», которые определяют логику каждого последующего вызова.
Планировщик Round Robin (RR)
Планировщик RR («карусель») похож на RTC, но более гибкий и, следовательно, более сложный:
Тем не менее, в случае планировщика RR у задачи нет необходимости выполнять оператор return в функции верхнего уровня. Она может освободить процессор в любое время, сделав вызов ОСРВ. Этот вызов приводит к тому, что ядро сохраняет контекст текущей задачи (все регистры, включая указатель стека и указатель команд) и загружает контекст следующей в очереди задачи. В некоторых ОСРВ процессор можно освободить (приостановить задачу) в ожидании доступности ресурса ядра. Это сложнее, но принцип тот же.
Гибкость планировщика RR определяется возможностью продолжать выполнение задач с момент приостановки, без внесения изменений в код приложения. За гибкость приходится платить меньшей портируемостью кода и отдельным стеком для каждой задачи.
Планировщик Time slice (TS)
Планировщик TS (time slice — «квант времени») на уровень сложнее RR. Время поделено на слоты (интервалы, кванты времени), где каждая задача может выполняться внутри назначенного ей интервала:
Помимо возможности добровольно освобождать процессор, задача может быть прервана вызовом планировщика, выполненным обработчиком прерываний системного таймера. Идея назначения каждой задаче фиксированного временного отрезка очень привлекательна (там, где это возможно): в ней легко разобраться, и она очень предсказуема.
Недостаток планировщика TS в том, что доля процессорного времени, выделенного для каждой задачи, может отличаться, в зависимости от того, приостановлены ли другие задачи и свободны ли другие части слотов:
Более предсказуемым планировщик TS может стать, если реализована работа задач в фоновом режиме. Фоновая задача может выполняться вместо любой приостановленной задачи и занимать временной интервал, когда задача освобождается (либо приостанавливает сама себя).
Очевидно, что фоновая задача не должна выполнять критичную по времени работу, так как доля процессорного времени, которое ей выделяется, абсолютно непредсказуемо: оно никогда не может быть запланировано.
Подобное решение предполагает, что каждая задача может предсказывать, когда она будет запланирована снова. Например, если у вас есть слоты на 10 мс и 10 задач, задача знает, что, если она освободится, то продолжит выполнение через 100 мс. С помощью этого решения можно добиться более гибкой настройки временных циклов (таймингов) для задач приложений. ОСРВ может предоставлять различные временные интервалы для каждой задачи. Это обеспечивает большую гибкость, но также предсказуемо, как и при фиксированном размере интервала. Другой вариант — выделить более одного интервала для одной и той же задачи, если нужно увеличить долю выделенного процессорного времени.
Приоритетный планировщик (Priority Scheduler)
Большинство ОСРВ поддерживают планирование на основании приоритетов. Идея проста: каждой задаче присваивается приоритет, и в любой момент задача, которая имеет наивысший приоритет и «готова» к выполнению, передается процессору:
Планировщик запускается, когда происходит какое-то событие (например, прерывание или вызов определенной службы ядра), которое вынуждает задачу с высоким приоритетом становиться «готовой». Есть три обстоятельства, при которых начинает работать планировщик:
- Задача приостанавливается; планировщик должен назначить следующую задачу.
- Задача подготавливает более приоритетную задачу (с помощью вызова API).
- Обработчик прерываний (англ. Interrupt Service Routine, ISR) подготавливает более приоритетную задачу. Это может быть обработчик прерываний устройства ввода/вывода или результат срабатывания системного таймера.
Количество уровней приоритета варьируется (от 8 до нескольких сотен), также разнятся пороговые значения: некоторые ОСРВ воспринимают наивысший приоритет как 0, а в других же 0 обозначает низший приоритет. Некоторые ОСРВ допускают только одну задачу на каждом уровне приоритетов; другие разрешают несколько, что значительно усложняет связанные с этим структуры данных. Многие операционные системы позволяют изменять приоритеты задач во время выполнения, что еще больше усложняет процессы.
Комбинированный планировщик (Composite Scheduler)
Мы рассмотрели несколько планировщиков, однако многие коммерческие ОСРВ предлагают еще более изощренные решения, обладающие характеристиками сразу нескольких алгоритмов. Например, ОСРВ может поддерживать несколько задач на каждом уровне приоритета, а затем использовать TS, чтобы разделить время между несколькими готовыми задачами на самом высоком уровне.
Состояния задач
В любой момент времени выполняется только одна задача. Помимо процессорного времени, затрачиваемого на обработчика прерываний (подробнее об этом в следующей статье) или планировщика, «текущей» задачей является та, чей код выполняется в настоящее время и чьи данные характеризуются текущими значениями регистра. Могут быть и другие задачи, «готовые» к запуску, и они будут учитываться планировщиком. В простой ОСРВ, использующей планировщик RTC, RR или TS, это всё. Но чаще, и всегда с Priority-планировщиком, задачи могут также находиться в приостановленном состоянии, что означает, что они не учитываются планировщиком до тех пор, пока не будут возобновлены и не перейдут в состояние «готовности».
Приостановка задачи
Приостановка задачи может быть довольно простой: задача приостанавливается самостоятельно (вызовом API) или другая задача приостанавливает ее. Через другой вызов API приостановленная задача может быть возобновлена другой задачей или обработчиком прерываний. Это «безусловная» (unconditional) или «чистая» (pure) приостановка. Некоторые операционные системы называют такую задачу «спящей».
ОСРВ может предоставлять задаче возможность приостанавливаться (засыпать) на определенный период времени, по истечении которого она возобновляется (по системным часам). Это можно назвать «засыпанием».
Если ОСРВ поддерживает «блокирующие» вызовы API, можно использовать более сложное приостановление. Такой вызов позволяет задаче запросить службу или ресурс, который она немедленно получит в случае его доступности. В противном случае она будет приостановлена до тех пор, пока он не станет доступным. Также могут быть определены таймауты, при которых задача возобновляется, если ресурс недоступен в определенный период времени.
Другие состояния задач
Многие ОСРВ поддерживают другие состояния, но понятия и определения сильно разнятся. Например, состояние «finished», которое просто означает, что внешняя функция задачи вышла (либо выполнив возврат кода, либо только закончив внешний функциональный блок). Для того чтобы завершенная задача снова начала выполняться, ее, вероятно, нужно будет каким-то образом сбросить.
Другой вариант — это состояние «terminated». Это похоже на полную приостановку (pure), за исключением того, что задача должна быть возвращена в исходное состояние для повторного запуска.
Если ОСРВ поддерживает динамическое создание и удаление задач (см. след. статью), это подразумевает другое возможное состояние задачи — «deleted».
Источник: https://www.embedded.com/design/operating-systems/4443042/Tasks-and-scheduling
Теги: ОСРВ, RTOS, планировщик
