进程调度
Table of Contents
目前为止, PRi OS已经是一个相当复杂的裸机程序, 但是说实话, 仍然不能将其称为操作系统
原因是它无法完成任何OS应该执行的任何核心任务。这种核心任务之一称为进程调度。通过调度器, 操作系统应该能够在不同进程之间共享CPU时间
其中最困难的部分是, 一个进程应该不知道调度的发生：它应该将自己视为唯一占用CPU的进程 接下来，将此功能添加到RPi OS
task_struct
如果要管理流程, 应该做的第一件事就是创建一个描述流程的结构。Linux具有这样的结构, 它称为 task_struct (在Linux中, 线程和进程只是不同类型的任务)
由于主要模仿Linux的实现, 因此将做同样的事情
RPi OS task_struct 如下所示：
struct cpu_context { unsigned long x19; unsigned long x20; unsigned long x21; unsigned long x22; unsigned long x23; unsigned long x24; unsigned long x25; unsigned long x26; unsigned long x27; unsigned long x28; unsigned long fp; unsigned long sp; unsigned long pc; }; struct task_struct { struct cpu_context cpu_context; long state; long counter; long priority; long preempt_count; };
该结构具有以下成员：
cpu_context : 一个嵌入式结构, 其中包含正在切换的任务之间 可能不同的 所有 寄存器 的值
有一个合理的问题是为什么不保存所有寄存器, 而只保存寄存器 x19-x30 和 sp ？(fp 是 x29 并且 pc 是 x30) 实际的上下文切换仅在任务中调用cpu_switch_to函数。因此, 从正在切换的任务的角度来看, 它仅调用cpu_switch_to函数, 并在一段时间(可能很长)后返回，该任务不会注意到在此期间发生了另一个任务 根据ARM的调用约定, 寄存器 x0-x18 可以被调用的函数覆盖, 因此调用者不得假定这些寄存器的值在函数调用后仍然存在 这就是为什么保存x0-x18寄存器没有意义的原因
state : 当前正在运行的任务的状态，对于仅在CPU上做一些工作的任务, 状态始终为 TASK_RUNNING
实际上, 这是RPi OS目前要支持的唯一状态。但是, 稍后将不得不添加一些其他状态 例如, 等待中断的任务应移至其他状态, 因为在尚未发生所需的中断时唤醒任务是没有意义的
counter : 该字段用于确定当前任务已运行多长时间
计数器会在每个计时器滴答时减少1, 到0时便会安排另一个任务
priority : 安排新任务时, 将其 优先级 复制到 计数器 中
通过设置任务优先级, 可以调节任务相对于其他任务获得的处理器时间
- preempt_count : 如果该字段的值为 非零值 , 则表明当前任务正在执行一些 不可中断 的关键功能(例如, 它运行调度功能)。如果在此时间发生计时器滴答, 则将忽略它, 并且不会触发重新计划
内核启动后, 只有一个任务正在运行：一个正在运行 kernel_main 函数. 它称为 初始化任务 。在启用调度程序功能之前, 必须填充与初始化任务相对应的 task_struct . 这个被完成在 这里
所有任务都存储在 task 数组. 该阵列只有64个插槽
这是在RPi OS中可以同时执行的最大任务数 对于生产就绪的OS来说, 它绝对不是最佳解决方案, 但对于我们的目标而言, 这是可以的
还有一个非常重要的变量称为 current 总是指向 当前正在执行 的任务。 current 和 task 数组都初始设置为持有指向 init任务 的指针。还有一个全局变量称为 nr_tasks : 它包含系统中当前正在运行的任务数
这些都是将用于实现调度程序功能的结构和全局变量 在对task_struct的描述中, 已经简要提到了调度工作的一些方面, 因为如果不了解如何使用特定的task_struct字段, 就无法理解其含义 现在将更详细地研究调度算法, 从 kernel_main 函数开始
kernel_main 函数
在深入探讨调度程序实现之前, 先快速展示如何证明调度程序确实有效
要了解它, 可以看一下 kernel.c 文件：
void kernel_main(void) { uart_init(); init_printf(0, putc); irq_vector_init(); timer_init(); enable_interrupt_controller(); enable_irq(); int res = copy_process((unsigned long)&process, (unsigned long)"12345"); if (res != 0) { printf("error while starting process 1"); return; } res = copy_process((unsigned long)&process, (unsigned long)"abcde"); if (res != 0) { printf("error while starting process 2"); return; } while (1){ schedule(); } }
关于此代码, 有一些重要的事情：
- 新函数 copy_process 需要2个参数:
- 在新进程中执行的函数
- 需要传递给该函数的参数
- 分配一个新的 task_struct 并使其可用于调度程序
- 另一个新函数称为 schedule 这是核心调度程序功能：它 检查 是否有 新任务 需要 抢占 当前任务
- 如果一个任务目前没有任何工作, 可以自动调用 schedule 函数
- 计时器中断处理程序也会调用 schedule 函数
这里两次调用copy_process, 每次传递的第一个参数都是指向 process 函数，这个 process 函数功能非常简单：
void process(char *array) { while (1){ for (int i = 0; i < 5; i++){ uart_send(array[i]); delay(100000); } } }
它只是一直在屏幕上打印数组中的字符, 这个字节数组也是做为参数传递给process 第一次使用参数 12345 调用它, 第二次使用 abcde 参数 如果调度程序实现正确, 应该在屏幕上看到两个线程的混合输出
内存分配
系统中的每个任务都应具有其 专用的 堆栈
这就是为什么在创建新任务时必须有一种分配内存的方法
目前, 内存分配器还非常原始：
static unsigned short mem_map [ PAGING_PAGES ] = {0,}; unsigned long get_free_page() { for (int i = 0; i < PAGING_PAGES; i++){ if (mem_map[i] == 0){ mem_map[i] = 1; return LOW_MEMORY + i*PAGE_SIZE; } } return 0; } void free_page(unsigned long p){ mem_map[p / PAGE_SIZE] = 0; }
分配器只能与内存页面一起使用(每个页面的大小为 4 KB )。创建一个名为 mem_map 的全局数组, 该数组对于系统中的 每个页面 都 保持 其 状态 ： 分配 还是 空闲 。每当需要分配一个新页面时, 就循环遍历此数组并返回第一个空闲页面。此实现基于两个假设：
- 系统中的内存总量，它是 1 GB - 1 MB (存储器的最后 1兆字节为 设备寄存器 保留)，此值存储在 HIGH_MEMORY 常量中
- 前 4 MB 的内存 保留 给 内核映像 和 init任务堆栈 ，此值存储在 LOW_MEMORY 常量. 所有内存分配都在此之后开始
创建一个新任务
新任务（进程）分配在 copy_process 函数实现：
int copy_process(unsigned long fn, unsigned long arg) { preempt_disable(); struct task_struct *p; p = (struct task_struct *) get_free_page(); if (!p) return 1; p->priority = current->priority; p->state = TASK_RUNNING; p->counter = p->priority; p->preempt_count = 1; //disable preemtion until schedule_tail p->cpu_context.x19 = fn; p->cpu_context.x20 = arg; p->cpu_context.pc = (unsigned long)ret_from_fork; p->cpu_context.sp = (unsigned long)p + THREAD_SIZE; int pid = nr_tasks++; task[pid] = p; preempt_enable(); return 0; }
现在, 来详细研究它：
preempt_disable(); struct task_struct *p;
该函数从禁用抢占和为新任务分配指针开始。抢占被禁用, 是因为不想在 copy_process 函数中间将其重新安排到其他任务
p = (struct task_struct *) get_free_page(); if (!p) return 1;
接下来, 分配一个新页面。在此页面的底部, 为新创建的任务放置 task_struct ，该页面的其余部分将用作 任务堆栈
p->priority = current->priority; p->state = TASK_RUNNING; p->counter = p->priority; p->preempt_count = 1; //disable preemtion until schedule_tail
分配好task_struct之后, 可以初始化其属性：
- 优先级和初始计数器是根据当前任务优先级设置
- 状态设置为 TASK_RUNNING , 表示新任务已准备好开始
- preempt_count设置为 1 , 这意味着在执行任务之后, 在完成一些初始化工作之前, 不应重新计划其时间
p->cpu_context.x19 = fn; p->cpu_context.x20 = arg; p->cpu_context.pc = (unsigned long)ret_from_fork; p->cpu_context.sp = (unsigned long)p + THREAD_SIZE;
这里 cpu_context 被初始化：
- 堆栈指针 sp 设置在新分配的内存页面的顶部
pc 被设置为 ret_from_fork 函数, 现在需要看一下这个函数, 以便理解为什么其余cpu_context寄存器以它们的方式初始化
.globl ret_from_fork ret_from_fork: bl schedule_tail mov x0, x20 blr x19 //should never return
ret_from_fork:
- 首先调用 schedule_tail , 只是 启用 了 抢占
- 使用存储在 x20 中的 参数 调用存储在 x19 寄存器中的 函数
- 在调用ret_from_fork函数之前, 需要从 cpu_context 中 恢复 出 x19 和 x20
现在, 回到copy_process.
int pid = nr_tasks++; task[pid] = p; preempt_enable(); return 0;
最后, copy_process 将新创建的任务添加到 task 数组 中, 并为当前任务 启用 抢占
关于copy_process函数要了解的重要一点是, 它在完成执行后不会发生上下文切换 该函数仅准备新的task_struct并将其添加到task数组中，而在调用schedule函数后才可能执行此任务
谁调用 schedule?
在深入了解schedule 函数之前, 首先要弄清楚schedule的调用方式。有2种情况：
当一个任务现在没有任何事情要做, 但是仍然无法终止时, 它可以自行调用schedule
就像 kernel_main 函数所做的
- schedule 也定期被 时钟中断 所调用
现在来看看 timer_tick 函数, 从计时器中断中调用：
void timer_tick() { --current->counter; if (current->counter>0 || current->preempt_count >0) { return; } current->counter=0; enable_irq(); _schedule(); disable_irq();
首先, 它减少了当前任务的计数器
- 如果计数器大于0, 或者当前禁用了抢占功能, 则返回该函数
否则调用schedule并启用中断
在中断处理程序内部, 默认情况下禁用中断 接下来会去了解为什么在调度程序执行期间必须启用中断
调度算法
最后, 看一下调度程序算法：
void _schedule(void) { preempt_disable(); int next,c; struct task_struct * p; while (1) { c = -1; next = 0; for (int i = 0; i < NR_TASKS; i++){ p = task[i]; if (p && p->state == TASK_RUNNING && p->counter > c) { c = p->counter; next = i; } } if (c) { break; } for (int i = 0; i < NR_TASKS; i++) { p = task[i]; if (p) { p->counter = (p->counter >> 1) + p->priority; } } } switch_to(task[next]); preempt_enable(); }
该算法的工作原理如下：
- 第一个内部的for循环遍历所有任务, 并尝试以最大计数器找到处于TASK_RUNNING状态的任务：
- 如果找到了这样的任务, 并且其计数器大于0, 立即从外部的 while 循环中中断, 并切换到该任务
如果找不到这样的任务, 则意味着当前不存在处于 TASK_RUNNING 状态的任务, 或者所有此类任务的计数器均为0
在实际的OS中, 例如, 当所有任务都在等待中断时, 就可能会发生
- 在这种情况下, 将执行第二个嵌套的 for 循环. 对于每个任务(无论处于什么状态), 此循环都会增加其计数器。计数器增加以非常聪明的方式完成：
- 任务通过的第二个for 循环的迭代次数越多, 其计数器的计数就越高
- 任务计数器永远不能超过 2 *优先级
- 在这种情况下, 将执行第二个嵌套的 for 循环. 对于每个任务(无论处于什么状态), 此循环都会增加其计数器。计数器增加以非常聪明的方式完成：
- 然后重复该过程：
- 如果至少有一个任务处于TASK_RUNNIG状态, 则外部while循环的第二次迭代将是最后一个, 因为在第一次迭代之后, 所有计数器都已经非零
但是, 如果没有 TASK_RUNNING 任务, 则该过程会反复进行, 直到某些任务变为 TASK_RUNNING 状态
但是, 如果在单个CPU上运行, 那么在此循环运行时如何更改任务状态？ 答案是, 如果某些任务正在等待中断, 则该中断可能在执行 schedule 函数时发生, 并且中断处理程序可以更改任务的状态 这实际上解释了为什么在 schedule 函数执行期间必须启用中断
这也说明了禁用中断和禁用抢占之间的重要区别：
- schedule 会在整个运行期间禁用抢占：这样可以确保在执行原始函数的过程中不会调用嵌套的 schedule
- 相反在 schedule 函数执行期间, 中断是可以合法发生的
切换任务
找到具有非零计数器的 TASK_RUNNING 状态的任务后, switch_to 函数被调用：
void switch_to(struct task_struct * next) { if (current == next) return; struct task_struct * prev = current; current = next; cpu_switch_to(prev, next); }
在这里, 检查下一个进程是否与当前进程不同, 如果不一致, 则更新 current 变量。实际工作被重定向到 cpu_switch_to 函数:
.globl cpu_switch_to cpu_switch_to: mov x10, #THREAD_CPU_CONTEXT add x8, x0, x10 mov x9, sp stp x19, x20, [x8], #16 // store callee-saved registers stp x21, x22, [x8], #16 stp x23, x24, [x8], #16 stp x25, x26, [x8], #16 stp x27, x28, [x8], #16 stp x29, x9, [x8], #16 str x30, [x8] add x8, x1, x10 ldp x19, x20, [x8], #16 // restore callee-saved registers ldp x21, x22, [x8], #16 ldp x23, x24, [x8], #16 ldp x25, x26, [x8], #16 ldp x27, x28, [x8], #16 ldp x29, x9, [x8], #16 ldr x30, [x8] mov sp, x9 ret
这是实际上下文切换发生的地方。让我们逐行查看它：
mov x10, #THREAD_CPU_CONTEXT add x8, x0, x10
- THREAD_CPU_CONTEXT 常量包含task_struct中的 cpu_context结构 的 偏移量
- x0 包含一个指向 第一个参数 的 指针 , 该指针是 当前的task_struct
在这里, 当前是指要从中切换的那个 task struct 复制的两行执行后, x8将包含指向 prev->cpu_context的指针
mov x9, sp stp x19, x20, [x8], #16 // store callee-saved registers stp x21, x22, [x8], #16 stp x23, x24, [x8], #16 stp x25, x26, [x8], #16 stp x27, x28, [x8], #16 stp x29, x9, [x8], #16 str x30, [x8]
接下来, prev->cpu_context结构中定义的寄存器都按照顺序存储（这些是prev进程的callee所存放在这里的：
- x30是链接寄存器, 包含函数返回地址, 存储为pc
- 当前堆栈指针存储为sp, x29存储为fp(帧指针)
add x8, x1, x10
因为 x1是指向下一个task_struct的指针, 因此x8将包含指向下一个cpu_context的指针 (next->cpu_context)
ldp x19, x20, [x8], #16 // restore callee-saved registers ldp x21, x22, [x8], #16 ldp x23, x24, [x8], #16 ldp x25, x26, [x8], #16 ldp x27, x28, [x8], #16 ldp x29, x9, [x8], #16 ldr x30, [x8] mov sp, x9
被调用者保存的寄存器从 next->cpu_context里恢复
ret
函数返回到 链接寄存器 x30 所指向的位置：
- 如果是第一次切换到某个任务（进程）, 则将 ret_from_fork 函数
- 其他情况下, 该位置将是先前由 cpu_switch_to 函数保存在 cpu_context 中的位置
调度与中断
在上一章中, 定义了 kernel_entry 和 kernel_exit 宏用于保存和恢复处理器状态 在引入调度程序后, 出现了一个新问题：现在完全可以合法地从一个任务进入中断, 离开中断的时候返回另外一个任务
然而用来从中断返回的 eret 指令依赖于： 返回地址 应存储在 elr_el1 中, 处理器状态 应存储在 spsr_el1 寄存器中。因此, 如果要在处理中断时切换任务, 则必须将这两个寄存器与所有其他通用寄存器一起保存和恢复。这样做的代码非常简单，保存这两个寄存器：
.macro kernel_entry sub sp, sp, #S_FRAME_SIZE ...... mrs x22, elr_el1 mrs x23, spsr_el1
恢复这两个寄存器：
.macro kernel_exit ldr x23, [sp, #16 * 16] ldp x30, x22, [sp, #16 * 15] msr elr_el1, x22 msr spsr_el1, x23 ......
在上下文切换期间跟踪系统状态
现在已经检查了与上下文切换有关的所有源代码，但是, 该代码包含许多异步交互, 这使得很难完全了解整个系统的状态如何随时间变化 接下来想描述从系统启动到第二次上下文切换之时发生的事件的顺序 对于每个此类事件, 将包括一个表示事件发生时存储器状态的图表 希望这种表示形式将帮助深入了解调度程序的工作方式
内核已初始化并 kernel_main 函数已被执行，初始堆栈配置为开始于 LOW_MEMORY , 这是4 MB
0 +------------------+ | kernel image | |------------------| | | |------------------| | init task stack | 0x00400000(4MB) +------------------+ | | | | 0x3F000000 +------------------+ | device registers | 0x40000000 +------------------+kernel_main 首次调用 copy_process ，分配了新的 4 KB内存页面 , 并在该页面的底部放置了 task_struct . (稍后, 将在此时创建的任务称为任务1)
0 +------------------+ | kernel image | |------------------| | | |------------------| | init task stack | 0x00400000 +------------------+ | task_struct 1 | |------------------| | | 0x00401000 +------------------+ | | | | 0x3F000000 +------------------+ | device registers | 0x40000000 +------------------+kernel_main第二次调用copy_process并且重复相同的过程. 任务2 已创建并添加到任务列表
0 +------------------+ | kernel image | |------------------| | | |------------------| | init task stack | 0x00400000 +------------------+ | task_struct 1 | |------------------| | | 0x00401000 +------------------+ | task_struct 2 | |------------------| | | 0x00402000 +------------------+ | | | | 0x3F000000 +------------------+ | device registers | 0x40000000 +------------------+- kernel_main 自动调用 schedule 函数并决定运行任务1
- cpu_switch_to 将 calee-saved的寄存器(内核进程的寄存器值) 保存在位于 内核映像内部的init任务 cpu_context 中
- cpu_switch_to 从 任务1的cpu_context 里恢复到各个寄存器里
- sp 现在指向 0x00401000
- 链接寄存器 x30 值指向 ret_from_fork 函数
- x19 包含一个指向 process 函数
- x20 一个指向字符串 12345 的指针, 该字符串位于内核映像中的某个位置
- cpu_switch_to 调用 ret 指令, 该指令跳转到 ret_from_fork 函数
ret_from_fork 读取 x19 和 x20 寄存器, 并使用参数 12345 调用 process 函数。在process函数开始执行后, 其堆栈开始增长：
0 +------------------+ | kernel image | |------------------| | | |------------------| | init task stack | 0x00400000 +------------------+ | task_struct 1 | |------------------| | | |------------------| | task 1 stack | 0x00401000 +------------------+1 | task_struct 2 | |------------------| | | 0x00402000 +------------------+ | | | | 0x3F000000 +------------------+ | device registers | 0x40000000 +------------------+发生计时器中断： kernel_entry 宏保存 所有通用寄存器 + elr_el1 和 spsr_el1 到 任务1堆栈的底部
0 +------------------------+ | kernel image | |------------------------| | | |------------------------| | init task stack | 0x00400000 +------------------------+ | task_struct 1 | |------------------------| | | |------------------------| | task 1 saved registers | |------------------------| | task 1 stack | 0x00401000 +------------------------+ | task_struct 2 | |------------------------| | | 0x00402000 +------------------------+ | | | | 0x3F000000 +------------------------+ | device registers | 0x40000000 +------------------------+schedule 被调用 并且它 决定 运行 任务2 。但是现在仍然运行任务1, 并且其堆栈 继续增长 到 任务1保存的寄存器区域 以下。在图中, 堆栈的这一部分标记为 int , 表示 中断堆栈
0 +------------------------+ | kernel image | |------------------------| | | |------------------------| | init task stack | 0x00400000 +------------------------+ | task_struct 1 | |------------------------| | | |------------------------| | task 1 stack (int) | |------------------------| | task 1 saved registers | |------------------------| | task 1 stack | 0x00401000 +------------------------+ | task_struct 2 | |------------------------| | | 0x00402000 +------------------------+ | | | | 0x3F000000 +------------------------+ | device registers | 0x40000000 +------------------------+cpu_switch_to 运行任务2. 为此, 它执行与任务1完全相同的步骤序列。任务2开始执行, 并且堆栈不断增长
0 +------------------------+ | kernel image | |------------------------| | | |------------------------| | init task stack | 0x00400000 +------------------------+ | task_struct 1 | |------------------------| | | |------------------------| | task 1 stack (int) | |------------------------| | task 1 saved registers | |------------------------| | task 1 stack | 0x00401000 +------------------------+ | task_struct 2 | |------------------------| | | |------------------------| | task 2 stack | 0x00402000 +------------------------+ | | | | 0x3F000000 +------------------------+ | device registers | 0x40000000 +------------------------+请注意, 此时并未从中断返回, 但这没关系, 因为现在已启用中断 (在 timer_tick 之前 schedule 被调用)
另一个定时器中断发生, kernel_entry将所有 通用寄存器+elr_el1和spsr_el1 保存在 任务2堆栈的底部 。任务2中断堆栈开始增长：
0 +------------------------+ | kernel image | |------------------------| | | |------------------------| | init task stack | 0x00400000 +------------------------+ | task_struct 1 | |------------------------| | | |------------------------| | task 1 stack (int) | |------------------------| | task 1 saved registers | |------------------------| | task 1 stack | 0x00401000 +------------------------+ | task_struct 2 | |------------------------| | | |------------------------| | task 2 stack (int) | |------------------------| | task 2 saved registers | |------------------------| | task 2 stack | 0x00402000 +------------------------+ | | | | 0x3F000000 +------------------------+ | device registers | 0x40000000 +------------------------+- schedule 被调用：它观察到所有任务的计数器都设置为0, 并将 计数器 设置 为 任务优先级
schedule 选择要运行的是 init任务，这是因为现在所有任务的计数器都设置为1, 而init任务是列表中的第一个
但是实际上, 此时 schedule 选择任务1或任务2是完全合法的, 因为它们的计数器值相等 我们对选择任务1的情况更感兴趣, 所以现在让我们假设选择了任务1
- cpu_switch_to 被调用 并从 任务1的cpu_context 中 恢复 callee-saved寄存器
链接寄存器现在注册到 switch_to 函数的最后
因为这是上次执行任务1时调用 cpu_switch_to的位置
- sp 指向任务1中断堆栈的底部
timer_tick 函数恢复执行, 从 disable_irq 这行开始，这禁用中断 并且最终 kernel_exit 被执行
0 +------------------------+ | kernel image | |------------------------| | | |------------------------| | init task stack | 0x00400000 +------------------------+ | task_struct 1 | |------------------------| | | |------------------------| | task 1 saved registers | |------------------------| | task 1 stack | 0x00401000 +------------------------+ | task_struct 2 | |------------------------| | | |------------------------| | task 2 stack (int) | |------------------------| | task 2 saved registers | |------------------------| | task 2 stack | 0x00402000 +------------------------+ | | | | 0x3F000000 +------------------------+ | device registers | 0x40000000 +------------------------+当开始 kernel_exit 时, 任务1的中断堆栈已折叠为0，因为这是中断程序需要使用的堆栈
kernel_exit 恢复所有通用寄存器以及elr_el1 和 spsr_el1
- elr_el1 现在指向 process 函数中间的某个位置
- sp 指向任务1堆栈的底部
0 +------------------------+ | kernel image | |------------------------| | | |------------------------| | init task stack | 0x00400000 +------------------------+ | task_struct 1 | |------------------------| | | |------------------------| | task 1 stack | 0x00401000 +------------------------+ | task_struct 2 | |------------------------| | | |------------------------| | task 2 stack (int) | |------------------------| | task 2 saved registers | |------------------------| | task 2 stack | 0x00402000 +------------------------+ | | | | 0x3F000000 +------------------------+ | device registers | 0x40000000 +------------------------+- kernel_exit 执行 eret 使用的指令 elr_el1 注册以 跳转 回 process 函数，任务1恢复其正常执行
上述步骤顺序非常重要，这是整个教程中最重要的事情之一
总结
现在已经完成了调度, 但是现在的内核只能管理内核线程：它们在EL1上执行, 并且可以直接访问任何内核函数或数据 接下来, 将解决此问题, 并介绍系统调用和虚拟内存
| Next: 系统调用 | Previous: 中断处理 | Home: 用树莓派学习操作系统开发 |