彩世界开奖app官网-彩世界平台官方网址(彩票平台)
做最好的网站
来自 彩世界开奖app官网 2019-12-06 21:46 的文章
当前位置: 彩世界开奖app官网 > 彩世界开奖app官网 > 正文

[校招面试]CPU调度系列二彩世界开奖app官网

    1.4.1五种互斥状态:      

      state域能够取5个互为排斥的值(简单来说就是这五个值任意两个不能一起使用,只能单独使用):

状态 描述
TASK_RUNNING 表示进程要么正在执行,要么正要准备执行(已经就绪),正在等待cpu时间片的调度
TASK_INTERRUPTIBLE 进程因为等待一些条件而被挂起(阻塞)而所处的状态。这些条件主要包括:硬中断、资源、一些信号……,一旦等待的条件成立,进程就会从该状态(阻塞)迅速转化成为就绪状态TASK_RUNNING
TASK_UNINTERRUPTIBLE 意义与TASK_INTERRUPTIBLE类似,除了不能通过接受一个信号来唤醒以外,对于处于TASK_UNINTERRUPIBLE状态的进程,哪怕我们传递一个信号或者有一个外部中断都不能唤醒他们。只有它所等待的资源可用的时候,他才会被唤醒。这个标志很少用,但是并不代表没有任何用处,其实他的作用非常大,特别是对于驱动刺探相关的硬件过程很重要,这个刺探过程不能被一些其他的东西给中断,否则就会让进城进入不可预测的状态
TASK_STOPPED 进程被停止执行,当进程接收到SIGSTOP、SIGTTIN、SIGTSTP或者SIGTTOU信号之后就会进入该状态
TASK_TRACED 表示进程被debugger等进程监视,进程执行被调试程序所停止,当一个进程被另外的进程所监视,每一个信号都会让进城进入该状态

重要的 CFS 数据结构

对于每个 CPU,CFS 使用按时间排序的红黑(red-black)树。

红黑树是一种自平衡二叉搜索树,这种数据结构可用于实现关联数组。对于每个运行中的进程,在红黑树上都有一个节点。红黑树上位于最左侧的进程表示将进行下一次调度的进程。红黑树比较复杂,但它的操作具有良好的最差情况(worst-case)运行时,并且在实际操作中非常高效:它可以在 O(log n) 时间内搜索、插入和删除 ,其中 n 表示树元素的数量。叶节点意义不大并且不包含数据。为节省内存,有时使用单个哨兵(sentinel)节点执行所有叶节点的角色。内部节点到叶节点的所有引用都指向哨兵节点。

该树方法能够良好运行的原因在于:

1.红黑树可以始终保持平衡。

2.由于红黑树是二叉树,查找操作的时间复杂度为对数。但是,除了最左侧查找以外,很难执行其他查找,并且最左侧的节点指针始终被缓存。

3.对于大多数操作,红黑树的执行时间为 O(log n),而以前的调度程序通过具有固定优先级的优先级数组使用 O(1)O(log n) 行为具有可测量的延迟,但是对于较大的任务数无关紧要。Molnar 在尝试这种树方法时,首先对这一点进行了测试。

4.红黑树可通过内部存储实现 — 即不需要使用外部分配即可对数据结构进行维护。

让我们了解一下实现这种新调度程序的一些关键数据结构。

4.参考链接:

  Linux进程管理与调度——CSDN

  Linux source

优先级和CFS

CFS 不直接使用优先级而是将其用作允许任务执行的时间的衰减系数。 低优先级任务具有更高的衰减系数,而高优先级任务具有较低的衰减系数。 这意味着与高优先级任务相比,低优先级任务允许任务执行的时间消耗得更快。 这是一个绝妙的解决方案,可以避免维护按优先级调度的运行队列。

  2.1什么是调度器?    

    一台个人电脑,最直观的资源便是你的硬盘、磁盘、内存等等,但其实CPU也是一个资源,每个程序在跑的时候都需要占用CPU一定时间。因此,如何让每个程序合理、公平地跑一定的时间,是一个很重要的问题,需要设计一个专门的地方去分配,这就是调度器。调度器的一个重要目标是有效地分配 CPU 时间片,同时提供很好的用户体验。调度器还需要面对一些互相冲突的目标,例如既要为关键实时任务最小化响应时间, 又要最大限度地提高 CPU 的总体利用率。

struct sched_class

该调度类类似于一个模块链,协助内核调度程序工作。每个调度程序模块需要实现 struct sched_class建议的一组函数。

彩世界开奖app官网 1

sched_class 结构体简介

函数功能说明:

enqueue_task:当某个任务进入可运行状态时,该函数将得到调用。它将调度实体(进程)放入红黑树中,并对 nr_running 变量加 1。

dequeue_task:当某个任务退出可运行状态时调用该函数,它将从红黑树中去掉对应的调度实体,并从 nr_running 变量中减 1。

yield_task:在 compat_yield sysctl 关闭的情况下,该函数实际上执行先出队后入队;在这种情况下,它将调度实体放在红黑树的最右端。

check_preempt_curr:该函数将检查当前运行的任务是否被抢占。在实际抢占正在运行的任务之前,CFS 调度程序模块将执行公平性测试。这将驱动唤醒式(wakeup)抢占。

pick_next_task:该函数选择接下来要运行的最合适的进程。

load_balance:每个调度程序模块实现两个函数,load_balance_start() 和load_balance_next(),使用这两个函数实现一个迭代器,在模块的 load_balance 例程中调用。内核调度程序使用这种方法实现由调度模块管理的进程的负载平衡。

set_curr_task:当任务修改其调度类或修改其任务组时,将调用这个函数。

task_tick:该函数通常调用自 time tick 函数;它可能引起进程切换。这将驱动运行时(running)抢占。

task_new:内核调度程序为调度模块提供了管理新任务启动的机会。CFS 调度模块使用它进行组调度,而用于实时任务的调度模块则不会使用这个函数。

    Linux的6种调度策略:

调度策略

描述

所在**调度器类**

SCHED_NORMAL

(也叫SCHED_OTHER)用于普通进程,通过CFS调度器实现。SCHED_BATCH用于非交互的处理器消耗型进程。SCHED_IDLE是在系统负载很低时使用

CFS

SCHED_BATCH

SCHED_NORMAL普通进程策略的分化版本。采用分时策略,根据动态优先级(可用nice()API设置),分配CPU运算资源。注意:这类进程比上述两类实时进程优先级低,换言之,在有实时进程存在时,实时进程优先调度。但针对吞吐量优化, 除了不能抢占外与常规任务一样,允许任务运行更长时间,更好地使用高速缓存,适合于成批处理的工作

