contributed by < linD026
>
linux2021
jobqueue_t
tpool_apply
把 task
放入 jobqueue_t
。thread pool
的執行緒會利用 jobqueue_fetch
從 jobqueue_t
中得到需要執行的 task
。queue
是空了的時候,執行緒會等待。
pthread_cond_wait(&jobqueue->cond_nonempty, &jobqueue->rwlock);
rwlock
。threadtask_t
jobqueue_fetch
函式中從 jobqueue_t
接收的 task
結構func
:
void *ret_value = task->func(task->arg);
__tpool_future
threadtask_t
結構所包住func
回傳結果的結構
tpool_future_get
確認執行時間是否超過限制以及得到結果
pthread_cond_timedwait
回傳的數值來確認future->flag |= __FUTURE_TIMEOUT;
__threadpool
__future_flags
__FUTURE_TIMEOUT
& __FUTURE_DESTROYED
為 1__FUTURE_FINISHED
& __FUTURE_DESTROYED
為 0tpool_apply
tpool_future_get
pthread_cond_timedwait
來檢測 task
是否完成。seconds
後,則會回傳直至 status
。status
為 ETIMEDOUT
則會使 task
的 flag
設為 __FUTURE_TIMEOUT
並且不等 task
結束回傳 NULL
。CLOCK_MONOTONIC
為:
CLOCK_MONOTONIC
Clock that cannot be set and represents monotonic time since—as described by POSIX—"some unspecified point in the past". On Linux, that point corresponds to the number of seconds that the system has been running since it was booted.
CLOCK_REALTIME
來取得現在時間。jobqueue_fetch
以目前 tpool_future_get
對超出時間限制的 task
操作仍然是等到 task
結束後才處理。
因此如果 task
是花超長時間才會結束,在那段時間內會有一個 thread 被浪費。
所以利用 thread_cancel
來停止,隨後重新運作。
tpool_future_get
裡看到目前操作的執行緒為何,先在 struct __tpool_future
裡增加當前 thread 的 pid
。
jobqueue_fetch
裡利用 pthread_setcanceltype
設定如果遇到 cancellation request 時可以立即 cancel
(但系統不一定保證)
A thread's cancellation type, determined by pthread_setcanceltype(3), may be either asynchronous or deferred (the default for new threads). Asynchronous cancelability means that the thread can be canceled at any time (usually immediately, but the system does not guarantee this).
要設定能夠在 task 過長時 cancel 的狀態,那麼下面設定執行緒 state 的函式須刪除。
不需要設定 PTHREAD_CANCEL_ENABLE
的狀態,是因為執行緒的初始狀態已經是如此了。
pthread_setcancelstate
The pthread_setcancelstate() sets the cancelability state of the calling thread to the value given in state. The previous cancelability state of the thread is returned in the buffer pointed to by oldstate. The state argument must have one of the following values:
PTHREAD_CANCEL_ENABLE
The thread is cancelable. This is the default cancelability state in all new threads, including the initial thread. The thread's cancelability type determines when a cancelable thread will respond to a cancellation request.
PTHREAD_CANCEL_DISABLE
The thread is not cancelable. If a cancellation request is received, it is blocked until cancelability is enabled.pthread_setcanceltype
The pthread_setcanceltype() sets the cancelability type of the calling thread to the value given in type. The previous cancelability type of the thread is returned in the buffer pointed to by oldtype. The type argument must have one of the following values:
PTHREAD_CANCEL_DEFERRED
A cancellation request is deferred until the thread next calls a function that is a cancellation point (see pthreads(7)). This is the default cancelability type in all new threads, including the initial thread.
PTHREAD_CANCEL_ASYNCHRONOUS
The thread can be canceled at any time. (Typically, it will be canceled immediately upon receiving a cancellation request, but the system doesn't guarantee this.)
tpool_future_get
如果超出時間會利用之前在 future
所紀錄的 pid
以及 pthread_cancel
發送 cancellation request 。
pid
來尋找 pool
裡被 cancel
的 thread ,之後重新 create 。thread_cancel
時 handler 對 task 的作處理
設定八個 task 並且執行下列 dummy
函式,時間限制為 1 秒。
而因 dummy
有 sleep(10);
函式因此會一定會被 cancel 。
如果以 terminal 裡的 time
來檢測,可以看出確實有在此情況省了很多時間。
可以看出兩者記憶體使用率相差不大,並且 ./rigin
也就是原先的方式甚至多出了 0.3 KB
。
threadtask_t
,之後如 pthread_cleanup_push(__task_cleanup, task);
一樣處理即可。task 設定回原先算圓周率的函式,並且 blocking wait
。
可以看出其實時間差距不會很大,但在 instructions 上卻有 20,0000 左右的明顯差距。
不能只看時間差,還要觀察 CPU 使用率和特定指令的行為
關於 queue 的效率,我找到一篇論文剛好有研究到 cache friendly 和 lock-free :
A lock-free cache-friendly software queue buffer for decoupled software pipelining
// TODO 仔細研讀
Reference
要從 github 下載來測試,需要先處理好 lfqueue 才可正常執行。
atomic_threadpool
裡執行緒拿取 task 的 at_thpool_worker
看出。
at_thpool_worker
對於等待新的 task 進來的處理是以用每 1 ms sleep 的方式。pthread_cond_wait
以及 pthread_cond_broadcast
方式。tpool
的最高峰卻可達 115.8 KB ,而 atomic_threadpool
只有 40.8 KB 。
tpool
記憶體如此之高,是因為除了 queue 以及 thread 所使用到的 threadtask_t
,在每次分配任務時也同時會分配 __tpool_future
物件讓 thread 回傳 task 的結果。tpool
回傳的 future 作適當處理後,記憶體使用量的高峰值降到 6.0 KB 。head
和 tail
會指向一個節點 base
,root_free
和 move_free
也會指向一個節點 free_base
。__lfq_recycle_free
來判斷。__lfq_recycle_free
value
的節點釋放掉之前的前置動作。move_free
的鍊結串列。
root_free
與 move_free
是指向同一物件,因此在之後操作時,兩個指標都會在同一個鍊結串列上。while
迴圈需要釋放的節點 freenode
一定會放入至鍊結串列裡。move_free
一定會指向最後連結串列的最後一個節點。__lfq_check_free
root_free
指標指向的節點開始釋放,直到遇到 movefree 所指向的節點,或是用於釋放的 rtfree
指標指向 NULL 。儘管 lock-free 在一般認知上可能會比有 lock 的效率還要好。
但為了避免使用 lock 進而完全採用 atomic 操作,有可能為了符合要求在機制上作改變,使得某些操作的效能反而降低了。
譬如,沒辦法完全釋放掉已經不需要的記憶體、利用迴圈以及諸多 if 和 CAS 來確保資料的正確性等。
我參考了 atomic_threadpool 裡 lfqueue 的物件操作以及資源管理。
原先 queue 的結構改成 head
會指向一個已被提取過的節點來當作 base
。
queue head
以及 tail
的初始化因此改成指向一個預先配置的無用 task 來當作 base
。
這樣作的目的是在於保證多執行緒下,以 atomic 進行多次 push 和 pop 操作後,head 一定會在 linked list 的頭端,反之亦然。
_Atomic(threadtask_t *)
限制每個執行緒對 queue 頭尾兩端的操作。
base
後,以 base->next
作為 task 。
base
亦即 queue head 端。
base
則會經由 jobqueue_free_list_through_and_clean
push 到 free_list
上。對於被放到 free_list 上的 task ,有可能把它放到其中與擁有它的是不同執行緒,因此也有可能正好還在執行,所以不能夠直接釋放它。
對於這方面的處理,我設計了兩個函式分別是 jobqueue_free_list_through_and_clean
以及 jobqueue_free_list_clean
。
jobqueue_free_list_through_and_clean
主要是處理 queue task 被從 base
上換下來,並且放入至 free_list
這個 linked list 上。jobqueue_free_list_clean
則是真正處理資源釋放的函式。它會在釋放前對 task 的狀態作一些判斷來確保 task 是完成的狀態。
free_list
的節點超出 water_mark
時,會進入 free_mode
的 critical section ,以確保每次進行釋放時只有一個執行緒會操作。free_mode
後,不會馬上進行釋放。但會先利用 tail_stop
對 free_list
上鎖,以防止有新的 task 干擾釋放資源的操作。free_list_adding
的狀態來判斷還有多少 task 沒完成。free_list
時會增加 free_list_adding
,而當 task 執行結束後呼叫 jobqueue_free_list_clean
確認 water_mark
甚至是進入 free_mode
前會減少 free_list_adding
。
free_list_adding
的操作是替換並放入增加,執行結束減少,因此可以確定當其數值為零的時候, free_list
的任務一定都是做完的。一樣以最一開始的 bpp 作為檢測目標。
可以看到兩者的最高記憶體使用量不會相差太多,分別是 15.4 KB 和 15.8 KB 。
但從圖表上可以輕易的看出,因為 atomic 版本在對資源的釋放方式,導致在執行時期都會有一定程度的沒有再使用資源殘留。
當然這取決於 task 的執行時間、 water_mark
的值為多少。
如果 water_mark
設太小會對影響放入 free_list
的操作效率,太大則會有過多的無用資源殘留。
在經過更改 jobqueue
以及 trash task 的操作後,在 cache-misses
、 instructions
以及使用時間都略優於原版。
可得知,確實有因為 atomic 讓各個執行緒的操作靈活度變大,使得 scalability 提升。
雖然也因為沒有了 mutex
的 cond_wait
系統層級對於排程上的處理,在實做 critical section 或是取值都需要進行 busy wait 或類似的操作使得 cycles
提高。
但整體而言,效率上還是有所提升的。
關於上述,後來在嘗試對執行緒數量進行效能分析時發現 memory leak 等記憶體問題。
原因有幾項:
task = base->next;
產生錯誤。
int tpool_join(struct __threadpool *pool)
裡 tpool_apply(pool, NULL, NULL);
是使執行緒結束的函式,但仍然會 allocate memory ,這在上述會導致 memory leak 情況。並且還有其他相關記憶體 bug ,在此不再贅述。
在試過 1 到 100 個執行緒測試 bpp 函式後,發現並不是越多執行緒效率就會提昇。
下圖可以看到,在過了約莫 5 執行緒數量後,atomic 版本的花費時間快速上升,約略到 20 個執行緒後才緩和。
而且可以得知, atomic 版本在執行緒 20 以下的時間花費是低於 normal 版本的。但在這之上卻是相似甚至在 70 以上是高於 normal 版本。
這主要的差異差別,在於有多少執行緒競爭 pop task 的執行權,並且也因為 free_list 釋放記憶體的機制也與前者有關(執行緒 A 進入 free_mode 進行釋放前,還須等待已進入 list_adding 領域的執行緒完成任務)。
之後,也各自對每個數量的執行緒進行分析與比較(忘記更改 X 軸標注,X軸為次數):
比較讓人難以理解的是,為何執行緒數量個別比較在數量越高的時候,atomic 以及 noraml 的效能高低是顛倒於整體數量測試的。
後來發現是檢測方式的落差而導致,若以下列更改過後的函式測量個別數值則會符合執行結果:
在此也可看到當執行緒數量來到 100 的時候, atomic 與 nomral 版本差異不會很大。
但在 4 到 16 區間,atomic 的時間成本較低。
原始程式碼: GitHub - linux2021_homework_quiz4_threadpool_pi
測試:
git clone https://github.com/linD026/linux2021_homework_quiz4_threadpool_pi.git
到 main.c 裡的 main 函式更改執行函式分別是
terminal: cost_time current_time
time_check(__benchmark(thread_num));
benchmark(thread_num);
執行緒數量整體測試
的輸出格式相同。
benchmark_split(int thread_pool_size, int times)
之後下 make
進行編譯,make test
執行 1000 次,make one
執行一次。
也可以利用 make massif
產生記憶體使用量圖表或 make perf
CPU 使用率。