phonebook concurrent
===
contributed by <`snoopy831002`>
## concurrency
* concurrency 的開始：cpu的演進不再以提昇時脈為方向，多核與多執行序的時代來臨
* 未來的效能效能提昇方向：

1. hyperthread(多執行序並行處理task)
2. multicore(核心多自然處理的快)
3. cache(cache大小的增加與速度的提昇對效能影響顯著)
* 未來程式的執行效能將不仰賴cpu的速度快慢，而是程式的平行化。
* lock 與 lock-free programming(核心目標為使程序間可互相溝通順利)
1. lock：包含mutex與semephore等，防止程序競爭同一記憶資源
2. lock-free:沒有使用mutex與semephore等，但能達到locK者
* concurrency v.s parallelism
1. concurrency指的是一次可以做很多事情：If two or more problems are solved by a single processor.(multi-thread)
2. parallelism指的是很多事情同時在發生:If one problem is solved by multiple processors.

* concurrency所產生的問題：
1. 多執行序競爭同ㄧ資源
2. thread之間的不同步行為
* 使用mutex或semephore改善
* 確保在寫入或讀取共享記憶體資源之操作是atomic的
* 必要時取消編譯器優化，因可能會有memory reordering所產生的不同步行為
* coroutine
* tasks are cooperatively multitasked by pausing and resuming functions at set points.(使原本單向執行的程式碼可以有交錯執行的結果)
## mmap
因為原始使用fget的緣故，城市無法平行化，所以造成append()的時間一直無法有效縮短。故吳彥寬同學使用了mmap

 void *mmap(void *addr, size_t length, int prot, int flags,
                  int fd, off_t offset);
       

1.addr可以設定起始位置
2.length決定mapping大小
3.flags可以決定是否可供其他thread看見
4.offset則由fd決定
## pthread
* Why not use a process?
* threads are light weight processes
* threads can be created with much less operating system overhead compared to processes.
* Pthread 的建立

  pthread_t         a_thread;//定義thread
  pthread_attr_t    a_thread_attribute;//通常使用pthread_attr_default即可
  void              thread_function(void *argument);//thread 所要執行的函式
  char              *some_argument;//thread 所要執行的函式中塞入的參數
  
  pthread_create( &a_thread, a_thread_attribute, (void *)&thread_function, 
               (void *) &some_argument);

* Pthread 的結束

pthread_exit()

* Pthread 的暫停(只影響單一thread，不影響整個process)

pthread_delay_np()

* Mutex

pthread_mutex_t mutex;
pthread_mutex_init(&mutex, pthread_mutexattr_default);//定義mutex
pthread_mutex_lock( &mutex );//鎖定共享資源
pthread_mutex_unlock( &mutex );//解所共享資源
pthread_mutex_destroy();//結束mutex

* Semaphores
[實做後再補上]
## thread pool
* 之前的實做著重在減少findname()的執行時間，現在我們可以利用thread pool的方式優化append()。
* 使用thread pool可以將我們之前多個thread的操作統整起來，現在我們要做的事情只要將工作丟入threadpool請它代為執行就好。在threadpool的操作下，thread的首要任務就是進入threadpool搶奪lock進行工作。
* 因為[threadpool-mbrossard](https://github.com/mbrossard/threadpool)本來就是以pthread寫的，所以在開始實做之前我把吳彥寬同學原本的pthread通通砍掉了

* 實際操做
* 利用[threadpool-mbrossard](https://github.com/mbrossard/threadpool)
* 引入的函式
* ```threadpool_t *pool=threadpool_create(THREAD_NUM,QUEUE SIZE,FLAG);```
定義thread的多寡與queue大小，flag則設為NULL即可。這裡很像我們在使用pthread也要create一樣
* ```threadpool_add(threadpool_t *pool, void (*function)(void *)```
將工作append()丟入threadpool中，此時thread就會開始搶工作了
*```int threadpool_destroy(threadpool_t *pool, int flags);```最後清理掉threadpool
* 實做結果
* 原始pthread與threadpool的差異(使用4個 thread)
* threadpool使用不同thread的差異

沒想到使用一條thread竟然是最快的...
# gnuplot補充
* plot語法
* datafile : 輸出的檔案
* <xcol>: 使用資料第幾列作圖(可以不用設定)
* <ycol>: 使用資料第幾行作圖(必設定)
* xticlable(<labelcol>)[等同xtic(<labelcol>)]：資料x座標標籤
* <plotstyle>：圖的種類(histogram長條圖)

plot ’datafile’ using <xcol>:<ycol>:xticlabels(<labelcol>) with <plotstyle>

* using語法

reset //清除先前設定
set ylabel 'time(sec)' //設定y軸資訊
set style fill solid
set title 'perfomance comparison with different num of threads' //設定圖片標題
set term png enhanced font 'Verdana,10'
set output 'runtime.png' //設定輸出檔名
plot [:][:0.02]'output.txt' using 2:xtic(1) with histogram title '1 thread', \
'' using ($0-0.2):($2+0.001):2 with labels title '', \
'' using 3:xtic(1) with histogram title '2 thread'  , \
'' using ($0-0.04):($3+0.0015):3 with labels title '', \
'' using 4:xtic(1) with histogram title '4 thread'   , \
'' using ($0+0.01):($4+0.0025):4 with labels title'',\
'' using 5:xtic(1) with histogram title '8 thread'  , \
'' using ($0+0.2):($5+0.0021):5 with labels title ' ', \
'' using 6:xtic(1) with histogram title '16 thread', \
'' using ($0+0.45):($6+0.003):6 with labels title ' ', \