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

## POSIX Threads 學習

### thread 是什麼？

* Thread 通常被稱做輕量級的行程（Lightweight process；LWP）
* [Mach microkernel](https://en.wikipedia.org/wiki/Mach_(kernel)) 作業系統中同一個task 的所有 thread 共享該 task 所擁有的系統資源。
* UNIX 的一個 process 可以看成是一個只有一個 thread 的 Mach task。
* 對 CPU 而言，產生一個 thread 是一件相對簡單的工作。
* 共享系統資源的 thread 跟獨佔系統資源的 process 比起來，thread 是也是相當節省記憶體的。

### 建立thread

  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);

timming delay 來達成thread間的同步是錯誤的，因為 thread 間的緊密耦合（tightly coupled）特性很容易讓我們使用一些不精確的方法來達成其間的同步處理，如果要讓thread 停頓可以使用pthread_delay_np （np 表示 not portable）函式。
>> 在 POSIX Thread 中，`_np` 表示 not portable [name=jserv]

### Thread 同步問題
#### mutex 和 condition variable
* POSIX 提供了兩組用來使 thread 同步的基本指令： mutex 和 condition variable。
* mutex 指的是一組用來控制共享資源存取的一組函數。
* thread 使用一些在pthreadcreate 之前定義或在其所呼叫的函數中定義的變數來完成其工作，並將他的成果經由整體變數合併。對這些大家都可以存取的變數，我們必須加以控制。
* mutex 一般用在解決 race condition 問題，但是 mutex 並不是一個很強的機制，因為他只有兩個狀態：locked 和 unlocked。
* POSIX 定義的條件變數（condition variable）將 mutex 的功能加以延伸，能夠做到讓某一個 thread 能暫停，並等待另一個 thread 的信號（signal）。

pthread_mutex_init() 

<s>pthread_mutex_lock() //需先lock mutex，看看buffer 中是否有資料，若有資料則將其取出</s>
>> 請不要活在「腦補」的世界中，再次詳細閱讀 man page: [pthread_mutex_lock](http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html) [name=jserv]
>已修改 謝謝老師提醒[name=儂偉]

pthread_mutex_lock()    //用來鎖定thread，直到mutex變為可用狀態
pthread_mutex_unlock()
pthread_mutex_destroy() //釋放 mutex

#### 使用 Semaphores 達成協調工作(解決 spin-lock 問題)
##### Semaphore 相關的運算

semaphore_init()	   //使用 semaphore 前必須呼叫 init 函數,初始值均為 1
semaphore_up()		   //遞增 semaphore
semaphore_down()          //運算將在 semaphore 值小於或等於零時暫停
semaphore_destroy()	   //釋放semaphore
semaphore_decrement()

### 使用注意事項
* 編譯使用 pthread 的程式，必須引入相關的標頭檔 (一般是 `<pthread.h>`)
* 連結 pthread library` cc hello_world.c -o hello_world -lpthread`
* 使用 semaphore 則額外引入標頭檔。
>> 注意: 有兩個完全不同的 semaphore 實作，一個是 System V semaphore，另一個是 POSIX semaphore，請參閱討論 [What are the trade-offs between using a System V and a Posix semaphore?](http://stackoverflow.com/questions/368322/differences-between-system-v-and-posix-semaphores) [name=jserv]
>謝謝老師提醒[name=儂偉]

#### Differences between System V and Posix semaphores
由[Semaphores in Linux](http://www.linuxdevcenter.com/pub/a/linux/2007/05/24/semaphores-in-linux.html?page=4)這個網站所列出的主要差異，並整理出來下列幾項
* System V 與 POSIX 區別於System V可以控制the semaphore count數量的增加或減少，但在POSIX，the semaphore count只能加1或減1。
* System V 可以去改變semaphores原始權限的子集，而POSIX不被允許更改semaphores的權限。
* 從用戶角度來看，semaphores的初始化和建立是 atomic 在POSIX。
* 但從使用角度來看，POSIX的可擴展性比System V 高很多，由於POSIX直接使用未命名semaphores。
* 當建立semaphore object時，System V 建立一個semaphores "array"，但POSIX 只建立單一semaphores。因此，System V在建立semaphore時"memory footprint-wise"的成本是比POSIX更高的。所以有人說POSIX性能是比System V更好。
* POSIX為 "process-wide semaphores" 機制而不是 "system-wide semaphores" 機制
* POSIX提供；non-persistent semaphores； 機制，也就是說當一個開發者忘記關閉"semaphore" ，會在"process exit"時被清除。

---
## [MMAP](http://man7.org/linux/man-pages/man2/mmap.2.html)

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset);
int munmap(void *addr, size_t length);

* mmap()建立新的mapping在呼叫行程的定址空間，新mapping的開始定址空間被指定在 *addr。
>> 尊重我們的傳統文化，請用台灣慣用術語。process = 行程; call = 呼叫; virtual memory = 虛擬記憶體; address space = 定址空間; file = 檔案; access = 存取; return = 傳回; create = 建立; [name=jserv]
>> 已修改,以後會多加注意[name=儂偉]
* length參數為指定mapping的長度。
* 如果addr為NULL，kernel將在建立的mapping地址中選擇，這是建立新的mapping最簡單的方法。
* 如果addr不是NULL，在LINUX,mapping會在附近的page boundary建立，並將新mapping地址傳回。
* prot參數描述了需要保護的記憶體保護mapping(必須不能跟打開傳回模式衝突)
* PROT_EXEC 可能執行
* PROT_READ 可能讀取
* PROT_WRITE 可能寫入
* PROT_NONE 可能不能存取
* flag參數用來確定更新mapping是否被有其他行程mapping同個區域，這些狀態由下列flag值來確定：
* MAP_SHARED 分享此mapping
* MAP_PRIVATE 建立一個私有copy-on-write mapping。

---
## 實作threadpool
參考[mbrossard 完整的 ThreadPool](https://github.com/mbrossard/threadpool/blob/master/src/threadpool.c) 原始碼
新增phonebook_threadpool來與opt做比較
並在main裡新增了下列程式碼

#if defined THREADPOOL
#define QUEUE 256
    extern threadpool_t *pool;
    extern pthread_mutex_t lock;

    pthread_mutex_init(&lock, NULL);
    assert((pool = threadpool_create(THREAD_NUM, QUEUE, 0)) != NULL);
    append_a **app = (append_a **) malloc(sizeof(append_a *) * THREAD_NUM);
    for (int i = 0; i < THREAD_NUM; i++)
        app[i] = new_append_a(map + MAX_LAST_NAME_SIZE * i, map + fs, i,
                              THREAD_NUM, entry_pool + i);
    for (int i = 0; i < THREAD_NUM; i++) {
        threadpool_add(pool, &append, (void *) app[i] , 0);
    }

    entry *etmp;
    pHead = pHead->pNext;
    for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = app[i]->pHead->pNext;
            dprintf("Connect %d head string %s %p\n", i,
                    app[i]->pHead->pNext->lastName, app[i]->ptr);
        } else {
            etmp->pNext = app[i]->pHead->pNext;
            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);
    }
    clock_gettime(CLOCK_REALTIME, &end);
    cpu_time1 = diff_in_second(start, end);
    assert(threadpool_destroy(pool, 0) == 0);

