以前一直不明白lock free是什么,后来发现原来是完全理解错了概念,lock free看到大家有的翻译为无锁,有的翻译为锁无关,其实用不用锁和lock free是不相关的,用了锁也可能是lock free,而不用锁有可能不是lock free。
一个lock free的解释是
一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。
其实看我们那副图就是说你的各个线程不会互相阻塞,那么你的程序才能成为lock free的。像我们平常用的互斥锁,当有线程获得锁,其他线程就被阻塞掉了,这里的问题就是如果获得锁的线程挂掉了,而且锁也没有释放,那么整个程序其实就被block在那了,而如果程序是lock free的那么即使有线程挂掉,也不影响整个程序继续向下进行,也就是系统在整体上而言是一直前进的。
那么,不用锁就是lock free的吗,一开始就提到了,不用锁也可能不是lock free的,举个例子
while (x == 0) {
x = 1-x;
}
在这里如果两个线程同时执行,可能同时进入while循环,然后x两次改变值之后,依然是0,那么两个线程就会一直互相在这里阻塞掉了,所以这里虽然没有锁,依然不是lock free的。
现在大家写lock free的时候一般都会使用CAS(compare and set)操作来写,因为现在很多的cpu都是支持CAS操作并作为原子操作来处理的,CAS操作一般是这样的
bool compare_and_swap (int *oldval, int *dest, int newval) {
if (*oldval == *dest) {
*dest = newval;
return true;
}
return false;
}
其实这样一个操作和乐观锁很像,并且操作简单,相应的比互斥锁的代价要小。所以现在大家都是喜欢用lock free的技术来提高系统的performance。
最后如果大家对于如何编写lock free的数据结构感兴趣的话,可以参考我后面给出的链接。
一种高效无锁内存队列的实现
无锁队列的实现
锁无关的(Lock-Free)数据结构
An Introduction to Lock-Free Programming
你好, 先在這裡謝謝你的文章對我有很多幫助.
我想請問: 如果應用Lock-Free在Queue, Stack上, 這兩個類型的資料結構如何改善執行效率?
據我瞭解兩者裡儲存的數據, 都一定會有先後順序的規則. 以Enqueue, Dequeue來說… 譬如:一位user1 正 Enqueue 在 Queue上. 為了不打亂數據的順序規則, 其他 user2, user3… 必須等待 user1 結束後才能使用 Enqueue 或 Dequeue.
所以這兩類的Data structure不管執行什麼動作一定要等待…, 我看不出Lock Free對Queue和Stack有什麼益處.
等待你的指教.
謝謝
@Hao: lock free的话就是保证不会有线程block整个程序的进程,比如用锁的时候user1获得锁去enqueue,操作还没结束user1 down掉了,这时候还没释放锁,其他线程也被block了,另外就是用cas这种原子操作的话代价比较小,用其他的锁,无法获得锁时可能会导致上下文切换,这个代价还是很大的,这是我的理解,希望对你有帮助
I think my dog may have a yeast infection or bacterial infection between his toes. He contasntly chews at his paws, causing them to become extremely sore. Is there an over the counter remedy for this problem?
这个理解好像也是错误的。
https://doc.akka.io/docs/akka/2.5.3/scala/general/terminology.html#concurrency-vs-parallelism
按照本文的解释,lock free 应该是在一系列调用中,有一些方法能够在有限步骤后结束。
“所有线程中至少有一个能够继续往下执行” 这个应该是obstruction-free
dpost.in
Who are passionate about publishing the Education Updates with transparency in general public interest. dpost.in dpost is a initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism.