2016q3 Homework2 (phonebook-concurrent)

contributed by <shelly4132>

開發環境

• 作業系統：Ubuntu 16.04 LTS

• Cache：

  $ lscpu | grep cache

  • L1d cache：32K
  • L1i cache：32K
  • L2 cache：256K
  • L3 cache：3072K

Concurrency vs. Parallelism

• Concurrency：我們將一個程式分割成多個小部份稱為task，而concurrency就是在一個proccessor的情況下，在能保證其正確性的前提下對這些task進行並行運算(thread不一定會同時執行)。

• Parallelism：parallelism則是指在多個proccessor的情況下，我們為了增進執行速度而對一個程式進行平行運算(同時執行多個thread)。

Sequenced-before

sequeced-before就是一種在同一個thread下，求值順序關係的描述。

• 求值：可分為value computation(運算完的結果)和side effect(修改記憶體內變數的值、呼叫library內的I/O function等等)

1. 如果A is sequenced-before B，代表A的求值會先完成，才進行對B的求值
2. 如果A is not sequenced before B 而且 B is sequenced before A，代表B的求值會先完成，才開始對A的求值。
3. 如果A is not sequenced before B 而且 B is not sequenced before A，代表兩種可能，一種是順序不定，甚至這兩者的求值過程可能會重疊（因為CPU優化指令交錯的關係）或不重疊

雖然我們對運算優先權做了很多定義，比如說f1() + f2()會先計算完f1()和f2()才計算他們加起來的結果(運算元的運算優於運算子)，但仍有許多運算是未定義的。
比如說 i = i++;，我們不知道究竟i會等於++後的結果還是等於i目前的值，因為我們沒有定義assignment跟i++的side effect的先後關係，所以讓程式產生了不確定性。

Happens-before

happens-before就是指前一個操作的效果必須在下一個操作執行之前出現。
但happens-before並不是指前一行的程式碼必須先於後一行的程式碼執行，只要執行出來的結果看起來像是那樣，那後面的程式碼先被執行也沒關係。

• sequence-before其實就是同一個thread裡的happens-before。
• 在多個thread的情形底下如果變數共用，若沒有保證happens-before的關係的話，可能會導致程式出現意料之外的結果。

Coroutines

• Context Switch：由OS根據一定的排程演算法，讓CPU一直保持有proccess在執行，而等到要執行某個proccess才把他的資料讀進記憶體，再把部份資料移出去的動作就叫context switch。

• Coroutines：由programmer利用一些程式技巧延遲執行某些task，讓程式不會因為某個要執行很久的東西而停頓。

  • coroutines的成本比context switch低

POSIX Threads

• Proccess：一個 process 包括了一個執行中的程式，和一些
  他所需的系統資源，諸如檔案描述表和位址空間等。

• Thread：thread 實質上就是一個程式計數器、一個堆疊再加上一組暫存器。一個proccess中可以有多個thread，而這些thread都共享同一個記憶體資源。

基本用法

• 宣告一個執行緒 pthread_t a_thread;
• pthread_attr_t ：thread attribute 描述 thread 的一些特性，目前我們遇到的大部份程式只需要指定為pthread_attr_default就好。
• pthread_create( &a_thread, a_thread_attribute, (void)&thread_function, (void *) &some_argument);：產生一個thread並執行傳進去的function。

同步問題

• Race Condition：當有2個以上的thread共享同樣的資料，並且他們同時都嘗試去改變它，那最後的結果會因為不同的thread先被執行而有不同。

mutex

mutex就像一把鎖，可以保護共享的資源。

• 宣告一個mutex變數 pthread_mutex_t mutex;
• 初始化mutex pthread_mutex_init(&mutex, pthread_mutexattr_default);
• 將mutex鎖起來，直到解鎖前其他thread不能存取被保護的共享資源pthread_mutex_lock( &mutex );
• 將mutex解鎖pthread_mutex_unlock( &mutex );
• 當我們不再需要mutex之後可以使用pthread_mutex_destroy(&mutex);來釋放mutex

