Concurrency support

[melkyades]

This is a broad topic, too big for just a issue. I would like to hear opinions about what kind of concurrency can be supported initially and in the future. These are my (@melkyades) initial thoughts about the topic.

The Process class in Egg is for now being implemented as coroutines. This means that there is no preemption, a process needs to yield or suspend in order to let other processes run. Of course, there's only one thread, and the system is exceptionally simple, which is great.

My initial question was if preemption support would be a positive or negative addition for the rest of the system. It might prove useful for the NOS platform, where each IRQ is handled by a different process. What would be other benefits of preemption support? How hard would it be to migrate the non-preemptive system to a preemptive one? Could we have support for both things at the same time?

For data-oriented multiprocessing, I'd prefer to have numba/anydsl alike support: the compiler takes as input a small code corpus of dynamic code and generates enough type information to convert it into a statically linked IR that can be run independently of the runtime and parallelized in different ways: simd, multiple processes, gpu. This approach has proven doable and leaves most complexity out to other frameworks, so it is the one that would give most benefits for less effort.

I'd rather not have application developers deal manually with multithreading and multiprocessing. It is extremely prone to race conditions and deadlocks, so they should be provided with good enough abstractions that solve most of their problems. The question is, what abstractions would those be?

In the most general case of a many-core system (multiple general process running different code synchronized in arbitrary ways), I'd prefer a system of multiple OS processes with shared parts of memory rather than multiple threads in the same process. I believe this can make the VM simpler, but I'm not sure.

Finally, Egg's concurrency support should aim for simplicity, we are not trying to create the concurrent system of the future, but just not-much-less-than-what-others-can-already-do :)

[KenDickey]

First, why concurrency? To reduce wait times; react to sensor events.

• GUI
• INet ports; I/O interrupts in general
• Timers (Timer service interrupts)
• System Services which take significant time (want non-blocking)
• Multicore Concurrent GC (e.g. http://doc.cat-v.org/inferno/concurrent_gc/ https://kcsrk.info/multicore/gc/2017/07/06/multicore-ocaml-gc/ )

Intuitively, I would look at

• microkernel abstractions/structure for cooperative components/separability
• functional data structures need no locking (e.g. use ropes rather than strings)

Exception handling interacts (because of stack capture). There are a bunch of papers on interaction between Scheme's continuations and multiprocessing (e.g. ref in https://github.com/schemedoc/bibliography). Capturing thisContext shares many strategies with capturing continuations. In both cases one ends up with spaghetti/cactus stacks and must be careful of when it is safe to interrupt.

Note Erlang-like concurrency in Termite Scheme: https://www-labs.iro.umontreal.ca/~feeley/papers/GermainFeeleyMonnierSW06.pdf . Also "futures".

Boy, it this a deep cavity to explore!

[melkyades]

Yep, there quite enough reasons to support concurrency. My doubts here are more concrete, what do you think about these:

• Should concurrency support be mandatory in kernel? (it can be useful to avoid it in minimal kernels). If not, how would we implement such a system in practice?
• Should the system be designed as preemptive or non-preemptive? can we support both at the same time?
• Should we go for a concurrency model where multiple process share mem zones or single process thead-based share all?
• Which other more or less automatic concurrency framework would you prefer? Promises? Actors? Some other thing?

[KenDickey]

? Should concurrency support be mandatory in kernel? (it can be useful to avoid it in minimal kernels). If not, how would we implement such a system in practice?

How is this different from, e.g. exception handling where one typically spawns a new thread (regs+stack). Once one has multiple threads...
Multicore SoCs are cheap and common these days. Over time there will be a usage cost to keeping this out.

? Should the system be designed as preemptive or non-preemptive? can we support both at the same time?

Does one want to maintain two variants of similar code? How would one make concurrency optional+additive?
I think much of the mutex/monitor race-condition complexity comes from adding concurrency to linear/non-concurrent runtimes.
Note that Gambit Scheme supports millions of lightweight threads: http://gambitscheme.org/wiki/index.php/Main_Page
So examples exist.

? Should we go for a concurrency model where multiple process share mem zones or single process thead-based share all?
I favor Per-Thread Arenas as outlined in
https://github.com/dvmason/Zag-Smalltalk/blob/main/Documentation/MemoryManagement.md
One could think of designated thread-originated objects which are promoted to a shared arena with a write barrier specialized to maintain some invariant needed for global access but not needed within an per-core arena.

? Which other more or less automatic concurrency framework would you prefer? Promises? Actors? Some other thing?

What are the use cases? I can see using multicore to spawn off tasks/processes for compute intensive CPU or GPU processing with somethink like Erlang/Termite-Scheme. Different from processing many other things while some threads block on I/O.

Robustness vs simplicity.

Architect to spawn small runtimes might be an option.
Idea source: "Multi-language task migration" strategy which includes continuations
http://www.iro.umontreal.ca/~feeley/papers/FeeleyDLS15.pdf - paper
https://www.iro.umontreal.ca/~gambit/migrate-dls15-talk.pdf - slides

If you are unafraid of parentheses, there are code examples for multithreading using mutex/condvars:
https://srfi.schemers.org/srfi-18/srfi-18.html
https://srfi.schemers.org/srfi-21/srfi-21.html

More mumble later..

[melkyades]

How is this different from, e.g. exception handling where one typically spawns a new thread (regs+stack). Once one has multiple threads...

My idea was to enable something that, in case of an error, would just produce a fatal error. We might be able to design a system where Processes, Semaphores and all that stuff is a module that could be loaded optionally. My question is whether supporting that would be worth the cost.

Does one want to maintain two variants of similar code? How would one make concurrency optional+additive?

Well, no :). I wouldn't want to maintain two versions, again, I'm wondering about costs and benefits of each. Gambit scheme looks very interesting in general. I don't have enough time to dedicate to explore it, but found the following piece of documentation which makes me wonder how they do multiprocessing:

