2017q1 Homework4 (phonebook-concurrent)

contributed by <petermouse>

開發環境

OS: Ubuntu 16.04 LTS
Memory: 8 GB
CPU:
- Name:
  - Intel® Core™ i5-4200H CPU @ 2.80GHz
- Cache:
  - L1d Cache： 32K
  - L1i Cache： 32K
  - L2 Cache： 256K
  - L3 Cache： 3072K

執行程式

先執行原本的程式看看，由於 opt 版本多使用了 gprof ，避免時間影響先移除 -pg

append() 加快好多，快要接近 findName() 的時間了

分析程式碼

opt 比起 orig 做了幾個改動:

1. text align

將所有字以 16 bytes 對齊，固定的偏移量可以直接計算存取下一筆字的位置

2. `mmap()`

mmap(2)

在 process 的 virtual address space 建立新的映射

TLPI 一書提到 mmap() 可能帶來的優點

一般 read() 與 write() 要經過兩次的傳輸
file <–> kernel buffer cache <–> user space buffer (參考圖片)
不過使用 mmap() 省去 kernel buffer cache <–> user space buffer 的傳輸
等於 kernel 與 user 共享一個 buffer ，多個 process 也共用同個 buffer

3. Pthread

使用 Pthread 平行處理，預設為 4 個 thread
每個 thread 用 cyclic 的方式建立 local linked-list ，最後再串接起來

4. 其他

使用 Variadic Macros (C C++) 做出 debug 訊息

改進程式

建立 thread pool

觀察 mbrossard 的 thread pool 程式碼

參考 threadpool-mbrossard 的作法，先釐清一下內部的實作，不過覺得有點難懂

struct threadpool_t {
  pthread_mutex_t lock;
  pthread_cond_t notify;
  pthread_t *threads;
  threadpool_task_t *queue;
  int thread_count;
  int queue_size;
  int head;
  int tail;
  int count;
  int shutdown;
  int started;
};

這是 thread pool 的資料結構，裡面是用 queue 來存放 task，thread 再從 queue 拿取 task

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

建立一個 thread pool ，並指定 thread 數量以及 queue 大小
thread 會在此時就建立

/* in threadpool_create() function */
for(i = 0; i < thread_count; i++) {
    if(pthread_create(&(pool->threads[i]), NULL,
                      threadpool_thread, (void*)pool) != 0){
        /* error handling*/                  
    }
}

不過每個 thread 執行的函式是 threadpool_thread ，參數是 pool ，也就是 threadpool_thread 是取得 task 的接口，並從參數 thread pool 中的 queue 接收 task

接下來的 thread 搶奪 lock 的過程原網頁都有提到了

int threadpool_destroy(threadpool_t *pool, int flags);

用來結束 thread pool ，分為 graceful shutdown ( flags 不為 0) 代表正常結束，以及 immediate shutdown ( flags 為 0)，通知所有 thread 喚醒，並且離開 threadpool_thread 最後 join ，釋放空間

在 phonebook-concurrent 內使用

在還沒使用 thread pool 之前，我預期結果會比原本還要慢，因為就只是把原本的 4 個 task (即 thread_args[] ) 先放入 queue 中， 4 個 thread 再去從 queue 拿取，比起直接 4 個 thread 分配各 1 個 task 多了初始化 thread pool 以及強奪 lock 的成本

實際上是稍微久了一些，但不會差距太多

接著我試著把 task 切得更細，不過一直 core dumped，後來發現在給 thread 執行 threadpool_thread 內執行 task append() 時最後直接呼叫了 pthread_exit(NULL) ，竟然把 thread 直接結束了，剩餘的 task 並沒有執行到。

嘗試 TASK=100 ，thread 維持在 4，結果奇怪的事情發生了

append() 的時間變得更多了，我覺得算是正常的
不過 findName() 時間突然暴漲了，怎麼會這樣RRR?

由於是 cyclic 建立 linked list，所以 zyxel 也會隨著 task 的數量不同而放到 linked list 的不同位置，所以有機會可以秒殺找到
但是原始版本中是按照字典序建立 linked list ，找尋 zyxel 已經是接近最糟的情況，結果相差快兩倍了!

我也試著用 show_entry() 驗證正確性，這部份是沒問題的

我推測是頻繁的 cache miss但導致的狀況, 但尚未建立實驗

findName() 也用 thread pool

我把 findName() 也試著用thread pool 處理
同樣是 task=100 thread=4

可以降低一些時間，但是會有幾個問題

原本的 append() 會 return 找到的 entry ，但現在 thread pool 的形式沒辦法有效取得 entry
- 解決辦法是在原本的 task 中紀錄結果，但最後還要從所有 task 找尋，很沒效率
一個 task 找到沒有辦法停止其他 thread 的找尋
- 我覺得有辦法再調整，還要在思考如何適當的停止 thread pool

mutrace 測試

參考 B08: mergesort-conurrent

使用 mutrace 測試 mutex 帶來的影響 (THREAD=4 TASK=100)

以下省略每個 mutex 的詳細資料

mutrace: 0.2 sucessfully initialized for process phonebook_tp (pid 2981).
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.005685 sec
execution time of findName() : 0.007196 sec

mutrace: Showing statistics for process phonebook_tp (pid 2981).
mutrace: 3 mutexes used.

mutrace: Showing 3 most contended mutexes:

 Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]  Flags
       1      206      106       36        0.029        0.000        0.000 Mx.--.
       2      209      110       30        0.040        0.000        0.005 Mx.--.
       0       40       24       10        0.005        0.000        0.001 M-.--.
                                                                           ||||||
                                                                           /|||||
          Object:                                     M = Mutex, W = RWLock /||||
           State:                                 x = dead, ! = inconsistent /|||
             Use:                                 R = used in realtime thread /||
      Mutex Type:                 r = RECURSIVE, e = ERRRORCHECK, a = ADAPTIVE /|
  Mutex Protocol:                                      i = INHERIT, p = PROTECT /
     RWLock Kind: r = PREFER_READER, w = PREFER_WRITER, W = PREFER_WRITER_NONREC 

mutrace: Note that the flags column R is only valid in --track-rt mode!

mutrace: Total runtime is 68.093 ms.

mutrace: Results for SMP with 4 processors.

Locked: mutex 鎖了幾次
Changed: thread 轉換的次數
Cont.: thread 嘗試要求已鎖住的 mutex 的次數
tot.Time[ms]: mutex 鎖住的總時間
avg.Time[ms]: 平均鎖住 mutex 的時間 (?)
max.Time[ms]: 持有 mutex 的最大時間

觀察各個 mutex 的資訊

Mutex #1 (0x0x20da650) first referenced by:
	/usr/lib/mutrace/libmutrace.so(pthread_mutex_init+0xf2) [0x7f206ff724b2]
	./phonebook_tp(threadpool_create+0xf3) [0x4021ab]
	./phonebook_tp(main+0x2df) [0x4017ab]
	/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0) [0x7f206f9a9830]

輸入 $ addr2line -e phonebook_tp 0x4021ab 就得到 mutex 的位置

/home/petermouse/workspace/sysprog/phonebook-concurrent/threadpool.c:122

實作 remove

參考資料

threadpool-mbrossard
mutrace