DongHao: 07 2010存档

先上代码,很少,就两个类。

  #include <iostream>

  using namespace std;

  struct Pig
  {
      virtual void call(void)
      {
          cout << "Pig\n";
      }

  };

  struct SmallPig : public Pig
  {
      virtual void call(void)
      {
          cout << "Small Pig\n";
      }
  };

  int main(int argc, char* argv[])
  {
      Pig* p = new SmallPig;
      p->call();
      delete p;
  }

打印出什么?这个简单,了解c++的都能答对:打出 "Small Pig“,因为是虚函数嘛。

好,现在改改Pig类:

  struct Pig
  {
      Pig()
      {
          call();
      }

      ~Pig()
      {
          call();
      }

      virtual void call(void)
      {
          cout << "Pig\n";
      }

  };

再运行,就不是打出3行“Small Pig”了,而是:

Pig

Small Pig

Pig

为什么?因为构造函数和析构函数特殊,在它们里面this指针只能当成自己用(而不是当成子类),所以调用虚函数的结果是调用了父类的实现。

这个问题造成了今天的bug,花了不少时间。其实这个注意事项在《Effective c++》里是有的,我也看过,但是....开发中谁还记得那么多条条框框?还是实际犯错印象比较深刻。

有人问了:如果我把call改成纯虚函数会怎样呢?更郁闷,g++编译的时候就会提示构造函数里的call“找不到实现”!

【转载请注明出处:http://oldblog.donghao.org/uii/ 】

【原理】

现在互联网公司使用的都是多CPU(多核)的服务器了,Linux操作系统会自动把任务分配到不同的处理器上,并尽可能的保持负载均衡。那Linux内核是怎么做到让各个CPU的压力均匀的呢?

做一个负载均衡机制,重点在于:

1. 何时检查并调整负载情况?

2. 如何调整负载?

先看第一个问题。

如果让我这样的庸俗程序员来设计,我第一个想到的就是每隔一段时间检查一次负载是否均衡,不均则调整之,这肯定不是最高效的办法,但肯定是实现上最简单的。实际上,2.6.20版linux kernel的确使用软中断来定时调整多CPU上的压力(调用函数run_rebalance_domains),每秒1次

但每秒一次还是不能满足要求,对很多应用来说,1秒太长了,一秒钟内如果发生负载失衡对很多web应用都是不能接受的,何况其他实时应用。最好kernel能够紧跟进程的变化来调整。

那么,好,我们在进程创建和进程exit的时候检查并调整负载呢?可以,但是不完整,一个进程创建以后如果频繁的睡眠、醒来、睡眠、醒来,它这样折腾对CPU的负载是有影响的,你就不管它了吗?说到底,我们其实关注的是进程是否在使用CPU,而不是它是否诞生了。所以,我们应该在进程睡眠和醒来这两个时间点检查CPU们的负载。

再看第二个问题,怎么调整负载呢?从最繁忙的那个CPU上挪一个进程到最闲的那个CPU上,如果负载还不均衡,就再挪一个进程,如果还不均衡,继续挪....这也是个最笨的方法,但它却真的是linux CPU负载均衡的核心,不过实际的算法在此基础上有很多细化。对于Intel的CPU,压缩在同一个chip上的多核是共享同一个L2的(如下图,里面的一个Processor其实就是一个chip),如果任务能尽可能的分配在同一个chip上,L2 cache就可以继续使用,这对运行速度是有帮助的。所以除非“很不均衡”,否则尽量不要把一个chip上的任务挪到其他chip上。

Intel MUlti-Core CPU

于是,为了应对这种CPU core之间的异质性——在不同的core之间迁移任务,代价不同——Linux kernel引入了sched_domain和sched_group的概念。sched_domain和sched_group的具体原理,可参考刘勃的文章英文资料

【代码剖析】

SMP负载均衡检查或调整在两个内核函数里发生:

1. schedule()。当进程调用了sleep、usleep、poll、epoll、pause时,也就是调用了可能睡去的操作时都会转为内核代码里对schedule()函数的调用。

2. try_to_wake_up() 。说白了就是进程刚才睡了,现在要醒来,那醒来以后跑在哪个CPU上呢?这个选择CPU的过程,也就是负载均衡的过程。

我们先看schedule()的代码,我们忽略函数前面那些和负载均衡无关的代码(本文代码以内核2.6.20版为准):