CFS

SCHED_IDLE

优先级最低,在系统空闲时才跑这类进程(如利用闲散计算机资源跑地外文明搜索,蛋白质结构分析等任务,是此调度策略的适用者)

CFS-IDLE

SCHED_FIFO

先入先出调度算法(实时调度策略),相同优先级的任务先到先服务,高优先级的任务可以抢占低优先级的任务

RT

SCHED_RR

轮流调度算法(实时调度策略),后者提供 Roound-Robin 语义,采用时间片,相同优先级的任务当用完时间片会被放到队列尾部,以保证公平性,同样,高优先级的任务可以抢占低优先级的任务。不同要求的实时任务可以根据需要用sched_setscheduler() API设置策略

RT

SCHED_DEADLINE

新支持的实时进程调度策略,针对突发型计算,且对延迟和完成时间高度敏感的任务适用。基于Earliest Deadline First (EDF) 调度算法

DL

CFS初探

CFS 调度程序使用安抚(appeasement)策略确保公平性。当某个任务进入运行队列后,将记录当前时间,当某个进程等待 CPU 时,将对这个进程的 wait_runtime 值加一个数,这个数取决于运行队列当前的进程数。当执行这些计算时,也将考虑不同任务的优先级值。 将这个任务调度到 CPU 后,它的 wait_runtime 值开始递减,当这个值递减到其他任务成为红黑树的最左侧任务时,当前任务将被抢占。通过这种方式,CFS 努力实现一种理想 状态,即 wait_runtime 值为 0!

CFS 维护任务运行时(相对于运行队列级时钟,称为 fair_clock(cfs_rq->fair_clock)),它在某个实际时间的片段内运行,因此,对于单个任务可以按照理想的速度运行。

例如,如果具有 4 个可运行的任务,那么 fair_clock 将按照实际时间速度的四分之一增加。每个任务将设法跟上这个速度。这是由分时多任务处理的量子化特性决定的。也就是说,在任何一个时间段内只有一个任务可以运行;因此, 其他进程在时间上的拖欠将增大(wait_runtime)。因此,一旦某个任务进入调度,它将努力赶上它所欠下的时间(并且要比所欠时间多一点,因为在追赶时间期间,fair_clock 不会停止计时)。

粒度和延迟如何关联?

关联粒度和延迟的简单等式为: 

gran = (lat/nr) - (lat/nr/nr)

其中 gran = 粒度,

lat = 延迟,而 

nr = 运行中的任务数。

加权任务引入了优先级。假设我们有两个任务:其中一个任务占用 CPU 的时间量是另一个任务的两倍,比例为 2:1。执行数学转换后,对于权重为 0.5 的任务,时间流逝的速度是以前的两倍。我们根据 fair_clock 对树进行排队。

请注意,CFS 没有使用时间片(time slices),至少,没有优先使用。CFS 中的时间片具有可变的长度并且动态确定。

  1.2进程内核栈与thread_info(用于存储进、线程及其信息等):

1 struct task_struct {
2      ......
3  
4      /* 指向进程内核栈 */
5      void *stack;
6  
7      ......
8  };

1 union thread_union {  
2      struct thread_info thread_info; 
3      unsigned long stack[THREAD_SIZE/sizeof(long)];    /*内核态的进程堆栈*/
4 };

 1 /*线程描述符(linux4.5 x86架构)*/
 2 /*typedef unsigned int __u32*/
 3 struct thread_info {
 4     struct task_struct  *task;    /* 存储进(线)程的信息 */
 5     __u32              flags;    /* 进程标记 */
 6     __u32              status;    /* 线程状态 */
 7     __u32              cpu;        /* current CPU */
 8     mm_segment_t        addr_limit;
 9     unsigned int        sig_on_uaccess_error:1;
10     unsigned int        uaccess_err:1;    /* uaccess failed */
11 };

  

  • 进程在内核态运行时需要自己的堆栈信息, 因此linux内核为每个进程都提供了一个内核栈kernel stack;
  • 内核还需要存储每个进程的PCB信息, linux内核是支持不同体系的的, 但是不同的体系结构可能进程需要存储的信息不尽相同, 这就需要我们实现一种通用的方式, 我们将体系结构相关的部分和无关的部门进行分离;
  • linux将内核栈和thread_info融合在一起, 组成一个联合体thread_union。(下图左块)

彩世界开奖app官网 2

   由上图(左大块为"进程内核栈", 右块为"进程描述符")所示,进程的内核栈是向下增长的,也就是栈底在高位地址,栈顶在低位地址,thread_info在进程内核栈的最低处。其中可总结出:

  • esp寄存器为CPU栈指针,用来存放栈顶单元的地址。当数据写入时,esp的值减少;
  • thread_info和内核栈虽然共用了thread_union结构, 但是thread_info大小固定, 存储在联合体的开始部分, 而内核栈由高地址向低地址扩展, 当内核栈的栈顶到达thread_info的存储空间时, 则会发生栈溢出(内核中有kstack_end函数判断);
  • 系统的current指针指向了当前运行进程的thread_union(或者thread_info)的地址;

   其中在早期的Linux内核中使用struct thread_info *thread_info,而之后的新版本(2.6.22后)中用进程task_struct中的stack指针指向了进程的thread_union(或者thread_info)的地址来代替thread_info指针,因为联合体中stack和thread_info都在起始地址, 因此可以很方便的转型:

#define task_thread_info(task)  ((struct thread_info *)(task)->stack)

内核 2.6.24 中的变化

新版本中不再追赶全局时钟(fair_clock),任务之间将彼此追赶。将引入每个任务(调度实体)的时钟 vruntime(wall_time/task_weight),并且将使用近似的平均时间初始化新任务的时钟。其他重要改动将影响关键数据结构。下面展示了 struct sched_entity 中的预期变动:

彩世界开奖app官网 3

2.6.24 版本中 sched_entity 结构的预期变动

彩世界开奖app官网 4

2.6.24 版本中 cfs_rq 结构的预期变动

彩世界开奖app官网 5

2.6.24版本中新添加的 task_group 结构

每个任务都跟踪它的运行时,并根据该值对任务进行排队。这意味着运行最少的任务将位于树的最左侧。同样,通过对时间加权划分优先级。每个任务在下面的时间段内力求获得精确调度:

sched_period = (nr_running > sched_nr_latency) ? sysctl_sched_latency : ((nr_running * sysctl_sched_latency) / sched_nr_latency)

