江苏龙网

  1. 主页 > 生活百科 > >

彻底理解Linux 进程调度所有知识点( 三 )

Linux


文章插图
 
所以 O(n) 调度器有如下缺陷：

  • 时间复杂度是 O(n) ， 运行队列中的任务数目越大 ， 调度器的效率就越低 。
  • 实时进程不能及时调度 ， 因为实时进程和普通进程在一个列表中 ， 每次查实时进程时 ， 都需要全部扫描整个列表 ， 所以实时进程不是很“实时” 。
  • SMP 系统不好 ， 因为只有一个 runqueue ， 选择下一个任务时 ， 需要对这个 runqueue 队列进行加锁操作 ， 当任务较多的时候 ， 则在临界区的时间就比较长 ， 导致其余的 CPU 自旋浪费 。
  • CPU空转的现象存在 ， 因为系统中只有一个runqueue ， 当运行队列中的任务少于 CPU 的个数时 ， 其余的 CPU 则是 idle 状态 。
O(1)内核2.6采用了O(1) 调度器 ， 让每个 CPU 维护一个自己的 runqueue ， 从而减少了锁的竞争 。每一个runqueue 运行队列维护两个链表 ， 一个是 active 链表 ， 表示运行的进程都挂载 active 链表中；一个是 expired 链表 ， 表示所有时间片用完的进程都挂载 expired 链表中 。当 acitve 中无进程可运行时 ， 说明系统中所有进程的时间片都已经耗光 ， 这时候则只需要调整 active 和 expired 的指针即可 。每个优先级数组包含140个优先级队列 ， 也就是每个优先级对应一个队列 ， 其中前100个对应实时进程 ， 后40个对应普通进程 。如下图所示：
彻底理解Linux 进程调度所有知识点

文章插图
 
总的来说 O(1) 调度器的出现是为了解决 O(n) 调度器不能解决的问题 ， 但 O(1) 调度器有个问题 ， 一个高优先级多线程的应用会比低优先级单线程的应用获得更多的资源 ， 这就会导致一个调度周期内 ， 低优先级的应用可能一直无法响应 ， 直到高优先级应用结束 。CFS调度器就是站在一视同仁的角度解决了这个问题 ， 保证在一个调度周期内每个任务都有执行的机会 ， 执行时间的长短 ， 取决于任务的权重 。下面详细看下CFS调度器是如何动态调整任务的运行时间 ， 达到公平调度的 。
CFS 调度器CFS是 Completely Fair Scheduler 简称 ， 即完全公平调度器 。CFS 调度器和以往的调度器不同之处在于没有固定时间片的概念 ， 而是公平分配 CPU 使用的时间 。比如：2个优先级相同的任务在一个 CPU 上运行 ， 那么每个任务都将会分配一半的 CPU 运行时间 ， 这就是要实现的公平 。
但现实中 ， 必然是有的任务优先级高 ， 有的任务优先级低 。CFS 调度器引入权重 weight 的概念 ， 用 weight 代表任务的优先级 ， 各个任务按照 weight 的比例分配 CPU 的时间 。比如：2个任务A和B ， A的权重是1024 ， B的权重是2048 ， 则A占 1024/(1024+2048) = 33.3% 的 CPU 时间 ， B占 2048/(1024+2048)=66.7% 的 CPU 时间 。
在引入权重之后 ， 分配给进程的时间计算公式如下：
实际运行时间 = 调度周期 * 进程权重 / 所有进程权重之和
CFS 调度器用nice值表示优先级 ， 取值范围是[-20, 19] ， nice和权重是一一对应的关系 。数值越小代表优先级越大 ， 同时也意味着权重值越大 ， nice值和权重之间的转换关系：
const int sched_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,}; 


推荐阅读


上一篇：自己搭建一个网站需要多少钱

下一篇：没有了