Protothread и кооперативная многозадачность

Продолжаем изучать планирование маленьких потоков. Я уже рассказала про два средства в ядре Linux, которые часто используются для отложенной обработки прерываний. Сегодня речь пойдет о совсем другой сущности — protothread Adam Dunkels, которые хоть и выбиваются из ряда, но в контексте рассматриваемой темы совсем не лишние.

А также:

1. Многозадачность в ядре Linux: прерывания и tasklet’ы


2. Многозадачность в ядре Linux: workqueue


3. 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(!(c)) 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 на новом ассемблере в этот момент — лишняя головная боль. Для использования же только легковесных потоков этого не требуется.

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.