操作系统原理：实验验证 Linux 内核的 CFS 算法

本文主要是介绍操作系统原理：实验验证 Linux 内核的 CFS 算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CFS——一个“公平”的“骗局”

全称为 Completely fair scheduler（完全公平调度算法）。顾名思义，这个算法就是为了实现进程之间调度的“完全公平”。但是这个“公平”仅仅只是Linux对进程的一个虚假的“骗局”，是虚拟运行时间（vruntime）的相同，然而真实运行时间（runtime）是根据优先级权重而分配的。

优先级 n 的权重计算公式如下：
$weight_{n}=1024 \times 1.25^{-n}$

优先级从 -20 到 20 的权重见下表：
优先级权重
进程真实运行时间（runtime）和虚拟运行时间（vruntime）的计算公式：
$\times (\frac{weight}{\sum weight} )$
$\times (\frac{weight_{0}}{\sum weight} )$
对于上面的两个公式，其中weight即为表中的-20~20的优先级对应的40个权重。至于runtime和vruntime的比值，由上面的两个公式可以得出应该与优先级所对应权重比值相等。那么在下面的实验中，我们就来验证一下这个结论。

设置进程优先级

首先使用CPU_ZERO(&curr_set)语句将CPU中所有的核设定清空，之后使用CPU_SET(0, &curr_set)语句将进程绑定到0号核。函数sched_getaffinity(pid_t pid, unsigned int cpusetsize, cpu_set_t *mask)会获得pid所指向的进程的CPU位掩码，并将该掩码返回到第三个参数mask所指向的结构中，即获得指定pid当前可以运行在哪些CPU上。如果pid的值为0，那么表示的是当前进程。

之后使用fork()语句创建子进程，因为子进程会继承父进程的处理器亲和性的绑定，所以在子进程中不需要再绑定处理器。此时子进程和父进程都绑定到了0号核上，去竞争CPU使用权。

在子进程和父进程中分别打印各自的进程编号，在子进程中打印从父进程中继承来的Nice值（进程优先级），之后使用setpriority(PRIO_PROCESS, getpid(), 10);语句将子进程的Nice值设置成10，并使用getpriority(PRIO_PROCESS, getpid())获取当前进程的优先级。最后让两个进程进入死循环，等待CPU运行时间的获取。

#include <stdio.h>
#ifndef __USE_GNU
#define __USE_GNU
#endif // !__USE_GNU
#include <unistd.h>
#include <sched.h>
#include <sys/resource.h>int main(int argc, char* argv[]) {cpu_set_t curr_set; CPU_ZERO(&curr_set);	//清空CPU设置CPU_SET(0, &curr_set);	//设置0号CPUsched_setaffinity(0, sizeof(curr_set), &curr_set);pid_t pid = fork();		//创建子进程if (pid == 0) {printf("The child pid: %d\n", getpid());	//显示子进程pid//sleep(3);//显示当前的进程优先级printf("\nParent and child's old priority: %d\n", getpriority(PRIO_PROCESS, getpid()));//将子进程的优先级改成10，并打印setpriority(PRIO_PROCESS, getpid(), 10);printf("Child's new priority: %d\n", getpriority(PRIO_PROCESS, getpid()));while (1);}else{printf("The parent pid: %d\n", getpid());	//显示父进程pidwhile (1);}
}

获取进程运行时间

首先使用命令行向Linux内核传参的方式获取两个进程号参数pid1和pid2，使用module_param(pid1, int, S_IRUGO);语句将其注册为int类型的“只读”参数。

遍历进程列表，找到两个进程，并打印他们的真实运行时间（runtime）和虚拟运行时间（vruntime）。

#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/sched/signal.h>int pid1;
int pid2;
module_param(pid1, int, S_IRUGO);
module_param(pid2, int, S_IRUGO);int module_load(void){struct task_struct* p;for_each_process(p) {if (p->pid == pid1 || p->pid == pid2)//打印进程的pid，运行时间，虚拟运行时间printk("%d  runtime:%llu \t vruntime:%lld\n", p->pid, p->se.sum_exec_runtime, p->se.vruntime);}return 0;
}
void module_rm(void){printk(KERN_INFO "========= Module removed! =========\n ");
}
module_init(module_load);
module_exit(module_rm);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("The runtime of progress.");
MODULE_AUTHOR("Song XJ");