fiber — легковесные процессы для Arduino

в 21:07, , рубрики: arduino, C, fibers, Алгоритмы, ненормальное программирование, необычные решения, параллельное программирование, программирование микроконтроллеров

fiber — легковесные процессы для Arduino - 1

А давайте притащим мир большого программирования в Arduino!

Любая программа, а тем более программа близкая к аппаратуре (а какие еще на arduino бывают?) при рассмотрении представляет собой множество параллельно работающих ветвей.

При этом в реальной жизни обработка большинства вещей в реальном времени не требуется. Достаточно иметь нечто похожее на реальное время.

Например если мы программируем скажем гистерезисный регулятор температуры, то как правило совершенно не важно прямо сейчас сработает включатель нагревателя или через пару милисекунд.

А вот если мы программируем скажем регулятор ШИМ (не рассматриваем аппаратные способы), то тут нам возможно потребуется считать каждый такт процессора, чтобы обеспечить приемлемую точность регулирования.

Если рассмотреть структуру произвольного сложного программно-аппаратного проекта в том числе на Arduino, то увидим, что задач требующих "реального" (с жесткими требованиями) реалтайма — меньшинство, а большинству задач достаточно условного реалтайма.

Программирование реального реалтайма — это как правило прерывания и аппаратные хитрости. В этой статье поговорим о программировании реалтайма условного.

Давайте представим что мы разрабатываем скажем систему управления обычным бытовым холодильником. Эта система включает в себя:

  1. Регулятор температуры
  2. Органы управления этой самой температурой (пусть будет переключатель на три положения)
  3. Датчик открытия двери
  4. Свет в холодильнике
  5. Ну и например выход в интернет, куда ж без него.

Управляем температурой

Давайте попробуем рассмотреть для начала регулятор температуры. Как правило в холодильниках используют гистерезисное регулирование. Мы не будем придумывать велосипед и просто его реализуем.

void
temperature_regulator(void) {

    for (;;) {
        uint16_t current_t = get_adc(INPUT_T);

        if (current_t > t_on)
            enable_cooler();

        if (current_t < t_off)
            disable_cooler();
    }
}

Где: t_on и t_off — температуры гистерезиса. INPUT_T — вход АЦП измерения температуры. get_adc — некая функция производящая измерение АЦП. Функции enable_cooler и disable_cooler — соответственно включают и выключают охладитель.

Вроде просто?

Рассматривая поближе составляющие сразу натыкаемся на то, что многие вещи включают в себя циклы ожидания. Например функция get_adc могла бы выглядеть как-то так:

uint16_t
get_adc(uint8_t input)
{
    while (adc_is_busy());
    adc_switch_mux(input);
    adc_start();
    while (adc_is_busy());
    return adc_value();
}

Где adc_switch_mux — переключает входной мультиплексор АЦП на нужный вход, adc_start запускает АЦП преобразование. Пока преобразование выполняется нам приходится ждать — пустой цикл пока adc_is_busy возвращает истину. Когда преобразование выполнится adc_value вернет нам результат.

управляем светом

Управление светом в холодильнике тривиально:

void
light_control(void)
{
    for (;;) {
        if (sensor_door() == DOOR_OPEN)
            light_on();
        else
            light_off();
    }
}

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

Обе программы вполне наглядны понять и написать их сможет школьник. Но как соединить их в один процесс?

Самое простое — преобразовать программы в функции и вызывать их в бесконечном цикле. Именно этот подход предлагает нам Arduino с его традиционной функцией loop:

void
temperature_regulator(void) {

    uint16_t current_t = get_adc(INPUT_T);

    if (current_t > t_on)
        enable_cooler();

    if (current_t < t_off)
        disable_cooler();
}

void
light_control(void)
{
    if (sensor_door() == DOOR_OPEN)
        light_on();
    else
        light_off();
}

void
loop(void)
{
    temperature_regulator();
    light_control();
    ...
}

Вроде все просто? Но давайте вернемся к get_adc. Просто так уже эта функция не разворачивается. Можно конечно оставить все как есть (АЦП преобразование надолго нас не задержит), для случая холодильника возможно и подойдет, но давайте попробуем развернуть и этот цикл.

Какие сложности возникают:

  1. Поскольку имеется возвращаемое значение get_adc, то нужно его где-то хранить
  2. Если АЦП не используется нигде в другом месте, то у разработчика возникает большой соблазн взять и сунуть измерение АЦП прямо внутрь temperature_regulator:

enum adc_state { FREE, BUSY, VERYBUSY } state = VERYBUSY;

