CSP v embedded světě

CSP v embedded světě
« kdy: 14. 03. 2021, 23:36:08 »
Čau,

snad nevadí, když nepoložím dotaz, ale (zne|vy)užiju fóra k neformálnímu brainstormingu.

V sousedním vlákně jsme s Idrisem narazili na myšlenku [1], která mi nedá spát.

V krátkosti shrnu:
  • knihovna pro embedded (tj. systémy přibližně velikosti ARM Cortex M0-3, RAM v řádu desítek až menších stovek kB)
  • API založené od základu na event-driven přístupu
  • programování využívající co nejvíc principy CSP [2]

Aniž bych si udělal nějaký větší research, zkusil jsem si představit, jestli by se dalo pro zábavu naprogramovat v C aspoň malé demo/technology preview takové knihovny. Komunikační primitiva, scheduling nejsou problém, nějaký jednoduchý virtuální stroj si případně taky umím představit. Co mi ale dělá vrásky, jsou procesy. Ty totiž musí být vytvořitelné dynamicky a knihovna jich musí zvládat potenciálně "velké" množství (definici "velké" zatím nechme být, řekněme třeba desítky?) A pokud se chceme bavit o konkurentnosti, každý proces musí mít vlastní stack. Alespoň v nějaké standardní, přímočaré implementaci.

A to už začíná být v embedded problém. Stacky musí být vyhrazené, dostatečně velké a naplno se zaplní jenom občas, navíc typicky ne naráz. Takže dost neefektivní využití paměti. A co je horší - člověk těžko získá nějakou jistou garanci, že stack bude vždy stačit. Pokud vím, obvykle se prostě nastaví "dostatečně velký", což se ale dá udělat třeba u FreeRTOSu s pár statickými tasky ručně, ale ne u předpokládaného hodně dynamického systému se spoustou procesů.

Takže otázka je, jestli vás nenapadá, čím by se daly klasické stacky nahradit, případě jestli by se nedala konkurentnost implementovat nějakým způsobem, který by problémem řídce využité a přesto potenciálně příliš malé paměti netrpěl.

Berte to prosím fakt jako brainstorming, takže žádná myšlenka není příliš pitomá nebo sci-fi, aby nemohla zaznít ;) Jde o srandu a mentální cvičení, raketu tím řídit nehodlám, takže žádná křeč ;)

[1] https://forum.root.cz/index.php?topic=24381.msg346418#msg346418
[2] https://en.wikipedia.org/wiki/Communicating_sequential_processes - tj. program je rozdělený na konkurentní procesy komunikující pomocí kanálů


Re:CSP v embedded světě
« Odpověď #1 kdy: 14. 03. 2021, 23:48:37 »
Vykopnu jeden nápad:

Jenom tak intuitivne, bez jakyhokoli researche si rikam, jestli by se nedal udelat nejaky jakoby "sdileny stack" - ze by se pouzily treba kontinuace bez moznosti returnu, takze by se nemusel udrzovat stack a kazda kontinuace by dostala cely potrebny kontext (stav) a pak by existovala treba nejaka globalni tabulka vsech kontinuaci, ze ktere by se pri kazdem kroku jenom vybrala nahodne kontinuace, ktera ja pripravena bezet. Cili misto spousty individualnich stacku by byla jedna globalni tabulka, ktera by pamet vyuzila lip a stacilo by kontrolovat, ze nepretece ona. Stav by mohl byt bud alokovany na halde, nebo by byla treba svrchu omezena jeho maximalni velikost, aby polozky v tabulce mely fixni velikost.

Prakticky by se teda program musel rozdělit na části, které by vždycky začínaly nějaký čekáním na něco - typicky na zprávu v kanálu. Z každé části by se pak udělaly funkce (callbacky). Každý callback by musel všechna data, která potřebuje, dostávat jako argumenty. "Globální stack" by potom spočíval v seznamu callbacků spolu s jejich argumenty a podmínkami, za kterých můžou běžet. Scheduler by pak prostě jenom z tabulky náhodně vybral callback, u nehož jsou podmínky splněné, a spustil ho.

