---
tags: ncku-course
---
# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`0140454`>
## 資料閱讀
### 軟體開發現況
#### [The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software](http://www.gotw.ca/publications/concurrency-ddj.htm)
* 過去
過去30年內，CPU Designer 從三大領域中提升執行效能，分別是「Clock Speed」、「Execution Optimization」以及「Cache」。
* 現在
但這幾年來，CPU Designer 為了榨乾 CPU 的效能，有可能利用激進的 Instruction Reordering，進而讓程式執行結果與預期的有所不同。
而在短期內，CPU 的效能增長來源將改為「Hyper-threading」、「Multi-core」以及「Cache」。
* 未來
因為在硬體設計上遇到了一些瓶頸，而 Cache 的部份越來越大，所以未來會朝向 Concurrency 的方向發展。
Concurrency 的優點是各執行緒之間的控制流程相互獨立，而缺點主要是在透顧 lock 來同步化時所需要的成本極高。
#### [An Introduction to Lock-Free Programming](http://preshing.com/20120612/an-introduction-to-lock-free-programming/)
* What is lock-free?
簡易的分辨流程：
lock-free 中的 `lock` 其實不是指 mutex 等等，而是指 ==不會被鎖定==。
* Lock-free Programming Techniques
* **Atomic Operations**
所謂的 atomic operation 即該操作在系統中是不可再繼續被分割的操作。
目前各平台都有提供相關的 API，如 Windows 下的 `_InterlockedIncrement`、iOS 下的 `OSAtomicAdd32` 以及 C\++11 中的 `std::atomic<int>::fetch_add`。
但值得一提的是，C\++11 的 atomic operation 並沒有保證他是 lock-free 的，所以必須透過 `std::atomic<>::is_lock_free` 來確認。
* Compare-And-Swap
最被廣泛討論的 atomic operation 方法。過程就是「先從記憶體中讀取資料，若與預期的相同才將新的值寫入」。但必須要注意到 [ABA Problem](https://zh.wikipedia.org/wiki/%E6%AF%94%E8%BE%83%E5%B9%B6%E4%BA%A4%E6%8D%A2#ABA.E9.97.AE.E9.A2.98)。
* Sequential Consistency
在所有執行緒中，對記憶體的操作會依尋著特定的順序進行，而且也會與程式碼中的順序一樣。
#### [Acquire and Release Semantics](http://preshing.com/20120913/acquire-and-release-semantics/) & [Weak vs. Strong Memory Models](http://preshing.com/20120930/weak-vs-strong-memory-models/)
透過 Acquire and Release Semantics 來限制優化，讓記憶體相關操作必須在特定語句前後完成。
```
+----------------------------------------+
| Acquire Semantics |
+----------------------------------------+ <<= 所有記憶體操作要在此線之下執行
| |
| .... |
| |
+----------------------------------------+ <<= 所有記憶體操作要在此線之前執行
| Release Semantics |
+----------------------------------------+
```
* Memory Barrier
透過一些指令防止 CPU 對一些記憶體操作進行重排。共分4種 Barrier。
* LoadLoad
* StoreStore
* LoadStore
* StoreLoad
* Weak vs. Strong Memory Model
所謂的 Weak 就是指有很大的機率會將 load/store 指令進行重排，而 Strong 則相反。
---
### Concurrency 相關
#### Concurrency vs. Parallelism
Concurrency 指的是兩個以上的工作 **相互交錯** 執行。
而 Parallelism 則是指兩個以上的工作 **同時** 執行。
#### Concurrency 系列文章
因為編譯器會最佳化程式碼的執行順序、處理器會亂序執行、硬體又可能有 Cache coherent 的問題，所以程式實際的執行過程和我們寫的不一定相同。
* Sequenced-Before
在同 thread 下，對求值順序關係的描述。
以 A is sequenced-before B 為例，也就是 A 會先求值完後才開始進行 B 的求值。
所以當有 A is sequenced-before B 且 B is sequenced-before A 的情況發生時，表示我們無法確定他的求值順序，抑或是他們是同時求值。
* Happens-Before
前一個操作的效果在後一個操作執行之前必須要可見。
happens-before 所關注的是 ==在執行前可見==，不同於 happening-before 是 ==發生的順序==。
而在同一個 thread 中的 happens-before 就是上面提到的 sequenced-before。
* Synchronized-With
發生在兩個不同 thread 間的同步行為。當 A is synchronized-with B 時，代表 A 對記憶體操作的效果，對於 B 是可見的。而 A 和 B 是兩個不同的 thread 的某個操作。
換句話說，synchrozied-with 就是不同 thread 間的 happens-before。
* Sequential Consistency
正如上面提到的，系統在執行時都維持程式原有的順序。在文章中舉 Dekker's algorithm 為例子，說明其重要性。
---
#### Thread Pool
Thread 雖然可以說是一個 lightweight process，但是在 create 跟 destroy 的時候還是需要一定的成本。
所以就有了 thread pool 這個概念，thread pool 讓我們在一開始先建立 worker thread，當有工作進來的時候先丟入 work queue，然後再指派給各 worker thread。
這中間免去了頻繁的 create 與 destroy，進而使得程式的效率以及工作的分配變得更好。
* 常見的實作方式
只擁有一個 work queue，必須仰賴 mutex 等方式來確保正常的執行。
* Lock-free 的實作方式
利用 mutex 來實作的 memory pool 必定會受到 mutex 的成本所影響，因此便有利用 CAS 等等的 atomic operation 來實作的版本。
作業說明中提及的 LFTPool 便是讓每個 work thread 擁有自己的 queue，當有工作進來的時候，利用 round-robin 的方式分配下去。
## 案例分析
### 正確性驗證
將優化版本的 linked list 印出後與原本的 words.txt 做比較，可以發現少了4個單字。
```shell=
$ colordiff -Naur dictionary/words.txt sorted.opt.words.txt
--- dictionary/words.txt 2016-10-03 10:59:13.531775949 +0800
+++ sorted.opt.words.txt 2016-10-06 02:32:27.803229037 +0800
@@ -1,7 +1,3 @@
-aaaa
-aaaaa
-aaaaaa
-aaaaaaa
aaaaaaaa
aaaaaaaah
aaaaaaauugh
```
原因在於合併 linked list 的時候，不小心把各個 linked list 的第一個 node 給跳過了。
修正方法就是將 main.c 中的
```clike=105
pHead = app[i]->pHead->pNext;
...
etmp->pNext = app[i]->pHead->pNext;
```
改成
```clike=105
pHead = app[i]->pHead;
...
etmp->pNext = app[i]->pHead;
```
### 閱讀程式碼
#### main.c
* 利用 mmap 將檔案內容 map 到 VMA 中
```clike=
char *map = mmap(NULL, fs, PROT_READ, MAP_SHARED, fd, 0);
```
* 先分配好所有 entry 的記憶體
fs 是檔案大小，因為檔案已經對齊了
所以 fs / MAX_LAST_NAME_SIZE 就等同於行數
```clike=
entry *entry_pool = (entry *) malloc(sizeof(entry) *
fs / MA X_LAST_NAME_SIZE);
```
* 設定 Concurrency Level
我們可以透過 `pthread_setconcurrency()` 來提示系統。預設而言，concurrency level 為 0，也就讓系統自行決定。
除此之外，man page 的 NOTES 也提到，當系統的 thread model 為 1:1 時，這個函數是沒有太大的意義。
```clike=
pthread_setconcurrency(THREAD_NUM + 1);
```
> 在 pthreads 的 [man page](http://man7.org/linux/man-pages/man7/pthreads.7.html) 中提到，對於 POSIX threads 的實作，Linux 不外乎分為 LinuxThreads 與 NPTL。可這兩種方式都是 1:1 的 model，所以在這邊是否有用呢？ [name=吳勃興]
#### phonebook_opt.c
* 準備 thread argument
`new_append_a()` 是負責準備要傳入 append 的參數。
在命名上有點讓人看不出來，在下一個區塊 Code Refactoring 會修改一下。
```clike=
append_a *new_append_a(char *ptr, char *eptr, int tid, int ntd,
entry *start)
```
* 建立 linked list
`append()` 會將資料放入一開始所分配好的 memory pool 中。
第一個 thread 負責的行數是：1、1 + THREAD_NUM、1 + THREAD_NUM * 2、...
第二個 thread 負責的行數是：2、2 + THREAD_NUM、2 + THREAD_NUM * 2、...
剩下的以此類推。
### Code Refactoring
#### main.c
* 將 [Line 50](https://github.com/0140454/phonebook-concurrent/blob/3c3f16e7adbcb409d1a6840b67b25efc557b2937/main.c#L50) 的 include directive 移到檔案的開頭，方便閱讀。
```clike=
#ifdef OPT
#include "file.c"
#include "debug.h"
#include <fcntl.h>
#define ALIGN_FILE "align.txt"
#endif
```
* 將 [Line 104](https://github.com/0140454/phonebook-concurrent/blob/3c3f16e7adbcb409d1a6840b67b25efc557b2937/main.c#L104) 中的 `i == 0` 狀況移到 for-loop 外，減少 branch 的時間。
```clike=
pHead = app[0]->pHead;
e = app[0]->pLast;
for (int i = 1; i < THREAD_NUM; i++) {
e->pNext = app[i]->pHead;
e = app[i]->pLast;
}
```
#### phonebook_opt.[ch]
* 傳遞給 `append()` 用的結構如下，有些命名並不是那麼直觀，而且風格不太統一。
```clike=
typedef struct _append_a {
char *ptr;
char *eptr;
int tid;
int nthread;
entry *entryStart;
entry *pHead;
entry *pLast;
} append_a;
```
修改後如下
```clike=
typedef struct __APPEND_ARGUMENT {
char *pDataStart;
char *pDataEnd;
int tid;
int nThread;
entry *pListHead;
entry *pListTail;
} append_argument;
```
* 在 `append()` 中的 for-loop 有一點難閱讀，改成 while-loop 會比較好一點。
```clike=
int count = 0;
entry *new_node = app->pListHead;
char *cur_last_name = app->pDataStart;
while (cur_last_name < app->pDataEnd) {
app->pListTail = app->pListTail->pNext = new_node;
app->pListTail->lastName = cur_last_name;
app->pListTail->pNext = NULL;
cur_last_name += MAX_LAST_NAME_SIZE * app->nThread;
new_node += app->nThread;
++count;
}
```
* 在 main.c 跟 phonebook_opt.c 中都有 `diff_in_second()`，因此把他拉出來，放在 utils.c 中。
```clike=
#ifndef _UTILS_H
#define _UTILS_H
#include <time.h>
double diff_in_second(struct timespec t1, struct timespec t2);
#endif
```
* 在編譯的時候可以看到一個 warning message
```shell=
phonebook_opt.c: In function ‘append’:
phonebook_opt.c:46:12: warning: variable ‘cpu_time’ set but not used [-Wunused-but-set-variable]
double cpu_time;
^
```
原先 `cpu_time` 是為了要讓 dprintf 來輸出，但是在沒有 define DEBUG 的情況下，會使得他成為未始用的變數。
為了維持原本的設計，所以我利用 `#ifdef DEBUG` 和 `__attribute__((unused))` 來避免這個訊息。
```clike=
#ifdef DEBUG
double cpu_time;
#else
double cpu_time __attribute__((unused));
#endif
```
### Thread Pool
在原本的程式中就如同下圖一般，會等到所有 thread 都 join 完後才會繼續下去。
可是這就有個問題，有些 thread 做的很快，有些 thread 做的很慢，這樣的話先完成的要在那邊呆呆的等。因此，在這邊會換成 thread pool 來實驗看看。
#### 原始版本
#### Thread Pool (mutex)
上圖更換至 threadpool-mbrossard 的結果。在 `append()` 的部份快了 0.00003 秒附近。
## 參考資料
* [Toward Concurrency](https://hackmd.io/s/H10MXXoT)
* [Memory Barriers Are Like Source Control Operations](http://preshing.com/20120710/memory-barriers-are-like-source-control-operations/)
* [記憶體映射函數 mmap 的使用方法](http://welkinchen.pixnet.net/blog/post/41312211-%E8%A8%98%E6%86%B6%E9%AB%94%E6%98%A0%E5%B0%84%E5%87%BD%E6%95%B8-mmap-%E7%9A%84%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95)
* [pthread_setconcurrency(3) - Linux manual page](http://man7.org/linux/man-pages/man3/pthread_getconcurrency.3.html)
Sign in with Wallet
Connect another wallet