菜鸟笔记
提升您的技术认知

linux 进程调度浅析-ag真人游戏

进程调度决定了将哪个进程进行执行,以及执行的时间。操作系统进行合理的进程调度,使得资源得到最大化的利用。

在单片机上,常常使用的方式是:系统初始化---->while(1){}。(当然,单片机也可以跑类似 freertos,也可以有进程切换)

在带操作系统的 cpu 上跑的逻辑是,允许多个进程(其实就是程序) ”同时” 跑。比如,你可以在操作鼠标的同时,进行音乐播放,文字编辑等。宏观上看上去是多个任务并行执行,事实的本质是 cpu 在不断的调度每一个进程,使得每个进程都得以响应,与此同时,还要兼顾不同场景下的响应效率(进程的执行时间)。

 进程调度器的任务就是合理分配cpu时间给运行的进程,创造一种所有进程并行运行的错觉。这就对调度器提出了要求:

1、调度器分配的cpu时间不能太长,否则会导致其他的程序响应延迟,难以保证公平性。

2、调度器分配的时间也不能太短,每次调度会导致上下文切换,这种切换开销很大。

而调度器的任务就是:1、分配时间给进程     2、上下文切换

所以具体而言,调度器的任务就明确了:用一句话表述就是在恰当的实际,按照合理的调度算法,选择进程,让进程运行到它应该运行的时间,切换两个进程的上下文。

运行的进程如果大部分来进行 i/o 的请求或者等待的话,这个进程称之为 i/o 消耗型,比如键盘。这种类型的进程经常处于可以运行的状态,但是都只是运行一点点时间,绝大多数的时间都在处于阻塞(睡眠)的状态。

如果进程的绝大多数都在使用 cpu 做运算的话,那么这种进程称之为 cpu 消耗型,比如开启 matlab 做一个大型的运算。没有太多的 i/o 需求,从系统响应的角度上来讲,调度器不应该经常让他们运行。对于处理器消耗型的进程,调度策略往往是降低他们的执行频率,延长运行时间。

linux 系统为了提升响应的速度,倾向于优先调度 i/o 消耗型。

调度算法中比较基本的就是靠进程的优先级来进行进程的调度,比如 freertos,靠 task 的优先级来进行进程的抢占。

一、普通进程

在 linux 中普通进程依赖称之为 nice 值 的东东来进行进程的优先级描述。nice 值的范围是 [-20, 19]。默认的 default 值为 0;越低的 nice 值,代表着越高的优先级,反之,越高的 nice 值代表着越低的优先级。

越高优先级的 普通进程 有着越高的执行时间(注意,这里值的越高的执行时间,指的是在一小段观察时间内,每个可执行的进程都执行一遍的情况,这里的描述可能产生一些歧义,稍安勿躁,接着看)。可以通过  ps -el 查看系统中进程列表

二、实时进程

实时优先级是可配置的默认情况下的范围是 0~99,与 nice 值相反,越高的实时优先级数值代表着越高的优先级。与此同时,任何实时进程的优先级都高于普通进程的优先级

—— 小结

实时进程优先级:value 越高,优先级越大

普通进程优先级:nice值越高,普通进程的优先级越小

任何实时进程的优先级 > 普通进程

linux 中有一个总的调度结构,称之为 调度器类(scheduler class),它允许不同的可动态添加的调度算法并存,总调度器根据调度器类的优先顺序,依次去进行调度器类的中的进程进行调度,挑选了调度器类,再在这个调度器内,使用这个调度器类的算法(调度策略)进行内部的调度

调度器的优先级顺序为:

scheduling class 的优先级顺序为 stop_ask > real_time > fair > idle_task,开发者可以根据己的设计需求,來把所属的task配置到不同的scheduling class中。其中的 real_timefair 是最最常用的,下面主要聊聊着两类。

一、fair 调度使用的是 cfs 的调度算法,即完全公平调度器

对于一个普通进程,cfs 调度器调度它执行(sched_normal),需要考虑两个方面维度:

