使用邮件的方式来写博客，可以间接避开博客地址登陆不上去的问题。关于使用邮件写博客的方法，这里有一个说明文档：http://en.support.wordpress.com/post-by-email/
例如一些常用的标签：
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
2010年10月20日星期三
Ubuntu任务栏上网络连接图标消失
之前使用Ubuntu配置ADSL上网，后来到可以使用局域网上网的环境，删除了PPPoE的配置后，发现图标不见了。可以通过如下的命令得到恢复：
sudo service network-manager stop
sudo rm /var/lib/NetworkManager/NetworkManager.state
sudo service network-manager start
sudo gedit /etc/NetworkManager/nm-system-settings.conf
把false改成true
sudo service network-manager restart
上面提到删除之前的ADSL，方法如下：
删除 /etc/ppp/dsl-provider
删除 /etc/network/interfaces中除了关于lo的段落外的
删除 /etc/rc5.d/中pppoe启动的脚本
删除了上述的配置后，等于就是使用Ubuntu的默认配置上网，一般情况下Ubuntu也能在不需要使用任何配置的情况下就能上网。另外有其他教程说重新删除Network-Manager和nm-applet的把他们安装回来，也能达到同样的效果。
务必记住：windows不用设置就能直接上网，linux也能。
引用:
NetworkManager和networking有冲突，如果启用了NetworkManager就不能再用networking管理网络了，如果用Networking管理网络，就不能用networkmanager,所以解决方法有两种：
1用networkmanager管理网络:
编辑/etc/network/interfaces，将其中的所有网络的设置全部注释掉(就是在行前面打上#)，仅留下lo（本地回环）的设置。然后重启NetworkManager和networking.
2用networking管理网络(就是命令行方式)
可以将networkmanager禁止,在终端里输入sudo apt-get remove network-manager --purge就可以了
或者sudo gedit /etc/NetworkManager/nm-system-settings.conf 将managed=true改为false
Reference sites：
这里对Ubuntu上网遇到的各种情况都有介绍，不过有点乱，阅读起来有点累：http://www.xxlinux.com/linux/article/accidence/install/20100625/18358.html
http://forum.ubuntu.org.cn/viewtopic.php?f=116&t=258095&start=0
http://forum.ubuntu.org.cn/viewtopic.php?f=116&t=230483&start=0
2010年10月11日星期一
VIM使用笔记
前面写过一篇《VIM的简明教程》，其实大部分都是抄袭过来，今天又参考了一篇文章，在这里，对VIM有个不一样的理解。总结一些心得如下：
VIM的感觉(feeling)：对VIM的理解
1、VIM是一个语言式的文本编辑器，有动词，名词，使用动词+名词，形成一个祈使句，用来执行命令，可以使用任意动词＋名词组合，形成各种命令。例如：
动词：chang命令(c)，delete命令(d)等等
名词：word命令(w)等等
我们来组成一句话，dw，删除一个词。
还有有趣的形容词：inside (i), around (a)，例如可以如下造句：
“change inside parenthesis” (ci( or cib)，这个命令的含义是：改变括号里面的内容。
2、VIM命令的物理含义，作者举了一个这样的例子：不管你扔一个球，还是扔一个三明治，虽然砸到人得到的效果不一样，但是这个扔的动作时一模一样的。vim中同样适用，例如：
daw 和 da{ 命令，前者是围绕一个词(word)删除，后者是围绕大括号({})删除。但是动作时一样的都是da<something>，即"delete aroud something"。
3、编程式的编辑，适用VIM编辑，就想编程一样。例如：
daw，可以看成是函数delete(type='word', around=True)；
另外，还可以在.vimrc文件中进行一些配置，例如在vimrc文件中，有这样一行nnoremap <leader>1 yypVr= ， 那么可以把 <leader>1 看成是一个函数，完成如下功能：复制当前行(yy)，粘贴到这一行下面(p)，全选当前行(V)，替换当前行全部为等号(r=)；
另外，VIM还有可以进行宏定义(macro)。
使VIM变得更好用
VIM的配置文件.vimrc，通过添加一些配置选项，使VIM使用起来得心应手。下面举例一些有用的配置选项：
filetype plugin indent on "打开文件类型，插件，缩进功能
set nocompatible " 禁用vi兼容
set modelines=0 " 取消vim的模式行
set encoding=utf-8
set scrolloff=3
set autoindent
set showmode
set showcmd
set hidden
set wildmenu
set wildmode=list:longest
set visualbell
set cursorline
set ttyfast
set ruler
" 以下两行是vim7.3的新特性
set relativenumber " 设置相对行号，真是非常有用的，因为很多命令要使用到行数，eg, 10dd删除10行
set undofile " 生成一个undo 文件，FILENAME.un~，关闭文件后再打开，还可以使用undo命令
set ignorecase " 搜索忽略大小写
set smartcase " 搜索，如果有大写，就大写匹配
set gdefault " 默认g模式(整行全局模式)，例如:%s/foo/bar/g 就可以写成 :%s/foo/bar/
set incsearch
set showmatch
set hlsearch
au FocusLost * :wa " 失去焦点，就自动保存
VIM插件
插件使VIM变得像神一样。
Pathogen插件，地址http://www.vim.org/scripts/script.php?script_id=2332
这是一个插件管理插件（怎么说的这么别扭，哈哈），具体的使用方法见这里。
Yankring插件，地址在这里，http://www.vim.org/scripts/script.php?script_id=1234
Surround插件，地址在这里，http://www.vim.org/scripts/script.php?script_id=1697
VIM插件数不胜数，合理使用插件，使VIM达到很多意想不到的效果。
参考地址：
http://wujblog.appspot.com/2010/06/27/vimjiancheng.html
http://stevelosh.com/blog/2010/09/coming-home-to-vim/
http://www.linuxeden.com/html/news/20100811/104261.html
2010年9月27日星期一
Windows多线程编程
前面写了一篇Linux多线程编程，由于算法要整合到一个运行在Windows平台下的系统中，所以需要改成Windows下的多线程方式（看我折腾的）。这里简单列一个Windows多线程编程的例子。其实我也想尝试是用一个跨平台的C++库Boost，Boost::Thread类库可以在不同的平台下运行多线程，而且多线程功能非常丰富和强大，使用起来也很容易，但是还需要安装这个库，先暂时放弃这个方案，因为毕竟我现在需要的多线程功能非常简单。
Windows API实现多线程
在上一篇文章中，已经列出了一个表，列出了Linux线程API和Windows下线程API的大致对应关系。根据那个表，和Linux下多线程经验，也能大概知道Windows下实现多线程的方法首先来看一个例子：
/* example.c */
#include <stdfx.h>
#include <stdio.h>
#include <process.h>const int NLOOP = 100;
int counter = 0;
void thread(void*);
CRITICAL_SECTION beswap ;
int main()
{
HANDLE pnt[2];
InitializeCriticalSection(&beswap);
pnt[0] = (HANDLE)_beginthread(doit,0,NULL);
pnt[1] = (HANDLE)_beginthread(doit,0,NULL);
WaitForMultipleObjects( 2, pnt, TRUE, 1000L);
DeleteCriticalSection(&beswap);
return 0;
}
void doit(void*)
{
printf("go...\n");
int i, val = 0;
for(i = 0; i < NLOOP; ++i)
{
EnterCriticalSection(&beswap);
val = counter;
printf("%d\n",val+1);
counter = val + 1;
LeaveCriticalSection(&beswap);
}
printf("end...\n");
return ;
}
根据这个例子，多线程的过程解释如下：
1、编写线程函数，这里线程函数要遵循如下函数原型:
DWORD WINAPI threadFunc(LPVOID lpvThreadParm);
函数的输入参数是一个DWORD的类型，可以是一个整数，也可以是一个内存指针，具体的意义由编程者自己决定。返回值是一个DWORD型的值。
2、创建一个线程
一个进程的主线程是由操作系统自动生成，如果你要让一个主线程创建额外的线程，你可以调用来CreateThread完成，使用的时候注意包含#include<process.h>头文件。其函数原型如下：
HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpsa,DWORD cbstack,LPTHREAD_START_ROUTINE lpStartAddr,
LPVOID lpvThreadParm, DWORD fdwCreate,LPDWORD lpIDThread);
其中，lpsa参数为一个指向SECURITY_ATTRIBUTES结构的指针。如果想让对象为缺省安全属性的话，可以传一个NULL，如果想让任一个子进程都可继承一个该线程对象句柄，必须指定一个SECURITY_ATTRIBUTES结构，其中bInheritHandle成员初始化为TRUE。
参数cbstack表示线程为自己所用堆栈分配的地址空间大小，0表示采用系统缺省值。
参数lpStartAddr用来表示新线程开始执行时代码所在函数的地址，即为线程函数。
lpvThreadParm为传入线程函数的参数，
fdwCreate参数指定控制线程创建的附加标志，可以取两种值。如果该参数为0，线程就会立即开始执行，如果该参数为CREATE_SUSPENDED，则系统产生线程后，初始化CPU，登记CONTEXT结构的成员，准备好执行该线程函数中的第一条指令，但并不马上执行，而是挂起该线程。
最后一个参数lpIDThread 是一个DWORD类型地址，返回赋给该新线程的ID值。
此外，还可以使用_beginthread等函数来创建线程,正如本例子中使用的方法：
handle=(HANDLE)_beginthread(threadFunc,0, NULL);
函数_beginthread的函数原型如下：
uintptr_t _beginthread(
void( *start_address )( void * ),
unsigned stack_size,
void *arglist
);
start_address新线程的起始地址，指向新线程调用的函数的起始地址；stack_size stack_size 新线程的堆栈大小，可以为0；arglist arglist 传递给线程的参数列表，无参数是为NULL。
3、终止线程，如果某线程调用了ExitThread 函数，就可以终止自己。
VOID ExitThread(UINTfuExitCode );
这个函数为调用该函数的线程设置了退出码fuExitCode后， 就终止该线程。调用TerminateThread函数亦可终止线程。
该函数用来结束由hThread参数指定的线程， 并把dwExitCode设成该线程的退出码。当某个线程不在响应时，我们可以用其他线程调用该函数来终止这个不响应的线程。BOOL TerminateThread(HANDLE hThread, DWORD dwExitCode);
4、另外还有设置程序的优先级，挂起和恢复线程之类的。这里就不详述，因为还没有用到。
BOOL SetThreadPriority(HANDLE hThread,intnPriority); // 设置线程优先级
DWORD ResumeThread(HANDLEhThread); // 恢复线程
DWORD SuspendThread(HANDLE hThread); // 挂起线程
5、这里还用到了线程的阻塞函数WaitForMultipleObjects，原型：
DWORD WaitForMultipleObjects(
DWORD nCount,
const HANDLE* lpHandles,
BOOL bWaitAll,
DWORD dwMilliseconds
);
WaitForMultipleObjects是Windows中的一个功能非常强大的函数，几乎可以等待Windows中的所有的内核对象。当WaitForMultipleObjects等到多个内核对象的时候，如果它的bWaitAll 参数设置为false。其返回值减去WAIT_OBJECT_0 就是参数lpHandles数组的序号。如果同时有多个内核对象被触发，这个函数返回的只是其中序号最小的那个。如果为TRUE 则等待所有信号量有效在往下执行。（FALSE 当有其中一个信号量有效时就向下执行）。
对应的还有一个函数WaitForSingleObject，用来等待指定的内核对象。
6、还有互斥锁的使用方法，在例子中也有很清楚的使用方法。单进程的线程可以使用这种临界资源对象来解决同步互斥问题,该对象不能保证哪个个线程能够获得到临界资源对象,因而该系统能公平的对待每一个线程。
MFC实现多线程
MFC对Windows API进行了封装，可以说使用起来更加简单，而且提供了很多多线程的扩张功能。MFC实现多线程有两种，一种是工作者线程，另一种是用户界面线程。前一种是简单的线程，后一种是带有消息队列的线程。
CWinThread* AfxBeginThread(
AFX_THREADPROC pfnThreadProc,
LPVOID pParam,
int nPriority = THREAD_PRIORITY_NORMAL,
UINT nStackSize = 0,
DWORD dwCreateFlags = 0,
LPSECURITY_ATTRIBUTES lpSecurityAttrs = NULL
);
CWinThread* AfxBeginThread(
CRuntimeClass* pThreadClass,
int nPriority = THREAD_PRIORITY_NORMAL,
UINT nStackSize = 0,
DWORD dwCreateFlags = 0,
LPSECURITY_ATTRIBUTES lpSecurityAttrs = NULL
);
这是一个重载函数，前一个用来创建一个工作线程，后一个用来创建界面线程。MFC框架还提供了很多同步类，来实现线程间的同步和通信，具体的使用方法可以参考MSDN，由于还没有用到，等用到了，再详细总结。另外，在编程中，我也是用WaitForMultipleObjects来等待了AfxBeginThread创建的线程，而没有出现问题。
参考地址：
http://wujblog.appspot.com/2010/09/26/linux-multi-thread.html
http://www.wangchao.net.cn/bbsdetail_69676.html
http://blog.csdn.net/zjl_1026_2001/archive/2008/03/18/2193626.aspx
http://msdn.microsoft.com/en-us/library/s3w9x78e(VS.80).aspx
http://msdn.microsoft.com/zh-cn/library/975t8ks0(v=VS.80).aspx
订阅：
博文 (Atom)