# 2017q1 Homework4 (phonebook-concurrent)
contributed by < `laochanlam` >
###### tags: `laochanlam`
## 開發環境
- Ubuntu 16.10 ( 64 bit )
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 61
Model name: Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
Stepping: 4
CPU MHz: 2400.878
CPU max MHz: 3000.0000
CPU min MHz: 500.0000
BogoMIPS: 4788.90
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 4096K
NUMA node0 CPU(s): 0-3
```
## 相關連結
- [2017 年春季作業說明](https://hackmd.io/s/Bk-1zqIte#)
- [2017q1 Homework4 (作業區)](https://hackmd.io/s/Hkxl2Zcpx)
- [B07: phonebook-concurrent 作業要求](https://hackmd.io/s/rkOExTOoe#)
- [課程進度與開放資源 Wiki](http://wiki.csie.ncku.edu.tw/sysprog/schedule)
## 開發紀錄
先研究一下 phonebook-concurrent 的整個架構。
先研究一些神奇的函式orz。
```Ｃ
int fd = open(ALIGN_FILE, O_RDONLY | O_NONBLOCK);
```
[這裡](http://c.biancheng.net/cpp/html/238.html)有關於 open() 各種參數的說明。
[這裡](http://c.biancheng.net/cpp/html/326.html)有關於 stat() 各種參數的說明。
```Ｃ
map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
```
[這裡](http://c.biancheng.net/cpp/html/138.html)有關於 mmap() 函式的一些說明。
看了良久,終於有點頭緒,先來記錄一下原來優化版本的執行時間:
所進行的優化有:
1. 對齊
2. 使用 mmap 防止 I/O Bound
3. 使用 Memory
4. POSIX Programming
### Refactoring
參考完[東霖學長的共筆](https://hackmd.io/s/ByiOeFYie#)後,嘗試用類似的方式實現 OOP 的程式架構。
然後要來實現一下 Thread Pool 了!
### Thread pool
在~~偷~~看完 [mbrossard](https://github.com/mbrossard/threadpool) 的 Thread pool 以及 [xdennisx 的 Github](https://github.com/xdennisx/phonebook-concurrent) 後,開始實作:
似乎得到了跟我預期不太同的結果...該來驗證一下程式碼...
### Remove
隨後實作了 link-listed remove, 並用 ```assert(removeName(input, e))``` 確定正確性，若有 Remove 失敗則回傳 NULL。
## 補充知識
- [x] Concurrency & Parallel
- [x] CPU bound & I/O bound
- [ ] Lock-Free
- [x] POSIX Thread
---
## Concurrency & Parallel
### Concurrency (並行)
Concurrency 是指一種"程式架構",把需要被執行的程式拆分成很多不同的小工作進行。
此處強調 **拆分** 。
實用場景:
- 單核心 CPU ( 多個任務運行在同一 CPU 上)
---
### Parallel (平行)
<img src="https://i.imgur.com/Oom3wM5.png" width="700" height="140" />
<br>
>話說我現在才知道 Markdown 可以寫 HTML lol
>[name=laochanlam][color=blue]
Parallel 是指可使程式分拆成幾個小工作同時執行,可用多條 Thread 等實作方法執行。
此處強調 **平行** 。
:::info
**Concurrency 可能會用到 parallelism，
但不一定要用 parallelism 才能實現 concurrency。**
:::
#### 實用場景:
- 多核心 CPU ( 多個任務運行在多個 CPU 上)
#### 參考及引用資料
[Toward Concurrency](https://hackmd.io/s/Skh_AaVix#)
---
## CPU bound & I/O bound
### CPU bound
CPU bound 是指大部分的狀況都是 CPU 在進行運算,相比下 CPU loading 較高, I/O 讀寫所佔的時間很短,所以說效能被 ＣＰＵ "bound" 住了。
### I/O bound
I/O bound 指 CPU 的 loading 較低,大部份時間都在執行 I/O的讀寫,效能被 I/O "bound" 住。
:::info
資料壓縮/解壓縮主要是增加 CPU 的 Loading ,平衡兩者。
:::
#### 參考及引用資料
[CPU bound? I/O bound?](http://delphi.ktop.com.tw/board.php?cid=30&fid=66&tid=90309)
---
## Lock-Free
簡單來說,就是每個 thread 的執行之間不會相影響 ( block )。
#### 參考及引用資料
[Toward Concurrency](https://hackmd.io/s/Skh_AaVix#)
---
## POSIX Thread
先來理解一下[Toward Concurrency](https://hackmd.io/s/Skh_AaVix#)中所包含的範例 Code。
```C
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define NUM_THREADS 3
#define TCOUNT 10
#define COUNT_LIMIT 12
int count = 0;
int thread_ids[3] = {0,1,2};
pthread_mutex_t count_mutex;
pthread_cond_t count_threshold_cv;
void *inc_count(void *t)
{
long my_id = (long)t;
for (int i = 0; i < TCOUNT; i++) {
pthread_mutex_lock(&count_mutex);
count++;
// Check the value of count and signal waiting thread when condition is
// reached. Note that this occurs while mutex is locked.
if (count == COUNT_LIMIT) {
pthread_cond_signal(&count_threshold_cv);
printf("inc_count(): thread %ld, count = %d Threshold reached.\n",
my_id, count);
}
printf("inc_count(): thread %ld, count = %d, unlocking mutex\n",
my_id, count);
pthread_mutex_unlock(&count_mutex);
/* Do some "work" so threads can alternate on mutex lock */
sleep(1);
}
pthread_exit(NULL);
}
void *watch_count(void *t)
{
long my_id = (long) t;
printf("Starting watch_count(): thread %ld\n", my_id);
/*
Lock mutex and wait for signal. Note that the pthread_cond_wait
routine will automatically and atomically unlock mutex while it waits.
Also, note that if COUNT_LIMIT is reached before this routine is run by
the waiting thread, the loop will be skipped to prevent pthread_cond_wait
from never returning.
*/
pthread_mutex_lock(&count_mutex);
while (count < COUNT_LIMIT) {
pthread_cond_wait(&count_threshold_cv, &count_mutex);
printf("watch_count(): thread %ld Condition signal received.\n", my_id);
count += 125;
printf("watch_count(): thread %ld count now = %d.\n", my_id, count);
}
pthread_mutex_unlock(&count_mutex);
pthread_exit(NULL);
}
int main (int argc, char *argv[])
{
int i, rc;
long t1 = 1, t2 = 2, t3 = 3;
pthread_t threads[3];
pthread_attr_t attr;
/* Initialize mutex and condition variable objects */
pthread_mutex_init(&count_mutex, NULL);
pthread_cond_init (&count_threshold_cv, NULL);
/* For portability, explicitly create threads in a joinable state */
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
pthread_create(&threads[0], &attr, watch_count, (void *)t1);
pthread_create(&threads[1], &attr, inc_count, (void *)t2);
pthread_create(&threads[2], &attr, inc_count, (void *)t3);
/* Wait for all threads to complete */
for (i = 0; i < NUM_THREADS; i++)
pthread_join(threads[i], NULL);
printf ("Main(): Waited on %d threads. Done.\n", NUM_THREADS);
/* Clean up and exit */
pthread_attr_destroy(&attr);
pthread_mutex_destroy(&count_mutex);
pthread_cond_destroy(&count_threshold_cv);
pthread_exit(NULL);
}
```
---
#### pthread_cond_wait(&count_threshold_cv, &count_mutex);
#### pthread_cond_signal(&count_threshold_cv);
wait 用於阻塞目前的 Thread , 等待另外一個 Thread 的 signal 的到來 (mutex 會在 wait 期間被 unlock , signal 到來後又 lock 回去 )。
例子:
A Thread:
```C
pthread_mutex_lock(&mut);
while (x <= y) {
pthread_cond_wait(&cond, &mut);
}
/* operate on x and y */
pthread_mutex_unlock(&mut);
```
B Thread:
```C
pthread_mutex_lock(&mut);
/* modify x and y */
if (x > y) pthread_cond_broadcast(&cond);
pthread_mutex_unlock(&mut);
```
---
#### pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
函式原型為
```C
pthread_attr_setdetachstate（pthread_attr_t *attr, int detachstate）
```
```datachstate``` 的參數可選擇為
##### ```PTHREAD_CREATE_DETACHED```（分離執行緒）
會在執行緒完成任務後直接釋放系統資源,不需等待```pthread_join()```。
##### 及 ```PTHREAD _CREATE_JOINABLE```（非分離執行緒）
反之,需要等待```pthread_join()```返回才會釋放系統資源。
---
#### pthread_create(&threads[0], &attr, watch_count, (void *)t1);
函式原型為
```C
int pthread_create(pthread_t *tid , const pthread_attr_t *attr , void *(*function)(void *) , void *argument)
```
產生一個Thread及執行Function，附有4個參數。
:::info
參數1:
pthread_t *tid為pthread的指標，在使用Thread之前必須要先宣告一個pthread_t的變數。
參數2:
const pthread_attr_t *attr 為該 Thread 的屬性，預設是NULL。
參數3:
void *(*function)(void *) 為 Function pointer ，這邊要放入需要被執行的Function。
參數4:
void *argument 為 Ｆunction pointer 所要帶的參數。
回傳值:
如果執行成功則回傳0，如果執行失敗則回傳錯誤代碼。
:::
---
#### void pthread_exit (void *value_ptr)
這個 Function 的作用是用來關閉一個 Thread ，附帶有1個參數。
:::info
參數1:
void *value_ptr 用來設定執行成功時該 Thread 會回傳的值，這個值可由 pthread_join() 這個 Function 來取得。
回傳值:
不會回傳任何值。
:::
---
#### int pthread_cancel (pthread_t thread)
關閉一個指定的 Thread ，附帶有一個參數。
:::info
參數1:
pthread_t thread 為要關閉的 Thread 。
回傳值:
如果執行成功則回傳0，如果執行失敗則回傳錯誤代碼。
:::
---
#### int pthread_join (pthread_t thread, void **value_ptr)
等待目標 Thread 執行完畢後,目前執行 pthread_join 的 Thread (呼叫者) 才會繼續執行。
:::info
參數1:
pthread_t thread為要等待的目標Thread。
參數2:
void \**value_ptr 用來取得目標 Thread 的回傳值。
回傳值:
如果執行成功則回傳0，如果執行失敗則回傳錯誤代碼。
:::
---
#### 參考及引用資料
[Toward Concurrency](https://hackmd.io/s/Skh_AaVix#)
[线程的分离状态 pthread_attr_setdetachstate 函数使用 ](http://blog.csdn.net/sjin_1314/article/details/8023575)
[Pthread 程式撰寫](http://blog.xuite.net/nikoung/wretch/154071878-Pthread+%E7%A8%8B%E5%BC%8F%E6%92%B0%E5%AF%AB)
[pthread_cond_signal和pthread_cond_wait简介](http://www.eefocus.com/andrew_dj/blog/12-08/282740_85e58.html)
---
Sign in with Wallet
Connect another wallet