分类: 2010 May

过度优化导致的线程安全问题

今天无聊看了看<程序员的自我修养>,才明白原来线程安全还别有洞天,它总是一个棘手的问题..即便我们已经用了原子操作,信号量,互斥量,临界区等等手段尽力保证线程的同步,也不一定能保证线程安全.这是由于落后的编译器技术已经无法满足日益增长的并发需求,以致于很多看似无错的代码在优化和并发面前又产生了麻烦..

过度优化

为了说明这个问题,<程序员的自我修养>举了一个很简单的例子:

int global_x = 0; // 两个线程共享的全局变量.

Thread1:  // 线程1的定义                                                           Thread2: // 线程2的定义

lock();                                                                                               lock();

global_x ++;                                                                                   global_x ++;

unlock();                                                                                          unlock();

看上去,因为线程1和线程2在访问global_x时都使用了lock()和unlock()保护,因此global_x ++ 的行为不会被并发破坏,所以在线程1和线程2结束之后,global_x 的值似乎一定是2..但其实,这么理所当然的猜测有可能是错误的.解释如下:

我们知道,一个简单的i=i++的操作在机器执行起来,变成了这么三步:

  1. 取i值到寄存器
  2. 寄存器值加1
  3. 寄存器值写回给i

而不同线程的寄存器是各自独立的,有一种可能导致global_x值不为2的情形如下:

  1. [Thread1] 读global_x值到寄存器R[1]
  2. [Thread1] R[1]++ (R[1]=1)
  3. [Thread2] 读global_x值到寄存器R[2]
  4. [Thread2] R[2]++ (R[2]=1)
  5. [Thread2] 将寄存器R[2]的值写回global_x (global_x=1)
  6. [Thread1] 将寄存器R[2]的值写回global_x (global_x=1)

之所以会出现这样的问题,是因为编译器为了提高global_x的访问速度,将global_x的值放到了某个寄存器里.,这就导致了所谓过度优化的问题..<程序员的自我修养>中还举了一个简单的例子,说的是CPU在执行程序的时候,为了提高效率可能交换指令的执行顺序..同样的,编译器在优化时,也可能会交换毫不相关的两条相邻指令..比如说:

x = y = 0;

x = 1;

z = y;

也许就会被调换成:

x = y = 0;

z = y;

x = 1;

从第1个例子可见,过度优化在单线程时不会有什么问题,而在多线程中可能就将导致一场灾难了..

解决过度优化

为了阻止过度优化,我们可以使用volatile关键字,volatile基本可以做到这么两件事:

  1. 阻止编译器为了提高速度将一个变量缓存在寄存器中而步写回
  2. 阻止编译器调整操作volatile变量的指令顺序

悲剧的是,volatile虽然能够阻止编译器调整顺序,却无法阻止CPU动态调度换序.这使得我们为了线程安全的努力变得异常困难..

从上面的讨论中,我们可以知道,为了保证线程安全,阻止CPU换序是必需的.虽然各种体系结构的CPU都提供了一个barrier指令,用于阻止CPU将该指令之前的指令交换到barrier之后,但这却涉及到了平台的问题,也就意味着,我们写出来的程序不再是可移植的了,这不得不说是一个遗憾..

腾讯一面,三面

终于搞定腾讯实习面试了,走出HR面门口时,已经不抱多少希望了,或者说,有点失望了.回了宿舍总感觉不爽,干脆记下一些感悟好了,当个小小的总结.

先说回一面,一面是3次面试中面试得最开心的了.面试官很亲民,以至于我根本没有想到自己是一个求职者,更多的是交流..我的每一次回答面试官都会加以总结,指出我的误解.面试官提出的问题很少,基本上是叫我说说自己的想法,真的很open的一个好gg,后拉才知道,原来是临时从上海过来的..面试的主要问题有:

  1. vim怎样快速对齐C源文件,Makefile怎么写的.
  2. 画出一个简单应答服务器的流程图,对每个步骤的进一步解释..#$%^&*!~
  3. fork的用法,子进程的功能
  4. select的用法,epoll的用法,select和epoll的区别
  5. 为什么需要cgi,cgi有什么作用
  6. HTTP协议头信息都有些什么参数,怎么了解HTTP协议的
  7. 进程间如何通信,怎么实现多线程共享内存,不加锁如何实现
  8. …(其他一些很细的问题,都忘记了)

一面下来,发现居然误解了cgi好几年,原来知识都停留在一两年前的地步了..其实,一面给自己带来的打击更多的不在技术,而在语言.比如说,我解释select和epoll的区别用了好几分钟,面试官总结时一言两语就挑明了.厚积才能薄发,彻底理解透了,参悟透了,也便明了了.大道至简,多是这番道理..

至于三面,相当悲剧的三面..坐在面试官面前,我纯粹就是一个做报告的..HR抛出问题,我回答问题,一问一答,称得上交流的,少之又少..总而言之,相当的悲剧.

  1. 谈谈自己的人生规划
  2. 给it企业排个名次
  3. 有没有想过自己可能进入google,ms
  4. 说说对其他公司的看法
  5. 说说对腾讯的看法

我都没说些什么,基本上怎么想的,也就怎么答了..或许说了太多腾讯的不足,自己也觉得不大好意思,于是不到10分钟,就夹着尾巴逃出房间了..

真的不抱什么希望了.

—————-

真的真的很感谢女友小陈..在我看来,你早已是我的家人了.

腾讯二面

发一发腾讯二面的面经,攒攒人品.

前天才一面腾讯,一面结束时,面试官说,如果有进一步的消息,会在两三天内联系你..昨天下午一直好无聊,原来等面试通知真的好辛苦.于是拿了本IPC的书看,突然接到一个腾讯深圳总部的电话,还以为是通知今天还是后天到华工面试的,开心着正要问呢,对方就说,假如你现在有空的话,我们就面试吧…瞬间石化了..

由于没有丝毫的准备,在自我介绍时显得有点慌张..好在面试官挺nice的,气定神闲,没有什么不耐烦的意思..

面试官先是问了项目经验,基本上和一面差不多,我唠唠叨叨的一直在说,好在面试官人很好,没有打断我..等我很罗唆地把一个服务器的具体流程实现回顾之后,面试官又问了我进程通信的问题,于是又来到了共享内存的问题,依次把进程间和线程间共享内存的细节描述了一下,然后说了说怎样不加锁的实现内存共享(一面时没答上来)..之后面试官问了我进程调度的问题,也是很常见的上百万请求时服务器的做法,我一笔带过说了说优先级,最高响应比等实现,然后重点介绍了facebook上个月的改进,即从多窗口排队改成一个窗口接收请求,多窗口处理,有空闲窗口时通知接收请求的窗口,接收请求窗口再把请求的进程转给处理窗口.其实也就是将接收请求和处理请求分立开来.据说facebook上个月有一周的单周流量超过了google,所以这种方法应该还是有点道理的吧..之后面试官又问了我c脚本编程的问题,我说我用的是bash,然后自己举了个例子,几句话介绍了用bash怎么实现知道5分钟内有哪些用户登录和注销,然后又介绍了用c语言应该怎么实现,最后比较了一下两种实现的优缺点..之后面试官没再问什么技术性的问题了,主要是问我对linux下API熟不熟悉,然后是问我自学的还是学校教的..之后也许面试官不太确定我自学得是否足够专业,就又问了个很简单的问题, printf, snprintf和fprintf的区别..我答完问题,为了打消面试官的疑虑,又介绍了其他的一些api..然后,面试就结束了,比预定的面试时间多出了快10分钟.

总的下来,结果自己发挥得还不错吧,至少90%的问题都能答到点子上,于是开始YY..过了不到半分钟,突然手机又响了起来,依旧是很nice的面试官,问我想不想去北京上海,我很开心的连连说好..晚上11点多,发现腾讯官网上终于公布二面名单了,好在上面没我名字,终于不用去华工了,一面时排队等了好久..(本来一面是在9:20的,不知道怎么的,到了华工发现自己没有房间号,最终被安排在了11:45左右…..)

不知道什么时候能够接到下一轮的面试通知,继续拿着本unp(volume 2)等吧..

PS: 貌似一面面试官也曾有过疑虑,问我是不是一个人做的项目,有没有copy他人源码,最后还问我怎么了解HTTP协议的..额.只怪我把HTTP协议的RFC编号忘记了..不过一面面试官在静静地听我说了快要5分钟自己的想法之后,突然很大声地说了一句,”说!!!”,把我吓了个半死,误听成了”stop!!!”了..面试官示意我继续后,我就知道有戏了.