Программисты C и так не избалованы возможностями языка, а разработчики встроенных систем на микроконтроллерах ограничены еще больше, зачастую их программы работают на голом железе, без поддержки ОС.
Возможность использования в С сопрограмм, генераторов, кооперативной многозадачности часто может сильно упростить программу и сэкономить силы, но эти возможности языка не очевидны и многие про них не знают.
Продолжения (contionuation) позволяют запомнить состояние выполнения программного потока (функции), и вернуться к этому месту в дальнейшем.
Используя продолжения, мы можем получить сопрограммы (coroutine), а это уже практически готовые генераторы, итераторы и кооперативная многозадачность.
Вот несколько способов реализовать продолжения на С и примеры библиотек, эти способы использующие:
- Сохранение текущего стека и регистров процессора, используя ассемблерные вставки (библиотека coro), либо стандартные POSIX функции сохранения/востановления контекста getcontext/setcontext или сохранения/восстановления стека setjmp/longjmp (библиотеки libpcl, libcoroutine, libconcurrency, libcoro).
- Хитрое применение оператора switch (известное как «устройство Даффа»).
Это, например, библиотека protothreads (каноническая версия от Adam Dunkels, и её расширенный аналог от Larry Ruane), библиотка coroutine от Simon Tatham, автора PuTTY. - Расширенния GCC «Переменные меток», (библиотека protothreads).
В статье я рассмотриваю библиотеку protothreads от Adam Dunkels. Она проста и минималистична, состоит из набора макросов в нескольких заголовочных файлах, совместима с С++. Библиотека содержит в себе всё необходимое, не имеет зависимостей от других библиотек, платформы и компилятора. Не использует динамическую память. Если у Вас gcc, библиотека предоставит дополнительные возможности благодаря применению переменных меток. В общем, эта библиотека мне показалась самой удобной для программирования встроенных приложений, где имеется большое разнообразие архитектур, компиляторов и операционных систем.
Как работает библиотека хорошо описано на её сайте, я приведу только краткое описание API и несколько примеров использования. Конечно, применение библиотеки является всего лишь «синтаксическим сахаром» и всё что она может, можно реализовать с помощью, например, конечных автоматов (собственно говоря, библиотека преобразует ваши функции в неявные конечные автоматы). Но в ряде задач библиотека сокращает объем текста программы, увеличивает линейность, ясность и, как следствие, может уменьшить время разработки и вероятность ошибок. Если Вы решаете задачу с помощью конечного автомата и у Вас десяток и более состояний, многие из них идут последовательно, то, скорее всего, protothreads Вам может сильно упростить жизнь, да и в любом случае полезно иметь альтернативу. По моему опыту, исходный код программы с использованием protothreads примерно на 20 – 50% меньше эквивалентного, написанного с использованием конечных автоматов.
Примеры, приведенные в статье, писались под Windows, работают в MinGW и Visual Studio, но внимание! В Visual Studio, в конфигурации DEBUG, библиотека protothreads, в том виде как она есть, не компилируется!
Причина в том, что макрос __LINE__ в конфигурации DEBUG в VS почему-то из константы превращается в вызов функции, это легко лечится, если в файле lc-switch.h заменить
#define LC_SET(s) s = __LINE__; case __LINE__:на
#define LC_SET(s) s = __COUNTER__+1; case (__COUNTER__):
В gcc под все платформы и процессоры библиотека работает без изменений.
Для использования библиотеки необходимо скачать и распаковать .h файлы в Ваш проект и подключить заголовок:
#include "pt.h"Итак, что мы можем получить от библиотеки:
Продолжения
Сами по себе продолжения не очень полезны, но они являются базой для других программных структур.
Функция с возможностью продолжения объявляется так:
int name(struct pt *pt [, дополнительные параметры])или с помощью макроса так:
PT_THREAD(name(struct pt *pt [, дополнительные параметры]))
аргумент pt является указателем на контекст продолжения, который тем, или иным способом хранит место, где прервалось выполнение функции.
Возвращать результат функция может через дополнительные аргументы, по ссылке.
Перед началом операторов должен быть макрос PT_BEGIN(pt), в конце потока — PT_END(pt). Если нужно выполнять какие-то действия при каждом вызове функции — они ставятся до макроса PT_BEGIN(pt). Это может быть, например, обновление значения таймера, счетчика и т.д.
Команда PT_YIELD(pt) возвращает результат и при следующем вызове функции функция продолжится со следующего оператора.
Прерывания потока (например, в случае ошибки) осуществляется макросом PT_EXIT(pt). После достижения конца потока или после прерывания(макросы PT_END(pt) и PT_EXIT(pt), перезапуска командой PT_RESTART(pt), функция «перематывается» на начало и при следующем вызове начнет работу заново.
Функция возвращает константу — причину прерывания функции: PT_WAITING — ожидание события, PT_YIELDED — возвращение значения, PT_EXITED — выход командой PT_EXIT(pt), PT_ENDED — функция дошла до конца PT_END(pt).
Перед первым использованием продолжения необходимо проинициализировать его контекст макросом PT_INIT(pt).
Переменные, которые должны сохранять свои значения между вызовами должны быть объявлены как static, либо переданы в функцию по ссылке.
Генераторы
Когда Вам нужно получить последовательность каких-нибудь данных по сложному алгоритму и способ получения каждого следующего элемента зависит от определенных условий и предыдущих значений, удобно использовать генератор.
Вот пример генерации чисел Фибоначчи:
#include "pt.h"
#include <stdio.h>
static int fib(struct pt *pt, int max, int* res) {
static int a,b;
PT_BEGIN(pt);
a=0;b=1;
while (a<max) {
*res=a;
PT_YIELD(pt);
b+=a;
a=b-a;
}
PT_END(pt);
}
int main(void)
{
int value;
struct pt pt1;
PT_INIT(&pt1);
while( fib(&pt1, 1000, &value) < PT_EXITED ){
printf("Value %dn",value);
}
return 0;
}
Сопрограммы
Классические сопрограммы — это программные потоки, которые могут передавать друг другу управление, с последующим возвратом в место прерывания. Сопрограммы используют в случае, когда среди нескольких программных потоков (функций) непонятно, что должно быть основной программой, а что подпрограммой (Кнут, I том книги «Искусство программирования»). Например, часть Вашей программы как-то производит данные, другая часть как-то их потребляет. Причем и потребитель, и производитель достаточно сложен. Когда Вы пишете программу производителя данных — Вам хочется вызывать потребление данных как функцию, когда у Вас готова часть данных. Но когда Вы программируете потребителя данных — Вам уже хочется сделать потребителя сделать основной программой, а функцию генерации вызывать, когда есть возможность данные получить и обработать. В таком случае вместо отношений программа-подпрограмма вполне уместны отношения сопрограмма-сопрограмма. Можно еще сначала все данные сгенерировать в память, а потом их все сразу потребить, но данных может быть больше чем памяти, особенно это актуально для встроенных систем. Сопрограммы тоже легко получить с помощью продолжений.
Например, нам нужно сгенерировать большое количество xml данных, затем заархивировать их, затем сохранить в файл или передать по сети. Для простоты примера реализуем только генерацию и сохранение. Различные проверки ошибок операций с памятью и файлами также опущены. makeXmlLine – наш производитель. Разбирает входное предложение и при каждом вызове генерирует строку XML. writeXmlLine – потребитель, при каждом вызове сохраняет строку в файл. сопрограммы вызываются поочередно до тех пор, пока сопрограмма производителя не закончится (вернет результат PT_EXITED).
#include "pt.h"
#include <stdio.h>
#include <string.h>
#include <malloc.h>
static int makeXmlLine(struct pt *pt, char* dst, char* src)
{
static char* text; // должна быть static чтоб значение не потерялось до выхода из функции
char * pch;
PT_BEGIN(pt);
strcpy(dst,"<?xml version="1.0" encoding="Windows-1251"?>");
PT_YIELD(pt);
strcpy(dst,"<text>");
PT_YIELD(pt);
text=strdup(src); // strtok портит исходный текст, нужно его сохранить
pch = strtok (text," ,.!?:");
while (pch != NULL){
sprintf(dst," <word>%s</word>",pch);
PT_YIELD(pt);
pch = strtok (NULL, " ,.!?:");
}
strcpy(dst,"</text>");
PT_YIELD(pt);
*dst=0; // Пустая строка будет индикатором того, что поток строк закончился
PT_YIELD(pt);
free(text);
PT_END(pt);
}
static int writeXmlLine(struct pt *pt, char* fileName, char* str)
{
static FILE* file;
PT_BEGIN(pt);
file=fopen(fileName,"w"); // Ошибки с файлами не обрабатываются для упрощения примера
while(*str){
fprintf(file,"%sn",str);
PT_YIELD(pt);
}
fclose(file);
PT_END(pt);
}
int main(void)
{
struct pt pt1,pt2;
char xmlString[128];
PT_INIT(&pt1);
PT_INIT(&pt2);
// Вызываем по очереди сопрограммы, пока не закончится текст
while (makeXmlLine(&pt1,xmlString, "Hello, world! Pleased to meet you!") < PT_EXITED)
writeXmlLine(&pt2,"file.xml",xmlString);
return 0;
}
Многозадачность
Во встраиваемых системах всегда нужно чего-то ждать — прихода данных в порт, освобождения буфера, срабатывания таймера, завершения другой операции, нажатия кнопок, выдерживания паузы и т.д. Использование многозадачности позволяет перейти от асинхронной модели программирования — к синхронной. Уместно это, или нет, зависит от ситуации.
Кооперативная многозадачность легко получается с помощью сопрограмм с несложным диспетчером потоков. В простейшем случае, диспетчер — это бесконечный цикл, последовательно вызывающий сопрограммы. Для более сложных диспетчеров можно реализовать добавление/снятие задач, систему приоритетов и т.д.
Использование многозадачности на основе сопрограмм даёт следующие преимущества перед вытесняющей многозадачностью:
- все операции атомарные, данные не нужно защищать критическим секциями и мьютексами. Примитивы синхронизации потоков или не нужны, или реализуются элементарно, и полностью программно
- низкие накладные расходы на поток. Расход памяти на поток можно ограничить двумя байтами, хранящими точку возврата, у потоков нет собственного стека. Переключение между потоками составляет считанные инструкции процессора в пространстве пользователя. Значит, количество потоков может исчисляться миллионами
- можно заблокировать поток до наступления комбинации из нескольких событий. Например, ожидание любого из событий: пришел пакет данных, или сработал таймер, или пользователь отменил операцию, или возникла ошибка
- заблокированный поток можно прервать, тогда, как стандартные блокирующие операции обычно прервать нельзя
Для многозачности Protothreads предоставляет следующие примитивы:
- макросы PT_WAIT_UNTIL и PT_WAIT_WHILE для блокировки потока до наступления определенного события
- макрос PT_WAIT_THREAD, останавливает поток, пока не окончится другой поток
- макрос PT_SPAWN позволяет одним потоком запустить другой поток с начала и дождаться его завершения
- макрос PT_SCHEDULE, примитив диспетчера потока, выполняет очередной шаг сопрограммы и возвращает, завершила она свою работу или еще нет
- структура pt_sem, PT_SEM_INIT, PT_SEM_WAIT, PT_SEM_SIGNAL — примитивы работы с семафорами, практически бесполезны
Если Вы хотите запустить много одинаковых потоков, передавайте в функцию потока ссылку на структуру, которая хранит все данные и переменные, которые поток должен использовать, для каждого потока свою. Для единственного потока, все переменные можно хранить внутри функции, просто объявив их как static.
Для примера многопоточности сделаем простой консольный Arkanoid под windows (чуть больше 100 строк). Файл на pastebin:arkanoid.c
У нас будет 3 потока: ракетка, шарик и игровое поле. Еще одна вспомогательная подзадача pauseThread будет делать паузу.
Планировщик будет простой: передаём управление каждому из потоков, потом пауза 10мс. Игра завершается, если любой из потоков завершится (шарик может улететь за поле, или мы можем выбить все кирпичи).
while (PT_SCHEDULE(printField(&fieldPt)) && PT_SCHEDULE(controlThr(&ctrlPt)) && PT_SCHEDULE(ballThread(&ballPt)))
Sleep(10);
Поток printField сначала создаёт в памяти игровое поле, затем, в цикле, ожидает флага изменения поля и перерисовывает всё поле на экране. Если кирпичи заканчиваются, поток завершается.
Поток controlThr рисует на поле биту, ждет нажатия на кнопку и перемещает биту. Или прерывает игру по нажатию «q».
Поток pauseThread просто выдерживает нужную паузу, сделан для примера вызова одной задачи из другой и помощью PT_SPAWN.
Поток ballThread перемещает шарик по полю с заданной скоростью, выбивая кирпичи и делая отскоки от стен и биты. Этот поток завершается, если мяч вылетает за поле.
Еще пару советов:
Если Вы используете gcc, рекомендую перед подключением библиотеки поставить один #define, вот так:
#define LC_INCLUDE "lc-addrlabels.h"
#include "pt.h"
Это позволит использовать расширение gcc «Labels as Values», и Вы сможете прерывать и переключать поток выполнения внутри оператора switch. В противном случае продолжения сами будут строиться с помощью оператора switch, с Вашим switch-ом они не поладят.
Обратите внимание, что после окончания потока, он автоматически начинается сначала. После того, как SCHEDULE вернет 0, нужно либо перестать его вызывать, либо в конце потока заблокировать его навсегда: PT_WAIT_WHILE(pt,1)
Автор: ldir
