2017q1 Homework4 (phonebook-concurrent)
===

contributed by <`vtim9907`>

# 開發環境
- OS : Ubuntu 16.04.2 LTS
- Kernel Version : 4.8.0-36-generic
- Memory : 32 GB
- CPU : Intel® Core™ i5-6600 Processor
- cache :
- L1i cache : 4*32 KB
- L1d cache : 4*32 KB
- L2 cache : 4*256 KB
- L3 cache : 6144 KB
- L1 cache imformation ( sudo dmidecode -t cache ) :

Handle 0x001E, DMI type 7, 19 bytes
Cache Information
	Socket Designation: L1 Cache
	Configuration: Enabled, Not Socketed, Level 1
	Operational Mode: Write Back
	Location: Internal
	Installed Size: 256 kB
	Maximum Size: 256 kB
	Supported SRAM Types:
		Synchronous
	Installed SRAM Type: Synchronous
	Speed: Unknown
	Error Correction Type: Parity
	System Type: Unified
	Associativity: 8-way Set-associative

# 教材研讀

觀賞 [課程影片](https://www.youtube.com/watch?v=3mkug2ygdIs) 和研讀 [Toward Concurrency](https://hackmd.io/s/Skh_AaVix)

- 其中我覺得最有趣的是 [lock-free](http://www.cnblogs.com/gaochundong/p/lock_free_programming.html)
- lock-free programming 簡單示意圖

其中上面 lock-free 連結的文章也提到，一般並不會期望整個程式都應用 lock-free 技術，而是應該仔細洞察眼前的案例，針對案例的特性去找出可以應用的地方下手改進。
# 原版程式碼分析

## 前置

### 瓶頸
pthread_join : 因為每個 thread 的執行時間不一，有的快有的慢，所以整體時間還是以最慢的為準，快的還是要等慢的。

### 問題

根據作業提供的分析，最後結論在於不知道為什麼 thread 的數量在超過 4 之後，執行時間就會增長不少。

### 研究前腦補想法 & 問題

1. 我的 cpu 規格上寫著 " 執行緒數量： 4 "，這跟 kernel thread 有什麼關係？
2. 如果硬體本身資源就小於工作量的需求，那麼 thread 開到超過適量個數之後，頂多也只是多個小工作輪流使用同一個 processor，對於加快整體工作的速度來說並沒有比較快。（如果是這樣的情況，用超多 thread 主要的目的變成是希望多個小工作同時運作，而不是加速整體大工作的速度。
3. 到底如何確定很多個 thread 在跑的時候，是真的同時運作，還是只是輪流使用同個 processor？ 如果只是輪流使用同個 processor，那麼對加速工作執行速度真的有幫助嘛？ 還是說變成只是讓工作 " 近似 " 同時運作，但整體時間最快的時間很難再壓縮。
4. 因為前面多個問題沒想清楚，我有點難想像做了 thread pool 之後會有多少效能提昇，或是說 thread pool 在這裡的功能就是控管 thread 運作的數量，避免使用過多的 thread 導致效能反而降低，但如果是這樣，以目前比較偏向寫死靜態的 phonebook 來說，作用應該不會太好，但是如果 phonebook 是動態的，有時可能需要新增大量資料，或是刪除大量資料，有時又停滯沒事，那麼 thread pool 的用處可能會比較顯著。

> 感覺作業系統要重念了...

- 在 [Operating Systems](https://books.google.com.tw/books?id=MBIQS9nayYYC&pg=SL16-PA20&lpg=SL16-PA20&dq=processor+less+than+kernel+thread&source=bl&ots=b7BhUTUlZL&sig=X8nePnyuODbfpvaOA4StGp4W6Fs&hl=zh-TW&sa=X&ved=0ahUKEwiFue_P7vPSAhVK2LwKHRkPAqYQ6AEIIzAB#v=onepage&q=processor%20less%20than%20kernel%20thread&f=false) 裡看到了 kernel thread 和 processor 數量的關係：

- a. 當 processors 數量大於 kernel threads 數量時，會造成一些未被 threads 對應到的 processors idle.
- b. 當 processors 數量等於 kernel threads 數量時，所有的 kernel thread 都會對應到一個 processor ，但當 kernel thread 被 block 時，也會造成對應的 processor 閒置。
- c. 當 processors 數量小於 kernel threads 數量時，每個 processor 都會對應到一個 kernel thread ，當 kernel thread 被 block 時，此 thread 會被 swap out ，並將其他已經準備好執行的 thread 對應到此 processor ，藉此提高 multiprocessor system 的效能。

這樣來看就稍微清楚一點，而 kernel thread 也是有 one-to-one, one-to-many, many-to-many 這些關係，一個 kernel thread 也是掌控一個或是多個 user thread ，若是多個，則多個 user thread 輪流執行。

- 這麼多問題，查資料查到暈頭了還是沒前進多少，還是先實驗看看吧...

## 案例實驗分析

由於實在無法確定 thread 運作情況，以本案例來說，我也不確定 thread 更多的時候，效能到底移動多少，因為數據都是單筆資料，在每次執行都會浮動的數字來說，還是用大數來看比較好判斷！

### 改變 THREAD_NUM

- 改變 THREAD_NUM 的值，每個做 4200 次，然後看結果

- THREAD_NUM = 4

- THREAD_NUM = 8

append 的時間整體來看，其實與 THREAD_NUM = 4 的時候差不多，但 findName 的時間卻提昇了兩倍！？

- THREAD_NUM = 16

這次 append 的時間就提昇的比較明顯了，大約比上面兩種效能都差了 1/3 左右， 但是 findName 的時間卻又掉回來 0.002s 左右？ 我原本預期是當 thread 開到超過某個閥值之後，開越多效能就越慢，但是 findName 變慢又變快的狀況是怎樣還要思考一下...

### 嘗試看 System Monitor ，觀察 CPU 運作

- 在上面的過程中，我另外看了 System Monitor ，觀察 CPU 運作情形，不過其實每次跑的情況都差不多，每顆 CPU 資源消耗的差不多，但 THREAD_NUM = 8 的時後，某次跑出現了滿特殊的情況：

- 第一次跑


- 第二次跑


- 可以看到第一次跑的時候運算幾乎都集中在 CPU3 上，其他 CPU 相較之下就比較不活躍。
- 但是第二次跑得時候，工作卻幾乎平分給四顆 CPU 上，可以看到四顆 CPU 的活躍程度差不多。

> 難道是 kernel thread 有可能都對應到同一顆 CPU!?

- 必須確定 pthread_create 出來的 thread 是什麼東西！？

- [Native POSIX Thread Library](https://en.wikipedia.org/wiki/Native_POSIX_Thread_Library)

- 這是一種在 Linux 環境底下實做 POSIX Threads 的實做方式。
- 根據其內容敘述

        NPTL is a so-called 1×1 threads library, in that threads created 
        by the user (via the pthread_create() library function) are in 
        1-1 correspondence with schedulable entities in the kernel 
        (tasks, in the Linux case). This is the simplest possible 
        threading implementation.

- 從上面看來，就是 pthread_create 出來的 thread 就是 1-to-1 model 的形式。

> 這樣來看，上面詭異的例子有可能真的是因為 kernel thread 都對應到同一顆 cpu 嘛！？ 但是應該是全部的 CPU 去 swap in/out 全部的 kernel thread 吧？ 那怎麼會出現只有一顆 CPU 特別忙碌的狀況？ 目前還不確定原因，實驗作法錯誤有可能，但是因為什麼都沒改跑了好幾次，就只有特定那次發生這樣的狀況，雖然說跑出來的數據正常，但是跑得過程為何怪異就要再想想...