Try   HackMD

2017q1 Homework4(phonebook-concurrent)

contributed by<yanang>

tags: yanang

開發環境

  • OS: Ubuntu 16.04 LTS
  • L1d cache: 32K
  • L1i cache: 32K
  • L2 cache: 256K
  • L3 cache: 3072K
  • Architecture: x86_64
  • CPU 作業系統: 32-bit, 64-bit
  • Byte Order: Little Endian
  • CPU(s): 4
  • Model name: Intel® Core™ i5-7200U CPU @ 2.50GHz
  • Linux yanang 4.8.0-36-generic
    #36~16.04.1-Ubuntu SMP

read

  • Concurrency系列(一): 理解Concurrency之路
    • atomic operation :
      不可被中斷的一個或一系列操作，多對應特殊的 CPU 指令。在所有的線程同步機制裡原子操作是最迅速的，因為完全不需要加鎖。原子操作是實現 Lock-Free 最重要的武器。
  • Concurrency系列(二): 從Sequenced-Before開始說起
    • Evaluation - value computations and side effect
    • A is sequeced-before B : A 必會在 B 之前完成

    經典的未定義行為 i = i++

    i++ 的 side effect 只 sequenced-before i++ 本身的 result，這個 side effect 可能發生在 assignment 之前或之後。

  • Concurrency系列(三): 朝Happens-Before邁進
    • Happens-before in Java : 當行為 A happens-before B 時，代表 A 的效果可見，而且發生於 B 之前
    • differnet between Sequenced-Before and Happens-before : sequenced-before 強調實際上的執行順序，而 happens-before 強調 "visible"-看起來先執行前者再執行後者的效果

    happens-before but not really execute first :
    A = B + 1;
    B = 1;
    實際上執行時，編譯器有很大的空間可以對程式執行的順序做優化。
    movl B(%rip), %eax
    addl $1, %eax
    movl %eax, A(%rip)
    movl $1, B(%rip)

    • Happens-before in c++ : (1) A is sequenced-before B (2) A inter-thread happens before B ( Sequenced-before 其實就是同一個 thread 內的 happens-before。)
    • C++定義 inter-thread 的 happens-before : (1) A synchronizes-with B (A和B有適當的同步) (2) A is dependency-ordered before B (A和B有相依的順序關係)
  • Concurrency系列(四): 與Synchronizes-With同在
    • synchronizes-with是一種跨thread間的happens-before關係，可以透過過mutex lock, thread create/join、Aquire and release Semantic來建立
  • Concurrency系列(五): Sequential Consistency的代價
    • Sequential Consistency :(1)對於每個獨立的處理單元，執行時都維持程式的順序(Program Order) (2)整個程式以某種順序在所有處理器上執行
    • Write Bufers with Bypassing Capability : 維持 Write->Read 的順序
    • Overlapping Write Operations : 維持 Write->Write 的順序
    • Non-Blocking Read Operations : 維持 Read->Read, Read->Write 的順序
    • cache coherence protocol : 確保程式遵守 SC

初步測試

  • $ make
  • $ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.002826 sec
execution time of findName() : 0.002683 sec
  • $ make plot

thread pool

概念

a thread pool maintains multiple threads waiting for tasks to be allocated for concurrent execution by the supervising program.
– wiki

實作




threadpool_t *threadpool_create(int thread_count, int queue_size, int flags);
int threadpool_add(threadpool_t *pool, void (*routine)(void *),void *arg, int flags);
int threadpool_destroy(threadpool_t *pool, int flags);
  • 先創出 threadpool ，再用將要呼叫的 function 傳入
  • threadpool_destroy 先判斷各個 thread 是否完成 ， 才 free(threadpool)
  • 完成後遇到一個 bug ，程式時好時壞
yanang@yanang:~/phonebook-concurrent$ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
phonebook_opt: main.c:165: main: Assertion `findName(input, e) && "Did you implement findName() in " IMPL "?"' failed.
已經終止 (core dumped)

yanang@yanang:~/phonebook-concurrent$ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.003103 sec
execution time of findName() : 0.002744 sec

觀察 threadpool_add() 的回傳值，thread 正常執行
重新看一次 threadpool_destroy() 當中的 pthread_join 是否正常執行
發現我傳入的 flags 錯了導致無法正常執行

  • 修改後重新執行 $ ./phonebook_opt
orginal file size = 3206080
size of entry : 24 bytes
execution time of append() : 0.003631 sec
execution time of findName() : 0.002710 sec
  • $ make plot

時間少量的增加了，因為我在中間呼叫 thread_join 之後，就立刻 free(thread pool)
增加了釋放記憶體的時間

參考資料

Last changed by 
 
yanang
0
359
Published on HackMD