任务调度系统：task_t 与上下文切换

Souloss

公告

欢迎来到我的博客！这是一条示例公告

Learn More

标签

Souloss

公告

欢迎来到我的博客！这是一条示例公告

Learn More

标签

Souloss

公告

欢迎来到我的博客！这是一条示例公告

Learn More

标签

1904 字

5 分钟

任务调度系统：task_t 与上下文切换

2021-07-04

操作系统

/

底层原理

早期计算机一次只能运行一个程序。多任务的出现让计算机看起来能同时做很多事，本质上是快速切换任务造成的错觉。在单核 CPU 上，任何时刻只有一条指令流在执行，所谓”并发”不过是调度器在多个任务之间来回跳转的结果。

多任务的动机#

单任务系统的局限显而易见：一个程序独占 CPU，其他程序只能等待。如果当前程序进入死循环，整个系统就卡住了。时间共享（time-sharing）的思路是给每个任务分配一小段 CPU 时间，用完就换下一个任务运行。这样即使某个任务卡死，其他任务仍然有机会执行。

任务调度系统需要解决四个问题：

CPU 时间分配：如何公平地将 CPU 时间分配给多个任务？
上下文保存：切换任务时，如何保存和恢复任务的执行状态？
任务管理：如何创建、销毁和管理任务的元数据？
资源同步：如何防止多个任务同时访问共享资源？

task_t 结构#

每个任务都需要保存自己的状态信息，包括任务 ID、运行状态、优先级、内核栈指针等。这些信息需要被操作系统持久保存，以便在任务切换时能够恢复。task_t 结构是操作系统中任务的核心数据结构，它包含了任务的所有元数据和运行时状态：

1
typedef struct task {
2
    /* identity - 任务标识 */
3
    tid_t tid;              /* 任务 ID */
4
    pid_t tgid;             /* 线程组 ID */
5
    char name[16];          /* 任务名称 */
6

7
    /* owner process - 所属进程 */
8
    struct process *owner;
9

10
    /* scheduling - 调度相关 */
11
    task_state_t state;     /* 任务状态 */
12
    int priority;           /* 优先级 */
13
    int timeslice;          /* 时间片 */
14

15
    /* kernel stack - 内核栈 */
16
    void *kstack_base;      /* 栈基址 */
17
    void *kstack_top;       /* 栈顶 */
18
    uint32_t kernel_esp;    /* 当前栈指针 */
19

20
    /* saved context - 保存的上下文 */
21
    cpu_context_t ctx;      /* CPU 上下文（寄存器） */
22

23
    /* runqueue node - 运行队列节点 */
24
    struct list_node rq_node;
25

26
    /* bookkeeping - 其他信息 */
27
    int exit_code;          /* 退出码 */
28
    int refcount;           /* 引用计数 */
29
} task_t;

任务状态枚举：

1
typedef enum {
2
    TASK_RUNNING,   /* 运行中 */
3
    TASK_RUNNABLE,  /* 可运行/就绪 */
4
    TASK_BLOCKED,   /* 阻塞中 */
5
    TASK_SLEEPING,  /* 睡眠中 */
6
    TASK_ZOMBIE,    /* 僵尸态 */
7
} task_state_t;

CPU 上下文结构：

1
typedef struct cpu_context {
2
    uint32_t ebx;  /* ebx 寄存器 */
3
    uint32_t esi;  /* esi 寄存器 */
4
    uint32_t edi;  /* edi 寄存器 */
5
    uint32_t ebp;  /* ebp 寄存器 */
6
    uint32_t esp;  /* 栈指针 */
7
    uint32_t eip;  /* 指令指针 */
8
} cpu_context_t;

有了描述任务的数据结构，接下来要解决的是：如何从一个任务切换到另一个。

上下文切换#

当调度器决定切换到另一个任务时，必须先保存当前任务的 CPU 寄存器状态，然后恢复下一个任务的寄存器状态。这个过程称为上下文切换。上下文切换由汇编代码实现，因为需要直接操作 CPU 寄存器。

上下文切换需要保存的寄存器是 callee-saved 寄存器，这些寄存器在函数调用中必须被调用者保存：

ebx、esi、edi、ebp：通用寄存器
esp：栈指针
eip：指令指针

flowchart TD A[开始上下文切换] --> B[保存当前任务的寄存器] B --> C[保存 ebx, esi, edi, ebp] C --> D[计算并保存 esp] D --> E[保存 eip] E --> F[加载下一个任务] F --> G[恢复下一个任务的寄存器] G --> H[恢复 ebx, esi, edi, ebp] H --> I[恢复 esp] I --> J[跳转到 eip] J --> K[开始执行新任务]

