🚫 Ad Blocker Detected

Please disable your AD blocker to continue using this site. Ads help us keep the content free! please press keyboard F5 to refresh page after disabled AD blocker

請關閉廣告攔截器以繼續使用本網站。廣告有助於我們保證內容免費。謝謝! 關閉後請按 F5 刷新頁面

Hello World

0%

高併發系統系列-使用lock & Interlocked CAS(compare and swap)

Posted on Edited on In , Disqus:
Symbols count in article: 5.3k Reading time ≈ 5 mins.

前言

在之前我有寫一篇關於資料庫的ACID分享RDBMS資料庫基本原則

假如我們系統是一個多執行續高併發系統也要注意Atomic不然會造成資料會有Data Racing導致bug產生..

本文使用範例在我github上CAS_Lock有興趣的人可以參考.

沒有注意Atomic會導致的問題

我是我們公司擔任技術面試官之一，假如面試者說他實作過高併發系統。

我就會先問以下問題來辨別是否要更深入面試高併發系統相關問題.

下面Sample Code是這樣.

我用Task假裝高併發，下面有一個Member類別預設給100000元的Balance

有一個UpdateBalance每呼叫一次就扣10元，我透過For跑10000次

理論上我預期在跑完下面顯示Balance會員餘額是0 (因為 10000*10 = 100000).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Program
{
	static void Main(string[] args)
	{
		Member member = new Member() { Balance = 100000 };
		List<Task> tasks = new List<Task>();
		for (int i = 0; i < 10000; i++)
		{
			tasks.Add(Task.Run(() => member.UpdateBalance()));
		}

		Task.WaitAll(tasks.ToArray());

		Console.WriteLine($"member remaining balance is {member.Balance}");
		Console.ReadKey();
	}
}

public class Member {
	public decimal Balance { get; set; }

	public void UpdateBalance()
	{
		Balance -= 10;
	}
}

但執行後蠻常會是不等於0!!

這時我會問面試者兩個問題

  • 為什麼會不等於0
  • 如果要解決你會怎麼解決這個問題?

如果知道的人可以跳到CAS部分，如果不知原因我下面會跟大家分享

為什麼會不等於0

這個問題牽扯到Thread是如何對於變數操作的，Thread在操作變數之前會把資料複製一份進Thread Context中在操作我們要步驟

所以在Balance -= 10;這段程式碼會拆成下面動作

  1. 將執行個體變數中的值載入至register。
  2. 將載入值減10
  3. 將異動後值放回原本值的Memory。

因為以上步驟，假如同一時間有兩個不同的Thread取到的Balance都是1000，並個別對於Balance減10元，我們原本預期這是兩個操作（預期資料為980）

但因為取的瞬間都是1000-10=990把數值放回變數中就導致少扣一個10元…

概念如下圖.

知道原因了要解決就簡單了.

使用Lock解決

因為這段程式碼遇到Data Raceing在同一個時間有兩個不同的Thread對於資料競爭

如果要避免競爭lock是一個比較方便的方式，他可以保證一瞬間只有一個Thread(Session)來執行某段程式碼(通常會放在異動資料那部分)來保證Isolation.

下面是使用lock版本的程式碼，能看到我在Balance -= 10;這一段使用lock來確保每一個瞬間只有一個Thread可以異動資料，其他的Thread需要blocking等他完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Program
{
	static object _lock = new object();
	static void Main(string[] args)
	{
		Member member = new Member() { Balance = 100000 };
		List<Task> tasks = new List<Task>();
		for (int i = 0; i < 10000; i++)
		{
			tasks.Add(Task.Run(() => member.UpdateBalance()));
		}

		Task.WaitAll(tasks.ToArray());

		Console.WriteLine($"member remaining balance is {member.Balance}");
		Console.ReadKey();
	}
}

public class Member {
	//here
	object _lock = new object();

	public decimal Balance { get; set; }

	public void UpdateBalance()
	{
		lock (_lock)
		{
			Balance -= 10;
		}
	}
}

使用lock之後能發現不管執行幾次資料都會如我們預期顯示.

使用lock執行概念圖如下.

在同一時間我們會把要執行程式 利用一個類似保護網的方式，確保同一時間只有一個Thread來做操作.

Thread2取得lock在操作Thread1就必須等待Thread2執行完,在取值=>改值..等等動作

只是使用lock會降低些許吞吐量(但資料正確性是最重要的)，所以要注意使用lock範圍大小

CAS(compare and swap)提高效率

CAS是利用compare and swap來確保資料Atomic.