其中 sched_nr_latency = (sysctl_sched_latency / sysctl_sched_min_granularity)。这表示,当可运行任务数大于 latency_nr 时,将线性延长调度周期。sched_fair.c 中定义的 sched_slice() 是进行这些计算的位置。因此,如果每个可运行任务运行与 sched_slice() 等价的时间,那么将花费的时间为 sched_period,每个任务将运行与其权重成比例的时间量。此外,在任何时刻,CFS 都承诺超前运行 sched_period,因为最后执行调度的任务将在这个时限内再次运行。

因此,当一个新任务变为可运行状态时,对其位置有严格的要求。在所有其他任务运行之前,此任务不能运行;否则,将破坏对这些任务作出的承诺。然而,由于该任务确实进行了排队,对运行队列的额外权重将缩短其他所有任务的时间片,在 sched_priod 的末尾释放一点位置,刚好满足新任务的需求。这个新的任务就被放在这个位置。

  2.6红黑树

新的调度程序调试接口

新调度程序附带了一个非常棒的调试接口,还提供了运行时统计信息,分别在 kernel/sched_debug.c 和 kernel/sched_stats.h 中实现。要提供调度程序的运行时信息和调试信息,需要将一些文件添加到 proc pseudo 文件系统:

/proc/sched_debug:显示运行时调度程序可调优选项的当前值、CFS 统计信息和所有可用 CPU 的运行队列信息。当读取这个 proc 文件时,将调用 sched_debug_show() 函数并在 sched_debug.c 中定义。

/proc/schedstat:为所有相关的 CPU 显示特定于运行队列的统计信息以及 SMP 系统中特定于域的统计信息。kernel/sched_stats.h 中定义的 show_schedstat() 函数将处理 proc 条目中的读操作。

/proc/[PID]/sched:显示与相关调度实体有关的信息。在读取这个文件时,将调用 kernel/sched_debug.c 中定义的 proc_sched_show_task() 函数

    Linux的5种调度类:

 

调度器类

描述

对应调度策略

stop_sched_class

优先级最高的线程,会中断所有其他线程,且不会被其他任务打断作用
1.发生在cpu_stop_cpu_callback 进行cpu之间任务migration
2.HOTPLUG_CPU的情况下关闭任务

无, 不需要调度普通进程

dl_sched_class

采用EDF最早截至时间优先算法调度实时进程

SCHED_DEADLINE

rt_sched_class

采用提供 Roound-Robin算法或者FIFO算法调度实时进程
具体调度策略由进程的task_struct->policy指定

SCHED_FIFO, SCHED_RR

fair_sched_clas

采用CFS算法调度普通的非实时进程

SCHED_NORMAL, SCHED_BATCH

idle_sched_class

采用CFS算法调度idle进程, 每个cup的第一个pid=0线程:swapper,是一个静态线程。调度类属于:idel_sched_class,所以在ps里面是看不到的。一般运行在开机过程和cpu异常的时候做dump

SCHED_IDLE

    

        其所属进程的优先级顺序为:         

stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

运行时调优选项

引入了重要的 sysctls 来在运行时对调度程序进行调优(以 ns 结尾的名称以纳秒为单位):

sched_latency_ns:针对 CPU 密集型任务进行目标抢占延迟(Targeted preemption latency)。

sched_batch_wakeup_granularity_ns:针对 SCHED_BATCH 的唤醒(Wake-up)粒度。

sched_wakeup_granularity_ns:针对 SCHED_OTHER 的唤醒粒度。

sched_compat_yield:由于 CFS 进行了改动,严重依赖 sched_yield() 的行为的应用程序可以要求不同的性能,因此推荐启用 sysctls。

sched_child_runs_first:child 在 fork 之后进行调度;此为默认设置。如果设置为 0,那么先调度 parent。

sched_min_granularity_ns:针对 CPU 密集型任务执行最低级别抢占粒度。

sched_features:包含各种与调试相关的特性的信息。

sched_stat_granularity_ns:收集调度程序统计信息的粒度。

彩世界开奖app官网 6

系统中运行时参数的典型值

  2.5CFS调度器.

    CFS完全公平调度器的调度器类叫fair_sched_class,下面是linux 4.5中的数据结构:

 1 /*
 2  * All the scheduling class methods:
 3  */
 4 const struct sched_class fair_sched_class = {
 5     .next            = &idle_sched_class,
 6     .enqueue_task        = enqueue_task_fair,
 7     .dequeue_task        = dequeue_task_fair,
 8     .yield_task        = yield_task_fair,
 9     .yield_to_task        = yield_to_task_fair,
10 
11     .check_preempt_curr    = check_preempt_wakeup,
12 
13     .pick_next_task        = pick_next_task_fair,
14     .put_prev_task        = put_prev_task_fair,
15 
16 #ifdef CONFIG_SMP
17     .select_task_rq        = select_task_rq_fair,
18     .migrate_task_rq    = migrate_task_rq_fair,
19 
20     .rq_online        = rq_online_fair,
21     .rq_offline        = rq_offline_fair,
22 
23     .task_waking        = task_waking_fair,
24     .task_dead        = task_dead_fair,
25     .set_cpus_allowed    = set_cpus_allowed_common,
26 #endif
27 
28     .set_curr_task          = set_curr_task_fair,
29     .task_tick        = task_tick_fair,
30     .task_fork        = task_fork_fair,
31 
32     .prio_changed        = prio_changed_fair,
33     .switched_from        = switched_from_fair,
34     .switched_to        = switched_to_fair,
35 
36     .get_rr_interval    = get_rr_interval_fair,
37 
38     .update_curr        = update_curr_fair,
39 
40 #ifdef CONFIG_FAIR_GROUP_SCHED
41     .task_move_group    = task_move_group_fair,
42 #endif
43 };

    其中一些成员变量的含义为:

成员

描述

next

下个优先级的调度类, 让所有的调度类通过next链接在一个链表中

enqueue_task

向就绪队列中添加一个进程, 某个任务进入可运行状态时,该函数将得到调用。它将调度实体(进程)放入红黑树中,并对 nr_running 变量加 1

dequeue_task

将一个进程从就就绪队列中删除, 当某个任务退出可运行状态时调用该函数,它将从红黑树中去掉对应的调度实体,并从 nr_running 变量中减 1

yield_task

在进程想要资源放弃对处理器的控制权的时, 可使用在sched_yield系统调用, 会调用内核API yield_task完成此工作. compat_yield sysctl 关闭的情况下,该函数实际上执行先出队后入队;在这种情况下,它将调度实体放在红黑树的最右端

check_preempt_curr

