5 6 並行程式的潛在問題(四) - ianchen0119/AwesomeCS GitHub Wiki

先前已經向各位介紹如何利用鎖保證多執行緒程式的同步，像是 Spinlock 、 Mutex lock 與 Semaphore 等。這樣的作法雖然可以有效避免 Condition race ，卻因為執行緒被阻塞而增加程式的延遲。

非阻塞演算法

為了有效避免上述狀況，電腦科學家又提出了非阻塞演算法，為了實現該演算法，計算機通常需要支援 Atomic operations ，常見的操作像是 CAS (Compare And Swap)。

Lock-free

在 Lock-free 系統中，有些特定的計算仍有可能被 Block 一段時間，不過，其他執行緒不會因為該計算被阻塞，而是繼續做其他無須該資原的任務進而增加整體的吞吐量。

Lock-free 這邊的無鎖指的是沒有執行緒會被鎖住，而不是程式中沒有鎖。

Wait-free

Thread pool

Ring buffer & KFIFO

Lock-free thread pool

DBMS 的資料同步問題

你可曾想過，當有多個 Client 同時對資料庫進行讀寫操作時，資料庫是如何保持資料的正確性呢? MVCC (Multiversion concurrency control) ，是 DBMS 常見的並行控制方法，其利用了時間戳記或是自動增量的事務 id 讓多個客戶操作能被資料庫處理，避免了鎖的使用與飢餓問題。

1981 年，一篇名為 Concurrency Control in Distributed Database Systems 的論文發表，其中清楚的說明 MVCC 的演算方法，本小節會稍微介紹 MVCC 的核心概念。

樂觀鎖與悲觀鎖

事務的定義

Read Ops on MVCC

MVCC 的 Read 操作有兩大類:

  • 一般讀 一般讀取時，資料庫會將當前的可見版本回傳給請求端，因此一般讀操作是不需使用鎖的。 常見的一般讀操作就是 SQL 的 SELECT 操作。

  • 緊接著寫操作的讀 當我們使用 UPDATE, INSERT, DELETE 嘗試修改資料庫的資料時，我們必須先讀入當前資料才能以它為基準做修改。

    select * from table where xxx lock in share mode，
select * from table where xxx for update，
update table set....
insert into table (xxx,xxx) values (xxx,xxx)
delete from table where id = xxx

Reference