1. 如何挑选哪一个进程进入运行状态?

—— 在 cfs 中,给每一个进程安排了一个虚拟时钟 vruntime(virtual runtime),这个变量并非直接等于他的绝对运行时间,而是根据运行时间放大或者缩小一个比例,cfs 使用这个 vruntime 来代表一个进程的运行时间。如果一个进程得以执行,那么他的 vruntime 将不断增大,直到它没有执行。没有执行的进程的 vruntime 不变。调度器为了体现绝对的完全公平的调度原则,总是选择 vruntime 最小的进程,让其投入执行。他们被维护到一个以 vruntime 为顺序的红黑树 rbtree 中,每次去取最小的 vruntime 的进程来投入运行。实际运行时间到 vruntime 的计算公式为:

[ vruntime = 实际运行时间 * 1024 / 进程权重 ]

这里的1024代表nice值为0的进程权重。所有的进程都以nice为0的权重1024作为基准,计算自己的vruntime。上面两个公式可得出,虽然进程的权重不同,但是它们的 vruntime增长速度应该是一样的 ,与权重无关。既然所有进程的vruntime增长速度宏观上看应该是同时推进的,那么就可以用vruntime来选择运行的进程,vruntime值较小就说明它以前占用cpu的时间较短,受到了“不公平”对待,因此下一个运行进程就是它。这样既能公平选择进程,又能保证高优先级进程获得较多的运行时间,这就是cfs的主要思想。

2. 挑选的进程进行运行了,它运行多久?

进程运行的时间是根据进程的权重进行分配。

 [ 分配给进程的运行时间 = 调度周期 *(进程权重 / 所有进程权重之和)

cfs 调度器实体结构作为一个名为 se 的 sched_entity 结构,嵌入到进程描述符 struct task_struct

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			nr_migrations;
#ifdef config_schedstats
	struct sched_statistics statistics;
#endif
#ifdef config_fair_group_sched
	struct sched_entity	*parent;
	/* rq on which this entity is (to be) queued: */
	struct cfs_rq		*cfs_rq;
	/* rq "owned" by this entity/group: */
	struct cfs_rq		*my_q;
#endif
};

二、实时调度策略

对于实时调度策略分为两种:sched_fifo 和 sched_rr:

这两种进程都比任何普通进程的优先级更高(sched_normal),都会比他们更先得到调度。

sched_fifo : 一个这种类型的进程出于可执行的状态,就会一直执行,直到它自己被阻塞或者主动放弃 cpu;它不基于时间片,可以一直执行下去,只有更高优先级的 sched_fifo 或者 sched_rr 才能抢占它的任务,如果有两个同样优先级的 sched_fifo 任务,它们会轮流执行,其他低优先级的只有等它们变为不可执行状态,才有机会执行。

sched_rr : 与 sched_fifo 大致相同,只是 sched_rr 级的进程在耗尽其时间后,不能再执行,需要接受 cpu 的调度。当 sched_rr 耗尽时间后,同一优先级的其他实时进程被轮流调度。

上述两种实时算法都是静态的优先级。内核不为实时优先级的进程计算动态优先级,保证给定的优先级的实时进程总能够抢占比他优先级低的进程。

一、进程切换

从进程的角度看,cpu是共享资源,由所有的进程按特定的策略轮番使用。一个进程离开cpu、另一个进程占据cpu的过程,称为进程切换(process switch)。进程切换是在内核中通过调用schedule()完成的。

发生进程切换的场景有以下三种:

1、进程运行不下去了:

比如因为要等待io完成,或者等待某个资源、某个事件,典型的内核代码如下:

//把进程放进等待队列,把进程状态置为task_uninterruptible
prepare_to_wait(waitq, wait, task_uninterruptible);
//切换进程
schedule();

2、进程还在运行,但内核不让它继续使用cpu了:

比如进程的时间片用完了,或者优先级更高的进程来了,所以该进程必须把cpu的使用权交出来;

3、进程还可以运行,但它自己的算法决定主动交出cpu给别的进程:

