# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`jayfeng0225`>
###### tags: `jayfeng0225`
## 作業要求
* 在 GitHub 上 fork [phonebook-concurrent](https://github.com/sysprog21/phonebook-concurrent)，然後適度修改 `phonebook_opt.c` 和相關的檔案
* 除了修改程式，也要編輯「[作業區](/s/HykJUcnT)」，增添開發紀錄和 GitHub 連結
* 至少涵蓋研讀 [concurrency](/s/H10MXXoT) 教材的認知、程式正確性驗證、效能分析實驗 (必須要有圖表)，以及充份說明你如何改善效能
* 延續 [A01: phonebook](/s/S1RVdgza) 的開發方向，本作業著重於透過 POSIX Thread 來縮減 `alloc()` 的時間成本
* 詳細閱讀吳彥寬的[實驗](/s/BkN1JNQp)，指出他的實做缺失，並提出改進縮減 append() 時間的可行提案，接著開發程式來驗證
* 提示：可透過建立 thread pool 來管理 worker thread
* 第一週 phonebook 未完成和待改進項目也一併在 [phonebook-concurrent](https://github.com/sysprog21/phonebook-concurrent) 的基礎下進行
* 學習 [concurrent-ll](https://github.com/jserv/concurrent-ll) (concurrent linked-list 實作) 的 scalability 分析方式，透過 gnuplot 製圖比較 list 操作的效能
* 一併嘗試重構 (refactor) 給定的程式碼，使得程式更容易閱讀和維護。延續 [A05: introspect](/s/BkhIF92p)，不只是在共筆上用文字提出良性詳盡的批評，也該反映在程式碼的變革
* 務必使用 astyle 來對程式碼進行排版，詳細使用方式見 [README.md](https://github.com/sysprog21/phonebook-concurrent/blob/master/README.md)
## 閱讀資料整理
### Concurrency V.S Parallelism
先對Concurrency與Parallelism有最基本的了解：
* Concurrent : 兩個或以上的問題藉由單個processor來解決。將這些問題分割成多個task，並在不同時間點配給CPU來執行。
* 可能可以分享資源的多個execution flow
* 例如 : 競爭一個I/O port的兩個執行緒
* 為了提供interleaved execution來將task做分割
* Concurrency用來解決有==很少CPU資源且很多task的問題==。因此可以透過程式碼來產生執行緒或是獨立執行的路徑來達到分享時間或是稀少資源的目的。
* Parellelism : 單個問題透過多個processor來解決，同樣會將問題分成多個task，但是會同時分配多個CPU(processor)來執行，以便增加執行速度。
* 將問題切割成多個類似的chunk
* 例如 : 要parse一個很大的檔案時，藉由執行兩個processor在每半個檔案。
* ==相同時間執行將work的多個部分來達到加速的功用==
* Parallelism用來==解決有足夠且適當(可以正確切割)的task，並且將其分散在足夠的CPU資源上執行==。
```
oncurrency Concurrency + parallelism
___ ___ ___
|th1| |th1|th2|
| | | |___|
|___|___ | |___
|th2| |___|th2|
___|___| ___|___|
|th1| |th1|
|___|___ | |___
|th2| | |th2|
```
### [The Free Lunch Is Over ](http://www.gotw.ca/publications/concurrency-ddj.htm)
Speedups in any of these areas will directly lead to speedups in sequential (nonparallel, single-threaded, single-process) applications, as well as applications that do make use of concurrency. That’s important, because ==the vast majority of today’s applications are single-threaded, for good reasons that I’ll get into further below.==
#### Moore’s Law and the Next Generation(s)
儘管CPU這幾年來在clock speed上並沒有卓越的成長(近幾年已經有4Ghz的CPU出現)，但CPU的效能還是有所提升，其中仰賴的是多處理器技術時代的三種主要方法：
1. Hyperthreading
平行執行兩個以上的多執行緒在單個CPU上。已經是目前(2005)很普遍的做法，不過hyperthread的做法需要仰賴額外的硬體像是額外的暫存器，而其他如cache , integer math unit , FPU(floating point unit)等等也都只有單個。
而Hyperthrading的方法即使在寫得好的多執行緒程式上，最多也能夠提升5%~15%的效能，甚至在最理想的環境下最多也就只能提升到40%。雖然很好，但效能幾乎無法double，也因此無法幫助單執行緒的應用程式。
2. Multicore
多核心表示在晶片上執行兩個以上的實體CPU。效能初始大約可以相近於實體的雙核心(CPU)系統，這代表某些情況可能不會到兩倍的速度，而multicore只能夠提升寫得好的多執行緒程式，而無法提升單執行緒的應用程式。
3. Cache
最後提到的是cache，on-die cache的size持續在成長。提到的三個方法中只有這個方法能夠大大的讓多數既有的應用程式受惠。最簡單的原因就是，以空間換取速度。通常存取Main memory的速度會遠大於存取cache的速度(10~50倍)，因此如果執行應用程式的working set能夠符合cache的大小，那麼效率就會很好。這也就是為什麼增加cache size能夠讓多數的程式受惠，不論是單執行緒或是多執行緒的程式。隨著程式所需要的data越來越多，會需要更頻繁的update，也因此如果能夠符合cache，執行效能上就能夠大大提升。
` on-die cache : 是指內建在晶片上的快取記憶體，目前通常是指L1,L2 cache。`
相對於cache能夠提升程式效能，那麼hyperthreading與multicore對於程式幾乎沒什麼影響。因此，在硬體上做的這些改變表示我們要怎麼去設計我們的軟體。 --> concurrency
#### Benefits and Costs of Concurrency
Concurrency，特別是multithreading已經作為主流的軟體設計有兩個主要理由 :
1. 獨立的分開control flows
2. 效能問題，不論是大大的利用多個實體CPU或者是簡單的利用應用程式的latency。
Concurrency的cost :
1. locks的取得成本較高，但如果使用的好，那麼可以從concurrent code的到的好處會遠大於在synchronization的所失去的成本。
2. 第二個concurrency的成本為，不是所有的application都是適合平行化的。
3. 第三個最大的成本為，要實踐concurrency是很困難的。
---
## Code Refactoring
### 何謂Refactoring?
[對於重構的兩則常見誤解](http://www.ithome.com.tw/node/79813)
Martin Fowler的定義是「在不改變軟體外部行為的前提下，改變其內部結構，使其更容易理解且易於修改」
> 程式碼的maintainability? [name=JayFeng]
```
從這個定義上來看，為軟體增加功能肯定不能算上重構。那麼改善安全性或者是提升效能，算不算是重構呢？顯然也不能。
改寫程式碼，使得程式碼在不改變行為的情況執行得更快，這應該算最佳化而不能算是重構。
不過，也有一些人把這類型的「整理」，歸類在重構的範圍，這可以說是與Martin Fowler的原意不甚相符了。
```
:::info
所以，我們不能說提升效能是重構的目的，但是透過重構，使得程式碼更清晰易懂，那麼對於察覺既有的各種問題，都可以提供相當的幫助
:::
### 執行Refactoring的時機
* 開發時就該做好安排
* 增加新功能
* 修正錯誤
* 程式碼審查
### 實作在phonebook-concurrency
目前找到phonebook_opt.c的for loop似乎可以改用while loop來表示，原先的版本在for的更新值部份似乎改用while看起來會比較順眼。
修改的版本：
```clike=
char *i = app->ptr;
while(i < app->eptr)
{
app->pLast->pNext = j;
app->pLast = app->pLast->pNext;
app->pLast->lastName = i;
dprintf("thread %d append string = %s\n",
app->tid, app->pLast->lastName);
app->pLast->pNext = NULL;
// 更新值
i += MAX_LAST_NAME_SIZE * app->nthread;
j += app->nthread;
count++;
//
//
}
```
---
## mmap的使用
Reference : [記憶體映射函數 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)
linux提供記憶體映射函數，可以把文件內容直接映射到一段VMA。透過對這段記憶體的讀取與修改，實現對文件的讀取修改。
__使用mmap有以下好處__：
* 高速檔案存取。一般的I/O機制通常需要將資料先到buffer中。mmap免去了中間這一層，加速檔案存取速度。
* 可執行檔可對映到記憶體空間中，使程式動態載入。Linux Dynamic Loading便是如此實作出來的。
* 新的記憶體可以透過利用/dev/zero來產生全零的檔案。
* 新的記憶體可以用於執行目的，這對解譯式編譯器非常有用。
* 可把檔案當成記憶體來用，直接使用指標來操作。
* 對映的記憶體可當成process間共享記憶體，該記憶體內容存在檔案中，因此與process無關。
__使用方法__ :
```
函數：void *mmap(void *start,size_t length, int prot, int flags, int fd, off_t offsize);
```
* 參數start：指向欲映射的核心起始位址，==通常設為NULL，代表讓系統自動選定位址，核心會自己在進程位址空間中選擇合適的位址建立映射==。映射成功後返回該位址。如果不是NULL，則給核心一個提示，應該從什麼位址開始映射，核心會選擇start之上的某個合適的位址開始映射。建立映射後，真正的映射位址通過返回值可以得到。
* 參數length：代表映射的大小。將文件的多大長度映射到記憶體。
* 參數prot：映射區域的保護方式。可以為以下幾種方式的組合：
```
PROT_EXEC 映射區域可被執行
PROT_READ 映射區域可被讀取
PROT_WRITE 映射區域可被寫入
PROT_NONE 映射區域不能存取
```
* 參數flags：影響映射區域的各種特性。在調用mmap()時必須要指定MAP_SHARED 或MAP_PRIVATE。
```
MAP_FIXED 如果參數start所指的位址無法成功建立映射時，則放棄映射，不對位址做修正。通常不鼓勵用此旗標。
MAP_SHARED 允許其他映射該文件的行程共享，對映射區域的寫入數據會複製回文件。
MAP_PRIVATE 不允許其他映射該文件的行程共享，對映射區域的寫入操作會產生一個映射的複製(copy-on-write)，對此區域所做的修改不會寫回原文件。
MAP_ANONYMOUS 建立匿名映射。此時會忽略參數fd，不涉及文件，而且映射區域無法和其他進程共享。
MAP_DENYWRITE 只允許對映射區域的寫入操作，其他對文件直接寫入的操作將會被拒絕。
MAP_LOCKED 將映射區域鎖定住，這表示該區域不會被置換(swap)。
```
* 參數fd：由open返回的文件描述符，代表要映射到核心中的文件。如果使用匿名核心映射時，即flags中設置了MAP_ANONYMOUS，fd設為-1。有些系統不支持匿名核心映射，則可以使用fopen打開/dev/zero文件，然後對該文件進行映射，可以同樣達到匿名核心映射的效果。
* 參數offset：從文件映射開始處的偏移量，通常為0，代表從文件最前方開始映射。offset必須是分頁大小的整數倍(在32位體系統結構上通常是4K)。
範例程式：[小談 mmap() 與 VMA](http://www.jollen.org/blog/2007/03/mmap_vma.html)
```clike=
#include <stdio.h>
#include <fcntl.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#define FILE_LENGTH 0x400
int main(int argc, char *argv[])
{
int fd;
void *map_memory;
/* Open a file to be mapped. */
fd = open("/tmp/shared_file", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
lseek(fd, FILE_LENGTH+1, SEEK_SET);
write(fd, "", 1);
lseek(fd, 0, SEEK_SET);
/* Create map memory. */
map_memory = mmap(0, FILE_LENGTH, PROT_WRITE, MAP_SHARED, fd, 0);
close(fd);
/* Write to mapped memory. */
if (strlen(argv[1]) < FILE_LENGTH)
sprintf((char *)map_memory, "%s", argv[1]);
sleep(10);
exit(0);
}
```
---
## Posix Thread
Reference :
[POSIX Threads Programming](https://computing.llnl.gov/tutorials/pthreads/)
[Getting Started With POSIX Threads 宋振華](http://www.csie.ntu.edu.tw/~r92094/c++/pthread.txt)
[學習筆記：多執行緒 (1) - 從零開始](http://huan-lin.blogspot.com/2013/04/csharp-notes-multithreading-1.html)
[How to Create Threads in Linux (With a C Example Program)](http://www.thegeekstuff.com/2012/04/create-threads-in-linux/?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+TheGeekStuff+(The+Geek+Stuff))
## 原始程式碼
mmap
```
char *map = mmap(NULL, fs, PROT_READ, MAP_SHARED, fd, 0);
```
原始版本優化新增thread的部份
```clike=
/* allocate at beginning */
entry *entry_pool = (entry *) malloc(sizeof(entry) *
fs / MAX_LAST_NAME_SIZE);
assert(entry_pool && "entry_pool error");
pthread_setconcurrency(THREAD_NUM + 1);
//用來通知實作concurrency的函數
//宣告pthread與用來實作thread append的struct
pthread_t *tid = (pthread_t *) malloc(sizeof(pthread_t) * THREAD_NUM);
append_a **app = (append_a **) malloc(sizeof(append_a *) * THREAD_NUM);
//new_append_a(char *ptr,char *eptr, int tid , int ntd);
for (int i = 0; i < THREAD_NUM; i++)
app[i] = new_append_a(map + MAX_LAST_NAME_SIZE * i, map + fs, i,
THREAD_NUM, entry_pool + i);
clock_gettime(CLOCK_REALTIME, &mid);
for (int i = 0; i < THREAD_NUM; i++)
pthread_create( &tid[i], NULL, (void *) &append, (void *) app[i]);
for (int i = 0; i < THREAD_NUM; i++)
pthread_join(tid[i], NULL);
```
使用entry pool並且建立4個thread，設立類似分界點的概念。每個thread各自負責一個分界裡的append，最後再各自串起來。
另外則是使用pthread_join()函數，這樣的缺點可能會變成：必須等待前一個thread完成，下一個thread才會開始執行，因此當thread數量變多時，相對的等待時間也許會更長。假如使用Thread pool，更加彈性的使用每個thread，也許就可以減少append的時間。
基於這個假設，先畫出不同thread數量下append所需要的時間：
```
$ man pthread_join
NAME
pthread_join -- wait for thread termination
ESCRIPTION
The pthread_join() function suspends execution of the calling thread until the target
thread terminates, unless the target thread has already terminated.
```
__假如不使用pthread_join() ?__
[pthread simple example: pthread_join](http://eeepage.info/pthread-simple-example-pthread_join/)
pthread_join 是等待其他的執行緒結束後才會return
==寫的代碼中如果沒有pthread_join主執行緒會很快結束從而使整個process結束，從而使創建的兩個執行緒沒有機會開始執行就結束了，所以沒有輸出==。加入pthread_join後，主thread會一直等待直到等待的執行緒結束自己才結束，使創建的執行緒有機會執行。
==pthread_create 一建立執行緒之後即開始執行==
如果對於創建的執行緒如果不調用pthread_join，會造成什麼樣的後果
有可能子執行緒沒被執行完就退出主線程了！
能不能說清楚一下點，為什麼會這樣，如果在執行緒裡加上控制，應該就不會出現這個問題吧
When a joinable thread terminates, its memory resources (thread
descriptor and stack) are not deallocated until another thread performs
pthread_join on it. Therefore, pthread_join must be called once for
each joinable thread created to avoid memory leaks.
程式的主執行緒結束了， 這個執行緒的process就over了。 process結束時，其他執行緒就被清理了。也就是執行不到了。主要就是防止在子執行緒結束完之前結束主執行緒。
所以說，加個pthread_join，既可防止內存洩露，又可以知道子執行緒的退出狀態，而不是所謂的子執行緒無法運行下去。要知道執行緒還有一個狀態：DETACHED，就不需要pthread_join
[pthread_join和pthread_detach的區別](http://fanli7.net/a/caozuoxitong/Unix/20101002/41573.html)
```
但是調用pthread_join(pthread_id)後，如果該執行緒沒有運行結束，調用者會被阻塞
```
### Thread Pool
Reference :
- [C 的 Thread Pool 筆記](http://swind.code-life.info/posts/c-thread-pool.html)
- [Threading – using the ThreadPool vs. creating your own threads](http://theburningmonk.com/2010/03/threading-using-the-threadpool-vs-creating-your-own-threads/)
#### The problem with creating your own threads
- 建立與破壞thread是相當耗CPU資源的，因此如果處理的task屬於很多小而簡單的task，那麼在建出thread與破壞thread時會相當耗時。
- 特別是在執行很多執行緒時可能會利用到100%的CPU，但是可能多數的時間都浪費在context switching(在thread之間做切換)。
- 因此原來的程式版本，執行緒數量不多時，還是能夠有不錯的效能提升，但是當執行緒數量越來越多時，每個執行緒所執行的task越來越小，且越來越簡單(需要append的數量越來越少)，所以效能
- 使用thread pool可以避免建立與破壞thread的時間。
#### When not to use the Thread Pool
- 當thread的loading差異較大時
- 某個thread有特別的priority
- task可能會造成thread block很長的時間
- 需要把thread放到single-thread的部分
所以試著將程式改為thread pool的方式 :
Sign in with Wallet
Connect another wallet