From 81779e3dd91e147c883974588a3be0410f225d42 Mon Sep 17 00:00:00 2001 From: Johannes Stoelp Date: Sun, 28 Apr 2024 18:31:51 +0200 Subject: xpost: add figure to match threads --- content/2023-01-14-xpost-matcha-threads/gen-svg.sh | 3 + content/2023-01-14-xpost-matcha-threads/index.md | 91 ++++++++++ .../os-vs-user-threads.drawio | 185 +++++++++++++++++++++ .../os-vs-user-threads.svg | 3 + 4 files changed, 282 insertions(+) create mode 100644 content/2023-01-14-xpost-matcha-threads/gen-svg.sh create mode 100644 content/2023-01-14-xpost-matcha-threads/index.md create mode 100644 content/2023-01-14-xpost-matcha-threads/os-vs-user-threads.drawio create mode 100644 content/2023-01-14-xpost-matcha-threads/os-vs-user-threads.svg (limited to 'content/2023-01-14-xpost-matcha-threads') diff --git a/content/2023-01-14-xpost-matcha-threads/gen-svg.sh b/content/2023-01-14-xpost-matcha-threads/gen-svg.sh new file mode 100644 index 0000000..365e243 --- /dev/null +++ b/content/2023-01-14-xpost-matcha-threads/gen-svg.sh @@ -0,0 +1,3 @@ +#!/bin/bash + +drawio -x -f svg -t --svg-theme dark -o os-vs-user-threads.svg os-vs-user-threads.drawio diff --git a/content/2023-01-14-xpost-matcha-threads/index.md b/content/2023-01-14-xpost-matcha-threads/index.md new file mode 100644 index 0000000..3456b09 --- /dev/null +++ b/content/2023-01-14-xpost-matcha-threads/index.md @@ -0,0 +1,91 @@ ++++ +title = "xpost: Cooperative-multitasking studies (matcha-threads)" + +[taxonomies] +tags = ["threading", "linux", "x86", "arm", "riscv"] ++++ + +This is a cross post to a **cooperative-multitasking implementation** that I +did in the past and hosted on github [>> matcha-threads <<][matcha]. + +Cooperative-multitasking allows to perform the thread scheduling in user space. +Executing threads need to give the control back to the `scheduler` such that +other threads can run. Since control is returned explicitly to the scheduler, +threads need to **"cooperate"**. + +The following code snippet shows an example of two such threads: +```cpp +#include "lib/executor.h" +#include "lib/thread.h" +#include + +void like_tea(nMatcha::Yielder& y) { + std::puts("like"); + y.yield(); + std::puts("tea"); +} + +int main() { + nMatcha::Executor e; + e.spawn(nMatcha::FnThread::make(like_tea)); + e.spawn(nMatcha::FnThread::make([](nMatcha::Yielder& y) { + std::puts("I"); + y.yield(); + std::puts("green"); + })); + e.run(); + return 0; +} +``` + +Which gives the following output when being run: +```txt +I +like +green +tea +``` + +The main focus of that project was to understand the fundamental mechanism +underlying cooperative-multitasking and implement such a `yield()` function as +shown in the example above. + +Looking at the final implementation, the yield function does the following: +```txt +yield: + 1. function prologue + 2. push callee-saved regs to current stack + 3. swap stack pointers (current - new) + 4. pop callee-saved regs from new stack + 5. function epilogue & return +``` + +Implementations for different ISAs are available here: +- [x86_64][yield-x86] +- [arm64][yield-arm64] +- [armv7a][yield-arm] +- [riscv64][yield-rv64] + +## Appendix: os-level vs user-level threading + +The figure below depicts *os-level* threading (left) vs *user-level* threading +(right). + +The main difference is that in the case of user-level threading, the operating +system (os) does not now anything about the user threads. In the concrete +example, only a **single** user thread can run at any given time, whereas in +the case of os-level threading, all threads can run truly parallel. + +When a user-level thread is scheduled, the *stack-pointer* (sp) of the os +thread is adjusted to the user threads' stack. For the example below, if the +user thread **A** is scheduled (yielded to), the stack-pointer for the os +thread **S** is switched to the **stack A**. Once the user thread yields back +to the scheduler, the stack-pointer is switched back to **stack S**. + + + +[matcha]: https://github.com/johannst/matcha-threads +[yield-x86]: https://github.com/johannst/matcha-threads/blob/master/lib/arch/x86_64/yield.s +[yield-arm]: https://github.com/johannst/matcha-threads/blob/master/lib/arch/arm/yield.s +[yield-arm64]: https://github.com/johannst/matcha-threads/blob/master/lib/arch/arm64/yield.s +[yield-rv64]: https://github.com/johannst/matcha-threads/blob/master/lib/arch/riscv64/yield.s diff --git a/content/2023-01-14-xpost-matcha-threads/os-vs-user-threads.drawio b/content/2023-01-14-xpost-matcha-threads/os-vs-user-threads.drawio new file mode 100644 index 0000000..1eacde1 --- /dev/null +++ b/content/2023-01-14-xpost-matcha-threads/os-vs-user-threads.drawio @@ -0,0 +1,185 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/content/2023-01-14-xpost-matcha-threads/os-vs-user-threads.svg b/content/2023-01-14-xpost-matcha-threads/os-vs-user-threads.svg new file mode 100644 index 0000000..38103d0 --- /dev/null +++ b/content/2023-01-14-xpost-matcha-threads/os-vs-user-threads.svg @@ -0,0 +1,3 @@ + + +
process address space
process address space
stack A
stack A
stack B
stack B
stack C
stack C
process address space
process address space
stack S
stack S
stack A
stack A
stack C
stack C
user thread
user thread
stack B
stack B
thread
S
thread...
OS thread
OS thread
user thread
user thread
user thread
user thread
yield
yield
yield
yield
yield
yield
thread
A
thread...
thread
B
thread...
thread
C
thread...
thread
A
thread...
OS thread
OS thread
thread
B
thread...
OS thread
OS thread
thread
C
thread...
OS thread
OS thread
sp
sp
sp
sp
sp
sp
sp
sp
sp when yielding to A
sp when yielding to AText is not SVG - cannot display \ No newline at end of file -- cgit v1.2.3