Try   HackMD

2016q3 Homework2 (phonebook-concurrent)

開發環境

  • 系統：Ubuntu 16.04 LTS (64 bit)
  • CPU：8-core 3.40GHz
  • Memory：24GB
  • Cache：
    • L1 data : 32KB
    • L1 instruction : 32KB
    • L2 : 256KB
    • L2 : 8192KB

使用liscpu和sudo lshw查看硬體資訊

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
每核心執行緒數：2
每通訊端核心數：4
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              94
Model name:            Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
製程：              3
CPU MHz：             799.929
CPU max MHz:           4000.0000
CPU min MHz:           800.0000
BogoMIPS:              6816.61
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           8192K
NUMA node0 CPU(s):     0-7

Concurrency

Concurrency (並行) vs. Parallelism (平行)

  • Concurrency 一條線上的分工
  • Parallelism 分好幾條線

Concurrency

  • A sequeced-before B 對同一個thread下，A先完成之後才開始進行B

  • A happens-before B 代表A的效果可見，而且發生於B之前

  • synchronized-with 跨thread版本的happens-before

  • happens-before存在相依性的問題

  • 最直覺的約定Sequential Consistency的定義:

    • 對於每個獨立的處理單元，執行時都維持程式的順序(Program Order)
    • 整個程式以某種順序在所有處理器上執行

  • 程式在編譯與執行的時候，不一定會真的照所寫的順序發生，non-blocking和cache存取的快慢有可能會違反SC

Blocking 與 Non-blocking I/O

  • Blocking I/O
    允許 sleep/awaken 動作的 process，基本動作：
    • 當 process 進行 read 動作但是資料尚未就緒時，process 必須被 block 住 (sleep)，而當有資料進來時就需要立即被喚醒 (awaken)，就算資料仍不完整也是
    • 當 process 進行 write 動作但是 buffer 沒有空間時，process 也必須被 block 住，而且必須被放到跟 read 動作不同的 wait queue 中去等待 wake-up (buffer 騰出空間寫入)
  • Non-blocking I/O
    • 讀不到資料或寫不進 buffer 時，他會送出 retry 的動作，再試一次

POSIX Threads

http://www.csie.ntu.edu.tw/~r92094/c++/pthread.txt
文中提到使用 thread 同步的基本指令： mutex 和 condition variable ，最後可用更強悍的整數 semaphore 來取代 mutex ，並解決 spin-lock 問題。

對於 thread 的 task migration，可用 atomics 這種輕量級的同步機制，效能會比 pthread_mutex_t 好許多。

lock-free thread pool 實做測試

$ git clone https://github.com/xhjcehust/LFTPool
$ cd LFTPool/
$ make
$ ./testtpool 
ok 1 - one thread in thread pool    time: 3105157us
ok 2 - heavy work    time: 573655us
ok 3 - light work    time: 64862us
ok 4 - drop remaing works and exit directly    time: 125113us
###0x7f5c928c9700.dispatch_work2thread: queue of thread selected is full!!!
not ok 5 - increase thread num
ok 6 - decrease thread num    time: 64772us
ok 7 - set least load alogrithm    time: 571112us

Phonebook Concurrency

offset

文件映射開始處的偏移量，紀錄兩個元素間的距離，0代表從最前端開始映射
依說明，因為不知道每個字元的offset，所以先將file整理成16 char alignment，之後再使用 mmap()

mmap

目的是解決fgets這個blocking IO，讓程式可以順利平行化

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

creates a new mapping in the virtual address space of the calling process. The starting address for the new mapping is specified in addr. The length argument specifies the length of the mapping.

其中開啟fd的open()中使用O_NONBLOCK設定:
以非阻塞不可阻断的方式開啟檔案打开文件，也就是无论有无数据读取或等待，都会立即返回行程进程之中

可加速程式進行，但有可能違反Sequential Consistency?

請尊重傳統文化，使用台灣科技術語 jserv

pthread + 簡易 memory pool

為thread開新的struct append_a存放，其中包括要append的phonebook entry

typedef struct _append_a {
    char *ptr;
    char *eptr;
    int tid;
    int nthread;
    entry *entryStart;
    entry *pHead;
    entry *pLast;
} append_a;

new_append_a()是使用mmap得到虛擬空間之後再依序設定位置

說好的 code refactoring 呢？ jserv

優化

memory pool

參考資料

https://hackmd.io/s/BkN1JNQp
https://hackmd.io/s/H10MXXoT
http://www.csie.ntu.edu.tw/~r92094/c++/pthread.txt
http://ithelp.ithome.com.tw/articles/10161404
http://man7.org/linux/man-pages/man2/mmap.2.html

Last changed by 
 
ChunJing Zhou
0
270
Published on HackMD