上下文切换解决了”怎么切换”的问题，但还没回答”切换到谁”，这是调度器的职责。

调度器#

调度器负责决定哪个任务应该在 CPU 上运行。它维护一个运行队列，包含所有可运行的任务，并从中选择下一个要执行的任务。调度器的核心函数是 schedule()，它执行以下步骤：

将当前任务（如果状态为 RUNNABLE）重新加入运行队列
从运行队列中选择下一个任务
更新当前任务指针
执行上下文切换

flowchart TD A[开始调度] --> B{当前任务是否为 RUNNABLE?} B -->|是| C[将当前任务加入运行队列] B -->|否| D[从运行队列选择下一个任务] C --> D D --> E{是否有可运行任务?} E -->|有| F[更新当前任务指针] E -->|无| G[使用 idle 任务] G --> F F --> H{prev == next?} H -->|是| I[无需切换] H -->|否| J[执行上下文切换] J --> K[恢复任务执行]

调度器需要一个数据结构来管理所有就绪的任务，这就是运行队列。

运行队列#

运行队列是调度器的数据源，它维护所有可运行的任务。调度器从队列中取出任务执行，执行完的任务（或时间片用完的任务）重新加入队列。运行队列使用双向链表实现，每个任务结构中嵌入一个链表节点（rq_node）。这种设计避免了额外的内存分配。

graph LR A[Runqueue Head] --> B[Task 1] B --> C[Task 2] C --> D[Task 3] D --> E[NULL] A -.prev.-> A B -.prev.-> A C -.prev.-> B D -.prev.-> C

代码实现#

文件结构#

1
09.kernel-task/
2
├── boot/
3
│   ├── mbr.S
4
│   └── loader.S
5
├── kernel/
6
│   ├── include/
7
│   │   ├── task.h           # 任务结构定义
8
│   │   ├── scheduler.h      # 调度器接口
9
│   │   └── runqueue.h       # 运行队列
10
│   ├── task/
11
│   │   ├── task.c          # 任务生命周期管理
12
│   │   ├── scheduler.c     # 调度器实现
13
│   │   └── runqueue.c      # 运行队列实现
14
│   └── arch/x86/
15
│       └── context_switch.S # 上下文切换汇编
16
└── Makefile

task_t 结构的设计遵循”最小化”原则，只包含必要字段：

1
typedef struct task {
2
    tid_t tid;              /* 任务 ID */
3
    task_state_t state;     /* 任务状态 */
4
    int priority;           /* 优先级 */
5
    void *kstack_base;      /* 内核栈基址 */
6
    uint32_t kernel_esp;    /* 当前栈指针 */
7
    cpu_context_t ctx;      /* CPU 上下文 */
8
    struct list_node rq_node; /* 运行队列节点 */
9
} task_t;

关键设计决策：

嵌入链表节点：rq_node 直接嵌入在 task_t 中，避免了额外的内存分配
内核栈：每个任务都有自己的内核栈，用于中断处理和系统调用
CPU 上下文：保存任务切换时需要恢复的寄存器状态

线程首次启动时，栈上需要设置一个特殊的结构：

1
typedef struct switch_stack {
2
    uint32_t edi;           /* edi 寄存器 */
3
    uint32_t esi;           /* esi 寄存器 */
4
    uint32_t ebp;           /* ebp 寄存器 */
5
    uint32_t ebx;           /* ebx 寄存器 */
6
    uint32_t edx;           /* edx 寄存器 */
7
    uint32_t ecx;           /* ecx 寄存器 */
8
    uint32_t eax;           /* eax 寄存器 */
9
    uint32_t start_eip;     /* 线程入口地址 */
10
    uint32_t unused_retaddr; /* 占位符 */
11
    void (*function)(void *); /* 线程函数 */
12
    void *arg;              /* 函数参数 */
13
} switch_stack_t;

任务创建流程：

flowchart TD A[task_create_kernel] --> B[分配 task_t 结构] B --> C[分配 TID] C --> D[设置任务名称和优先级] D --> E[分配内核栈] E --> F[初始化 switch_stack] F --> G[设置 ctx.eip = resume_thread] G --> H[将任务加入运行队列] H --> I[返回任务指针]

上下文切换流程：

