# [AIdrifter CS 浮生筆錄](https://hackmd.io/s/rypeUnYSb) : Multi-Thread
## Process vs Thread
- **Process**
- 只是一個 `container` 可以想像成 process 只是一個房子，真正做事情的是房子裡面的，一個 process 建立，裡面會有一個 primary thread，或有時候成為 main thread，當 primary thread 結束，process 就跟著結束
- **Thread**
每個 thread 有自己的 thread ID 以及 stack，Threads之間可以共用 **global variables, static variables**.　Thread可以是任意function，一個 thread 的生命週期從 function 第一行開始，到function 運行完畢就結束。

### How to terminate Process?
- Main thread returns
- 這個是最好的結束方式
- 可以考虑做到 **Graceful shutdown**
- Graceful shutdown : main thread 要結束之前先通知所有的 child threads，然後等它們把手頭上的事情做完再離開。
- 任何 Thread 決定 `exit()`
- 使用 `exit()` 將會導致整個 process 結束，而且會導致 **destructor(s)** 沒有被執行
- 被別的 process 所終止
- Windows 之下被別人 TerminateProcess()
- Linux 之下被別人 kill -9
- 當然，destructor(s) 也不會被執行

### Multi Process vs Mulit Thread

| Multi Process | Milti Thread |
| :------| :-----------|
| Pa(Ta) Pb(Tb) Pc(Tc) | Pa(Ta Tb Tc) |
| 1.Create Process(s) 需要較多資源 | 1. 一個 thread 沒寫好 (divide by zero)，全部跟著完蛋|
| 2.Create Process(s) 比較慢 | 2. Multi-thread programming 陷阱太多 |
| 3.交換資料比較困難 (要用IPC) | 2.1 Thread-safe problem<br> 2.2 Double free　 problem　<br> 2.3 Volatile <br> 2.4 Cache line problem|
| 4.效能較差，process 切換需要做context switch ｜

### Linux fork()

#include <sys/wait.h>
void main(void) {
	int n=10;
	pid_t pid;
	
	if ((pid=fork()) < 0) 
	    printf(“fork failed”);
	else if (pid == 0) { // child
	    n = n + 10;
	    printf(“child, n=%d\n”, n);
	}
	else { // parent
	    n = n + 20;
	    printf(“parent, n=%d\n”, n);
	}
}


:::info
[INFO] Parent use wait() or waitpid() until Child terminates
:::

- system ("a.out"); // 會等 a.out 執行完畢

ret = WEXITSTATUS(system(“a.out”));

- system (“a.out &”); // 不等待 a.out 執行
- Reference: http://www.linuxidc.com/Linux/2011-02/32125.htm

- 等待其它 process
- 用 busy waiting. 例如3rd lib -> libprocps

/* busy waiting */
FILE *fp=NULL;
int n=0;

do {	
	fp = popen(”ps gux | grep a.out | wc –l”, ”r”);
	fscanf(fp, “%d”, &n);
	fclose(fp);
	sleep(1);
} while (n > 1);
fp = NULL;

### Windows MFC Process
- system ("a.exe");
- Parent 等待 Child process

char szFilename[] = "a.exe";
STARTUPINFO si;
PROCESS_INFORMATION pi;
si.cb = sizeof(si); // si 必須先 initialize
CreateProcess (NULL, szFilename, NULL, NULL, FALSE,
                            0, NULL, NULL, &si, &pi);
WaifForSingleObject (pi.hProcess, INFINITE); // 等待 process
CloseHandle (pi.hProcess); // 這兩行不做的話會有 resource leak
CloseHandle (pi.hThread);

- `szFilename`不能直接寫 `a.exe`，必須透過一個變數，不然結果不保證。
- parameter 6 `0` 可以設定 **CREATE_NO_WINDOW** 在背景運行。
- parameter 10 `&pi` pi.hProcess 以及 pi.hThread 可以拿到 `Handle(s)`。
- 等待其它 process
- `CreateToolhelp32Snapshot()` 取得目前所有 processes，`Process32First()` and `Process32Next()` 取得 process 訊息

- 用 `szExeFile` 取得檔案名稱
- 用 `th32ProcessID` 取得 process ID
- 用 `OpenProcess()` 取得 process handle
- 用 `TerminateProcess()` 殺掉這個 process
- 用 `WaitForSingleObject()` 等待這個 process 結束
- 用 `GetExitCodeProcess()` 取得這個 process 結束後的 return value，如果是 **STILL_ALIVE** 代表還活著

HANDLE hSnapShot=0;
HANDLE hProcess=0;

// 取得目前所有的 process(es)
hSnapShot=CreateToolhelp32Snapshot (TH32CS_SNAPALL,NULL);