void
temperature_regulator(void)
{
    uint16_t current_t;
    switch(state) {
        case VERYBUSY:      // АЦП не нами занято
            if (adc_is_busy())
                return;
            state = FREE;
        case FREE:
            adc_switch_mux(input);
            adc_start();
            state = BUSY;
            return;
        case BUSY:
            if (adc_is_busy())
                return;
            current_t = adc_value();
            state = FREE;
            break;
    }

    if (current_t > t_on)
        enable_cooler();

    if (current_t < t_off)
        disable_cooler();
}

Вроде не сильно сложно? Но из неприятностей:

  1. появилось внешнее по отношению к функции хранилище состояния АЦП-модуля
  2. мы смешали код работы с АЦП с кодом регулятора (инкапсуляция нарушена)

Если мы АЦП захотим использовать еще в паре мест, то придется тщательно работать над рефакторингом:

  • восстанавливать инкапсуляцию (котлеты отдельно, мухи — отдельно)
  • организовать еще одно хранилище — результаты работы АЦП между вызовами надо где-то хранить

Итого получается у нас при таком подходе недостатки:

  1. Резко возрастает сложность программ;
  2. Появляются внешние (по отношению к программным сущностям) хранилища данных (где мы их храним: в статических переменных или глобальных — вопрос стиля);
  3. Либо если мы хотим отказаться от внешних хранилищ данных, появляется протокол обмена данными (каждая функция может вернуть данные или признак их отсутствия. Другие функции будут обрабатывать данные или ничего не делать при их отсутствии.

Если мы решим вывести наш холодильник в интернет, то программирование его в такой парадигме может стать адом.

Как бороться с этим адом?

Резкое занижение требований к ПО

Это нормальный метод, если он подходит, то можно на нем остановиться. Помните выше мы сформулировали что можно не разворачивать функцию get_adc, а оставить как есть.

И так сойдёт!

Вполне себе работоспособный подход, для холодильника (без сложного интернета) подойдет вполне.

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

Треды и процессы

В какой-то момент возникает соблазн даже взять и портировать на нашу систему полноценные треды/процессы. Гугля находим массу проектов, например вот этот.

Заглядывая в код треда видим все те же функции. Разглядывая код поближе — видим попытку организовать периодический вызов функций через примерно равные интервалы.

Например

loop() { ... }

Вызывается максимально часто, а вот Thread.onRun можно сконфигурировать чтобы вызывался скажем раз в две секунды.

То есть человек назвал тредом то что не является тредом в смысле CPU. Увы.

Реальных тредов в том понимании как их понимают в "большом" мире я не нашел. Буду благодарен, если кто-то подбросит мне ссылку на такой проект.

Однако в рамках обсуждения тредов и процессов скажу еще что в "большом" мире для решения задач треды обычно не применяют.
Почему? Реализация тредов (процессов) неизбежно приводит нас к введению понятия "квант времени": каждый тред/процесс выполняется определенный квант времени, после чего управление у него отнимается и передается другому треду/процессу.

Такая многозадачность называется вытесняющей: текущий процесс вытесняется следующим.

Почему в рамках "больших" проектов треды в основном не применяются? Для того чтобы заставить работать множество тредов на одном CPU необходимо делать очень маленький квант времени. Частота квантования например на современном Linux — равна 1000Гц. То есть если у Вас в системе выполняется 1000 процессов одновременно, то каждый из них будет получать 1 квант времени на 1мс один раз в секунду (это если оверхеда на вытеснение нет), а в реальном мире переключая 1000 процессов хорошо если получится выдать каждому по милисекунде раз в десять секунд.

Кроме того, поскольку многозадачность вытесняющая, то возникает масса вопросов по межпроцессному взаимодействию. Возились с гонками между прерыванием Arduino и основной программой? И здесь те же проблемы.

В общем все нагруженные, так называемые HighLoad проекты в "большом" мире делают без массового использования тредов. Проекты HighLoad делают с применением кооперативной, а не вытесняющей многозадачности.

Чтобы обслужить 1000 клиентов выделив каждому тред — нужно примерно 20 современных компьютеров. При том что на практике достаточно одного сервера чтобы обслужить 50 тыс клиентов.

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

Что это такое? Вот типовой loop() проекта Arduino и есть один из вариантов кооперативной многозадачности: переключение к следующей функции не произойдет до тех пор пока предыдущая не завершится. Все функции стараемся писать чтобы они возвращали управление максимально быстро и таким способом решаем задачу.

Этот способ реализации кооперативной многозадачности можно называть колбечным (или функциональным).
Если обратиться к "большому" миру, там есть проекты для HighLoad построенные исключительно на этом способе, например тот же Node.JS.

Если Вы почитаете отзывы о Node.JS, то увидите весь набор от восторженных "наконец я нашел инструмент на котором МОЖНО реализовать мою задачу", до типовых: "callback hell!".

Существует второй способ реализации кооперативной многозадачности — сопрограммы (корутины, файберы). Идея тут примерно такая же как в традиционных тредах: каждый процесс работает как бы независимо от других. Однако ключевое отличие тут в том, что переключение между процессами производится не по таймеру, а тогда, когда сам процесс решит что ему процессор больше не нужен.

Какие прелести дает подобный подход?

  1. Нет ада функций;
  2. Межпроцессное взаимодействие очень простое (ведь если процесс не прервут в критической секции, то и само понятие "критическая секция" нивелируется): мютексы, семафоры — все или резко упрощается или заменяется простыми переменными;

"Лучшие умы человечества" (ц) разрабатывавшие в прошлом веке для нас язык C и писавшие о нем книги по которым многие из нас учились читать, попытались обобщить все достоинства и тредов и кооперативной нефункциональной многозадачности и в итоге родился язык для HighLoad — Go.

Но впрочем давайте вернемся из большого мира в наш мир Arduino. Go у нас нет, поэтому будем работать с тем что есть.

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

Итак нам нужны:

  1. Возможность создать процесс;
  2. Возможность переключиться на другой процесс из процесса.

Традиционное название функции переключения между процессами — yield или cede.

Вернемся к нашей функции get_adc:

uint16_t
get_adc(uint8_t input)
{
    while (adc_is_busy());
    adc_switch_mux(input);
    adc_start();
    while (adc_is_busy());
    return adc_value();
}

Если бы у нас были кооперативные процессы, то в их среде ее бы следовало доработать до следующего вида:

uint16_t
get_adc(uint8_t input)
{
    while (adc_is_busy())
        cede();         // пока ждем - пусть другие работают
    adc_switch_mux(input);
    adc_start();
    while (adc_is_busy())
        cede();         // пока ждем - пусть другие работают
    return adc_value();
}

Температурный регулятор выглядел бы так:

void
temperature_regulator(void) {

    for (;;) {
        uint16_t current_t = get_adc(INPUT_T);

        if (current_t > t_on)
            enable_cooler();

        if (current_t < t_off)
            disable_cooler();
    }
}

Но позвольте! Тут же никаких изменений нет! Скажете Вы. А все изменения вошли в get_adc, зачем нам еще?

Ну и управление светом тоже доработаем:

void
light_control(void)
{
    for (;;) {
        if (sensor_door() == DOOR_OPEN)
            light_on();
        else
            light_off();

        cede(); // сам поработал - дай другому
    }
}

Красиво? Наглядно? По моему максимально наглядно насколько это возможно.

Все используемые нами функции подразделяются на два вида:

  1. вызывающие yield/cede внутри себя
  2. остальные

Если в Вашем цикле есть хоть одна функция гарантировано вызывающая yield/cede внутри себя, то добавлять вызовы cede()/yield() не нужно.

В "большом" мире хорошим тоном считается писать вызовы cede()/yield() внутри так называемых низкоуровневых функций и сводить вызовы этих операторов к минимуму.

Сколько это будет стоить?

Поскольку процессы все-таки слабо зависимы друг с другом (хоть и передают друг другу управление), то, очевидно, у каждого процесса должен быть собственный стек.

Собственный стек — понятие относительно дорогое. Происходит например прерывание. В стек попадает текущий адрес выполнения программы. Так же в стек попадают все регистры которые будут использованы в прерывании.
Вы вызываете функцию: в стек попадают адрес возврата, все ее аргументы и ее временные переменные.

Я занимался замерами, практика показывает что прерывание обслуживающее например таймер (проинкрементировать счетчик, послать уведомление) занимает на стеке 16-30 байт. Ну и обычный цикл тоже доходит до 16-30 байт глубины. Например наш temperature_regulator занимает на стеке:

  1. всего 2 байта под свою переменную
  2. 2 байта на вызов get_adc
  3. 1 байт на аргумент для get_adc
  4. 2 байта на вызов adc_switch_mux
  5. 1 байт на ее аргумент

Итого 2 + 2 + 1 + 2 + 1 = 8 байт. Плюс компилятор посохраняет регистры в стек/подостает их оттуда. Умножим на два. Плюс возможный вектор прерывания. Итого получается где-то 50-60 байт на файбер нам было бы достаточно. Сколько файберов можем запустить на Arduino nano328? 5-10 штук со стеком 64-128 и еще останется память для всего остального.

Расходы памяти на 5-10 полноценных файберов стоят упрощения реализации алгоритмов программы? Ну и поскольку 640 килобайт хватит всем 5-10 файберов хватит для того чтобы комфортно написать не только холодильник но и скажем http-клиента займемся написанием такой библиотеки!

Прототип

Мной реализован прототип (уже можно пользоваться но API будет расширяться) библиотеки файберов для Arduino. Пока только AVR (есть завязки на avr-libc).

Данная статья пишется в гит того же проекта и оригинал ее (будет дорабатываться) лежит здесь.

Библиотека написана на чистом C (не C++).

API

Начинается все с инклюда и инициализации:

#include <fiber.h>

void
setup()
{
    ...
    fibers_init();
}

Для создания файбера используется функция fiber_create, принимающая ссылку на заранее выделенный для него стек, его размер и ссылку на данные которые будут переданы в файбер:

struct fiber *
fiber_create(fiber_cb cb, void *stack, size_t stack_size, void *data);

Для того чтобы не мучиться в программе над выделением стека, предусмотрены пара макросов:

FIBER_CREATE(__cb, __stack_size, __data);
FIBERV_CREATE(__cb, __stack_size);

Которые за Вас выделят память в статической области (обратите внимание: malloc не используется, поэтому нельзя применять эти макросы в цикле).

Или даже если Вы определите заранее какой размер стека будут иметь все Ваши файберы то два макроса:

FIBER(__cb, __data);
FIBERV(__cb);

для определения файбера.

Файбер может иметь несколько состояний, вот базовые:

  • 'работает' — обычное состояние
  • 'усыплен' — не автопланируется

Усыпить можно только текущий файбер (то есть сам файбер себя усыпляет, получив ссылку на себя fiber_current) вызвав функцию fiber_schedule, разбудить — функцией fiber_wakeup:


    struct fiber *waiter;

    // где-то в файбере
    waiter = fiber_current();
    fiber_schedule();

    // где-то в другом месте, например в прерывании или другом файбере
    if (waiter) {
        fiber_wakeup(waiter);
        waiter = NULL;
    }

На механизме усыпления/пробуждения можно сокращать использование CPU на циклах ожидания: если Ваш файбер сейчас ждет и есть кому разбудить (например прерывание), то можно его усыпить: другие файберы получат больше процессорного времени на работу.

Передача управления из процесса в процесс выполняется вызовом fiber_cede():

void
light_control(void)
{
    for (;;) {
        if (sensor_door() == DOOR_OPEN)
            light_on();
        else
            light_off();

        fiber_cede(); // сам поработал - дай другому
    }
}

Тонкости

  • Никакие функции (кроме fiber_wakeup) нельзя вызывать из прерываний. Это обстоятельство видимо не преодолеть;
  • Нет возможности контроллировать автоматически переполнение стека;

Соответственно некоторые файберные паттерны из "большого" мира тут применять не получится. Данная библиотека годится под паттерн: на стадии инициализации запускаем N файберов и дальше они работают.

Паттерн "при событии запускаем файбер", при повторном — еще один — тут увы не проходит. Ресурсов Arduino не хватит. Но можете "разбудить" того кто обрабатывает редкие события.

Паттерн: положи ссылку на себя в переменную, засни, а прерывание тебя разбудит — имеет тонкости: прерывание может прийти раньше чем мы заснём. На эту тему решение внедрено, но требует дополнительного разъяснения. Просто исходите из того что так делать МОЖНО.

Что не доделано

  1. Пока не дооформил как библиотеку Arduino: не смог понять пока как заставить его компилировать (из GUI имеется ввиду, с Makefile-то все просто) C'шные файлы в стандарте C99 (даже заголовки avr-libc предполагают C99). Не хочу оформлять как C++ (потому что не только Arduino в планах);
  2. В большом мире есть fiber_join, так и не знаю стоит ли его реализовывать.
  3. Больной вопрос: если программа использует регистровые переменные и при этом переключает файберы, то предсказать поведение невозможно. Сохранять ВСЕ регистры на стеке — дополнительный оверхед. Пока не натыкался на эти проблемы. Возможно придется сделать опцию: будут файберы более требовательны к памяти, но более надёжные;

В общем буду рад коментариям, дельным предложениям и pull-реквестам :)

Пинг-понг на файберах:

#define FIBER_STACK_SIZE 64
#include <fiber.h>
#include <stdio.h>

void
ping(void *data)
{
       printf("pingn");
       fiber_cede();
}

void
pong(void *data)
{
     printf("pongn");
     fiber_cede();
}

void
setup(void)
{
       fibers_init();
       FIBERV(ping);
       FIBERV(pong);
}

void
loop()
{
     fiber_schedule(); // этот файбер нам не нужен
}

Ссылки

  1. Библиотека fiber;
  2. Эта статья в Git;
  3. Библиотека Thread, в тексте статьи;
  4. Многозадачность в терминах википедии;
  5. Когда-то на HighLoad выступал о аналогичном но в "большом" мире;
  6. Node.JS.

Автор: linuxover

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js