该函数将检查当前运行的任务是否被抢占。在实际抢占正在运行的任务之前,CFS 调度程序模块将执行公平性测试。这将驱动唤醒式(wakeup)抢占

pick_next_task

该函数选择接下来要运行的最合适的进程

put_prev_task

用另一个进程代替当前运行的进程

set_curr_task

当任务修改其调度类或修改其任务组时,将调用这个函数

task_tick

在每次激活周期调度器时, 由周期性调度器调用, 该函数通常调用自 time tick 函数;它可能引起进程切换。这将驱动运行时(running)抢占

task_fork

内核调度程序为调度模块提供了管理新任务启动的机会, 用于建立fork系统调用和调度器之间的关联, 每次新进程建立后, 则用new_task通知调度器, CFS 调度模块使用它进行组调度,而用于实时任务的调度模块则不会使用这个函数

    CFS的就绪队列:

 1 struct cfs_rq {
 2     struct load_weight load;/*CFS队列中所有进程的总负载*/
 3     unsigned int nr_running, h_nr_running;
 4 
 5     u64 exec_clock;/**/
 6     u64 min_vruntime; /*最小虚拟运行时间*/
 7 #ifndef CONFIG_64BIT
 8     u64 min_vruntime_copy;
 9 #endif
10    /*红黑树的根root*/
11     struct rb_root tasks_timeline;
12   /*红黑树最左边的节点,也是下一个调度节点*/
13     struct rb_node *rb_leftmost;
14    
15     /*
16      * 'curr' points to currently running entity on this cfs_rq.
17      * It is set to NULL otherwise (i.e when none are currently running).
18      */
19     struct sched_entity *curr, *next, *last, *skip;
20 
21 #ifdef    CONFIG_SCHED_DEBUG
22     unsigned int nr_spread_over;
23 #endif
24 
25 #ifdef CONFIG_SMP
26     /*
27      * CFS load tracking
28      */
29     struct sched_avg avg;
30     u64 runnable_load_sum;
31     unsigned long runnable_load_avg;
32 #ifdef CONFIG_FAIR_GROUP_SCHED
33     unsigned long tg_load_avg_contrib;
34 #endif
35     atomic_long_t removed_load_avg, removed_util_avg;
36 #ifndef CONFIG_64BIT
37     u64 load_last_update_time_copy;
38 #endif
39 
40 #ifdef CONFIG_FAIR_GROUP_SCHED
41     /*
42      *   h_load = weight * f(tg)
43      *
44      * Where f(tg) is the recursive weight fraction assigned to
45      * this group.
46      */
47     unsigned long h_load;
48     u64 last_h_load_update;
49     struct sched_entity *h_load_next;
50 #endif /* CONFIG_FAIR_GROUP_SCHED */
51 #endif /* CONFIG_SMP */
52 
53 #ifdef CONFIG_FAIR_GROUP_SCHED
54     struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */
55 
56     /*
57      * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
58      * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
59      * (like users, containers etc.)
60      *
61      * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
62      * list is used during load balance.
63      */
64     int on_list;
65     struct list_head leaf_cfs_rq_list;
66     struct task_group *tg;    /* group that "owns" this runqueue */
67 
68 #ifdef CONFIG_CFS_BANDWIDTH
69     int runtime_enabled;
70     u64 runtime_expires;
71     s64 runtime_remaining;
72 
73     u64 throttled_clock, throttled_clock_task;
74     u64 throttled_clock_task_time;
75     int throttled, throttle_count;
76     struct list_head throttled_list;
77 #endif /* CONFIG_CFS_BANDWIDTH */
78 #endif /* CONFIG_FAIR_GROUP_SCHED */
79 };

    一些成员变量的含义:

成员

描述

nr_running

队列上可运行进程的数目

h_nr_running

只对进程组有效,其下所有进程组中cfs_rq的nr_running总和

load

就绪队列上可运行进程的累计负荷权重(总负载)

min_vruntime

跟踪记录队列上所有进程的最小虚拟运行时间. 这个值是实现与就绪队列相关的虚拟时钟的基础。当更新当前运行任务的累计运行时间时或者当任务从队列删除去,如任务睡眠或退出,这时候会查看剩下的任务的vruntime是否大于min_vruntime,如果是则更新该值。

tasks_timeline

用于在按时间排序的红黑树中管理所有进程(红黑树的root)

rb_leftmost

总是设置为指向红黑树最左边的节点, 即需要被调度的进程. 该值其实可以可以通过病例红黑树获得, 但是将这个值存储下来可以减少搜索红黑树花费的平均时间

curr

