Voluntary Context Switch

先從最基本的開始，想要達成 multi-tasking，至少需要有 voluntary context switch 的功能，也就是說 context switch 發生的時機在程式主動呼叫 scheduler 來進行 schedule。

注意：scheduler 指的是一段程式，用來決定下一個 task 該跑誰，而非一個 process

Task Structure

用來保存 task 的一些資訊。

schedule.h

 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
struct cpu_context {
    // ARM calling convention
    // x0 - x18 can be overwritten by the called function
    uint64_t x19;
    uint64_t x20;
    uint64_t x21;
    uint64_t x22;
    uint64_t x23;
    uint64_t x24;
    uint64_t x25;
    uint64_t x26;
    uint64_t x27;
    uint64_t x28;
    uint64_t fp;  // x29
    uint64_t lr;  // x30
    uint64_t sp;
};

enum task_state {
    RUNNING,
    ZOMBIE,
    EXIT,
};

struct task_t {
    uint64_t id;
    enum task_state state;
    int priority;
    int counter;
    int need_resched;
    int exit_status;
    struct cpu_context cpu_context;
};

task_state 沒有 IDLE 是因為我還想不到要用 IDLE 的時機。目前我是直接從一個 priority queue 拿，有需要被 schedule 到就 push 進去，所以有沒有 IDLE 好像也沒差了 (?) (歡迎糾正)

schedule.c

1
struct task_t task_pool[TASK_POOL_SIZE];

Task Priority Queue

這邊也順便做了 elective 2 的需求，task_t 上的 prority 用來表示該 task 的優先程度，優先程度越高會先被 schedule 到。

queue.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
struct task_queue_elmt_t {  /* priority queue */
    struct task_t* task;
    struct task_queue_elmt_t* prev;
    struct task_queue_elmt_t* next;
};

struct task_queue_t {
    struct task_queue_elmt_t* front;
    struct task_queue_elmt_t* rear;
};

queue.c

我偷懶直接用 linked list 在 push 的時候檢查順序，然後找對的地方 insert 進去，使用 heap 應該效果更佳。

 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
void task_queue_init(struct task_queue_t* q) {
    q->front = 0;
    q->rear = 0;
}

void task_queue_elmt_init(struct task_queue_elmt_t* elmt, struct task_t *task) {
    elmt->task = task;
    elmt->next = 0;
    elmt->prev = 0;
}

void task_queue_push(struct task_queue_t* q, struct task_queue_elmt_t* elmt) {
    if (q->front == 0) {
        q->front = elmt;
        q->rear = elmt;
    }
    // task priority is largest
    else if (elmt->task->priority > q->front->task->priority) {
        q->front->next = elmt;
        elmt->prev = q->front;
        q->front = elmt;
    }
    // task priority is smallest
    else if (elmt->task->priority <= q->rear->task->priority) {
        q->rear->prev = elmt;
        elmt->next = q->rear;
        q->rear = elmt;
    }
    // q->front->priority >= elmt->task->priority > q->last->priority
    else {
        // find appropriate place to insert
        struct task_queue_elmt_t *ptr = q->rear;
        while (ptr->next != 0 && elmt->task->priority > ptr->task->priority) {
            ptr = ptr->next;
        }
        // push elmt to back of ptr
        elmt->next = ptr;
        elmt->prev = ptr->prev;
        // relink before and after element
        ptr->prev->next = elmt;
        ptr->prev = elmt;
    }
}

struct task_t* task_queue_pop(struct task_queue_t* q) {
    if (q->front == 0) {
        return &task_pool[0];
    }
    else if (q->front == q->rear) {
        struct task_queue_elmt_t* pop_elmt = q->front;
        struct task_t* pop_task = pop_elmt->task;
        pop_elmt->next = 0;
        pop_elmt->prev = 0;
        q->front = 0;
        q->rear = 0;
        return pop_task;
    }
    else {
        struct task_queue_elmt_t* pop_elmt = q->front;
        struct task_t* pop_task = pop_elmt->task;
        q->front = pop_elmt->prev;
        pop_elmt->next = 0;
        pop_elmt->prev = 0;
        return pop_task;
    }
}

schedule.c

1
2
3
4
5
6
7
8
9
struct task_queue_elmt_t runqueue_elmt_pool[TASK_POOL_SIZE];
struct task_queue_t runqueue;

void runqueue_init() {
    for (int i = 0; i < TASK_POOL_SIZE; i++) {
        task_queue_elmt_init(&runqueue_elmt_pool[i], &task_pool[i]);
    }
    task_queue_init(&runqueue);
}

Create privilege tasks

傳進 function pointer 與 priority，找到沒在用的 task，初始化他的 task structure，並將該 task 的 cpu_context 做設定：

lr 指到 function pointer
fp 指到該 task 所屬的 kernel stack
sp 指到該 task 所屬的 kernel stack

目前還沒有 Dynamic Allocator，所以 stack 先使用靜態宣告

