ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【项目】基于MiniOS的CFS调度和增量式sleep [打印本页]

作者: 宝塔山 时间: 2024-8-30 11:37
标题: 【项目】基于MiniOS的CFS调度和增量式sleep
基于MiniOS的CFS调度和增量式sleep

一、项目内容

项目文档及源码见：schedule-miniOS

实现CFS调度策略：
- 参考Linux中实现的完全公平调度算法
- 编写nice系统调用控制差别进程的分配时间片权重
增量式sleep，通过维护sleep队列中的等待时间增量实现O(1)弹出，插入为O(n)的sleep实现
编写测试步调：
- 创建多个进程，设置每个进程的nice值，观察调度的变化。
- 增加每个进程的统计信息，包括进程的nice值、运行时间等。
- 让多个进程使用增量式sleep等待差别的时间，观察它们被唤醒的时间顺序。
- 在大规模并发的环境下运行步调，检查CFS调度和增量式sleep的性能表现。

二、项目需求及分析

CFS调度策略

CFS（Completely 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 1
struct 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标志位设置为false，表示当前进程不在CFS树中。
    
    调用cfs_remove_process函数从CFS树中移除当前进程。
    
    调用cfs_node_init函数初始化cfs_list，该函数将进程p与CFS节点关联，并初始化其优先级为0。
    
    如果进程的状态为READY，阐明该进程可以被调度，实行以下操作：
    
    调用cfs_insert函数将cfs_list插入CFS树中。
    
    调用set_nice函数设置该进程的nice值为-5。
    
    增加cfs_cnt计数。
    
    将in_cfs标志位设置为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;
else
rb_parent(old)->rb_right = node;
} else
root->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;
else
parent->rb_right = child;
}
else
root->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)
node=node->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)
node=node->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;
      else
         return 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);
// 更新节点的 vruntime
node->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_table+NR_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_table+NR_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");
}

// 测试update
print_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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4