changed 8 years ago
Linked with GitHub

phonebook concurrent

contributed by <snoopy831002>

concurrency

  • concurrency 的開始:cpu的演進不再以提昇時脈為方向,多核與多執行序的時代來臨

  • 未來的效能效能提昇方向:

    1. hyperthread(多執行序並行處理task)
    2. multicore(核心多自然處理的快)
    3. cache(cache大小的增加與速度的提昇對效能影響顯著)
  • 未來程式的執行效能將不仰賴cpu的速度快慢,而是程式的平行化。

  • lock 與 lock-free programming(核心目標為使程序間可互相溝通順利)

    1. lock:包含mutex與semephore等,防止程序競爭同一記憶資源
    2. lock-free:沒有使用mutex與semephore等,但能達到locK者
  • concurrency v.s parallelism

    1. concurrency指的是一次可以做很多事情:If two or more problems are solved by a single processor.(multi-thread)
    2. parallelism指的是很多事情同時在發生:If one problem is solved by multiple processors.
  • concurrency所產生的問題:

    1. 多執行序競爭同ㄧ資源
    2. thread之間的不同步行為
      • 使用mutex或semephore改善
      • 確保在寫入或讀取共享記憶體資源之操作是atomic的
      • 必要時取消編譯器優化,因可能會有memory reordering所產生的不同步行為
  • coroutine

    • tasks are cooperatively multitasked by pausing and resuming functions at set points.(使原本單向執行的程式碼可以有交錯執行的結果)

mmap

因為原始使用fget的緣故,城市無法平行化,所以造成append()的時間一直無法有效縮短。故吳彥寬同學使用了mmap

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

1.addr可以設定起始位置
2.length決定mapping大小
3.flags可以決定是否可供其他thread看見
4.offset則由fd決定

pthread

  • Why not use a process?
    • threads are light weight processes
    • threads can be created with much less operating system overhead compared to processes.
  • Pthread 的建立
pthread_t a_thread;//定義thread pthread_attr_t a_thread_attribute;//通常使用pthread_attr_default即可 void thread_function(void *argument);//thread 所要執行的函式 char *some_argument;//thread 所要執行的函式中塞入的參數 pthread_create( &a_thread, a_thread_attribute, (void *)&thread_function, (void *) &some_argument);
  • Pthread 的結束
pthread_exit()
  • Pthread 的暫停(只影響單一thread,不影響整個process)
pthread_delay_np()
  • Mutex
pthread_mutex_t mutex; pthread_mutex_init(&mutex, pthread_mutexattr_default);//定義mutex pthread_mutex_lock( &mutex );//鎖定共享資源 pthread_mutex_unlock( &mutex );//解所共享資源 pthread_mutex_destroy();//結束mutex
  • Semaphores
    [實做後再補上]

thread pool

  • 之前的實做著重在減少findname()的執行時間,現在我們可以利用thread pool的方式優化append()。

    • 使用thread pool可以將我們之前多個thread的操作統整起來,現在我們要做的事情只要將工作丟入threadpool請它代為執行就好。在threadpool的操作下,thread的首要任務就是進入threadpool搶奪lock進行工作。
    • 因為threadpool-mbrossard本來就是以pthread寫的,所以在開始實做之前我把吳彥寬同學原本的pthread通通砍掉了
  • 實際操做

    • 利用threadpool-mbrossard
    • 引入的函式
      • threadpool_t *pool=threadpool_create(THREAD_NUM,QUEUE SIZE,FLAG);
        定義thread的多寡與queue大小,flag則設為NULL即可。這裡很像我們在使用pthread也要create一樣
      • threadpool_add(threadpool_t *pool, void (*function)(void *)
        將工作append()丟入threadpool中,此時thread就會開始搶工作了
        *int threadpool_destroy(threadpool_t *pool, int flags);最後清理掉threadpool
  • 實做結果

    • 原始pthread與threadpool的差異(使用4個 thread)
    • threadpool使用不同thread的差異

沒想到使用一條thread竟然是最快的

gnuplot補充

  • plot語法
    • datafile : 輸出的檔案
    • <xcol>: 使用資料第幾列作圖(可以不用設定)
    • <ycol>: 使用資料第幾行作圖(必設定)
    • xticlable(<labelcol>)[等同xtic(<labelcol>)]:資料x座標標籤
    • <plotstyle>:圖的種類(histogram長條圖)
plot ’datafile’ using <xcol>:<ycol>:xticlabels(<labelcol>) with <plotstyle>
  • using語法
    2:xtic(1) : 使用第二行資料與第一行資料作為xlabel作圖
    using ($0-0.2):($2+0.001):2 : 現在只有一維資料y(所以x使用$0表示label之x座標), $2是第二個column的資料座標, 2則是表示使用output.txt中的第二行資料作為資料來源。-0.2與+0.001則是座標的調整
reset //清除先前設定 set ylabel 'time(sec)' //設定y軸資訊 set style fill solid set title 'perfomance comparison with different num of threads' //設定圖片標題 set term png enhanced font 'Verdana,10' set output 'runtime.png' //設定輸出檔名 plot [:][:0.02]'output.txt' using 2:xtic(1) with histogram title '1 thread', \ '' using ($0-0.2):($2+0.001):2 with labels title '', \ '' using 3:xtic(1) with histogram title '2 thread' , \ '' using ($0-0.04):($3+0.0015):3 with labels title '', \ '' using 4:xtic(1) with histogram title '4 thread' , \ '' using ($0+0.01):($4+0.0025):4 with labels title'',\ '' using 5:xtic(1) with histogram title '8 thread' , \ '' using ($0+0.2):($5+0.0021):5 with labels title ' ', \ '' using 6:xtic(1) with histogram title '16 thread', \ '' using ($0+0.45):($6+0.003):6 with labels title ' ', \
Select a repo