Gambit supports the execution of multiple Scheme threads. These threads are managed entirely by Gambit’s runtime and are not related to the host operating system’s threads. Gambit’s runtime does not currently take advantage of multiprocessors (i.e. at most one thread is running).

I favor Per-Thread Arenas as outlined in
https://github.com/dvmason/Zag-Smalltalk/blob/main/Documentation/MemoryManagement.md
One could think of designated thread-originated objects which are promoted to a shared arena with a write barrier specialized to maintain some invariant needed for global access but not needed within an per-core arena.

Yep, me too. Unfortunately the per-thread arena solve only the allocation part, synchronization still is the bulk work and there's a lot of shared state in global objects in a global heap.

[KenDickey]

Popping up a level. Dan Ingalls rubric:
"Reactive Principle: Every component accessible to the user should be able to present itself in a
meaningful way for observation and manipulation"

I think the key to gleaning from all the various possible mechanisms is to maintain a sensible viewpoint.

Back toward the beginning of time a couple of guys, Suresh Jagannathan and Jim Philbin, published some papers on concurrent building block abstract objects like Virtual Processors and Threads.

https://www.researchgate.net/publication/2819936_A_Customizable_Substrate_for_Concurrent_Languages
https://www.researchgate.net/publication/2419746_High-Level_Abstractions_for_Efficient_Concurrent_Systems
https://www.researchgate.net/publication/2508143_Virtual_Topologies_A_New_Concurrency_Abstraction_for_High-Level_Parallel_Languages

Think "assigning thread to processor" == "scheduling" but with more useful semantics.

Later, this resulted in a distributed runtime, "Kali Scheme", with mobile threads. [Aside: Kali Scheme was implemented on Scheme48 which was the "VM written in Scheme compile to C" which inspired Squeak].

https://dl.acm.org/doi/pdf/10.1145/213978.213986

Note also ideas in: "Transactional Monitors for Concurrent Objects" to avoid explicit locking
https://www.cs.purdue.edu/homes/suresh/papers/ecoop04.pdf

