# 2017q1 Homework4 (phonebook-concurrent) contributed by < `laochanlam` > ###### tags: `laochanlam` ## 開發環境 - Ubuntu 16.10 ( 64 bit ) ``` Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 61 Model name: Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz Stepping: 4 CPU MHz: 2400.878 CPU max MHz: 3000.0000 CPU min MHz: 500.0000 BogoMIPS: 4788.90 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 4096K NUMA node0 CPU(s): 0-3 ``` ## 相關連結 - [2017 年春季作業說明](https://hackmd.io/s/Bk-1zqIte#) - [2017q1 Homework4 (作業區)](https://hackmd.io/s/Hkxl2Zcpx) - [B07: phonebook-concurrent 作業要求](https://hackmd.io/s/rkOExTOoe#) - [課程進度與開放資源 Wiki](http://wiki.csie.ncku.edu.tw/sysprog/schedule) ## 開發紀錄 先研究一下 phonebook-concurrent 的整個架構。 先研究一些神奇的函式orz。 ```Ｃ int fd = open(ALIGN_FILE, O_RDONLY | O_NONBLOCK); ``` [這裡](http://c.biancheng.net/cpp/html/238.html)有關於 open() 各種參數的說明。 [這裡](http://c.biancheng.net/cpp/html/326.html)有關於 stat() 各種參數的說明。 ```Ｃ map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0); ``` [這裡](http://c.biancheng.net/cpp/html/138.html)有關於 mmap() 函式的一些說明。 看了良久,終於有點頭緒,先來記錄一下原來優化版本的執行時間: ![Imgur](http://i.imgur.com/Sipct8q.png) 所進行的優化有: 1. 對齊 2. 使用 mmap 防止 I/O Bound 3. 使用 Memory 4. POSIX Programming ### Refactoring 參考完[東霖學長的共筆](https://hackmd.io/s/ByiOeFYie#)後,嘗試用類似的方式實現 OOP 的程式架構。 然後要來實現一下 Thread Pool 了! ### Thread pool 在~~偷~~看完 [mbrossard](https://github.com/mbrossard/threadpool) 的 Thread pool 以及 [xdennisx 的 Github](https://github.com/xdennisx/phonebook-concurrent) 後,開始實作: ![Imgur](http://i.imgur.com/1XtF0XT.png) 似乎得到了跟我預期不太同的結果...該來驗證一下程式碼... ### Remove 隨後實作了 link-listed remove, 並用 ```assert(removeName(input, e))``` 確定正確性，若有 Remove 失敗則回傳 NULL。 ## 補充知識 - [x] Concurrency & Parallel - [x] CPU bound & I/O bound - [ ] Lock-Free - [x] POSIX Thread --- ## Concurrency & Parallel ### Concurrency (並行) ![](https://i.imgur.com/rweOyiD.png) Concurrency 是指一種"程式架構",把需要被執行的程式拆分成很多不同的小工作進行。 此處強調　**拆分**　。 實用場景: - 單核心 CPU ( 多個任務運行在同一 CPU 上) --- ### Parallel (平行) <img src="https://i.imgur.com/Oom3wM5.png" width="700" height="140" /> <br> >話說我現在才知道 Markdown 可以寫 HTML lol >[name=laochanlam][color=blue] Parallel 是指可使程式分拆成幾個小工作同時執行,可用多條 Thread 等實作方法執行。 此處強調　**平行**　。 :::info **Concurrency 可能會用到 parallelism， 但不一定要用 parallelism 才能實現 concurrency。** ::: #### 實用場景: - 多核心 CPU ( 多個任務運行在多個 CPU 上) #### 參考及引用資料 [Toward Concurrency](https://hackmd.io/s/Skh_AaVix#) --- ## CPU bound & I/O bound ### CPU bound CPU bound 是指大部分的狀況都是 CPU 在進行運算,相比下 CPU loading 較高, I/O 讀寫所佔的時間很短,所以說效能被 ＣＰＵ "bound" 住了。 ### I/O bound I/O bound 指 CPU 的 loading 較低,大部份時間都在執行 I/O的讀寫,效能被 I/O "bound" 住。 :::info 資料壓縮/解壓縮主要是增加 CPU 的 Loading ,平衡兩者。 ::: #### 參考及引用資料 [CPU bound? I/O bound?](http://delphi.ktop.com.tw/board.php?cid=30&fid=66&tid=90309) --- ## Lock-Free ![](https://i.imgur.com/XAbt1fh.png) 簡單來說,就是每個 thread 的執行之間不會相影響 ( block )。 #### 參考及引用資料 [Toward Concurrency](https://hackmd.io/s/Skh_AaVix#) --- ## POSIX Thread 先來理解一下[Toward Concurrency](https://hackmd.io/s/Skh_AaVix#)中所包含的範例 Code。 ```C #include <pthread.h> #include <stdio.h> #include <stdlib.h> #define NUM_THREADS 3 #define TCOUNT 10 #define COUNT_LIMIT 12 int count = 0; int thread_ids[3] = {0,1,2}; pthread_mutex_t count_mutex; pthread_cond_t count_threshold_cv; void *inc_count(void *t) { long my_id = (long)t; for (int i = 0; i < TCOUNT; i++) { pthread_mutex_lock(&count_mutex); count++; // Check the value of count and signal waiting thread when condition is // reached. Note that this occurs while mutex is locked. if (count == COUNT_LIMIT) { pthread_cond_signal(&count_threshold_cv); printf("inc_count(): thread %ld, count = %d Threshold reached.\n", my_id, count); } printf("inc_count(): thread %ld, count = %d, unlocking mutex\n", my_id, count); pthread_mutex_unlock(&count_mutex); /* Do some "work" so threads can alternate on mutex lock */ sleep(1); } pthread_exit(NULL); } void *watch_count(void *t) { long my_id = (long) t; printf("Starting watch_count(): thread %ld\n", my_id); /* Lock mutex and wait for signal. Note that the pthread_cond_wait routine will automatically and atomically unlock mutex while it waits. Also, note that if COUNT_LIMIT is reached before this routine is run by the waiting thread, the loop will be skipped to prevent pthread_cond_wait from never returning. */ pthread_mutex_lock(&count_mutex); while (count < COUNT_LIMIT) { pthread_cond_wait(&count_threshold_cv, &count_mutex); printf("watch_count(): thread %ld Condition signal received.\n", my_id); count += 125; printf("watch_count(): thread %ld count now = %d.\n", my_id, count); } pthread_mutex_unlock(&count_mutex); pthread_exit(NULL); } int main (int argc, char *argv[]) { int i, rc; long t1 = 1, t2 = 2, t3 = 3; pthread_t threads[3]; pthread_attr_t attr; /* Initialize mutex and condition variable objects */ pthread_mutex_init(&count_mutex, NULL); pthread_cond_init (&count_threshold_cv, NULL); /* For portability, explicitly create threads in a joinable state */ pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); pthread_create(&threads[0], &attr, watch_count, (void *)t1); pthread_create(&threads[1], &attr, inc_count, (void *)t2); pthread_create(&threads[2], &attr, inc_count, (void *)t3); /* Wait for all threads to complete */ for (i = 0; i < NUM_THREADS; i++) pthread_join(threads[i], NULL); printf ("Main(): Waited on %d threads. Done.\n", NUM_THREADS); /* Clean up and exit */ pthread_attr_destroy(&attr); pthread_mutex_destroy(&count_mutex); pthread_cond_destroy(&count_threshold_cv); pthread_exit(NULL); } ``` --- #### pthread_cond_wait(&count_threshold_cv, &count_mutex); #### pthread_cond_signal(&count_threshold_cv); wait 用於阻塞目前的 Thread , 等待另外一個 Thread 的 signal 的到來 (mutex 會在 wait 期間被 unlock , signal 到來後又 lock 回去 )。 例子: A Thread: ```C pthread_mutex_lock(&mut); while (x <= y) { pthread_cond_wait(&cond, &mut); } /* operate on x and y */ pthread_mutex_unlock(&mut); ``` B Thread: ```C pthread_mutex_lock(&mut); /* modify x and y */ if (x > y) pthread_cond_broadcast(&cond); pthread_mutex_unlock(&mut); ``` --- #### pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); 函式原型為 ```C pthread_attr_setdetachstate（pthread_attr_t *attr, int detachstate） ``` ```datachstate``` 的參數可選擇為 ##### ```PTHREAD_CREATE_DETACHED```（分離執行緒） 會在執行緒完成任務後直接釋放系統資源,不需等待```pthread_join()```。 ##### 及 ```PTHREAD _CREATE_JOINABLE```（非分離執行緒） 反之,需要等待```pthread_join()```返回才會釋放系統資源。 --- #### pthread_create(&threads[0], &attr, watch_count, (void *)t1); 函式原型為 ```C int pthread_create(pthread_t *tid , const pthread_attr_t *attr , void *(*function)(void *) , void *argument) ``` 產生一個Thread及執行Function，附有4個參數。 :::info 參數1: pthread_t *tid為pthread的指標，在使用Thread之前必須要先宣告一個pthread_t的變數。 參數2: const pthread_attr_t *attr 為該 Thread 的屬性，預設是NULL。 參數3: void *(*function)(void *) 為 Function pointer ，這邊要放入需要被執行的Function。 參數4: void *argument 為 Ｆunction pointer 所要帶的參數。 回傳值: 如果執行成功則回傳0，如果執行失敗則回傳錯誤代碼。 ::: --- #### void pthread_exit (void *value_ptr) 這個 Function 的作用是用來關閉一個 Thread ，附帶有1個參數。 :::info 參數1: void *value_ptr 用來設定執行成功時該 Thread 會回傳的值，這個值可由 pthread_join() 這個 Function 來取得。 回傳值: 不會回傳任何值。 ::: --- #### int pthread_cancel (pthread_t thread) 關閉一個指定的 Thread ，附帶有一個參數。 :::info 參數1: pthread_t thread 為要關閉的 Thread 。 回傳值: 如果執行成功則回傳0，如果執行失敗則回傳錯誤代碼。 ::: --- #### int pthread_join (pthread_t thread, void **value_ptr) 等待目標 Thread 執行完畢後,目前執行 pthread_join 的 Thread (呼叫者) 才會繼續執行。 :::info 參數1: pthread_t thread為要等待的目標Thread。 參數2: void \**value_ptr 用來取得目標 Thread 的回傳值。 回傳值: 如果執行成功則回傳0，如果執行失敗則回傳錯誤代碼。 ::: --- #### 參考及引用資料 [Toward Concurrency](https://hackmd.io/s/Skh_AaVix#) [线程的分离状态 pthread_attr_setdetachstate 函数使用 ](http://blog.csdn.net/sjin_1314/article/details/8023575) [Pthread 程式撰寫](http://blog.xuite.net/nikoung/wretch/154071878-Pthread+%E7%A8%8B%E5%BC%8F%E6%92%B0%E5%AF%AB) [pthread_cond_signal和pthread_cond_wait简介](http://www.eefocus.com/andrew_dj/blog/12-08/282740_85e58.html) ---
Last changed by  
 
Chan Lam Lao
771
Published on HackMD