Prostě princip podobný futures, resp. async/await, ale s jinou motivací a ruční implementací.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:CSP v embedded světě
« Odpověď #2 kdy: 15. 03. 2021, 00:05:35 »
každý proces musí mít vlastní stack
Proč?

Re:CSP v embedded světě
« Odpověď #3 kdy: 15. 03. 2021, 00:13:10 »
Proč?
Přijde mi to samozřejmý, ale tak asi tou otázkou někam míříš...

Protože každý task se může v danou chvíli nacházet v libovolném místě programu a potřebuje teda mít někde uložený kontext volání?

viz obrázek "Memory layout of a multi-threaded program" tady: https://ferrous-systems.com/blog/embedded-concurrency-patterns/

P.S. Posílal jsem ti tohle i jako SZ, ale jsou tady blbě viditelný, asi jsi to nepostřehl.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:CSP v embedded světě
« Odpověď #4 kdy: 15. 03. 2021, 00:14:23 »
Takže otázka je, jestli vás nenapadá, čím by se daly klasické stacky nahradit, případě jestli by se nedala konkurentnost implementovat nějakým způsobem
Nejjednodušší je mít normální zásobníky a v případě potřeby je zvětšovat. Takhle to má Go a šlape to skvěle. Na MCU by mohla každá korutina začít třeba s 512B paměti (nebo i méně) a v případě potřeby růst. Není to žádná věda.


Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:CSP v embedded světě
« Odpověď #5 kdy: 15. 03. 2021, 00:16:57 »
Proč?
Přijde mi to samozřejmý, ale tak asi tou otázkou někam míříš...

Protože každý task se může v danou chvíli nacházet v libovolném místě programu a potřebuje teda mít někde uložený kontext volání?

viz obrázek "Memory layout of a multi-threaded program" tady: https://ferrous-systems.com/blog/embedded-concurrency-patterns/

P.S. Posílal jsem ti tohle i jako SZ, ale jsou tady blbě viditelný, asi jsi to nepostřehl.
Ne, SZ jsem si všiml až teď, po upozornění :)

Samozřejmé to není, asi se shodneme na použití kooperativního multitaskingu, což implikuje použití korutin. A ty můžou být bezzásobníkové. Nicméně viz mou předchozí odpověď.

Re:CSP v embedded světě
« Odpověď #6 kdy: 15. 03. 2021, 00:27:51 »
Nejjednodušší je mít normální zásobníky a v případě potřeby je zvětšovat. Takhle to má Go a šlape to skvěle. Na MCU by mohla každá korutina začít třeba s 512B paměti (nebo i méně) a v případě potřeby růst. Není to žádná věda.
Jo, to by asi šlo. Zvlášť pokud by procesy byly short-lived jako v Erlangu, mohlo by to být dost dobrý řešení, paměť by se často uvolňovala. Zároveň by se musela sem tam kopírovat, ale na to asi sere pes ;)

Samozřejmé to není, asi se shodneme na použití kooperativního multitaskingu, což implikuje použití korutin. A ty můžou být bezzásobníkové.
Aha! Klíčové slovo teda "stackless coroutine". Co na to zatím z rychlíku dívám, přijde mi to dost podobné té má intuitivní představě.

