Chinaunix首页 | 论坛 | 博客
  • 博客访问: 254363
  • 博文数量: 37
  • 博客积分: 480
  • 博客等级: 下士
  • 技术积分: 443
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-13 12:36
文章分类
文章存档

2013年(8)

2012年(29)

分类:

2012-10-23 08:11:44

原文地址:linux内核调度算法 作者:vangoghiscoding

 
linux内核调度算法
 

 

 

linux内核调度算法(1)--快速找到最高优先级进程

为什么要了解内核的调度策略呢?呵呵,因为它值得我们学习,不算是废话吧。内核调度程序很先进很强大,管理你的LINUX上跑的大量的乱七八糟的进程,同时还保持着对用户操作的高灵敏响应,如果可能,为什么不把这种思想放到自己的应用程序里呢?或者,有没有可能更好的实现自己的应用,使得操作系统能够以自己的意志来分配资源给自己的进程?

带着这两个问题来看看KERNEL。首先回顾上我们开发应用程序,基本上就两种类型,1、IO消耗型:比如hadoop上的trunk服务,很明显它的消耗主要在IO上,包括网络IO磁盘IO等等。2、CPU消耗型,比如mapreduce或者其他的需要对大量数据进行计算处理的组件,就象对高清视频压缩成适合手机观看分辨率的进程,他们的消耗主要在CPU上。当两类进程都在一台SERVER上运行时,操作系统会如何调度它们呢?现在的服务器都是SMP多核的,那么一个进程在多CPU时会来回切换吗?如果我有一个程序,既有IO消耗又有CPU消耗,怎么让多核更好的调度我的程序呢?

又多了几个问题。来看看内核调度程序吧,我们先从它的优先队列谈起吧。调度程序代码就在内核源码的kernel/sched.c的schedule函数中。

首先看下面的优先级队列,每一个runqueue都有。runqueue是什么?下面会详细说下,现在大家可以理解为,内核为每一颗CPU分配了一个runqueue,用于维护这颗CPU可以运行的进程。runqueue里,有几个成员是prio_array类型,这个东东就是优先队列,先看看它的定义:

[cpp] view plaincopyprint?struct prio_array {

    unsigned int nr_active; 表示等待执行的进程总数

    unsigned long bitmap[BITMAP_SIZE]; 一个unsigned long在内核中只有32位哈,大家要跟64位OS上的C程序中的long区分开,那个是64位的。那么这个bitmap是干什么的呢?它是用位的方式,表示某个优先级上有没有待处理的队列,是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级,我只需要四位就能表示某个优先级上有没有进程要运行,例如优先级是2和3上有进程,那么就应该是0110.......非常省空间,效率也快,不是吗?

    struct list_head queue[MAX_PRIO]; 与上面的bitmap是对应的,它存储所有等待运行的进程。

};

struct prio_array {

    unsigned int nr_active; 表示等待执行的进程总数

    unsigned long bitmap[BITMAP_SIZE]; 一个unsigned long在内核中只有32位哈,大家要跟64位OS上的C程序中的long区分开,那个是64位的。那么这个bitmap是干什么的呢?它是用位的方式,表示某个优先级上有没有待处理的队列,是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级,我只需要四位就能表示某个优先级上有没有进程要运行,例如优先级是2和3上有进程,那么就应该是0110.......非常省空间,效率也快,不是吗?

    struct list_head queue[MAX_PRIO]; 与上面的bitmap是对应的,它存储所有等待运行的进程。

};

看看BITMAP_SIZE是怎么算出来的:#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

那么,LINUX默认配置(如果你用默认选项编译内核的话)MAX_PRIO是140,就是说一共内核对进程一共定义了140种优先级。等待某个CPU来处理的进程中,可能包含许多种优先级的进程,但,LINUX是个抢占式调度算法的操作系统,就是说,需要调度时一定是找到最高优先级的进程执行。上面的BITMAP_SIZE值根据MAX_PRIO算出来为5,那么bitmap实际是32*5=160位,这样就包含了MAX_PRIO的140位。优先级队列是怎么使用的?看2649行代码:idx = sched_find_first_bit(array->bitmap);这个方法就用来快速的找到优先级最高的队列。看看它的实现可以方便我们理解这个优先级位的设计:

点击(此处)折叠或打开

  1. static inline int sched_find_first_bit(unsigned long *b)

  2. {

  3.     if (unlikely(b[0]))

  4.     return __ffs(b[0]);

  5.     if (unlikely(b[1]))

  6.     return __ffs(b[1]) + 32;

  7.     if (unlikely(b[2]))

  8.     return __ffs(b[2]) + 64;

  9.     if (b[3])

  10.     return __ffs(b[3]) + 96;

  11.     return __ffs(b[4]) + 128;

  12. }
  13. //采用折半的思想查找某一位为一。非常高效的方法。
  14. static inline int __ffs(int x)

  15. {

  16.     int r = 0;

  17.     if (!x)

  18.     return 0;
  19.     //先取低16位,判断是否有1.
  20.     //如果有1,往下走。
  21.     //如果没有1,右移16位
  22.     if (!(x & 0xffff)) {

  23.         x >>= 16;

  24.         r += 16;

  25.     }

  26.     if (!(x & 0xff)) {

  27.         x >>= 8;

  28.         r += 8;

  29.     }

  30.     if (!(x & 0xf)) {

  31.         x >>= 4;

  32.         r += 4;

  33.     }

  34.     if (!(x & 3)) {

  35.         x >>= 2;

  36.         r += 2;

  37.     }

  38.     if (!(x & 1)) {

  39.         x >>= 1;

  40.         r += 1;

  41.     }

  42.     return r;

  43. }

sched_find_first_bit返回值就是最高优先级所在队列的序号,与queue是对应使用的哈,queue = array->queue + idx;这样就取到了要处理的进程队列。这个设计在查找优先级时是非常快的,非常值得我们学习。

阅读(1418) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~