sequenceDiagram participant Schedule participant ContextSwitch participant TaskA participant TaskB Schedule->>ContextSwitch: context_switch(&prev->ctx, &next->ctx) ContextSwitch->>TaskA: 保存 ebx, esi, edi, ebp ContextSwitch->>TaskA: 计算并保存 esp ContextSwitch->>TaskA: 保存 eip ContextSwitch->>TaskB: 恢复 ebx, esi, edi, ebp ContextSwitch->>TaskB: 恢复 esp ContextSwitch->>TaskB: 跳转到 eip TaskB-->>Schedule: 任务继续执行

context_switch.S 汇编实现#

1
global context_switch
2
context_switch:
3
    ; 保存 callee-saved 寄存器
4
    mov eax, [esp+4]   ; prev
5
    mov [eax + 0], ebx   ; 保存 ebx
6
    mov [eax + 4], esi   ; 保存 esi
7
    mov [eax + 8], edi   ; 保存 edi
8
    mov [eax + 12], ebp  ; 保存 ebp
9

10
    ; 保存 esp
11
    mov ecx, esp
12
    add ecx, 12          ; 跳过返回地址 + prev + next
13
    mov [eax + 16], ecx  ; 保存 esp
14

15
    ; 保存 eip
16
    mov ecx, [esp]       ; 获取返回地址
17
    mov [eax + 20], ecx  ; 保存 eip
18

19
    ; 切换到 next 任务
20
    mov edx, [esp+8]     ; next
21

22
    ; 恢复 next 任务的寄存器
23
    mov ebx, [edx + 0]   ; 恢复 ebx
24
    mov esi, [edx + 4]   ; 恢复 esi
25
    mov edi, [edx + 8]   ; 恢复 edi
26
    mov ebp, [edx + 12]  ; 恢复 ebp
27

28
    ; 恢复 esp
29
    mov esp, [edx + 16]  ; 恢复 esp
30

31
    ; 跳转到 next 任务的 eip
32
    mov eax, [edx + 20]  ; 获取 next->ctx.eip
33
    jmp eax              ; 跳转执行

这段汇编做了五件事：

寄存器保存：按照 cpu_context_t 结构的偏移量保存 ebx、esi、edi、ebp
esp 计算：跳过栈上的返回地址（4 字节）和两个参数（各 4 字节），得到调用 context_switch 之前的 esp
eip 保存：保存函数调用的返回地址，这是任务恢复后继续执行的地址
寄存器恢复：从 next 结构中恢复所有寄存器
跳转执行：使用 jmp 跳转到 next->ctx.eip，而不是 ret

task_create 创建任务#

1
task_t *task_create_kernel(const char *name, void (*fn)(void *), void *arg, int prio)
2
{
3
    task_t *task;
4

5
    /* 分配 task_t 结构 */
6
    task = (task_t *)kmalloc(sizeof(task_t));
7
    if (task == NULL) {
8
        vga_printf("task_create_kernel: kmalloc failed\n");
9
        return NULL;
10
    }
11
    memset(task, 0, sizeof(task_t));
12

13
    /* 分配 TID */
14
    if (!id_pool_allocate_id(&tid_pool, (uint32_t *)&task->tid)) {
15
        kfree(task);
16
        return NULL;
17
    }
18

19
    /* 分配内核栈 */
20
    stack_addr = (uint32_t)kmalloc_aligned(KERNEL_STACK_SIZE);
21
    task->kstack_base = (void *)stack_addr;
22
    task->kstack_top = (void *)(stack_addr + KERNEL_STACK_SIZE);
23

24
    /* 初始化 switch_stack */
25
    uint32_t stack_top = stack_addr + KERNEL_STACK_SIZE;
26
    uint32_t kernel_esp = stack_top - (sizeof(interrupt_frame_t) + sizeof(switch_stack_t));
27
    switch_stack_t *switch_stack = (switch_stack_t *)kernel_esp;
28

29
    /* 设置线程入口点 */
30
    switch_stack->start_eip = (uint32_t)kernel_thread;
31
    switch_stack->function = (void (*)(void *))fn;
32
    switch_stack->arg = arg;
33

34
    /* 保存到 task_t */
35
    task->kernel_esp = kernel_esp;
36
    task->ctx.esp = kernel_esp;
37
    task->ctx.eip = (uint32_t)resume_thread;
38

39
    /* 加入运行队列 */
40
    runqueue_add(rq, task);
41

42
    return task;
43
}

task_create_kernel 的核心步骤：使用 kmalloc 分配 task_t 结构和内核栈；在内核栈顶部预留 interrupt_frame_t 和 switch_stack_t 空间；ctx.eip 设置为 resume_thread，这是线程首次启动的入口；新任务初始状态为 TASK_RUNNABLE，加入运行队列等待调度。