当前正在运行的sched_entity(对于组虽然它不会在cpu上运行,但是当它的下层有一个task在cpu上运行,那么它所在的cfs_rq就把它当做是该cfs_rq上当前正在运行的sched_entity

next

表示有些进程急需运行,即使不遵从CFS调度也必须运行它,调度时会检查是否next需要调度,有就调度next

skip

略过进程(不会选择skip指定的进程调度)

完全公平调度CFS

CFS(Completely Fair Scheduler)试图按照对 CPU 时间的 “最大需求(gravest need)” 运行任务;这有助于确保每个进程可以获得对 CPU 的公平共享。

    Linux的3种调度实体:

      调度器不限于调度进程, 还可以调度更大的实体, 比如实现组调度: 可用的CPUI时间首先在一半的进程组(比如, 所有进程按照所有者分组)之间分配, 接下来分配的时间再在组内进行二次分配,这种一般性要求调度器不直接操作进程, 而是处理可调度实体, 因此需要一个通用的数据结构描述这个调度实体,即seched_entity结构, 其实际上就代表了一个调度对象,可以为一个进程,也可以为一个进程组。linux中针对当前可调度的实时和非实时进程, 定义了类型为seched_entity的3个调度实体:

调度实体

名称

描述

对应调度器类

sched_dl_entity

DEADLINE调度实体

采用EDF算法调度的实时调度实体

dl_sched_class

sched_rt_entity

RT调度实体

采用Roound-Robin或者FIFO算法调度的实时调度实体

rt_sched_class

sched_entity

CFS调度实体

采用CFS算法调度的普通非实时进程的调度实体

fair_sched_class

struct task_struct 的变化

CFS 去掉了 struct prio_array,并引入调度实体(scheduling entity)和调度类 (scheduling classes),分别由 struct sched_entity 和 struct sched_class 定义。因此,task_struct 包含关于 sched_entity 和 sched_class 这两种结构的信息:

struct task_struct {

/* Defined in 2.6.23:/usr/include/linux/sched.h */....

-  struct prio_array *array;

  struct sched_entity se;

  struct sched_class *sched_class;  

 ....   ....

};

1.操作系统是怎么组织进程的?

CFS 组调度

考虑一个两用户示例,用户 A 和用户 B 在一台机器上运行作业。用户 A 只有两个作业正在运行,而用户 B 正在运行 48 个作业。组调度使 CFS 能够对用户 A 和用户 B 进行公平调度,而不是对系统中运行的 50 个作业进行公平调度。每个用户各拥有 50% 的 CPU 使用。用户 B 使用自己 50% 的 CPU 分配运行他的 48 个作业,而不会占用属于用户 A 的另外 50% 的 CPU 分配。

CFS 调度模块(在 kernel/sched_fair.c 中实现)用于以下调度策略:SCHED_NORMAL、SCHED_BATCH 和 SCHED_IDLE。对于 SCHED_RR 和 SCHED_FIFO 策略,将使用实时调度模块(该模块在 kernel/sched_rt.c 中实现)。

CFS 另一个有趣的地方是组调度 概念(在 2.6.24 内核中引入)。组调度是另一种为调度带来公平性的方式,尤其是在处理产生很多其他任务的任务时。 假设一个产生了很多任务的服务器要并行化进入的连接(HTTP服务器的典型架构)。不是所有任务都会被统一公平对待,CFS 引入了组来处理这种行为。产生任务的服务器进程在整个组中(在一个层次结构中)共享它们的虚拟运行时,而单个任务维持其自己独立的虚拟运行时。这样单个任务会收到与组大致相同的调度时间。我们会发现 /proc 接口用于管理进程层次结构,让我们对组的形成方式有完全的控制。使用此配置,我们可以跨用户、跨进程或其变体分配公平性。

    2.6.1什么是红黑树?

    红黑树是一种在插入或删除结点时都需要维持平衡的二叉查找树,并且每个结点都具有颜色属性:

  1.     一个结点要么是红色的,要么是黑色的。
  2.     根结点是黑色的。
  3.     如果一个结点是红色的,那么它的子结点必须是黑色的,也就是说在沿着从根结点出发的任何路径上都不会出现两个连续的红色结点。
  4.     从一个结点到一个NULL指针的每条路径上必须包含相同数目的黑色结点。

    如下图所示:

    彩世界开奖app官网 7

    可以很明显的看出,该树的最左端的值是最小的。取走最左端的端点后,需要重新平衡红黑树。

其他调度器

继续研究调度,您将发现正在开发中的调度器将会突破性能和扩展性的界限。Con Kolivas 没有被他的 Linux 经验羁绊,他开发出了另一个 Linux 调度器,其缩写为:BFS。该调度器据说在 NUMA 系统以及移动设备上具有更好的性能, 并且被引入了 Android 操作系统的一款衍生产品中。

  1.3进程标示符PID:

struct task_struct {
    ........

    /* 进程ID,每个进程(线程)的PID都不同 */
    pid_t pid;
    /* 线程组ID,同一个线程组拥有相同的pid,与领头线程(该组中第一个轻量级进程)pid一致,保存在tgid中,线程组领头线程的pid和tgid相同 */
    pid_t tgid;
    /* 用于连接到PID、TGID、PGRP、SESSION哈希表 */
    struct pid_link pids[PIDTYPE_MAX];
    /*PID : 进程的ID(Process Identifier),对应pids[PIDTYPE_PID]
     *TGID : 线程组ID(Thread Group Identifier),对应pids[PIDTYPE_TGID]
     *PGRP : 进程组(Process Group),对应pids[PIDTYPE_PGID]
     *SESSION : 会话(Session),对应pids[PIDTYPE_SID]
    */

    ........
};

    PID就像我们学生的学号,每个人的身份证号一样,是独一无二的。而我们会有一个群体,比如同一个班级,同一个学校等,即有同一个组群,因此建立了TGID,用来将同一个组的PID串联起来。其中getpid()返回当前进程的tgid值而不是pid的值。

    而在系统运行的时候,可能会建立非常非常多的进程,因此为了提高内核的查找效率,专门建立了四个hash表pids[PIDTYPE_TGID]、pids[PIDTYPE_TGID]、pids[PIDTYPE_PGID]、pids[PIDTYPE_SID]用来索引。

    在内核中,这四个哈希表一共占16个页框,也就是每个哈希表占4个页框,他们每个可以拥有2048个表项,内核会把把这四个哈希表的地址保存到pid_hash数组中。现在问题来了,拿pids[PIDTYPE_TGID]为例,怎么在2048个表项中保存32767个PID值,其实内核会对每个已经分配的PID值进行一个处理,得到的结果的数值就是对应的表项,处理结果相同的PID被串成一个链表,如下:

    彩世界开奖app官网 8
    当我们使用"kill 29384"命令时,内核会根据29384处理得出199,然后以199为下标,获取PID哈希表中对应的链表头,并在此链表中找出PID=29384的进程。在进程描述符(thread_info)的*task中使用struct pid_link pids[PIDTYPE_MAX]链入这四个哈希表。对于另外三个哈希表,道理一样。

运行队列中CFS 有关的字段

对于每个运行队列,都提供了一种结构来保存相关红黑树的信息。

struct cfs_rq {

struct load_weight load;/*运行负载*/

unsigned long nr_running;/*运行进程个数*/

u64 exec_clock;

u64 min_vruntime;/*保存的最小运行时间*/

struct rb_root tasks_timeline;/*运行队列树根*/

struct rb_node *rb_leftmost;/*保存的红黑树最左边的

节点,这个为最小运行时间的节点,当进程

选择下一个来运行时,直接选择这个*/

struct list_head tasks;

struct list_head *balance_iterator;

/*

* 'curr' points to currently running entity on this cfs_rq.

* It is set to NULL otherwise (i.e when none are currently running).

*/

struct sched_entity *curr, *next, *last;

unsigned int nr_spread_over;

#ifdef CONFIG_FAIR_GROUP_SCHED

struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */

/*

* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in

* a hierarchy). Non-leaf lrqs hold other higher schedulable entities

* (like users, containers etc.)

*

* leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This

* list is used during load balance.

*/

struct list_head leaf_cfs_rq_list;

struct task_group *tg; /* group that "owns" this runqueue */

#ifdef CONFIG_SMP

/*

* the part of load.weight contributed by tasks

*/

unsigned long task_weight;

/*

*  h_load = weight * f(tg)

*

* Where f(tg) is the recursive weight fraction assigned to

* this group.

*/

unsigned long h_load;

/*

* this cpu's part of tg->shares

*/

unsigned long shares;

/*

* load.weight at the time we set shares

*/

unsigned long rq_weight;

#endif

#endif

};

    1.4.3睡眠状态:      

      正常只需将state域的值设为以下两种状态就可进入睡眠状态:

状态 描述
TASK_INTERRUPTIBLE 进程处于睡眠状态,正在等待某些事件发生。进程可以被信号中断。接收到信号或被显式的唤醒呼叫唤醒之后,进程将转变为 TASK_RUNNING 状态。
TASK_UNINTERRUPTIBLE 此进程状态类似于 TASK_INTERRUPTIBLE,只是它不会处理信号。中断处于这种状态的进程是不合适的,因为它可能正在完成某些重要的任务。 当它所等待的事件发生时,进程将被显式的唤醒呼叫唤醒。

      而在Linux2.6.25以后,新增了一条睡眠状态 : “TASK_KILLABLE”:

状态 描述
TASK_KILLABLE 当进程处于这种可以终止的新睡眠状态中,它的运行原理类似于 TASK_UNINTERRUPTIBLE,只不过可以响应致命信号。

      由代码的line 31可以看出,TASK_UNINTERRUPTIBLE TASK_WAKEKILL = TASK_KILLABLE。

  2.4调度器的设计.

展望

对于 Linux 技术而言,惟一不变的就是永恒的变化。今天,CFS 是 2.6 Linux 调度器; 明天可能就会是另一个新的调度器或一套可以被静态或动态调用的调度器。 CFS、RSDL 以及内核背后的进程中还有很多秘密等待我们去研究。

  1.4.4进程转换图:     彩世界开奖app官网 9

  因此,通过对以上数据的操作,操作系统便可以对进程进行组织和管理。

CFS内部原理

Linux 内的所有任务都由称为 task_struct 的任务结构表示。该结构(以及其他相关内容)完整地描述了任务并包括了任务的当前状态、其堆栈、进程标识、优先级(静态和动态)等等。可以在 ./linux/include/linux/sched.h 中找到这些内容以及相关结构。 但是因为不是所有任务都是可运行的,在 task_struct 中不会发现任何与 CFS 相关的字段。 相反,会创建一个名为 sched_entity 的新结构来跟踪调度信息。

彩世界开奖app官网 10

任务和红黑树的结构层次关系

树的根通过 rb_root 元素通过 cfs_rq 结构(在 ./kernel/sched.c 中)引用。红黑树的叶子不包含信息,但是内部节点代表一个或多个可运行的任务。红黑树的每个节点都由 rb_node 表示,它只包含子引用和父对象的颜色。 rb_node 包含在 sched_entity 结构中,该结构包含rb_node引用、负载权重以及各种统计数据。最重要的是,sched_entity 包含 vruntime(64 位字段),它表示任务运行的时间量,并作为红黑树的索引。 最后,task_struct 位于顶端,它完整地描述任务并包含 sched_entity 结构。

就 CFS 部分而言,调度函数非常简单。 在 ./kernel/sched.c 中,通用 schedule() 函数,它会先抢占当前运行任务(除非它通过 yield() 代码先抢占自己)。注意 CFS 没有真正的时间切片概念用于抢占,因为抢占时间是可变的。当前运行任务(现在被抢占的任务)通过对 put_prev_task 调用(通过调度类)返回到红黑树。当schedule函数开始确定下一个要调度的任务时,它会调用 pick_next_task函数。此函数也是通用的(在./kernel/sched.c 中),但它会通过调度器类调用 CFS 调度器。

CFS调度算法的核心是选择具有最小vruntine的任务。运行队列采用红黑树方式存放,其中节点的键值便是可运行进程的虚拟运行时间。CFS调度器选取待运行的下一个进程,是所有进程中vruntime最小的那个,他对应的便是在树中最左侧的叶子节点。实现选择的函数为pick_next_task_fair,CFS 中的 pick_next_task 函数可以在 ./kernel/sched_fair.c(称为pick_next_task_fair())中找到。 此函数只是从红黑树中获取最左端的任务并返回相关sched_entity。通过此引用,一个简单的 task_of()调用确定返回的task_struct 引用。通用调度器最后为此任务提供处理器。

static struct task_struct *pick_next_task_fair(struct rq *rq)

{

struct task_struct *p;

struct cfs_rq *cfs_rq = &rq->cfs;

struct sched_entity *se;

if (unlikely(!cfs_rq->nr_running))

return NULL;

do {/*此循环为了考虑组调度*/

se = pick_next_entity(cfs_rq);

set_next_entity(cfs_rq, se);/*设置为当前运行进程*/

cfs_rq = group_cfs_rq(se);

} while (cfs_rq);

p = task_of(se);

hrtick_start_fair(rq, p);

return p;

}

实质工作调用__pick_next_entity完成。

/*函数本身并不会遍历数找到最左叶子节点(即就是所有进程中vruntime最小的那个),因为该值已经缓存在rb_leftmost字段中*/

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)

