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

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

    Похожие публикации

    Комментарии 18

      +6
      Я прошу прощения, но protothreads — это жуткое, грязное, страшное извращение, опасное, неудобное и неотлаживаемое, как и вся макросная магия в C, которое нельзя использовать ни в коем случае.
        +1
        Выглядит убедительней, чем целая статья, если быть честным.
          0
          В эмбедде вполне себе используют это извращение ( на 8-ми битном камне с 500 байтами ОЗУ мало какая RTOS взлетит).
            0
            В эмбеддеде на 8-битном камне надо не лениться писать машины состояний на switch. Самому же легче будет, правда.
              +1
              Отлаживать автомат на пару сотен состояний будет легче? Не сказал бы…
          +1
          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;
          }
          
          Разве конструкция case может разрывать цикл?
            0
            «case» это метка, куда переместиться, почему нет?
              +3
              Да, может, это известная «фича» С.
              +1
              Device в Duff's device это все-таки «прием» (как, например, rhetorical device — риторический прием), а не «устройство».
                0
                Как альтернатива — «метод». Увидев «прием Даффа», мне было бы решительно непонятно, зачем автор хотел бы этого Даффа приесть.
                  0
                  Зря вы так. Слово «приём» используется в русском языке слишком часто, чтобы его можно было путать с будущим временем глагола «приедать».
                    +1
                    Вот к таким недоразумениям приводят дурацкие инициативы по избавлению от буквы «ё»
                  0
                  Спасибо, вы правы, в статье исправила.
                  0
                  Машины состоянний, многозадачность на switch (а-ля protothreads), или с помощью проверки флагов очень востребована. Встраиваемые системы, микроконтроллеры, даже оконная функция в виндах это один большой swithc, обрабатывающий события.
                  Почему же за пол-века эволюции языков программирования ни в одном из них не ввели поддержку машин состояний или легковесных потоков?

                  p.s.
                  В ADA есть task (на на МК, по-видимому, не работают)
                  В C# есть yield
                  Но это все сделано совсем недавно.
                    0
                    В C++ вот-вот добавят co_yield и co_await, причем некоторые компиляторы уже поддерживают их экспериментальную версию.
                      0
                      думаю, что в C++ для МК мы этого никогда не дождемся.
                        0
                        Если там используются необычные компиляторы — то, вероятно, так и есть. А если обычные gcc или clang — то никуда МК не денутся.
                      0
                      В си есть setjmp/longjmp, очень во многих языках через них это и сделано.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое