Protothread и кооперативная многозадачность
Продолжаем изучать планирование маленьких потоков. Я уже рассказала про два средства в ядре Linux, которые часто используются для отложенной обработки прерываний. Сегодня речь пойдет о совсем другой сущности — protothread Adam Dunkels, которые хоть и выбиваются из ряда, но в контексте рассматриваемой темы совсем не лишние.А также:
Многозадачность в ядре Linux: прерывания и tasklet«ы Многозадачность в ядре Linux: workqueue Protothread и кооперативная многозадачность Что это и зачем все это нужно? Объединить отложенную обработку прерываний и кооперативную многозадачность в одном цикле статей я решила не случайно. Те сущности, что я рассматриваю в цикле, и идеи, которые они реализуют, имеют большое значение не только в контексте обозначенных задач, но также в целом для систем реального времени.Главным образом их объединяет вопрос планирования. Tasklet«ы, речь о которых шла в первой статье, например, работают по правилам невытесняющей многозадачности. Кстати, про кооперативную многозадачность я уже довольно подробно рассказывала в одной из предыдущих статьей.
Кооперативная многозадачность и protothread Protothread«ы — это легковесные бесстековые потоки, реализованные на чистом C. Одно из возможных применений — реализация кооперативной многозадачности, не требующей больших накладных расходов. Например, их можно использовать во встроенных системах с жестким ограничением по памяти или в узлах беспроводной сенсорной сети.На хабрахабре уже есть хорошая статья ldir про многозадачность на основе protothreads, в ней рассматривается практическая сторона вопроса: возможности библиотеки, как ее применять. Статья сопровождается интересными и показательными примерами.
Здесь же будет больше о том, как это работает. Далее в этом разделе я приведу вольный и несколько переработанных перевод информации с сайта Adam Dunkels, создателя protothreads, где подробно описана как сама библиотека, так и детали реализации, так что желающие могут насладиться оригиналом и перейти к следующему разделу.
Основные особенности и преимущества protothreads:
Реализация последовательно потока управления без использования сложных машин состояний и полной многопоточности, Использование условной блокировки внутри функций на C, Protothread«ы очень легкие, так как у них отсутствует стек, Protothread«ы могут вызывать другие функции, но не могут блокироваться внутри вызываемой функции, поэтому нужно каждую функцию, использующую блокировку, обернуть в дочерний protothread. Таким образом, используется только явная блокировка. Protothread«ы реализованы с помощью продолжений (continuation), которые представляют текущее состояние исполнения в конкретном месте в программе, но при этом не поддерживает историю вызовов и локальные переменные. Здесь нужно быть особо внимательными — использовать локальные переменные нужно очень аккуратно! Выделенного стека у protothread«ов нет, локальные переменные хранить негде. Если поток используется лишь однажды, то переменные можно объявить как статические. В противном случае можно, например, обернуть protothread в свою структуру, и хранить переменные прямо там. В общем, я хочу сказать, что нужно отдавать себе отчет в том, что неправильное использование локальных переменных может привести к непредсказуемым результатам.В рассматриваемой реализации роль состояния играет целое положительное число — текущий номер строки программы. Управление происходит с помощью switch (), наподобие того, как это происходит в устройстве Даффа и со-программах реализации Simon Tatham. Protothread«ы похожи на генераторы в Python, только предназначены они для разных целей: protothread«ы предоставляют блокировку внутри функции на C, тогда как Python предоставляет множественный выход из генератора.
Важное ограничение реализации: код внутри protothread сам не может в полной мере использовать оператор switch (). Впрочем, это ограничение можно с помощью возможностей некоторых компиляторов, например, gcc.
Вся библиотека реализована на макросах, так как макросы, в отличие от простых функций, могут изменять поток управления только лишь средствами стандартных конструкций C.
Основное API включает в себя следующие макросы:
Макрос инициализации PT_INIT, Макросы PT_BEGIN и PT_END, объявляющие начало и конец protothread, Макросы ожидания выполнения условия PT_WAIT_UNTIL и PT_WAIT_WHILE, Макросы ожидания выполнения дочерних protothread«ов PT_WAIT_THREAD и PT_SPAWN, Макросы перезапуска PT_RESTART и выхода PT_EXIT, Макрос планирования (по сути, запуска) PT_SCHEDULE, Макрос произведения значения PT_YIELD, Макросы для использования семафоров PT_SEM_INIT, PT_SEM_WAIT и PT_SEM_SIGNAL. Разберемся теперь, как работают макросы. Для начала рассмотрим программу, использующую protothread«ы. Protothread example выполняет вечный цикл, где он сначала ждет, пока счетчик достигнет определенного значения, потом выводит сообщение и сбрасывает счетчик. #include «pt.h» static int counter; static struct pt example_pt; static PT_THREAD (example (struct pt *pt)) { PT_BEGIN (pt); while (1) { PT_WAIT_UNTIL (pt, counter == 1000); printf («Threshold reached\n»); counter = 0; } PT_END (pt); } int main (void) { counter = 0; PT_INIT (&example_pt); while (1) { example (&example_pt); counter++; } return 0; } Теперь взглянем на упрощенную версию макросов, использующихся в примере: struct pt { unsigned short lc; }; #define PT_THREAD (name_args) char name_args #define PT_BEGIN (pt) switch (pt→lc) { case 0: #define PT_WAIT_UNTIL (pt, c) pt→lc = __LINE__; case __LINE__: \ if (!©) return 0 #define PT_END (pt) } pt→lc = 0; return 2 #define PT_INIT (pt) pt→lc = 0 Структура pt состоит из единственного поля lc (сокращенно от local continuation). Обратите внимание на PT_BEGIN и PT_END, которые соответственно открывают и закрывают оператор switch, а также на чуть более сложный макрос PT_WAIT_UNTIL. В нем используется встроенный макрос __LINE__, возвращающий номер текущей строки программного файла.Сравним исходную и развернутую препроцессором версии example:
static PT_THREAD (example (struct pt *pt)) { PT_BEGIN (pt); while (1) { PT_WAIT_UNTIL (pt, counter == 1000); printf («Threshold reached\n»); counter = 0; } PT_END (pt); } static char example (struct pt *pt) { switch (pt→lc) { case 0: while (1) { pt→lc = 12; case 12: if (!(counter == 1000)) return 0; printf («Threshold reached\n»); counter = 0; } } pt→lc = 0; return 2; } Protothread example теперь выглядит как обычная функция на C. Возвращаемое значение используется для того, чтобы определить статус protothread: заблокирован ли он в ожидании чего-то, завершен, вышел, или сгенерировал очередное значение. PT_BEGIN макрос содержит инструкцию case 0, таким образом, код, идущий сразу после этого макроса, будет исполняться первым, ведь начальное значение pt→lc и есть 0.Посмотрите, во что развернулся макрос PT_WAIT_UNTIL. Полю pt→lc теперь присваивается 12, это номер строки, и тут же появляется case 12 — благодаря этому switch точно знает, куда прыгать. В случае, если условие не выполнено, функция возвращает 0, что означает, что поток ожидает (в самой библиотеки все эти константы вынесены). В следующий раз, когда в main вызовется example (), выполнение, соответственно, продолжится с case 12, то есть с проверки, выполнено ли условие ожидания. Как только счетчик достигнет 1000, условие станет истинным, и example () теперь не вернет 0, а напечатает сообщение и обнулит счетчик. Дальше, как положено, переходим в начало тела цикла.
В одной из предыдущих статей я приводила код примитивного кооперативного планировщика (раздел «Невытесняющий планировщик с сохранением порядка вызовов»). Сделав незначительные изменения, можно адаптировать его под protothread«ы. Это довольно просто, поэтому код я приводить не буду. Но желающим предлагаю поиграться.
Сравнение Напоследок предлагаю сравнить tasklet, workqueue и protothread. На самом деле, конечно, с одной стороны не очень корректно сравнивать protothread со средствами обработки bottom-half прерываний — все-таки они созданы для разных задач, нельзя так просто подменить одно другим. С другой стороны, workqueue тоже несколько выбивается из тройки: в отличие от остальных, он работает по правилам вытесняющего планирования, область применения у него куда шире.Сравнение я привожу скорее для того, чтобы извлечь полезные идеи.
А вот и сравнительная таблица:
Tasklet Workqueue Protothreads Наличие своего стека Нет — обрабатываются как softirq (на специально выделенном общем для всех обработчиков стеке, по крайней мере в Linux на x86) Да — исполняются на стеке worker-потоков, число которых сильно меньше, чем число задач Нет Скорость Быстрые — минимальная дополнительная обработка Быстрые, но не как tasklet«ы, требуется переключение контекста, когда worker«ы сменяют друг друга Очень быстрые — практически нет дополнительной обработки, больше простора для оптимизации компилятором Примитивы синхронизации Отсутствуют (за исключением spinlock) Присутствуют в полном объеме Псевдо-семафоры; примитивное ожидание событий Концепция планирования Кооперативный планировщик как softirq; tasklet«ы вытесняются только аппаратными прерываниями Worker«ы играют роль планировщика для work«ов, сами управляются основным планировщиком Кооперативный планировщик, реализуется пользователем Каждый из этих подходов имеет свои плюсы и минусы, используются они для разных задач, в контексте которых отвечают запросам пользователей.Например, в Embox у нас возникла идея реализовать свои легкие потоки, у которых не будет своего стека, подобно protothread и tasklet, при этом будут управляться основным планировщикам, как это реализовано в workqueue, а также будут хоть в каком-то виде поддерживать механизм ожидания событий (даже более того — использовать подмножество того же API, что используют и полноценные потоки). У такого подхода есть несколько привлекательных для нас применений:
Замена механизм отложенной обработки прерываний; Использование только легких потоков в планировщике позволит использовать почти полноценную многозадачность даже для ограниченных по ресурсам встроенным системам; Предыдущий сценарий хорош ещё кое-чем: при портировании системы на новую процессорную архитектуру сперва хочется получить хоть сколько-нибудь работоспособную систему. Реализация полноценного context_switch на новом ассемблере в этот момент — лишняя головная боль. Для использования же только легковесных потоков этого не требуется. О том, как это у нас получилось, каких результатов мы добились, я расскажу в следующий раз, через некоторое время.
