2016q3 Homework2 (phonebook-concurrent) === contributed by <`beieve7028`> --- 預期目標 * 學習第二週提及的 [concurrency](/s/H10MXXoT) 程式設計 * 學習 POSIX Thread * 學習效能分析工具 * code refactoring 練習 * 探索 clz 的應用 --- # 相關資料閱讀及重點整理 ## Functional Programming [函数式程序设计为什么至关重要 - BYVoid](https://www.byvoid.com/blog/why-functional-programming/)當中提到函數程式設計的優點： - 一個函数除了計算本身的值以外，不會產生任何作用。这一特性減少了Bug的主要来源 - 同时也使執行顺序不再重要——没有副作用而能夠改變一个表達式的值，故可以在任何時間被求值 這對於平行程式設計來說就很有誘惑，可以不用顧慮race condition的問題，在適合的任何地方壓榨硬體的效能。 從[學習的教材](https://lucabolognese.wordpress.com/2013/01/04/functional-programming-in-c/)看到有使用glib，才發覺這個函式庫有點強大，趕緊玩看看。 ``` wget http://ftp.gnome.org/pub/gnome/sources/glib/2.50/glib-2.50.0.tar.xz tar -vxf glib-2.50.0.tar.xz cd glib-2.50.0/ ./configure ``` 結果出現一個 error: `configure: error: *** Working zlib library and headers not found ***` 從[這裡](http://www.cnblogs.com/pcat/p/5520317.html)看到解法於是安裝了: `zlib-1.2.8` 然後又一個新問題: `configure: error: *** Could not find libmount` > 到這邊還無法順利解決[name=believe7028] ## Concurrency (並行) vs. Parallelism (平行) ![](https://hackpad-attachments.s3.amazonaws.com/embedded2016.hackpad.com_K6DJ0ZtiecH_p.537916_1460613009716_task.jpg) 這隻地鼠要努力的把書燒掉，過去直覺上會採用平行計算，但是現在可以使用並行的技巧: ![](https://hackpad-attachments.s3.amazonaws.com/embedded2016.hackpad.com_K6DJ0ZtiecH_p.537916_1460613058438_concurrency.jpg) 可以看到上面每個地鼠各有分工，有的是拿書、有的運書、有的是中繼站、也有最後負責燒書的，這種分工跟平行計算不同，平行計算是同時各個獨立的計算各別完成，而這種並行的計算則是需要溝通，像go language有所謂的通道。在作業系統當中也可以見到類似的概念，譬如IO裝置與儲存裝置與CPU之間的配合，就是一種分工，當程式計算完成後，資料可能會從暫存器->cache->main memory->disk一層一層的傳遞。這種計算的方式避免的平行計算的一些問題，例如race condition。再從上面這圖來說，他也可以平行（分成上下）。 我在使用Visual Studio Code以debug 模式追蹤時，看到使用了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)可以了解這是一種將檔案物件直接對應到虛擬記憶體的技巧，具有能以指標操作且存取不因寫入緩衝存在而提昇速度，以下是函式界面的說明： ```clike 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)。 返回值： 若映射成功則返回映射區的核心起始位址，否則返回MAP_FAILED(-1)，錯誤原因存於errno 中。 ``` 而由[此](http://c.biancheng.net/cpp/html/139.html)可以知道 ```clike int munmap(void *start, size_t length) ``` 函數說明：munmap()用來取消參數start 所指的映射記憶體起始地址，參數length 則是欲取消的記憶體大小。當行程結束或利用exec 相關函數來執行其他程式時，映射記憶體會自動解除，但關閉對應的文件描述詞時不會解除映射。 ## pthread_setconcurrency 而對於並行的使用`pthread_setconcurrency`，參考了[這篇的說明](http://www.bianceng.cn/OS/unix/201408/44151.htm) ``` #include <pthread.h> int pthread_setconcurrency(void); //返回值:當前的並行度 int pthread_setconcurrency(int level); //返回值:若成功則返回0,否則返回錯誤編號 ``` 裡面有特別指出設定的值不保證會執行對應的並行度。 --- 學習 POSIX Thread === ## Thread Pool [這裡](http://blog.darkthread.net/post-2010-01-02-multicore-1.aspx)則說明了thread pool要注意的缺點。 ``` Multi-Threading的機制並非免費午餐，在運作時也要相對付出代價。 ThreadPool的基本原理是將要執行的工作放進一個Queue裡，然後啟動多條Thread，每條Thread會去檢查Queue裡還有沒有工作要做，若有就取出來。 由於要管控每件工作只交給其中一個Thread去處理，所以得動用lock機制； 也就是同一時間只能開放一條Thread去檢查Queue並取出工作，可以想像成全部的Thread排成一列輪流存取。 另外，在程式裡透過JOB_COUNT掌握工作何時全部做完，在遞減JOB_COUNT也要等同要啟動lock機制(Interlocked.Decrement)，任何時間下只允許一個Thread去修改它的值。 另外還有一點，CPU在切換不同Thread執行時，也要保留與切換Thread相關的暫存器、快取、堆疊等環境，稱作Context Switch，也會損耗一些運算資源。 ``` 不是什麼情況都適合使用thread，而[這篇](http://swind.code-life.info/posts/c-thread-pool.html)更生動的形容thread pool的機制: ``` Thread 第一件要做的事情就是去搶奪 pool 的 lock，當搶到 lock 的 Thread 發現沒有工作可以做的時候， 就會執行 pthread_cond_wait 來等待通知。 這時候 pool->lock 會被 Unlock，因此這時候其他 Thread 也可以進來這個區域。 所以在完全沒有工作的情況下，所有的 Thread 都會在這邊 Waiting。 當 Thread 被透過 pthread_cond_signal 喚醒的時候，該 Thread 就會重新取得 pool->lock。 這時他就可以安心的取出 queue 中的 task，等待取出完畢之後，再 unlock 讓其他被喚醒的 Thread 也可以去取得 Task。 ``` ## Lock-Free Thread Pool [這裡](http://blog.monkeypotion.net/gameprog/note/multicore-multithread-and-multifun)則以簡單的程式碼說明thread pool的如何以Lock-Free實作，主要的原理是以具有 atomic 特性的計算操作來達成。 ```clike= bool CAS(T* addr, T exp, T val) { if (*addr == exp) { *addr = val; return true; } return false; } ``` --- Refactoring === 這[同學](https://hackmd.io/s/rk5IVI0a)當中有特別去比對資料而發現bug的存在，因此先以他的成果進行修改。 再來則以這他所整理重構的要點對程式碼修改 --- 探索 clz 的應用 ===