合租的室友在帮他的一同学做百度笔试题,并拉上我和另一室友一起做。第一题是关于线程安全的:
现代的处理器提供了compare-and-swap原子操作:
int compare_and_swap(int * pv, const int cv, const int nv);
即比较*pv与cv,如果相等,则把*pv值替换为nv并返回*pv原值,否则返回*pv的值。
请利用上述原子操作实现如下操作:
int inc_if_gt_zero(int * pv);
即如果*pv > 0,则把*pv加1并返回修改后的*pv,否则返回*pv。
结果要线程安全且不使用锁、信号灯、互斥量、临界区或类似机制。
由于看过一些java多线程方面的书籍,也比较熟悉,JDK5的AtomicXXX中incrementAndGet等操作的内部实现也用到compare-and-swap这一原子操作。 下面是我的代码:
int inc_if_gt_zero(int * pv) {
while (true) {
int c = *pv;
if (c <= 0) return c;
int v = compare_and_swap(pv, c, c+1);
if (c == v) {
return c+1;
}
}
}
主要思想是在对pv进行加1操作之前,看它的值有没有改变,没有改变就执行加1操作,否则重试。Doug Lea的经典著作《Concurrent Programming in Java》将这种方法称之为"乐观重试",《Concurrent in Practice》书中则称之为"无等待算法"。对我来说这显而易见,但是我的两个室友却不同意。我的两个室友都是做C++的,都是我的同学,不妨称之为室友A和室友B。室友A直觉上感觉不靠谱,但是找不出原因,室友B则认为完全不对。我没能说服他们,我发现争议的焦点在于对线程安全的理解上,室友A做过多线程编程,他从锁机制的角度来考虑线程安全,因而才对"乐观重试"的方法感觉不靠谱,室友B则基本没有做过,认为对上题来说,输入为2时,必须输出就为3,对他来说,下面的单线程程序就是正确的:
int inc_if_gt_zero(int * pv) {
int c = *pv;
if (c <= 0) return c;
*pv = ++c;
return c;
}
当时我对线程安全的概念也一直没有好好梳理,也无法用语言清晰的表达出我的思想。经过一晚上的思考,思路终于有些清晰了。线程安全的一个重要规则是"as-if-serial"规则,也就是多个线程同时执行操作(在语义上是原子性的操作),看起来就像在单个线程顺序执行这些操作一样。具体来说,以上面的例子为例,假设n个线程,分别表示为T1,T2,...和Tn,同时执行inc_if_gt_zero操作,pv的初始值为1,那么对于线程安全的程序来说它必须保证两个结果:
- n个线程执行完毕后,它必须和单个线程中顺序执行n个inc_if_gt_zero操作之后的内存效果一样,也就是pv的值必须为n+1。
- as-if-serial规则虽然保证多个操作看起来像在单线程中执行一样,但并不保证它们执行的顺序。对于该例子,执行的结果可能是按T1,T2,...Tn的顺序,也可能是按Tn,Tn-1,...T1的顺序,最多只可能为n!种顺序。如果按照T1,T2,...Tn的顺序的操作执行,T1,T2,...Tn的inc_if_gt_zero分别返回2,3,...n+1,如果按Tn,Tn-1,...T1的顺序,T1,T2,...Tn的inc_if_gt_zero分别返回n+1,n,...1。可以得知,线程T1,T2,...Tn的inc_if_gt_zero的返回结果必定是2,3,...,n+1的一个排列,但到底是哪个排列是不确定的。这里并不需要保证inc_if_gt_zero返回时pv的值和返回值相同。
对于该程序的单线程版本,它明显可能违背结果1,最终pv的值可能小于n+1,当然也违背结果2,多个线程执行的结果也可能出现重复的值。对于该程序的关键是保证判断c是否大于0的语句和将pv的值加1的语句之间不能被别的线程给打断,这可以通过锁机制来实现,也可以通过上面说的乐观重试机制来实现,这多少有些类似数据库中的悲观锁和乐观锁。
最后要注意的是,对于该程序的乐观锁版本,如果将最后一句"return c+1",改成"return *pv"是有问题的,这在单线程程序中是正确的,在多线程中这时pv的值可能不再等于c+1了,这导致T1,T2, ...Tn的inc_if_gt_zero可能返回重复值。
分享到:
相关推荐
百度历年笔试题百度历年笔试题百度历年笔试题百度历年笔试题
百度笔试题 百度 笔试题 百度 笔试题
百度笔试题百度笔试题百度笔试题百度笔试题百度笔试题百度笔试题
百度笔试题大全 百度笔试题大全 百度笔试题大全 百度笔试题大全 百度笔试题大全
百度校招笔试题.doc
百度笔试题,一套完整的百度笔试题,有要应聘百度的兄弟不要错过。
一套百度的笔试题,蓝色部分为参考答案 (本资源来自互联网)
2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度...
百度公司两年来的笔试题,快来看啊
百度历年笔试试题汇总 技术类笔试试题 算法 数据结构等
百度最全笔试题
百度笔试题 这个不用多说了吧,学计算机的百度应该算是比较向往的地方了
12年5月份的百度前端笔试题,看你的距离在哪里。
百度Java笔试题
历年百度笔试题的收集,对面试百度很有帮助
有txt格式的,有的是俺在网上搜的网页直接保存下来的。有的题目给出了参考答案,不过不一定正确。我当初笔试的是质量部的软开,笔试题附其中了,其余的更多是运维部的笔试题吧。
百度技术研发笔试题,涉及数据结构及相关算法,哈希等知识
百度校园招聘笔试题及答案-未知年份及岗位(1).docx百度校园招聘笔试题及答案-未知年份及岗位(1).docx百度校园招聘笔试题及答案-未知年份及岗位(1).docx百度校园招聘笔试题及答案-未知年份及岗位(1).docx百度校园招聘...
百度的历年笔试试题,很齐全,大家有兴趣可以下载下来做做,一定有好处。