phonebook-concurrent

執行看看

THREAD_NUM 4

• cache miss

Performance counter stats for './phonebook_opt' (100 runs):

           31,0883      cache-misses              #   22.999 % of all cache refs      ( +-  0.61% )
          135,1713      cache-references                                              ( +-  1.27% )
       2,2886,1173      instructions              #    1.10  insns per cycle          ( +-  0.04% )
       2,0871,7787      cycles                                                        ( +-  0.72% )

       0.149621109 seconds time elapsed                                          ( +-  2.18% )

理解code

mmap

將文件檔案的內容映射到一段虛擬記憶體上，通過對這段記憶體的讀取和修改，實現對文件的讀取和修改。

請尊重傳統文化，書寫台灣慣用科技術語。file = 檔案 jserv
好的><
shelly4132

void *mmap(void *start,size_t length, int prot,
           int flags, int fd, off_t offsize);

• start
  指向欲映射的核心起始位址，通常設為NULL，代表讓系統自動選定位址，核心會自己在行程位址空間中選擇合適的位址建立映射，映射成功後會返回該位址。
• length
  代表映射的大小。將的大小映射到記憶體。
• prot
  映射區域的保護方式。
  • PROT_EXEC 映射區域可被執行
  • PROT_READ 映射區域可被讀取
  • PROT_WRITE 映射區域可被寫入
  • PROT_NONE 映射區域不能存取
• flags
  影響映射區域的各種特性。
  • MAP_SHARED 允許其他映射該檔案的行程共享，對映射區域的寫入數據會複製回文件。
  • MAP_PRIVATE 不允許其他映射該檔案的行程共享，對映射區域的寫入操作會產生一個映射的複製(copy-on-write)，對此區域所做的修改不會寫回原檔案。
• fd
  由open返回的檔案描述符，代表要映射到核心中的檔案。
• offsize
  從檔案映射開始處的偏移量，通常為0，代表從檔案最前方開始映射。

Code Refactoring

• 將_append_a裡面的nthread刪掉，有需要用到thread數目的統一用THREAD_NUM代替，還可以減小entry size。
• 將append()裡面原本很多參數的for迴圈改成while讓程式比較好看。
• 利用彥寬學長寫的show_entry()去將字串印出來時發現有缺失，因為在將所有entry串成一條的時候，他一開始就從pNext開始所以導致前面4個字串被漏掉了，改成從pHead開始就ok了。

改進方向

• Thread pool
  建立thread需要系統資源，如果我們每次需要的時候才建立thread，不要的時候就丟掉，當數量多時其實是會降低效能的。所以thread pool的概念就是建立一個thread的池子，當需要thread的時候就從裡面拿，不用的時候再放回去，有效的重複利用資源。

• threadpool-mbrossard

• 建立一個task，讓thread知道要做什麼事。這裡我們紀錄要執行的 function pointer 與要傳遞的參數。

typedef struct {
	void (*function)(void *);
	void *argument;
} threadpool_task_t;

• 使用 pthread_t的pointer來紀錄所有thread(array)，head和tail用來紀錄array的offset

struct threadpool_t {
   pthread_mutex_t lock;
   pthread_cond_t notify;
   pthread_t *threads;
   threadpool_task_t *queue;
   int thread_count;
   int queue_size;
   int head;
   int tail;
   int count;
   int shutdown;
   int started;
};

參考

• Toward Concurrency
• Concurrency系列(二): 從Sequenced-Before開始說起
• Concurrency系列(三): 朝Happens-Before邁進
• 淺談coroutine與gevent
• Getting Started With POSIX Threads (繁體中文翻譯)
• 彥寬學長的筆記與影片
• 記憶體映射函數 mmap 的使用方法
• threadpool-mbrossard
• TempoJiJi