# 2017q1 Homework4 (phonebook-concurrent)
###### tags: `embedded`
contributed by <`Cayonliow`>

## 作業
* 作業說明： [B07: phonebook-concurrent](https://hackmd.io/s/rkOExTOoe#)
* 參考資料： [Toward Concurrency](https://hackmd.io/s/Skh_AaVix#), [李昆憶學長的共筆](https://hackmd.io/s/HJFhaiAp#) , [The Free Lunch Is Over ](http://www.gotw.ca/publications/concurrency-ddj.htm), [Concurrency is not parallelism](https://blog.golang.org/concurrency-is-not-parallelism)

## 背景知識
這張圖我在計組上課的時候有看過， 跟老師說的一樣
* 以前 CPU 增進效能的手段
* Clock speed
* Execution Optimization
* Pipelining、Branch prediction
* Out-of-order execution 還要注意不能讓原本程式崩潰 (read/write reorder)
* Cache：盡量減少存取 Main memory 的機會

可是依上圖， Perf/Clock(ILP), Power 跟 Clock Speed 在 2000 年就出現飽和的現象， 所以增進效能的手段也跟着改變

* 現在 CPU 增進效能的手段

* Hyperthreading: 在 single CPU 上同時執行多個 thread，但是共用 ALU、FPU
* Multicore：多個 CPU
* Cache

[Free (performance) lunch](http://www.gotw.ca/publications/concurrency-ddj.htm) 指的是程式設計的效能可以透過 CPU 時脈的進步而得到改善。會說 over 是因為 CPU 的時脈無法得到更進一步的增加，由於耗電和散熱的問題，所以程式設計師必須要修改程式才能改善效能

### Concurrency

* 使用 Concurrency 的理由:
1.分離可獨立運作的工作；
2.為了效能，像是使用多核新的 CPU

* 可是並非所有的程式都合適平行化；所以程式要設計可以實行 Concurrency 是很困難的
* 如果程式的相依性太高或是太常取用共同資源則會拖慢 Concurrency 的效率
* 對軟體設計的影響
1. 想要完全使用到 CPU 所有的資源
2. 程式越來越有機會造成 CPU-bound。雖然主要還是 IO-bound 等，但如果 CPU 時脈無法增加，而其他存取方式速度變快，最後會發生 CPU-bound
3. 效能優化將會越來越重要
4. 程式語言強迫必須好好處理 concurrency
* A happends-before B ： 在 B 開始執行之前， A 的執行效果必須可見。
* A is Sequenced-Before B ： 在同一個 thread 下，A 比 B 先求值。
* A is synchronized-with B ： A 在這一個 thread 對記憶體的操作，在另一個 thread 的 B 必須可見。
* Sequential consistency ： 無論處理器實際怎麼執行，確保結果跟照程式順序執行一樣
* Read before Write ： 在新值寫入前讀取到舊值
* Write after Write ： 在正確值寫入後被舊值複寫 (有先後)

* Concurrency is not parallelism
* Concurrency 是指程式架構， 將程式拆開成多個可獨立運作的工作
* eg：drivers， 都可以獨立運作，但不需要平行化。
* 拆開多個的工作不一定要同時運行
* 多個工作在單核心 CPU 上運行
* 工作可拆分成「獨立執行」的部份, 這樣「可以」讓很多事情一起做, 但是「不一定」要真的同時做。
* 展示具有並行性，但不去同時執行
* 並行性是種「架構程式」的概念。寫下一段程式之前, 思考問題架構時就決定好的。

* 

* Parallelism 是指程式執行， 同時執行多個程式. Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。
* eg：Vector dot product
* 程式會同時執行 (例如：分支後，同時執行，再收集結果)
* 一個工作在多核心 CPU 上運行
* 把規劃好， 能夠並行的程式, 分配給不同執行緒, 並讓他們同時執行。
* 

## 開發記錄

一開始先 make plot 看看結果
發現 `append()` 的效能提升了很多， 所用的時間甚至比 `findName()` 來的少

然後參考 [csielee 的共筆](https://hackmd.io/s/ByiOeFYie#) 分析 concurrent 的實作

主要是在 append() 的時候將工作分給多個 thread 一起做
並使用下面的方法，讓多個 thread 可以順利 concurrent

* 對齊
* 利用 text_align 對齊 `DICT_FILE`(要讀取的名字檔案)
* [open()](http://c.biancheng.net/cpp/html/238.html)
* `O_RDONLY`: 以只讀方式打開文件
* `O_NONBLOCK`：以不可阻斷的方式打開文件，也就是無論有無數據讀取或等待，都會立即返回進程之中

    text_align(DICT_FILE, ALIGN_FILE, MAX_LAST_NAME_SIZE);
    int fd = open(ALIGN_FILE, O_RDONLY | O_NONBLOCK);
    off_t file_size = fsize(ALIGN_FILE);

* 對映
* 把 `ALIGN_FILE` 的檔案內容利用 mmap() 記憶體對映到記憶體當中
* 同時利用對齊後的檔案大小去計算出需要幾個 entry，利用一次 malloc 把需要的記憶體空間一次分配好
* [mmap()](http://c.biancheng.net/cpp/html/138.html)
* `PROT_READ`：映射區域可被讀取
* `PROT_WRITE`：映射區域可被寫入
* `MAP_PRIVATE`：對應射區域的寫入操作會產生一個映射文件的複制，即私人的“寫入時復制”（copy on write）對此區域作的任何修改都不會寫回原來的文件內容 。
* 在調用mmap（）時必須要指定MAP_SHARED或MAP_PRIVATE。

    map = mmap(NULL, file_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
    assert(map && "mmap error");
    entry_pool = (entry *)malloc(sizeof(entry) *
                                 file_size / MAX_LAST_NAME_SIZE);
    assert(entry_pool && "entry_pool error");

* 分配
* 最後將這些東西分配進每個 thread，這樣互相執行起來， 就可以解決同時讀取同一個檔案的檔案指標 critical 問題，跟頻繁的 malloc

for (int i = 0; i < THREAD_NUM; i++)
        // Created by malloc, remeber to free them.
        thread_args[i] = createThead_arg(map + MAX_LAST_NAME_SIZE * i, map + file_size, i,
                                         THREAD_NUM, entry_pool + i);

* merge linked list
* 最後等每個 thread 執行完，就把每個 thread 各自產生的 linked list 合併起來

    for (int i = 0; i < THREAD_NUM; i++) {
        if (i == 0) {
            pHead = thread_args[i]->lEntry_head->pNext;
            DEBUG_LOG("Connect %d head string %s %p\n", i,
                      pHead->lastName, thread_args[i]->data_begin);
        } else {
            e->pNext = thread_args[i]->lEntry_head->pNext;
            DEBUG_LOG("Connect %d head string %s %p\n", i,
                      e->pNext->lastName, thread_args[i]->data_begin);
        }

        e = thread_args[i]->lEntry_tail;
        DEBUG_LOG("Connect %d tail string %s %p\n", i,
                  e->lastName, thread_args[i]->data_begin);