caxapa.ru :: Прототреды это биг-луп вывернутый наизнанку. Или наоборот. То же самое, что конечные автоматы им. Шалыто, switch-технология. Удобней представлять в виде big loop всё-таки. Идея в том, что какой-то "протопоток", "автомат", отдал управление обратно циклу и он побежал вызывать остальные "протопотоки" или автоматы...

Связанные сообщения

fk0, легенда (11.06.2020 19:54, просмотров: 1218) ответил lloyd на В protothreads мютексом будет просто любая булевская переменная (или битовый флаг, пофиг), даже volatile не обязателен. Проблема лишь в том, что любая система с обработчиком прерываний - уже вытесняющая многозадачность.

Прототреды это биг-луп вывернутый наизнанку. Или наоборот. То же самое, что конечные автоматы им. Шалыто, switch-технология. Удобней представлять в виде big loop всё-таки. Идея в том, что какой-то "протопоток", "автомат", отдал управление обратно циклу и он побежал вызывать остальные "протопотоки" или автоматы...

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

В итоге очень низкая реактивность: после установки переменной нужно пробежать весь цикл, сделать 100500 проверок, увидеть, что условие выполнилось, установить пару переменных для сигнализации следующему автомату (протопотоку), и опять бежать по кругу весь цикл, чтоб запустить следующий автомат. А круг, из-за того, что переменных и автоматов много, оборачивается очень медленно. В итоге работает всё медленно, а CPU load стремится к 100%.

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

Я давал ранее три шикарные идеи, которые можно скомбинировать в ОС 21-го века:

0) нужно ввести понятие события как атома [4, 5], события которое или произошло когда-либо в прошлом, или не происходило (событие не может нести ассоциированные данные, не может быть счётнмы -- для этого есть другие механизмы);

1) нужен разумеется планировщик, но не "планировщик задач" в многозадачной ОС, а планировщик событий, который решает какое из произошедших ранее событий требует обработки и запускает соответствующий обработчик (наподобии планировщика libevent) [3, 4, 5].

Пункты 0 и 1 -- база, фундамент для построения событийно-управляемой системы конечных автоматов, кооперативной или вытесняющей ОС. В последнем случае событие -- это срабатывание семафора, мьютекса и т.п.

2) разделение стеков [1], важный вопрос для микроконтроллеров при традиционном подходе к многозадачному программированию стек каждой задачи должен быть гигантского размера, такого, чтоб хватило на самый "глубокий" из возможных вызов функций. В итоге каждой задаче приходится выделять минимум несколько килобайт под стек. При объёме памяти в 32кБайта, например, много ли задач так запустишь? Идея в том, чтоб разделить все функции программы на два класса [2]:

* позволяющие вытеснение;

* не вытесняемые.

Функции использующие большой объём стека должны стать не вытесняемыми. Например, быстро исполняемые библиотечные функции. И все такие функции, независимо из какого потока/задачи вызваны, могут тогда использоват общий стек. Функции же которые допускают вытеснение должны использовать свои отдельные стеки, но они могут быть достаточно маленькими, буквально несколько десятков-сотен байт.

Остаётся вопрос с медленными и блокирующимися функциями требующими и большой объём стека, и вытеснение. Такие функции только остаётся реализовывать как отдельные задачи.

Разделение стеков можно реализовать с помощью функции split stacks реализованной в gcc, но её поддержка по-моему до сих пор находится на зачаточном уровне, и далеко не на всех платформах.

Альтернативой [2] может быть решение основывающееся на поддержке компилятором функции alloca или массивов переменной длины (C99). При этом указатель стека (SP) постоянно находится в "общей" области памяти предназначенной для не вытесняемых функций, но при исполнении вытесняемой функции возможно переключение задач заключающееся в смене значения регистра указателя кадра стека (FP, frame pointer), который указывает на короткий фрагмент памяти текущей задачи. Переключение задач возможно только пока не исполняется "невытесняемая функция". При переключении задач сохраняются регистры, короткий стек задачи, но общий для всех задач стек "невытесняемых функций" каждый раз инициализируется заново. Вызов вытесняемых функций при этом возможен не напрямую, а через специальный "враппер" обеспечивающий сохранение регистров и переустановку указателя стека.

