linux内核实现-process scheduletasking schedule base principles 调度的基本原理Linux Schedule Algorithm 调度算法Preempt 抢占 & Context switch 上下文切换

tasking schedule base principles 调度的基本原理

kernel 任务调度的对象是 thread

调度策略决定何时让什么进程运行。

疑问：多线程的程序如何调度的？

1.Multitasking

 多任务操作系统：同时并发的交互执行多个进程的操作系统

 多任务操作系统能使多个进程处于阻塞或者睡眠状态：尽管位于内存，但不被投入执行；利用内核阻塞自己，直到某一时间发生。

相关的名词：

cooperative multitasking：除非进程主动停止（exit 或者yeilding），否则它会一直执行

preemptive multitasking：由调度程序来决定什么时候停止一个进程，以便其他进程能获得执行的机会

timeslice:分配给可运行进程的处理器时间段

2.进程特性

2.1 IO消耗型 CPU消耗型

这种划分也不是绝对，进程可以同时展现两种特性，例如：字处理器

进程调度的策略就是在两个矛盾中找到平衡：相应速度&（利用率）吞吐量

进程的特性

IO消耗型	CPU消耗型
大部分时间用来等待或提交IO请求（阻塞）	大部分时间代码执行
GUI等用户交互	MATLAB 视频编解码等
最快的响应	不应该经常让ta运行（响应速度） 降低调度频率 延长运行时间（吞吐量考虑） 不情愿有这样的进程，一旦有，就保证它运行赶紧执行完（自理解）

3.Priority 优先级

1.nice值，nice[-20,19]越大优先级越低，获得的时间片比例越少；ps中NI列

2.实时优先级：RTpriority[0,99]越大优先级越高；ps中RTPRO列"-"表示不是实时进程

4.timeslice 时间片

时间片的划分考虑的方面：

1. 进程切换上下文消耗的处理器时间：最短时间片
2. 时间片过长，响应速度慢；时间片过短，利用率不高：因此采用动态时间片机制

linux中的 CFS调度，使用nice作为权值调整进程使用CPU的时间比；

linux中进程进入可运行、态，它就被准许运行，程序是否投入运行，由优先级和是否有时间片绝对的；抢占=['、的时机取决于新的可运行程序消耗了多少处理器时间比：消耗的使用比比当前进程小，则新进程立即投入运行（抢占），否则推迟运行。（这是Shortest Job First ？）

5.调度活动

 以 "运行文本编辑器和视频编解码程序两个进行的系统" 为例，说明调度活动。

进程说明

文本编辑器	视频编解码程序
1.分配更多的处理器时间 2.被唤醒时抢占视频编解码程序	尽快的完成任务

linux系统，分配给两个程序给定的处理器使用比：

场景一：两者nice值相同，使用比为1:1，文本编辑器有更多的时间等待用户，（等待时阻塞(休眠)让出处理器时间），视频编解码程序cpu使用时间相对的会高于50%。

疑问

linux CFS调度的具体表述是什么？

实时优先级与nice的关系，级具体使用？

Linux Schedule Algorithm 调度算法

1.常用的调度算法

1. Priority：
2. Round robin时间片轮询：
3. FCFS:First Come First Service
4. Shortest Job First:
5. multi-Level feedback queue:

详细的查看博客：空缺。

2.Scheduler Classes 调度器类

linux调度器是以模块的方式提供的，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，它会按照优先级顺序遍历调度器类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的程序。

CFS是一个针对普通进程（SCHED_NORMAL或SCHED_OTHER）的调度类。

3.UNIX 中的进程调度分析

查看书中相关章节。

4.Completely Fair Scheduler 完全公平调度算法

理想的处理器模型如下：

1. 每个进程可以获得1/n的处理器时间（n:处理器个数）；
2. 可以调度给他们无限小的调度时间:时间片很小。

CFS的做法：

1. 运行每个进程运行一段时间，循环轮转，选择运行最少的进程作为下一个运行进程。
2. CFS在所有可运行进程总数基础上，计算出进程应该运行多久；
3. nice值作为获得CPU的权重；
4. 每个进程按照时间片的权重来运行；
5. 引入时间片“最小颗粒”机制：最短时间线保证 时间片>切换消耗

不是很明白，后期再补！！！

5.linux 调度的实现

5.1时间记账

5.2进程选择

rbtree 选择vruntime最少的进程。

5.3 调度器入口

schedule()函数

5.4 睡眠与唤醒

进程在 等待队列 与 执行队列 之间切换。

5.5 实时调度策略

1. 实时调度策略，不被CFS管理，被实时调度管理器管理；
2. 实时调度策略。采用静态优先级，高优先级的先执行，低优先级的不可能抢占高优先级的进程；
3. 实时调度的进程，将高于CFS管理的进程被调度。

实时优先级同等级的进程-两种调度模式：

1. SCHED_FIFO:同等级的按照顺序依次执行
2. SCHED_RR:同等级的采用时间片轮询

5.6 调度相关的系统调用

nice，sched_*,相关的后续补充

1. sched_setaffinity():设置CPU的掩码位，进程可以指定CPU核，对应与cpus_allows成员；
2. sched_getaffinity():同sched_setaffinity；
3. sched_yeild(): 显示的让出CPU，然后进程被放在优先级队列的最后，保证一段时间内不被调用。

Preempt 抢占 & Context switch 上下文切换

相关函数：

1. swith_mm()函数：把虚拟内存从上一个进程映射到下一个进程；
2. switch_to()函数：从上一个处理器状态切换到下一个处理器状态；
3. schedule_tick：设置进程中need_resched标志

用户抢占的发生：

1. 从系统调用返回用户空间时（内核返回用户空间时）：
2. 从中断处理程序返回用户空间时。

内核抢占：

   只要没有加锁的进程就可以被抢占（加锁时，preempt_count++，去锁时preempt_count--；调度通过此标志来区分进程被加锁了）。

   内核可以显示的调用schedule()，来进行重新调度，此时进程可以被抢占。

总结下来，内核抢占发送在：

1. 中断处理程序正在执行，且返回内核空间之前（不是很明白）；
2. 代码再次具有可抢占性的时候(没锁了)；
3. 内核任务显式调用schedule()；
4. 内核有任务阻塞。