{

/*rb_leftmost为保存的红黑树的最左边的节点*/

struct rb_node *left = cfs_rq->rb_leftmost;

if (!left)

return NULL;

return rb_entry(left, struct sched_entity, run_node);

}

    Linux的2种调度器:

调度器 描述
主调度器 直接根据进程的状态进行调度,比如当其打算睡眠或出于其他原因放弃占用CPU时
周期调度器 通过周期性的机制, 以固定的频率运行, 不时地去检测是否有必要进行调度

    其中这两者统称为通用调度器(generic scheduler)核心调度器(core scheduler)。

    每个调度器包括两个内容:调度框架(其实质就是两个函数框架)及调度器类。

调度类和域

与 CFS 一起引入的是调度类概念。每个任务都属于一个调度类,这决定了任务将如何调度。 调度类定义一个通用函数集(通过sched_class),函数集定义调度器的行为。例如,每个调度器提供一种方式, 添加要调度的任务、调出要运行的下一个任务、提供给调度器等等。每个调度器类都在一对一连接的列表中彼此相连,使类可以迭代(例如,要启用给定处理器的禁用)。一般结构如下图所示。注意,将任务函数加入队列或脱离队列只需从特定调度结构中加入或移除任务。 函数 pick_next_task 选择要执行的下一个任务(取决于调度类的具体策略)。

彩世界开奖app官网 11

调度类视图

但是不要忘了调度类是任务结构本身的一部分,这一点简化了任务的操作,无论其调度类具体如何实现。例如, 以下函数用 ./kernel/sched.c 中的新任务抢占当前运行任务(其中 curr 定义了当前运行任务, rq 代表 CFS 红黑树而 p 是下一个要调度的任务):

