2017q1 Homework4 (phonebook-concurrent)

constributed by <henry0929016816>

phonebook thread 版

mmap
- 功能：
  Linux 提供了記憶體映射函數 mmap ，它把文件內容映射到一段記憶體上(準確說是虛擬記憶體上)，通過對這段記憶體的讀取和修改，實現對文件的讀取和修改。映射成功的化，會回傳一個指向映射區域的 pointer ，然而失敗的話則會回傳 MAP_FAILED ( (void *) -1)
- 好處：
  由於使用 fgets 讀取字典是 block I/O 所以 thread 開的在多，也會因為 block 的關係而無法做到平行化的讀取字典資料。而使用 mmap 可以得到一個對應檔案的記憶體，這個記憶體可以是 thread 間的共享記憶體，讀取時不會產生 block 所以能平行化。
- 函式解說：
  - 函式樣板：
    void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset)
  - addr：
    如果 addr 是 NULL ，那 kernel 會選擇適當的 address 建立映射（mapping)，如果不是 NULL ，kernel 會將填入的 addr 當作是暗示要再哪裡建立映射，而 kernel 會選擇在 addr 之上合適的位子建立映射。
  - length：
    代表映射的大小。將文件的多大長度映射到記憶體。
  - prot：
    映射區域的保護方式。可以為以下幾種方式的組合：
    PROT_EXEC 映射區域可被執行
    PROT_READ 映射區域可被讀取
    PROT_WRITE 映射區域可被寫入
    PROT_NONE 映射區域不能存取
  - flags：
    影響映射區域的各種特性：
    MAP_PRIVATE ：不允許其他映射該文件的行程共享，對映射區域的寫入操作會產生一個映射的複製(copy-on-write)，對此區域所做的修改不會寫回原文件。
  - fd ：
    由 open 回傳的文件描述符，代表 mmap 要映射的文件
  - offset ：
    從文件映射開始處的偏移量，通常為 0，代表從文件最前方開始映射。 offset 必須是分頁大小的整數倍(在 32 位體系統結構上通常是 4K )。
text_align
- 功能：
  原本字典裡的字串長度是不固定的，所以如果使用 mmap 映射字典檔案，會因為每個字串長度的不固定，而無法確定下一個字串是從哪個記憶體位址開始存取，既然這樣那我們就重新修改原本字典的格式，將字串長度都固定就好了，不夠長的就補上 null character 使每個字串長度都固定，這樣 mmap 後也可以方便的找尋下一個字串開始位址。
- strncpy
  - 函式樣板：
    char *strncpy(char *dest, const char *src, size_t n)
  - 函式解說：
    strncpy 會將 src 字串 n 個長度複製到 dest 字串，如果 n 比 src 長，會再字串後面補上 null character('\0') 確保複製的長度有 n 個 byte，而我們利用這點就可以使得每個字串的長度固定都是 MAX_LAST_NAME_SIZE（16 byte)。
- createThread_arg
  - 函式樣板：
    thread_arg *createThread_arg(char *data_begin, char *data_end, int threadID, int numOfThread,entry *entryPool)
  - 功能說明：
    由於 thread 實作的 append 函式只接收一個參數，所以我們要將必要的資訊都封裝進 structure 裡， data_begin 紀錄要從 mmap 映射出的記憶體的哪個位址開始讀取資料，避免 4 thread 執行 append 函式時重複讀取資料而導致程式沒有加快運行， data_end 紀錄了記憶體位址界線再哪，以免讀取超過界線
效能分析：
- 執行時間：
  
  上圖可以看出原本 append 的時間為 0.080164 s，然而經過平行化處理，執行時間已經降為 0.004982 s 跟 findName 執行時間很接近。
- cache misses

397,275      cache-misses              #   31.523 % of all cache refs      ( +-  0.96% )
         1,260,273      cache-references                                              ( +-  1.41% )
       248,716,045      instructions              #    1.12  insn per cycle           ( +-  0.08% )
       222,848,294      cycles                                                        ( +-  0.82% )

       0.098804162 seconds time elapsed                                          ( +-  0.93% )

改善 cache-misses

觀點：
參考了 LanKuDot (李昆憶)的共筆，讓我注意到了 thread 版的 append（）函式還有修正的空間，原版的由於考量到不讓資料重複讀取，而使得每次讀取字串長度都要跨過 thread 數量的字串，然而這樣的作法卻不是個好方法，由於 cache 會傾向 load 進連續的記憶體，所以這樣不連續的記憶體操作，則會導致 cache misses 的增加。
改善方式：
將要讀取資料分成 4 個部份，而 thread 分別在這 4 個部份，做連續的讀取，期許能降低 cache misses
code：

參考資料

concurrency
記憶體映射函數 mmap 的使用方法
 mmap
LanKuDot (李昆憶)的共筆