⾮抢占式优先调度算法例题_Linux进程调度
linux进程调度
Completely Fair Schedule)，基于 ⾯向基础，深⼊学习linux进程调度的相关知识，源码阅读，主要介绍 linux公平调度
linux公平调度 CFS ( Completely Fair Schedule linux版本2.6.34。
看源码所感：“⽽世之奇伟、瑰怪，⾮常之观，常在于险远，⽽⼈之所罕⾄焉，故⾮有志者不能⾄也。”
概述
调度程序即(scheduler)决定了多个程序运⾏策略，调度程序的最⼤原则在于能够最⼤限度的利⽤计算资源。
多任务系统可以划分为两类：⾮抢占式多任务(cooperative multitasking), 抢占式多任务(preemptive mulittasking).
Linux2.6.34内核中调度器的设计是模块化的，这样做的好处是允许不同可以有针对性的选择不同调度算法，其中最基本的调度算法为基于time sharing)的技术。
分时(time sharing
架构
整体架构如下，即调度策略是模块化设计的，调度器根据不同的进程依次遍历不同的调度策略，到进程对应的调度策略，调度的结果即为选出⼀个可运⾏的进程指针，并将其加⼊到进程可运⾏队列中。
CFS完全公平调度： CFS的出发点基于⼀个简单的理念：即所有进程实际占⽤处理器CPU的时间应为⼀致，⽬的是确保每个进程公平的处理器使⽤⽐，即最⼤的利⽤了计算资源。
FIFO先⼊先出队列：不基于时间⽚调度，处于可运⾏状态的SCHED_FIFO级别的进程⽐SCHED_NORMAL有更⾼优先级得到调度，⼀旦SCHED_FIFO级别的进程处于可执⾏的状态，它就会⼀致运⾏，直到进程阻塞或者主动释放。
RR(Round-Robin)：SCHED_RR级别的进程在耗尽事先分配的时间⽚之后就不会继续执⾏。即可以理解将RR调度理解为带有时间⽚的SCHED_FIFO。
FIFO和RR调度算法都为静态优先级。内核不为实时进程计算动态优先级，保证了优先级别⾼的实时进程总能抢优先级⽐它低的进程。Linux进程调度的实现
主要针对CFS调度
实现部分主要4个点：时间记账，进程选择，调度器⼊⼝，睡眠和唤醒
整体涉及的数据结构图如下：
task_struct：为进程任务基础数据结构，存储着进程相关信息
sched_entity：存储着进程调度相关的信息，其中run_node为可执⾏红⿊树的节点
ofs_rq: 存储着rb_root，红⿊树的根节点task_timelineslab: linux内核对于对象内存的⼀种⾼效的管理机制, 可以有效的降低内存碎⽚。task_struct这类数据结构由slab分配并管理
时间记账
所有的调度器都必须对进程的运⾏时间做记账。CFS不再有时间⽚的概念，维护了每个进程运⾏的时间记账，因为每个进程只在公平分配给它的处理器时间内运⾏。关键数据结构如下：
vruntime: 虚拟运⾏时间是在所有可运⾏基础的总数上计算出⼀个进程应该运⾏多久，计算时相应的nice值在CFS被作为进程获得处理器运⾏⽐的权重：越⾼的nice（越低优先级）值，获得更低的处理器权重，更低的nice值获得更⾼的处理器使⽤权重。
个⼈理解：CFS的vruntime += 处理器运⾏时间 * nice对应的权重
// sched.h
struct sched_entity {
struct load_weight load;  /* for load-balancing ⽤来做负载均衡 */
struct rb_node  run_node;  /* 红⿊树运⾏节点 */
struct list_head group_node;
unsigned int  on_rq;      /* 表明是否在可运⾏的队列中 */
u64  exec_start;
u64  sum_exec_runtime;
u64  vruntime;          /* 虚拟运⾏时间，通常是加权的虚拟运⾏时间 */
u64  prev_sum_exec_runtime;
u64  last_wakeup;
u64  avg_overlap;
u64  nr_migrations;
u64  start_runtime;
linux下的sleep函数
u64  avg_wakeup;
}
进程选择
进程选择是CFS调度算法的最重要的模块，当CFS调度器选择下⼀个要进⾏调度的进程时，就会选择具有最⼩vruntime的任务。涉及到获取最⼩值，以及有序数据结构，在各种场景下都很适⽤的红⿊树就发挥了其作⽤。即⽤红⿊树维护以vruntime为排序条件，存储着任务的运⾏情况。
进程的维护都在红⿊树上进⾏相关操作：
1. 选择下⼀个任务
执⾏__pick_next_entity函数即获取了红⿊树最左的节点（最⼩值）。
// kernel/sched_fair.c
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) {
// 获取缓存的最左节点
struct rb_node *left = cfs_rq->rb_leftmost;
if (!left)
return NULL;
// 遍历获取最左节点，如果NULL则说明RB树中没有任何节点，则选择idle任务运⾏
return rb_entry(left, struct sched_entity, run_node);
}
2. 向红⿊树中加⼊进程
这⼀步骤发⽣在进程变成可运⾏态，或者通过fork系统调⽤第⼀次创建进程时。
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/*
* 通过调⽤update_curr()，在更新min_vruntime之前先更新规范化的vruntime
*/
if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
se->vruntime += cfs_rq->min_vruntime;
/*
* 更新“当前任务”运⾏时统计数据
*/
update_curr(cfs_rq);
// 将on_rq置为1，nr_running++ (可运⾏进程数量)
account_entity_enqueue(cfs_rq, se);
if (flags & ENQUEUE_WAKEUP) {
place_entity(cfs_rq, se, 0);
enqueue_sleeper(cfs_rq, se);
}
update_stats_enqueue(cfs_rq, se);
check_spread(cfs_rq, se);
if (se != cfs_rq->curr)
// 将se的红⿊树节点，插⼊到红⿊树中，并维护和更新最左节点
__enqueue_entity(cfs_rq, se);
}
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se){
struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
struct rb_node *parent = NULL;
struct sched_entity *entry;
s64 key = entity_key(cfs_rq, se);
int leftmost = 1;
/*
/*
* Find the right place in the rbtree:
*/
while (*link) {
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
/*
* We dont care about collisions. Nodes with
* the same key stay together.
*/
// 查插⼊的合适的节点位置，⼆叉搜索树的性质
if (key < entity_key(cfs_rq, entry)) {
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = 0;
}
}
/
*
* Maintain a cache of leftmost tree entries (it is frequently
* used): 维护和更新最左⼦节点
*/
if (leftmost)
cfs_rq->rb_leftmost = &se->run_node;
// 连接红⿊树节点
rb_link_node(&se->run_node, parent, link);
// 对红⿊树进⾏旋转和着⾊
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}
3. 从红⿊树中删除进程
这⼀步操作发⽣在进程阻塞，即进程变成不可运⾏状态或者当进程终⽌时。
static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep){
/*
* Update run-time statistics of the 'current'.
* 更新当前任务运⾏的虚拟运⾏时间
*/
update_curr(cfs_rq);
update_stats_dequeue(cfs_rq, se);
clear_buddies(cfs_rq, se);
if (se != cfs_rq->curr)
// 辅助函数，即从红⿊树中删除节点
__dequeue_entity(cfs_rq, se);
// 进⾏⼀次记账account
account_entity_dequeue(cfs_rq, se);
// 更新最⼩的虚拟运⾏时间，以备下⼀次的调度
update_min_vruntime(cfs_rq);
/*
* Normalize the entity after updating the min_vruntime because the
* update can refer to the ->curr item and we need to reflect this
* movement in our normalized position.
*/
if (!sleep)
se->vruntime -= cfs_rq->min_vruntime;
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se){
if (cfs_rq->rb_leftmost == &se->run_node) {
// 维护最左⼦节点
struct rb_node *next_node;
next_node = rb_next(&se->run_node);
cfs_rq->rb_leftmost = next_node;
}
/
/ 从红⿊树中删除节点
rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}
调度器⼊⼝
进程调度器的⼊⼝函数为schedule()，总体流程即为选择合适的调度策略选出下⼀个需要被调度的进程任务，然后进⾏⼀次上下⽂切换，将进程置为运⾏态。
/*
* schedule() is the main scheduler function.
*/
asmlinkage void __sched schedule(void){
// asmlinkage 为系统调⽤函数关键字的定义
struct task_struct *prev, *next;
// prev 和 next标识之前调度的进程任务和当前要调度的进程任务
unsigned long *switch_count;
struct rq *rq;
int cpu;
need_resched:
// 需要重新调度标签
preempt_disable();
cpu = smp_processor_id();
// 获取cpu的可运⾏任务队列
rq = cpu_rq(cpu);
rcu_sched_qs(cpu);
prev = rq->curr;
switch_count = &prev->nivcsw;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。