====Before I forget
some useful observations in "Polling efficiently on stock hardware"
https://www.cs.tufts.edu/comp/150FP/archive/marc-feeley/polling.pdf

[KenDickey]

On 2024-01-26 05:40, Javier Pimas wrote: ..

Well, no :). I wouldn't _want_ to maintain two versions, again, I'm wondering about costs and benefits of each. Gambit scheme looks very interesting in general. I don't have enough time to dedicate to explore it, but found the following piece of documentation which makes me wonder how they do multiprocessing:

They are basically doing shared memory. Bare metal proof of concept: https://icfp20.sigplan.org/details/scheme-2020-papers/3/Running-Scheme-On-Bare-Metal-Experience-Report- # Then Click on "File Attached" for paper Code at: https://github.com/udem-dlteam/mimosa Virtual memory multi-address space mechanics: -------------------------------------------- XV6 (MIT mini OS) https://pdos.csail.mit.edu/6.828/2022/xv6/book-riscv-rev3.pdf - Book PDF https://github.com/michaelengel/xv6-vf2 - Vision Five 2 (riscv) https://github.com/zhiyihuang/xv6_rpi_port - Raspberry Pi (arm) NuttX RTOS https://github.com/lupyuen/pinephone-nuttx (arm) https://www.hackster.io/lupyuen/rtos-on-a-risc-v-sbc-star64-jh7110-apache-nuttx-2a7429 (riscv) bungha deep dives at https://lupyuen.github.io/ Basic strategy is to map trampoline area to all address spaces, but super access only so kernel call (ecall) or interrupt is directed via code uniformly mapped to all address spaces. For me, the real interest is in strategies used in the Sting OS. Note James Philbin's Thesis: https://cpsc.yale.edu/sites/default/files/files/tr997.pdf

Unfortunately the per-thread arena solve only the allocation part, synchronization still is the bulk work and there's a lot of shared state in global objects in a global heap.

Note that Bee/Egg runtime has a big advantage WRT things like write barriers. Local thread stack and heap areas don't need to check, but when an object is GC'd into a shared heap area, its Behavior is prepended with a method dict which contains setter overrides (#at:put: ..) with write barrier. The way to think about this is there is a subclass of Joe Object's class which contains the overrides and it is this dict which is interposed into the head of the Behavior chain. PICs respect the "class change" of this instance, and everyone is happy (modulo code design maintaining invariants). Aside from the Sting OS, there are a number of strategies which relate to vary different use-cases. Let me confabulate a bit here. Warning: my development model is kinda like papers & runtimes ----------->Idea Soup------>painting on clouds-->cast in jello-->prototype-->observe+refine mine ideas cook You know Ropes, right? Immutable strings. Share structure. Mutators memoize changes/deltas and return a new rope. So a text editor keeps a history of ropes. Undo is setting current-rope to a previous and redisplay. Redo is set current-rope to newer and redisplay. Immutable => no worries with multithreading. Carrying this idea a bit further. Think about a collection with, say multiple readers and a single mutator. Let's say the important thing is that readers only see a consistent collection (e.g. to iterate over) and we can be a bit sloppy on when items are added or removed. One strategy would be to make a shallow/shadow copy which the mutator thread sees and let the readers see the original collection. When we get to a stable point, one can assign to the value holder to commit the update. Atomic assignment is basically a short term write barrier which blocks reader threads until the assignment is complete. Many variants on this theme. I think of implementing invariant policy as data structure problem/design. Also, presenting system => disk, keyboard/UART, mouse, display .. as objects. Oh, yet another basket of papers: https://research.scheme.org/concurrency/

[KenDickey]

Oh, downstream: Genode microkernel (https://genode.org/) has a very ineresting GUI controller called NitPicker which allows a componentized system to safely share the screen, including drag 'n drop mechanics.

https://genode-labs.com/publications/nitpicker-secure-gui-2005.pdf