Рисунок 1. Окно усреднения сдвигается во времени
Принципы работы планировщика потоков
Статья включает:
Планировщик потоков адаптивного партиционирования — дополнительный планировщик потоков, который гарантирует минимальную долю времени CPU группам потоков, процессов и приложений. Доля времени CPU, предоставляемая партиции, называется ее бюджетом.
Планировщик потоков адаптивного партиционирования основан на архитектуре ЗОСРВ «Нейтрино» и предназначен в первую очередь для решения двух задач проектирования встраиваемых систем:
Партиции называются «адаптивными» потому, что их содержимое динамически меняется:
Для распределения времени CPU между партициями планировщик потоков адаптивного партиционирования измеряет его среднее потребление каждой партицией при помощи окна усреднения с настраиваемой длительностью, которая по умолчанию составляет 100 миллисекунд.
Тем не менее, планировщик потоков рассчитывает среднее значение не каждые 100 миллисекунд, а значительно чаще. Окно усреднения сдвигается с периодом 1 миллисекунду, после чего расход времени CPU за последнюю миллисекунду суммируется с расходом времени CPU за предыдущие 99 миллисекунд.
От размера окна усреднения зависит длительность временного интервала, в котором планировщик потоков предоставляет партициям гарантированную долю ресурсов CPU. Размер окна усреднения можно задавать в диапазоне от 8 до 400 миллисекунд.
Он влияет на точность балансировки нагрузки, а в экстремальных случаях — на максимальные задержки готовых к выполнению потоков. Дополнительную информацию см. в главе Аспекты применения адаптивного планировщика потоков.
Поскольку перемещение окна усреднения во времени затрудняет ведение статистики в долгосрочном периоде, планировщик использует еще два окна:
Чтобы просмотреть статистику по дополнительным окнам, следует воспользоваться командой aps с параметром show -v или show -vv.
Планировщик потоков начисляет использованное время с точностью до доли такта системных часов, учитывает время выполнения потоков обработки прерываний и кода ядра от имени пользовательских потоков. Этот механизм называется микроучетом.
 | На целевых системах с процессорной архитектурой ARM микроучет осуществляется приблизительно, если система не обеспечивает достаточную точность отсчета времени. |
