Linux调度算法代码解析 (linux调度算法代码)
在操作系统中，调度算法是非常重要的一部分。调度算法的目的是在多个进程之间分配CPU使用权，使其能够高效、公平地利用CPU资源。Linux系统中采用了多种调度算法，其中最常用的是CFS（Completely Fr Scheduler，完全公平调度器）算法。本文将对Linux的调度算法进行代码解析，帮助读者更好地理解这一重要的系统组成部分。
一、调度算法的原理和特点
调度算法的主要目的是通过调度器来平衡各种进程之间的CPU的使用，从而使得这些进程在一个公平的环境下进行。为达到这个目的，Linux采用了CFS调度算法。CFS调度算法采用了一种新的方法，通过对进程的虚拟运行时间进行跟踪，来判断哪个进程应该获得CPU使用权。
CFS的特点是完全公平、完全可公平共享。每个进程都有相应的虚拟运行时间，调度器会根据进程的虚拟运行时间来进行调度，以保证每个进程都能够得到相应的使用CPU的机会。此外，CFS还采用了一种称为“红黑树”的数据结构，以便能够高效地维护运行队列和完全公平分配CPU资源。
二、CFS算法的实现
CFS算法的实现主要是通过sched_fr.c文件。该文件定义了多个结构体，包含了CFS执行所需的各种数据结构及功能函数。下面对其中比较重要的 结构体进行简单介绍：
1. sched_entity结构体
sched_entity是CFS调度器中的基本数据类型之一，它保存了单个进程的调度信息。其中，vruntime字段表示该进程的虚拟运行时间，以纳秒为单位。vruntime的值越小，进程的优先级就越高。
2. sched_class结构体
sched_class结构体是一个调度策略的主要模块。它包含了一些钩子函数，通过这些函数来控制进程的调度。主要有enqueue_task和dequeue_task两个函数，用于将指定进程加入或移出调度器。
3. cfs_rq结构体
cfs_rq是一个运行队列结构体，被用来维护所有CFS进程的调度状态。在cfs_rq结构体中，每一个vruntime值最小的sched_entity结构体会获得CPU使用权。
除了上述结构体之外，sched_fr.c文件还包含了多个重要的函数，比如下面两个函数：
1. __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
用于将一个进程加入到运行队列中，并将该进程的vruntime加到队列总时间上。
2. __Dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int b)
用于将一个进程从运行队列中取出，并更新队列总时间。
三、CFS算法的优劣势分析
1. 优势
CFS的主要优点是完全公平和完全可公平共享。这意味着，对于同样的CPU时间限制，每个进程都有相应的时间份额。这使得所有进程获得了公平的CPU使用机会。此外，CFS还采用了一种红黑树数据结构，以便能够高效地维护运行队列和完全公平分配CPU资源。
2. 劣势
CFS的主要问题是对于CPU密集的多核应用程序效率不高。当多个CPU密集型进程竞争时，CFS会将CPU资源分配给每个进程，这导致了CPU利用率下降。此外，CFS适用于公平调度，但并不适合实时调度。在实时操作系统中，需要更快的调度时间和更精确的调度算法。
四、
本文对Linux的调度算法进行了代码解析，主要针对了CFS算法。CFS算法采用了虚拟运行时间来跟踪进程，以保证更高优先级的进程能获得CPU使用权。此外，CFS还采用了红黑树等数据结构，以便能够高效地维护运行队列和完全公平分配CPU资源。
虽然CFS算法在公平性方面有很大的优势，但对于CPU密集型任务来说，效率过低。因此，在Linux系统调度算法的选择上，需要根据具体情况来选择合适的算法。
相关问题拓展阅读：
请教linux下用户态进程调度问题
在进行Linux系统操作的时候，有时候会遇到一次用户态进程死循环，即系统反应迟钝、进程挂死等问题，那么遇到这些问题又该如何解决呢？下面小编就给大家介绍下一次用户态进程死循环的问题该如何处瞎颤理。
Linux下如何处理一次用户态进程死循环问题
1、问题现象
业务进程（用户态多线程程序）挂死，操作系统反应迟钝，系统日志没有任何异常。从进程的内核态堆栈看，看似所有线程都卡在了内核态的如下堆栈流程中：
［root@vmc116 ~］# cat /proc/27007/task/11825/stack
［《ffffffff8100baf6》］ retint_careful+0x14/0x32
［《ffffffffffffffff》］ 0xffffffffffffffff
2、喊兄问题分析
1）内核堆栈分析
从内核堆栈看，所有进程都阻塞在 retint_careful上，这个是中断返回过程中的流程，代码（汇编）如下：
entry_64.S
代码如下：
ret_from_intr：
DISABLE_INTERRUPTS（CLBR_NONE）
TRACE_IRQS_OFF
decl PER_CPU_VAR（irq_count）
/* Restore saved previous stack */
popq %rsi
CFI_DEF_CFA rsi，SS+8-RBP /* reg/off reset after def_cfa_expr */
leaq ARGOFFSET-RBP（%rsi）， %rsp
CFI_DEF_CFA_REGISTER rsp
CFI_ADJUST_CFA_OFFSET RBP-ARGOFFSET
。。。
retint_careful：
CFI_RESTORE_STATE
bt $TIF_NEED_RESCHED，%edx
jnc retint_signal
TRACE_IRQS_ON
ENABLE_INTERRUPTS（CLBR_NONE）
pushq_cfi %rdi
磨渗败 SCHEDULE_USER
popq_cfi %rdi
GET_THREAD_INFO（%rcx）
DISABLE_INTERRUPTS（CLBR_NONE）
TRACE_IRQS_OFF
jmp retint_check
这其实是用户态进程在用户态被中断打断后，从中断返回的流程，结合retint_careful+0x14/0x32，进行反汇编，可以确认阻塞的点其实就在
SCHEDULE_USER
这其实就是调用schedule（）进行调度，也就是说当进程走到中断返回的流程中时，发现需要调度（设置了TIF_NEED_RESCHED），于是在这里发生了调度。
有一个疑问：为什么在堆栈中看不到schedule（）这一级的栈帧呢？
因为这里是汇编直接调用的，没有进行相关栈帧压栈和上下文保存操作。
2）进行状态信息分析
从top命令结果看，相关线程实际一直处于R状态，CPU几乎完全耗尽，而且绝大部分都消耗在用户态：
［root@vmc116 ~］# top
top – 09:42:23 up 16 days， 2:21， 23 users， load average： 84.08， 84.30， 83.62
Tasks： 1037 total， 85 running， 952 sleeping， 0 stopped， 0 zombie
Cpu（s）： 97.6%us， 2.2%sy， 0.2%ni， 0.0%id， 0.0%wa， 0.0%hi， 0.0%si， 0.0%st
Mem：k total，k used，k free，k buffers
Swap：k total， 38644k used，k free，k cached
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
rootm 163m 14m R 10.2 0.5 321:06.17 z_itask_templat
rootm 163m 14m R 10.2 0.5 296:23.37 z_itask_templat
rootm 163m 14m R 10.2 0.5 337:57.26 z_itask_templat
rootm 163m 14m R 10.2 0.5 327:31.93 z_itask_templat
rootm 163m 14m R 10.2 0.5 306:49.44 z_itask_templat
rootm 163m 14m R 10.2 0.5 310:47.41 z_itask_templat
rootm 163m 14m R 10.2 0.5 283:03.37 z_itask_templat
rootm 163m 14m R 10.2 0.5 283:49.67 z_itask_templat
rootm 163m 14m R 10.2 0.5 261:24.46 z_itask_templat
rootm 163m 14m R 10.2 0.5 150:24.53 z_itask_templat
rootm 163m 14m R 10.2 0.5 100:26.77 z_itask_templat
rootm 163m 14m R 9.9 0.5 337:18.77 z_itask_templat
rootm 163m 14m R 9.9 0.5 314:24.17 z_itask_templat
rootm 163m 14m R 9.9 0.5 336:32.78 z_itask_templat
rootm 163m 14m R 9.9 0.5 338:55.08 z_itask_templat
rootm 163m 14m R 9.9 0.5 306:46.08 z_itask_templat
rootm 163m 14m R 9.9 0.5 316:49.51 z_itask_templat
。。。
3）进程调度信息
从相关线程的调度信息看：
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
［root@vmc116 ~］# cat /proc/27007/task/11825/schedstat
发现相关线程的调度统计一直在增加，说明相关线程一直是在被调度运行的，结合其状态也一直是R，推测很可能在用户态发生了死循环（或者非睡眠死锁）。
这里又有问题：为什么从top看每个线程的CPU占用率只有10%左右，而不是通常看到的死循环进程导致的100%的占用率？
因为线程数很多，而且优先级都一样，根据CFS调度算法，会平均分配时间片，不会让其中一个线程独占CPU。结果为多个线程间轮流调度，消耗掉了所有的cpu。。
另一个问题：为什么这种情况下，内核没有检测到softlockup？
因为业务进程的优先级不高，不会影响watchdog内核线程（更高优先级的实时线程）的调度，所以不会产生softlockup的情况。
再一个问题：为什么每次查看线程堆栈时，总是阻塞在retint_careful，而不是其它地方？
因为这里（中断返回的时候）正是调度的时机点，在其它时间点不能发生调度（不考虑其它情况~），而我们查看线程堆栈的行为，也必须依赖于进程调度，所以我们每次查看堆栈时，正是查看堆栈的进程（cat命令）得到调度的时候，这时正是中断返回的时候，所以正好看到的阻塞点为retint_careful。
4）用户态分析
从上面的分析看，推测应该是用户态发生了死锁。
用户态确认方法：
部署debug信息，然后gdb attach相关进程，确认堆栈，并结合代码逻辑分析。
最终确认该问题确为用户态进程中产生了死循环。
如何修改linux默认io调度算法
目余败伏前 Linux 上有如下几种 I/O 调度算法：
1 noop – 通常竖携用于内存存储的设备。
2 cfq – 完全公平调度器。进程平均使用枯游IO带宽。
3 Deadline – 针对延迟的调度器，每一个 I/O，都有一个最晚执行时间。
4 Anticipatory – 启发式调度，类似 Deadline 算法，但是引入预测机制提高性能。
关于linux调度算法代码的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
