# 2017q1 Homework4(phonebook-concurrent)

contributed by<`yanang`>
###### tags: `yanang`

## 開發環境
* OS: Ubuntu 16.04 LTS
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
* Architecture: x86_64
* CPU 作業系統: 32-bit, 64-bit
* Byte Order: Little Endian
* CPU(s): 4
* Model name: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz
*
Linux yanang 4.8.0-36-generic
#36~16.04.1-Ubuntu SMP

## read
* [Concurrency系列(一): 理解Concurrency之路](http://opass.logdown.com/posts/784600-concurrency-series-1-the-road-to-understand-concurrency)
* atomic operation :
不可被中斷的一個或一系列操作，多對應特殊的 CPU 指令。在所有的線程同步機制裡原子操作是最迅速的，因為完全不需要加鎖。原子操作是實現 Lock-Free 最重要的武器。
* [Concurrency系列(二): 從Sequenced-Before開始說起](http://opass.logdown.com/posts/788206-concurrency-series-2-starting-from-sequenced-before)
* Evaluation - value computations and side effect
* A is sequeced-before B : A 必會在 B 之前完成
> 經典的未定義行為 i = i++
> 
> i++ 的 side effect 只 sequenced-before i++ 本身的 result，這個 side effect 可能發生在 assignment 之前或之後。
* [Concurrency系列(三): 朝Happens-Before邁進](http://opass.logdown.com/posts/797113-concurrency-series-3-happens-before)
* Happens-before in Java : 當行為 A happens-before B 時，代表 A 的效果可見，而且發生於 B 之前
* differnet between Sequenced-Before and Happens-before : sequenced-before 強調實際上的執行順序，而 happens-before 強調 "visible"-看起來先執行前者再執行後者的效果
> happens-before but not really execute first :
> A = B + 1;
> B = 1;
> 實際上執行時，編譯器有很大的空間可以對程式執行的順序做優化。
> movl B(%rip), %eax
> addl $1, %eax
> movl %eax, A(%rip)
> movl $1, B(%rip)
* Happens-before in c++ : (1) A is sequenced-before B (2) A inter-thread happens before B ( Sequenced-before 其實就是同一個 thread 內的 happens-before。)
* C++定義 inter-thread 的 happens-before : (1) A synchronizes-with B (A和B有適當的同步) (2) A is dependency-ordered before B (A和B有相依的順序關係)
* [Concurrency系列(四): 與Synchronizes-With同在](http://opass.logdown.com/posts/797957-concurrency-series-4-be-with-the-synchronizes-with-relation)
* 
* synchronizes-with是一種跨thread間的happens-before關係，可以透過過mutex lock, thread create/join、Aquire and release Semantic來建立
* [Concurrency系列(五): Sequential Consistency的代價](http://opass.logdown.com/posts/809449-concurrency-series-5-the-price-of-sequential-consistency)
* Sequential Consistency :(1)對於每個獨立的處理單元，執行時都維持程式的順序(Program Order) (2)整個程式以某種順序在所有處理器上執行
* Write Bufers with Bypassing Capability : 維持 Write->Read 的順序
* Overlapping Write Operations : 維持 Write->Write 的順序
* Non-Blocking Read Operations : 維持 Read->Read, Read->Write 的順序
* cache coherence protocol : 確保程式遵守 SC

## 初步測試
* $ make
* $ ./phonebook_opt

orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.002826 sec
execution time of findName() : 0.002683 sec

* $ make plot
## thread pool
### 概念
> a thread pool maintains multiple threads waiting for tasks to be allocated for concurrent execution by the supervising program.
> -- wiki
* 
### 實作

threadpool_t *threadpool_create(int thread_count, int queue_size, int flags);
int threadpool_add(threadpool_t *pool, void (*routine)(void *),void *arg, int flags);
int threadpool_destroy(threadpool_t *pool, int flags);

* 先創出 threadpool ，再用將要呼叫的 function 傳入
* threadpool_destroy 先判斷各個 thread 是否完成 ， 才 free(threadpool)
* 完成後遇到一個 bug ，程式時好時壞

yanang@yanang:~/phonebook-concurrent$ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
phonebook_opt: main.c:165: main: Assertion `findName(input, e) && "Did you implement findName() in " IMPL "?"' failed.
已經終止 (core dumped)

yanang@yanang:~/phonebook-concurrent$ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.003103 sec
execution time of findName() : 0.002744 sec

> 觀察 threadpool_add() 的回傳值，thread 正常執行
> 重新看一次 threadpool_destroy() 當中的 pthread_join 是否正常執行
> 發現我傳入的 flags 錯了導致無法正常執行
* 修改後重新執行 $ ./phonebook_opt

orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.003631 sec
execution time of findName() : 0.002710 sec

* $ make plot
> 時間少量的增加了，因為我在中間呼叫 thread_join 之後，就立刻 free(thread pool)
> 增加了釋放記憶體的時間
## 參考資料
* [C 的 Thread Pool 筆記](http://swind.code-life.info/posts/c-thread-pool.html)