消息队列是一些平台的通信的基石，各个任务的通信基于消息队列，消息队列的处理速度往往影响整个系统的性能，为了避免多任务同时处理消息队列，通常有任务处理队列时需要加锁来互斥访问。

1:假设每个模块有自己的消息队列，任何模块都可以给这个模块发消息，但只有本模块会从消息队列中取消息处理，如下图所示一个消息队列可能多个任务同时写，一个任务读。

2：为了避免多个任务处理时使用锁导致的效率底线我们可以使用免锁设计来实现队列操作，见http://www.cnblogs.com/chencheng/p/3527692.html

3：上面的设计在多个任务入队操作效率很高，但在的问题是如果队列中存在元素可读，但队头元素始终没有准备好，Tout任务会一直轮询而不能处理后面已经准备好的元素。

4：为了提高任务消息处理效率，可以设计一种基于滑动窗口机制的消息队列来处理出队操作，避免轮询。

1）任务处理队头元素，如果队头元素可读，马上读出队头元素操作：

2）任务处理队头元素，如果队头元素不可读，但队列中存在可读的消息，设置处理窗口为当前队尾到队头的空间，顺序的在窗口中取出可读数据进行处理，直到该窗口所有数据处理完毕：

3）当前窗口处理完毕后，移动队头位置，构建下一个滑动窗口处理数据。

5：通过上述设计可以提高消息处理的速度，避免轮询等待。

6：后记，问题定位

• 想通过自身比较来取模，结果发现偶尔CAS(&(g_que.rear),g_que.rear,g_que.rear%MAXLEN) &(g_que.rear)地址中的值并不等于g_que.rear。

1：gcc -lpthread -g -o FreeLockQueue FreeLockQueue.c 用-g选项编译

2：objdump -S FreeLockQueue 反汇编

3：    CAS(&(g_que.rear),MAXLEN,0);
  40079f: b8 d0 07 00 00        mov    $0x7d0,%eax
  4007a4: ba 00 00 00 00        mov    $0x0,%edx
  4007a9: f0 0f b1 15 53 d4 20  lock cmpxchg %edx,0x20d453(%rip)        # 60dc04 <g_que+0xbb84>

4：    CAS(&(g_que.rear),g_que.rear,g_que.rear%MAXLEN);
  40079f: 8b 0d 5f d4 20 00     mov    0x20d45f(%rip),%ecx        # 60dc04 <g_que+0xbb84>
  4007a5: ba d3 4d 62 10        mov    $0x10624dd3,%edx
  4007aa: 89 c8                 mov    %ecx,%eax
  4007ac: f7 ea                 imul   %edx
  4007ae: c1 fa 07              sar    $0x7,%edx
  4007b1: 89 c8                 mov    %ecx,%eax
  4007b3: c1 f8 1f              sar    $0x1f,%eax
  4007b6: 29 c2                 sub    %eax,%edx
  4007b8: 89 d0                 mov    %edx,%eax
  4007ba: 69 c0 d0 07 00 00     imul   $0x7d0,%eax,%eax
  4007c0: 29 c1                 sub    %eax,%ecx
  4007c2: 89 c8                 mov    %ecx,%eax
  4007c4: 89 c2                 mov    %eax,%edx
  4007c6: 8b 05 38 d4 20 00     mov    0x20d438(%rip),%eax        # 60dc04 <g_que+0xbb84>
  4007cc: f0 0f b1 15 30 d4 20  lock cmpxchg %edx,0x20d430(%rip)        # 60dc04 <g_que+0xbb84>      

5：CAS(&(g_que.rear),g_que.rear,g_que.rear%MAXLEN)的参数计算从汇编看是多条指令，并不具有原子性，原子操作 是比较和交换本身，如果将g_que.rear参数的值移入寄存器后，发生线程切换，另外一个线程修改了g_que.rear的值， 那么切换回来后&(g_que.rear)地址中的值和寄存器中保存的值并不相同。

结论：原子操作仅仅是针对操作本身，小心参数求解可能发生的切换。

• g_que.readableCnt--;汇编指令如下，

  400bd4: 8b 05 32 d0 20 00     mov    0x20d032(%rip),%eax        # 60dc0c <g_que+0xbb8c>
  400bda: 83 e8 01              sub    $0x1,%eax
  400bdd: 89 05 29 d0 20 00     mov    %eax,0x20d029(%rip)        # 60dc0c <g_que+0xbb8c>

1：先把地址中的值取到寄存器，再将寄存器中的值减一，最后将寄存器的值存入地址，可以看到如果在第一条指令执行后被切换出去，其它线程如果操作了readableCnt再切换回来，此刻值就出问题
2：g_que.readableCnt初始为1，执行g_que.readableCnt--
3：执行指令1后被切换出去，此刻eax中为1，
4：另一个线程操作g_que.readableCn+1，完后被切换回来
5：执行指令2，eax中值为0
6：执行指令3，将0存回g_que.readableCn，最后g_que.readableCn为0.
7：与我们预期的值1不一致了。所以应该使用FAS(&(g_que.readableCnt),1)原子操作保证一致性。

转载请注明原始出处：http://www.cnblogs.com/chencheng/p/3961263.html 

基于滑动窗口的免锁队列设计实现