---
# System prepended metadata

title: 04_行程與執行緒概論

---

---
title : 04_行程與執行緒概論
---

# 行程與執行緒概論

by CY, Tsai 
Date : 2021-07-23

---

## 壹、Program? Process? Thread?
這裡我用我自己的記憶方式說明這三者各自代表的意義。首先是Program，意思是在IDE或文本編輯器等所寫出的程式碼，尚未開始執行者叫做Program，可以把建造房屋、工廠的設計圖當成Program。

再來是Process, 中文翻譯為"行程"，顧名思義Process就是一個Program的執行過程(動工)，而且是照著Program(設計圖)下去做的，所以可以衍伸出以下幾個Process的重點:
* Process 是 Program 的實體
* 每個 Process 是互相獨立的，彼此不會互相干涉。
* Process 會占用部分系統資源達成工作，例如: RAM, CPU, 螢幕...
* 因為上述幾點，Process的排程(Scheduling)還有有效的使記憶體是OS很重要的工作之一

最後是Thread，這邊的疑問是既然Process就是Program的實體，並且OS會對其進行管理，那Thread的用意在哪裡?Thread又是屬於/獨立在哪裡?其實Process還有一個重點沒提到，它其實是Thread的容器，意味著在同一個Process可能會有多個Thread，而每個Thread會對應到各自所負責的工作，也就是說Process是一個工廠，這個工廠是根據Program所建造而成，而工廠裡的員工就是所謂的Thread。所以Thread會有以下幾的重點:
* 同一個Process 會同時存有多個Thread
* 屬於同一個Process之下的Thread共享這個Process的資源
* 因為上述幾點，在多執行緒的程式中，同時存取會有同步問題(Synchronization)以及資源如何分配給各個Thread的問題，是OS很重要的工作之一
![](https://i.imgur.com/8S19dZH.png)

## 貳，現在程式與執行緒的關係
現在程式中，有許多需要分工且達到同步的效果，例如通訊軟體在收發訊息時是單獨的一個Thread，而處理來電的Thread也是單獨的，同屬於這個軟體的Process，但這兩個Thread是同步處理的，總不可能在發送消息時，電話就打不進來吧！另外在惡意程式中，多執行緒是很重要的，例如簡單的鍵盤紀錄器，這個Process需要同時記錄使用者按下什麼鍵，同時將按鍵編碼傳回駭客的伺服器，甚至駭客會透過網路下指令做更多的操作。

不管是惡意程式，還是日常使用的軟體，沒有執行緒是無法做到這麼多功能的，為了這些程式的寫作，執行緒的應用必須徹底的了解。


---

## 參、核心物件
建立核心物件，或稱內核物件，會取得核心物件控制碼(HANDLE)。可以很簡單的理解成去公家機關，常常會抽取號碼牌，而號碼牌又會分為辦理一般業務、特殊業務等，根據要做的事情抽取號碼牌，要注意的是，如果拿著特殊業務的號碼牌去一般業務的櫃檯，那勢必完成不了要做的事情了，而HANDLE的用意就是如此，它可以控制現有的或是新建立的核心物件做到特定的動作。
下圖是來自Windows說明文件的示意圖:
![](https://i.imgur.com/YlBoSdR.png)

應用程式使用CreateEvent()函數建立一個Event object, 而函數的回傳值就是該物件的HANDLE。
當然不是只有這個函數可以取得物件的HANDLE，還有很多像是建立執行緒也會回傳該執行緒的HANDLE，建立新檔案也會回傳該檔案的HANDLE等等，無法一一列舉出來。

## 肆、創建執行緒
### 1.如何選擇
這邊我使用的是Windows的API，所以有提供兩種方法建立執行緒，_beginthreadex 和 CreateThread, 以下說明應該使用哪個函數。

在說明如何選擇前，要先知道C run-time library(CRT)是什麼? 在C語言的kernel開發出來後，Dennis Ritchie 和 Brian Kernighan 就用C語言重寫了90%以上的UNIX系統函數，然後把其中最常用的部分獨立出來，便形成了CRT。然而在上個世紀1970年代，CRT已經被當時的程式設計師使用，但當時還沒出現執行緒的概念，所以在設計上沒有考慮到執行緒帶來的問題。

再來是CRT與Windows API的關系，Windows API 因為是 Windows 的一部份，當然Windows API也是在CRT之上編寫的。 在作業系統的編寫上，需要一個底層函式庫，為了完成基本且重複性高的工作，自然就有了Windows中的CRT, 但是為了增加針對Windows平台程式設計的需求，像是Thread等，自然只能建立在Windows API上。

在 Win32 API 中，創建線程的基本函數是 CreateThread，而 _beginthread(ex) 是C++ 運行庫的函數。為什麼要有兩個呢？因為CRT裡面有一些函數使用了全局變數，如果使用 CreateThread 的情況下使用這些CRT的函數，就會出現某個Ｔhread使用過的全局變數被另一個Thread拿去用的問題，而 _beginthreadex 為這些全局變數做了處理，使得每個線程都有一份獨立的「全局」變數。

如下文所示(引用自MSDN):
> A thread in an executable that calls the C run-time library(CRT) should use the _beginthreadex and _endthreadex functions for thread management rather than CreateThread and ExitThread; this requires the use of tje multithread version of the CRT. If a thread created using CreateThread calls the CRT, the CRT may terminate the process in low-mwmory conditions.

而_beginthreadex 處理數據的方法是當新的Thread透過此函數創建時，會建立一個新的區塊Ａ，裡面存放著該執行緒所需要處理的數據，當Ｔhread執行時，區塊Ａ會跟執行緒關聯，然後執行緒調用CRT時會取得Ａ的位址，然後再把要保護的變量放入Ａ區塊，達到執行緒之間的變量不會互相干擾的效果。

### 2.創建/關閉執行緒
_beginthreadex的函數定義：
```c=
uintptr_t _beginthreadex( // NATIVE CODE
   void *security,
   unsigned stack_size,
   unsigned ( __stdcall *start_address )( void * ),
   void *arglist,
   unsigned initflag,
   unsigned *thrdaddr
);
uintptr_t _beginthreadex( // MANAGED CODE
   void *security,
   unsigned stack_size,
   unsigned ( __clrcall *start_address )( void * ),
   void *arglist,
   unsigned initflag,
   unsigned *thrdaddr
);
```
* security : SECURITY_ATTRIBUTES結構的指標，此結構會判斷所傳回的控制碼是否可以由子進程繼承。 如果 Security 為 NULL ，則無法繼承控制碼。
* stack_size : 創建的執行緒堆疊大小，會設定成0
* arglist : 傳遞給執行緒的參數列表，一般設定成NULL
* initflag : 控制新執行緒之初始狀態的旗標。 設定 initflag 為0會立即執行，或設為以 CREATE_SUSPENDED 暫停狀態建立執行緒; 使用 ResumeThread 來執行執行緒。
* thrdaddr : 指向接收執行緒識別項的 32 位元變數。 如果是 NULL ，則不會使用它。

以上為MSDN說明文件。

另外會發現有兩個版本的定義，NATIVE CODE 與 MANAGED CODE，所以第三個參數就是指定使用__stdcall或是__clrcall的方式NATIVE CODE 是在執行前就編譯成機器碼，而MANAGED CODE 則是在執行階段才編譯。詳細資訊可以參考MSDN說明文件。

CloseHandle的函數定義：
```c=
BOOL CloseHandle(
  HANDLE hObject
);
```

唯一的參數就是要關閉的HANDLE object，而回傳值為有沒有成功關閉，若失敗回傳0並可以呼叫ＧetLastError取得錯誤。

### 3.實作創建多個執行緒
相同工作的執行序可以使用_beginthreadex搭配for loop就可以做到。
```c=
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <process.h>

UINT __stdcall fun(PVOID lp) {
    printf("ID of thread is : %d\n", GetCurrentThreadId());
    return 0;
}

INT main(){
    const INT thread_num = 5;
    HANDLE hd[thread_num];
    for (int i=0; i<thread_num; i++) {
        hd[i] = (HANDLE)_beginthreadex(
            NULL, 0, fun, 0, NULL
        );
    }
    WaitForMultipleObjects(thread_num, hd, TRUE, INFINITE);
    for (int i=0; i<thread_num; i++) {
    CloseHandle(hd[i]);
    }
    return 0;
}
```
以上是最簡單的多執行緒創建，通常會使用WaitForMultipleObjects進入等待狀態，讓所有執行緒執行完成，最後通過for loop關閉HANDLE。

## 伍、執行緒執行順序問題
下面用一個簡單的報數程式來凸顯執行緒執行順序的問題。
```c=
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <process.h>

UINT __stdcall fun(PVOID lp) {
    INT count = * (INT*) lp;
    printf("執行緒編號 %d, 報數 : %d\n", GetCurrentThreadId(), count);
    return 0;
}

INT main() {
    const int thread_num = 11;
    HANDLE hd[thread_num];
    int count_number[thread_num];
    int number = 0;
    for (int i=0; i<thread_num; i++) {
        count_number[i] = i+1;
        hd[i] = (HANDLE)_beginthreadex(NULL, 0, fun, &count_number[i], 0, NULL);
    }
    WaitForMultipleObjects(thread_num, hd, TRUE, INFINITE);
    for (int i=0; i<thread_num; i++) {
        CloseHandle(hd[i]);
    }
    
    return 0;
}
```
從執行結果來看，執行順序是不固定的，沒有依照排定的順序執行。

再來這個程式使用兩個執行緒，且兩個執行緒做同樣的工作，目標是處理完100份的文件，在合理預期的情況下，我希望結果是一個執行緒處理50份文件，且每份文件只透過一個執行緒處理，以下是程式碼：
```c=
#include <stdio.h>
#include <Windows.h>
#include <process.h>

#define ALL_DOCUMENT 100
#define TOTAL_THREAD 2

volatile LONG Document_Number = 0;
INT DOCUMENT_Counter[ALL_DOCUMENT];

UINT __stdcall fun(PVOID lp) {
    
}
```

這個程式輸出兩件事情，第一是該文件被哪個執行緒處理，第二是該文件被處理幾次。然而從輸出結果得知，結果不如預期，有些文件被處理超過一次，原因也是因為執行緒未經協調就開始各自的工作所造成的。


從上面的例子可以發現，執行緒是需要經過協調的，不然多執行緒的程式執行結果會不可預期，以下會探討多執行緒的協調問題的解決方法。

## 陸、不可分割的運算
在第二個例子中，有出現Sleep(rand()%2)這行，在讓Document_Number更新前有一小段延遲，會不會是因為這樣導致另一個執行緒在Document_Number更新前就存取了這個變數？那如果把這行拿掉就不會有問題了嗎？確實以這個例子而言，重複處理文件的數量會大大減少，但那是因為只有100份，如果是1000份呢？10000份呢？還是會有這種問題出現的！所以問題變得很簡單，只要讓存取變數一直到更新變數這段時間沒有其他的執行緒插隊進來就可以了！但是我剛開始有個疑問，就把更新的程式碼改成Document_Number++;不就好了嗎？但是其實這行程式碼還是可以拆分的，分成三個動作：從記憶體取出變數，加1，存回記憶體。很明顯有兩個地方會被插隊，所以問題無碼解決。

解決方法：InterlockedIncrement64，這個函數是給64位元變數的，他會將變數遞增1而且確保執行過程不會被其他的執行緒插隊，當然也有非64位元版本。
```c=
code in hear
```

從執行結果來看，確實已經達到我們的要求：所有文件經過一個執行緒處理，且沒有文件被重複處理，雖然執行順序依然不固定。

## 柒、執行緒的互斥

互斥：對於執行緒Ａ與執行緒Ｂ來說，同一時刻，僅限定其中一個執行緒對臨界資源進行操作，也就是說當Ａ在臨界區域時，Ｂ就必須等待，反之亦然。

而臨界資源、臨界區域又是什麼？其實在生活中有很多臨界資源，像是印表機就是一個，印表機疑次只允許一個執行緒使用，應該不會看到有印表機影印的結果是兩份文件融合在一起吧！而使用到臨界資源的那段程式碼就稱之為臨界區。
臨界資源的使用規範：
* 一次僅允許一個執行緒進入，其他想進入的必須等待
* 進入臨界區的執行緒必須在有限時間內退出並釋放臨界資源
* 無法進入臨界區的執行緒應釋放CPU資源避免“忙等”

更改上面的例子，加入臨界區的概念一樣可以達到執行緒協調的動作。
```c=
#include <stdio.h>
#include <Windows.h>
#include <process.h>
#include "INIT_.h"
#define MAX_DOCUMENT 100
#define TOTAL_STAFF 2

CRITICAL_SECTION CriticalSection;

UINT __stdcall Staff(PVOID lp) {
	INT Staff_Number = *(INT *)lp;
	while (Document_Number < MAX_DOCUMENT) {
		EnterCriticalSection(&CriticalSection);
		INT i = Document_Number;
		Sleep(rand() % 2);
		Document_Number = i + 1;
		LeaveCriticalSection(&CriticalSection);
		printf("Process Document %2d by staff %d\n", i, Staff_Number);
		Document_Counter[i]++;
	}
	return 0;
}

int run_CriticalSection() {
	HANDLE hd[TOTAL_STAFF];
	INT Staff_Number[TOTAL_STAFF];
	srand(GetTickCount());
	ZeroMemory(Document_Counter, sizeof(Document_Counter));
	InitializeCriticalSection(&CriticalSection);
	for (int i = 0; i < TOTAL_STAFF; i++) {
		Staff_Number[i] = i;
		hd[i] = (HANDLE)_beginthreadex(NULL, 0, Staff, &Staff_Number[i], CREATE_SUSPENDED, NULL);
	}
	printf("Stuff are ready\n");
	for (int i = 0; i < TOTAL_STAFF; i++) {
		ResumeThread(hd[i]);
	}
	WaitForMultipleObjects(TOTAL_STAFF, hd, TRUE, INFINITE);
	for (int i = 0; i < TOTAL_STAFF; i++) {
		CloseHandle(hd[i]);
	}
	for (int i = 0; i < MAX_DOCUMENT; i++) {
		printf("Document %2d processed by %d staff\n", i, Document_Counter[i]);
	}
	//DeleteCriticalSection(&CriticalSection);

	return 0;
}
```


接下來是互斥鎖(mutex)的使用，參考MSDN的說明，mutex物件是用來保護這些共享資源，確保同一時間只有一個一個執行緒或行程存取。可以使用CreateMutex函數創建mutex物件。當有執行緒要存取資源時，第一步就是要請求mutex的所有權，然後使用WaitForSingleObject等待回應，如果取得所有權便可以進行存取，結束後必須釋放mutex的所有權。

在使用mutex時，要避免死鎖(Deadlock)，然而什麼是deadlock?其中有一個情況是，如果同一個執行緒呼叫兩次mutex，但是因為mutex，已經被佔用，而佔用的就是自己，所以會陷入一個死循環，永遠處於等待的狀態。另一種情況是若存在兩個mutex，執行緒Ａ獲得mutex 1，執行緒Ｂ獲得mutex 2
，這時Ａ對2發出請求，但因為Ｂ佔有2，所以Ａ進入等待狀態，然後Ｂ對1發出請求，但因為Ａ佔有1，所以Ｂ進入等待狀態，所以兩個執行緒就一直處於等待狀態，然後就死鎖了。

```c=
#include <stdio.h>
#include <Windows.h>
#include <process.h>

#define TIMES 100
#define TOTAL_STAFF 5

HANDLE hmutex;

UINT __stdcall Staff1(PVOID lp) {
	INT Staff_Number = *(INT*)lp;
	for (int i = 0; i < TIMES; i++) {
		WaitForSingleObject(hmutex, INFINITE);
		printf("Staff %d get the mutex\n", Staff_Number);
		Sleep(rand() % 2);
		printf("Staff %d release the mutex\n", Staff_Number);
		ReleaseMutex(hmutex);
	}
	return 0;
}

int run_mutex() {
	HANDLE Staff_Handle[TOTAL_STAFF];
	INT Staff_Numbers[TOTAL_STAFF];
	srand(GetTickCount());
	hmutex = CreateMutex(NULL, FALSE, NULL);
	for (int i = 0; i < TOTAL_STAFF; i++) {
		Staff_Numbers[i] = i;
		Staff_Handle[i] = (HANDLE)_beginthreadex(NULL, 0, Staff1, &Staff_Numbers[i], CREATE_SUSPENDED, NULL);
	}
	printf("Stuffs are ready\n");
	for (int i = 0; i < TOTAL_STAFF; i++) {
		ResumeThread(Staff_Handle[i]);
	}
	WaitForMultipleObjects(TOTAL_STAFF, Staff_Handle, TRUE, INFINITE);
	for (int i = 0; i < TOTAL_STAFF; i++) {
		CloseHandle(Staff_Handle[i]);
	}
	CloseHandle(hmutex);
	return 0;
}
```


## 捌、執行緒的同步
同步：建立在互斥的基礎上，而達到執行緒的有序訪問。

### 1.Event
這裡使用事件(Event)同步機制，相較於前面互斥鎖或臨界區域有較高的彈性，一個事件分為激發態與未激發態，且分為兩個型別，手動重置與自動重置，以下為MSDN說明文件：


| Object | Description |
| -------- | -------- |
| Manual-reset event | An event object whose state remains signaled until it is explicitly reset to nonsignaled by the ResetEvent function. While it is signaled, any number of waiting threads, or threads that subsequently specify the same event object in one of the wait functions, can be released.     |
| Auto-reset event | An event object whose state remains signaled until a single waiting thread is released, at which time the system automatically sets the state to nonsignaled. If no threads are waiting, the event object's state remains signaled. If more than one thread is waiting, a waiting thread is selected. Do not assume a first-in, first-out (FIFO) order. External events such as kernel-mode APCs can change the wait order. |

簡單來說，手動重置只能用程式手動設定，當事件被激發，可以使用ResetEvent或是SetEvent設定。自動重置的意思是當事件被激發後，會自動恢復到未激發狀態，不須另外設定。

以下一樣用文件處裡的程式說明:
```c=
#include <stdio.h>
#include <Windows.h>
#include <process.h>
#include "INIT_.h"
#define MAX_DOCUMENT 100
#define TOTAL_THREAD 2
HANDLE Process1Done, Process2Ready, Process2Get;

volatile LONG Document_Number = 0;
INT Document_Counter[MAX_DOCUMENT];
UINT __stdcall Thread1(PVOID lp) {
	while (Document_Number < MAX_DOCUMENT) {
		printf("Process document %2d by staff 1\n", Document_Number);
		// process
		printf("Finish1 document %2d by staff 1\n", Document_Number);
		Document_Counter[Document_Number]++;
		SetEvent(Process1Done);
		WaitForSingleObject(Process2Ready, INFINITE);
		WaitForSingleObject(Process2Get, INFINITE);
		Document_Number++;
	}
	return 0;
}

UINT __stdcall Thread2(PVOID lp) {
	SetEvent(Process2Ready);
	while (Document_Number < MAX_DOCUMENT) {
		WaitForSingleObject(Process1Done, INFINITE);
		INT i = Document_Number;
		printf("Process document %2d by staff 2\n", i);
		SetEvent(Process2Get);
		printf("Finish2 document %2d by staff 2\n", Document_Number);
		Document_Counter[i]++;
		SetEvent(Process2Ready);
	}
	return 0;
}

int run_Event() {
	HANDLE hd[TOTAL_THREAD];
	ZeroMemory(Document_Counter, sizeof(Document_Counter));
	Process1Done = CreateEvent(NULL, FALSE, NULL, FALSE);
	Process2Ready = CreateEvent(NULL, FALSE, NULL, FALSE);
	Process2Get = CreateEvent(NULL, FALSE, NULL, FALSE);
	hd[0] = (HANDLE)_beginthreadex(NULL, 0, Thread1, NULL, 0, NULL);
	hd[1] = (HANDLE)_beginthreadex(NULL, 0, Thread2, NULL, 0, NULL);
	WaitForMultipleObjects(TOTAL_THREAD, hd,TRUE, INFINITE);
	CloseHandle(Process1Done);
	CloseHandle(Process2Get);
	CloseHandle(Process2Ready);
	for (int i = 0; i < MAX_DOCUMENT; i++) {
		printf("Document %2d processed by %d staffs\n", i, Document_Counter[i]);
	}
	return 0;
}
```
這邊有兩個執行緒，執行緒間用接力的方式處裡文件，假設Thread1有沒辦法完成的部分，所以Thread1做完的文件交給Thread2繼續做，預期結果為每份文件有經兩個執行緒處理。裡面有看到三個對Event的HANDLE，其中Process1Done的用意是當Thread1處理好一份文件時，要激活這個事件，告訴Thread2換他處理這份文件了，而Process2Ready則是Thread2激活的，意思是告訴Thread1可以把他手上的文件交給Thread1了，最後這個Process2Get的用意是告訴Thread1他已經成功拿到文件，Thread1可以取下一份文件處理，而為什麼要這個Process2Get呢?如果沒有，Thread1一把文件交給Thread2就取下一份文件，就會進行Document_Number++，這樣有可能Thread2拿到的文件是Thread1新取的那份。


### 2.Semaphore
另外還有一個同步機制叫做Semaphore，Semaphore機制有點像是去火車站櫃台買票(不是用悠遊卡那種)，通常會有三到四個櫃台，但是排隊不是直接排去某個櫃台，而是全部排成一列，等哪個櫃台閒置便會廣播"旅客請至1號窗口購票"。Semaphore可以控制最多可以處理多少執行緒的數量，以下會用Semaphore模擬買東西時結帳的情境:
```c=
#include <Windows.h>
#include <process.h>
#include <stdio.h>

#define MAX_CUSTOMER 100
#define TOTAL_CLERK 4

volatile LONGLONG Customer_Number = 0;
volatile LONGLONG Customer_Serving = 0;
INT Customer_Counter[MAX_CUSTOMER];
HANDLE Semaphore = NULL;

UINT __stdcall Clerk(PVOID lp) {
	INT Clerk_Number = *(INT*)lp;
	while (Customer_Number < MAX_CUSTOMER) {
		WaitForSingleObject(Semaphore, INFINITE);
		INT i = InterlockedIncrement64(&Customer_Number) - 1;
		printf("Serve customer %d by Clerk %d (%d)\n", i, Clerk_Number, InterlockedIncrement64(&Customer_Serving));
		Sleep(rand() % 4);
		printf("Serve customer %d by Clerk %d (%d) done\n", i, Clerk_Number, InterlockedDecrement64(&Customer_Serving));
		ReleaseSemaphore(Semaphore, 1, NULL);
		Customer_Counter[i]++;
	}
	return 0;
}

int run_Semaphore() {
	HANDLE Clerk_Handles[TOTAL_CLERK];
	Semaphore = CreateSemaphore(NULL, TOTAL_CLERK, TOTAL_CLERK, NULL);
	INT Clerk_Numbers[TOTAL_CLERK];
	srand(GetTickCount());
	ZeroMemory(Customer_Counter, sizeof(Customer_Counter));
	for (int i = 0; i < TOTAL_CLERK; i++) {
		Clerk_Numbers[i] = i;
		Clerk_Handles[i] = (HANDLE)_beginthreadex(NULL, 0, Clerk, &Clerk_Numbers[i], CREATE_SUSPENDED, NULL);
	}
	printf("Stuffs are ready\n");
	for (int i = 0; i < TOTAL_CLERK; i++) {
		ResumeThread(Clerk_Handles[i]);
	}
	WaitForMultipleObjects(TOTAL_CLERK, Clerk_Handles, TRUE, INFINITE);
	for (int i = 0; i < MAX_CUSTOMER; i++) {
		printf("Customer %2d processed by %d Clerks\n", i, Customer_Counter[i]);
	}
	CloseHandle(Semaphore);
	return 0;
}
```