用户程序可以通过系统调用sched_yield()来交出cpu,内核则可以通过函数cond_resched()或者yield()来做到。

进程切换分为自愿切换(voluntary)和强制切换(involuntary),以上场景1属于自愿切换,场景2和3属于强制切换。

  • 自愿切换发生的时候,进程不再处于运行状态,比如由于等待io而阻塞(task_uninterruptible),或者因等待资源和特定事件而休眠(task_interruptible),又或者被debug/trace设置为task_stopped/task_traced状态;
  • 强制切换发生的时候,进程仍然处于运行状态(task_running),通常是由于被优先级更高的进程抢占(preempt),或者进程的时间片用完了。

注意:进程可以通过调用sched_yield()主动交出cpu,这不是自愿切换,而是属于强制切换,因为进程仍然处于运行状态。有时候内核代码会在耗时较长的循环体内通过调用 cond_resched()或yield() ,主动让出cpu,以免cpu被内核代码占据太久,给其它进程运行机会。这也属于强制切换,因为进程仍然处于运行状态。

进程自愿切换(voluntary)和强制切换(involuntary)的次数被统计在 /proc//status 中,其中voluntary_ctxt_switches表示自愿切换的次数,nonvoluntary_ctxt_switches表示强制切换的次数,两者都是自进程启动以来的累计值。

也可以用 pidstat -w 命令查看进程切换的每秒统计值:

pidstat -w 1
linux 3.10.0-229.14.1.el7.x86_64 (bj71s060)     02/01/2018      _x86_64_       (2 cpu)
 
12:05:20 pm   uid       pid   cswch/s nvcswch/s  command
12:05:21 pm     0      1299      0.94      0.00  httpd
12:05:21 pm     0     27687      0.94      0.00  pidstat

自愿切换和强制切换的统计值在实践中有什么意义呢?
大致而言,如果一个进程的自愿切换占多数,意味着它对cpu资源的需求不高。如果一个进程的强制切换占多数,意味着对它来说cpu资源可能是个瓶颈,这里需要排除进程频繁调用sched_yield()导致强制切换的情况。

二、调度时机

自愿切换意味着进程需要等待某种资源,强制切换则与抢占(preemption)有关。

抢占(preemption)是指内核强行切换正在cpu上运行的进程,在抢占的过程中并不需要得到进程的配合,在随后的某个时刻被抢占的进程还可以恢复运行。发生抢占的原因主要有:进程的时间片用完了,或者优先级更高的进程来争夺cpu了。

抢占的过程分两步,第一步触发抢占,第二步执行抢占,这两步中间不一定是连续的,有些特殊情况下甚至会间隔相当长的时间:

  1. 触发抢占:给正在cpu上运行的当前进程设置一个请求重新调度的标志(tif_need_resched),仅此而已,此时进程并没有切换。
  2. 执行抢占:在随后的某个时刻,内核会检查tif_need_resched标志并调用schedule()执行抢占。

抢占只在某些特定的时机发生,这是内核的代码决定的。

触发抢占的时机

每个进程都包含一个tif_need_resched标志,内核根据这个标志判断该进程是否应该被抢占,设置tif_need_resched标志就意味着触发抢占。

直接设置tif_need_resched标志的函数是 set_tsk_need_resched();
触发抢占的函数是resched_task()。

tif_need_resched标志什么时候被设置呢?在以下时刻:

  • 周期性的时钟中断

时钟中断处理函数会调用scheduler_tick(),这是调度器核心层(scheduler core)的函数,它通过调度类(scheduling class)的task_tick方法 检查进程的时间片是否耗尽,如果耗尽则触发抢占:

/*
 * this function gets called by the timer code, with hz frequency.
 * we call it with interrupts disabled.
 */
void scheduler_tick(void)
{
    ...
	curr->sched_class->task_tick(rq, curr, 0);
    ...
}
  • 唤醒进程的时候

