Try   HackMD

2017q1 Homework4 (phonebook-concurrent)

contributed by <vtim9907>

開發環境

  • OS : Ubuntu 16.04.2 LTS
  • Kernel Version : 4.8.0-36-generic
  • Memory : 32 GB
  • CPU : Intel® Core™ i5-6600 Processor
    • cache :
      • L1i cache : 4*32 KB
      • L1d cache : 4*32 KB
      • L2 cache : 4*256 KB
      • L3 cache : 6144 KB
    • L1 cache imformation ( sudo dmidecode -t cache ) :
Handle 0x001E, DMI type 7, 19 bytes
Cache Information
	Socket Designation: L1 Cache
	Configuration: Enabled, Not Socketed, Level 1
	Operational Mode: Write Back
	Location: Internal
	Installed Size: 256 kB
	Maximum Size: 256 kB
	Supported SRAM Types:
		Synchronous
	Installed SRAM Type: Synchronous
	Speed: Unknown
	Error Correction Type: Parity
	System Type: Unified
	Associativity: 8-way Set-associative

教材研讀

觀賞 課程影片 和研讀 Toward Concurrency

  • 其中我覺得最有趣的是 lock-free
    • lock-free programming 簡單示意圖

其中上面 lock-free 連結的文章也提到，一般並不會期望整個程式都應用 lock-free 技術，而是應該仔細洞察眼前的案例，針對案例的特性去找出可以應用的地方下手改進。

原版程式碼分析

前置

瓶頸

pthread_join : 因為每個 thread 的執行時間不一，有的快有的慢，所以整體時間還是以最慢的為準，快的還是要等慢的。

問題

根據作業提供的分析，最後結論在於不知道為什麼 thread 的數量在超過 4 之後，執行時間就會增長不少。

研究前腦補想法 & 問題

  1. 我的 cpu 規格上寫著 " 執行緒數量： 4 "，這跟 kernel thread 有什麼關係？
  2. 如果硬體本身資源就小於工作量的需求，那麼 thread 開到超過適量個數之後，頂多也只是多個小工作輪流使用同一個 processor，對於加快整體工作的速度來說並沒有比較快。（如果是這樣的情況，用超多 thread 主要的目的變成是希望多個小工作同時運作，而不是加速整體大工作的速度。
  3. 到底如何確定很多個 thread 在跑的時候，是真的同時運作，還是只是輪流使用同個 processor？ 如果只是輪流使用同個 processor，那麼對加速工作執行速度真的有幫助嘛？ 還是說變成只是讓工作 " 近似 " 同時運作，但整體時間最快的時間很難再壓縮。
  4. 因為前面多個問題沒想清楚，我有點難想像做了 thread pool 之後會有多少效能提昇，或是說 thread pool 在這裡的功能就是控管 thread 運作的數量，避免使用過多的 thread 導致效能反而降低，但如果是這樣，以目前比較偏向寫死靜態的 phonebook 來說，作用應該不會太好，但是如果 phonebook 是動態的，有時可能需要新增大量資料，或是刪除大量資料，有時又停滯沒事，那麼 thread pool 的用處可能會比較顯著。

感覺作業系統要重念了…

  • 在 Operating Systems 裡看到了 kernel thread 和 processor 數量的關係：

    • a. 當 processors 數量大於 kernel threads 數量時，會造成一些未被 threads 對應到的 processors idle.
    • b. 當 processors 數量等於 kernel threads 數量時，所有的 kernel thread 都會對應到一個 processor ，但當 kernel thread 被 block 時，也會造成對應的 processor 閒置。
    • c. 當 processors 數量小於 kernel threads 數量時，每個 processor 都會對應到一個 kernel thread ，當 kernel thread 被 block 時，此 thread 會被 swap out ，並將其他已經準備好執行的 thread 對應到此 processor ，藉此提高 multiprocessor system 的效能。

這樣來看就稍微清楚一點，而 kernel thread 也是有 one-to-one, one-to-many, many-to-many 這些關係，一個 kernel thread 也是掌控一個或是多個 user thread ，若是多個，則多個 user thread 輪流執行。

  • 這麼多問題，查資料查到暈頭了還是沒前進多少，還是先實驗看看吧…

案例實驗分析

由於實在無法確定 thread 運作情況，以本案例來說，我也不確定 thread 更多的時候，效能到底移動多少，因為數據都是單筆資料，在每次執行都會浮動的數字來說，還是用大數來看比較好判斷！

改變 THREAD_NUM

  • 改變 THREAD_NUM 的值，每個做 4200 次，然後看結果

  • THREAD_NUM = 4

  • THREAD_NUM = 8

append 的時間整體來看，其實與 THREAD_NUM = 4 的時候差不多，但 findName 的時間卻提昇了兩倍！？

  • THREAD_NUM = 16

這次 append 的時間就提昇的比較明顯了，大約比上面兩種效能都差了 1/3 左右， 但是 findName 的時間卻又掉回來 0.002s 左右？ 我原本預期是當 thread 開到超過某個閥值之後，開越多效能就越慢，但是 findName 變慢又變快的狀況是怎樣還要思考一下…

嘗試看 System Monitor ，觀察 CPU 運作

  • 在上面的過程中，我另外看了 System Monitor ，觀察 CPU 運作情形，不過其實每次跑的情況都差不多，每顆 CPU 資源消耗的差不多，但 THREAD_NUM = 8 的時後，某次跑出現了滿特殊的情況：

  • 第一次跑

  • 第二次跑

  • 可以看到第一次跑的時候運算幾乎都集中在 CPU3 上，其他 CPU 相較之下就比較不活躍。
  • 但是第二次跑得時候，工作卻幾乎平分給四顆 CPU 上，可以看到四顆 CPU 的活躍程度差不多。

難道是 kernel thread 有可能都對應到同一顆 CPU!?

  • 必須確定 pthread_create 出來的 thread 是什麼東西！？

    • Native POSIX Thread Library

      • 這是一種在 Linux 環境底下實做 POSIX Threads 的實做方式。
      • 根據其內容敘述
      ​​​​​​​​NPTL is a so-called 1×1 threads library, in that threads created 
​​​​​​​​by the user (via the pthread_create() library function) are in 
​​​​​​​​1-1 correspondence with schedulable entities in the kernel 
​​​​​​​​(tasks, in the Linux case). This is the simplest possible 
​​​​​​​​threading implementation.
      • 從上面看來，就是 pthread_create 出來的 thread 就是 1-to-1 model 的形式。

這樣來看，上面詭異的例子有可能真的是因為 kernel thread 都對應到同一顆 cpu 嘛！？ 但是應該是全部的 CPU 去 swap in/out 全部的 kernel thread 吧？ 那怎麼會出現只有一顆 CPU 特別忙碌的狀況？ 目前還不確定原因，實驗作法錯誤有可能，但是因為什麼都沒改跑了好幾次，就只有特定那次發生這樣的狀況，雖然說跑出來的數據正常，但是跑得過程為何怪異就要再想想…

Last changed by 
 
vtim
<svg/onload=alert`{{8+9}}`>
0
452
Published on HackMD