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
如果本文對您幫助很大，可街口支付斗內鼓勵石頭^^