2016q3 Homework2 (phonebook-concurrent)

contributed by <beieve7028>

預期目標

學習第二週提及的 concurrency 程式設計
學習 POSIX Thread
學習效能分析工具
code refactoring 練習
探索 clz 的應用

相關資料閱讀及重點整理

Functional Programming

函数式程序设计为什么至关重要 - BYVoid當中提到函數程式設計的優點：

一個函数除了計算本身的值以外，不會產生任何作用。这一特性減少了Bug的主要来源
同时也使執行顺序不再重要——没有副作用而能夠改變一个表達式的值，故可以在任何時間被求值

這對於平行程式設計來說就很有誘惑，可以不用顧慮race condition的問題，在適合的任何地方壓榨硬體的效能。

從學習的教材看到有使用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 ***
從這裡看到解法於是安裝了:
zlib-1.2.8
然後又一個新問題:
configure: error: *** Could not find libmount

到這邊還無法順利解決believe7028

Concurrency (並行) vs. Parallelism (平行)

這隻地鼠要努力的把書燒掉，過去直覺上會採用平行計算，但是現在可以使用並行的技巧:

可以看到上面每個地鼠各有分工，有的是拿書、有的運書、有的是中繼站、也有最後負責燒書的，這種分工跟平行計算不同，平行計算是同時各個獨立的計算各別完成，而這種並行的計算則是需要溝通，像go language有所謂的通道。在作業系統當中也可以見到類似的概念，譬如IO裝置與儲存裝置與CPU之間的配合，就是一種分工，當程式計算完成後，資料可能會從暫存器->cache->main memory->disk一層一層的傳遞。這種計算的方式避免的平行計算的一些問題，例如race condition。再從上面這圖來說，他也可以平行（分成上下）。

我在使用Visual Studio Code以debug 模式追蹤時，看到使用了mmap，從說明可以了解這是一種將檔案物件直接對應到虛擬記憶體的技巧，具有能以指標操作且存取不因寫入緩衝存在而提昇速度，以下是函式界面的說明：

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 中。

而由此可以知道

int munmap(void *start, size_t length)

函數說明：munmap()用來取消參數start 所指的映射記憶體起始地址，參數length 則是欲取消的記憶體大小。當行程結束或利用exec 相關函數來執行其他程式時，映射記憶體會自動解除，但關閉對應的文件描述詞時不會解除映射。

pthread_setconcurrency

而對於並行的使用pthread_setconcurrency，參考了這篇的說明

#include <pthread.h>
int pthread_setconcurrency(void); //返回值:當前的並行度
int pthread_setconcurrency(int level); //返回值:若成功則返回0,否則返回錯誤編號

裡面有特別指出設定的值不保證會執行對應的並行度。

學習 POSIX Thread

Thread Pool

這裡則說明了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，而這篇更生動的形容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

這裡則以簡單的程式碼說明thread pool的如何以Lock-Free實作，主要的原理是以具有 atomic 特性的計算操作來達成。








bool CAS(T* addr, T exp, T val)  
{  
    if (*addr == exp) {  
        *addr = val;  
        return true;  
    }  
    return false;  
}

Refactoring

這同學當中有特別去比對資料而發現bug的存在，因此先以他的成果進行修改。
再來則以這他所整理重構的要點對程式碼修改