linux核心無鎖cas,無鎖程式設計以及CAS

無鎖程式設計 / lock-free / 非阻塞同步

無鎖程式設計，即不使用鎖的情況下實作多線程之間的變量同步，也就是在沒有線程被阻塞的情況下實作變量的同步，是以也叫非阻塞同步(Non-blocking Synchronization)。

實作非阻塞同步的方案稱為“無鎖程式設計算法”( Non-blocking algorithm)。

lock-free是目前最常見的無鎖程式設計的實作級别(一共三種級别)。

為什麼要 Non-blocking sync ？

使用lock實作線程同步有很多缺點：

* 産生競争時，線程被阻塞等待，無法做到線程實時響應。

* dead lock。

* live lock。

* 優先級翻轉。

* 使用不當，造成性能下降。

如果在不使用 lock 的情況下，實作變量同步，那就會避免很多問題。雖然目前來看，無鎖程式設計并不能替代 lock。

實作級别

非同步阻塞的實作可以分成三個級别：wait-free/lock-free/obstruction-free。

wait-free

是最理想的模式，整個操作保證每個線程在有限步驟下完成。

保證系統級吞吐(system-wide throughput)以及無線程饑餓。

截止2011年，沒有多少具體的實作。即使實作了，也需要依賴于具體CPU。

lock-free

允許個别線程饑餓，但保證系統級吞吐。

確定至少有一個線程能夠繼續執行。

wait-free的算法必定也是lock-free的。

obstruction-free

在任何時間點，一個線程被隔離為一個事務進行執行(其他線程suspended)，并且在有限步驟内完成。在執行過程中，一旦發現資料被修改(采用時間戳、版本号)，則復原。

也叫做樂觀鎖，即樂觀并發控制(OOC)。事務的過程是：1讀取，并寫時間戳；2準備寫入，版本校驗；3校驗通過則寫入，校驗不通過，則復原。

lock-free必定是obstruction-free的。

CAS原語

LL/SC, atom read-modify-write

如果CPU提供了Load-Link/Store-Conditional(LL/SC)這對指令，則就可以輕松實作變量的CPU級别無鎖同步。

LL [addr],dst：從記憶體[addr]處讀取值到dst。

SC value,[addr]：對于目前線程，自從上次的LL動作後記憶體值沒有改變，就更新成新值。

上述過程就是實作lock-free的 read-modify-write 的原子操作。

CAS (Compare-And-Swap)

LL/SC這對CPU指令沒有實作，那麼就需要尋找其他算法，比如CAS。

CAS是一組原語指令，用來實作多線程下的變量同步。

在 x86 下的指令CMPXCHG實作了CAS，前置LOCK既可以達到原子性操作。截止2013，大部分多核處理器均支援CAS。

CAS原語有三個參數，記憶體位址，期望值，新值。如果記憶體位址的值==期望值，表示該值未修改，此時可以修改成新值。否則表示修改失敗，傳回false，由使用者決定後續操作。

Bool CAS(T* addr, T expected, T newValue)

{

if( *addr == expected )

{

*addr = newValue;

return true;

}

else

return false;

}

ABA 問題

thread1意圖對val=1進行操作變成2，cas(*val,1,2)。

thread1先讀取val=1；thread1被搶占(preempted)，讓thread2運作。

thread2 修改val=3，又修改回1。

thread1繼續執行，發現期望值與“原值”(其實被修改過了)相同，完成CAS操作。

使用CAS會造成ABA問題，特别是在使用指針操作一些并發資料結構時。

解決方案

ABAʹ：添加額外的标記用來訓示是否被修改。

語言實作

Java demo

AtomicInteger atom = new AtomicInteger(1);

boolean r = atom.compareAndSet(1, 2);

C# demo

int i=1;

Interlocked.Increment(ref i);

Refs

4.鎖--無鎖程式設計以及CAS

