# 改進 quiz4 (D)
contributed by < [Wallmountain](https://github.com/Wallmountain/preemptive-scheduling) >
:::warning
不用抄寫題目，直接探討和改進 [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 實作。
:notes: jserv
:::
:::spoiler
## 題目
> 以下嘗試用 lab0 提及的 [setjmp](https://man7.org/linux/man-pages/man3/setjmp.3.html) 和 [longjmp](https://man7.org/linux/man-pages/man3/setjmp.3.html)，用以實作〈[你所不知道的 C 語言: goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow)〉闡述的 [coroutine](https://en.wikipedia.org/wiki/Coroutine)，參考的程式執行輸出如下:
```cpp
Task 0: n = 3
Task 1: n = 3
Task 0: resume
Task 1: resume
Task 0: resume
Task 0: complete
Task 1: resume
Task 1: complete
```
> 原始程式碼如下: (檔名 jmp.c)
```cpp
#include <setjmp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
struct task {
jmp_buf env;
struct list_head list;
};
static LIST_HEAD(tasklist);
static void (**tasks)(void *);
static int ntasks;
static jmp_buf sched;
static void task_add(struct list_head *tasklist, jmp_buf env)
{
struct task *t = malloc(sizeof(*t));
memcpy(t->env, env, sizeof(jmp_buf));
INIT_LIST_HEAD(&t->list);
list_add_tail(&t->list, tasklist);
}
static void task_switch(struct list_head *tasklist)
{
jmp_buf env;
if (!list_empty(tasklist)) {
struct task *t = list_first_entry(tasklist, struct task, list);
list_del(&t->list);
memcpy(env, t->env, sizeof(jmp_buf));
free(t);
longjmp(env, 1);
}
}
static void task_join(struct list_head *tasklist)
{
jmp_buf env;
while (!list_empty(tasklist)) {
struct task *t = list_first_entry(tasklist, struct task, list);
list_del(&t->list);
memcpy(env, t->env, sizeof(jmp_buf));
free(t);
longjmp(env, 1);
}
}
void schedule(void)
{
static int i;
srand(0xCAFEBABE ^ (uintptr_t) &schedule); /* Thanks to ASLR */
setjmp(sched);
while (ntasks-- > 0) {
int n = rand() % 5;
tasks[i++](&n);
printf("Never reached\n");
}
task_join(&tasklist);
}
/* A task yields control n times */
void task0(void *arg)
{
jmp_buf env;
static int n;
n = *(int *) arg;
printf("Task 0: n = %d\n", n);
if (setjmp(env) == 0) {
task_add(&tasklist, env);
longjmp(sched, 1);
}
for (int i = 0; i < n; i++) {
if (setjmp(env) == 0) {
task_add(&tasklist, env);
task_switch(&tasklist);
}
printf("Task 0: resume\n");
}
printf("Task 0: complete\n");
longjmp(sched, 1);
}
void task1(void *arg)
{
jmp_buf env;
static int n;
n = *(int *) arg;
printf("Task 1: n = %d\n", n);
if (setjmp(env) == 0) {
task_add(&tasklist, env);
longjmp(sched, 1);;
}
for (int i = 0; i < n; i++) {
if (setjmp(env) == 0) {
task_add(&tasklist, env);
task_switch(&tasklist);
}
printf("Task 1: resume\n");
}
printf("Task 1: complete\n");
longjmp(sched, 1);
}
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
int main(void)
{
void (*registered_task[])(void *) = {task0, task1};
tasks = registered_task;
ntasks = ARRAY_SIZE(registered_task);
schedule();
return 0;
}
```
:::
首先，先來看 ```setjmp``` 和 ```longjmp``` 的文件
> The `setjmp()` function saves various information about the calling environment (typically, the stack pointer, the instruction pointer, possibly the values of other registers and the signal mask) in the buffer env for later use by `longjmp()`. In this case, `setjmp()` returns 0.
```setjmp``` 可跨越函式，在任意程式碼之間跳躍 (即 non-local goto)，儲存目前位置資訊，之後可以使用 ```longjmp``` 跳躍到目前儲存的位置
> The `longjmp()` function uses the information saved in env to transfer control back to the point where setjmp() was called and to restore ("rewind") the stack to its state at the time of the setjmp() call. In addition, and depending on the implementation (see NOTES), the values of some other registers and the process signal mask may be restored to their state at the time of the `setjmp()` call.
修改原程式碼中的 ```task``` 函式，印出變數的數值，去看執行結果是否符合預期
```cpp
void task0(void *arg)
{
jmp_buf env;
static int n;
n = *(int *) arg;
printf("Task 0: n = %d\n", n);
if (setjmp(env) == 0) {
task_add(&tasklist, env);
longjmp(sched, 1);
}
for (int i = 0; i < n; i++) {
if (setjmp(env) == 0) {
task_add(&tasklist, env);
task_switch(&tasklist);
}
printf("Task 0: resume %d\n", i);
}
printf("Task 0: complete %d\n", n);
longjmp(sched, 1);
}
```
在下面的狀況下，執行結果並不符合預期，在 task 0 中的區域變數 ```i``` 在 task 1 完成後，發生了非預期的變化，變數 ```i``` 的值和原先尚未 ```longjmp``` 前不同。
```cpp
Task 0: n = 2
Task 1: n = 0
Task 1: complete 0
Task 0: resume 22052
Task 0: complete 2
```
而問題在文件中有提到
> The compiler may optimize variables into registers, and longjmp()
may restore the values of other registers in addition to the
stack pointer and program counter. Consequently, the values of
automatic variables are unspecified after a call to longjmp() if
they meet all the following criteria:
• they are local to the function that made the corresponding
setjmp() call;
• their values are changed between the calls to setjmp() and
longjmp(); and
• they are not declared as volatile.
在編譯器優化後， ```longjmp``` 可能不會恢復 ```stack``` 中的變數，於是將變數 ```i``` 宣告成靜態變數，變數 ```i``` 便不會放在 ```stack``` 中了，以此解決這邊因為編譯器造成的問題。
```cpp
Task 0: n = 4
Task 1: n = 3
Task 0: resume 0
Task 1: resume 0
Task 0: resume 1
Task 1: resume 1
Task 0: resume 2
Task 1: resume 2
Task 1: complete 3
Task 0: resume 3
Task 0: complete 4
```
在 [preempt_sched](https://github.com/sysprog21/concurrent-programs/blob/master/preempt_sched/task_sched.c) 有實作 preemptive scheduling，將 ```task``` 以鏈結的形式儲存
> 若在將新工作加入鏈結或刪除鏈結中的工作時被搶占，則有機會發生工作遺失的問題，因此加入靜態變數 ```preempt_count```，當在需要更改工作的鏈結時，將其改成不能被搶占，便能解決 [race condition](https://en.wikipedia.org/wiki/Race_condition)
```cpp
static int preempt_count = 0;
static void preempt_disable(void)
{
preempt_count++;
}
static void preempt_enable(void)
{
preempt_count--;
}
```
在 [preempt.h](https://elixir.bootlin.com/linux/v5.8.9/source/include/asm-generic/preempt.h#L9) 中，有用到以下的程式碼，也顯示了在 linux kernel 中各個執行緒擁有其各自的變數 ```preempt_count```，在需要搶佔時，必須去確定當前執行緒是否能夠被搶佔
```cpp
static __always_inline int preempt_count(void)
{
return READ_ONCE(current_thread_info()->preempt_count);
}
```
> 0-7 bit 為 preempt-disable count 紀錄到目前為止，搶占被禁止的次數
> 接著三個 count 為分別記錄執行緒被中斷的次數
> 8-15 bit 為 Software interrupt count
> 16-19 bit 為 Hardware interrupt count
> 20-23 bit 為 Non-maskable interrupt count
接著，來研究 ```signal``` 使用方式，以下為 ```sigaction``` 的結構
```cpp
struct sigaction {
void (*sa_handler)(int);
void (*sa_sigaction)(int, siginfo_t *, void *);
sigset_t sa_mask;
int sa_flags;
void (*sa_restorer)(void);
};
```
> ```sa_handler``` 為 function pointer，代表訊號產生時要做的行為
> ```sa_sigaction``` 只有在當 ```sa_flags``` 被賦值為 ```SA_SIGINFO``` 時，取代 ```sa_handler``` 成為訊號產生時要做的行為
當 ```sa_flags``` 被賦值為 ```SA_SIGINFO``` 時，```handler``` 會轉變成指向帶有三個參數的函式的指標
```cpp
void handler(int sig, siginfo_t *info, void *ucontext)
{
...
}
```
> ```sig``` 為導致觸發信號處理函式的信號編號
> ```info``` 為指向帶有信號資訊結構的指標
> ```ucontext``` 為指向結構 ```ucontext_t``` 的指標，用來記錄存在 ```user space stack``` 中的信號內容
```cpp
typedef struct ucontext_t {
struct ucontext_t *uc_link;
sigset_t uc_sigmask;
stack_t uc_stack;
mcontext_t uc_mcontext;
...
} ucontext_t;
```
> ```uc_link``` 為指向下一個內容的指標，當前的 ```context``` 可用 [makecontext](https://man7.org/linux/man-pages/man3/makecontext.3.html) 建立
為避免在 ```printf``` 此類系統呼叫時被搶占，故將其包夾成一個 crititcal section
```cpp
#define task_printf(...) \
({ \
preempt_disable(); \
printf(__VA_ARGS__); \
preempt_enable(); \
})
```
設定多久之後要觸發訊號 ```SIGALRM```，而之後會不會繼續每隔一段時間觸發訊號，則是要另外設定間格時間
```cpp
static void timer_create(unsigned int usecs)
{
ualarm(usecs, usecs);
}
```
:::warning
問題 :
訊號觸發後，程式會跳到後續的處理函式，但由於跳轉前的函式執行位置來不及去用 ```setjmp``` 進行記錄，因此便會造成程式執行結果不符合預期
在原程式碼中，在每一次 ```longjmp``` 前，都會用 ```setjmp``` 儲存當前函式進行的進度
```cpp
if (setjmp(env) == 0) {
task_add(&tasklist, env);
longjmp(sched, 1);
}
```
:::
> ```ucontext_t``` 需要儲存所有暫存器的資料，而 ```jmp_buf``` 只需要儲存有用到的暫存器即可，因此 ```ucontext_t``` 會比 ```jmp_buf``` 大不少
:::info
對照 ==[cserv](https://hackmd.io/@ycwu4142/linux2022-cserv)== 的 coroutine (也叫做 `coro`) 實作，裡頭的 context 切換成本較低，且考慮到排程。
:notes: jserv
:::
> 在 [setjmp](https://man7.org/linux/man-pages/man3/setjmp.3.html) 中，有介紹 ```sigsetjmp``` 會另外紀錄 ```signal mask```， 之後再用 ```siglongjmp``` 回到記錄點
一開始，在[程式](https://github.com/Wallmountain/preemptive-scheduling/commit/efbdf2c41fbbf25c6665f2b397dca5c5abed3d4d)當中加入每隔一段時間會觸發訊號，而結果發生問題
```cpp
Task 0: n = 0
Task 0: n = 0
signal
Task 1: n = 3
Task 0: complete 0
Task 0: complete 0
signal
Task 1: resume 0
Task 1: resume 1
Task 1: resume 1
signal
Task 1: resume 2
Task 1: complete 3
Task 1: complete 3
signal
```
Sign in with Wallet
Connect another wallet