做网站 前端,网站开发 保证书,wordpress图片自动居中,单页网站 html5 动态Github代码仓库链接 上一节我们已经实现了线程的基本结构并且能够切换到新的线程#xff0c;但是这个切换过程是我们手动指定的。这一节我们来实现内核线程调度#xff0c;使得我们只需要创建线程#xff0c;处理器就会按照某个调度算法自动调入调出线程#xff0c;实现并发…Github代码仓库链接 上一节我们已经实现了线程的基本结构并且能够切换到新的线程但是这个切换过程是我们手动指定的。这一节我们来实现内核线程调度使得我们只需要创建线程处理器就会按照某个调度算法自动调入调出线程实现并发。 6.1 线程管理
1、线程辅助状态我们目前的线程 Thread 结构体只存储了线程上下文相关的信息我们需要更多的信息来用于线程的调度。首先就是线程的状态这里划分四个状态
Ready线程就绪Running线程正在占有 CPU 执行Sleeping线程等待资源而休眠Exited线程退出。其实 Exited 状态可有可无因为一个线程调用 Exit() 退出时就会被直接回收资源而不会继续存储在线程池中。
// kernel/thread.h/* 线程状态 */
typedef enum {Ready, // 就绪Running, // 运行Sleeping, // 休眠Exited // 退出
} Status;接着我们就可以定义存储在线程池中的线程信息了。其实定义的是线程池中的一个线程信息空位。
// kernel/thread.h/* 线程池中的线程信息槽 */
typedef struct {Status status; // 线程状态int tid; // 线程IDint occupied; // 该槽位是否被占用Thread thread; // 线程
} ThreadInfo;我们同时定义一个结构 RunningThread用来表示一个正在运行的线程其实就是将 tid 和 Thread 封装一下。
// kernel/thread.h// 正在运行的线程
typedef struct {int tid;Thread thread;
} RunningThread;2、线程池
我们定义一个结构体用于存储调度算法的一些函数。这相当于一个算法框架要实现一个调度算法只需要实现其中的函数即可。
// krenel/thread.h// 调度器算法实现函数指针
typedef struct {void (* init)(void); // 初始化调度器void (* push)(int); // 将一个线程加入线程调度int (* pop) (void); // 从就绪线程中选择一个运行如果没有可运行的线程则返回 -1int (* tick)(void); // 提醒调度算法当前线程又运行了一个 tick返回的 int 表示调度算法认为当前线程是否需要被切换出去void (* exit)(int); // 告诉调度算法某个线程已经结束
} Scheduler;接着就可以定义线程池了
// kernel/consts.h// 线程池最大线程数
#define MAX_THREAD 0x40// kernel/thread.h// 线程池
typedef struct {ThreadInfo threads[MAX_THREAD];Scheduler scheduler;
} ThreadPool;3、线程池相关函数
allocTid() 函数用于遍历线程池寻找一个未被使用的 tid。若所有 tid 都被使用则会进入 panic。addToPool() 函数用于将一个线程添加到线程池中线程池会为其分配一个 tid并分配一个空位保存这个线程相关的信息并通知调度算法让这个线程参与调度调度算法只会操作 tid。acquireFromPool() 函数用于向线程池获取一个可以运行的线程由于调用该函数的下一步就要直接切换到这个线程所以在线程池中直接标记为 Running 状态。如果线程池中没有可以运行的线程那么返回的 RunningThread 中的 tid 为 -1。retrieveToPool() 函数会在一个线程停止运行切换回调度线程后调用用于修改线程池内的线程信息。线程停止运行有两种情况一种是线程运行结束另一种是还没有运行完但是时间片用尽这种情况就需要重新将线程加入调度器。tickPool() 函数基本就是对调度器的 tick() 函数的包装用于查看当前正在运行的线程是否需要切换。exitFromPool() 函数的参数是 tid用于释放该 tid 线程信息的空位并且通知调度器让这个 tid 不再参与调度。
// kernel/thread.c// 遍历线程池寻找未被使用的tid
int
allocTid(ThreadPool *pool)
{int i;for(i 0; i MAX_THREAD; i) {if(!pool-threads[i].occupied)return i;}panic(Alloc tid failed!\n);return -1;
}// 将线程添加到线程池中
void
addToPool(ThreadPool *pool, Thread thread)
{int tid allocTid(pool); // 遍历线程池寻找未使用tid// 配置线程信息pool-threads[tid].status Ready; // 就绪pool-threads[tid].occupied 1; // 占用pool-threads[tid].thread thread; // 线程上下文地址和栈底地址pool-scheduler.push(tid); // 将线程加入参与调度
}// 向线程池获取一个可以运行的线程若没有返回-1
RunningThread
acquireFromPool(ThreadPool *pool)
{int tid pool-scheduler.pop(); // 从就绪线程中获取一个可运行线程RunningThread rt;rt.tid tid;if(tid ! -1) {ThreadInfo *ti pool-threads[tid]; // 从线程池取出线程// 修改取出线程在线程池的状态上行代码用引用传入的ti-status Running; // 由于调用该函数的下一步就要直接切换到这个线程所以在线程池中直接标记为 Running 状态ti-tid tid; // 线程ID因为将线程添加到线程池中时没用设置ThreadInfo.tid所以这里初始化rt.thread ti-thread;}return rt;
}// 修改线程池内的线程信息在一个线程停止运行切换回调度线程后调用
// 线程停止运行有两种情况
// 一种是线程运行结束
// 一种是还没有运行完但是时间片用尽这种情况就需要重新将线程加入调度器
void
retrieveToPool(ThreadPool *pool, RunningThread rt)
{int tid rt.tid;// 若线程不被占用了即线程运行结束if(!pool-threads[tid].occupied) { // 表明刚刚这个线程退出了回收栈空间传入栈底地址根据HEAP维护的二叉树即可知道回收多大空间kfree((void *)pool-threads[tid].thread.kstack);return;}// 线程时间片用完重新加入调度器ThreadInfo *ti pool-threads[tid];ti-thread rt.thread; // 更新线程上下文、栈地址if(ti-status Running) {ti-status Ready; // 更新线程状态pool-scheduler.push(tid); // 加入线程调度}
}// 对调度器的 tick() 函数包装用于查看当前正在运行的线程是否需要切换
int
tickPool(ThreadPool *pool)
{// 提醒调度算法当前线程又运行了一个 tick返回的 int 表示调度算法认为当前线程是否需要被切换出去return pool-scheduler.tick();
}// 释放该 tid 线程信息的占用位并且通知调度器让这个 tid 不再参与调度
void
exitFromPool(ThreadPool *pool, int tid)
{pool-threads[tid].occupied 0; // 清除占用标志pool-scheduler.exit(tid); // 告诉调度算法某个线程已经结束
}6.2 调度线程
1、我们所有的运行流程都是运行在线程中的如果我们要对所有的线程进行调度我们还需要另外创建一个线程专门用于调度。调度线程的作用是
当没有线程在运行时调度线程根据一定的策略来选择一个线程来执行当一个线程被调度器判断需要让出 CPU 控制权时例如运行时间过长或者运行结束并不是直接切换到另一个线程而是先切换到这个调度线程让调度线程根据一定的策略来选择另一个线程执行。
我们定义一个结构用来保存调度线程参与调度所需要的所有信息
// kernel/thread.h// 调度线程参与调度所需要的所有信息
typedef struct {ThreadPool pool; // 线程池Thread idle; // 调度线程RunningThread current; // 当前运行线程信息int occupied; // 当前是否有线程除了调度线程正在运行
} Processor;我们需要定义一个全局唯一的 Processor来进行调度。
// kernel/processor.c// 全局唯一的 Processor 实例
static Processor CPU;2、我们需要在进入 idle 线程时关闭调度防止调度过程被时钟打断并在某个适当的时机恢复。涉及的就是关闭全局中断通过设置sstatus寄存器实现操作。
// kernel/riscv.h/* 打开异步中断并等待中断 */
static inline void
enable_and_wfi()
{ // csrsi - 控制状态寄存器某个位 11 - 置位第二位SIE// wfi - Wait for Interrupt特殊指令用于暂停 CPU 直到某个中断发生CPU进入低功耗状态asm volatile(csrsi sstatus, 1 1; wfi);
}/* 关闭异步中断并保存原先的 sstatus */
static inline usize
disable_and_store()
{usize x; // 保存操作后的 sstatus 返回// csrrci - CSR read and clear with Immediate清除SIE位并存储到%0即xasm volatile(csrrci %0, sstatus, 1 1 : r (x) );return x;
}/* 用 flags 的值恢复 sstatus */
static inline void
restore_sstatus(usize flags)
{// cars - CSR set with Immediate用输入变量flags的值设置sstatus寄存器asm volatile(csrs sstatus, %0 :: r(flags) );
}3、线程调度操作相关的函数
initCPU() 函数使用 idle 线程和 pool 线程池来对 CPU 进行初始化参数 pool 主要就是为了指定这个 Processor 所使用的调度算法。addToCPU() 函数主要就是对 addToPool() 函数的包装不用做其他处理。exitFromCPU() 这个函数由线程主动执行效果类似于 exit()用于主动通知 CPU 这个线程运行结束CPU 会通知线程池释放资源并切换到 idle 线程进行下一步调度。runCPU() 函数用于切换到 idle 线程表示正式由 CPU 进行线程管理和调度这个函数通常在启动线程中调用由于启动线程被构造为一个局部变量我们再也无法切换回启动线程相当于操作系统的初始化工作已经结束。
// kernel/processor.c// 对CPU调度线程初始化
// 使用 idle 线程和 pool 线程池来对 CPU 进行初始化
// 参数 pool 主要就是为了指定这个 Processor 所使用的调度算法
void
initCPU(Thread idle, ThreadPool pool)
{CPU.idle idle; // 调度线程CPU.pool pool; // 线程池CPU.occupied 0; // 当前没有线程在运行
}// 将线程添加到CPU管理的线程池中对 addToPool() 进行包装
void
addToCPU(Thread thread)
{addToPool(CPU.pool, thread);
}// 线程主动退出通知 CPU 这个线程运行结束
// CPU 会通知线程池释放资源并切换到 idle 线程进行下一步调度
void
exitFromCPU(usize code)
{disable_and_store(); // 关闭异步中断int tid CPU.current.tid; // 当前运行线程tidexitFromPool(CPU.pool, tid); // 清除线程池中占用标记告诉调度算法线程已经结束printf(Thread %d exited, exit code %d\n, tid, code);switchThread(CPU.current.thread, CPU.idle); // 切换到调度器线程
}// 切换到 idle 线程表示正式由 CPU 进行线程管理和调度这个函数通常在启动线程中调用
// 由于启动线程被构造为一个局部变量我们再也无法切换回启动线程相当于操作系统的初始化工作已经结束
void
runCPU()
{ Thread boot {0L, 0L}; // 启动线程switchThread(boot, CPU.idle); // 从启动线程切换进 idleboot 线程信息丢失不会再回来
}4、线程调度的入口点函数idleMain()是调度线程最核心的函数。调度线程的所有逻辑都在这个函数中循环。
// kernel/processor.c// 线程调度的入口点函数是调度线程最核心的函数
void
idleMain()
{// 进入 idle 时禁用异步中断disable_and_store();while(1) {// 向线程池获取一个可以运行的线程RunningThread rt acquireFromPool(CPU.pool);if(rt.tid ! -1) {// 有线程可以运行CPU.current rt; // 设置调度器当前线程CPU.occupied 1; // 标志线程正在运行printf(\n will switch_to thread %d in idle_main!\n, CPU.current.tid);// 从调度器线程 切换到 当前线程switchThread(CPU.idle, CPU.current.thread); // 切换回 idle 线程处printf( switch_back to idle in idle_main!\n);CPU.occupied 0; // 标记当前没有线程正在运行// 修改线程池内的线程信息在一个线程停止运行切换回调度线程后调用retrieveToPool(CPU.pool, CPU.current);} else {// 无可运行线程短暂开启异步中断并处理enable_and_wfi();disable_and_store();}}
}5、时钟中断引发调度线程调度很重要的一个特点就是由时钟中断来触发。
tickCPU() 函数在时钟中断时被调用每当时钟中断发生时如果当前有正在运行的线程都会检查一下当前线程的时间片是否用完如果用完了就需要切换到调度线程。
// kernel/processor.c// 在时钟中断时被调用每当时钟中断发生时如果当前有正在运行的线程
// 都会检查一下当前线程的时间片是否用完如果用完了就需要切换到调度线程
void
tickCPU()
{// 判断当前是否有正在运行线程不是 idleif(CPU.occupied) {// 当前线程运行时间片是否耗尽if(tickPool(CPU.pool)) {// 关闭中断usize flags disable_and_store();// 切换到 idle 调度器线程switchThread(CPU.current.thread, CPU.idle);// 某个时刻再切回此线程时从这里开始restore_sstatus(flags);}}
}不要忘了在时钟中断处理函数中调用这个函数。
// kernel/interrupt.c// 时钟中断处理设置下一次时钟中断时间
void
supervisorTimer()
{extern void tick(); tick(); // 设置下一次时钟中断时间extern void tickCPU(); tickCPU(); // 检查当前线程的时间片是否用完
}6.3 Round-Robin 调度算法
1、我们在第一节已经实现了一个调度算法的框架只要实现其中的五个函数即可本节将实现一个很基础的 Round-Robin 调度算法 wiki即时间片轮转调度算法。大致思想下图来自小林coding图解操作系统6.1 进程调度/页面置换/磁盘调度算法 | 小林coding (xiaolincoding.com) 2、我们使用一个双向环形链表来实现队列链表的节点按照 tid 1 都存放在数组中其中下标 0 处为 Dummy Head用于快速找到队列头。
队列中的元素如下定义
// kernel/rrscheduler.c// 双向环形链表来实现队列,队列元素如下
// 链表的节点按照 tid 1 都存放在数组中其中下标 0 处为 Dummy Head用于快速找到队列头
typedef struct
{int valid; // 标记线程是否有效usize time; // 线程剩余时间片int prev; // 前一个线程tidint next; // 后一个线程tid
} RRInfo;这些元素并不存储 Thread只存储 tid这种实现方式侵入性较小耦合度低便于替换。定义一个结构体用于存储调度器相关信息其中 current 表示当前正在运行的线程的 tid。
// kernel/rrscheduler.c// 调度器信息结构体
struct
{RRInfo threads[MAX_THREAD 1]; // 优先级调度队列由于 0 号位有个 Dummy Head所以 threads 数组的长度为 MAX_THREAD 1usize maxTime; // 最大时间片int current; // 当前正在运行的tid
} rrScheduler;3、具体的五个调度函数实现代码中附有详细注释
// kernel/rrscheduler.c// 初始化调度器
void
schedulerInit()
{rrScheduler.maxTime 1; // 设置最大时间片为1rrScheduler.current 0; // 当前没有线程运行设置当前线程为0/* 第 0 个位置为 Dummy head用于快速找到链表头和尾 */RRInfo ri {0, 0L, 0, 0}; // 初始化一个无效的线程信息结构rrScheduler.threads[0] ri;
}// 将一个线程加入线程调度即加入调度队列尾部
void
schedulerPush(int tid)
{tid 1; // 调整索引if(tid 1 MAX_THREAD 1) {panic(Cannot push to scheduler!\n);}// 若线程没有时间片初始化为最大时间片if(rrScheduler.threads[tid].time 0) {rrScheduler.threads[tid].time rrScheduler.maxTime;}// 获取当前队列尾部int prev rrScheduler.threads[0].prev;// 将线程加入队列尾部rrScheduler.threads[tid].valid 1; // 标记线程有效rrScheduler.threads[prev].next tid; // 尾部next指向当前线程rrScheduler.threads[tid].prev prev; // 当前线程prev指向尾部线程rrScheduler.threads[0].prev tid; // 头部prev指向当前线程rrScheduler.threads[tid].next 0; // 当前线程next指向头部
}// 从就绪线程中选择一个运行如果没有可运行的线程则返回 -1
int
schedulerPop()
{// 获取队列一个有效线程int ret rrScheduler.threads[0].next; if(ret ! 0) {// 若有可用线程则从队列头部弹出int next rrScheduler.threads[ret].next; // 获取该线程的下一个线程int prev rrScheduler.threads[ret].prev; // 获取该线程的上一个线程rrScheduler.threads[next].prev prev; // 更新下一个线程的prevrrScheduler.threads[prev].next next; // 更新上一个线程的nextrrScheduler.threads[ret].prev 0; // 清空当前线程的prevrrScheduler.threads[ret].next 0; // 清空当前线程的nextrrScheduler.threads[ret].valid 0; // 标记当前线程为无效rrScheduler.current ret; // 设置调度器当前线程为弹出线程}return ret-1; // 调整索引
}// 提醒调度算法当前线程又运行了一个 tick
// 输出1-表示调度算法认为当前线程需要被切换出去0-不需要切换出去
int
schedulerTick()
{int tid rrScheduler.current; // 获取当前线程tidif(tid ! 0) {// 当前线程有效rrScheduler.threads[tid].time - 1; // 当前线程时间片-1if(rrScheduler.threads[tid].time 0) { return 1; // 时间片用尽则切换出去} else {return 0; // 否则不切换}}return 1; // 如果当前线程也进行切换
}// 告诉调度算法某个线程已经结束
void
schedulerExit(int tid)
{tid 1; // 调整索引// 判断结束的线程是否为当前正在运行的线程if(rrScheduler.current tid) {rrScheduler.current 0; // 将当前线程设置为0表示没有线程在运行}
}6.4 调度测试
1、我们完成了所有的部分终于可以开始测试了我们计划创建一些线程线程的入口点是这个函数
// kernel/thread.c// 线程测试函数作为入口点
void
helloThread(usize arg)
{printf(Begin of thread %d\n, arg);int i;// 将传入的参数输出800遍for(i 0; i 800; i ) {printf(%d, arg);}printf(\nEnd of thread %d\n, arg);exitFromCPU(0); // 退出while(1) {}
}会将传入的参数输出 800 遍之后调用 exitFromCPU() 退出。初始化线程更新为如下
// kernel/thread.c// 初始化线程
void
initThread()
{// 1.创建调度函数实现Scheduler s {schedulerInit,schedulerPush,schedulerPop,schedulerTick,schedulerExit};s.init(); // 初始化调度器// 2.创建线程池ThreadPool pool newThreadPool(s);// 3.构建idle调度线程Thread idle newKernelThread((usize)idleMain);// 4.初始化CPU调度器initCPU(idle, pool);// 5.构造线程并添加到CPU中usize i;for(i 0; i 5; i ) {Thread t newKernelThread((usize)helloThread); // 构造新内核线程usize args[8];args[0] i;appendArguments(t, args); // 为线程传入初始化参数// 6.启动addToCPU(t); // 将线程添加到调度队列中}printf(***** init thread *****\n);
}在main函数中加入线程初始化和切换到idle调度线程
void main()
{extern void initInterrupt(); initInterrupt(); // 设置中断处理程序入口 和 模式extern void initTimer(); initTimer(); // 时钟中断初始化extern void initMemory(); initMemory(); // 初始化 页分配 和 动态内存分配extern void mapKernel(); mapKernel(); // 内核重映射三级页表机制extern void initThread(); initThread(); // 初始化线程管理extern void runCPU(); runCPU(); // 切换到 idle 调度线程表示正式由 CPU 进行线程管理和调度while(1) {}
}运行输出结果如下 Init Interrupt
***** Init Memory *****
***** Remap Kernel *****
***** init thread ***** will switch_to thread 0 in idle_main!
Begin of thread 0
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
End of thread 0
Thread 0 exited, exit code 0switch_back to idle in idle_main! will switch_to thread 1 in idle_main!
Begin of thread 1
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 switch_back to idle in idle_main! will switch_to thread 2 in idle_main!
Begin of thread 2
22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222
End of thread 2
Thread 2 exited, exit code 0switch_back to idle in idle_main! will switch_to thread 3 in idle_main!
Begin of thread 3
33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
End of thread 3
Thread 3 exited, exit code 0switch_back to idle in idle_main! will switch_to thread 4 in idle_main!
Begin of thread 4
444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 switch_back to idle in idle_main! will switch_to thread 1 in idle_main!
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
End of thread 1
Thread 1 exited, exit code 0switch_back to idle in idle_main! will switch_to thread 4 in idle_main!
44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444
End of thread 4
Thread 4 exited, exit code 0switch_back to idle in idle_main!你的输出可能与我不完全一样但是可以看出线程 1 在第一次运行时没有来得及运行结束就被切换到线程 2 了在线程 3 运行结束后线程 1 又被调度占用了 CPU 才运行结束。
