Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7093756
  • 博文数量: 3857
  • 博客积分: 6409
  • 博客等级: 准将
  • 技术积分: 15948
  • 用 户 组: 普通用户
  • 注册时间: 2008-09-02 16:48
个人简介

迷彩 潜伏 隐蔽 伪装

文章分类

全部博文(3857)

文章存档

2017年(5)

2016年(63)

2015年(927)

2014年(677)

2013年(807)

2012年(1241)

2011年(67)

2010年(7)

2009年(36)

2008年(28)

分类: LINUX

2013-11-15 10:44:31

    在linux中,支持对称smp的处理器模型,在多处理器的情况下,每个处理器都有自己的一个运行队列,这样就存在着分配不均的情况,有的cpu运行队列很多进程,导致一直很忙,有的cpu运行队列可能很少的进程甚至没有任何运行进程,导致cpu经常处于空转的状态,因此我们需要一种机制,来均衡各个cpu上运行队列的进程数。
1数据结构
为了支持多种多处理器模型,linux提出了调用域及组的概念,一个调用域可以包含其它的调用域或者多个组,一个组通常包含一个或者多个cpu,组的数据结构是:


struct sched_group {
struct sched_group *next;//一个调用域可能会包含多个组,该next用于将//sched_group串到调用域的链表上面
cpumask_t cpumask; //每个group中可能会包含一个或者多个cpu,这里的mask表//示了该group所包含的cpu
unsigned long cpu_power;//通常是cpu的个数
};
下面是调用域的数据结构:
struct sched_domain {
struct sched_domain *parent;//调用域可以被别的调用域所包含,parent指向父调用域
struct sched_group *groups;   //该调用域所包含的组
cpumask_t span;
unsigned long min_interval;//最小的时间间隔,用于检查进行负载均衡操作的时机是否到了
unsigned long max_interval; //同上
unsigned int busy_factor;   //当处理器在不空闲的状态下时,进行负载均衡操作的时间间隔一般也长很多,该factor为其乘数银子
unsigned int imbalance_pct;
unsigned long long cache_hot_time;
unsigned int cache_nice_tries;
unsigned int per_cpu_gain;
int flags;  
unsigned long last_balance;
unsigned int balance_interval;  //负载均衡进行的时间间隔 
unsigned int nr_balance_failed; //负载均衡迁移进程失败的次数
 
};

下图表现出了调用域和组之间的关系,这里我们关注2-cpu的smp和8-cpu的numa;2-cpu的SMP有一个调用域,调用域含两个组,每个组含有一个cpu;8-cpu的numa中包含两个调用域,最底层的调用域代表一个节点,每个最底层的调用域包含四个组,每个组有1个cpu,上层调用域包含两个基础的调用域。

2进行cpu负载均衡的时机
每经过一次时钟中断,scheduler_tick()就调用rebalance_tick()函数,rebalance_tick()函数会去触发cpu运行队列的负载均衡操作。该函数从最底层的调度域开始,一直到最上层的调度域进行检查,对于每个调度域都去查看是否到了调用load_balance()函数的时间,该函数会进行cpu的负载均衡操作。由当前cpu的idle状态和sched_domain的参数来确定调用load_balance()的时间间隔。


3 2-cpu smp和8-cpu numa cpu模型的调用域初始化
对调用域的初始化部分的代码在linux2.6.11版本里面是在arch_init_sched_domains()函数中,被sched_init_smp()函数所调用。
在sched.c中定义了一个数组static struct sched_group sched_group_phys[NR_CPUS];每个数组元素代表一个cpu组。另外定义了一个每cpu变量Sched.c (kernel):static DEFINE_PER_CPU(struct sched_domain, phys_domains);,系统为每个物理cpu都生成了一个调度域数据结构。
对于2-cpu smp的情形来说,其初始化后,调度域和各个组之间的关系是:

在这个里面虽然每个cpu都有个调度域的数据结构,但调度域的groups链表指向的都是同一个group链表

8-cpu numa的组和调度域关系:

