Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1336377
  • 博文数量: 488
  • 博客积分: 161
  • 博客等级: 入伍新兵
  • 技术积分: 5054
  • 用 户 组: 普通用户
  • 注册时间: 2011-07-01 07:37
个人简介

只有偏执狂才能生存

文章分类

全部博文(488)

文章存档

2016年(10)

2015年(112)

2014年(66)

2013年(272)

2012年(28)

分类: LINUX

2013-03-05 18:03:47

     最近几天结合源码看了很多linux进程调度的文章,虽然掌握了个大概,但是越看,细节越多,写这篇文章的信心也就越不足,曾有系列文章叫鼠眼看linux进程调度,很符合我现在的心境,就像盲人摸象,学到一些东西,很惊喜,但是总有一种力不从心的惶恐。但是好久没写博文了,还是写一篇。写的不对的地方,请大家批评指正。

    CPU是一种宝贵的资源,Linux是多任务的OS,这种多任务要求,对于每个任务或者说进程来说,就好像它独占了CPU。想想如果只有一个CPU,但是有80个处于TASK_RUNNING状态的进程,在这八十个进程选择进程,切换进程是多么困难。如果你理解不了这种难度,你可以想想如果你同时有80个女朋友,性格迥异,爱好不同,要做到每个女朋友都认为她自己是你唯一的女友是多么的困难。

   刘明在《Linux 调度器BFS简介》中有个很有意思的比喻,linux 内核调度器就像处境尴尬的主妇,满足孩子对晚餐的要求便有可能伤害到老人的食欲,做出一桌让男女老少都满意的饭菜实在是太难了。Linux是一个通用的操作系统,无法预测运行其上的进程有什么样的特点,就像一家人的口味各不相同,孩子喜欢吃甜,爸爸喜欢吃咸,老人喜欢口味清淡,所以调度器也很为难。

    一般来说根据进程的特点,可以将进程分成几类
1 交互式进程
   这个比较简单了,想想你你使用vi编辑文本,大量的人机交互,进程不断的进入睡眠状态等待你的输入,CPU占用不高但是要求响应迅速,比如你敲了键盘,过了10秒钟才在编辑器上显示出来,这用户体验是多么的糟糕。

2 批处理进程
    最典型的就是编译工程这种进程了,如果我们编译一个大型的工程,我们敲了个make,也许1个小时才能编译成功,但是没有人会两个眼睛盯着屏幕看编译的过程,我们更关心的是编译的结果。对于这种进程就是属于姥姥不疼舅舅不爱的进程,这要他在跑就行了,不必给他太多的关注和资源。

3 实时进程
    实时进程原本的含义是给定的工作要在指定的时间内完成,不要求你多快,但是一定要在指定的时间前完成指定的任务,多用在火箭 导弹类似的精密系统中。这种实时叫做硬实时,对于Linux 这种通用的OS来讲,完全做到硬实时有点强人所难了,中断,磁盘寻道,总线征用 锁,等很多的机制带来了太多的不确定性,很难做到硬实时。

    linux所说的实时进程是软实时,就是尽量的实时,如果做不到,也不会出现毁灭性的后果。比如视频播放器,解码速度有点慢,顶多是视频播放有点卡,用户体验不好,但是不会机毁人亡。

    不同的进程,就用不同的调度策略伺候之,对于实时进程,我们就采用实时调度策略:FIFO or Round Robin(时间片轮转)。对于批处理进程和交互进程,我们采用CFS调度器。在之前的版本,Linux采用O(1)调度器的时候,有复杂的方法识别交互性进程,奖励交互性进程,算法比较复杂,现在采用CFS调度器后,核心思想比较简单“完全公平”,降低了代码复杂度,很好地满足了各种需求。

    先说说实时调度,实时调度有两个维度1 优先级2 调度策略。linux用户程序可以通过调用sched_setscheduler系统调用来设置进程的优先级和调度策略。

    实时进程共有0~99共100种不同的优先级,0优先级最高,99优先级最低,对应100个队列。对于实时进程来说,高优先级实时进程存在,低优先级的实时进程就捞不着CPU资源,普通进程更捞不着CPU资源。
    接下来就是调度策略,一种是FIFO,先进先出,如果最高优先级的进程是FIFO类型,那么他就一直执行,一条路跑到黑,直到进程退出,或者它调用sched_yield主动让出资源,或者突然出现更高优先级的进程横空出世,抢占了它的CPU。另外一种是时间片轮转,假如说最高优先级实时进程队列存在多个进程,当前进程耗尽自己时间片后自动排到队尾,选择同一个队列的队列头部的进程去执行。这些事情是在task_tick_rt函数做的。

    
    前面提到实时进程存在,普通进程完全捞不到CPU资源也不完全对,后来LINUX增加组调度策略后,有/proc/sys/kernel/sched_rt_period_us和/proc/sys/kernel/sched_rt_runtime_us两个参数,这两个参数表示的含义是:在sched_rt_peroid_us的周期内,所有的实时进程运行时间之和不得超过sched_rt_runtime_us。 默认值为1秒和0.95秒换句话说,在1秒的周期以内,所有实时进程运行时间之和不得超过0.95秒,剩下的0.5秒钟留给普通进程。

    对于普通进程的CFS调度器,内容相对比较独立,如果有时间,后面会有专门的博文总结。