Недостатком такого метода является факт, что компилятор для всех "вытесняемых" функции вынужден генерировать менее эффективный код поддерживающий отдельно кадр стека (через выделенный регистр frame pointer) -- потому, что значение SP в момент исполнения функции не детерминировано, и разумеется недопустимо в таких функциях использовать alloca или массивы неконстантной длины.

Ссылки:

1. http://caxapa.ru/458152

2. http://caxapa.ru/954365

3. http://caxapa.ru/953557

4. http://caxapa.ru/911520

5. http://caxapa.ru/841745

[ZX]

Ответить

- >наподобии планировщика libevent lloyd(89 знак., 11.06.2020 21:15)
- Не соглашусь. В случае оптимальной реализации автомата он входит в состояние ожидания продолжения работы, и делает только это. Кроме того, никто не заставляет по одному кругу крутить все автоматы. - VLLV(11.06.2020 20:37)
  - В состоянии ожидания он постоянно проверяет некоторую переменную. Если переменных много, когда параллельных/независимых автоматов много -- эти проверки оказываются чрезмерно длительными. Вложенные КА (в терминологии switch-технологии Шалыто) отчасти спасают ситуацию, но в целом проблема остаётся: сильно параллельные задачи методом big loop, switch-технологие, с помощью protothreads -- эффективно не решаются. При том, что с ними элементарно справится планировщик типовой RTOS. - fk0(11.06.2020 20:45)
    - Вызов вложенных автоматов можно организовать с разной частотой, соответсвующей необходимой скорости обработки. Это исключит тупую проверку. Да, сильно параллельные ДОЛГОВРЕМЕННЫЕ задачи сложно реализовать методом биглуп, но я за свою жизнь с этим столкнулся только в одном проекте из десятков. А ресурсы нужно делить в каждом втором. - VLLV(11.06.2020 21:27)
      - Это уже пошли костыли и подпорки. Я хотел акцентировать внимание на проблеме, что bigloop плохо масштабиуется. Он хорош пока маленький, когда становится большой -- он еле ворочается. Как и прототреды, как и switch-технология. По сути это всё одно и то же. Чтоб ворочалось побыстрее нужен какой-то механизм, планировщик, который будет знать кому какие события интересны и вызывать обработчик события по факту его получения (а не опрашивать каждое событие в цикле из обработчика fk0(37 знак., 11.06.2020 23:37)
        
        У события делать список задач, ожидающих события? И, вестимо, у них есть приоритеты. - Dingo(15.06.2020 17:38)
        
        Такой планировщик называется системой прерываний, и это прослойка есть и в биглупе и в ОС. - VLLV(12.06.2020 04:48)
    - А зачем, блядь он ее проверяет?! Пусть не проверяет, пусть выберет десяток, случайным образом, будет быстро. Мужики, так нельзя. Если технически возможно аппаратное выявление изменения состояния входов автомата (АКА прерывание), то это можно использовать, а если нет - можно только то, что можно. Cкpипaч(222 знак., 11.06.2020 20:52)
      - Со switch-технологией наверняка знаком? А что ему делать -- там автомат следит за своими входами и, что более важно, может изменение переменной состояния другого автомата воспринимать как свой входной сигнал. Последнее принципиально важно, т.к. является одним из способов коммуникации автоматов между собой (второй способ работает только на передачу информации -- прямой вызов функции автомата с передачей номера входного сигнала). И если у нас есть множество параллельных fk0(968 знак., 11.06.2020 21:18)
        
        Организуйте очередь событий и отстаньте от совы. - Cкpипaч(11.06.2020 21:46)
        
        И получится Quantum Leap он же state-machine.com. И сразу будут спрашивать, "а что если очередь событий переполнится". И ведь переполняется бывает. С очередью есть одна принципиальная проблема: события из очереди обрабатываются в порядке очереди. И если она одна на всё, то возможен "шторм событий", когда некоторые события попавшие на вход генерируют достаточно большое количество внутренний событий, и так рекурсивно. И если на вход поступает сразу много "проблемных" событий, fk0(815 знак., 11.06.2020 23:34)
        
        Стоп. Основная идея машины состояний - разделение входов, выходов и не-асинхронность. Иначе гонки можно и без очередей получить. Cкpипaч(1079 знак., 12.06.2020 10:12)

Средства и методы разработки