schedule.c

我在這邊採到一個雷，一開始我將 KSTACK_TOP_IDX 設成 KSTACK_SIZE - 1，發現 QEMU 上可以動，但是實體機上卻出現問題，後來才發現sp 需要 16 bytes 的 alignment，把它設成 KSTACK_SIZE - 16 就可以了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
char kstack_pool[TASK_POOL_SIZE][KSTACK_SIZE];
char ustack_pool[TASK_POOL_SIZE][USTACK_SIZE];

int privilege_task_create(void (*func)(), int priority) {
    struct task_t *new_task;
    for (int i = 0; i < TASK_POOL_SIZE; i++) {
        if (task_pool[i].state == EXIT) {
            new_task = &task_pool[i];
            break;
        }
    }

    new_task->state = RUNNING;
    new_task->priority = priority;
    new_task->counter = TASK_EPOCH;
    new_task->need_resched = 0;
    new_task->cpu_context.lr = (uint64_t)func;
    new_task->cpu_context.fp = (uint64_t)(&kstack_pool[new_task->id][KSTACK_TOP_IDX]);
    new_task->cpu_context.sp = (uint64_t)(&kstack_pool[new_task->id][KSTACK_TOP_IDX]);

    task_queue_push(&runqueue, get_runqueue_elmt(new_task));

    return new_task->id;
}

Context switch

從 task queue 取出一個 target task，將目前的 task push 進 task queue，將目前的 task 更新成 target task，並執行 context switch。

schedule.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void context_switch(struct task_t* next) {
    struct task_t* prev = get_current_task();
    if (prev->state == RUNNING) {
        task_queue_push(&runqueue, get_runqueue_elmt(prev));
    }
    update_current_task(next);
    switch_to(&prev->cpu_context, &next->cpu_context);
}

void schedule() {
    struct task_t* next = task_queue_pop(&runqueue);
    context_switch(next);
}

schedule.S

1
extern void switch_to(struct cpu_context* prev, struct cpu_context* next);

將狀態保存在自己的 kernel stack，以 task 1 換到 task 2 為例:

+------------------------+ 0
|           .            |
+------------------------+
| kernel image           |
|------------------------|
|           .            |
|           .            |
|------------------------| <- 3. sp before task 2 context restoring
| task 2 saved registers |
|------------------------| <- 4. sp after switch_to
|           .            |
+------------------------+ <- task 2 kenrel stack
|           .            |
|           .            |
|------------------------| <- 2. sp after task 1 context saving
| task 1 saved registers |
|------------------------| <- 1. sp before switch_to
|           .            |
+------------------------+ <- task 1 kenrel stack

備註: sp 是往記憶體位址低的方向長的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
.global switch_to
switch_to:
    mov x9, sp
    stp x19, x20, [x0, 16 * 0]
    stp x21, x22, [x0, 16 * 1]
    stp x23, x24, [x0, 16 * 2]
    stp x25, x26, [x0, 16 * 3]
    stp x27, x28, [x0, 16 * 4]
    stp fp, lr,   [x0, 16 * 5]
    str x9,       [x0, 16 * 6]

    ldp x19, x20, [x1, 16 * 0]
    ldp x21, x22, [x1, 16 * 1]
    ldp x23, x24, [x1, 16 * 2]
    ldp x25, x26, [x1, 16 * 3]
    ldp x27, x28, [x1, 16 * 4]
    ldp fp, lr,   [x1, 16 * 5]
    ldr x9,       [x1, 16 * 6]
    mov sp, x9
    ret

Idle task

我把一開始在 EL1 進行初始化的 task 當作是 idle task (task 0)，在初始化結束後會主動呼叫 schedule() 來 context switch 到別的 task。如果 idle task 被 scheduler 給 schedule 到，那他會進入無限迴圈主動呼叫 schedule()，直到有其他 task 被 schedule 到。

main.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void boot_init() {
    task_init();

    ...

    schedule_init();
    while (1) {
        schedule();
    }
}

schedule.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void task_init() {
    for (int i = 0; i < TASK_POOL_SIZE; i++) {
        task_pool[i].id = i;
        task_pool[i].state = EXIT;
        task_pool[i].need_resched = 0;
    }
    // idle task
    task_pool[0].state = RUNNING;
    task_pool[0].priority = 0;
    update_current_task(&task_pool[0]);
}

void schedule_init() {
    runqueue_init();
    privilege_task_create(zombie_reaper, 10);

    // privilege_task_create(demo_task_1, 10);
    // privilege_task_create(demo_task_2, 10);
    // privilege_task_create(demo_do_exec, 15);
    privilege_task_create(demo_syscall, 10);

    arm_core_timer_enable();
    schedule();
}

狀態轉移範例

圖片來自 Lab 4 Spec

Voluntary context switch 的缺點在於，若要進行 context switch，必須由程式主動呼叫 schedule() 才能切換 task，可能會因此產生 starvation 的問題。