>遇到問題 findname一直失敗，待解決[name=儂偉]

#### 使用GDB

[New Thread 0x7ffff6a96700 (LWP 4518)]
[New Thread 0x7ffff6295700 (LWP 4519)]
[New Thread 0x7ffff5a94700 (LWP 4520)]
[New Thread 0x7ffff5293700 (LWP 4521)]
[Thread 0x7ffff5293700 (LWP 4521) exited]
[Thread 0x7ffff6295700 (LWP 4519) exited]
[Thread 0x7ffff5a94700 (LWP 4520) exited]
[Thread 0x7ffff6a96700 (LWP 4518) exited]

Breakpoint 1, main (argc=1, argv=0x7fffffffde68) at main.c:106
106	    pHead = pHead->pNext;
(gdb) p entry_pool[2]->lastName 
$1 = 0x0
(gdb) p entry_pool[3]->lastName 
$2 = 0x0
(gdb) p entry_pool[4]->lastName 
$3 = 0x7ffff729a040 "aaaaaaaa\n"
(gdb) p entry_pool[5]->lastName 
$4 = 0x0
(gdb) p entry_pool[8]->lastName 
$5 = 0x7ffff729a080 "aaaaaahhhhh\n"

>發現只有app[0]的thread有執行,待解決[name=儂偉]
* 看到[TempoJiJi同學](https://hackmd.io/s/rymKa4aT)有遇到同樣問題，並提供解決方法

assert(threadpool_destroy(pool, 1) == 0);

將上面0改成1，解決Thread未完成被shutdown的問題

### 與原始OPT做比較
#### THREAD = 4
#### THREAD = 8
#### THREAD = 16
#### THREAD = 32

>>發現apped的速度反而變慢，可是當我THREAD數量增加時，threadpool的速度會增加，但OPT卻下降[name=儂偉]
### 最後統計圖
### cache-misses 比較圖
>>發現在Thread=8時cache-misses最高，但還在思考原因，待有人可以討論和解答。[name=儂偉]
---
## 重新學習Git Commit
由於上禮拜被老師指出這方面的缺失，並且根據老師給的資料重新學習
* 使用`$git log --oneline -5`可以查詢commit資訊
* 根據[How to Write a Git Commit Message](http://chris.beams.io/posts/git-commit/)網站，一開始就指出內容需要保持簡潔和一致性
* git提交訊息是為了傳遞開發者對相關程式更改，並且這些更改的差異能正確提提供給其他開發者
* 一個長期專案的生產力，其中間取決於其可維護性和維護者寫的日誌
>了解到了寫好git commit的重要性[name=儂偉]
* 為了創造一個有用的版本歷史紀錄，一個團隊需定義至少下面3點達成一致：
* Style： Markup syntax, wrap margins, grammar, capitalization, punctuation等，刪除一些不確定性，並讓其盡可能簡單，最終會產生非常一致的日誌。
* Content： commit內容需要包含哪些訊息，或不應該包含？
* Metadata： 要如何發佈被引用的tracking IDs，pull request numbers等。

---
## 參考資料
* [Getting Started With POSIX Threads](http://www.csie.ntu.edu.tw/~r92094/c++/pthread.txt)
* [Differences between System V and Posix semaphores](http://stackoverflow.com/questions/368322/differences-between-system-v-and-posix-semaphores)
* [Semaphores in Linux](http://www.linuxdevcenter.com/pub/a/linux/2007/05/24/semaphores-in-linux.html?page=4)
* [MMAP](http://man7.org/linux/man-pages/man2/mmap.2.html)
* [TempoJiJi同學](https://hackmd.io/s/rymKa4aT)
* [How to Write a Git Commit Message](http://chris.beams.io/posts/git-commit/)