Основные идеи и понятия

Мы приступаем к рассмотрению политик и параметров планирования применительно к использованию процессоров потоками управления (процессами), готовыми к выполнению. Эта тема уже затрагивалась в курсе [1] и предыдущих разделах данного курса, посвященных потокам управления.

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

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

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

Списки равноприоритетных потоков упорядочены, от первого элемента (головы) к последнему (хвосту). Цель политики планирования состоит в определении допустимых операций над множеством списков (например, перемещение потоков между списками и внутри них).

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

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

Другие действия (предыдущие и последующие) специфичны для установленной политики планирования. Рассмотрим их.

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

Если выполняемый поток управления вытесняется с процессора, он помещается в голову списка, соответствующего его приоритету.
Когда приостановленный (блокированный) поток управления становится готовым к выполнению, он помещается в хвост списка, соответствующего его приоритету.
Когда выполняемый поток управления вызывает функцию sched_setscheduler(), политика и приоритет планирования процесса, указанного в вызове, изменяются в соответствии со значением аргумента param (см. далее).
Когда выполняемый поток управления вызывает функцию sched_setparam(), приоритет планирования процесса, указанного в вызове, изменяется в соответствии со значением аргумента param (см. далее).
Когда выполняемый поток управления вызывает функцию pthread_setschedparam(), политика и приоритет планирования потока, указанного в вызове, изменяются в соответствии со значениями аргументов policy и param.
Когда выполняемый поток управления вызывает функцию pthread_setschedprio(), приоритет планирования потока, указанного в вызове, изменяется в соответствии со значением аргумента prio.
Если поток управления, чьи политика и/или приоритет планирования подверглись изменению вызовами, отличными от pthread_setschedprio(), является выполняемым или готовым к выполнению, он помещается в хвост списка, соответствующего его новому приоритету.
Если поток управления, чей приоритет планирования изменен вызовом pthread_setschedprio(), является выполняемым или готовым к выполнению, воздействие на его позицию в списке определяется направлением изменения, а именно:
- если приоритет увеличился, поток помещается в хвост соответствующего списка;
- если приоритет уменьшился, поток помещается в голову соответствующего списка;
- если приоритет не изменился, не меняется и позиция потока в списке.
Когда выполняемый поток управления вызывает функцию sched_yield(), он помещается в хвост своего списка.
Ни при каких других событиях позиция потока управления в списках при данной политике планирования не изменяется.

Допустимый диапазон приоритетов должен включать по крайней мере 32 различных значения и ограничиваться величинами, которые возвращают функции sched_get_priority_min() и sched_get_priority_max() с аргументом SCHED_FIFO.

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

Чтобы сделать планирование более справедливым по отношению к равноприоритетным процессам, можно воспользоваться политикой SCHED_RR (циклическое планирование ). Она эквивалентна SCHED_FIFO с одним исключением: когда время, в течение которого поток управления занимал процессор, становится больше или равным результату функции sched_rr_get_interval(), он перемещается в хвост соответствующего списка, а для выполнения выбирается головной поток. Таким образом, ни один из равноприоритетных потоков не сможет монополизировать процессор.

Если поток управления вытесняется, а потом возобновляет выполнение, он "дорабатывает" выделенный ему квант процессорного времени.

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

текущий поток управления контролирует процессор в течение времени Q, где Q – величина кванта выделяемого процессорного времени;
если имеется N наиболее приоритетных потоков управления, то каждый из них будет ожидать доступ к процессору не более (N – 1) * Q единиц времени (или, что почти то же, будет получать доступ к процессору с периодом N * Q).

Если накладными и непредвиденными расходами процессорного времени пренебречь нельзя, встает вопрос, на кого их списывать. От ответа на этот вопрос зависит, какое из сформулированных выше утверждений станет ложным. Если списывать расходы "на систему" и честно выделять каждому потоку управления Q единиц процессорного времени, поток может возобновить свое выполнение существенно позднее, чем через (N – 1) * Q единиц времени. Обычно для приложений реального времени это неприемлемо (не гарантируется время отклика на события, обслуживаемые потоками), поэтому расходы списывают на потоки, выделяя каждому из них не более Q единиц процессорного времени, что делает ложным первое утверждение, но гарантирует истинность второго. Разумеется, взрывная активность периферийных устройств, "отвлекающих" процессор на обработку прерываний, может практически целиком "съесть" выделяемый потоку квант времени; если подобная активность окажется периодической с тем же периодом, что и циклическое планирование, некоторые потоки рискуют оказаться на голодном пайке, поэтому стандарт добавляет еще одно требование к реализации политики SCHED_RR: ни один поток управления не должен ожидать доступ к процессору неопределенно долго.

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

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

Период пополнения бюджета характеризуется значением элемента sched_ss_repl_period описанной ранее структуры типа sched_param. Доступный бюджет вычислительных ресурсов инициализируется значением элемента sched_ss_init_budget той же структуры.

Политика спорадического планирования предусматривает ряд дополнительных условий, при выполнении которых приоритет потока управления "переключается" между значениями элементов sched_priority и sched_ss_low_priority структуры типа sched_param.

Приоритет потока определяется следующим образом. Если доступный бюджет вычислительных ресурсов положителен и число ждущих операций пополнения бюджета меньше значения элемента sched_ss_max_repl структуры типа sched_param, потоку управления присваивается приоритет sched_priority, в противном случае - sched_ss_low_priority. Если значение sched_priorityне больше, чем sched_ss_low_priority, приоритет считается неопределенным. Изменение доступного бюджета вычислительных ресурсов и, следовательно, присваиваемого приоритета, производится по следующим правилам.

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

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

выше). Операция пополнения бюджета планируется на момент времени, равный сумме времени активации и значения элемента sched_ss_repl_period структуры типа sched_param. Число операций пополнения бюджета, планируемых за один раз, не должно превышать значения sched_ss_max_repl.
Операция пополнения бюджета состоит в прибавлении в запланированное время размера пополнения к доступному бюджету вычислительных ресурсов. Если при этом бюджет станет больше начального, он уменьшается до значения sched_ss_initial_budget. Кроме того, если поток управления был готов к выполнению или выполнялся с приоритетом sched_ss_low_priority, он помещается в хвост списка sched_priority.

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

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

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

Четвертая политика планирования, которую должны поддерживать реализации, соответствующие стандарту POSIX, называется "прочей" (SCHED_OTHER).

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

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

Вообще говоря, установки и изменения атрибутов планирования могут производиться мелкими порциями, путем обращения к множеству функций вроде pthread_setschedprio(), или массово, в результате вызова одной функции с несколькими аргументами или одним структурным аргументом (такой, например, как pthread_setschedparam()). При начальной установке второй подход предпочтительнее. Из соображений минимальности интерфейса его следует распространить и на другие ситуации, что в общем и целом и сделано в стандарте POSIX-2001. Дополнительным доводом в пользу данного подхода является простота поддержания целостности конфигурации планирования, если значения отдельных характеристик могут оказаться некорректными для определенных реализаций: вызов "массовой" функции изменит все или ничего.

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

приостановка выполнения потока управления;
вытеснение потока управления;
возобновление выполнения потока управления;
вызов функции, способной изменить значения атрибутов планирования потока управления (процесса);
другие события, специфичные для политики планирования и указанные в ее описании.

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

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

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

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

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

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

Содержание раздела