| 多任务
|
|
|
|
| 单任务cpu，多任务并发的基本原理
|
| 对时间资源分片，分时复用
|
| 单cpu只有并发，没有并行
|
| 每个task分多少时间，看调度策略
|
| 任务切换，需要保存现场，重新调度可以恢复现场
|
| 任务无感知
|
|
|
| 任务调度基本机制
|
| current是当前任务
|
| ready queue里保存即将运行的task
|
| 然后随时switch
|
|
|
| 任务状态
|
| 当前任务有runing，如果被抢占，进入Ready
|
| 如果等待资源可以用，使用wait进入blocked状态，需要主动唤醒
|
| 子任务结束，不会完全释放，linux需要父任务清理，
|
| 这里设计一个专门的系统任务gc来负责清理
|
|
|
数据结构TaskInner
| idle
|
是标记系统任务，别人都没工作，它会工作
|
| init
|
就是主线程
|
| entry
|
任务逻辑函数入口
| 可以认为这里所有并发的都是线程，没有进程的概念，因为就一个地址空间
|
|
| state
|
就是4个状态
|
| kstack
|
每个线程有自己的stack
| 调度是需要切换的上下文ctx
|
| 包含一系列寄存器状态，通过状态的保存恢复来完成调度
|
|
| task_ext
|
任务扩展属性，用于向宏内核和Hypervisor扩展，这里是空
|
|
|
调度整体框架
| 支持协作式和抢占式调度通用框架
|
在这三里调来调去
| 当前任务，
|
| run_queue，
|
| 并列的wait_queue，
|
|
| 还有定时器，比较关键
|
|
|
|
|
|
|
|
|
|
api
| spawn创建新任务
|
| yield_now主动让出cpu执行权，
|
| 称为协作式
|
|
|
调度框架初始化
| run_queue的初始化，
|
| 初始化idle,main,gc
|
| 初始化定时器
|
|
|
三个系统任务
| main
|
没有多任务就这一个
|
| 其他子线程gc回收
|
|
| idle
|
| 所有任务都阻塞，没有ready
|
| 对特定arch（体系结构），会等待中断irq，或其他非忙等指令
|
|
|
|
| 小结
|
|
任务如何切换
| 对任务上下文context进行切换
|
任务状态的最小寄存器集合
|
| 从两个角度看
|
左边
| 包含ra
|
函数调用返回地址
|
对应于执行流
|
| sp
|
多任务之间关键就是换栈
|
|
| s0-s11
|
体系结构要求必须保存
|
|
|
| context_switch
|
| 进入的时候是current_task，
|
| 返回的时候从另一个任务返回next-task
|
|
|
|
内部实现
| 保存当前任务状态
|
| 所有寄存器
|
| 把下一个任务状态恢复出来
|
|
|
协作式调度
| 如果完全协作式调度
|
| 某个不让出或延迟让出
|
| 其他任务会饥饿
|
|
|
| 协作式算法FIFO
|
|
具体实现
| 实现trait Base Scheduler
|
| 重要的是pick_next_task
|
| 和put_prev_task
|
|
|
同步互斥
| 单cpu，只需要实现上面两层，
|
| 只要关中断，就没有其他抢占
|
|
|
|
| 多cpu需要一个争夺临界区特殊变量，
|
| 一个原子变量
|
|
|
|
互斥锁
| 一块是自旋锁
|
简化版可以用一个原子变量代替
|
| 一块等待队列
|
|
|
|
内存分配算法
| tlsf
|
| 两级bitmap加链表
|
| bitmap第一级，每个bit对应一个内存块
|
| 图右上角，1代表空闲，0占用，这里有两个1，2^15和2^6有空闲块
|
|
| 第二级，继续去找哪块空闲
|
| 有几个bit，对块几等分，这里是4等分
|
| 再指向一个链表头
|
|
|
|
|
| linux用来管理page的一个传统核心算法
|
| 这里用来作为balloc字节分配器使用
|
| order用来表示块大小
|
| 每一级不同大小，上一级是下一级两倍
|
|
|
|
|
| 比较好解决内存碎片化问题
|
|
| Slab
|
| 在linux里跟buddy配合的
|
| 用来做page的上一级，就是缓存的这一级的管理
|
| 也用在字节分配器balloc
|
| 也有一个order list
|
| 指向一个slab管理结构体
|
| 核心结构也是一个空闲链表，包含所有空闲块
|
| 刚开始初始化，从page里申请出来，根据单元大小切分
|
| 不足的时候继续按照buddy申请过程来
|
| 如果链表里块比较多，可以合并再放回去
|
|
|
|
抢占式调度概念
| 必须基于系统定时器来打断当前任务执行
|
| 抢占针对目标就是current task
|
|
| 不是无条件抢占
|
|
| 内部条件
|
比如时间片耗尽
|
| 外部条件
|
通过锁，保证临界区不抢占
|
|
|
|
抢占发生条件
| 内部条件
|
每次中断，对时间片计数递减，耗尽，设置pending标志，表示可以抢占
|
| 外部条件
|
设置临界区的控制标志
| 一个是自旋锁
|
| 自旋锁有两部分能力
|
| 保存中断状态，关中断
|
| 可以关抢占no preempt
|
|
| 单独关闭抢占
|
|
| 这俩可叠加
|
有点像信号量
|
|
|
| 内外条件都具备的时候，可以抢占
|
|
|
抢占与协作式的主要区别
| 需要引入平台时钟中断
|
| 需要外部抢占控制，自旋锁+guard变量
|
|
|
时钟中断与抢占式调度细节
| 注册时钟中断响应函数
|
|
| 中断内部会先检测事件列表
|
check_events
|
| RUN_QUEUE是跟当前task调度相关的
|
| 里面检查task_tick看内部条件是否满足
|
| 满足就可以pending了
|
|
|
|
抢占式调度算法
| rr算法
|
| 简单，定时器递减，到了就pending
|
| 同时如果外部条件允许抢占，处于禁用到启用的边沿上，可以进行抢占
|
| 仍然可以使用yield自己主动让出
|
|
| 实现
|
| 保持一个时间片成员time_slice
|
| 循环列表，使用双端可操作队列VecQueue
|
| 如果时间片没耗尽，放回queue脑袋，下次继续提出这个
|
| 耗尽了，放回队尾，等待调度
|
| task_tick，就是处理递减
|
| <=1的时候可以被抢占了
|
|
|
| CFS最常用的公平调度算法
|
| vruntime最小的任务是优先级最高的任务
|
| delta是可变的，其他固定
|
| delta跟时钟中断相关
|
| 每次触发，只针对当前这个任务操作
|
| 对delta进行递加操作
|
| vruntime向上走，超过其他的之后，它不是最小，会触发其他的抢占
|
|
| 实现
|
| 基于btreemap运行队列
|
可以当成一个有序队列
|
队首最小
|
| 插入进去的时候需要重新计算此时的runtime
|
使用get_vruntime
|
因为当前任务执行后 runtime一定会发生变化
|
| 取下个任务直接从有序队列取第一个
|
|
|
| 存在当前任务放进去后仍然队首，拿出来还是他
|
|
|
| task_tick，第一次运行的时候允许进行一次调度，min_vruntime.is_none
|
|
|
| 再就是计算当前任务的vruntime是不是比min_vruntime大，说明有其他的可以调度，触发重新调度
|
|
|
|
| 具体数据结构
|
| init_vruntime决定一开始是否容易被调度
|
后面影响变小
|
|
| nice跟优先级相关，决定delta的变化速度，nice高，变化慢，优先级高
|
|
|
|
|
|
|
| 总结
|
|
|
Generated
2025-05-05 04:17:35 +0000
25bcfca-dirty
2025-05-04 14:47:56 +0000
