1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
+++
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 <cstdio>
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:
1. push callee-saved regs to current stack
2. swap stack pointers (current - new)
3. pop callee-saved regs from new stack
<img src="yield.svg">
Implementations for different ISAs are available here:
- [x86_64][yield-x86]
- [arm64][yield-arm64]
- [armv7a][yield-arm]
- [riscv64][yield-rv64]
<div style="overflow: auto;">
<img src="init-stack.svg" style="float: right; width: 25%; padding-left: 2ch;">
Since a thread returns into the last stack-frame of the new thread after
switching the stack pointers in the yield function, special care must be taken
when a new stack is created.
The _initial stack_ is setup such that, when yield-ing into the new stack for
the first time, the stack contains the initial values for the callee-saved
registers, which yield will restore and the return frame contains an address
which should be returned to when returning from yield.
An example of setting up the initial stack can be seen in [init_stack
(x86)][init-stack]. From this it can also be seen that the first time the
thread will return to [thread_create][thread-create], which just calls into a
function passed to [init_stack][init-stack].
</div>
## 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 know 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**.
<img src="os-vs-user-threads.svg">
[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
[init-stack]: https://github.com/johannst/matcha-threads/blob/master/lib/arch/x86_64/init_stack.cc
[thread-create]: https://github.com/johannst/matcha-threads/blob/master/lib/arch/x86_64/thread_create.s
|
