- 論壇徽章:
- 4
|
最近在看這塊，說(shuō)說(shuō)我的理解，請(qǐng)大家指點(diǎn)。。。
1.先說(shuō)說(shuō)幾個(gè)概念
鎖只是同步方法的一種，同步分阻塞同步和非阻塞同步。
lockfree就可以保證非阻塞同步，同時(shí)也盡量保證了waitfree，但依然做不到完全的waitfree。
2.既然討論無(wú)鎖，就得說(shuō)說(shuō)有鎖會(huì)導(dǎo)致的問(wèn)題
a）死鎖
多個(gè)鎖不按順序的話
b）優(yōu)先級(jí)反轉(zhuǎn)
可能高優(yōu)先級(jí)的等待低優(yōu)先級(jí)的
c）影響實(shí)時(shí)性
等鎖時(shí)間不定
d）信號(hào)安全
信號(hào)處理中不能用鎖
e）崩潰處理
崩潰時(shí)可能占著鎖
f）搶占的影響
被搶占時(shí)可能還占著鎖
g）影響整體性能
切換進(jìn)程影響性能
最后，鎖的實(shí)現(xiàn)是跟硬件相關(guān)的，自然影響移植性。
3.無(wú)鎖首先得根據(jù)業(yè)務(wù)邏輯，這個(gè)是首要的。
脫離業(yè)務(wù)去有鎖或無(wú)鎖是沒(méi)有意義的。
根據(jù)業(yè)務(wù)流程去簡(jiǎn)化，一般可以將鎖的存在壓縮到最小。另外鎖只是同步機(jī)制的一種，應(yīng)該還有其它選擇。
4.如果已經(jīng)將有鎖的存在壓縮到最小的數(shù)據(jù)結(jié)構(gòu)了，就可以考慮無(wú)鎖算法了。
通用的lock free算法都是針對(duì)基本的數(shù)據(jù)結(jié)構(gòu)的：buffer，list，queue，map
基本原理就是CAS機(jī)制了�，F(xiàn)在幾乎所有的CPU指令都支持CAS的原子操作，X86下對(duì)應(yīng)的是CMPXCHG匯編指令。（可見(jiàn)，lockfree是依賴(lài)于機(jī)器體系結(jié)構(gòu)的，而且lockfree其實(shí)還是有鎖的，只是CAS給壓縮含義了）
一般CAS會(huì)封裝成下面的形式：（以32bit機(jī)為例）
bool cas32( int * pVal, int oldVal, int newVal );
pVal 表示要比較和替換數(shù)值的地址，oldVal表示期望的值，newVal表示希望替換成的值。
gcc中：
http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html- bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
- type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
- These builtins perform an atomic compare and swap. That is, if the current value of *ptr is oldval, then write newval into *ptr.
- The “bool” version returns true if the comparison is successful and newval was written. The “val” version returns the contents of *ptr before the operation.
- __sync_synchronize (...)
- This builtin issues a full memory barrier.
- #define LOCK_PREFIX "lock;"
- #define __sync_bool_compare_and_swap(mem, oldval, newval) \
- ({ __typeof (*mem) ret; \
- __asm __volatile (LOCK_PREFIX "cmpxchgl %2, %1;sete %%al; movzbl %%al,%%eax" \
- : "=a" (ret), "=m" (*mem) \
- : "r" (newval), "m" (*mem), "a" (oldval)\
- :"memory"); \
- ret; })
5.下面以說(shuō)說(shuō)無(wú)鎖隊(duì)列的實(shí)現(xiàn)，說(shuō)下我的理解- EnQueue(x)
- {
- q = newrecord();
- q->value = x;
- q->next = NULL;
-
- do{
- p = tail;
- }while( CAS(p->next, NULL, q) != TRUE);
-
- CAS(tail, p, q);
- }
- DeQueue()
- {
- do{
- p = head;
- if(p->next == NULL){
- returnERR_EMPTY_QUEUE;
- }
- while( CAS(head, p, p->next) != TRUE );
- returnp->next->value;
- }
考慮加入隊(duì)列的處理：如果thread 1 EnQueue(x)在成功完成第一個(gè)CAS，還沒(méi)開(kāi)始第二個(gè)CAS時(shí)掛掉了。那么other threads就會(huì)全死循環(huán)了:都在等著next字段為NUL的tail，但其實(shí)這個(gè)tail的next恒指向T1 在第一個(gè)CAS中新增的節(jié)點(diǎn)了。
解決此問(wèn)題的修改后的：- EnQueue(x)
- {
- q = newrecord();
- q->value = x;
- q->next = NULL;
-
- p = tail;
- oldp = p
- do{
- while(p->next != NULL)
- p = p->next;
- }while( CAS(p.next, NULL, q) != TRUE);
-
- CAS(tail, oldp, q);
- }
回復(fù) 1# send_linux |
評(píng)分
-
查看全部評(píng)分
|
免費(fèi)注冊(cè)
發(fā)表于 2013-06-21 09:21
發(fā)表于 2013-06-21 11:45