static inline void check_preempt( struct rq *rq, struct task_struct *p ){ 

 rq->curr->sched_class->check_preempt_curr( rq, p );

}

如果此任务正使用公平调度类,则 check_preempt_curr() 将解析为check_preempt_wakeup()。 我们可以在 ./kernel/sched_rt.c,/kernel/sched_fair.c 和 ./kernel/sched_idle.c 中查看这些关系。

调度类是调度发生变化的另一个有趣的地方,但是随着调度域的增加,功能也在增加。 这些域允许您出于负载平衡和隔离的目的将一个或多个处理器按层次关系分组。 一个或多个处理器能够共享调度策略(并在其之间保持负载平衡)或实现独立的调度策略从而故意隔离任务。

    CFS调度的原理:

    在理想状态下时每个进程都能获得相同的时间片,并且同时运行在CPU上,但实际上一个CPU同一时刻运行的进程只能有一个。 也就是说,当一个进程占用CPU时,其他进程就必须等待。而往往有一些需要优先去占用CPU的进程,所以实际上我们是根据每个进程的权重来分配每个进程的运行时间,越重要的进程,我们设置的权重就越高。

    而前面说过,调度还有一个重要的意义在于要对所有进程尽可能地公平分配时间,可是从分配时间来看,权重越高的似乎分配到的运行时间就会越多,并没有让人感觉到公平,于是CFS引入了一个变量 : 虚拟运行时间(virtual runtime),它会惩罚当前正在运行的进程,以使那些正在等待的进程下次被调度。用vruntime的大小来衡量哪个进程是最优先需要被调度的。

    虚拟运行时间计算公式为:一次调度间隔的vruntime = 实际运行时间 * NICE_0_LOAD / 进程权重;**

    其中代码NICE_0_LOAD对应的是nice为0的进程的权重值为1024,而所有进程都以nice为0的进程的权重1024作为基准,计算自己的vruntime增加速度。(见后面公式)     

 /*nice和权重值的转换表*/
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,  
};

 

    因为CFS中的就绪队列是一棵以vruntime为键值的红黑树,虚拟时间越小的进程越靠近整个红黑树的最左端。因此,调度器每次选择位于红黑树最左端的那个进程,该进程的vruntime最小。(对应之前的min_vruntime)

    其中vruntime以下公式计算它的增长数值:

条件

公式

当前进程的nice != NICE_0_LOAD

vruntime = delta_exec * NICE_0_LOAD / 进程权重

当前进程的nice == NICE_0_LOAD

vruntime = delta_exec

  •  其中delta_exce为"内核计算当前和上一次更新负荷权重时两次的时间的差值", 计算公式为:delta_exec = 当前时间 - 上次更新时间

    因此权重越大的进程的vruntime的增长率会越小,更容易排在红黑树偏左端,进而更容易被调度,而权重小的则相反。

    计算完vruntime之后,就要进行设置红黑树。

2.6.24 中的组调度有哪些改变

在 2.6.24 中,我们将能够对调度程序进行调优,从而实现对用户或组的公平性,而不是任务公平性。可以将任务进行分组,形成多个实体,调度程序将平等对待这些实体,继而公平对待实体中的任务。要启用这个特性,在编译内核时需要选择 CONFIG_FAIR_GROUP_SCHED。目前,只有 SCHED_NORMAL 和SCHED_BATCH 任务可以进行分组。

可以使用两个独立的方法对任务进行分组,它们分别基于:

1.用户 ID。

2.cgroup pseudo 文件系统:这个选项使管理员可以根据需要创建组。有关更多细节,阅读内核源文档目录中的 cgroups.txt 文件。

3.内核配置参数 CONFIG_FAIR_USER_SCHED 和 CONFIG_FAIR_CGROUP_SCHED 可帮助您进行选择。

通过引入调度类并通过增强调度统计信息来简化调试,这个新的调度程序进一步扩展了调度功能。

  1.1什么是线程,什么是进程:

    刚接触时可能经常会将这两个东西搞混。简单一点的说,进程是一个大工程,线程则是这个大工程中每个小地方需要做的东西(在linux下看作"轻量级进程"):

    例如当你打开QQ微信,这时系统启动了一个进程。然后你开始看别人发的消息,这时启动了一个线程用来传输文本,如果发了一段语音,这也会启动一个线程来传输语音......(当然一个程序并不代表一定只有一个进程)

struct sched_entity

运行实体结构为sched_entity,该结构包含了完整的信息,用于实现对单个任务或任务组的调度。它可用于实现组调度。调度实体可能与进程没有关联。所有的调度器都必须对进程运行时间做记账。CFS不再有时间片的概念,但是他也必须维护每个进程运行的时间记账,因为他需要确保每个进程只在公平分配给他的处理器时间内运行。CFS使用调度器实体结构来最终运行记账。

彩世界开奖app官网 12

sched_entity 结构体简介

实现记账功能,由系统定时器周期调用

static void update_curr(struct cfs_rq *cfs_rq)

{

struct sched_entity *curr = cfs_rq->curr;

u64 now = rq_of(cfs_rq)->clock;/*now计时器*/

unsigned long delta_exec;

if (unlikely(!curr))

return;

/*

* Get the amount of time the current task was running

* since the last time we changed load (this cannot

* overflow on 32 bits):

*/

/*获得从最后一次修改负载后当前任务所占用的运行总时间*/

/*即计算当前进程的执行时间*/

delta_exec = (unsigned long)(now - curr->exec_start);

if (!delta_exec)/*如果本次没有执行过,不用重新更新了*/

return;

/*根据当前可运行进程总数对运行时间进行加权计算*/

__update_curr(cfs_rq, curr, delta_exec);

curr->exec_start = now;/*将exec_start属性置为now*/

if (entity_is_task(curr)) {/*下面为关于组调度的,暂时不分析了*/

struct task_struct *curtask = task_of(curr);

trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);

cpuacct_charge(curtask, delta_exec);

account_group_exec_runtime(curtask, delta_exec);

}

}

  2.3调度器的演变.

    一开始的调度器是复杂度为O(n)**的始调度算法(实际上每次会遍历所有任务,所以复杂度为O(n)), 这个算法的缺点是当内核中有很多任务时,调度器本身就会耗费不少时间,所以,从linux2.5开始引入赫赫有名的O(1)**调度器。然而,linux是集全球很多程序员的聪明才智而发展起来的超级内核,没有最好,只有更好,在O(1)调度器风光了没几天就又被另一个更优秀的调度器取代了,它就是CFS调度器(Completely Fair Scheduler). 这个也是在2.6内核中引入的,具体为2.6.23,即从此版本开始,内核使用CFS作为它的默认调度器,O(1)调度器被抛弃了, 其实CFS的发展也是经历了很多阶段,最早期的楼梯算法(SD), 后来逐步对SD算法进行改进出RSDL(Rotating Staircase Deadline Scheduler), 这个算法已经是”完全公平”的雏形了, 直至CFS是最终被内核采纳的调度器, 它从RSDL/SD中吸取了完全公平的思想,不再跟踪进程的睡眠时间,也不再企图区分交互式进程。它将所有的进程都统一对待,这就是公平的含义。CFS的算法和实现都相当简单,众多的测试表明其性能也非常优越。     