schedule 调度器#

1
void schedule(void)
2
{
3
    task_t *prev = current_running_task;
4
    task_t *next = NULL;
5
    runqueue_t *rq = get_global_runqueue();
6

7
    /* 将当前任务重新加入队列 */
8
    if (prev != NULL && prev->state == TASK_RUNNABLE) {
9
        runqueue_add(rq, prev);
10
    }
11

12
    /* 选择下一个任务 */
13
    next = runqueue_pop(rq);
14

15
    /* 更新当前任务 */
16
    current_running_task = next;
17
    next->state = TASK_RUNNING;
18

19
    /* 执行上下文切换 */
20
    if (prev != next) {
21
        context_switch(&prev->ctx, &next->ctx);
22
    }
23
}

schedule 的逻辑很直接：当前任务如果是 RUNNABLE 状态，重新加入运行队列（时间片轮转）；runqueue_pop 从队列头部取出下一个任务（FIFO）；新任务状态设置为 RUNNING；最后调用 context_switch 完成实际的切换。

resume_thread 启动线程#

1
global resume_thread
2
resume_thread:
3
    ; pop 所有寄存器
4
    pop edi
5
    pop esi
6
    pop ebp
7
    pop ebx
8
    pop edx
9
    pop ecx
10
    pop eax
11

12
    ; 开中断
13
    sti
14

15
    ; ret 指令会 pop start_eip 并跳转到 kernel_thread
16
    ret

resume_thread 只在新线程首次被调度时执行。它从栈上 pop 所有通用寄存器（eax、ecx、edx、ebx、ebp、esi、edi），然后 sti 开启中断，允许定时器中断触发调度。ret 指令从栈上弹出 start_eip（kernel_thread 的地址）并跳转，开始执行用户提供的线程函数。

运行与验证#

编译运行#

1
cd 09.kernel-task
2
make clean
3
make all
4
make run

预期输出#

1
Hello, kernel world!
2
Initializing task subsystem...
3
Creating test threads...
4
Threads created: test1 (tid=1), test2 (tid=2)
5
Starting scheduler...
6
Thread 1: started
7
Thread 1: count = 0
8
Thread 1: before yield
9
Thread 2: started
10
Thread 2: count = 0
11
Thread 2: before yield
12
Thread 1: after yield
13
Thread 1: count = 1
14
...
15
Thread 1: exiting
16
Thread 2: exiting

测试代码分析#

在 kernel.c 中，我们创建了两个测试线程：

1
void test_thread1(void *arg) {
2
    int i;
3
    for (i = 0; i < 3; i++) {
4
        vga_printf("Thread 1: count = %d\n", i);
5
        schedule_yield();
6
    }
7
    vga_printf("Thread 1: exiting\n");
8
    task_exit(0);
9
}
10

11
void kernel_main(void) {
12
    task_subsystem_init();
13

14
    /* 创建测试线程 */
15
    task_create_kernel("test1", test_thread1, NULL, 10);
16
    task_create_kernel("test2", test_thread2, NULL, 10);
17

18
    /* 启动调度器 */
19
    schedule();
20
}

踩坑记录#

问题：为什么线程首次运行时需要 resume_thread？

原因：新创建的线程没有之前的上下文，无法直接使用 context_switch。resume_thread 从栈上预置的 switch_stack_t 恢复寄存器，然后跳转到 kernel_thread 执行用户提供的线程函数。
问题：为什么要保存 esp 而不是直接保存栈指针？

原因：context_switch 被调用时，栈指针已经改变。需要保存的是调用 context_switch 之前的栈指针，这样任务恢复时才能回到正确的栈帧。
问题：为什么使用 jmp 而不是 ret 来跳转到新任务？

原因：ret 指令需要栈上有返回地址，但新任务的栈上可能没有正确的返回地址。jmp 直接跳转到 eip，更加灵活和安全。

小结#

本章实现了多任务系统的基础组件：task_t 结构定义了任务的元数据和运行时状态，上下文切换通过汇编代码保存和恢复 CPU 寄存器，调度器使用简单的 FIFO 算法从运行队列选择任务，运行队列用双向链表维护可运行的任务。这些组件让内核能够创建和管理多个并发执行的线程，但当前的调度策略还很粗糙，没有时间片的概念，也没有抢占机制。下一章将引入时间片轮转（Round-Robin）调度算法和时钟中断驱动的抢占式调度，让任务切换变得公平和自动。