В адаптивном партиционировании используется справедливый планировщик потоков, который гарантирует партиции доступ к минимальному времени CPU, определяемому ее бюджетом, по запросу партиции. Этот планировщик также работает в жестком реальном времени с применением механизма вытеснения потоков на основе приоритетов. Может создаться впечатление, что эти две характеристики противоречат друг другу, однако планировщик потоков строго соблюдает приоритеты и не гарантирует бюджеты одним партициям за счет других. Более подробную информацию см. в следующих разделах:
При неполной нагрузке партиции расходуют в окне усреднения меньше времени CPU, чем предусмотрено их бюджетами. Допустим, мы создали три партиции:
Если каждой партиции требуется небольшое количество времени CPU, результат команды aps show выглядит следующим образом:
+---- CPU Time ----+-- Critical Time -- Partition name id | Budget | Used | Budget | Used --------------------+------------------+------------------- System 0 | 70% | 6.23% | 200ms | 0.000ms Pa 1 | 20% | 15.56% | 0ms | 0.000ms Pb 2 | 10% | 5.23% | 0ms | 0.000ms --------------------+------------------+------------------- Total | 100% | 27.02% |
Здесь ни одна из трех партиций не расходует свой бюджет полностью.
В этом случае планировщик потоков передает управление потоку с наивысшим приоритетом независимо от партиции, в которой он находится. Другими словами, при неполной нагрузке планировщик потоков работает в режиме жесткого реального времени, стандартном для ЗОСРВ «Нейтрино».
Свободное время возникает, когда партиция не выполняется. Планировщик потоков передает ее время другим активным партициям. При необходимости другие партиции могут использовать дополнительное время сверх своего бюджета.
Партиция должна возмещать сверхурочное время в количестве, зафиксированном планировщиком (т.е. дополнительное время, полученное в последнем окне усреднения).
Допустим, у нас имеются следующие партиции:
Поскольку партиция System не расходует время, планировщик потоков передает оставшееся время самому приоритетному потоку в системе (в данном случае — потоку с бесконечным циклом в партиции Pb). Результат выполнения команды aps show выглядит следующим образом:
+---- CPU Time ----+-- Critical Time -- Partition name id | Budget | Used | Budget | Used --------------------+------------------+------------------- System 0 | 70% | 0.11% | 200ms | 0.000ms Pa 1 | 20% | 20.02% | 0ms | 0.000ms Pb 2 | 10% | 79.83% | 0ms | 0.000ms --------------------+------------------+------------------- Total | 100% | 99.95% |
В этом примере партиция Pa получает гарантированный минимум 20%, однако все свободное время передается партиции Pb, поскольку при неполном расходовании бюджетов планировщик выбирает потоки строго по приоритету. Эта стратегия максимально соответствует критериям реального времени.
Тем не менее, в некоторых ситуациях нежелательно передавать все свободное время партиции Pb только потому, что в ней находится самый приоритетный поток. Например, в партиции Pb может быть размещено ненадежное стороннее приложение, код которого невозможно изменить.
В этом случае можно настроить планировщика потоков так, чтобы он применял более строгий алгоритм и распределял свободное время между бюджетами активных партиций, а не передавал его самому приоритетному потоку. Для этого установите флаг SCHED_APS_SCHEDPOL_FREETIME_BY_RATIO с помощью функции SchedCtl() или выполните команду aps modify -S freetime_by_ratio.
Если воспользоваться пропорциональным режимом в нашем примере, результат выполнения команды aps show будет выглядеть следующим образом:
+---- CPU Time ----+-- Critical Time -- Partition name id | Budget | Used | Budget | Used --------------------+------------------+------------------- System 0 | 70% | 0.04% | 200ms | 0.000ms Pa 1 | 20% | 65.96% | 0ms | 0.000ms Pb 2 | 10% | 33.96% | 0ms | 0.000ms --------------------+------------------+------------------- Total | 100% | 99.96% |
Эти данные показывают, что в пропорциональном режиме планировщик потоков делит свободное время между партициями Pa и Pb приблизительно 2:1, что соответствует соотношению их бюджетов.
При полной нагрузке все партиции расходуют свои бюджеты целиком. Полную нагрузку легко продемонстрировать на нашем примере: достаточно запустить циклы while( 1 ) во всех партициях. Результаты выполнения команды aps show будут выглядеть следующим образом:
+---- CPU Time ----+-- Critical Time -- Partition name id | Budget | Used | Budget | Used --------------------+------------------+------------------- System 0 | 70% | 69.80% | 200ms | 0.000ms Pa 1 | 20% | 19.99% | 0ms | 0.000ms Pb 2 | 10% | 9.81% | 0ms | 0.000ms --------------------+------------------+------------------- Total | 100% | 99.61% |
Здесь соблюдение гарантированных бюджетов партиций имеет преимущество перед соблюдением приоритетов потоков.
Когда партиции исчерпывают или превышают свои бюджеты, планировщик потоков делит время CPU между ними пропорционально их бюджетам с точностью до нескольких процентов от их размера (дополнительную информацию о точности бюджетов см. в разделе Выбор размера окна усреднения).
Планировщик может выполнять заданное множество критически важных потоков в реальном времени даже при полной нагрузке (см. раздел Критически важные потоки далее в этой главе). Тем не менее, в этом случае планирование критически важных потоков имеет преимущество перед соблюдением бюджетов.
В следующей таблице указано, как планировщик потоков делит время CPU между партициями в обычном и пропорциональном режимах:
| Состояние партиции | Обычный режим | Пропорциональный режим |
|---|---|---|
| Нагрузка < бюджет | По приоритетам | По приоритетам |
| Нагрузка > бюджет и есть свободное время | По приоритетам | Пропорционально бюджетам |
| Полная нагрузка | Пропорционально бюджетам | Пропорционально бюджетам |
| Выполнение критически важного потока при любой нагрузке | По приоритетам | По приоритетам |
| Поскольку накладные расходы планировщика не увеличиваются с количеством потоков, но могут увеличиваться с количеством партиций, рекомендуется создавать как можно меньше партиций. |
Когда поток сервера получает от клиента сообщение в соответствии со стандартным механизмом send-receive-reply, с точки зрения ЗОСРВ «Нейтрино» этот поток работает от имени клиента. По этой причине операционная система выполняет поток сервера с приоритетом клиента. Другими словами, потоки, которые принимают сообщения, наследуют приоритеты их отправителей.
Планировщик потоков расширяет этот принцип и выполняет потоки сервера в партиции потока клиента, когда сервер работает от его имени. Время получателя зачисляется на счет партиции отправителя.
Когда сервер создает новые потоки и процессы, они размещаются в партициях следующим образом:
| Чтобы запретить выполнение сервера и создаваемых им процессов и потоков в партиции клиента, необходимо установить флаг _NTO_CHF_FIXED_PRIORITY при создании канала сервера (см. ChannelCreate()). |
| Обмен сообщениями send-receive-reply является единственным механизмом взаимодействия потоков, который обеспечивает автоматическое наследование партиции клиента сервером. |
Импульсы не наследуют партицию отправителя; по умолчанию их обработчики выполняются в партиции, где изначально создан процесс. Чтобы изменить партицию, в которой обрабатывается импульс, следует выполнить команду SCHED_APS_JOIN_PARTITION функции SchedCtl(), указав идентификатор процесса и значение -1 в качестве идентификатора потока.
Критически важный поток — это поток, который может выполняться, даже если его партиция превысила бюджет (при условии, что у нее имеется резервный временной бюджет). По умолчанию ЗОСРВ «Нейтрино» автоматически обнаруживает все потоки, которые активизируются прерыванием ввода/вывода как критически важные. Разработчик также может назначать критически важные потоки с помощью функции SchedCtl().
| Поскольку любой поток можно отмечать как критически важный, для защиты системы от DOS-атак могут потребоваться превентивные меры. Дополнительную информацию см. в разделе Управление безопасностью планировщика потоков. |
Критически важные потоки выполняются в реальном времени даже при полной загрузке системы и ограниченном доступе других потоков партиции к CPU для соблюдения бюджетов. Основная идея заключается в том, что критически важные потоки могут нарушать правила бюджета своей партиции и немедленно запускаться в режиме реального времени. Для корректного функционирования этого механизма в системе не должно быть большого количества критически важных потоков.
Чтобы перевести поток в критически важный режим, можно воспользоваться структурой sigevent:
struct sigevent my_event;SIGEV_PULSE_INIT( &my_event, coid, 10, MY_SIGNAL_CODE, 6969 );
SIGEV_MAKE_CRITICAL( &my_event );
Эти действия приводят к результату только при условии, что поток, который принимает событие, выполняется в партиции с резервным бюджетом.
Чтобы аннулировать статус критически важного потока, можно воспользоваться макросом SIGEV_CLEAR_CRITICAL() при настройке структуры sigevent.
| Макросы SIGEV_CLEAR_CRITICAL() и SIGEV_MAKE_CRITICAL() устанавливают скрытый бит в поле sigev_notify field. Чтобы проверить значение поля sigev_notify структуры sigevent после ее создания и обработки макросом SIGEV_MAKE_CRITICAL(), воспользуйтесь кодом:
вместо:
|
Поток, который принимает сообщение от критически важного потока, также становится критически важным.
Разработчик может отмечать партиции как критически важные и назначать им резервные бюджеты. Резервное время дает потокам, которые обрабатывают ответственные прерывания, возможность выполняться с превышением бюджета.
Резервный бюджет задается в миллисекундах. Он определяет количество времени, которое все критически важные потоки могут использовать в рамках окна усреднения. Критически важный поток выполняется даже если бюджет CPU его раздела исчерпан, при условии, что резервный бюджет этого раздела не равен нулю.
Резервное время зачисляется в счет партиции до тех пор, пока выполняются следующие условия:
SIG_INTR(), структуры sigevent с флагом критической важности, либо принял сообщение от критически важного потока. В противном случае критическое время не начисляется, однако это не влияет на выполнение критически важных потоков. Критически важные потоки не выполняются только в случае, если исчерпан резервный бюджет их партиции (см. раздел Банкротство).
Критически важные потоки полезны и эффективны, когда их количество в системе крайне невелико; кроме того, желательно назначать им уникальные высокие приоритеты. В противном случае планировщик потоков теряет возможность гарантировать минимальные бюджеты CPU всем партициям и система работает в обычном приоритетном режиме.
Статус критически важного потока полезен, если поток имеет наивысший приоритет и в системе нет других потоков с таким же приоритетом. Критически важный поток вынужден уступать CPU обычным потокам своей партиции, если они имеют более высокий или равный приоритет, но стали готовыми к выполнению раньше, и при этом бюджет партиции исчерпан. Тем не менее, критически важный поток снова может выполняться, когда окно усреднения сдвигается и резервный бюджет партиции восстанавливается.
Критически важный поток сохраняет свой статус до тех пор, пока не становится receive-блокированным. К потоку, на счет которого зачисляется критическое время, не применяется карусельное планирование, даже если она задана его атрибутом.
| ЗОСРВ «Нейтрино» отмечает все структуры sigevent, которые возвращаются пользовательскими функциями обработки событий прерываний, как критически важные. Следовательно, все потоки обработки ввода/вывода также автоматически становятся критически важными. Этот принцип минимизирует количество изменений, которые необходимо вносить в код для управления планированием потоков партиции. Чтобы отключить указанный режим работы, следует передать параметр -c модулю procnto в файле построения загрузочного образа. |
Чтобы назначить партиции бесконечный резервный бюджет, следует задать его равным произведению количества процессоров на размер окна усреднения. Это следует делать с осторожностью во избежание проблем с безопасностью системы (см. раздел Управление безопасностью планировщика потоков).
Банкротство происходит, когда критическое время CPU, начисленное партиции, превышает ее резервный бюджет.
| Партиция System имеет бесконечный резервный бюджет и никогда не становится банкротом. |
Для проверки правильности назначенных размеров резервных бюджетов крайне важно тестировать работу системы при максимальной нагрузке. Один из методов такого тестирования заключается в выполнении потоков с циклом while ( 1 ) в каждой партиции с целью полностью израсходовать время CPU.
Считается, что банкротство всегда происходит вследствие ошибок проектирования приложений, однако пользователь может настраивать реакцию системы на него. ЗОСРВ «Нейтрино» позволяет задавать следующие политики восстановления:
SCHED_APS_MODIFY_PARTITION функции SchedCtl() или команды aps modify с ключом -B. Политика восстановления после банкротства задается с помощью утилиты aps или команды SCHED_APS_SET_PARMS функции SchedCtl().
При изменении резервного или обычного бюджета партиции уведомление о банкротстве отправляется с задержкой длительностью в два окна во избежание ложного обнаружения банкротства в случае резкого изменения бюджета партиции (например, с 90% до 1%).
| Аннулирование бюджета при банкротстве приводит к изменению резервного бюджета партиции и предотвращает повторное обнаружение банкротства на протяжении двух последующих окон. |
Для стабилизации системы в указанной ситуации планировщик потоков предоставляет всем партициям отсрочку объявления о банкротстве длительностью в два окна при отмене бюджета одной из партиций.
Если планировщик потоков работает в режиме балансировки бюджетов, приоритеты и алгоритмы планирования потоков действуют только в рамках конкретной адаптивной партиции.
Планировщик потоков поддерживает FIFO-, карусельную и спорадическое планирование, однако может:
Это происходит, если партиция потока исчерпывает бюджет, а у другой партиции имеется неизрасходованный бюджет; другими словами, планировщик потоков принимает решение о передаче управления потоку другой партиции, не дожидаясь окончания кванта времени текущего потока. Планировщик принимает это решение при каждом тактовом сигнале системных часов, периодичность которого на большинстве устройств составляет 1 миллисекунду. Квант времени равен четырем тактам системных часов.
В процессе расходования резервного бюджета потоки с карусельным алгоритмом планирования не прерываются готовыми к выполнению потоками с таким же приоритетом по окончании квантов времени.
Следует помнить о возможных ошибках при использовании FIFO-планирования. Cуществует метод взаимного исключения нескольких потоков, которые выполняют операции чтения и записи над одними и теми же данными, без использования мьютекса. Если назначить этим потокам одинаковый приоритет.
При FIFO-планировании, они не будут прерывать друг друга, поскольку в каждый момент времени может выполняться только один поток (по крайней мере, в однопроцессорной системе). Таким образом, каждый поток будет иметь монопольный доступ к общим данным на протяжении всего времени своего выполнения. Уязвимость этого метода состоит в том, что любое случайное изменение алгоритма планирования или приоритета с высокой вероятностью приведет к тому, что выполнение критической секции одного потока будет прервано другим потоком и целостность кода будет нарушена. Если потоки, которые используют описанный метод, находятся в разных партициях или могут принимать сообщения от разных партиций, их критические секции будут нарушены.
Если очередность выполнения потоков приложения определяется их приоритетами, следует всегда помещать эти потоки в одну партицию и не отправлять им сообщения из других партиций.
Пары потоков, которые должны выполняться в определенном порядке в соответствии с их приоритетами, следует всегда помещать в одну партицию и не отправлять им сообщения из других партиций.
Для решения этой проблемы необходимо управлять порядком выполнения потоков с помощью мьютексов, барьеров или импульсов. Их использование также предотвращает возникновение неполадок в приложении на многоядерной системе. В качестве временного решения можно вызвать функцию ChannelCreate() с флагом _NTO_CHF_FIXED_PRIORITY, чтобы запретить выполнение потока-адресата в партиции отправителя.
Общая рекомендация по реализации взаимного исключения — использовать в приложениях механизмы, которые не зависят от FIFO-планирования и длительности кванта.
В многоядерной системе можно одновременно использовать партиции планировщика и симметричную многопроцессорную обработку (Symmetric Multiprocessing, SMP).
Следует иметь в виду, что:
Поскольку в большинстве систем существует много потоков, наличие единственного потока в каждой партиции маловероятно, однако такая ситуация возможна в многопоточной системе.
Параметр runmask задает CPU, на которых разрешается выполнение потока. С помощью параметра runmask можно настроить потоки так, что планировщик не сможет соблюдать бюджеты из-за недостаточного количества потоков, которым разрешено выполняться на конкретном процессоре.
При наличии нескольких готовых потоков, которым разрешено выполняться на любом CPU, планировщик потоков гарантирует корректное соблюдение минимальных бюджетов всех партиций.
| На многопоточном компьютере фактическое потребление ресурсов CPU партициями может не совпадать с процентными значениями, которые сообщает планировщик потоков. Это несоответствие обусловлено тем, что на многопоточном компьютере потребление не всегда пропорционально времени независимо от типа используемого планировщика. Как правило, такая ситуация возникает, когда количество готовых к выполнению потоков в партиции недостаточно для загрузки всех псевдопроцессоров многопоточного компьютера. |
Иногда использование масок потоков и бюджетов партиций приводит к курьезным результатам.
Предположим, что на двухпроцессорном SMP-компьютере имеются две партиции:
Допустим, что система бездействует. Если запустить поток с приоритетом 10, который привязан к CPU 1 и выполняет бесконечный цикл в партиции Pa, планировщик потоков воспримет это как попытку партиции Pa монополизировать доступ к CPU 1, поскольку на его долю приходится лишь 50% суммарного процессорного времени компьютера.
Если запустить еще один поток с приоритетом 9, который также привязан к CPU 1, но находится в партиции System, планировщик потоков воспримет это как попытку партиции System монополизировать доступ к CPU 1.
Поскольку планировщик потоков не может выполнить требования обеих партиций, он отдаст CPU 1 в монопольное распоряжение партиции Pa.
Это объясняется следующим образом: когда система бездействует, планировщик потоков обнаруживает, что у обеих партиций имеется доступный для использования бюджет. Поскольку в такой ситуации планировщик потоков работает в режиме реального времени, т.е. строго по приоритетам, он запускает партицию Pa runs. Тем не менее, поскольку ресурс CPU 1 меньше, чем бюджет партиции Pa, бюджет Pa никогда не исчерпывается. Таким образом, планировщик потоков продолжает работать в режиме реального времени и никогда не запускает партицию System, поскольку она имеет более низкий приоритет.
В этом примере результаты выполнения команды aps show выглядят следующим образом:
+---- CPU Time ----+-- Critical Time -- Partition name id | Budget | Used | Budget | Used --------------------+------------------+------------------- System 0 | 50% | 0.09% | 200ms | 0.000ms Pa 1 | 50% | 49.93% | 0ms | 0.000ms --------------------+------------------+------------------- Total | 100% | 50.02% |
Партиция System не получает доступ к CPU несмотря на то, что в ней имеется готовый к выполнению поток.
Аналогичные ситуации могут возникать при наличии нескольких партиций, бюджеты которых по отдельности составляют менее 50%, а в сумме — 50% или более.
Для предотвращения таких ситуаций следует избегать бесконечных циклов, однако контролировать код сторонних программ не всегда возможно.
Для облегчения использования параметров runmask можно задавать более строгий алгоритм планирования, при котором исполнение бюджетов партиций в определенных обстоятельствах преобладает над соблюдением приоритетов.
Для этого установите флаг SCHED_APS_SCHEDPOL_BMP_SAFETY с помощью функции SchedCtl(), которая объявлена в заголовочном файле <sys/aps_sched.h>, или выполните команду aps modify -S bmp_safety.
В следующей таблице указано распределение времени в обычном режиме (с риском монополизации) и режиме с жесткой привязкой потоков (BMP-safety) на двухпроцессорном компьютере:
| Состояние партиции | Обычный режим | Режим с жесткой привязкой потоков (BMP-safety) |
|---|---|---|
| Нагрузка < бюджет / 2 | По приоритетам | По приоритетам |
| Нагрузка < бюджет | По приоритетам | Пропорционально бюджетам |
| Нагрузка > бюджет, но есть свободное время | По приоритетам¹ | Пропорционально бюджетам |
| Полная нагрузка | Пропорционально | Пропорционально бюджетам |
(¹) Когда флаг SCHED_APS_SCHEDPOL_FREETIME_BY_PRIORITY не установлен. Дополнительную информацию см. в описании команды SCHED_APS_SET_PARMS функции SchedCtl().
Если включить режим BMP-safety в указанном выше примере, планировщик потоков будет не только выполнять обе партиции System и Pa, но и распределять время CPU 1 пропорционально их бюджетам. Результат команды aps show выглядит следующим образом:
+---- CPU Time ----+-- Critical Time -- Partition name id | Budget | Used | Budget | Used --------------------+------------------+------------------- System 0 | 50% | 25.03% | 200ms | 0.000ms Pa 1 | 50% | 24.99% | 0ms | 0.000ms --------------------+------------------+------------------- Total | 100% | 50.02% |
Режим BMP-safety облегчает анализ планирования благодаря исключению ряда условий, в которых планировщик строго соблюдает приоритеты потоков.
Предыдущий раздел: перейти