Ok, dík, ještě na to víc kouknu, vypadá to zajímavě.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:CSP v embedded světě
« Odpověď #7 kdy: 15. 03. 2021, 00:36:18 »
Posílal jsem ti tohle i jako SZ
S dovolením odpovím tady, ať to je na očích. Jo, je to zajímavé, sám si pohrávám s myšlenkou napsat překladač (podmnožiny) Go pro MCU. Osobně bych z několika důvodů upřednostnil ty už zmíněné nafukovací zásobníky. Ten tvůj "divoký" :) nápad má v sobě rysy bezzásobníkových korutin (stackless), ale to by asi bylo na MCU zbytečně komplikované. Implicitně toho jde dosáhnout přes bloky, tak jak je má Apple v C (viz Wikipedie: https://en.wikipedia.org/wiki/Blocks_(C_language_extension)). Překladač kopíruje proměnné v případě potřeby naprosto transparentně na haldu (schválně si zkus udělat lokální int p a zírej, jak se po přesunu bloku na haldu změní &p). Tohle je alternativní cesta (výzvou pak je napsat překladač, který by to zautomatizoval).

Re:CSP v embedded světě
« Odpověď #8 kdy: 15. 03. 2021, 00:39:08 »
Ten tvůj "divoký" :) nápad
Nepopírám, že divoký. Nikdy jsem se tímhle nezabýval, překladače nikdy nebyly moje hobby :) Dík za nasměrování.

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:CSP v embedded světě
« Odpověď #9 kdy: 15. 03. 2021, 00:39:33 »
Nejjednodušší je mít normální zásobníky a v případě potřeby je zvětšovat. Takhle to má Go a šlape to skvěle. Na MCU by mohla každá korutina začít třeba s 512B paměti (nebo i méně) a v případě potřeby růst. Není to žádná věda.
Jo, to by asi šlo. Zvlášť pokud by procesy byly short-lived jako v Erlangu, mohlo by to být dost dobrý řešení, paměť by se často uvolňovala. Zároveň by se musela sem tam kopírovat, ale na to asi sere pes ;)
Jo, občas se kopíruje paměť (při nafukování zásobníku), proto se ti občas pod rukama změní ukazatel na instanci objektu (to může být zábavné, když v Go předáš ukazatel přes cgo někam ven a runtime ho při nafukování aktualizuje) :)

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:CSP v embedded světě
« Odpověď #10 kdy: 15. 03. 2021, 00:40:47 »
Samozřejmé to není, asi se shodneme na použití kooperativního multitaskingu, což implikuje použití korutin. A ty můžou být bezzásobníkové.
Aha! Klíčové slovo teda "stackless coroutine". Co na to zatím z rychlíku dívám, přijde mi to dost podobné té má intuitivní představě.
Ano, je tam jistá neinfinitezimální podobnost ;)

Re:CSP v embedded světě
« Odpověď #11 kdy: 15. 03. 2021, 00:41:21 »
Jo, občas se kopíruje paměť (při nafukování zásobníku), proto se ti občas pod rukama změní ukazatel na instanci objektu (to může být zábavné, když v Go předáš ukazatel přes cgo někam ven a runtime ho při nafukování aktualizuje) :)
To mi neva, můj quick&dirty pokus, jesti se k němu někdy dostanu, rozhodně ukazatele podporovat nebude :)

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:CSP v embedded světě
« Odpověď #12 kdy: 15. 03. 2021, 00:43:22 »
Ten tvůj "divoký" :) nápad
Nepopírám, že divoký. Nikdy jsem se tímhle nezabýval, překladače nikdy nebyly moje hobby
V jádru není divoký, jen prostě brainstormingově napsaný ;) Glad to be of help

Idris

  • *****
  • 2 286
    • Zobrazit profil
    • E-mail
Re:CSP v embedded světě
« Odpověď #13 kdy: 15. 03. 2021, 00:44:36 »
Jo, občas se kopíruje paměť (při nafukování zásobníku), proto se ti občas pod rukama změní ukazatel na instanci objektu (to může být zábavné, když v Go předáš ukazatel přes cgo někam ven a runtime ho při nafukování aktualizuje) :)
To mi neva, můj quick&dirty pokus, jesti se k němu někdy dostanu, rozhodně ukazatele podporovat nebude :)
A co to bude za jazyk?

Re:CSP v embedded světě
« Odpověď #14 kdy: 15. 03. 2021, 00:48:04 »
A co to bude za jazyk?
Tak především nevím, jestli bude, TODO list rozhodně nemám prázdný :) Ale jestli si budu chtít někdy od všeho odpočinout, představoval bych si fakt jenom úplně nejjednodušší možné demo spousty tasků na malém MCU. Naprostý minimalismus ve stylu původního Hoareho článku nebo Occamu.

Samozřejmě se nebudu babrat s překladačem, na to fakt čas nemám, jde mi jenom o naimplementování těch primitv v C.