2 SMP时代的进程调度

    更要命的是现在进入了多核的时代,纵然不谈服务器的高配置,我的笔记本配置不高,也已经是四核,可见多核计算机已经是满大街了。对于负载的SMP,就引入了新的问题。单核的时候,只有一个CPU,不需要考虑选择几个运行队列,就是一个run queue。但是多核的时候,是建立一个run queue,所有的CPU去run queue上选择摘取可执行的进程,还是每个CPU一个run queue?其实都是可以的。

    1 per cpu run queue
     目前linux 内核采用的是per cpu run queue,每个CPU去自己的run queue 去选择可执行的进程,这样减少  了竞争。其实除了这个好处,还有另外一个甚至更重要的好处,缓存重利用。进程落在这个CPU的运行队列上,经过多次调度后(暂不考虑多CPU的load balance),仍然是同一颗CPU运行这个进程,也许上次运行时的变量 内存还在cache中,如果只有一个运行队列,多个CPU的话,上次执行所在的CPU和这次执行所在的CPU很可能不是同一颗CPU,那么上次执行调入的缓存就完全用不上了。

    2 single run  queue
    所有的CPU使用同一个队列,这也是可以的,有些人觉着太土,因为如果一个CPU 访问run queue的时候,其他的CPU 就不能访问run queue了,一把大锁降低了性能,尤其是当CPU特别多的时候,想想如果你有1024个CPU,然而只有一个运行队列,run queue这个瓶颈就是显而易见的了。

    介绍到这里,很多筒子可能就会说了,那还有啥好纠结的,肯定是per cpu run  queue 更优越。但是实际情况要比理论复杂的多。BFS(Brain Fuck Scheduler ,又称脑残调度器)就是一种单一队列的调度器,这种调度器对于桌面应用来说,效果非常的好。感兴趣的筒子可以阅读《Linux调度器BFS简介》《BFS,Linux桌面的极速未来》

     per cpu run queue也不是完全没有缺点。既然是多个队列,就会有可能不均衡,比如一个CPU忙的要死,另一个CPU无事可做,这种情景本身也是对CPU资源的浪费。内核为了解决这个问题就必须要发起CPU间的负载均衡load balance,两个CPU之间负载均衡,要获取两个run queue的锁,会伤害并发,除此以外,负载均衡本身也消耗CPU资源。

    我们按照我们的硬件常识,如果我有两颗物理CPU,每颗物理CPU有两个核,那么我的CPU就是4核的,每个核又可以通过SMT(Simultaneous Multi-Threading)类似的技术实现多个硬件线程或者叫做Virtual CPU,比如Intel的超线程技术,如果每个核可以实现2个Virtual CPU,那么我的硬件就有8个Virtual CPU。这些Virtual CPU 之间的亲缘关系是不同的。

    为了应对多核多CPU,Linux引进了调度域的概念,其实就是根据的亲缘关系的远近,划分不同的范围。根据亲缘关系的远近从近到远分成四个层次:
1 超线程
同一个核利用超线程技术演化出来的Virtual CPU。我们知道CPU的速度要比内存访问的速度快,如果cache没有命中,CPU在等待内存的时间里面无事可做,这是一种浪费,就切换到其他线程。这样多个线程分时复用一个核。说实话,这个超线程技术我其实并不是特别理解,改天研究下Intel手册看个究竟。

2 同一个物理CPU的不同Core

3 同一个NUMA结点上的不同物理CPU

4 不同NUMA节点上的物理CPU。


    NUMA(非一致性内存系统),CPU和RAM是以结点为单位分组的,同一个CPU访问本结点内的本地RAM代价要比访问其他节点的RAM代价低。CPU亲缘关系越近,他们之间进程迁移的代价越低。比如说,将进程在同一个物理CPU下的两个Core之间迁移,代价要低于不同物理CPU之间的迁移,原因就是一部分cache可以继续使用。

    load balance,就是将进程从一个CPU(广义的CPU)迁移到另一个CPU,如果将进程从一个核的一个超线程域搬到另一个超线程域,没啥关系,因为代价不高,就好像让我从办公楼4楼搬到办公楼3楼,代价很低,但是CPU亲缘关系越远,代价越高,就好像上午还在南京上班,下午让我搬到乌鲁木齐上班,所以这种搬家尽量要少。事实上linux 内核也是这么做的。

    OK,继续我们的调度域:假如我们有两个物理CPU,每个物理CPU有两个Core,每个Core有通过超线程演化出两个Virtual CPU,那么我们看下下面这个图(这个图是从Linux内核SMP负载均衡浅析中拷贝的)

     对于每个virtual CPU,属于一组调度域sched_domain,就像我是位于雨花区的,同时我也是位于南京,我还是江苏的,我还是位于中国的,我隶属的不同区域反应的不过是不同层次看我所处的位置。每个调度域分成多个组,就好像中国分成30多个省级行政单位,每个省级行政单位又分成不同的市,每个市又分成不同的区。

    这还只是普通进程的SMP 调度,想想实时进程,我们每个CPU都有队列,也许CPU-a的最高优先级的实时进程尚不如 CPU-b第二高优先级的实时进程,这时候,需要将CPU-b中的实时进程拽到CPU-a上面执行,不然,会出现低优先级的实时进程先执行的异常情况,这个拽的过程是有pull_rt_task 实现的。

参考文献   
Linux内核SMP负载均衡浅析
2 Linux 进程调度浅析
3 鼠眼看Linux调度器
4 Linux调度器BFS简介
5 BFS,Linux桌面的极速未来

阅读(526) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册