钦州网站建设设计,wordpress倒计时,客户网站留言,闲鱼网络营销方式基于MiniOS的CFS调度和增量式sleep 文章目录 基于MiniOS的CFS调度和增量式sleep一、项目内容二、项目需求及分析CFS调度策略nicevruntime红黑树 增量式sleep/delay延时队列系统延时队列的插入延迟队列的操作延时队列的实现 三、具体实现3.1 实验环境与搭建3.2 实验设计CFS调度策…基于MiniOS的CFS调度和增量式sleep 文章目录 基于MiniOS的CFS调度和增量式sleep一、项目内容二、项目需求及分析CFS调度策略nicevruntime红黑树 增量式sleep/delay延时队列系统延时队列的插入延迟队列的操作延时队列的实现 三、具体实现3.1 实验环境与搭建3.2 实验设计CFS调度策略红黑树设计CFS树设计CFS调度策略设计 增量式sleep延时队列增量式sleep策略设计 简单测试程序设计修改设计3.3 添加函数的代码红黑树核心代码CFS树核心代码nice系统调用核心代码CFS调度策略核心代码延时队列核心代码增量式sleep策略核心代码简单测试程序核心代码修改设计核心代码 四、调试运行结果红黑树测试cfstree测试CFS调度以及nice调用测试增量式sleep测试 五、所遇问题及解决方法Q1每次创建新进程时由于新插入的进程的运行时间是0所以会疯狂抢占运行时间这也导致老进程会出现饥饿的情况。Q2一开始vruntime设置为int因为ticks就是int类型但是根据测试发现当nice值过小时每次÷的权重会变得很大。由于int÷int最后是结果为整数并且向0趋近所以会使vruntime不增加导致调度不切换。Q3延迟队列时不时会发生崩溃还有明明到时间了不出队的情况。 六、项目总结七、参考资料 一、项目内容 项目文档及源码见schedule-miniOS
实现CFS调度策略 参考Linux中实现的完全公平调度算法编写nice系统调用控制不同进程的分配时间片权重 增量式sleep通过维护sleep队列中的等待时间增量实现O(1)弹出插入为O(n)的sleep实现编写测试程序 创建多个进程设置每个进程的nice值观察调度的变化。增加每个进程的统计信息包括进程的nice值、运行时间等。让多个进程使用增量式sleep等待不同的时间观察它们被唤醒的时间顺序。在大规模并发的情况下运行程序检查CFS调度和增量式sleep的性能表现。 二、项目需求及分析 CFS调度策略 CFSCompletely Fair Scheduler是 Linux 内核中用于进程调度的一种策略。它旨在提供公平性和可预测性以便在多任务环境中合理分配 CPU 时间片给各个进程。以下是 CFS 调度策略的主要特点和原则 公平性CFS 致力于公平地分配 CPU 时间给所有的任务即使在高负载的情况下也要保持公平。这是通过追踪任务的运行时间并动态调整时间片大小来实现的。红黑树CFS 使用红黑树来组织正在运行的进程队列。进程在红黑树中的位置决定了它们获得 CPU 时间片的顺序。虚拟运行时间CFS 使用“虚拟运行时间”来跟踪每个进程运行的时间。这是一个相对的概念即使进程被阻塞它仍然会累积虚拟运行时间以便在下次分配 CPU 时获得更多的时间片。时间片调整CFS 动态调整进程的时间片大小使得进程的虚拟运行时间与其他进程大致相等。这有助于确保所有进程在长期运行时都能获得相似的CPU时间。低延迟CFS 避免了传统的抢占式调度中可能出现的大的抢占延迟。它倾向于平滑地调整时间片以避免频繁的上下文切换。自调节CFS 调度器尽量自动适应不同负载下的情况以确保系统整体上的性能和公平性。 CFS 的设计目标是保持系统公平性、有效利用 CPU 资源并在多任务环境下提供较为一致的响应时间。通过跟踪虚拟运行时间和动态调整时间片大小CFS 力图确保每个进程都能公平地分享 CPU 资源。 CFS 调度器没有时间片的概念CFS 的理念就是让每个进程拥有相同的使用 CPU 的时间。比如有 n 个可运行的进程那么每个进程将能获取的处理时间为 1/n。
在引入权重之后在一个调度周期中分配给进程的运行时间计算公式如下 实际运行时间 调度周期 ∗ 进程权重 / 所有进程权重之和 实际运行时间 调度周期 * 进程权重 / 所有进程权重之和 实际运行时间调度周期∗进程权重/所有进程权重之和 可以看到权重越大分到的运行时间越多。
调度周期在某个时间长度可以保证运行队列中的每个进程至少运行一次把这个时间长度称为调度周期。也称为调度延迟因为一个进程等待被调度的延迟时间是一个调度周期。调度最小粒度为了防止进程切换太频繁进程被调度后应该至少运行一小段时间把这个时间长度称为调度最小粒度。
//默认调度周期 20ms
unsigned int sysctl_sched_latency 20000000ULL;
//默认调度最小粒度 4ms
unsigned int sysctl_sched_min_granularity 4000000ULL;
// 默认一个调度周期内的进程数sysctl_sched_latency / sysctl_sched_min_granularity
static unsigned int sched_nr_latency 5;如果运行队列中的进程数量太多导致把调度周期 sysctl_sched_latency 平分给进程时的时间片小于调度最小粒度那么调度周期取 “调度最小粒度 × 进程数量”。
如果真的以上面的方式进行调度那就是完全按照权重进行调度也就实现不了完全公平调度了。
nice
再引入nice值来调节权重带来的影响。
CFS 调度器中使用 nice 值(取值范围为[-20 ~ 19])作为进程获取处理器运行比的权重nice 值越高(优先级越低)的进程获得的 CPU使用的权重越低。
Linux中权重和nice的关系可以通过prio_to_weight数组进行转换
static const int prio_to_weight[40] {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};vruntime
为了让每个进程完全公平调度因此就引入了一个 vruntime (虚拟运行时间virtual runtime)的概念, 每个调度实体都有一个 vruntime该vruntime 根据调度实体的调度而不停的累加CFS 根据 vruntime 的大小来选择调度实体。
虚拟时间和实际时间的关系如下 虚拟运行时间 实际运行时间 ∗ ( N I C E _ 0 _ L O A D / 进程权重 ) 虚拟运行时间 实际运行时间 * ( NICE\_0\_LOAD / 进程权重) 虚拟运行时间实际运行时间∗(NICE_0_LOAD/进程权重) 其中NICE_0_LOAD 是 nice为0时的权重(默认)也即是 1024。也就是说nice 值为0的进程实际运行时间和虚拟运行时间相同。
虚拟运行时间一方面跟进程运行时间有关另一方面跟进程优先级有关。进程权重越大, 运行同样的实际时间, vruntime 增长的越慢。
一个进程在一个调度周期内的虚拟运行时间大小为: v r u n t i m e 进程在一个调度周期内的实际运行时间 ∗ 1024 / 进程权重 ( 调度周期 ∗ 进程权重 / 所有进程总权重 ) ∗ 1024 / 进程权重 调度周期 ∗ 1024 / 所有进程总权重。 vruntime 进程在一个调度周期内的实际运行时间 * 1024 / 进程权重 \\ (调度周期 * 进程权重 / 所有进程总权重) * 1024 / 进程权重\\ 调度周期 * 1024 / 所有进程总权重。 vruntime进程在一个调度周期内的实际运行时间∗1024/进程权重(调度周期∗进程权重/所有进程总权重)∗1024/进程权重调度周期∗1024/所有进程总权重。 可以看到, 一个进程在一个调度周期内的 vruntime 值大小是不和该进程自己的权重相关的, 所以所有进程的 vruntime 值大小都是一样的。
红黑树
CFS 采用虚拟运行时间越小越先调度。
当权重越高的进程随着调度的次数多其 vruntime 的累加也就越多。当其 vruntime 的累加大于其他低优先级进程的 vruntime 时低优先级的进程得以调度。这就保证了每个进程都可以调度而不会出现高优先级的一直得到调度而优先级低的进程得不到调度而产生饥饿。
那么在 CFS 中 vruntime 是怎么使用的呢
CFS 中的就绪队列是一棵以 vruntime 为键值的红黑树虚拟时间越小的进程越靠近整个红黑树的最左端。因此调度器每次选择位于红黑树最左端的那个进程该进程的 vruntime 最小也就最应该优先调度。 增量式sleep/delay 延时队列系统
延时队列系统Delayed Queue System是一种用于管理和处理延时任务的系统。它允许将任务排入队列并在指定的延时时间之后执行这些任务。
原有的延时队列系统
把所有延时进程的TCB表按要求的延时时间从小到大排序称为延迟队列 。每次时钟中断把队列中的所有等待时间减1。为0则使之就绪。需要遍历整个队列。
可见原有的延时系统每次时钟中断需要将遍历整个延时队列时间复杂度为O(n)。
为了改进原有的延时队列引进了相对延迟这个概念。
相对延迟 △ t i △t_i △ti任务i的延迟时间与前面任务延迟时间的差值。
绝对延迟 t i t_i ti:任务i要等的绝对时间。
它们之间满足如下关系 延时队列的插入
设任务Q调用延时命令它的延迟时间为 t Q t_Q tQ。
寻找插入位置若 T C B Q TCB_Q TCBQ要插入 T C B i − 1 TCB_{i-1} TCBi−1与 T C B i TCB_i TCBi之间则必须有满足如下条件 计算Q的相对时间然后从 △ t i △t_i △ti中减去 △ t Q △t_Q △tQ △ t i △ t i − △ t Q \triangle t_i \triangle t_i - \triangle t_Q △ti△ti−△tQ 特殊状况
队列为空插到队首延迟最长时要挂在队尾 。
延迟队列的操作
每次时钟中断将队首TCB时间减1。若非零则进行其它操作若为零把它从延时队列中取出并插入就绪队列还要检查以后的TCB看是否也为零。
延时命令处理和时钟中断处理必须进行互斥访问延迟队列。
延时队列的实现 这种实现的延时队列其实就是一种差分的算法根据插入操作的定义此队列是一个有序递增的队列所以出队的时间复杂度为O(1)入队的时间复杂度为O(n)。 三、具体实现 3.1 实验环境与搭建 系统Ubuntu 20.04编译⼯具gcc 9.4.0, nasm 2.14.02, make 4.2.1调试器: gdb 9.2模拟器: qemu-system-i386 4.2.1运行库: GNU Binutils 2.34, gcc-multilib与gcc配套版本管理工具: git 2.25.1 3.2 实验设计 CFS调度策略 红黑树设计
节点设计
struct rb_node
{unsigned long rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1struct rb_node *rb_right;struct rb_node *rb_left;
};根设计
struct rb_root
{struct rb_node *rb_node;
};主要接口设计
红黑树插入调整与删除
extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);红黑树插入函数
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,struct rb_node ** rb_link)红黑树节点获取及遍历函数
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);CFS树设计
节点设计
typedef double runtime_t;typedef struct cfs_node {struct rb_node node; // 红黑树节点char *keystring; PROCESS* proc;u32 lock;int nice;runtime_t vruntime;int rruntime;int start;
}cfs_node;nice值转换表
static const int sched_prio_to_weight[40] {/* -20 */ 88761, 71755, 56483, 46273, 36291,/* -15 */ 29154, 23254, 18705, 14949, 11916,/* -10 */ 9548, 7620, 6100, 4904, 3906,/* -5 */ 3121, 2501, 1991, 1586, 1277,/* 0 */ 1024, 820, 655, 526, 423,/* 5 */ 335, 272, 215, 172, 137,/* 10 */ 110, 87, 70, 56, 45,/* 15 */ 36, 29, 23, 18, 15,
};主要接口设计
创建节点及初始化
// 初始化cfs_node
struct cfs_node *cfs_node_init(cfs_node* node, PROCESS* proc, int nice);
// 创建一个CFS节点
struct cfs_node *create_cfs_node(PROCESS *proc, int nice);搜索接口
// 通过搜索vruntime进行搜索
struct cfs_node *cfs_search(struct rb_root *root, struct cfs_node* tar);
// 通过pid进行搜索
struct cfs_node *cfs_search_pid(struct rb_root *root, u32 pid);插入删除接口
// 插入操作
int cfs_insert(struct rb_root *root, struct cfs_node *data);
// 删除操作
int cfs_remove(struct rb_root *root, struct cfs_node *data);
// 从CFS调度器中删除进程
int cfs_remove_process(struct rb_root *root, PROCESS *proc);调度接口
// CFS调度函数选择下一个要执行的进程
PROCESS *cfs_schedule_next(struct rb_root *root);更新vruntime并调整红黑树结构接口
// 更新节点的 vruntime 并调整红黑树结构
int cfs_update_vruntime(struct rb_root *root, struct cfs_node *node, runtime_t new_vruntime);
// 更新进程的运行时间vruntime
runtime_t update_vruntime(struct cfs_node *node, int ticks);输出调试信息接口
// 打印进程信息
void print_process_info(PROCESS *proc);
// 遍历CFS调度器并打印进程信息
void print_cfs_scheduler(struct rb_root *root);Set接口
// 设置nice值
void set_nice(struct cfs_node* node, int nice);
//设置vruntime值
void set_vruntime(struct cfs_node* node, runtime_t vruntime);Get接口
// 返回cfstree中最小的vruntime
runtime_t get_min_vruntime(struct rb_root *root);CFS调度策略设计
初始化CFS树 init_cfs函数 首先声明了一个指向PROCESS结构体的指针p和一个整数i并初始化i为0。 将全局变量cfs_cnt初始化为0用于记录CFS树中的进程数。 使用循环遍历操作系统的进程表proc_table中的所有进程。每次迭代中对当前进程p执行以下操作 将in_cfs[i]标志位设置为false表示当前进程不在CFS树中。 调用cfs_remove_process函数从CFS树中移除当前进程。调用cfs_node_init函数初始化cfs_list[i]该函数将进程p与CFS节点关联并初始化其优先级为0。如果进程的状态为READY说明该进程可以被调度执行以下操作 调用cfs_insert函数将cfs_list[i]插入CFS树中。调用set_nice函数设置该进程的nice值为-5。增加cfs_cnt计数。将in_cfs[i]标志位设置为true表示该进程在CFS树中。 kernel_main函数 该函数是内核的主函数在操作系统启动时被调用。 在初始化其他部分之前调用init_cfs函数来初始化CFS树。
// 初始化cfs树
void init_cfs();刷新CFS树
CFS每次调度时要及时刷新cfs树。如果有进程状态为ready但是不在cfs树中则需要将该进程插入到cfs树对于新进程可以选择将vruntime设置为cfstree中vruntime最小值-1来插入这样能保证新进程被优先调度同时对于那些仍在cfs树中但进程状态已经不是ready的需要将其移出cfs树。
flush_cfs用于在CFS调度器中刷新进程状态。通过遍历操作系统的进程表根据进程的READY状态和在CFS树中的状态动态地更新CFS树的结构。对于READY状态的进程将其插入CFS树并设置相应的运行时信息而对于非READY状态的进程将其从CFS树中移除。这确保了CFS树中的进程状态与实际进程表中的状态保持一致维护了CFS调度算法的准确性和公平性。
void flush_cfs();CFS调度逻辑
cfs_schedule函数是CFS调度器的核心部分负责在每个调度周期内选择下一个要执行的进程。它首先根据当前运行进程和系统时间计算已运行时间然后根据CFS算法更新虚拟运行时值并在CFS树上调整进程位置。接着通过刷新CFS树和循环选择下一个进程确保选中的进程是READY状态并更新其运行时信息。如果选中的进程不是READY状态则将其从CFS树中移除减少计数并在树为空时重新初始化。这确保CFS调度器根据进程的虚拟运行时值公平地选择下一个执行的进程。
void cfs_schedule();增量式sleep 延时队列
节点设计
typedef struct delay_node_s {PROCESS* proc;u32 lock;int delay;struct delay_node_s* next;
}delay_t;队列设计
typedef struct delaylist{delay_t* head;u32 lock;int size;int capacity;
}delaylist;主要接口设计
初始化接口
// 初始化节点
void init_delay_node(delay_t* node, PROCESS* proc);
// 初始化队列
void init_delaylist(delaylist* dlist, int capacity);插入删除接口
在insert_delay_node函数中
如果队列为空或新节点的延时小于等于队列头节点的延时将新节点插入队列头部更新队列头节点的延时值。否则遍历队列找到新节点应插入的位置保持队列的有序性。在遍历的过程中更新节点的延时值。插入成功后更新队列的大小释放锁然后返回插入成功的标志。
在remove_delay_node函数中
遍历延时队列找到指定节点更新其前一个节点的next指针同时更新后续节点的延时值。如果节点为队列头节点则更新队列头指针。移除成功后更新队列的大小释放锁然后返回移除成功的标志。如果未找到指定节点释放锁后返回未找到节点的错误码。
// 在延迟队列中插入
int insert_delay_node(delaylist* dlist, delay_t* node);
// 在延迟队列中删除
int remove_delay_node(delaylist* dlist, delay_t* node);打印接口
// 打印延迟队列
void print_delay_list(delaylist* dlist);减少延迟接口
首先检查延时队列是否为NULL或队列头为空如果是则直接返回不执行后续操作。然后使用disable_int函数禁用中断以确保对共享资源的访问是原子的。减小延时队列头节点的延时值即dlist-head-delay--。最后使用enable_int函数启用中断解锁对共享资源的访问。
这个函数的作用是将延时队列中队头节点的延时值减1。在并发环境中通过禁用中断确保对共享资源的原子访问以避免竞态条件和不一致性的问题。
// 延迟队列整体延迟减 1 tick
void minus_delay(delaylist* dlist);增量式sleep策略设计
sleep系统调用
原本MiniOS实现的sleep仅仅是通过循环检查时钟滴答数来实现睡眠功能。在每次循环中将进程状态设置为SLEEPING然后调用sched函数进行调度。这种实现方式会在循环中占用 CPU 资源不是一种高效的睡眠实现方式。通常更好的方式是使用延时队列将进程插入队列中并在合适的时机唤醒。
新修改的sleep调用
首先将当前进程的延时值设置为传入的参数n表示需要睡眠的时间。然后调用insert_delay_node函数将当前进程插入到延时队列中以按照延时值有序地管理睡眠进程。将当前进程的状态设置为SLEEPING表示它正在睡眠。最后调用sched函数进行调度选择新的可运行进程执行。
这个函数的作用是将当前进程加入延时队列设置其状态为睡眠然后通过调度选择新的可运行进程执行。这样通过合理管理延时队列系统能够实现进程的睡眠和唤醒机制。
void sys_sleep(int n);wakeup系统调用
原本MiniOS实现的wakeup仅仅是通过遍历所有进程检查每个进程的状态和通道以实现唤醒指定通道上的睡眠进程。这种方法在处理简单场景时可能是有效的但在系统规模扩大时会导致效率较低因为需要遍历整个进程表。
首先调用minus_delay函数减小延时队列中队头节点的延时值。然后获取延时队列的头节点并检查是否存在。如果队列为空直接返回表示没有需要唤醒的进程。进入一个循环遍历延时队列中的节点同时获取当前节点对应的进程。在循环中判断当前进程的状态是否为SLEEPING并且该节点的延时值是否为0。如果满足条件说明该进程需要被唤醒执行以下操作 调用remove_delay_node函数从延时队列中移除当前节点。将进程的状态设置为READY表示它可以被调度执行。将进程的延时值设为0表示不再需要延时。 继续循环获取下一个节点对应的进程直到找到一个不满足唤醒条件的节点为止。
整体而言这个函数的作用是从延时队列中唤醒所有延时时间为0且状态为SLEEPING的进程。通过遍历延时队列逐个检查节点对应的进程符合唤醒条件的进程将被移出延时队列并设置为READY状态。这样系统可以有效地管理进程的睡眠和唤醒操作。
void sys_wakeup(void *channel);在时钟中断中
在每次的时钟中断中调用wakeup减少延迟时间并查看是否有等待结束的进程
void clock_handler(int irq);简单测试程序设计 红黑树测试
详见user/rbtest.c。
首先创建一个红黑树根节点然后插入三个结构体节点每个节点包含一个字符串键值。通过遍历红黑树输出节点键值验证插入操作的正确性。接着查找键值为baichen的节点并输出其键值然后从红黑树中删除该节点再次遍历红黑树验证删除操作的正确性。整个过程测试了红黑树的插入、查找和删除功能。
cfstree测试
详见user/cfstest.c。
首先创建了一个空的红黑树作为 CFS 调度器的数据结构并初始化三个进程为每个进程关联一个 CFS 节点。随后为每个节点设置虚拟运行时间并通过 cfs_insert 将这些节点插入 CFS 红黑树中。通过测试搜索、删除、调度等功能验证了 CFS 调度器的正确性。通过输出各个阶段的信息包括插入、搜索、删除和调度的结果以及当前红黑树的状态对 CFS 的实现进行了全面的测试和验证。
CFS调度以及nice调用测试
详见user/forktest.c。
通过多次创建线程并在每个线程中执行 test 函数测试了进程优先级的设置和多线程并发执行的情况。在 test 函数中通过 nice 函数设置进程的优先级然后进入一个无限循环在循环中模拟计算密集型工作并输出当前进程的PID、通过 get_pid() 获取的PID以及通过 nice(0) 获取的进程优先级。主函数中通过 --global 递减全局变量 global 并休眠1ticks多次创建线程使得多个线程以并发方式执行 test 函数观察不同线程在执行时的行为。
增量式sleep测试
详见user/delaytest.c。
创建多个线程每个线程在执行test函数时进行不同的延时操作并输出相应的延时完成时间差。在test函数中使用sleep模拟线程的延时操作然后输出当前线程的PID以及延时完成后的时间差。主函数通过循环创建多个线程并在每个线程中设置不同的延时时间通过输出总的延时完成时间差来观察所有线程的执行情况。这样的测试能够验证多线程在不同延时条件下的并发执行行为。 修改设计 CFS完全公平调度可能在一轮中只会调度一次内核进程可能会出现一些实时进程得不到处理的情况。
为了避免这个问题我选择在原本CFS调度的基础上在时钟中断中每2ticks就用轮询调度调度一下内核进程保证实时进程可以被及时调用不会出现饥饿的情况。
并且在clock中按照调度方式的不同执行不同的调度逻辑保证每个调度逻辑之间互不干扰。
当然这种调度策略可能会影响到测试程序因为测试程序只测试全部都为CFS调度的情况。为了测试结果正确在clock_handler中我先关闭了两种调度策略切换的逻辑如果老师或助教想测试可以自行打开。
调度器设计
enum scheduler {ORDER,CFS,
};enum scheduler gsch;调度策略设计
void schedule();void clock_handler(int irq);3.3 添加函数的代码 红黑树核心代码 由于左旋右旋等代码逻辑过于复杂且非本次任务的核心代码所以不在报告中进行展示详见lib/rbtree.c
红黑树插入调整与删除
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{struct rb_node *parent, *gparent;while ((parent rb_parent(node)) rb_is_red(parent)){gparent rb_parent(parent);if (parent gparent-rb_left){{register struct rb_node *uncle gparent-rb_right;if (uncle rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node gparent;continue;}}if (parent-rb_right node){register struct rb_node *tmp;__rb_rotate_left(parent, root);tmp parent;parent node;node tmp;}rb_set_black(parent);rb_set_red(gparent);__rb_rotate_right(gparent, root);} else {{register struct rb_node *uncle gparent-rb_left;if (uncle rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node gparent;continue;}}if (parent-rb_left node){register struct rb_node *tmp;__rb_rotate_right(parent, root);tmp parent;parent node;node tmp;}rb_set_black(parent);rb_set_red(gparent);__rb_rotate_left(gparent, root);}}rb_set_black(root-rb_node);
}void rb_erase(struct rb_node *node, struct rb_root *root)
{struct rb_node *child, *parent;int color;if (!node-rb_left)child node-rb_right;else if (!node-rb_right)child node-rb_left;else{struct rb_node *old node, *left;node node-rb_right;while ((left node-rb_left) ! NULL)node left;if (rb_parent(old)) {if (rb_parent(old)-rb_left old)rb_parent(old)-rb_left node;elserb_parent(old)-rb_right node;} elseroot-rb_node node;child node-rb_right;parent rb_parent(node);color rb_color(node);if (parent old) {parent node;} else {if (child)rb_set_parent(child, parent);parent-rb_left child;node-rb_right old-rb_right;rb_set_parent(old-rb_right, node);}node-rb_parent_color old-rb_parent_color;node-rb_left old-rb_left;rb_set_parent(old-rb_left, node);goto color;}parent rb_parent(node);color rb_color(node);if (child)rb_set_parent(child, parent);if (parent){if (parent-rb_left node)parent-rb_left child;elseparent-rb_right child;}elseroot-rb_node child;color:if (color RB_BLACK)__rb_erase_color(child, parent, root);
}红黑树插入函数
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,struct rb_node ** rb_link)
{node-rb_parent_color (unsigned long )parent;node-rb_left node-rb_right NULL;*rb_link node;
}红黑树节点获取及遍历函数
struct rb_node *rb_first(const struct rb_root *root)
{struct rb_node *n;n root-rb_node;if (!n)return NULL;while (n-rb_left)n n-rb_left;return n;
}struct rb_node *rb_last(const struct rb_root *root)
{struct rb_node *n;n root-rb_node;if (!n)return NULL;while (n-rb_right)n n-rb_right;return n;
}struct rb_node *rb_next(const struct rb_node *node)
{struct rb_node *parent;if (rb_parent(node) node)return NULL;if (node-rb_right) {node node-rb_right; while (node-rb_left)nodenode-rb_left;return (struct rb_node *)node;}while ((parent rb_parent(node)) node parent-rb_right)node parent;return parent;
}struct rb_node *rb_prev(const struct rb_node *node)
{struct rb_node *parent;if (rb_parent(node) node)return NULL;if (node-rb_left) {node node-rb_left; while (node-rb_right)nodenode-rb_right;return (struct rb_node *)node;}while ((parent rb_parent(node)) node parent-rb_left)node parent;return parent;
}CFS树核心代码 与红黑树相同由于代码量过大为了避免冗长只展示核心接口的代码CFS树全部接口代码详见lib/cfsrbt.c。
搜索接口
struct cfs_node *cfs_search(struct rb_root *root, struct cfs_node* tar) {struct rb_node *node root-rb_node;while (node) {struct cfs_node *data rb_entry(node, struct cfs_node, node);runtime_t result cfs_cmp(data, tar);if (result 0)node node-rb_left;else if (result 0)node node-rb_right;elsereturn data;}return NULL;
}struct cfs_node *cfs_search_pid(struct rb_root *root, u32 pid) {struct rb_node *node;for (node rb_first(root); node; node rb_next(node)) {struct cfs_node *data rb_entry(node, struct cfs_node, node);if (data-proc-task.pid pid) {return data;}}return NULL;
}插入删除接口
int cfs_insert(struct rb_root *root, struct cfs_node *data) {while (xchg(cfs_lock, 1) 1) {// 休眠int myticks ticks;while (ticks - myticks DEFAULT_TICKS) ;}struct rb_node **new (root-rb_node), *parent NULL;while (*new) {struct cfs_node *this rb_entry(*new, struct cfs_node, node);runtime_t result cfs_cmp(data, this);parent *new;if (result 0)new ((*new)-rb_left);else if (result 0)new ((*new)-rb_right);}// 新节点插入到红黑树中rb_link_node(data-node, parent, new);rb_insert_color(data-node, root);xchg(cfs_lock, 0);return TRUE; // 插入成功
}int cfs_remove(struct rb_root *root, struct cfs_node *data) {if (!data)return FALSE; // 节点不存在while (xchg(cfs_lock, 1) 1) {// 休眠int myticks ticks;while (ticks - myticks DEFAULT_TICKS) ;}while (xchg(data-lock, 1) 1) {// 休眠int myticks ticks;while (ticks - myticks DEFAULT_TICKS) ;}struct rb_node *node (data-node);if (!node) {xchg(cfs_lock, 0);xchg(data-lock, 0);return FALSE; // 节点不存在于红黑树中}rb_erase(node, root); // 从红黑树中删除节点// 释放节点的内存xchg(cfs_lock, 0);xchg(data-lock, 0);return TRUE; // 删除成功
}int cfs_remove_process(struct rb_root *root, PROCESS *proc) {struct cfs_node *node cfs_search_pid(root, proc-task.pid);if (!node) {return FALSE; // 未找到节点}return cfs_remove(root, node); // 调用已有的删除函数删除节点
};调度接口
PROCESS *cfs_schedule_next(struct rb_root *root) {if (!root-rb_node) return NULL;struct cfs_node *next_node rb_entry(rb_first(root), struct cfs_node, node);if (!next_node) {return NULL; // 没有可执行的进程}return next_node-proc; // 返回下一个要执行的进程
}更新vruntime并调整红黑树结构接口
int cfs_update_vruntime(struct rb_root *root, struct cfs_node *node, runtime_t new_vruntime) {if (!node)return -1; // 节点不存在while (xchg(cfs_lock, 1) 1) {// 休眠int myticks ticks;while (ticks - myticks DEFAULT_TICKS) ;}while (xchg(node-lock, 1) 1) {// 休眠int myticks ticks;while (ticks - myticks DEFAULT_TICKS) ;}// cfstree中找不到此节点if (!cfs_search_pid(root, node-proc-task.pid)) return -2;// 从树中删除节点rb_erase(node-node, root);// 更新节点的 vruntimenode-vruntime new_vruntime;// 重新将节点插入到树中struct rb_node **new (root-rb_node), *parent NULL;while (*new) {struct cfs_node *this rb_entry(*new, struct cfs_node, node);runtime_t result cfs_cmp(node, this);parent *new;if (result 0)new ((*new)-rb_left);else if (result 0)new ((*new)-rb_right);}// 新节点插入到红黑树中rb_link_node(node-node, parent, new);rb_insert_color(node-node, root);xchg(cfs_lock, 0);xchg(node-lock, 0);return 0; // 更新成功
}输出调试信息接口
void print_cfs_scheduler(struct rb_root *root) {struct rb_node *node;uart_kprintf(CFS Scheduler Contents:\n);for (node rb_first(root); node; node rb_next(node)) {struct cfs_node *data rb_entry(node, struct cfs_node, node);print_process_info(data-proc);uart_kprintf(Process vruntime: %d\n, (int)(data-vruntime));uart_kprintf(Process rruntime: %d\n\n, data-rruntime);}
}Set接口
void set_nice(struct cfs_node* node, int nice) {while (xchg(node-lock, 1) 1) {// 休眠int myticks ticks;while (ticks - myticks DEFAULT_TICKS) ;}if(nice -20 || nice 19) {xchg(node-lock, 0);return;}node-nice nice;xchg(node-lock, 0);
}void set_vruntime(struct cfs_node* node, runtime_t vruntime) {while (xchg(node-lock, 1) 1) {// 休眠int myticks ticks;while (ticks - myticks DEFAULT_TICKS) ;}node-vruntime vruntime;xchg(node-lock, 0);
}Get接口
runtime_t get_min_vruntime(struct rb_root *root) {if (!root || !root-rb_node) return -1;struct rb_node *node node rb_first(root);struct cfs_node *data rb_entry(node, struct cfs_node, node);return data-vruntime;
}nice系统调用核心代码 详见kernel/proc.c。
int do_nice(u32 pid, int incr) {if (incr -20 || incr 19) return -1;struct cfs_node* node cfs_search_pid(cfs_tree_root, pid);if (!node) return -1;if (incr) set_nice(node, node-nice incr);return node-nice;
}CFS调度策略核心代码 详见kernel/proc.c。
初始化CFS树
// 初始化cfs树
void init_cfs()
{PROCESS* p;int i 0;cfs_cnt 0;for (p proc_table, i 0; p proc_tableNR_PCBS; p, i) {in_cfs[i] false;cfs_remove_process(cfs_tree_root, p);cfs_node_init(cfs_list[i], p, 0);if (p-task.stat READY) {cfs_insert(cfs_tree_root, cfs_list[i]);set_nice(cfs_list[i], -5);cfs_cnt;in_cfs[i] true;}}
} // main.c
int kernel_main()
{// ...// 在启动时初始化cfs树init_cfs();// ...
}刷新CFS树
void flush_cfs()
{PROCESS* p;int i 0;for (p proc_table, i 0; p proc_tableNR_PCBS; p, i) {if (p-task.stat READY in_cfs[i] false) {cfs_node_init(cfs_list[i], p, 0);// 为了避免老程序饥饿的情况以及保证新进程能被优先调度将新进程以cfstree中最小vruntime - 1插入runtime_t new_vruntime get_min_vruntime(cfs_tree_root) - 1;set_vruntime(cfs_list[i], new_vruntime 0 ? new_vruntime : 0);cfs_insert(cfs_tree_root, cfs_list[i]);cfs_cnt;in_cfs[i] true;}else if (p-task.stat ! READY in_cfs[i] true){cfs_remove_process(cfs_tree_root, p);cfs_cnt--;in_cfs[i] false;}}
}CFS调度逻辑
void cfs_schedule()
{PROCESS* p;cur_proc cfs_list[p_proc_current-task.pid];assert(cur_proc-proc-task.pid 12);assert(cur_proc-vruntime 0);if (cur_proc-start 0) cur_proc-start ticks;int myticks ticks - cur_proc-start; // 计算已运行的时间// 当程序运行准备好或者没有运行满最短时长直接返回if (p_proc_current-task.stat READY myticks sysctl_sched_min_granularity) { p_proc_next p_proc_current; return;}// 更新虚拟时长并将更新其在cfs树上的位置update_vruntime(cur_proc, myticks);cfs_update_vruntime(cfs_tree_root, cur_proc, cur_proc-vruntime);assert(cur_proc-proc-task.pid 12);assert(cur_proc-vruntime 0);// 刷新cfs树flush_cfs();while (1) {p_proc_next cfs_schedule_next(cfs_tree_root);if (p_proc_next-task.stat READY) {next_proc cfs_list[p_proc_next-task.pid];next_proc-start ticks;return;}else {in_cfs[p_proc_next-task.pid] false;cfs_remove_process(cfs_tree_root, p_proc_next);cfs_cnt--;if (cfs_cnt 0) {init_cfs();} }}
}在时钟中断中
详见kernel/clock.c。
void clock_handler(int irq)
{// ...// 真实运行时间cfs_list[p_proc_current-task.pid].rruntime; // ...
}延时队列核心代码 与红黑树相同由于代码量过大为了避免冗长只展示核心接口的代码CFS树全部接口代码详见lib/delaylist.c。
插入删除接口
int insert_delay_node(delaylist* dlist, delay_t* node) {if (dlist NULL || node NULL) {return -1; // 非法输入}if (dlist-size dlist-capacity) {return -2; // 延时队列已满}disable_int();if (dlist-head NULL || node-proc-task.delay dlist-head-delay) {node-delay node-proc-task.delay;dlist-head-delay - node-delay;node-next dlist-head;dlist-head node;} else {delay_t* prev NULL, *cur dlist-head;int delay cur-delay;while (cur-next delay node-proc-task.delay) {prev cur;cur cur-next;delay cur-delay;}if (delay node-proc-task.delay) { node-delay node-proc-task.delay - delay;cur-next node;node-next NULL;} else {node-delay node-proc-task.delay - delay cur-delay;cur-delay - node-delay;node-next prev-next;prev-next node;}}dlist-size;xchg(dlist-lock, 0);xchg(node-lock, 0);enable_int();return 0; // 插入成功
}int remove_delay_node(delaylist* dlist, delay_t* node) {if (dlist NULL || node NULL) {return -1; // 非法输入}disable_int();delay_t* prev NULL, *cur dlist-head;while (cur) {if (cur node) {if (prev NULL) {if (cur-next) cur-next-delay cur-delay;dlist-head cur-next;} else {if (cur-next) cur-next-delay cur-delay;prev-next cur-next;}dlist-size--;enable_int();return 0; // 移除成功}prev cur;cur cur-next;}enable_int();return -2; // 未找到节点移除失败
}打印接口
void print_delay_list(delaylist* dlist) {if (dlist NULL) return;uart_kprintf(delay list content:\n);for (delay_t* cur dlist-head; cur; cur cur-next) {uart_kprintf(pid: %d; delay: %d\n, cur-proc-task.pid, cur-delay);}uart_kprintf(\n);
}减少延迟接口
void minus_delay(delaylist* dlist) {if (dlist NULL || dlist-head NULL) return;disable_int();dlist-head-delay--;enable_int();
}增量式sleep策略核心代码 sleep系统调用
详见kernel/proc.c。
void sys_sleep(int n)
{p_proc_current-task.delay n;insert_delay_node(dlist, delay_nodes[p_proc_current-task.pid]);p_proc_current-task.stat SLEEPING;sched();
}wakeup系统调用
详见kernel/proc.c。
void sys_wakeup(void *channel)
{minus_delay(dlist);delay_t* dnode dlist.head;if (!dnode) return;PROCESS *p dnode-proc;while (dnode p-task.stat SLEEPING dnode-delay 0) {remove_delay_node(dlist, delay_nodes[p-task.pid]);p-task.stat READY;p-task.delay 0;dnode dlist.head;if (!dnode) return;p dnode-proc;}
}在时钟中断中
详见kernel/clock.c。
void clock_handler(int irq)
{// ...// 在每次的时钟中断中调用wakeup减少延迟时间并查看是否有等待结束的进程sys_wakeup(ticks);
}简单测试程序核心代码 红黑树测试
详见user/rbtest.c。 struct rb_root root RB_ROOT;struct mytype data1, data2, data3;rb_init_node(data1.node);rb_init_node(data2.node);rb_init_node(data3.node);data1.keystring hello;data2.keystring world;data3.keystring baichen;my_insert(root, data1);my_insert(root, data2);my_insert(root, data3);struct rb_node* cur rb_first(root);int i 0;printf(before delete\n);while (1) {struct mytype* data container_of(cur, struct mytype, node);printf(data%d: %s\n, i, data-keystring);i;if (!(cur rb_next(cur))) break;}struct mytype* ret my_search(root, baichen);printf(data%s\nstart delete\n, ret-keystring);rb_erase(ret-node, root);printf(delete finished\n);i 0;cur rb_first(root);while (1) {struct mytype* data container_of(cur, struct mytype, node);printf(data%d: %s\n, i, data-keystring);i;if (!(cur rb_next(cur))) break;}cfstree测试
详见user/cfstest.c。 struct rb_root cfs_tree RB_ROOT; // 创建一个空的红黑树myproc process1, process2, process3;init_process(process1, 1, 1, DEFAULT_PRIORITY);init_process(process2, 2, 2, DEFAULT_PRIORITY);init_process(process3, 3, 3, DEFAULT_PRIORITY);process1.task.pid 1;process2.task.pid 2;process3.task.pid 3;printf(init success\n);struct cfs_node node1, node2, node3;cfs_node_init(node1, process1);cfs_node_init(node2, process2);cfs_node_init(node3, process3);printf(node create success\n);node1.vruntime 1024;node2.vruntime 512;node3.vruntime 2048;// 插入节点到红黑树中cfs_insert(cfs_tree, node1);cfs_insert(cfs_tree, node2);cfs_insert(cfs_tree, node3);printf(node insert success\n);// 测试搜索功能struct cfs_node *found_node cfs_search(cfs_tree, process2.task.pid);if (found_node ! NULL) {printf(Node with PID %d found.\n, process2.task.pid);} else {printf(Node with PID %d not found.\n, process2.task.pid);}// 测试删除功能if (cfs_remove_process(cfs_tree, process3)) {printf(Node with PID %d removed successfully.\n, process3.task.pid);} else {printf(Failed to remove node with PID %d.\n, process3.task.pid);}print_cfs_scheduler(cfs_tree);// 测试调度功能myproc *next_process cfs_schedule_next(cfs_tree);if (next_process ! NULL) {printf(Next myproc to be executed: %s\n, next_process-task.p_name);} else {printf(No myproc found for scheduling.\n);}// 测试updateprint_cfs_scheduler(cfs_tree);cfs_update_vruntime(cfs_tree, node3, 100);print_cfs_scheduler(cfs_tree);CFS调度以及nice调用测试
详见user/forktest.c。
int global 2;
void test()
{nice(global);while (1) {int i 100000000;while (--i) {;}printf(i am %d; nice: %d\n, get_pid(), nice(0));}
}int main(int arg, char *argv[]) {int i 0;int j 0;printf(i am father, pid %d\n, get_pid());pthread(test);sleep(1);--global;pthread(test);sleep(1);--global;pthread(test);sleep(1);--global;pthread(test);sleep(1);--global;pthread(test);sleep(1);--global;return 0;
}增量式sleep测试
详见user/delaytest.c。
int i 0;
static int delay[5] {12, 20, 40, 80, 160};void test()
{int past get_ticks();sleep(delay[i % 5]);printf(pid: %d; , get_pid());printf(delay done, delay ticks: %d\n, get_ticks() - past);while (1) {;}
}int main()
{int past get_ticks();for (i 0; i 5; i) {pthread(test);sleep(1);}printf(delay done, delay ticks: %d, get_ticks() - past);return 0;
}修改设计核心代码 详见kernel/proc.c以及kernel/clock.c。
void schedule()
{if (gsch CFS)cfs_schedule();else if (gsch ORDER)order_schedule();
}void clock_handler(int irq)
{// ...if (gsch ORDER) p_proc_current-task.ticks--;else cfs_list[p_proc_current-task.pid].rruntime;gsch CFS;if (ticks % 2 0) gsch ORDER;// ...
}四、调试运行结果 红黑树测试 可见红黑树完成了正确的插入、查找以及删除并且按照我测试程序中的排序函数也即字符串进行排序。 cfstree测试 这个测试是用来独立测试cfstree的正确性的为此我专门重写了simple_cfsrbt这个库保证其可以进行独立测试。
由于在minios上测试会出现一些奇怪链接问题以下的测试我使用我的云服务器进行测试 可见前面插入的三个进程分别按虚拟时间大小进行了排序并且成功打印查询逻辑删除逻辑调度逻辑以及update功能都符合我的预期。
所以cfstree的基本功能正确下面可以进行调度测试。 CFS调度以及nice调用测试 要测试调度正确性以及nice正确性首先要关闭flush_cfstree中的反饥饿处理 运行结果如下 nice值分别为2、1、0、-1、-2符合预期。
现在来查看实际运行实际和nice的关系 可以看到nice为0的7号进程vruntime和rruntime是相等的这也符合理论公式nice为2到-2时pid分别为5到9当进程的虚拟运行时间都为160多时由结果可知实际运行时间9号最长5号最短而且nice每差1实际运行时间会多25%左右。
由以上分析可知调度完全符合预期CFS调度器完成了正确调度。 增量式sleep测试 由以上信息可得上面5个并发的进程都完成了预期时间的等待所以增量式sleep实现成功。 五、所遇问题及解决方法 Q1每次创建新进程时由于新插入的进程的运行时间是0所以会疯狂抢占运行时间这也导致老进程会出现饥饿的情况。 A1为了避免老进程饥饿并且为了保证新进程能被优先调度要将进程的初始vruntime以cfstree中最小的vruntime – 1的值进行插入。 Q2一开始vruntime设置为int因为ticks就是int类型但是根据测试发现当nice值过小时每次÷的权重会变得很大。由于int÷int最后是结果为整数并且向0趋近所以会使vruntime不增加导致调度不切换。 A2为了保证精准度最后将vruntime改为了double类型使其可以更加精准地调度。 Q3延迟队列时不时会发生崩溃还有明明到时间了不出队的情况。 A3延时队列必须注意判空因为延迟队列每次只操作其头节点。每次操作头节点前要进行判空。否则会出现错误。并且在延时队列中可能有多个同一等待时间的任务要将其一次出队。 六、项目总结 带有提交日志的代码仓库schedule-miniOS。 实现CFS调度策略 实现增量式sleep 编写简单测试程序并修改代码中的bug 七、参考资料 Linux 进程管理之 CFS 调度策略 操作系统调度算法3——CFS完全公平调度器 sysprog21/linux-cfs-sim: Simulate Linux Completely Fair Scheduler (CFS) using POSIX Threads