無鎖程式設計以及CAS 無鎖程式設計 / lock-free / 非堵塞同步 無鎖程式設計,即不使用鎖的情況下實作多線程之間的變量同步,也就是在沒有線程被堵塞的情況下實作變量的同步,是以也叫非堵塞同步(Non-b ...

【多線程】無鎖程式設計以及CAS

無鎖程式設計 / lock-free / 非阻塞同步 無鎖程式設計,即不使用鎖的情況下實作多線程之間的變量同步,也就是在沒有線程被阻塞的情況下實作變量的同步,是以也叫非阻塞同步(Non-blocking Sy ...

無鎖程式設計(四) - CAS與ABA問題

CAS 一般采用原子級的read-modify-write原語來實作Lock-Free算法,其中LL和SC是Lock-Free理論研究領域的理想原語,但實作這些原語需要CPU指令的支援,非常遺憾的是目 ...

【Java并發程式設計】2、無鎖程式設計：lock-free原理；CAS；ABA問題

轉自:http://blog.csdn.net/kangroger/article/details/47867269 定義 無鎖程式設計是指在不使用鎖的情況下,在多線程環境下實作多變量的同步.即在沒有線程 ...

[轉]透過 Linux 核心看無鎖程式設計

非阻塞型同步 (Non-blocking Synchronization) 簡介 如何正确有效的保護共享資料是編寫并行程式必須面臨的一個難題,通常的手段就是同步.同步可分為阻塞型同步(Blocking ...

海量并發的無鎖程式設計 (lock free programming)

最近在做線上架構的實作,線上架構和離線架構近線架構最大的差別是服務品質(SLA,Service Level Agreement,SLA 99.99代表10K的請求最多一次失敗或者逾時)和延時.而離線架 ...

C++11原子操作與無鎖程式設計(轉)

不講語言特性,隻從工程角度出發,個人覺得C++标準委員會在C++11中對多線程庫的引入是有史以來做得最人道的一件事:今天我将就C++11多線程中的atomic原子操作展開讨論:比較互斥鎖,自旋鎖(sp ...

C++性能榨汁機之無鎖程式設計

C++性能榨汁機之無鎖程式設計 來源 http://irootlee.com/juicer_lock_free/ 前言 私以為個人的技術水準應該是一個螺旋式上升的過程:先從書本去了解一個大概,然後在實踐中 ...

随機推薦

css讓圖檔作為按鈕的背景并且大小合适

最近在做ASP大作業,在做html頁面的時候想把一個圖檔作為按鈕的背景,搞了好久終于在csdn上找到了滿意的答案: background-size: cover; 隻需要這一句就ok了,就是這麼簡答. ...

C#與mysql做ASP.NET網頁資料庫查詢速度測試

兩種方法是:1,使用mysql資料庫的存儲過程:2,C#編碼,做網頁背景與mysql資料庫連接配接,前台測試顯示測試過結果下面我将分别講解兩種方法的具體實作. 1,使用mysql資料庫的存儲過程插入萬條大 ...

二十一、oracle pl/sql分類一 存儲過程

存儲過程用于執行特定的操作,當建立存儲過程時,既可以指定輸入參數(in),也可以指定輸出參數(out),通過在過程中使用輸入參數,可以将資料傳遞到執行部分:通過使用輸出參數,可以将執行部分的資料傳遞到 ...

iOS深淺拷貝

淺拷貝:你和你的影子,你改變,你的影子發生改變 深拷貝:你的克隆人,你改變,你的克隆人并不會發生變化 eg: NSString *string = @"我是一個小白鼠"; NSSt ...

shell進階函數

函數的定義和用途 函數function是由若幹條shell指令組成的語句塊,實作shell代碼的重用和子產品化程式設計. 函數和shell程式的異同點 它與shell程式形式上是相似的,不同的是它不是一個單 ...

win7 powershell配色方案

首先我是參考微軟的word的, look~ Windows PowerShell 配置檔案 要配置powershell很簡單, 就幾步 1.顯示 Windows PowerShell 配置檔案的路徑 ...

jar 包 的用處 ，dozer、poi、itext 、jxl 、jbarcode 、itextrenderer jquery 效果

1.dozer 做類型轉換的, 建立 xml 檔案 描述兩個實體的對應關系 ,DozerBeanMapper mapper =new DozerBeanMapper().addMappingFiles ...

java中判斷圖檔格式并且等比例壓縮圖檔

最近項目中需要判斷上傳的圖檔必須是png,jpg,gif三種格式的圖檔,并且當圖檔的寬度大于600px時,壓縮圖檔至600px,并且等比例的壓縮圖檔的高度. 具體的實作形式: 大緻的思路是: 判斷根據 ...

unity 品質設定 Quality Settings

Unity allows you to set the level of graphical quality it will attempt to render. Generally speaking ...