2012年1月1日星期日
2011已经过去
今天已经步入了新的一年。回首一下，想不到“世界末日”的2012年来的这么快。大家各种总结，我也尝试着回忆一下我的这一年。平时觉得自己过的很混乱，每天都感觉都差不多，但是试着回忆一下，却发现这一年经历了这么多事情。
春节刚回到回家，惊闻妈在工地上做事，出了事故，小腿骨被压骨折。回家第一件事情就去跑去躺在医院病床上的妈妈，脚上打着石膏，本来就瘦削的面庞，有明显被疼痛折磨的痕迹。看到妈妈这样的状况，顿时眼泪涌出来。还遇到黑心的老板，不愿意赔偿，朴实的老百姓，哪有什么公平可言啊。在过年的前一天，妈妈勉强出院回家过春节。妈妈已经年过半百，还在做着只有二三十岁的年轻人能胜任的体力活，不管风吹日晒，酷暑严寒，都需要在高空作业。曾经弱弱的和爸妈说，您歇着吧，不要再出来干这种活儿了。爸妈总是摇头说，你还没有参加工作，虽然你上学不需要什钱，但是，家里的日常支出也是不小的负担的，等你工作了再说吧。我语塞。
开学后，快要面临毕业的事情，开始找实习。幸运的进入创新工场实习。在李开复名声的召感下，非常憧憬和珍惜这份实习。实习过程中经历了很多，加班、团队、创业、产品、开发等等，很多东西都让我有了比较直观的认识，并且亲身参与其中。后来还换了几次实习，分别到阿里和微软，算是各种类型的公司文化都有体验，实习让我收获很多，也让我失去了很多。在实习中遇到的人，现在想想都感觉很美好，谢谢我遇到的每一个人。世界很大也很复杂，圈子很小也很单纯...
六月三十号开始我不再单身，开始进入我这个年龄的人都期待了无数遍的恋爱生活。可能是命运，也是实习给我的馈赠。在一起也有半年的时间，不是算长也不算短，也经历过很多事情。出去玩、搬家、做饭、甜蜜、吵架、抚慰。有付出，也有幸福。有压力，也很舒服。在恋爱中，很容易让一个人变得透明，所有的性格和脾气都可以暴露无遗，甚至被放大。两个人走到一起不容易，一直走下去却更不容易。不成熟的我，给我们的感情带来很大的影响。我也知道后面的路很长，摩擦一定还会有，期望我们能好好走下去。期望能到修成正果的那一天。
8月的一天晚上，我和正常的时间一样给家里打电话，却感受到电话那头传来异样的气氛。我一直追问下去，果然，家里有事，事情远远超出我能承受的范围--爸爸可能得了肺癌。晴天霹雳一般，我买了第二天的票赶上了回家的火车。在省肿瘤医院，爸爸的检查结果出来，确诊为中晚期。妈妈从家里打来电话，妈妈在那头号啕大哭，我也在这边泪如雨下，却极力控制自己的声音...命运，你为什么这么做弄人，我可怜的爸爸，从我记事起，就一直忙忙碌碌，为了我们找个家，为我们这几个孩子，什么不能吃的苦都吃了，什么不能受的委屈都受了，什么样的穷日子也都过了，在我即将成人独立的时候，在我即将有机会让爸妈能够停下来的时候，在我爸爸身体慢慢虚弱的时候，却还要然这样恐怖的恶魔来这么我爸和我的家人，难道我们家受的苦还不够吗，命运要这样来作弄，多么希望命运之神突然发现自己弄错了，只是不小心开的一个玩笑，明天就告诉我这一切都是假的。我甚至到目前都不敢接受这样的事实，无数次从梦中惊醒，说真的，我害怕了。“子欲养而亲不待”，爸！我是不孝的，这么多年来，我从来没有孝敬过您，一直觉得以后有的是机会，等我挣钱再来孝敬您，可是发现可能连这样的机会都可能会没有了。可怕的恶魔，你为什么要这个时候出现，我不解...我不解...
因为要找工作，我回到北京找工作。在实习的同时，准备简历，网上海投简历，接下来，奔跑各地赶场笔试，面试。有时候在同一天参加六七个面试，而且在不同的地方，几乎一天能踏遍北京东西南北。好多天下来，简历或者面试之后就石沉大海，疲惫和沮丧几乎都要把我击垮。谢谢yq在我身边陪伴和鼓励，谢谢同学之间的相互帮助，我们都走过来了。找工作尘埃落定，本来就不胖的我，也掉下来几斤肉。
2011年，对我来说，是噩梦般的，也是有惊喜的。命运2011年给我的一切我都接受，2011都过去了，新2012也来到了，祈祷2012命运的垂青，让我爸爸好起来，期望我的家人都健康幸福！
春节刚回到回家，惊闻妈在工地上做事，出了事故，小腿骨被压骨折。回家第一件事情就去跑去躺在医院病床上的妈妈，脚上打着石膏，本来就瘦削的面庞，有明显被疼痛折磨的痕迹。看到妈妈这样的状况，顿时眼泪涌出来。还遇到黑心的老板，不愿意赔偿，朴实的老百姓，哪有什么公平可言啊。在过年的前一天，妈妈勉强出院回家过春节。妈妈已经年过半百，还在做着只有二三十岁的年轻人能胜任的体力活，不管风吹日晒，酷暑严寒，都需要在高空作业。曾经弱弱的和爸妈说，您歇着吧，不要再出来干这种活儿了。爸妈总是摇头说，你还没有参加工作，虽然你上学不需要什钱，但是，家里的日常支出也是不小的负担的，等你工作了再说吧。我语塞。
开学后，快要面临毕业的事情，开始找实习。幸运的进入创新工场实习。在李开复名声的召感下，非常憧憬和珍惜这份实习。实习过程中经历了很多，加班、团队、创业、产品、开发等等，很多东西都让我有了比较直观的认识，并且亲身参与其中。后来还换了几次实习，分别到阿里和微软，算是各种类型的公司文化都有体验，实习让我收获很多，也让我失去了很多。在实习中遇到的人，现在想想都感觉很美好，谢谢我遇到的每一个人。世界很大也很复杂，圈子很小也很单纯...
六月三十号开始我不再单身，开始进入我这个年龄的人都期待了无数遍的恋爱生活。可能是命运，也是实习给我的馈赠。在一起也有半年的时间，不是算长也不算短，也经历过很多事情。出去玩、搬家、做饭、甜蜜、吵架、抚慰。有付出，也有幸福。有压力，也很舒服。在恋爱中，很容易让一个人变得透明，所有的性格和脾气都可以暴露无遗，甚至被放大。两个人走到一起不容易，一直走下去却更不容易。不成熟的我，给我们的感情带来很大的影响。我也知道后面的路很长，摩擦一定还会有，期望我们能好好走下去。期望能到修成正果的那一天。
8月的一天晚上，我和正常的时间一样给家里打电话，却感受到电话那头传来异样的气氛。我一直追问下去，果然，家里有事，事情远远超出我能承受的范围--爸爸可能得了肺癌。晴天霹雳一般，我买了第二天的票赶上了回家的火车。在省肿瘤医院，爸爸的检查结果出来，确诊为中晚期。妈妈从家里打来电话，妈妈在那头号啕大哭，我也在这边泪如雨下，却极力控制自己的声音...命运，你为什么这么做弄人，我可怜的爸爸，从我记事起，就一直忙忙碌碌，为了我们找个家，为我们这几个孩子，什么不能吃的苦都吃了，什么不能受的委屈都受了，什么样的穷日子也都过了，在我即将成人独立的时候，在我即将有机会让爸妈能够停下来的时候，在我爸爸身体慢慢虚弱的时候，却还要然这样恐怖的恶魔来这么我爸和我的家人，难道我们家受的苦还不够吗，命运要这样来作弄，多么希望命运之神突然发现自己弄错了，只是不小心开的一个玩笑，明天就告诉我这一切都是假的。我甚至到目前都不敢接受这样的事实，无数次从梦中惊醒，说真的，我害怕了。“子欲养而亲不待”，爸！我是不孝的，这么多年来，我从来没有孝敬过您，一直觉得以后有的是机会，等我挣钱再来孝敬您，可是发现可能连这样的机会都可能会没有了。可怕的恶魔，你为什么要这个时候出现，我不解...我不解...
因为要找工作，我回到北京找工作。在实习的同时，准备简历，网上海投简历，接下来，奔跑各地赶场笔试，面试。有时候在同一天参加六七个面试，而且在不同的地方，几乎一天能踏遍北京东西南北。好多天下来，简历或者面试之后就石沉大海，疲惫和沮丧几乎都要把我击垮。谢谢yq在我身边陪伴和鼓励，谢谢同学之间的相互帮助，我们都走过来了。找工作尘埃落定，本来就不胖的我，也掉下来几斤肉。
2011年，对我来说，是噩梦般的，也是有惊喜的。命运2011年给我的一切我都接受，2011都过去了，新2012也来到了，祈祷2012命运的垂青，让我爸爸好起来，期望我的家人都健康幸福！
2011年12月16日星期五
在Blogger中添加代码语法高亮
对于一个码农，博客中有代码是不可避免的，语法高亮也是博客的必备功能了。之前在Google App Engine使用Micolog搭建了一个自己的博客系统，那里添加代码高亮插件是十分简单的。因为所有文件都可以自己上传和定义。
具体操作如下：
http://heisencoder.net/2009/01/adding-syntax-highlighting-to-blogger.html
http://yacoding.blogspot.com/2008/05/how-to-add-syntax-highlight-to-blogger.html
- 进入您的相应的博客的后台，选择“模板” or "Templete"；
- 这里可以选择自己喜欢博客整体布局，然后点击“修改Html”；
- 打开了模板的html代码，如果你是网页设计高手，这里您就可以大展身手了。如果您看到这个些密密麻麻的代码，完全晕了，不要紧。找到这样的标签对b:skin。把如下文件中的代码加到
http://syntaxhighlighter.googlecode.com/svn/trunk/Styles/SyntaxHighlighter.css
这里使用Google Code上host的SyntaxHighlighter.css，所以不用自己把里面的代码拷过来粘在这里了。 - 然后在里面找到标签/head，在这之前添加如下代码：
这里是添加syntaxhighlighter的语言javascript文件。 - 最后，找到标签/body，在此标签之前添加如下代码：
这里是让语法高亮处理生效。到这里全部设置已经完成。为了保证您的编辑没有错误，可以首先预览一下，确认无误后再保存。 - 具体的用法是，如果在写文章的过程中需要输入代码段，可以，具体做法如下：在写博客的时候切换到HTML模式，在相应的位置输入，下面是一个例子：
Put your code here...
http://heisencoder.net/2009/01/adding-syntax-highlighting-to-blogger.html
http://yacoding.blogspot.com/2008/05/how-to-add-syntax-highlight-to-blogger.html
2010年10月28日星期四
Test Post by Email
Word press 可以使用邮件发表博文，这里来尝试一下。
使用邮件的方式来写博客，可以间接避开博客地址登陆不上去的问题。关于使用邮件写博客的方法，这里有一个说明文档：http://en.support.wordpress.com/post-by-email/
例如一些常用的标签：
使用邮件的方式来写博客，可以间接避开博客地址登陆不上去的问题。关于使用邮件写博客的方法，这里有一个说明文档：http://en.support.wordpress.com/post-by-email/
例如一些常用的标签：
2010年10月27日星期三
继续发牢骚
看到上一篇博文是在5月17日的，也是因为心情烦乱。今天来到这里，同样是因为心情烦乱。好久了，感觉自己一直处在一个自己不想要的状态上，每天都在想，自己不应该是这样的呢，我的想法就是自己踏实，埋头苦干。可是恰恰相反，而我一直处在一个烦乱的状态，每天都在混日子，一天二十四小时不知道怎么过来的，我真的要好好计划一下了。
今天可以说是一种日子的结束吧，我不知道是应该开心还是应该悲伤。从理性上，我不知道这段时间我都做了些什么，既然都走到了这一步，那就放手吧，继续我的工作，我还有很多事情要做，现在又两个文档需要写，这一个星期已经快过去了，我不能再拖下去了，慢慢的学会专注，好好的做事情吧。不要去想那些痛苦的事情，想了也不能有什么结果，做什么无用功呢？
今天可以说是一种日子的结束吧，我不知道是应该开心还是应该悲伤。从理性上，我不知道这段时间我都做了些什么，既然都走到了这一步，那就放手吧，继续我的工作，我还有很多事情要做，现在又两个文档需要写，这一个星期已经快过去了，我不能再拖下去了，慢慢的学会专注，好好的做事情吧。不要去想那些痛苦的事情，想了也不能有什么结果，做什么无用功呢？
2010年10月25日星期一
2007百度公司招聘试题--尝试解答
在网上看到百度07年的招聘试题，原文在这里，发现大部分不会做，没有一个题目有把握，利用网络资源吧每一个题，都尽可能详细的找到答案，记录在这里。
一、选择题：15 分 共 10 题
1. 在排序方法中，关键码比较次数与记录地初始排列无关的是：
A. Shell 排序 B. 归并排序 C. 直接插入排序 D. 选择排序
解：这一题自己的解答是D，选择排序的比较次数是固定的，要进行(1/2)n*(n-1)次比较。而插入排序，根据原序列的情况不同，比较次数不同，如果远序列是按照从小到大有序的排列，则只需要n此比较就可以；如果最糟的情况下，即逆序排列，则要进行(1/2)n*(n-1)此比较。Shell排序，在本质上可以看成是插入排序，所以也是与数列的初始排列有关的。归并排序，可以设一个这样的例子，一个长度为n的数列，最后一次归并前半部分为和后半部分分别是有序的，若前半部分所有的元素都小于后半部分，这时最后一次归并就只要比较n/2次；另外，最后一次归并前，前部分每个隔一个元素比后半部分的大，这样前后部分的元素交替进入有序数列，这样就要进行n次比较。
2. 以下多线程对 int 型变量x的操作，哪几个需要进行同步：
A. x=y; B. x++; C. ++x; D. x=1;
解：下面是反汇编的代码，从汇编代码中就能看出此题肯定要选BC，A的争议比较大。
x = y;
00411A25 mov eax,dword ptr [y]
00411A28 mov dword ptr [x],eax
x ;
00411A2B mov eax,dword ptr [x]
00411A2E add eax,1
00411A31 mov dword ptr [x],eax
x;
00411A34 mov eax,dword ptr [x]
00411A37 add eax,1
00411A3A mov dword ptr [x],eax
x = 1;
00411A3D mov dword ptr [x],1这个题目，还有非常专业的解释在这里：http://www.parallellabs.com/2010/04/15/atomic-operation-in-multithreaded-application/可以好好看下一
3. 代码
void func()
{
static int val;
…
}
中，变量 val 的内存地址位于：
A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈
4. 同一进程下的线程可以共享以下：
A. stack B. data section C. register set D. thread ID
5. TCP 和 IP 分别对应了 OSI 中的哪几层？
A. Application layer B. Data link layer C. Presentation layer D. Physical layer E. Transport layer F. Session layer G. Network layer
6. short a[100]，sizeof(a) 返回？
A. 2 B. 4 C. 100 D. 200 E. 400
7. 以下哪种不是基于组件的开发技术_____。
A. XPCOM B. XP C. COM D. CORBA
8. 以下代码打印的结果是（假设运行在 i386 系列计算机上）：
字串2
struct st_t
{
int status;
short *pdata;
char errstr[32];
};
st_t st[16];
char *p = (char *)( st[2].errstr + 32 );
printf( "%d", ( p - (char *)(st) ) );
A. 32 B. 114 C. 120 D. 1112
9. STL 中的哪种结构是连续形式的存储：
A. map B. set C. list D. vector
10. 一个栈的入栈序列是 A，B，C，D，E，则栈的不可能的输出序列是：
A. EDCBA B. DECBA C. DCEAB D. ABCDE
二、简答题：20 分，共 2 题
1. （5 分）重复多次 fclose 一个打开过一次的 FILE *fp 指针会有什么结果，并请解释。
考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异常。
2. （15 分）下面一段代码，想在调用 f2(1) 时打印 err1，调用 f2(2) 时打印 err4，但是代码中有一些问题，请做尽可能少的修改使之正确。
1 static int f1( const char *errstr, unsigned int flag ) {
2 int copy, index, len;
3 const static char **__err = { "err1", "err2", "err3", "err4" };
字串2
4
5 if( flag & 0x10000 )
6 copy = 1;
7 index = ( flag & 0x300000 ) >> 20;
8
9 if( copy ) {
10 len = flag & 0xF;
11 errstr = malloc( len );
12 if( errstr = NULL )
13 return -1;
14 strncpy( errstr, __err[index], sizeof( errstr ) );
15 } else
16 errstr = __err + index;
17 }&nbs
p;
18
19 void f2( int c ) {
20 char *err;
21
22 swtch( c ) {
23 case 1:
24 if( f1( err, 0x110004 ) != -1 )
25 printf( err );
26 case 2:
27 if( f2( err, 0x30000D ) != -1 )
28 printf( err );
29 }
30 }
三、编程题：30 分 共 1 题
注意：要求提供完整代码，如果可以编译运行酌情加分。
1. 求符合指定规则的数。
给定函数 d(n) = n + n 的各位之和，n 为正整数，如 d(78) = 78+7+8=93。 这样这个函数可以看成一个生成器，如 93 可以看成由 78 生成。 字串3
定义数 A：数 A 找不到一个数 B 可以由 d(B)=A，即 A 不能由其他数生成。现在要写程序，找出 1 至 10000 里的所有符合数 A 定义的数。
输出：
1
3
…
四、设计题：35 分 共 1 题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲，并记录了可收听这些歌曲的 2^30 条 URL，但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL，如果一个 URL 不可用则不出现在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统有如下需求：
1) 通过 SONG_ID 搜索一首歌的 URL_ID，给出 URL_ID 计数和列表
2) 给定一个 SONG_ID，为其添加一个新的 URL_ID
3) 添加一个新的 SONG_ID
4) 给定一个 URL_ID，将其置为不可用
限制条件：内存占用不超过 1G，单个文件大小不超过 2G，一个目录下的文件数不超过 128 个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
关于多线程中操作的原子性
看到百度07年的一个招聘试题：
看到这个题目，觉得还是没有什么把握，到网上搜到一个篇非常详细的文章，很忍不住要转过来，原文地址是：http://www.parallellabs.com/2010/04/15/atomic-operation-in-multithreaded-application/，希望作者不要介意，看到这个作者写博文相当认真，他的博客都是关于并行计算的，地址在这里。此博文详细的介绍了原子性操作的机制，详细的分析解答了此题目。
以下是转载，转载来自parallellabs.com
------------------------------------------------------------------------------
原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念，它常常用来实现一些同步机制，同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题：1. 多线程程序中对变量的读写操作是否是原子的？2. 多线程程序中对Bit field（位域）的读写操作是否是线程安全的？3. 程序员该如何使用原子操作？
我们先从一道很热门的百度笔试题讲起。很多人讲不清楚其背后的原理，下面我们就来对它进行一下剖析（其实这个题目有点歧义，后面我们会讲到）：
要彻底理解这个问题，我们首先需要从硬件讲起。以常见的X86 CPU来说，根据Intel的参考手册，它基于以下三种机制保证了多核中加锁的原子操作（8.1节）：
（1）Guaranteed atomic operations （注：8.1.1节有详细介绍）
（2）Bus locking, using the LOCK# signal and the LOCK instruction prefix
（3）Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors
这三个机制相互独立，相辅相承。简单的理解起来就是
（1）一些基本的内存读写操作是本身已经被硬件提供了原子性保证（例如读写单个字节的操作）；
（2）一些需要保证原子性但是没有被第（1）条机制提供支持的操作（例如read-modify-write）可以通过使用”LOCK#”来锁定总线，从而保证操作的原子性
（3）因为很多内存数据是已经存放在L1/L2 cache中了，对这些数据的原子操作只需要与本地的cache打交道，而不需要与总线打交道，所以CPU就提供了cache coherency机制来保证其它的那些也cache了这些数据的processor能读到最新的值（关于cache coherency可以参加我的一篇博文）。
那么CPU对哪些（1）中的基本的操作提供了原子性支持呢？根据Intel手册8.1.1节的介绍：
从Intel486 processor开始，以下的基本内存操作是原子的：
• Reading or writing a byte（一个字节的读写）
• Reading or writing a word aligned on a 16-bit boundary（对齐到16位边界的字的读写）
• Reading or writing a doubleword aligned on a 32-bit boundary（对齐到32位边界的双字的读写）
从Pentium processor开始，除了之前支持的原子操作外又新增了以下原子操作：
• Reading or writing a quadword aligned on a 64-bit boundary（对齐到64位边界的四字的读写）
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus（未缓存且在32位数据总线范围之内的内存地址的访问）
从P6 family processors开始，除了之前支持的原子操作又新增了以下原子操作：
• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line（对单个cache line中缓存地址的未对齐的16/32/64位访问）
那么哪些操作是非原子的呢？
Accesses to cacheable memory that are split across bus widths, cache lines, and
page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel®
Atom™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and
Intel486 processors.（说点简单点，那些被总线带宽、cache line以及page大小给分隔开了的内存地址的访问不是原子的，你如果想保证这些操作是原子的，你就得求助于机制（2），对总线发出相应的控制信号才行）。
需要注意的是尽管从P6 family开始对一些非对齐的读写操作已经提供了原子性保障，但是非对齐访问是非常影响性能的，需要尽量避免。当然了，对于一般的程序员来说不需要太担心这个，因为大部分编译器会自动帮你完成内存对齐。
回到最开始那个笔试题。我们先反汇编一下看看它们到底执行了什么操作：
（1）很显然，x=1是原子操作。
因为x是int类型，32位CPU上int占32位，在X86上由硬件直接提供了原子性支持。实际上不管有多少个线程同时执行类似x=1这样的赋值语句，x的值最终还是被赋的值（而不会出现例如某个线程只更新了x的低16位然后被阻塞，另一个线程紧接着又更新了x的低24位然后又被阻塞，从而出现x的值被损坏了的情况）。
（2）再来看x++和++x。
其实类似x++, x+=2, ++x这样的操作在多线程环境下是需要同步的。因为X86会按三条指令的形式来处理这种语句：从内存中读x的值到寄存器中，对寄存器加1，再把新值写回x所处的内存地址（见上面的反汇编代码）。
例如有两个线程，它们按照如下顺序执行（注意读x和写回x是原子操作，两个线程不能同时执行）：
time Thread 1 Thread 2
0 load eax, x
1 load eax, x
2 add eax, 1 add eax, 1
3 store x, eax
4 store x, eax
我们会发现最终x的值会是1而不是2，因为Thread 1的结果被覆盖掉了。这种情况下我们就需要对x++这样的操作加锁（例如Pthread中的mutex）以保证同步，或者使用一些提供了atomic operations的库（例如Windows API中的atomic库，Linux内核中的atomic.h，Java concurrent库中的Atomic Integer，C++0x中即将支持的atomic_int等等，这些库会利用CPU提供的硬件机制做一层封装，提供一些保证了原子性的API）。
（3）最后来看看x=y。
在X86上它包含两个操作：读取y至寄存器，再把该值写入x。读y的值这个操作本身是原子的，把值写入x也是原子的，但是两者合起来是不是原子操作呢？我个人认为x=y不是原子操作，因为它不是不可再分的操作。但是它需要不需要同步呢？其实问题的关键在于程序的上下文。
例如有两个线程，线程1要执行{y = 1; x = y;}，线程2要执行{y = 2; y = 3;}，假设它们按如下时间顺序执行：
time Thread 1 Thread 2
0 store y, 1
1 store y, 2
2 load eax, y
3 store y, 3
4 store x, eax
那么最终线程1中x的值为2，而不是它原本想要的1。我们需要加上相应的同步语句确保y = 2不会在线程1的两条语句之间发生。y = 3那条语句尽管在load y和store x之间执行，但是却不影响x=y这条语句本身的语义。所以你可以说x=y需要同步，也可以说x=y不需要同步，看你怎么理解题意了。x=1是否需要同步也是一样的道理，虽然它本身是原子操作，但是如果有另一个线程要读x=1之后的值，那肯定也需要同步，否则另一个线程读到的就是x的旧值而不是1了。
Bit field常用来高效的存储有限位数的变量，多用于内核/底层开发中。一般来说，对同一个结构体内的不同bit成员的多线程访问是无法保证线程安全的。
例如Wikipedia中的如下例子：
两个线程分别对my_foo.flag和my_foo.counter进行读写操作，但是即使有上面的加锁方式仍然不能保证它是线程安全的。原因在于不同的成员在内存中的具体排列方式“跟Byte Order、Bit Order、对齐等问题都有关，不同的平台和编译器可能会排列得很不一样，要编写可移植的代码就不能假定Bit-field是按某一种固定方式排列的”[3]。而且一般来讲CPU对内存操作的最小单位是word（X86的word是16bits），而不是1bit。这就是说，如果my_foo.flag和my_foo.counter存储在同一个word里，CPU在读写任何一个bit member的时候会同时把两个值一起读进寄存器，从而造成读写冲突。这个例子正确的处理方式是用一个mutex同时保护my_foo.flag和my_foo.counter，这样才能确保读写是线程安全的。
在C++0x草案中对bit field是这样定义的：
连续的多个非0bit的bit fields是属于同一个memory location的；长度为0bit的bit field会把占单独的一个memory location。对同一个memory location的读写不是线程安全的；对不同memory location的读写是线程安全的。
例如在下图的例子中bf1和bf2是同一个memory location，bf3是一个单独的memory location，bf4是一个单独的memory location：
这里有一个因为Bit field不是线程安全所导致的一个Linux内核中的Bug。
引用一下Pongba的总结：
一般情况下程序员不需要跟CPU提供的原子操作直接打交道，所以只需要选择语言或者平台提供的atomic API即可。而且使用封装好了的API还有一个好处是它们常常还提供了诸如compare_and_swap，fetch_and_add这样既有读又有写的较复杂操作的封装。
常见的API如下：
Windows上InterlockedXXXX的API
GNU/Linux上linux kernel中atomic_32.h
GCC中的Atomic Builtins (__sync_fetch_and_add()等)
Java中的java.util.concurrent.atomic
C++0x中的atomic operation
Intel TBB中的atomic operation
[1] 关于变量操作的原子性(atomicity)FAQ
[2] http://en.wikipedia.org/wiki/Atomic_operation
[3] 关于内存对齐、bit field等 –《Linux C编程一站式学习》
[4] Do you need mutex to protect an ‘int’?
[5] C++ Concurrency in Action
[6] Multithreaded simple data type access and atomic variables
-------------------------------------------------------------------------------------------
转载到这里结束
allellabs.com
以下多线程对 int 型变量x的操作，哪几个需要进行同步：
A. x=y; B. x++; C. ++x; D. x=1;
看到这个题目，觉得还是没有什么把握，到网上搜到一个篇非常详细的文章，很忍不住要转过来，原文地址是：http://www.parallellabs.com/2010/04/15/atomic-operation-in-multithreaded-application/，希望作者不要介意，看到这个作者写博文相当认真，他的博客都是关于并行计算的，地址在这里。此博文详细的介绍了原子性操作的机制，详细的分析解答了此题目。
以下是转载，转载来自parallellabs.com
------------------------------------------------------------------------------
多线程程序中操作的原子性
0. 背景
原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念，它常常用来实现一些同步机制，同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题：1. 多线程程序中对变量的读写操作是否是原子的？2. 多线程程序中对Bit field（位域）的读写操作是否是线程安全的？3. 程序员该如何使用原子操作？
1. 多线程环境下对变量的读写操作是否是原子的？
我们先从一道很热门的百度笔试题讲起。很多人讲不清楚其背后的原理，下面我们就来对它进行一下剖析（其实这个题目有点歧义，后面我们会讲到）：
以下多线程对int型变量x的操作，哪几个需要进行同步：（ ）
A. x=y; B. x++; C. ++x; D. x=1;
要彻底理解这个问题，我们首先需要从硬件讲起。以常见的X86 CPU来说，根据Intel的参考手册，它基于以下三种机制保证了多核中加锁的原子操作（8.1节）：
（1）Guaranteed atomic operations （注：8.1.1节有详细介绍）
（2）Bus locking, using the LOCK# signal and the LOCK instruction prefix
（3）Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors
这三个机制相互独立，相辅相承。简单的理解起来就是
（1）一些基本的内存读写操作是本身已经被硬件提供了原子性保证（例如读写单个字节的操作）；
（2）一些需要保证原子性但是没有被第（1）条机制提供支持的操作（例如read-modify-write）可以通过使用”LOCK#”来锁定总线，从而保证操作的原子性
（3）因为很多内存数据是已经存放在L1/L2 cache中了，对这些数据的原子操作只需要与本地的cache打交道，而不需要与总线打交道，所以CPU就提供了cache coherency机制来保证其它的那些也cache了这些数据的processor能读到最新的值（关于cache coherency可以参加我的一篇博文）。
那么CPU对哪些（1）中的基本的操作提供了原子性支持呢？根据Intel手册8.1.1节的介绍：
从Intel486 processor开始，以下的基本内存操作是原子的：
• Reading or writing a byte（一个字节的读写）
• Reading or writing a word aligned on a 16-bit boundary（对齐到16位边界的字的读写）
• Reading or writing a doubleword aligned on a 32-bit boundary（对齐到32位边界的双字的读写）
从Pentium processor开始，除了之前支持的原子操作外又新增了以下原子操作：
• Reading or writing a quadword aligned on a 64-bit boundary（对齐到64位边界的四字的读写）
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus（未缓存且在32位数据总线范围之内的内存地址的访问）
从P6 family processors开始，除了之前支持的原子操作又新增了以下原子操作：
• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line（对单个cache line中缓存地址的未对齐的16/32/64位访问）
那么哪些操作是非原子的呢？
Accesses to cacheable memory that are split across bus widths, cache lines, and
page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel®
Atom™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and
Intel486 processors.（说点简单点，那些被总线带宽、cache line以及page大小给分隔开了的内存地址的访问不是原子的，你如果想保证这些操作是原子的，你就得求助于机制（2），对总线发出相应的控制信号才行）。
需要注意的是尽管从P6 family开始对一些非对齐的读写操作已经提供了原子性保障，但是非对齐访问是非常影响性能的，需要尽量避免。当然了，对于一般的程序员来说不需要太担心这个，因为大部分编译器会自动帮你完成内存对齐。
回到最开始那个笔试题。我们先反汇编一下看看它们到底执行了什么操作：
01 | x = y; |
02 | mov eax,dword ptr [y] |
03 | mov dword ptr [x],eax |
04 |
05 | x++; |
06 | mov eax,dword ptr [x] |
07 | add eax,1 |
08 | mov dword ptr [x],eax |
09 |
10 | ++x; |
11 | mov eax,dword ptr [x] |
12 | add eax,1 |
13 | mov dword ptr [x],eax |
14 |
15 | x = 1; |
16 | mov dword ptr [x],1 |
（1）很显然，x=1是原子操作。
因为x是int类型，32位CPU上int占32位，在X86上由硬件直接提供了原子性支持。实际上不管有多少个线程同时执行类似x=1这样的赋值语句，x的值最终还是被赋的值（而不会出现例如某个线程只更新了x的低16位然后被阻塞，另一个线程紧接着又更新了x的低24位然后又被阻塞，从而出现x的值被损坏了的情况）。
（2）再来看x++和++x。
其实类似x++, x+=2, ++x这样的操作在多线程环境下是需要同步的。因为X86会按三条指令的形式来处理这种语句：从内存中读x的值到寄存器中，对寄存器加1，再把新值写回x所处的内存地址（见上面的反汇编代码）。
例如有两个线程，它们按照如下顺序执行（注意读x和写回x是原子操作，两个线程不能同时执行）：
time Thread 1 Thread 2
0 load eax, x
1 load eax, x
2 add eax, 1 add eax, 1
3 store x, eax
4 store x, eax
我们会发现最终x的值会是1而不是2，因为Thread 1的结果被覆盖掉了。这种情况下我们就需要对x++这样的操作加锁（例如Pthread中的mutex）以保证同步，或者使用一些提供了atomic operations的库（例如Windows API中的atomic库，Linux内核中的atomic.h，Java concurrent库中的Atomic Integer，C++0x中即将支持的atomic_int等等，这些库会利用CPU提供的硬件机制做一层封装，提供一些保证了原子性的API）。
（3）最后来看看x=y。
在X86上它包含两个操作：读取y至寄存器，再把该值写入x。读y的值这个操作本身是原子的，把值写入x也是原子的，但是两者合起来是不是原子操作呢？我个人认为x=y不是原子操作，因为它不是不可再分的操作。但是它需要不需要同步呢？其实问题的关键在于程序的上下文。
例如有两个线程，线程1要执行{y = 1; x = y;}，线程2要执行{y = 2; y = 3;}，假设它们按如下时间顺序执行：
time Thread 1 Thread 2
0 store y, 1
1 store y, 2
2 load eax, y
3 store y, 3
4 store x, eax
那么最终线程1中x的值为2，而不是它原本想要的1。我们需要加上相应的同步语句确保y = 2不会在线程1的两条语句之间发生。y = 3那条语句尽管在load y和store x之间执行，但是却不影响x=y这条语句本身的语义。所以你可以说x=y需要同步，也可以说x=y不需要同步，看你怎么理解题意了。x=1是否需要同步也是一样的道理，虽然它本身是原子操作，但是如果有另一个线程要读x=1之后的值，那肯定也需要同步，否则另一个线程读到的就是x的旧值而不是1了。
2. 对Bit field（位域）的读写操作是否是线程安全的？
Bit field常用来高效的存储有限位数的变量，多用于内核/底层开发中。一般来说，对同一个结构体内的不同bit成员的多线程访问是无法保证线程安全的。
例如Wikipedia中的如下例子：
01 | struct foo { |
02 | int flag : 1; |
03 | int counter : 15; |
04 | }; |
05 |
06 | struct foo my_foo; |
07 |
08 | /* ... */ |
09 |
10 | /* in thread 1 */ |
11 |
12 | pthread_mutex_lock(&my_mutex_for_flag); |
13 | my_foo.flag = !my_foo.flag; |
14 | pthread_mutex_unlock(&my_mutex_for_flag); |
15 |
16 | /* in thread 2 */ |
17 |
18 | pthread_mutex_lock(&my_mutex_for_counter); |
19 | ++my_foo.counter; |
20 | pthread_mutex_unlock(&my_mutex_for_counter); |
两个线程分别对my_foo.flag和my_foo.counter进行读写操作，但是即使有上面的加锁方式仍然不能保证它是线程安全的。原因在于不同的成员在内存中的具体排列方式“跟Byte Order、Bit Order、对齐等问题都有关，不同的平台和编译器可能会排列得很不一样，要编写可移植的代码就不能假定Bit-field是按某一种固定方式排列的”[3]。而且一般来讲CPU对内存操作的最小单位是word（X86的word是16bits），而不是1bit。这就是说，如果my_foo.flag和my_foo.counter存储在同一个word里，CPU在读写任何一个bit member的时候会同时把两个值一起读进寄存器，从而造成读写冲突。这个例子正确的处理方式是用一个mutex同时保护my_foo.flag和my_foo.counter，这样才能确保读写是线程安全的。
在C++0x草案中对bit field是这样定义的：
连续的多个非0bit的bit fields是属于同一个memory location的；长度为0bit的bit field会把占单独的一个memory location。对同一个memory location的读写不是线程安全的；对不同memory location的读写是线程安全的。
例如在下图的例子中bf1和bf2是同一个memory location，bf3是一个单独的memory location，bf4是一个单独的memory location：
这里有一个因为Bit field不是线程安全所导致的一个Linux内核中的Bug。
引用一下Pongba的总结：
所以，如果你的多个bitfields是连续的，同时又想要无冲突的读取它们，有两种做法，一是在中间用0大小bitfield隔开，但这种做法实际上就消除了bitfield的节省内存的初衷，因为为了使它们不冲突，至少被隔开的两个bitfield肯定不可能共享byte了。另一种做法当然就是用锁了。
3. 程序员该怎么用Atomic操作？
一般情况下程序员不需要跟CPU提供的原子操作直接打交道，所以只需要选择语言或者平台提供的atomic API即可。而且使用封装好了的API还有一个好处是它们常常还提供了诸如compare_and_swap，fetch_and_add这样既有读又有写的较复杂操作的封装。
常见的API如下：
Windows上InterlockedXXXX的API
GNU/Linux上linux kernel中atomic_32.h
GCC中的Atomic Builtins (__sync_fetch_and_add()等)
Java中的java.util.concurrent.atomic
C++0x中的atomic operation
Intel TBB中的atomic operation
4. 参考文献：
[1] 关于变量操作的原子性(atomicity)FAQ
[2] http://en.wikipedia.org/wiki/Atomic_operation
[3] 关于内存对齐、bit field等 –《Linux C编程一站式学习》
[4] Do you need mutex to protect an ‘int’?
[5] C++ Concurrency in Action
[6] Multithreaded simple data type access and atomic variables
-------------------------------------------------------------------------------------------
转载到这里结束
allellabs.com
订阅：
博文 (Atom)