当进程被唤醒的时候,如果优先级高于cpu上的当前进程,就会触发抢占。相应的内核代码中,try_to_wake_up()最终通过check_preempt_curr()检查是否触发抢占。

  • 新进程创建的时候

如果新进程的优先级高于cpu上的当前进程,会触发抢占。相应的调度器核心层代码是sched_fork(),它再通过调度类的 task_fork方法触发抢占:

int sched_fork(unsigned long clone_flags, struct task_struct *p)
{
        ...
        if (p->sched_class->task_fork)
                p->sched_class->task_fork(p);
        ...
}
  • 进程修改nice值的时候

如果进程修改nice值导致优先级高于cpu上的当前进程,也会触发抢占。内核代码参见 set_user_nice()。

  • 进行负载均衡的时候

在多cpu的系统上,进程调度器尽量使各个cpu之间的负载保持均衡,而负载均衡操作可能会需要触发抢占。

不同的调度类有不同的负载均衡算法,涉及的核心代码也不一样,比如cfs类在load_balance()中触发抢占:

load_balance()
{
        ...
        move_tasks();
        ...
        resched_cpu();
        ...
}

rt类的负载均衡基于overload,如果当前运行队列中的rt进程超过一个,就调用push_rt_task()把进程推给别的cpu,在这里会触发抢占。

执行抢占的时机

触发抢占通过设置进程的tif_need_resched标志告诉调度器需要进行抢占操作了,但是真正执行抢占还要等内核代码发现这个标志才行,而内核代码只在设定的几个点上检查tif_need_resched标志,这也就是执行抢占的时机。

抢占如果发生在进程处于用户态的时候,称为user preemption(用户态抢占);如果发生在进程处于内核态的时候,则称为kernel preemption(内核态抢占)。

执行user preemption(用户态抢占)的时机

1. 从系统调用(syscall)返回用户态时;

源文件:arch/x86/kernel/entry_64.s
sysret_careful:
        bt $tif_need_resched,�x
        jnc sysret_signal
        trace_irqs_on
        enable_interrupts(clbr_none)
        pushq_cfi %rdi
        call schedule
        popq_cfi %rdi
        jmp sysret_check

2. 从中断返回用户态时:

retint_careful:
        cfi_restore_state
        bt    $tif_need_resched,�x
        jnc   retint_signal
        trace_irqs_on
        enable_interrupts(clbr_none)
        pushq_cfi %rdi
        call  schedule
        popq_cfi %rdi
        get_thread_info(%rcx)
        disable_interrupts(clbr_none)
        trace_irqs_off
        jmp retint_check

执行kernel preemption(内核态抢占)的时机

inux在2.6版本之后就支持内核抢占了,但是请注意,具体取决于内核编译时的选项:

  • config_preempt_none=y
    不允许内核抢占。这是sles的默认选项。
  • config_preempt_voluntary=y
    在一些耗时较长的内核代码中主动调用cond_resched()让出cpu。这是rhel的默认选项。
  • config_preempt=y
    允许完全内核抢占。

在 config_preempt=y 的前提下,内核态抢占的时机是:

1. 中断处理程序返回内核空间之前会检查tif_need_resched标志,如果置位则调用preempt_schedule_irq()执行抢占。preempt_schedule_irq()是对schedule()的包装。

#ifdef config_preempt
        /* returning to kernel space. check if we need preemption */
        /* rcx:  threadinfo. interrupts off. */
entry(retint_kernel)
        cmpl $0,ti_preempt_count(%rcx)
        jnz  retint_restore_args
        bt  $tif_need_resched,ti_flags(%rcx)
        jnc  retint_restore_args
        bt   $9,eflags-argoffset(%rsp)  /* interrupts off? */
        jnc  retint_restore_args
        call preempt_schedule_irq
        jmp exit_intr
#endif

2. 当内核从non-preemptible(禁止抢占)状态变成preemptible(允许抢占)的时候;
在preempt_enable()中,会最终调用 preempt_schedule 来执行抢占。preempt_schedule()是对schedule()的包装。

 

网站地图