# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`shelly4132`>

## 開發環境
* ### 作業系統：Ubuntu 16.04 LTS
* ### Cache：

	* L1d cache：32K
	* L1i cache：32K
	* L2 cache：256K
	* L3 cache：3072K


## Concurrency vs. Parallelism
* **Concurrency**：我們將一個程式分割成多個小部份稱為task，而concurrency就是在一個proccessor的情況下，在能保證其正確性的前提下對這些task進行並行運算(thread不一定會同時執行)。

![](https://hackpad-attachments.s3.amazonaws.com/embedded2016.hackpad.com_K6DJ0ZtiecH_p.537916_1460613316743_p1.png)

* **Parallelism**：parallelism則是指在多個proccessor的情況下，我們為了增進執行速度而對一個程式進行平行運算(同時執行多個thread)。
* 
![](https://hackpad-attachments.s3.amazonaws.com/embedded2016.hackpad.com_K6DJ0ZtiecH_p.537916_1460613329719_p2.png)

## Sequenced-before
sequeced-before就是一種在同一個thread下，求值順序關係的描述。


* 求值：可分為value computation(運算完的結果)和side effect(修改記憶體內變數的值、呼叫library內的I/O function等等)


1. 如果A is sequenced-before B，代表A的求值會先完成，才進行對B的求值
2. 如果A is not sequenced before B 而且 B is sequenced before A，代表B的求值會先完成，才開始對A的求值。
3. 如果A is not sequenced before B 而且 B is not sequenced before A，代表兩種可能，一種是順序不定，甚至這兩者的求值過程可能會重疊（因為CPU優化指令交錯的關係）或不重疊


雖然我們對運算優先權做了很多定義，比如說f1() + f2()會先計算完f1()和f2()才計算他們加起來的結果(運算元的運算優於運算子)，但仍有許多運算是未定義的。
比如說 ``` i = i++; ```，我們不知道究竟i會等於++後的結果還是等於i目前的值，因為我們沒有定義assignment跟```i++```的side effect的先後關係，所以讓程式產生了不確定性。

## Happens-before
happens-before就是指前一個操作的效果必須在下一個操作執行之前出現。
但happens-before並不是指前一行的程式碼必須先於後一行的程式碼執行，只要執行出來的結果++看起來++像是那樣，那後面的程式碼先被執行也沒關係。

* sequence-before其實就是同一個thread裡的happens-before。
* 在多個thread的情形底下如果變數共用，若沒有保證happens-before的關係的話，可能會導致程式出現意料之外的結果。


## Coroutines
* **Context Switch**：由OS根據一定的排程演算法，讓CPU一直保持有proccess在執行，而等到要執行某個proccess才把他的資料讀進記憶體，再把部份資料移出去的動作就叫context switch。
* **Coroutines**：由programmer利用一些程式技巧延遲執行某些task，讓程式不會因為某個要執行很久的東西而停頓。

	* coroutines的成本比context switch低

## POSIX Threads
* Proccess：一個 process 包括了一個執行中的程式，和一些
他所需的系統資源，諸如檔案描述表和位址空間等。

* Thread：thread 實質上就是一個程式計數器、一個堆疊再加上一組暫存器。一個proccess中可以有多個thread，而這些thread都共享同一個記憶體資源。

### 基本用法
* 宣告一個執行緒 ```pthread_t a_thread;```
* ``` pthread_attr_t ``` ：thread attribute 描述 thread 的一些特性，目前我們遇到的大部份程式只需要指定為``` pthread_attr_default ```就好。
* ```pthread_create( &a_thread, a_thread_attribute, (void)&thread_function, (void *) &some_argument);```：產生一個thread並執行傳進去的function。

### 同步問題
* Race Condition：當有2個以上的thread共享同樣的資料，並且他們同時都嘗試去改變它，那最後的結果會因為不同的thread先被執行而有不同。

#### mutex
mutex就像一把鎖，可以保護共享的資源。
* 宣告一個mutex變數``` pthread_mutex_t mutex;```
* 初始化mutex``` pthread_mutex_init(&mutex, pthread_mutexattr_default);```
* 將mutex鎖起來，直到解鎖前其他thread不能存取被保護的共享資源``` pthread_mutex_lock( &mutex ); ```
* 將mutex解鎖``` pthread_mutex_unlock( &mutex ); ```
* 當我們不再需要mutex之後可以使用``` pthread_mutex_destroy(&mutex); ```來釋放mutex


## phonebook-concurrent
### 執行看看
 THREAD_NUM 4
* cache miss

Performance counter stats for './phonebook_opt' (100 runs):

31,0883 cache-misses # 22.999 % of all cache refs ( +- 0.61% )
135,1713 cache-references ( +- 1.27% )
2,2886,1173 instructions # 1.10 insns per cycle ( +- 0.04% )
2,0871,7787 cycles ( +- 0.72% )

0.149621109 seconds time elapsed ( +- 2.18% )

![](https://i.imgur.com/MidMRuo.png)

### 理解code

#### mmap
將<s>文件</s>檔案的內容映射到一段虛擬記憶體上，通過對這段記憶體的讀取和修改，實現對文件的讀取和修改。
>> 請尊重傳統文化，書寫台灣慣用科技術語。file = 檔案 [name=jserv]
>> 好的>< 
[name=shelly4132]

void *mmap(void *start,size_t length, int prot,
int flags, int fd, off_t offsize);

* start
	指向欲映射的核心起始位址，通常設為NULL，代表讓系統自動選定位址，核心會自己在行程位址空間中選擇合適的位址建立映射，映射成功後會返回該位址。
* length
	代表映射的大小。將的大小映射到記憶體。
* prot
	映射區域的保護方式。
	* PROT_EXEC 映射區域可被執行
	* PROT_READ 映射區域可被讀取
	* PROT_WRITE 映射區域可被寫入
	* PROT_NONE 映射區域不能存取
* flags
	影響映射區域的各種特性。
	* MAP_SHARED 允許其他映射該檔案的行程共享，對映射區域的寫入數據會複製回文件。
	* MAP_PRIVATE 不允許其他映射該檔案的行程共享，對映射區域的寫入操作會產生一個映射的複製(copy-on-write)，對此區域所做的修改不會寫回原檔案。
* fd
	由open返回的檔案描述符，代表要映射到核心中的檔案。
* offsize 
	從檔案映射開始處的偏移量，通常為0，代表從檔案最前方開始映射。

### Code Refactoring
* 將_append_a裡面的nthread刪掉，有需要用到thread數目的統一用THREAD_NUM代替，還可以減小entry size。
* 將append()裡面原本很多參數的for迴圈改成while讓程式比較好看。
* 利用彥寬學長寫的show_entry()去將字串印出來時發現有缺失，因為在將所有entry串成一條的時候，他一開始就從pNext開始所以導致前面4個字串被漏掉了，改成從pHead開始就ok了。

### 改進方向
* Thread pool
	建立thread需要系統資源，如果我們每次需要的時候才建立thread，不要的時候就丟掉，當數量多時其實是會降低效能的。所以thread pool的概念就是建立一個thread的池子，當需要thread的時候就從裡面拿，不用的時候再放回去，有效的重複利用資源。

* [threadpool-mbrossard](https://github.com/mbrossard/threadpool)

* 建立一個task，讓thread知道要做什麼事。這裡我們紀錄要執行的 function pointer 與要傳遞的參數。

typedef struct {
void (*function)(void *);
void *argument;
} threadpool_task_t;

* 使用 pthread_t的pointer來紀錄所有thread(array)，head和tail用來紀錄array的offset

struct threadpool_t {
pthread_mutex_t lock;
pthread_cond_t notify;
pthread_t *threads;
threadpool_task_t *queue;
int thread_count;
int queue_size;
int head;
int tail;
int count;
int shutdown;
int started;
};

![](https://i.imgur.com/J58TqwL.png)



## 參考
* [Toward Concurrency](https://hackmd.io/s/H10MXXoT)
* [Concurrency系列(二): 從Sequenced-Before開始說起](http://enginechang.logdown.com/posts/788206-concurrency-series-2-starting-from-sequenced-before)
* [Concurrency系列(三): 朝Happens-Before邁進](http://enginechang.logdown.com/posts/797113-concurrency-series-3-happens-before)
* [淺談coroutine與gevent](http://blog.ez2learn.com/2010/07/17/talk-about-coroutine-and-gevent/)
* [Getting Started With POSIX Threads  (繁體中文翻譯)](http://www.csie.ntu.edu.tw/~r92094/c++/pthread.txt)
* [彥寬學長的筆記](https://hackmd.io/s/BkN1JNQp)與[影片](https://www.youtube.com/watch?v=sWtWslsr4Ac)
* [記憶體映射函數 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)
* [threadpool-mbrossard](https://github.com/mbrossard/threadpool)
* [TempoJiJi](https://hackmd.io/s/rymKa4aT)