PROCESSENTRY32 pEntry;
pEntry.dwSize = sizeof(pEntry);
DWORD dwID;

// Get first process
Process32First (hSnapShot,&pEntry);

// Get all processes
while(1)
{
    BOOL hRes=Process32Next (hSnapShot,&pEntry);
    if(hRes==FALSE) // 已經找不到下一個 process, 跳出 while(1)
        break;

    // 看看是否是 a.exe, 也可直接用 stricmp
    if ((_tcsicmp(pEntry.szExeFile,_T(“a.exe”)) == 0)
    {
            dwID=pEntry.th32ProcessID; // 取得 process ID

            // 由 process id 取得 process handle
            if ((hProcess = OpenProcess(PROCESS_TERMINATE, 0, dwID)) != NULL)
            {
                TerminateProcess(hProcess, 9); // 送出訊息讓 a.exe 結束
                CloseHandle(hProcess);
                hProcess = 0;
            }
     }
}

## Multi-thread
### Base Thread-safe problem(global variable)
- 典型：有多個 Threads 修改同一個`Global variable`
- 因為 3 個 threads (main, aa, bb) 運行的順序不保證所以 j 的答案有可能是 `0, 2, 3, 5`，用**組語**的方式去思考。
- 已經確保 aa & bb 運行完畢，才去 printf (“%d”,j);但是 j 的答案還是有可能是 `2, 3, 5`
- Thread Safe Rule
- 所有這些修改的地方都有用 `Critical Ｓection` 等方式保證不被中斷

int j=0;

/*
* (3)load  r0, j
* (4)add  r0, r0, 2
* (5)store  r0, j
*/
aa()
{
      // critical section start
      j += 2;
      // critical section end
}

/*
* (1)load  r1, j
* (2)add  r1, r1, 3
* (6)store  r1, j
*/
bb()
{
      // critical section start
      j += 3;
      // critical section end
}

main() 
{
     create_thread ( aa );
     create_thread ( bb );

     // get j = 3 in this assembly language sequence
     printf(“j=%d\n”, j);
}

### Double free problem
- Thread A

aa() {
     char *s=NULL;
     s = (char *)malloc(100); // step 1
     …
     free (s); // step 2

     …

     free (s); // step 4 
}

- Thread B

bb() 
{
     char *s2=NULL;
     s2 = (char *)malloc(50); // step 3
     …
     …
     … (用到 s2)
     free (s2); // step 5 double free s pointer prbolem
}

> HEAP

char *s1 = mallo(100);
free(s1);
char *s2 = malloc(50)
free(s1)  // free到 &s2
free(s2) // crash here if &s1 == &s2

- Conclustion: **Crash!! 而且 bb() 無法 debug !!**
- **How To resolove Double free problem?**
- 宣告的時候要 initialize
- 所有 resource free 之後，全部改回 initialize value

// Memory
char *s=NULL;
s = (char *)malloc(100);
…
…
if (s) 
{
     free(s);
     s = NULL;
}

// File
FILE *fp=NULL;
fp = fopen(“aa.txt”,”r”);
…
…
if (fp) 
{
     fclose(fp);
     fp = NULL;
}

// Socket
int fd=0;
fd = socket(…);
…
…
if (fd) 
{
     close(fd);
     fd = 0;
}

### Compiler 過度優化: Volatile
- Compiler認為**g_flag**沒被修改過，自動做optimize

bool g_flag = false;

main() 
{
     create thread (aa);
     …
     while (!g_flag);  // 等待 aa 结束
     … // aa 做完了, 可以繼續往下
}

aa() 
{
     …
     …
     g_flag = true;  // 做完, set g_flag
}

- Analyze assembly language `while (!g_flag)`

// you think
label:    Load	r0 <- g_flag # r0 has chance be changed via assign g_flag
          Compare	r0 and true
          jne	label;       # jump not equal

- **Infinite Loop!!** `while()` nerver terminate.
- r0 has no chance to be **re-assign** via g_flag

// actually
	Load	r0 <- g_flag
label: 	Compare	r0 and true # if r0 is fasle
	jne	label;      # jump to label because r0 is not true

- 解決方法 1
- volatile bool g_flag=false;
- **在 global 變數之前加上 volatile**, 主動告訴 compile 這個變數不需要**Optimize**
- 使用時機
- Multi-thread
- 用 Global variable 當成 flag
- 用 Busy waiting 的方式去 test 這個 flag

- 解決方法 2
- 根本就不應該用 **Busy waiting** 的方式來做 **Thread synchronization**
- 請用 `event`, `conditional variable` 等方式

### Cache line Problem
- 有沒有可能，一段 multi-thread 程式在 single CPU 反而跑得比 multi CPU 還快很多?
>Memory Hierarchy

- What's **cache line**?


- How to resolve cache line problem ?