进程调度决定了将哪个进程进行执行,以及执行的时间。操作系统进行合理的进程调度,使得资源得到最大化的利用。
在单片机上,常常使用的方式是:系统初始化---->while(1){}。(当然,单片机也可以跑类似 FreeRTOS,也可以有进程切换)
在带操作系统的 CPU 上跑的逻辑是,允许多个进程(其实就是程序) ”同时” 跑。比如,你可以在操作鼠标的同时,进行音乐播放,文字编辑等。宏观上看上去是多个任务并行执行,事实的本质是 CPU 在不断的调度每一个进程,使得每个进程都得以响应,与此同时,还要兼顾不同场景下的响应效率(进程的执行时间)。
进程调度器的任务就是合理分配CPU时间给运行的进程,创造一种所有进程并行运行的错觉。这就对调度器提出了要求:
而调度器的任务就是:
所以具体而言,调度器的任务就明确了:用一句话表述就是在恰当的实际,按照合理的调度算法,选择进程,让进程运行到它应该运行的时间,切换两个进程的上下文。
运行的进程如果大部分来进行 I/O 的请求或者等待的话,这个进程称之为 I/O 消耗型,比如键盘。这种类型的进程经常处于可以运行的状态,但是都只是运行一点点时间,绝大多数的时间都在处于阻塞(睡眠)的状态。
如果进程的绝大多数都在使用 CPU 做运算的话,那么这种进程称之为 CPU 消耗型,比如开启 Matlab 做一个大型的运算。没有太多的 I/O 需求,从系统响应的角度上来讲,调度器不应该经常让他们运行。对于处理器消耗型的进程,调度策略往往是降低他们的执行频率,延长运行时间。
Linux 系统为了提升响应的速度,倾向于优先调度 I/O 消耗型。
调度算法中比较基本的就是靠进程的优先级来进行进程的调度,比如 FreeRTOS,靠 task 的优先级来进行进程的抢占。
总之:实时进程优先级:value 越高,优先级越大;普通进程优先级:nice值越高,普通进程的优先级越小;任何实时进程的优先级 > 普通进程。
Linux 中有一个总的调度结构,称之为 调度器类(scheduler class),它允许不同的可动态添加的调度算法并存,总调度器根据调度器类的优先顺序,依次去进行调度器类的中的进程进行调度,挑选了调度器类,再在这个调度器内,使用这个调度器类的算法(调度策略)进行内部的调度
调度器的优先级顺序为:
Scheduling Class 的优先级顺序为 Stop_ask > Real_Time > Fair > Idle_Task,开发者可以根据己的设计需求,來把所属的Task配置到不同的Scheduling Class中。其中的 Real_time 和 Fair 是最最常用的,下面主要聊聊着两类。
对于一个普通进程,CFS 调度器调度它执行(SCHED_NORMAL),需要考虑两个方面维度:
—— 在 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的主要思想。
进程运行的时间是根据进程的权重进行分配。
[ 分配给进程的运行时间 = 调度周期 *(进程权重 / 所有进程权重之和) ]
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),都会比他们更先得到调度。
上述两种实时算法都是静态的优先级。内核不为实时优先级的进程计算动态优先级,保证给定的优先级的实时进程总能够抢占比他优先级低的进程。
从进程的角度看,CPU是共享资源,由所有的进程按特定的策略轮番使用。一个进程离开CPU、另一个进程占据CPU的过程,称为进程切换(process switch)。进程切换是在内核中通过调用schedule()完成的。
发生进程切换的场景有以下三种:
//把进程放进等待队列,把进程状态置为TASK_UNINTERRUPTIBLE
prepare_to_wait(waitq, wait, TASK_UNINTERRUPTIBLE);
//切换进程
schedule();
注意:进程可以通过调用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了。
抢占的过程分两步,第一步触发抢占,第二步执行抢占,这两步中间不一定是连续的,有些特殊情况下甚至会间隔相当长的时间:
抢占只在某些特定的时机发生,这是内核的代码决定的。
每个进程都包含一个TIF_NEED_RESCHED标志,内核根据这个标志判断该进程是否应该被抢占,设置TIF_NEED_RESCHED标志就意味着触发抢占。
直接设置TIF_NEED_RESCHED标志的函数是 set_tsk_need_resched();触发抢占的函数是resched_task()。
TIF_NEED_RESCHED标志什么时候被设置呢?在以下时刻:
/*
* 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);
...
}
int sched_fork(unsigned long clone_flags, struct task_struct *p)
{
...
if (p->sched_class->task_fork)
p->sched_class->task_fork(p);
...
}
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(用户态抢占)的时机:
源文件:arch/x86/kernel/entry_64.S
sysret_careful:
bt $TIF_NEED_RESCHED,%edx
jnc sysret_signal
TRACE_IRQS_ON
ENABLE_INTERRUPTS(CLBR_NONE)
pushq_cfi %rdi
call schedule
popq_cfi %rdi
jmp sysret_check
retint_careful:
CFI_RESTORE_STATE
bt $TIF_NEED_RESCHED,%edx
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
在 CONFIG_PREEMPT=y 的前提下,内核态抢占的时机是:
#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()的包装。
文章参考:https://stephenzhou.blog.csdn.net/article/details/86290196