因為CAS可以取得數值記憶體空間來比較給值並且他也是一條CPU原語具有原子性 cpu 硬體同步原語

前面有說過在Balance -= 10;這段程式碼會拆成下面動作

  1. 將執行個體變數中的值載入至register。
  2. 將載入值減10
  3. 將異動後值放回原本值的Memory。
1
balance -= 10;

會拆解成類似下面動作

1
2
3
int temp = balance;
temp = temp -10;
balance = temp;

假如在取balance(附值給temp)跟把值重新寫入balance中間有其他Thread來操作，就會造成所謂Data Racing，因為對於我們來說上面後兩部有不可分割性(Atomic).

而這時候我們就可以使用CAS算法來幫我們解決問題，在C#如果我們想要達成變數修改的Atomic可以透過Interlocked類別

使用Interlocked提高效率

在C#中我們可以使用Interlocked這個類別

對於Int,Long相關操作都有封裝成method.

下面這段虛擬碼解釋balance -= 10;CAS中類似下面效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//original
int temp = balance;
temp = temp -10;
balance = temp;

//CAS 
int oldValue = balance;
int newValue = oldValue - 1;
//compare value source and set
Interlocked.CompareExchange(ref balance,newValue,oldValue);

//Interlocked.CompareExchange類似下面做法，但具有Atomic
//if(ref balance == oldValue){
//	balance = newValue;
//}

主要是把compare value source and set這段包成一個不可分割區段達到Atomic.

＞ 我上面用ref來表示從記憶體位置取得balance原始資料

  • CompareExchange:把值改成另一個數值 具有Atomic (比較並交換)
  • Decrement:把數值– 具有Atomic
  • Increment:把數值++ 具有Atomic

除了上面我們還可以針對Reference Type做Atomic有興趣的人在自行了解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Program
{
	static object _lock = new object();
	static void Main(string[] args)
	{
		Stopwatch sw = new Stopwatch();
		int balanceValue = 10000000;
		Member member = new Member() { Balance = balanceValue };
		List<Task> tasks = new List<Task>();
		sw.Start();
		for (int i = 0; i < 1000000; i++)
		{
			tasks.Add(Task.Run(() => member.UpdateBalance()));
		}
		Task.WaitAll(tasks.ToArray());
		sw.Stop();
		Console.WriteLine("Lock Version");
		Console.WriteLine($"member remaining balance is {member.Balance}");
		Console.WriteLine($"Exec Time Cost : {sw.ElapsedMilliseconds}");

		tasks.Clear();
		member.Balance = balanceValue;
		sw.Restart();
		for (int i = 0; i < 1000000; i++)
		{
			tasks.Add(Task.Run(() => member.UpdateBalanceByInterlock()));
		}
		Task.WaitAll(tasks.ToArray());
		sw.Stop();
		Console.WriteLine("InterLocked Version:");
		Console.WriteLine($"member remaining balance is {member.Balance}");
		Console.WriteLine($"Exec Time Cost : {sw.ElapsedMilliseconds}");

		Console.ReadKey();
	}
}

public class Member
{
	object _lock = new object();

	public int Balance;

	public void UpdateBalance()
	{
		lock (_lock)
		{
			Balance -= 10;
		}
	}

	public void UpdateBalanceByInterlock()
	{
		int val;
		do
		{
			val = Balance;
		}
		while (val != Interlocked.CompareExchange(ref Balance, val - 10, val));
	}
}

下圖是比較兩者執行時間還有併發計算數值，能發現數值兩個都正確計算出0，但Interlocked執行時間少於lock版本.

Interlocked效率會比較高是因為block會造成Thread的blocking等待浪費,但Interlocked核心概念是在這段話Atomic取得資料跟原職比較(如果資料還沒改就把值修改進Memory中)

所以效率就會比lock好很多

小結

在有些情境適合使用Lock(例如許多操作需要有一致的Atomic)就比較適合.

Interlocked適合用在對於數值的Atomic.

在多執行緒的世界中要顧慮的點真的很多，稍有不甚就會造成很多錯誤.

因為多執行緒有許多地方需要注意,不然執行效率會不如單執行緒.

我慢慢可以理解為什麼Redis,Node.js一開始要使用 single Thread 來運作了…

__此文作者__：Daniel Shih(石頭)
__此文地址__： https://isdaniel.github.io/high-concurrency-atomic-cas-algorithm/
__版權聲明__：本博客所有文章除特別聲明外，均採用 CC BY-NC-SA 3.0 TW 許可協議。轉載請註明出處！

Related Posts
如果本文對您幫助很大，可街口支付斗內鼓勵石頭^^