# 2016q3 Homework2 (phonebook-concurrent)
contributed by <`HaoTse`>

---

## 閱讀筆記

----

### Concurrency vs. Parallelism

#### Concurrency (並行)
- 單一處理器處理兩個或兩個以上的問題
- 分割的工作是交錯執行的
- 用於當只有少量的 CPU 資源和許多工作
- 因為 CPU 的可操作性上升，所以 Concurrency 愈來愈熱門了


#### Parallelism (並行)
- 多個處理器處理一個問題
- 將一個問題分割成數個相似的大部份


----

### Thread vs. Coroutines

#### Thread
- 作業系統會交錯執行 task，並根據下列 scheduling algorithm 的不同決定優先權
- [SMT (Simultaneous Multithreading), VMT(Vertical Multithreading)](http://www.fujitsu.com/global/products/computing/servers/unix/sparc-enterprise/technology/performance/processor.html)


#### Coroutines (協同程序、協程)
- 由 programmer 控制，與 kernel 無關
- [wiki](https://en.wikipedia.org/wiki/Coroutine)


----

### POSIX Threads
[Getting Started With POSIX Threads](http://www.csie.ntu.edu.tw/~r92094/c++/pthread.txt)

pthread_t         a_thread;
pthread_attr_t    a_thread_attribute;
void              thread_function(void *argument);
char              *some_argument;
  
pthread_create( &a_thread, a_thread_attribute, (void *)&thread_function, 
               (void *) &some_argument);

- `exit`的陷阱
在任何一個 thread （不論 parent or child）裡呼叫 `exit` 都將導致 process 結束，而所有的 thread 也跟著一起結束了。所以如果要結束一個 thread ，我們必須使用 `pthread_exit` 這個函數。
- **race condition**
當許多 process 同時對同一個資料進行存取和操作，會依賴於不受控制的事件的出現順序或者出現時機而導致結果有所不同。
- `sleep`的陷阱
當 thread 呼叫 `sleep` 時，講導致整個 process 停下來。這表示所有屬於這個 process 的 thread 也將跟著停頓下來。另外一個適用的函數是 `pthread_delay_np` （np 表示 not portable）。
>> `_np` 表示 not portable，網路上找資料容易找到錯誤的材料，所以要回歸第一手資料。權威性的資料可參見 Open Group: [Threads](http://pubs.opengroup.org/onlinepubs/007908799/xsh/threads.html) [name=jserv]

例如要讓程式停2秒可以使用下列方法

struct timespec delay;
delay.tv_sec = 2;
delay.tv_nsec = 0;
pthread_delay_np(&delay);

- 同步問題
- mutex：一組用來控制共享資源存取的一組函數
`pthread_mutex_init(&mutex, pthread_mutexattr_default)` 初始 mutex
`pthread_mutex_destroy(&mutex)` 釋放 mutex
- condition variable
將 mutex 的功能加以延伸，能夠做到讓某一個 thread 能暫停，並等待另一個 thread 的信號（signal）。當信號來了，thread 就醒過來，然後將相關的 mutex lock 起來。

----

### Thread Pool

#### Thread 可能造成的缺陷
- 建立太多執行緒，會浪費一定資源，並且有些執行緒未被充份使用
- 銷毀太多執行緒，會導致之後浪費時間再次創建它們
- 建立執行緒太慢，導致效能變差
- 銷毀執行緒太慢，導致其它執行緒沒有資源

#### Thread Pool 可以解決這上述問題，它可以達到下列工作
1. 管控 Thread 的產生與回收
2. 分發 Thread 處理 request
3. 處理 request 的 queue

#### C Thread Pool 實作範例
- [x] [threadpool-mbrossard](https://github.com/mbrossard/threadpool)
- [ ] [threadpool-jmatthew](http://people.clarkson.edu/~jmatthew/cs644.archive/cs644.fa2001/proj/locksmith/code/ExampleTest/)
- [ ] [cthreadpool](https://sourceforge.net/projects/cthpool/)
- [ ] [C-Thread-Pool](https://github.com/Pithikos/C-Thread-Pool)

----

### Lock-free Thread Pool

---

## Code Refactoring

----

- 將 `main.c` 中 opt 版本需引入的標頭檔集中在 `main.c` 的前面方便閱讀

//include the needed header file and define marco when OPT
#if defined(OPT)
#include "file.c"
#include "debug.h"
#include <fcntl.h>

#define ALIGN_FILE "align.txt"

#ifndef THREAD_NUM
#define THREAD_NUM 4
#endif

#endif

----

- 改變 `phonebook_opt.c(append)` 中的 for loop 為 while loop，因為 for loop 中條件敘述過長，不易閱讀

char *i = app->ptr;
while(i < app->eptr) {
	app->pLast->pNext = j;
	app->pLast = app->pLast->pNext;

	app->pLast->lastName = i;
	dprintf("thread %d append string = %s\n",
			app->tid, app->pLast->lastName);
	app->pLast->pNext = NULL;

	i += MAX_LAST_NAME_SIZE * app->nthread;
	j += app->nthread;
	count++;
}

----
- 解決 `warning: ‘CPU_time’ defined but not used [-Wunused-function]`
將 `phonebook_opt.c` 和 `phonebook_opt.h` 中的 `static double diff_in_second(struct timespec t1, struct timespec t2)` 前後加入 `#ifdef PROFILE` 確認是否開啟 PROFILE 模式。
如果要使用 DEBUG 需要使用 `$ make DEBUG=1 PROFILE=1`

----

- 更改 `main.c` 中的第105行起的 for loop 為下列的樣子

pHead = app[0]->pHead;
dprintf("Connect %d head string %s %p\n", 0, app[0]->pHead->pNext->lastName, app[0]->ptr);
etmp = app[0]->pLast;
for (int i = 1; i < THREAD_NUM; i++) {
	etmp->pNext = app[i]->pHead;
	dprintf("Connect %d head string %s %p\n", i, app[i]->pHead->pNext->lastName, app[i]->ptr);

	etmp = app[i]->pLast;
	dprintf("Connect %d tail string %s %p\n", i, app[i]->pLast->lastName, app[i]->ptr);
	dprintf("round %d\n", i);
}

做了兩個主要的修改
1.將 i = 0 的情況移出 for loop 減少 branch 的數量
2.更正原本程式的錯誤，原本為連接 `pHead->pNext` ，但應連接 `pHead` 才對

---

## 效能分析

### 原始版本

### Thread Pool
使用前面提到的 **threadpool-mbrossard** 實作
將 `main.c` 中的 thraed 改變為以下的操作方式

threadpool_t *pool = threadpool_create(THREAD_NUM, POOL_SIZE, 0);
for(int i = 0; i < THREAD_NUM; i++) {
	app[i] = new_append_arg(map + MAX_LAST_NAME_SIZE * i, map + fs, i, THREAD_NUM, entry_pool + i);
	threadpool_add(pool, &append, (void *)app[i], 0);
}
threadpool_destroy(pool, 0);

不過這裡執行時產生了 Segmentation fault，研究了一陣子沒有結論，在[TempoJiJi 的筆記](https://hackmd.io/s/rymKa4aT#修改opt實做thread-pool) 中找到了答案，將 `threadpool_destroy(pool, 0)` 改成 `threadpool_destroy(pool, 1);` 就成功了。

---

## 參考資料
- [mmap](http://welkinchen.pixnet.net/blog/post/41312211-%E8%A8%98%E6%86%B6%E9%AB%94%E6%98%A0%E5%B0%84%E5%87%BD%E6%95%B8-mmap-%E7%9A%84%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95)

###### tags: `HaoTse` `sysprog21` `phonebook` `concurrent` `POSIX Threads`