linux内核进程调度

本节主要介绍进程的调度器,设计的目标:吞吐和响应,轮流让其他进程获取CPU资源。

进程调度机制的架构

操作系统通过中断机制,来周期性地触发调度算法进行进程的切换。

  • rq: 可运行队列,每个CPU对应一个,包含自旋锁,进程数量,用于公平调度的CFS结构体,当前正在运行的进程描述符。
  • cfs_rq: cfs调度的运行队列信息,包含红黑色的根节点,正在运行的进程指针,用于负载均衡的叶子队列等。
  • sched_entity: 调度实体,包含负载权重值,对应红黑树节点,虚拟运行时vruntime等。
  • sched_class: 调度算法抽象成的调度类,包含一组通用的调度操作接口,将接口和实现分离。

linux内核进程调度

schedule函数的流程包括:

  1. 关闭内核抢占,标识cpu状态。通知RCU更新状态,关闭本地终端,获取所要保护的运行队列的自旋锁,为查找可运行进程做准备。
  2. 检查prev状态,决定是否将进程插入到运行队列,或者从运行队列中删除。
  3. task_on_rq_queued(prev) : 将pre进程插入到运行队列的队尾。
  4. pick_next_task : 选取下一个将要执行的进程。
  5. context_switch(rq, prev, next) 进行进程上下文切换。

CPU/IO消耗型进程

吞吐 vs. 响应

  • 响应:最小化某个任务的响应时间,哪怕牺牲其他的任务为代价。
  • 吞吐:全局视野,整个系统的workload被最大化处理。

任何操作系统的调度器设计只追求2个目标:吞吐率大和延迟低。这2个目标有点类似零和游戏,因为吞吐率要大,势必要把更多的时间放在做真实的有用功,而不是把时间浪费在频繁的进程上下文切换;而延迟要低,势必要求优先级高的进程可以随时抢占进来,打断别人,强行插队。但是,抢占会引起上下文切换,上下文切换的时间本身对吞吐率来讲,是一个消耗,这个消耗可以低到2us或者更低(这看起来没什么?),但是上下文切换更大的消耗不是切换本身,而是切换会引起大量的cache miss。你明明weibo跑的很爽,现在切过去微信,那么CPU的cache是不太容易命中微信的。

操作系统中估算”上下文切换”对吞吐能力影响时,不是计算上下文切换本身,而是在CPU 高速cache中的miss。一旦从一个进程切到另一个进程,会造成比较多的cache miss,从而影响吞吐能力。

在内核编译的时候,Kernel Features —> Preemption Model选项实际上可以让我们编译内核的时候,是倾向于支持吞吐,还是支持响应

preemption model:选择内核的抢占模型,影响调度算法

  1. No Forced Preemption (Server): 不强制抢占,更在意吞吐,支撑比较大的连接等。
  2. Voluntary kernel preemption (Desktop): 内核不能抢占。
  3. Preemtible Kernel(low-latency desktop): 内核都可以抢占,更在意响应,滑动触摸屏等操作需要立刻响应。

I/O消耗型 vs. CPU消耗型

  • IO bound: CPU利用率低,进程的运行效率主要受限于I/O速度;
  • tips: IO 消耗型对拿到CPU(延迟)比较敏感,应该被优先调度。一般需要CPU的响应速度快,即优先级要求比较高。
  • CPU bound: 多数时间花在CPU上面(做运算);

调度算法: 策略 + 优先级

早期2.6调度器:优先级数组 和 Bitmaps

  • 0~ 139: 在内核空间, 把整个Linux优先级划分为0~139,数字越小,优先级越高。用户空间设置时,是反过来的。
  • 某个优先级有TASK_RUNNING进程,响应bit设置1。
  • 调度第一个bitmap设置为1的进程

linux内核进程调度

SCHED_FIFO、SCHED_RR

实时(RT)进程调度策略: 0~99采用的RT,100~139是非RT的。

  • SCHED_FIFO: 不同优先级按照优先级高的先跑到睡眠,优先级低的再跑;同等优先级先进先出。
  • SCHED_RR:不同优先级按照优先级高的先跑到睡眠,优先级低的再跑;同等优先级轮转。

linux内核进程调度

当所有的SCHED_FIFO和SCHED_RR都运行至睡眠态,就开始运行 100~139之间的 普通task_struct。这些进程讲究 nice,

SCHED_NORMAL

非实时进程的调度和动态优先级:

早期内核2.6的调度器,100对应nice值为 -20,139对应nice值为19。对于普通进程,优先级高不会形成对优先级低的绝对优势,并不会阻塞优先级低的进程拿到时间片。
普通进程在不同优先级之间进行轮转,nice值越高,优先级越低。此时优先级的具体作用是:

  1. 时间片。优先级高的进程可以得到更多时间片。
  2. 抢占。从睡眠状态到醒来,可以优先去抢占优先级低的进程。

Linux根据睡眠情况,动态奖励和惩罚。 越睡,优先级越高。想让CPU消耗型进程和IO消耗型进程竞争时,IO消耗型的进程可以竞争过CPU消耗型。

rt的门限

Linux内核在period的时间里RT最多只能跑runtime的时间。
在参数 /proc/sys/kernel/sched_rt_period_us 和 /proc/sys/kernel/sched_rt_runtime_us 中设置。单位:微秒。

CFS 完全公平调度

后期,Linux对普通进程调度,提供了 完全公平调度算法,每次都会调vruntime最小的进程调度。

红黑树,左边节点小于右边节点的值,运行到目前为止 (vruntime最小)的进程,同时考虑了CPU/IO和nice。

linux内核进程调度

linux内核进程调度

vruntime: virtual runtime,= pruntime/weight 权重* 系数。

随着时间运行,分子pruntime变大,vruntime也就变大,优先级变低。喜欢睡眠、IO消耗型的进程,分子小。nice值低的,分母大。但是RT的进程,优先级高于所有普通的进程。

红黑树实现的CFS,用分子pruntime来照顾 睡眠情况,用分母来照顾nice值。

当进程里fork了多个线程,每个线程的 调度策略都可以不同,优先级可以不同。原因显然。

酷客网相关文章:

赞(0)

评论 抢沙发

评论前必须登录!