Введение
Protothreads - программная модель разработанная Adam Dunkels объединяющая достоинства событие-ориентированной модели (event-driven) (иногда называемый конечным автоматом (state machine) и потокового программирования. Основным достоинством событийной модели является эффективное использование памяти и скорости исполнения. Основным достоинством потоковой модели является простота алгоритма (algorithm clarity). Протопотоки получают достоинства обоих моделей, предоставляя также экстремально легковесные потоки. Как и в событийно-ориентированным программировании мы имеет единый стек, но также благодаря потоковому программированию функция может (хотя-бы в теории) содержать примитивы взаимоблокировки. В текущей реализации мы имеем:
- не реализует стандартное API (POSIX или какие-либо другие);
- не требуется ассемблерный код или использование setjmp/longjmp;
- кросс-платформенная реализация;
- не вытесняющий (non-preemptibly) планировщик и четко определенный порядок(deterministically) выполнения;
- не использует возможностей SMP.
Я решил переписать эту версию с нуля без совместимости с другими более ранними версиями протопотоков. Реализация имеет только одну не определенную стандартом С особенность - использование переменных как меток перехода (gcc label variables).
Проект включает:
- Полный исходный код (около 400 строк включая комментарии);
- реализацию двух примитивов синхронизации (семафоры и блокировки);
- около 800 строчек тестового кода;
- gdb макросы для отображения стека потока или потоков.
Потоки без стека
Вы можете считать протопоток обычной событийно-ориентированной моделью. В такой модели(если обрабатывается запрос) обычно сохраняется только указатель на функцию (или состояние( state)) которое используется в больших операциях условных переходов (switch) вместо отдельных функций) и контекст(context), включающих текущее состояние обработки. В протопотоках не используется указатель на функции и контекст, переход осуществляется непосредственно на адрес(без функции). Этот адрес гораздо лучше описывает состояние чем указатель на функцию. Действительно, протопотоки более универсальны; если функция A вызывает функцию B, B вызывает C и C блокируется, тогда поток сохраняет только три указателя на реальное место запуска в середине этих функций.
Пример производитель-потребитель
typedef struct {
pt_thread_t pt_thread;
pt_func_t pt_func;
int i;
int * mailbox;
} pc_thread_context_t;Кроме первых двух, описывающих служебные поля системы, содержит счетчик i, и указатель на общий для потоков почтовый ящик. Для производителя i количество записанных писем, для потребителя это количество писем для чтения. Значение ноль - почтовый ящик пуст.
Пример 2 описание потоков производителя и потребителя:
static pt_t
producer_thr(void * const env)
{
pc_thread_context_t * const c = env;
pt_resume(c);
for (c->i = 1; c->i <= 100; c->i++) {
while (*c->mailbox) {
/* mailbox is full */
pt_wait(c, c->mailbox);
}
*c->mailbox = c->i;
pt_signal(pt_get_pt(c), c->mailbox);
}
return PT_DONE;
}
static pt_t
consumer_thr(void * const env)
{
pc_thread_context_t * const c = env;
pt_resume(c);
for (c->i = 1; c->i <= 100; c->i++) {
while (*c->mailbox == 0) {
/* mailbox is empty */
pt_wait(c, c->mailbox);
}
assert(*c->mailbox == c->i);
*c->mailbox = 0;
pt_signal(pt_get_pt(c), c->mailbox);
}
return PT_DONE ;
}
Производитель ждет пока почтовый ящик освободится и записывает следующее значение и посылает событие потребителю. Потребитель ждет изменения состояния почтового ящика, проверяет его состояние, освобождает ящик(записывает 0) и разблокирует производителя. Для передачи сигналов как канал используется указатель на почтовый ящик. Это стандартное использование адреса структуры, состояние которой интересует потоки, как канал. В качестве канала, адрес никогда не освобождается, и используется для привязки к ожидаемым сигналам.
Эта технология синхронизации потоков (и термин канал "channel") впервые использовалась в ядре UNIX. Концепция подобна переменным состояния (condition variable) в POSIX потоках -- в данном случае память не ассоциируется с каналом или переменной состояния(как в POSIX); сигнал или смена состояние переменной для ожидающего потока не изменяет его состояния. Основной причиной выбора реализации использующей канал, является простота реализации, так как не требуется выделение переменной состояния. API также включает pt_broadcast(), подобный pt_signal() отличающийся от него только тем что он пробуждает все ожидающие потоки, не только наиболее длительно ожидающие.
Тестовая функция создает служебный объект и контекст для каждого потока, инициализирует почтовый ящик, создает потоки, и выполняет цикл пока выполняется условие:
static void
test_pc(void)
{
protothread_t const pt = protothread_create();
pc_thread_context_t * const cc = malloc(sizeof(*cc));
pc_thread_context_t * const pc = malloc(sizeof(*pc));
int mailbox = 0;
/* set up consumer context, start consumer thread */
cc->mailbox = &mailbox;
cc->i = 0;
pt_create(pt, &cc->pt_thread, consumer_thr, cc);
/* set up producer context, start producer thread */
pc->mailbox = &mailbox;
pc->i = 0;
pt_create(pt, &pc->pt_thread, producer_thr, pc);
/* while threads are available to run ... */
while (protothread_run(pt)) {
}
/* threads have completed */
assert(cc->i == 101);
assert(pc->i == 101);
free(cc);
free(pc);
protothread_free(pt);
}
Как это работает?
static pt_t
producer_thr(void * const env)
{
pc_thread_context_t * const c = env;
/* pt_resume(c) expanded: *****/
if ((c)->pt_func.label) goto *(c)->pt_func.label;
/* pt_resume end *****/
for (c->i = 1; c->i <= 100; c->i++) {
while (*c->mailbox) {
/* mailbox is full */
/* pt_wait(c, c->mailbox) expanded: *****/
do {
(c)->pt_func.label = &&pt_label_18;
pt_enqueue_wait((c)->pt_func.thread, c->mailbox);
return PT_WAIT;
pt_label_18:;
} while (0);
/* pt_wait end *****/
}
*c->mailbox = c->i;
pt_signal(pt_get_pt(c), c->mailbox);
}
return PT_DONE;
}
В начале работы потока, переменная содержит NULL, и функция не выполняет переход на сохраненный адрес(goto) -- код входит в выполнение цикла for в начале функции. Достигнув вызова pt_wait(), сохраняет значение адреса переменной (ее имя имя получяется из номера строки __LINE__; уточнение: двойной амперсанд сообщает, что нужно использовать расширение получения адреса по имени переменной), ставит поток в очередь ожидания внутри описания потока, сохраняет адрес возврата, что равносильно ожиданию сигнала связанного с адресом общей переменой, в данном случае почтового ящика, и возвращает PT_WAIT. (Результат возврата в данном примере не используется; как будет описано ранее он используется только для вложенных функций protothread.)
Когда приходе сигнал значение переменной будет отличаться от NULL, так что pt_resume() перейдет на сохраненный в ней адрес, и исполнение продолжиться. В этом случае функция продолжит выполнение цикла while, ожидая освобождения почтового ящика. При использовании стандартных переменных состояния POSIX обычно перепроверяют значение состояния перед следующим циклом ожидания.
Структура protothread
Структура описания протопотока обязательно содержит одну или больше протопотоковых функций. Только функции протопотоков могут блокироваться или вызывать блокируемые функции. Всем протопотокам требуется pt_thread_t структура для хранения внутренних состояний потоков. Кроме этого, каждый уровень вложенности функций нуждается в pt_func(тип pt_func_t), которая содержит внутреннюю(служебную) информацию для функций. Если A вызывает B которая вызывает C (и C блокируется), каждая из них нуждается в собственном экземпляре структуры pt_func.
Эта структура также содержит определенные пользователем состояния специфичные для функции, обычно это внутренние переменные если используется потоки POSIX. Функции протопотоков обычно не содержат внутренних переменных, так как эти переменные не сохраняются во время ожиданий событий. (Вы можете посмотреть в примере используется c->i вместо просто i для организации циклов.) Существует одно исключение, однако в обычно в C коде есть несколько локальных переменных инициализируемые при описании (на основе аргументов) и неизменные во время исполнения. Вы можете использовать этот принцип и при создании потоков protothreads также (перед вызовом pt_resume()), так как эта инициализация не имеет побочных эффектов. Пример 2 содержит подобную переменную c.
Существует только 2 пути запуска функций в протопотоках; протопоточные функции нельзя запускать непосредственно.
- Любой код(обычная функция или протопоточная функция) вызывается через pt_create() для создания нового потока. При передаче управления указатель на функцию и контекст исполнения передается одним аргументом. Этот вызовы планирует вызов потока (но не запускает его непосредственно). Не существует метода отмены выполнения потока. Систем пропотоков не сообщает когда он выполниться; он только запланирует выполнение. Вызов pt_create() также требует уникальной структуры (для данного потока) pt_thread_t, которая может быть выделена где угодно, но обычно это делают в вызывающей функции и включают в контекст вызывающей функции (как структура pc_thread_context_t указанная выше).
- Функция (внутри потока) может вызывать pt_call(). Последовательность обработки подобна обычному вызову функции, кроме того что вы используете pt_call() для вызова функции. Любое количество аргументов любых типов может быть передано при вызове функции ( проверку типов обычно осуществляет компилятор), но первым аргументом обязательно должен быть указатель на контекст исполнения (содержащий поле pt_func) для сохранения состояния функции после ее вызова.
При возврате состояний вы должны возвращать PT_DONE. К сожалению вы не можете использовать возвращаемое функцией значение для своих целей, но можете возвращать через указатели в аргументах и можете вернуть результат как часть описание контекста исполнения. Когда управление возвращается вызывающей функции, поток завершается и управление возвращается планировщику.
Вложенные функции в Protothread
Как работает вложенность? Когда функция A вызывает (используя pt_call()) потоковую функцию B, и B ожидает события (pt_wait()), B сохраняет текущее адрес исполнения и возвращает PT_WAIT в pt_call() в A, что вызывает сохранение его в контекст исполнения A как адрес восстановления где будет вызвана B. A возвращает PT_WAIT функции которая ее вызывала. Когда планировщик продолжит исполнение A , вызовется pt_resume() вызывающая B, так как A вызвала B, и B's pt_resume() перейдет на адрес после блокировки и продолжит исполнение. Так стек разматывается, когда поток блокируется и восстанавливается при снятии блокировки. Так можно описать как реализуется использование единого стека. Также мы должны осветить как обрабатываются параметры которые A передает B без побочных эффектов -- A всегда вызывает B при возобновлении работы.
Когда B полностью завершиться и возвратит PT_DONE, A будет знать что нужно продолжить выполнение кода после вызова pt_call() для B.
Контекст исполнения функции A может включать контекст B's внутри себя, или динамически создавать контекст функции B; выделение контекста возложено на пользователя. Для получения скрытия данных, A может выделять очень минимальную копию структуры pt_func и указатель не скрытую контекст B(для A). И в начале обработки B динамически выделяет память под полную структуру данных и связывает ее с переданной от A структурой.
Другая интересная идея заключается в том что,если A вызовет B, затем B вернет A вызов C (так что B и C не может работать одновременно), контекст для B и C могут быть полями(union) внутри контекста A. Эта разделение памяти между B и C подобна разделению стека внутри POSIX потока.
Четкий порядок исполнения
Основное достоинство событийно-ориентированной модели по сравнению с потоками POSIX их время исполнения можно точно спрогнозировать. Protothreads использует эту особенность. Почему это важно? Так как позволяет написать псевдо-случайные тесты которые могут достоверно воспроизвести ошибки. Вы можете начать тест с любого начального значения случайной последовательности, если выявиться ошибка вы всегда способны повторить тест с того же места (только уже с включенными отладочными метками или дополнительными проверками которые смогут выявить возможную ошибку), и тест всегда будет выполняться именно в том же порядке, как и при первом запуске и всегда повторит ошибочные состояния. Также это позволит проверить предлагаемое решения (кроме случае когда изменение приведет к изменению порядка смены состояний).
Конечно, исходное окружение должно быть полностью контролируемо, так как при жестком порядке исполнения(no nondeterminism) система подстраиваеться под окружение. Это важно например для случая, во время эмуляции; код не должен принимать решения на основе реального времени, так реальное время может изменяться от запуска к запуску. Генераратор случайных чисел должен использоваться для всех элементов имеющих случайные значения параметров(таких как задержки в передаче данных по сети или задержки при обращении к дискам).
Использование потоков POSIX делает невозможным написание четких тестов, так как на планировщик не возможно повлиять, и по моим наблюдениям он делает случайные решения(результат очень отличает от запуска к запуску).
Использование памяти и производительность
Наиболее известная реализация протопотоков (Adam Dunkels) использует 2 байта на каждый поток. Эта реализация не такая оптимальная ( в основном благодаря тому что реализация включает планировщик: потоки могут быть в списке ожидающих или работающих потоков); наше окружение не столь ограничено в использовании памяти. Каждый описатель потока содержит структуру pt_func_t , содержащую 2 указателя. Полное описание содержит структуру pt_thread_t, содержащую 5 указателей. Но все равно это гораздо меньше чем у стандартного потока POSIX.
Время создания и уничтожения нерабочих потоков на моем компьютере около 12.2 nanoseconds. Время создания и уничтожения при использовании POSIX реализации 7.85 microseconds, то есть различие в 643 раз. Для сравнения времени переключения контекста для модели производитель-потребитель, каждый поток переключался за 22.2 nanoseconds. Смена контекста в стандартной реализации 3.0 microseconds, то есть разница в 135 раз.
Заключение
Использование protothreads для приложений реального времени или с ограничением на использование ресурсов может дать значительный прирост производительности по сравнению с стандартными реализациями POSIX потоков. В тоже время алгоритм получается более прозрачным, чем при использовании стандартных реализаций событийно-ориентированной модели.
Описание API
Контекст исполнения потока
Далее указаны используемые макросы ( реализованные чтобы выглядеть и работать подобно функциям) первым аргументов выступает определенная пользователем структура описатель контекста выполнения, c (подобная context_t, но описанная пользователем). Для всех служебных функций используется тип pt_f_t.
void pt_resume(struct context_t *c)
Каждая функция должна вызвать этот макрос перед выполнением основной логики, но после того как выполнила инициализацию своих внутренних переменных (которые инициализируются из аргументов, но не из глобального состояния). Если выполнение поток будет восстановлено, pt_resume() вызовет переход (goto) на точку где прервалось выполнение. Если функция вызвана первый раз (еще не разу выполнение не блокировалось), pt_resume() ничего делать не будет.
void pt_wait(struct context_t *c, void *channel)
Заблокировать на время отправки сигнала в указанный канал. Канал интерпретируется как void * и обычно им выступает адрес структуры изменение состояния которой интересует функцию. Сам канал не имеет состояния; система протоптоков никогда не обращается по указанному адресу. Обычно, после возврата значения этой функцией функция будет вызвана еще раз. Аналог для POSIX pthread_cond_wait().
void pt_yield(struct context_t *c)
Перепланировать текущий поток и освободить процессор. Подобно pt_wait() по которому сразу пришел сигнал. В текущей реализации списка потоков он ставиться в конец очереди и возвращает управление планировщику.
void pt_call(struct context_t *c, pt_f_t child_func, struct child_context_t *child_context, arg...)
Непосредственно вызвать функцию протопотока, передать ей значение аргументов и контекст исполнения и подождать окончания ее выполнения. Это позволяет вызвать потомка без смены контекста исполнения. Будьте внимательны, чтобы не было побочных эффектов при обработке параметров, так как этот вызов осуществляется при возврате управление ожидавшему исполнения потоку. Обычная для C проверка типов будет осуществлена для всех аргументов.
bool_t pt_call_waited(struct context_t *c)
Возвращает TRUE если выполнение функции pt_call() было заблокировано (непосредственно в вызывающей функции или в ее потомке). Если функция A вызывает B и B блокируется, тогда при возврате в A, это поможет понять что должен исполняться другой поток, это позволит заново пересчитать значение глобального состояния. Но если B не заблокирована, тогда A знает, что нужно только изменение локального состояния (независимо от того, что B выполнил).
protothread_t pt_get_pt(struct context_t *c)
Возвращает указатель на описание потока(protothread_t). Используется для вызова функций требующих для исполнение описания потока, таких как: pt_create() или pt_signal().
Контекст исполнения других реализаций потоков
void pt_create(protothread_t, pt_thread_t, pt_f_t func, void *env)
Планирует указанный поток на выполнение, передает ему его аргументы и значение окружения. Эта функция предок всех потоков. Никакой смены контекста между этим вызовом и следующим состоянием вызвавшей функции. Новый список потоков добавляется в конец очереди готовых к исполнению потов. Аналог для POSIX pthread_create().
void pt_broadcast(protothread_t, void *channel)
Отправить сигнал в указанный канал, разблокирует все потоки ожидавшие сигнала по этому каналу в том же порядке в котором они блокировались. Если не было ожидающих потоков, вызов ничего не делает; сигналы в очередь не ставятся (память с каналом не ассоциируется). Полученный список разблокированных потоков добавляется в конец готовых к исполнению потоков. Аналог для POSIX pthread_cond_broadcast().
void pt_signal(protothread_t, void *channel)
Подобно pt_broadcast() но пробуждаеться только наиболее долго ждавший поток. Аналог для POSIX pthread_cond_signal().
protothread_t protothread_create(void)
Этот вызов обычно вызывается одни раз для создание дескриптора для потока. Возвращает дескриптор потока. Система протопотоков не использует глобальные переменные. Все состояния потоков сохраняются в этом объекте; множество экземпляров протопотоков независимы. Эта функция только вызывает выделение памяти под объект.
void protothread_free(protothread_t)
Очистка состояния созданного с использованием protothread_create(). Перед запуском не должно быть ни одного связанного с этим объектов потоков.
Планирование
bool_t protothread_run(protothread_t)
Запуск следующего готового процесса (если он конечно есть). Возвращает TRUE, если нет ждущих исполнения потоков.
void protothread_set_ready_function(protothread_t, void (*ready_function)(void *), void *env)
Эту функция предназначена для использования с уже существующим планировщиком (если нет возможности его заменить, или не хотим его заменять). Вам эта функция не нужна, если вы используете собственный планировщик. Эта функция обычно запускается один раз во время инициализации. Результатом вызова этой функции является вызов для всех свободных потоков ready_function (с передачей ей env) когда поток будет готов (и нет рабочих потоков), и нет (в данный момент ) запущенных потоков. Вы можете передать NULL вместо ready_function для отключения этой возможности.
Указанная ready_function обычно планирует (используя методы доступные в вашей системе). Другая функция вызывает protothread_run() пока не закончатся потоки для выполнения (protothread_run() returns FALSE). ready_function не должна вызывать protothread_run() непосредственно.
Для того чтобы последовательность выполнения потоков не заняла слишком много времени, функция может ограничить количество запусков protothread_run(); для примера: она запускает не более 20 потоков до того как вернуть управление планировщику для выполнения других задач (вне протопотоков). Она это делает (если последний вызов protothread_run() вернет TRUE), только если нужно выполнить перепланировку, так как осталась не завершенные задачи.
Источники
Большая благодарность Adam Dunkels (с поддержкой от Oliver Schmidt) за блестящую идею. Пожалуйста, зайдите на его сайт.
Большое спасибо также за помощь Paul Soulier в разработке концепции потоков, Marshall McMullen и John Rockenfeller за рецензию черновиков этой статьи.
No comments:
Post a Comment