[kernel/sched.c --> schedule() ]

  3489     cpu = smp_processor_id();
  3490     if (unlikely(!rq->nr_running)) {
  3491         idle_balance(cpu, rq);
  3492         if (!rq->nr_running) {
  3493             next = rq->idle;
  3494             rq->expired_timestamp = 0;
  3495             wake_sleeping_dependent(cpu);
  3496             goto switch_tasks;
  3497         }
  3498     }

每个CPU都有一个运行队列即这里的rq,运行队列里放着该CPU要运行的进程,如果运行队列里没有进程了,就说明当前CPU没有可调度的任务了,那就要调用idle_balance从其它CPU上“平衡”一些(就是挪一些)进程到当前rq里。

再看idle_balance()的实现:

[kernel/sched.c --> idle_balance()]
  2806 /*
  2807  * idle_balance is called by schedule() if this_cpu is about to become
  2808  * idle. Attempts to pull tasks from other CPUs.
  2809  */
  2810 static void idle_balance(int this_cpu, struct rq *this_rq)
  2811 {
  2812     struct sched_domain *sd;
  2813     int pulled_task = 0;
  2814     unsigned long next_balance = jiffies + 60 *  HZ;
  2815
  2816     for_each_domain(this_cpu, sd) {
  2817         unsigned long interval;
  2818
  2819         if (!(sd->flags & SD_LOAD_BALANCE))
  2820             continue;
  2821
  2822         if (sd->flags & SD_BALANCE_NEWIDLE)
  2823             /* If we've pulled tasks over stop searching: */
  2824             pulled_task = load_balance_newidle(this_cpu,
  2825                                 this_rq, sd);
  2826
  2827         interval = msecs_to_jiffies(sd->balance_interval);
  2828         if (time_after(next_balance, sd->last_balance + interval))
  2829             next_balance = sd->last_balance + interval;
  2830         if (pulled_task)
  2831             break;
  2832     }
  2833     if (!pulled_task)
  2834         /*
  2835          * We are going idle. next_balance may be set based on
  2836          * a busy processor. So reset next_balance.
  2837          */
  2838         this_rq->next_balance = next_balance;
  2839 }

从子sched_domain到父sched_domain遍历该CPU对应的domain(2816行),并调用load_balance_newidle,我们继续:

[kernel/sched.c --> load_balance_newidle()]
2730 static int
  2731 load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
  2732 {
  2733     struct sched_group *group;
  2734     struct rq *busiest = NULL;
  2735     unsigned long imbalance;
  2736     int nr_moved = 0;
  2737     int sd_idle = 0;
  2738     cpumask_t cpus = CPU_MASK_ALL;
  2739
  2740     /*
  2741      * When power savings policy is enabled for the parent domain, idle
  2742      * sibling can pick up load irrespective of busy siblings. In this case,
  2743      * let the state of idle sibling percolate up as IDLE, instead of
  2744      * portraying it as NOT_IDLE.
  2745      */
  2746     if (sd->flags & SD_SHARE_CPUPOWER &&
  2747         !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2748         sd_idle = 1;
  2749
  2750     schedstat_inc(sd, lb_cnt[NEWLY_IDLE]);
  2751 redo:
  2752     group = find_busiest_group(sd, this_cpu, &imbalance, NEWLY_IDLE,
  2753                    &sd_idle, &cpus, NULL);
  2754     if (!group) {
  2755         schedstat_inc(sd, lb_nobusyg[NEWLY_IDLE]);
  2756         goto out_balanced;
  2757     }
  2758
  2759     busiest = find_busiest_queue(group, NEWLY_IDLE, imbalance,
  2760                 &cpus);
  2761     if (!busiest) {
  2762         schedstat_inc(sd, lb_nobusyq[NEWLY_IDLE]);
  2763         goto out_balanced;
  2764     }
  2765
  2766     BUG_ON(busiest == this_rq);
  2767
  2768     schedstat_add(sd, lb_imbalance[NEWLY_IDLE], imbalance);
  2769
  2770     nr_moved = 0;
  2771     if (busiest->nr_running > 1) {
  2772         /* Attempt to move tasks */
  2773         double_lock_balance(this_rq, busiest);
  2774         nr_moved = move_tasks(this_rq, this_cpu, busiest,
  2775                     minus_1_or_zero(busiest->nr_running),
  2776                     imbalance, sd, NEWLY_IDLE, NULL);

原来就是我们上面说的“笨办法”,针对当前CPU所属的每个domain(从子到父),找到该sched_domain里最忙的sched_group(2752行),再从该group里找出最忙的运行队列(2759行),最后从该“最忙”运行队列里挑出几个进程到当前CPU的运行队列里。move_tasks函数到底挪多少进程到当前CPU是由第4和第5个参数决定的,第4个参数是指最多挪多少个进程,第5个参数是指最多挪多少“压力”。有了这两个参数限制,就不会挪过头了(即把太多进程挪到当前CPU,造成新的不均衡)。

举个例子,假如有一台8核的机器,两个CPU插槽,也就是两个chip,每个chip上4个核,再假设现在core 4最忙,core 0第二忙,如图:
按照刘勃的文章里的提法,首先是core domain,即Processor 0属于domain 1,Processor 1属于domain 2,其中domain 1包含4个sched_group,每个group对应一个core,如下图(group未画出):
假如现在是 Core 3 在执行idle_balance,则先在domain 1里找最忙的group,找到第二忙的group是core 0(core 4不在domain 1里,所以不会找到它),再从core 0里找最忙的runqueue(运行队列),core 0就一个运行队列,所以直接就是它对应的runqueue了,然后从该runqueue里挪出几个任务到Core 3,这一层domain的均衡做完了。

接着是domain 1的父domain,即 cpu_domain,下图的domain 0:
这个domain 0包含了两个group,每个group对应一个chip,即每个group对应了4个core。
在domain 0找最繁忙的group,显然会找到Processor1 对应的group(因为core 4超忙),那么继续在Processor 1里找最忙的runqueue,于是找到core 4,最后从core 4的runqueue里挑出几个任务挪到core 3,。
这样,整个系统8个核都基本平衡了。

也许有人要问,为什么是从子domain到父domain这样遍历,而不是倒过来,从父到子遍历呢?这是因为子domain通常都是在一个chip上,任务的很多数据在共享的L2 cache上,为了不让其失效,有必要尽量让任务保持在一个chip上。

也许还有人要问:如果core 3本来就是最忙的core,它如果运行idle_balance,会发生什么?答案是什么也不会发生。因为在find_busiest_group函数里,如果发现最忙的是“本CPU”,那么就直接返回NULL,也就不再做任何事。
那core 3岂不永远是最忙的了?呵呵,大家忘了,系统里总有闲的CPU(哪怕是相对比较闲),它总会执行schedule(),就算它从不调用sleep从不睡眠,时钟中断也会迫使其进程切换,进而调用schedule,进而将繁忙CPU的任务揽一部分到自己身上。这样,谁最闲,谁早晚会从忙人身上揽活儿过来,所以忙人不会永远最忙,闲人也不会永远最闲,所以就平等,就均衡了。

再看try_to_wake_up():
[kernel/sched.c --> try_to_wake_up()]
1398 static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
  1399 {
            ......
  1417
  1418     cpu = task_cpu(p);
  1419     this_cpu = smp_processor_id();
  1420
  1421 #ifdef CONFIG_SMP
  1422     if (unlikely(task_running(rq, p)))
  1423         goto out_activate;
  1424
  1425     new_cpu = cpu;
  1426
  1427     schedstat_inc(rq, ttwu_cnt);
  1428     if (cpu == this_cpu) {
  1429         schedstat_inc(rq, ttwu_local);
  1430         goto out_set_cpu;
  1431     }

变量this_cpu和变量cpu有什么区别?变量this_cpu是实际运行这个函数的处理器(“目标处理器”),而变量cpu是进程p在睡眠之前运行的处理器??为了方便我们暂且称之为“源处理器”。当然,这两个处理器也可能是同一个,比如进程p在处理器A上运行,然后睡眠,而运行try_to_wake_up的也是处理器A,其实这样就最好了,进程p在处理器A里cache的数据都不用动,直接让A运行p就行了??这就是1428行的逻辑。

如果this_cpu和cpu不是同一个处理器,那么代码继续:
  1447     if (this_sd) {
  1448         int idx = this_sd->wake_idx;
  1449         unsigned int imbalance;
  1450
  1451         imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
  1452
  1453         load = source_load(cpu, idx);
  1454         this_load = target_load(this_cpu, idx);
  1455
  1456         new_cpu = this_cpu; /* Wake to this CPU if we can */
  1457
  1458         if (this_sd->flags & SD_WAKE_AFFINE) {
  1459             unsigned long tl = this_load;
  1460             unsigned long tl_per_task;
  1461
  1462             tl_per_task = cpu_avg_load_per_task(this_cpu);
  1463
  1464             /*
  1465              * If sync wakeup then subtract the (maximum possible)
  1466              * effect of the currently running task from the load
  1467              * of the current CPU:
  1468              */
  1469             if (sync)
  1470                 tl -= current->load_weight;
  1471
  1472             if ((tl <= load &&
  1473                 tl + target_load(cpu, idx) <= tl_per_task) ||
  1474                 100*(tl + p->load_weight) <= imbalance*load) {
  1475                 /*
  1476                  * This domain has SD_WAKE_AFFINE and
  1477                  * p is cache cold in this domain, and
  1478                  * there is no bad imbalance.
  1479                  */
  1480                 schedstat_inc(this_sd, ttwu_move_affine);
  1481                 goto out_set_cpu;
  1482             }
  1483         }

计算出“目标处理器”和“源处理器”各自的负载(1453行和1454行),再计算“目标处理器”上的每任务平均负载 tl_per_task,最后进行判断:如果“目标处理器”的负载小于“源处理器”的负载且两处理器负载相加都比 tl_per_task小的话,唤醒的进程转为“目标处理器”执行。还有一种情况就是1474行的判断,如果“目标处理器”的负载加上被唤醒的进程的负载后,还比“源处理器”的负载(乘以imbalance后)的小的话,也要把唤醒的进程转为“目标处理器”执行。如果两个因素都不满足,那还是由p进程原来呆的那个CPU(即”源处理器“)继续来处理吧。

有点儿绕,是吧?其实代码虽绕,用意是简单的:

1472行-1473行其实是这样一个用意:如果“目标处理器”的负载很小,小得即使把压力全给到“源处理器”上去也不会超过“源处理器”上的平均任务负载,那么这“目标处理器”的负载是真的很小,值得把p进程挪过来。
1474行的用意则是:如果我们真的把p进程挪到“目标处理器”以后,“目标处理器”的压力也不比“源处理器”大多少,所以,还是值得一挪。

说来说去,还是那个笨原则:把任务从最忙的CPU那儿转到很闲的CPU这儿。

我们已经看过了睡眠和醒来时的内核函数,那么软中断里的run_rebalance_domains又干了些什么呢?其实也很简单,它调用了load_balance函数,而这个函数和load_balance_newidle实现上基本一样,就不累述了。

这里没有探讨进程优先级和进程负载的计算方法,因为太复杂我也不太理解,以后看代码如果有心得,再与大家分享。

为了发挥多核机器的威力,可以用多进程或多线程的办法,由于多进程往往涉及共享内存等IPC问题,所以很多人都倾向于选择多线程,并以此为灵丹妙药。但多线程并非万能,它虽然使用方便,却也有硬伤——线程一死,会牵连其它。孙子曰“不尽知用兵之害者,则不能尽知用兵之利也”,不了解多线程的缺点,也就不能很好的使用它。

我们项目中有一个daemon,功能是转发并处理消息,为了能看到daemon运行的细节,我们还做了一个monitor线程,由该线程通过某个端口提供简单的web服务,这样就可以直接用浏览器查看daemon的运行状态(比如处理了多少消息,丢弃了多少等)。后来,monitor线程出现了一个bug,造成线程挂掉——于是造成了整个daemon挂掉。这下郁闷了,daemon本身是很重要的,而monitor是不那么重要的,现在是次要部分的bug拖累了重要部分的运行

这就是多线程程序的缺陷。如果多个线程做的是同样的事情,那还尚可;但如果多个线程,有的做这件事,有的做那件事,而且事情的重要程度不同,那不重要的线程由于代码错误或其他原因死了,其它的线程——包括执行重要功能的——也只能跟着挂。这在健壮性上肯定是不好的。apache采用多进程应该也是出于这样的考虑,因为它的module可能是用户自己写的,可能并不稳定,但由于module不稳定而挂掉整个apache,显然不应该。当然,apache2开始支持多线程,但即使这样,它默认还是多进程的,并没有整个倒向多线程。

也许有人会说:你代码写好一点,不要有bug,多线程不就没事了吗?首先,我们讨论的是软件健壮性的问题——怎样在坏了一部分以后其它部分还能工作,而不是软件正确性的问题——怎样写正确的代码。不是一个方向的问题,并不矛盾。其次,软件不可能没有bug,我们如果能把不同杀伤性的bug通过不同进程把它们隔开,就能降低影响,这跟挖掘bug的目标是一致的——都是为了增加软件的可用性。

所以,多线程并非万金油。为了健壮性,可以考虑把不同性质的任务分到不同的进程上,再由父进程统一管理。而在这些进程之下,可以再有多线程。当然,这样开发就复杂了。

旧事一则

| | Comments (5) | TrackBacks (0)
现在唐骏文凭造假的事闹得沸沸扬扬。提起唐先生,想起旧事一则。

那时候我还在软件学院读研。一天早上,一个IBM的工程师来学院演讲,主要是讲开发相关的东西,讲座中提到”各位同学将来应该都是以写代码为主“云云;正好当天下午,唐骏也来学院演讲(先生还挺喜欢走穴演讲),讲的是个很虚幻的主题,我已记不大清了,但中间也提到一句”各位软件学院的同学将来是软件业的领军者“云云。当天晚上,有同学在学院论坛上发帖,说:唐骏是好样的,因为他说咱们是领军者,那个IBM的不像话,居然说我们是码农。

人贵有自知之明。软件学院的学生基本都是考计算机系考不上调剂的,或知道自己考不上计算机系而改考的(比如我),这个地方毕业,能找个安安稳稳的写代码的工作就不错了,还他妈的”软件领军者“!?扯淡去吧。

IBM的工程师一句实话,同学们不爱听,唐先生一句马屁,大家还挺入耳,也难怪唐骏这么火——说话这么动听这么广结善缘,捧他的人、爱听他说的人能不多吗?

人们太爱听好听的了,所以现在各类兜售“成功学”的书都很火,什么《我的成功可以复制》啊,《世界因你不同》啊。如果有个老实巴交的工程师站出来告诉大家:”成功只能是老老实实学习,辛辛苦苦工作“,估计没几个人愿听

唐骏本来就是个前微软分部的CEO,一个普普通通的职业经理人,他之所以能火,不也是浮躁的人们追捧的结果吗?
为了在32位机器和64位机器之间传递状态消息,我们给消息格式做了padding:

struct StateMsg
{
uint32_t msgType;
uint32_t padding;
uint64_t msgID;
};

这样,不管是在32位机器上还是64位机器上,消息的大小都是16个字节。开始一切正常,直到后来我们发现有问题:程序里会比较本条状态消息与上一条有什么不同,如果不一样,要清空路由表;如果一样,就说明状态没有变化,于是不做任何操作。而错误出现在我们的消息比较用的是memcmp:

memcmp(oldMsg, newMsg, sizeof(struct StateMsg));

这下连padding也加入比较了,但是padding我们却没有对它赋初值!结果,每条消息都和上一条不同,路由表于是被频繁的清空....
padding本身是用来对齐的,对业务没有任何意义,所以赋值的时候容易忘掉它。教训啊。



====== 2010.12.1 ======

fix这个bug以后,在生产上我们上线了一部分机器,但是发现流量不均匀的问题依旧。照理说路由表被清空的已经不怎么频繁了,怎么还会流量不匀呢?

和架构师一起查这个问题又查了两周,才发现:原来我们的路由表是分段的,每个段都有单独的RoundRobin计数器,一旦路由表清空,这所有段的RoundRobin计数器都置0。线上的服务器很多,我们估算有50台,对应路由表中有400个段!一旦清空,假如来了400个消息,正好均匀分布到400个段上(这有可能发生),于是,这400个消息都从头开始RoundRboin。所以,一次清空路由表的影响,被这个分段机制给恶化了。

分段还是要的,解决方案不变,还是把所有的服务器上的软件都升到fix bug的最新版本。只要“路由表频繁清空”这个根源解掉,后继的问题就都会消失。

找了个周一的下午,和PE一起升级,最后看到流量慢慢恢复均匀了。长达半年的bug终于落地。