Организация многозадачности

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

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

На самом деле, если процессор один, то задачи выполняются не одновременно, а поочередно – короткими временными отрезками. Пока выполняется одна задача, другие ожидают. Для организации ожидания обычно используются две очереди (см. рис.3):

• очередь готовых для исполнения задач;

• очередь задач, заблокированных отсутствием необходимых ресурсов.

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

Рис. 3. Граф многозадачности

Существуют два основных способа организации многозадачности:

• кооперативный;

• вытесняющий.

Кооперативная многозадачность – режим работы операционной системы, при котором различные задачи сами принимают решения о передаче управления друг другу в те моменты времени, когда им это «удобно». Точнее, текущая задача отдает управление операционной системе, а уж та извлекает другую задачу из очереди и отдает ей управление. (Примечание: передача управления другой задаче могут также происходить по инициативе пользователя или внешнего устройства, возбудившего аппаратное прерывание.) С одной стороны, при правильном проектировании программного обеспечения с учетом всех влияющих факторов такой подход позволяет добиваться высокой реактивности СРВ на внешние события, предсказуемости ее поведения и эффективного использования ресурсов ЭВМ. С другой стороны, это усложняет процесс разработки, налагает повышенные требования на квалификацию разработчика, служит потенциальным источником ошибок, уменьшает устойчивость системы. В частности, «зависание» одной задачи приводит к невозможности передачи управления следующей задаче и, как следствие, к отказу всей системы.

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

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

Для управления последовательностью выполнения задач (т.е. порядком размещения в очереди) им присваиваются числовые приоритеты. Чем выше приоритет, тем ближе к голове очереди располагается задача. Основное правило: если в очереди появляется задача с приоритетом выше, чем приоритет исполняющейся в настоящий момент задачи, то текущая задача немедленно прекращает выполнение, а выполняться начинает новая, более приоритетная задача. Алгоритм, в соответствии с которым операционная система назначает приоритеты и передает управление от одной задачи к другой, называется «дисциплиной диспетчеризации».

Для исследования корректности и эффективности дисциплин диспетчеризации используют модель, которая рассматривает задачи трех типов:

• спорадические – необходимость выполнения, которых возникает в случайные моменты времени;

• периодические - необходимость выполнения, которых возникает в моменты времени, повторяющиеся через равные интервалы;

• фоновые – задачи, которые выполняются по мере наличия свободного процессорного времени.

Рис. 4. Периодические и спорадические задачи

На рисунке:

• Ti – период повторения i-ой задачи;

• Ci – полное время, за которое i-я задача выполняет свою работу (например, открывает/закрывает вентиль трубопровода);

• Di≤Ti – предельный срок завершения i-ой задачи, превышение его недопустимо;

• ∆t – квант времени, выделяемый каждой задаче для непрерывного выполнения.

Если запущены только «периодические» задачи, то существует критерий корректности системы реального времени, основанный на вычислении «коэффициента загруженности процессора»:

Интерпретация значений критерия:

• при µ<1 система работает корректно, есть свободное время для выполнения «спорадических» и «фоновых задач»;

• при µ=1 система работает корректно, но лишнего времени нет;

• при µ>1 система не корректна, задачи не успевают выполняться в указанные строки.

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

Эффективность системы реального времени зависит и от использованной дисциплины диспетчеризации.

1. Дисциплина Round Robin (RR, «карусельная», «круговорот») – наиболее проста. Предполагается, что все задачи имеют равные и постоянные приоритеты, соответственно, очередь устроена по правилу: «FIFO - первый пришел, первый вышел».

Данная дисциплина не позволяет учитывать «важность» задач.

2. Дисциплина Rate Monotonic (RM) - алгоритм с монотонно возрастающей частотой выполнения задач. Правила:

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

• чем меньше период Ti повторения задачи, тем более высокий приоритет она имеет;

• приоритеты назначаются в момент запуска задачи и остаются постоянными весь срок ее работы.

Рис. 6. Пример работы в режиме «RM»

Для дисциплины RM критерий корректности имеет вид µ ≤ N ⋅(2^1/N −1).

3. Дисциплина Earliest Deadline First (EDF) – алгоритм приоритетности раннего завершения. Правила:

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

• более высокий приоритет получает та задача, которой осталось

меньше времени до ее предельного срока завершения Di.

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

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

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