调度器

Linux版本

O(n)的始调度算法

linux-0.11~2.4

O(1)调度器

linux-2.5

CFS调度器

linux-2.6~至今

  1.4进程状态的转换:

    进程的状态用state表示,简单表示有以下3种:

volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */

    其中详细有以下状态:

 1 /*
 2  * Task state bitmask. NOTE! These bits are also
 3  * encoded in fs/proc/array.c: get_task_state().
 4  *
 5  * We have two separate sets of flags: task->state
 6  * is about runnability, while task->exit_state are
 7  * about the task exiting. Confusing, but this way
 8  * modifying one set can't modify the other one by
 9  * mistake.
10  */
11 #define TASK_RUNNING            0
12 #define TASK_INTERRUPTIBLE      1
13 #define TASK_UNINTERRUPTIBLE    2
14 #define __TASK_STOPPED          4
15 #define __TASK_TRACED           8
16 
17 /* in tsk->exit_state */
18 #define EXIT_DEAD               16
19 #define EXIT_ZOMBIE             32
20 #define EXIT_TRACE              (EXIT_ZOMBIE | EXIT_DEAD)
21  
22 /* in tsk->state again */
23 #define TASK_DEAD               64
24 #define TASK_WAKEKILL           128    /** wake on signals that are deadly **/
25 #define TASK_WAKING             256
26 #define TASK_PARKED             512
27 #define TASK_NOLOAD             1024
28 #define TASK_STATE_MAX          2048
29 
30  /* Convenience macros for the sake of set_task_state */
31 #define TASK_KILLABLE           (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
32 #define TASK_STOPPED            (TASK_WAKEKILL | __TASK_STOPPED)
33 #define TASK_TRACED             (TASK_WAKEKILL | __TASK_TRACED)

3.体会

  这些只是Linux下的一小部分罢了,源码的代码量大到吓人,基于无数大牛们的努力写出了现在的Linux,而Linux永远在不断的更新,这些代码算法等等永远不会是最好的,我还需要不断的学习新的知识,继续探索这个充斥着01的世界。

    2.6.2重新设置min_vruntime的红黑树

    代码如下:

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
   /*初始化vruntime的值 
   *相当于如下的代码 
   *if (cfs_rq->curr != NULL) 
   *  vruntime = cfs_rq->curr->vruntime; 
   *else 
   *  vruntime = cfs_rq->min_vruntime;
   */
    u64 vruntime = cfs_rq->min_vruntime;
  if (cfs_rq->curr)
        vruntime = cfs_rq->curr->vruntime;

    /* 检测红黑树是都有最左的节点, 即是否有进程在树上等待调度
     * cfs_rq->rb_leftmost(struct rb_node *)存储了进程红黑树的最左节点
     * 这个节点存储了即将要被调度的结点 */

  if (cfs_rq->rb_leftmost) {
    /* 获取最左结点的调度实体信息se, se中存储了其vruntime      
     * rb_leftmost的vruntime即树中所有节点的vruntiem中最小的那个 */

struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
                           struct sched_entity,
                           run_node);
   /* 如果就绪队列上没有curr进程      
    * 则vruntime设置为树种最左结点的vruntime      
    * 否则设置vruntiem值为cfs_rq->curr->vruntime和se->vruntime的最小值 */
        if (!cfs_rq->curr)  /* 此时vruntime的原值为cfs_rq->min_vruntime*/
            vruntime = se->vruntime;
        else          /* 此时vruntime的原值为cfs_rq->curr->vruntime*/
            vruntime = min_vruntime(vruntime, se->vruntime);
    }

    /* ensure we never gain time by being placed backwards. 
   * 为了保证min_vruntime单调不减 
   * 只有在vruntime超出的cfs_rq->min_vruntime的时候才更新 */
    cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
#ifndef CONFIG_64BIT
    smp_wmb();
    cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
#endif
}

    重新平衡完min_vruntime的红黑树之后,就可以继续通过CFS去调度进程了,并以此循环。

  2.2进程的分类.

    当涉及有关调度的问题时, 传统上把进程分类为”I/O受限(I/O-dound)”或”CPU受限(CPU-bound)”.

类型

别称

描述

示例

I/O受限型

I/O密集型

频繁的使用I/O设备, 并花费很多时间等待I/O操作的完成

数据库服务器, 文本编辑器

CPU受限型

计算密集型

花费大量CPU时间进行数值计算

图形绘制程序

    另外一种分类法把进程区分为三类:

类型

描述

示例

交互式进程(interactive process)

此类进程经常与用户进行交互, 因此需要花费很多时间等待键盘和鼠标操作. 当接受了用户的输入后, 进程必须很快被唤醒, 否则用户会感觉系统反应迟钝

shell, 文本编辑程序和图形应用程序

批处理进程(batch process)

此类进程不必与用户交互, 因此经常在后台运行. 因为这样的进程不必很快相应, 因此常受到调度程序的怠慢

程序语言的编译程序, 数据库搜索引擎以及科学计算

实时进程(real-time process)

这些进程由很强的调度需要, 这样的进程绝不会被低优先级的进程阻塞. 并且他们的响应时间要尽可能的短

视频音频应用程序, 机器人控制程序以及从物理传感器上收集数据的程序

2.进程是怎么被调度的?

    1.4.2二种终止状态:      

      这两个附加的进程状态既可以被添加到state域中,又可以被添加到exit_state域中。只有当进程终止的时候,才会达到这两种状态:

状态 描述
EXIT_ZOMBIE 进程的执行被终止,但是其父进程还没有使用wait()等系统调用来获知它的终止信息,此时进程成为僵尸进程
EXIT_DEAD 进程的最终状态

本文由彩世界开奖app官网发布于彩世界开奖app官网,转载请注明出处:[校招面试]CPU调度系列二彩世界开奖app官网

关键词: Linux linux校招面试