4cpu负载均衡的源码解析


  1. 4.1rebalance_tick()  
  2. static void rebalance_tick(int this_cpu, runqueue_t *this_rq,  
  3.                enum idle_type idle)  
  4. {  
  5.     unsigned long old_load, this_load;  
  6.     unsigned long j = jiffies + CPU_OFFSET(this_cpu);  
  7.     struct sched_domain *sd;  
  8.   
  9.     //当前运行队列中可运行的进程数决定了当前运行队列的  
  10.     //cpu_load参数  
  11.     old_load = this_rq->cpu_load;  
  12.     this_load = this_rq->nr_running * SCHED_LOAD_SCALE;  
  13.   
  14.     if (this_load > old_load)  
  15.         old_load++;  
  16.     //将运行队列的cpu load值设定为上一次的cpu_load和本次cpu_load的平均值  
  17.     this_rq->cpu_load = (old_load + this_load) / 2;  
  18.     //从该cpu所属的调度域开始,依次遍历各个更高级的调用域  
  19.     for_each_domain(this_cpu, sd) {  
  20.         unsigned long interval;  
  21.         //在该调度域上不需要做负载均衡  
  22.         if (!(sd->flags & SD_LOAD_BALANCE))  
  23.             continue;  
  24.   
  25.         //若当前cpu不处于空闲状态的话,其调用load_balance的时间间隔会比较长  
  26.         interval = sd->balance_interval;  
  27.         if (idle != SCHED_IDLE)  
  28.             interval *= sd->busy_factor;  
  29.   
  30.         //将时间间隔ms转换成jiffies  
  31.         interval = msecs_to_jiffies(interval);  
  32.         if (unlikely(!interval))  
  33.             interval = 1;  
  34.         //当前的时间戳和上次balance的时间大于其间隔的话,调用load_balance进行负载的均衡  
  35.         if (j - sd->last_balance >= interval) {  
  36.             //load_balance会去寻找最繁忙的cpu组中的最繁忙的cpu,将其进程迁移过来一部分  
  37.             if (load_balance(this_cpu, this_rq, sd, idle)) {  
  38.                 /* We've pulled tasks over so no longer idle */  
  39.                 idle = NOT_IDLE;  
  40.             }  
  41.             sd->last_balance += interval;  
  42.         }  
  43.     }  
  44. }  
  45. 4.2load_balance()  
  46. static int load_balance(int this_cpu, runqueue_t *this_rq,  
  47.             struct sched_domain *sd, enum idle_type idle)  
  48. {  
  49.     struct sched_group *group;  
  50.     runqueue_t *busiest;  
  51.     unsigned long imbalance;  
  52.     int nr_moved;  
  53.   
  54.     spin_lock(&this_rq->lock);  
  55.     schedstat_inc(sd, lb_cnt[idle]);  
  56.     //查找最繁忙的cpu组  
  57.     group = find_busiest_group(sd, this_cpu, &imbalance, idle);  
  58.     //所有的组都是平衡的,不需要做均衡  
  59.     if (!group) {  
  60.         schedstat_inc(sd, lb_nobusyg[idle]);  
  61.         goto out_balanced;  
  62.     }  
  63.     //找到最繁忙的组中最繁忙的运行队列  
  64.     busiest = find_busiest_queue(group);  
  65.     if (!busiest) {  
  66.         schedstat_inc(sd, lb_nobusyq[idle]);  
  67.         goto out_balanced;  
  68.     }  
  69.   
  70.     //最繁忙的运行队列是当前cpu的运行队列,不需要做均衡  
  71.     if (unlikely(busiest == this_rq)) {  
  72.         WARN_ON(1);  
  73.         goto out_balanced;  
  74.     }  
  75.   
  76.     schedstat_add(sd, lb_imbalance[idle], imbalance);  
  77.   
  78.     nr_moved = 0;  
  79.     if (busiest->nr_running > 1) {  
  80.           
  81.         double_lock_balance(this_rq, busiest);  
  82.         //将imbalance个进程从最繁忙的运行队列上迁移到当前的cpu运行队列上面  
  83.         nr_moved = move_tasks(this_rq, this_cpu, busiest,  
  84.                         imbalance, sd, idle);  
  85.         spin_unlock(&busiest->lock);  
  86.     }  
  87.     spin_unlock(&this_rq->lock);  
  88.     //nr_moved == 0,表示没有迁移成功  
  89.     if (!nr_moved) {  
  90.         schedstat_inc(sd, lb_failed[idle]);  
  91.         sd->nr_balance_failed++;  
  92.   
  93.         if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) {  
  94.             int wake = 0;  
  95.   
  96.             spin_lock(&busiest->lock);  
  97.             //active_balance表明该运行队列是否唤醒迁移线程来进行负载均衡,  
  98.             //push_cpu记录了由哪个cpu来唤醒了其迁移线程  
  99.             if (!busiest->active_balance) {  
  100.                 busiest->active_balance = 1;  
  101.                 busiest->push_cpu = this_cpu;  
  102.                 wake = 1;  
  103.             }  
  104.             spin_unlock(&busiest->lock);  
  105.             //唤醒最繁忙运行队列上的迁移内核线程,对进程进行迁移  
  106.             if (wake)  
  107.                 wake_up_process(busiest->migration_thread);  
  108.   
  109.               
  110.             sd->nr_balance_failed = sd->cache_nice_tries;  
  111.         }  
  112.   
  113.           
  114.         if (sd->balance_interval < sd->max_interval)  
  115.             sd->balance_interval++;  
  116.     } else {  
  117.                 sd->nr_balance_failed = 0;  
  118.         //进程迁移成功,重置调用域的balance_interval参数  
  119.         sd->balance_interval = sd->min_interval;  
  120.     }  
  121.   
  122.     return nr_moved;  
  123.   
  124. out_balanced:  
  125.     spin_unlock(&this_rq->lock);  
  126.   
  127.     /* tune up the balancing interval */  
  128.     //不需要进行进程的迁移,适当的加大负载均衡的间隔时间,说明  
  129.     //当前的负载均衡做的比较好  
  130.     if (sd->balance_interval < sd->max_interval)  
  131.         sd->balance_interval *= 2;  
  132.   
  133.     return 0;  
  134. }  
  135. 4.3move_tasks()  
  136. static int move_tasks(runqueue_t *this_rq, int this_cpu, runqueue_t *busiest,  
  137.               unsigned long max_nr_move, struct sched_domain *sd,  
  138.               enum idle_type idle)  
  139. {  
  140.     prio_array_t *array, *dst_array;  
  141.     struct list_head *head, *curr;  
  142.     int idx, pulled = 0;  
  143.     task_t *tmp;  
  144.   
  145.     if (max_nr_move <= 0 || busiest->nr_running <= 1)  
  146.         goto out;  
  147.   
  148.     //先从过期队列上进行进程的迁移,这样对硬件cache的  
  149.     //影响比较小  
  150.     if (busiest->expired->nr_active) {  
  151.         array = busiest->expired;  
  152.         dst_array = this_rq->expired;  
  153.     } else {  
  154.         array = busiest->active;  
  155.         dst_array = this_rq->active;  
  156.     }  
  157.   
  158. new_array:  
  159.     idx = 0;  
  160. skip_bitmap:  
  161.     //从优先级最高的可运行进程开始进行迁移  
  162.     if (!idx)  
  163.         idx = sched_find_first_bit(array->bitmap);  
  164.     else  
  165.         idx = find_next_bit(array->bitmap, MAX_PRIO, idx);  
  166.     if (idx >= MAX_PRIO) {  
  167.         if (array == busiest->expired && busiest->active->nr_active) {  
  168.             array = busiest->active;  
  169.             dst_array = this_rq->active;  
  170.             goto new_array;  
  171.         }  
  172.         goto out;  
  173.     }  
  174.     //找到对应优先级队列的队列末尾的进程,该进程应该是被  
  175.     //放入的最早的一个进程了  
  176.     head = array->queue + idx;  
  177.     curr = head->prev;  
  178. skip_queue:  
  179.     tmp = list_entry(curr, task_t, run_list);  
  180.   
  181.     curr = curr->prev;  
  182.     //判断该进程能否进行迁移  
  183.     if (!can_migrate_task(tmp, busiest, this_cpu, sd, idle)) {  
  184.         //该优先级别的队列是否遍历完毕  
  185.         if (curr != head)  
  186.             goto skip_queue;  
  187.         idx++;  
  188.         //该优先级别的任务队列遍历完毕,去遍历下一个优先级的任务队列  
  189.         goto skip_bitmap;  
  190.     }  
  191.   
  192.       
  193.     schedstat_inc(this_rq, pt_gained[idle]);  
  194.     schedstat_inc(busiest, pt_lost[idle]);  
  195.     //将队列迁移到本地的任务队列  
  196.     pull_task(busiest, array, tmp, this_rq, dst_array, this_cpu);  
  197.     pulled++;  
  198.   
  199.     if (pulled < max_nr_move) {  
  200.         //该优先级别的队列是否遍历完毕  
  201.         if (curr != head)  
  202.             goto skip_queue;  
  203.         idx++;  
  204.         //该优先级别的任务队列遍历完毕,去遍历下一个优先级的任务队列  
  205.         goto skip_bitmap;  
  206.     }  
  207. out:  
  208.     return pulled;  
  209. }  
阅读(563) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~