HackMD
2016q3 Homework2 (phonebook-concurrent)
contributed by <HaoTse>
閱讀筆記
Concurrency vs. Parallelism
Concurrency (並行)
- 單一處理器處理兩個或兩個以上的問題
- 分割的工作是交錯執行的
- 用於當只有少量的 CPU 資源和許多工作
- 因為 CPU 的可操作性上升，所以 Concurrency 愈來愈熱門了
Parallelism (並行)
- 多個處理器處理一個問題
- 將一個問題分割成數個相似的大部份
Thread vs. Coroutines
Thread
- 作業系統會交錯執行 task，並根據下列 scheduling algorithm 的不同決定優先權
Coroutines (協同程序、協程)
- 由 programmer 控制，與 kernel 無關
- wiki
POSIX Threads
Getting Started With POSIX Threads
pthread_t a_thread;
pthread_attr_t a_thread_attribute;
void thread_function(void *argument);
char *some_argument;
pthread_create( &a_thread, a_thread_attribute, (void *)&thread_function,
(void *) &some_argument);
exit的陷阱
在任何一個 thread （不論 parent or child）裡呼叫exit都將導致 process 結束，而所有的 thread 也跟著一起結束了。所以如果要結束一個 thread ，我們必須使用pthread_exit這個函數。- race condition
當許多 process 同時對同一個資料進行存取和操作，會依賴於不受控制的事件的出現順序或者出現時機而導致結果有所不同。 sleep的陷阱
當 thread 呼叫sleep時，講導致整個 process 停下來。這表示所有屬於這個 process 的 thread 也將跟著停頓下來。另外一個適用的函數是pthread_delay_np（np 表示 not portable）。
_np表示 not portable，網路上找資料容易找到錯誤的材料，所以要回歸第一手資料。權威性的資料可參見 Open Group: Threads jserv
例如要讓程式停2秒可以使用下列方法
struct timespec delay;
delay.tv_sec = 2;
delay.tv_nsec = 0;
pthread_delay_np(&delay);
- 同步問題
- mutex：一組用來控制共享資源存取的一組函數
pthread_mutex_init(&mutex, pthread_mutexattr_default)初始 mutex
pthread_mutex_destroy(&mutex)釋放 mutex - condition variable
將 mutex 的功能加以延伸，能夠做到讓某一個 thread 能暫停，並等待另一個 thread 的信號（signal）。當信號來了，thread 就醒過來，然後將相關的 mutex lock 起來。
- mutex：一組用來控制共享資源存取的一組函數
Thread Pool
Thread 可能造成的缺陷
- 建立太多執行緒，會浪費一定資源，並且有些執行緒未被充份使用
- 銷毀太多執行緒，會導致之後浪費時間再次創建它們
- 建立執行緒太慢，導致效能變差
- 銷毀執行緒太慢，導致其它執行緒沒有資源
Thread Pool 可以解決這上述問題，它可以達到下列工作
- 管控 Thread 的產生與回收
- 分發 Thread 處理 request
- 處理 request 的 queue
C Thread Pool 實作範例
Lock-free Thread Pool
Code Refactoring
- 將
main.c中 opt 版本需引入的標頭檔集中在main.c的前面方便閱讀
//include the needed header file and define marco when OPT
#if defined(OPT)
#include "file.c"
#include "debug.h"
#include <fcntl.h>
#define ALIGN_FILE "align.txt"
#ifndef THREAD_NUM
#define THREAD_NUM 4
#endif
#endif
- 改變
phonebook_opt.c(append)中的 for loop 為 while loop，因為 for loop 中條件敘述過長，不易閱讀
char *i = app->ptr;
while(i < app->eptr) {
app->pLast->pNext = j;
app->pLast = app->pLast->pNext;
app->pLast->lastName = i;
dprintf("thread %d append string = %s\n",
app->tid, app->pLast->lastName);
app->pLast->pNext = NULL;
i += MAX_LAST_NAME_SIZE * app->nthread;
j += app->nthread;
count++;
}
- 解決
warning: ‘CPU_time’ defined but not used [-Wunused-function]
將phonebook_opt.c和phonebook_opt.h中的static double diff_in_second(struct timespec t1, struct timespec t2)前後加入#ifdef PROFILE確認是否開啟 PROFILE 模式。
如果要使用 DEBUG 需要使用$ make DEBUG=1 PROFILE=1
- 更改
main.c中的第105行起的 for loop 為下列的樣子
pHead = app[0]->pHead;
dprintf("Connect %d head string %s %p\n", 0, app[0]->pHead->pNext->lastName, app[0]->ptr);
etmp = app[0]->pLast;
for (int i = 1; i < THREAD_NUM; i++) {
etmp->pNext = app[i]->pHead;
dprintf("Connect %d head string %s %p\n", i, app[i]->pHead->pNext->lastName, app[i]->ptr);
etmp = app[i]->pLast;
dprintf("Connect %d tail string %s %p\n", i, app[i]->pLast->lastName, app[i]->ptr);
dprintf("round %d\n", i);
}
做了兩個主要的修改
1.將 i = 0 的情況移出 for loop 減少 branch 的數量
2.更正原本程式的錯誤，原本為連接 pHead->pNext ，但應連接 pHead 才對
效能分析
原始版本
Thread Pool
使用前面提到的 threadpool-mbrossard 實作
將 main.c 中的 thraed 改變為以下的操作方式
threadpool_t *pool = threadpool_create(THREAD_NUM, POOL_SIZE, 0);
for(int i = 0; i < THREAD_NUM; i++) {
app[i] = new_append_arg(map + MAX_LAST_NAME_SIZE * i, map + fs, i, THREAD_NUM, entry_pool + i);
threadpool_add(pool, &append, (void *)app[i], 0);
}
threadpool_destroy(pool, 0);
不過這裡執行時產生了 Segmentation fault，研究了一陣子沒有結論，在TempoJiJi 的筆記 中找到了答案，將 threadpool_destroy(pool, 0) 改成 threadpool_destroy(pool, 1); 就成功了。
