2016q3 Homework2 (phonebook-concurrent)

contribute by <andy19950>

Refactor

首先先詳讀程式碼，可以發現幾個問題

1. main.c 裡面使用太多 #ifndef #if defined
   • 其實很多都可以放一起使用，把它們合併起來吧
2. 變數名稱看不懂
   • 許多變數名稱都宣告成 ptr i j 第一次看根本看不懂，把它改成有意義的名字吧！
3. 程式碼指標使用有誤
   • 在 main.c 後面把 linked-list 接起來時少接了每個 linked-list 的 head node
   • findName() 裡面一開始也少找了第一個 node ，這些錯誤會讓程式搜尋其他名字的時候壞掉。
4. 額外的宣告
   • 像是 pdtail 之類的多餘的宣告或定義把它拿掉

---

MMAP

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

• addr : 要map到的記憶體位置，傳NULL系統會自行尋找一塊空間 mapping 完之後回傳。

• length:　要 mapping 的長度，它會從 fd + offset 的位置開始 mapping 檔案。

• prot: 不能跟 open mode 有衝突

  • PROT_EXEC Pages may be executed.
  • PROT_READ Pages may be read.
  • PROT_WRITE Pages may be written.
  • PROT_NONE Pages may not be accessed.

• flags: 選擇 map file 能不能被其他程式看到

• fd: 用系統函式 open 打開的檔案位置，open mode 可以選擇檔案的讀寫屬性，不能跟 prot 有衝突。

• offset: 從檔案的哪裡開始 mapping，offset 必須是 page size 的倍數，可以用 sysconf(_SC_PAGE_SIZE) 取得。

mmap 是 UNIX 系統呼叫 jserv

• 一般來說把資料從硬碟搬進記憶體時，會建立 page table 來紀錄 virtual address 與 physical address 的相對關係，在程式執行時用動態位置轉換來取得實體位置裡面的資料。
• mmap 就有點像是這樣，只是它不把資料搬進記憶體，只將實體位置跟虛擬位置的關係記錄下來，如此可以省去許多 I/O 的時間。

在這份程式碼中，缺乏驗證資料正確性的機制，請嘗試逐一輸出 last name 到一份檔案，再跟 dictionary/words.txt 比對。 jserv

---

資料正確性檢查

• 因為我把 append 稍做修改，改成比較像是 insert，所以 linked-list 的順序是完全亂掉的。
• 因此我在 main 的最下面把輸入資料再重新跑一遍，每個名字都去 findName() 確認有沒有在 linked-list 內。
• 時間複雜度是 O(n²)，因為資料量太龐大了所以驗證一次非常花時間。

while(fgets(line, sizeof(line), fp)) {
    e = pHead;
    printf("%s", line);
    if(strcmp(findName(line, e)->lastName, line) != 0) {
        printf("ERROR : Name %s is not in linked-list!!\n", line);
    }
}

• 然後我執行 ./phonebook-concurrent > output.txt 搜尋 ERROR 之後找不到就代表 linked-list 內部資料完全正確

E486: 找不到 ERROR

• 若要加速驗證時間的話可以寫一個 linked-list sort function 把它排序成跟原來檔案的順序一樣，這樣時間複雜度是 O(nlogn)。

---

findName() 的缺點

- 資料都在硬碟裡面，所以不允許修改它的內容，我本來想讓在 findName 找到的時候直接去把 \n 轉成 \0 ，但每次都會 segmentation fault。

mmap 可在記憶體映射 (map) 給定檔案時，指定存取模式，請詳細閱讀 man page: mmap(2) jserv
謝謝老師，正在想有沒有辦法解決呢！！ andy19950
下面有修改過 findName 的版本所以刪掉的地方就當做沒看到吧 andy19950

• 後來我發現原本的程式碼是把要找的名字跟 map 裡的資料做比較，找到後就 malloc 一塊記憶體位置把要找的名字寫入。
• 但是如果這支程式長時間的執行，當所有名字都在記憶體內部之後，這隻程式依然會傻傻的一直 malloc 空間給它，所以如果多執行幾次 findName 可能會發生 segmentation fault 。

修改 open mode 及 mmap prot

• 我把兩邊的參數都修改成 read write 模式
• 然後我就可以對檔案做修改了！！

int fd = open(ALIGN_FILE, O_RDWR | O_NONBLOCK);
char *map = mmap(NULL, fs, PROT_READ | PROT_WRITE,
                 MAP_SHARED, fd, 0);

於是我可以把 findName 改成可直接把 \n -> \0

• 因為我有修改過變數名稱，看不懂的話可以先去 github 看一下 .h 檔

while (current != NULL) {
    if (strncasecmp(lastName, current->lastName, len) == 0) {
        current->lastName[len] = '\0';
        current->dtl = (detail *) malloc( sizeof(detail));
        return current;
    }
    current = current->pNext;
}

---

使用 thread pool – source code

threadpool_t *threadpool_create(int thread_count,
                                int queue_size,
                                int flags);

int threadpool_add(threadpool_t *pool,
                   void (*routine)(void *),
                   void *arg, int flags);
		
int threadpool_destroy(threadpool_t *pool, int flags);

1. threadpool_create：傳入 thread 的數量，queue 的大小，回傳 threadpool 型態是 threadpool_t
2. threadpool_add：傳入 threadpool，要執行的function位置，要傳入的參數
3. threadpool_destroy：傳入 threadpool，會把 threadpool 的空間 free 掉

flags 只有 destroy 會用到， threadpool_graceful = 1，其他的傳 NULL 就可以了。

• 我個人覺得用起來跟 pthread 很像
• 程式碼改起來也很像，就是把
  • pthread_create -> threadpool_create + threadpool_add
  • pthread_join -> threadpool_destroy

threadpool_t *pool = threadpool_create(THREAD_NUM, 512, NULL);
for (int i = 0; i < THREAD_NUM; i++) {
    threadpool_add(pool, &append, app[i], NULL);
}
threadpool_destroy(pool, 1);

執行結果

• 效果好像不大， THREAD_NUM = 4 是最佳了

我們只對 append() 有興趣，可以單獨製圖，然後調整 Y 軸刻度，得以比較不同 thread 數量對效能的影響。讓視覺效果更顯著 jserv

今天把 THREAD_NUM = 1 ~ 64 跑了一次，竟然是一條 thread 跑最快！！

---

Reference

• mmap