Mar 29, 2016 課程紀錄

[2016q1 Week #6] [編輯共筆內容]

重要事項宣達

拾人牙慧

回顧 C 語言

假設我們有兩個****有號整數***: <stdint.h>

然後原本涉及到分支的陳述:

可更換為沒有分支的版本:

為什麼呢?一旦 b 右移 31 個 bit,在右移 `>>` 時在前面補上 sign bit ,所以移完會是 0xffff 也就是-1,故結果會是 `a -= -1`,即 `a++`,於是,原本為負數的值就變成 1 ,而原本正數的值就變成 0,又因為原本的行為是有條件的 a++,如此就是數值操作,沒有任何分支指令。

POSIX Thread

Condition variables must be declared with type pthread_cond_t, and must be initialized before they can be used. There are two ways to initialize a condition variable:

  1. Statically, when it is declared. For example: 
  1. Dynamically, with the pthread_cond_init() routine. The ID of the created condition variable is returned to the calling thread through the condition parameter. This method permits setting condition variable object attributes, attr.

使用案例與情境

Thread Pool

[ source ]

StackOverFlow 裡頭提及: Existing threadpool C implementation

裡面有提到幾個 C Thread Pool 的實作範例與可參考的文件

以 threadpool-mbrossard 作為第一個研究的版本,因為他一直有在維護。 而且作者就是 Existing threadpool C implementation 的發文者。

A simple C thread pool implementation

Currently, the implementation:

from wikipedia

Thread Pool 的資料結構

首先 Thread Pool 要有的東西就是 job 或者是 task 讓 Thread 知道他們要做什麼事情。

所以只要有一個資料結構紀錄要執行的 function pointer 與要傳遞的參數即可。 接下來就是 Thread Pool 本身,他必須存放所有的 Thread 與 Job Queue:

這邊使用一個 pthread_t 的 pointer 來紀錄所有的 Thread,簡單來說,就是一個 pthread_t 的 array,而 head, tail 就是紀錄 array 的 offset。 threadpool_task_t 也是一樣的原理,真是出乎意料的簡單。

ThreadPool 的建立與工作的執行

再來就是 Thread Pool 的建立,由於剛剛提到的他其實是使用一個 pthread array 與一個 job array 來存放所有的 thread 與 jobs。 因此需要在一開始的時候就決定 Thread Pool 與 Jobs 的最大數量。

而每個 Thread 要排入執行的 callback function 透過以下:

for(;;) 裡面,Thread 第一件要做的事情就是去搶奪 pool 的 lock,當搶到 lock 的 Thread 發現沒有工作可以做的時候, 就會執行 pthread_cond_wait 來等待通知。這時候 pool->lock 會被 Unlock,因此這時候其他 Thread 也可以進來這個區域。 所以在完全沒有工作的情況下,所有的 Thread 都會在這邊 waiting。

當 Thread 被透過 pthread_cond_signal 喚醒的時候,該 Thread 就會重新取得 pool->lock。 這時他就可以安心的取出 queue 中的 task,等待取出完畢之後,再 unlock 讓其他被喚醒的 Thread 也可以去取得 Task。

之後就是執行 task 中的 function pointer 做該做的工作。

ThreadPool 的 destory

destory 就更簡單了,只要使用 pthread_cond_broadcast 通知所有的 Thread 起來,由於 shoutdown 的確認會在執行工作之前。 所以該 thread 就會離開執行工作的迴圈,並且結束。

mbrossard 完整的 ThreadPool 原始碼

Lock-free Thread Pool

[ source ]

大多數 thread pool 實做都離不開 lock 的使用,如 pthread_mutex 結合 (condition variable) pthread_cond。一般來說,lock 的使用對於程式效能影響較大,雖然現有的 pthread_mutex 在 lock 的取得 (acquire) 與釋放,已在 Linux 核心和對應函式庫進行效能提昇,但我們仍會希望有不仰賴 lock 的 thread pool 的實做。

常見 thread pool 實做原理

如上圖所示,workqueue (工作佇列) 由 main thread (主執行緒) 和 worker thread 共享,main thread 將任務放進 workqueue,worker thread 從 workqueue 中取出任務執行。要注意到,共享 workqueue 的操作必須在 mutex 的保護下安全進行,main thread 將任務放進 workqueue 時,若偵測到目前待執行的工作數目小於 worker thread 總數,則要透過 condition variable 喚醒可能處於等待狀態的 worker thread。

lock-free 化 thread pool 實做原理

為解決 lock-free 所面臨的議題,我們一定要避免共享資源的競爭 (contention),因此將共享 workqueue 加以拆分成每 worker thread 一個 workqueue 的方式,如上圖。對於 main thread 放入工作和 worker thread 取出任務的競爭問題,可以採取 ring-buffer 的方式避免。在解決了lock 機制後,就只剩下 condition variable 的問題,condition variable 本質上就是提出來解決執行緒之間的通訊議題,不然為了追蹤特定變數,如之前提到的 "count" 變數,還得額外建立執行緒來追蹤。而 semaphore 作為一種通信方式,可以代替之,其大體開發模式為:

lock-free thread pool 實做說明

程式碼請見: https://github.com/xhjcehust/LFTPool

在 lock-free thread pool 的實做裡頭,有別於常見 thread pool 之處,在於 semaphore 與 condition variable 、排程演算法、增加或減少執行緒數目後的 task migration,另一點則是引入 ring-buffer,後者參考了 Linux 核心中的 kfifo 實做。

(1) semaphore 與 condition variable 

semaphore 與 condition variable 的區別,主要在於 condition variable 的喚醒 (signal),對於接收端執行緒而言可以忽略,而在未設定 semaphore 處理函式的情況下,semaphore 的接收會導致接收執行緒,甚至是整個程式的終止。因此,需要在 thread pool 產生執行緒前,事先指定 semaphore 處理函式,如此一來,新建立的執行緒會繼承這個 semaphore 處理函式。多執行緒中,semaphore 的訊號 (UNIX signal; 本質上非同步) 傳送,主要採用 `pthread_kill`,為避免使用其他 semaphore ,本程式中使用了SIGUSR1。

(2) 任務排程演算法

常見 thread pool 實做的任務排程,主要透過作業系統的 thread scheduler 來達成。考慮到 load-balancing,main thread 放入任務時應採取合適的任務排程演算法,將任務放入對應的 worker thread 隊列,本程式目前已實做 Round-Robin 和 Least-Load 演算法。Round-Robin 即輪詢式地分配工作,Least-Load 即選擇目前具有最少工作的 worker thread 放入。

(3) Task migration

在執行緒的動態增加和減少的過程中,同樣基於 load-balancing 的考量,涉及到現有 task 的遷移 (migration) 問題。load-balancing 演算法主要基於平均工作量的想法,即統計目前時刻的總任務數目,均分至每一個執行緒,求出每個工作者執行緒應該增加或減少的工作數目,然後從頭至尾遍歷,需要移出工作的執行緒與需要移入工作的執行緒執行 task migration,相互抵消。最後若還有多出來的工作,再依次分配。

遷入 (migreate IN) 工作不存在競態,因為加入工作始終由 main thread 完成,而遷出 (migrate OUT) 工作則存在競態,因為在遷出工作的同時,worker thread 可能在同時執行任務。所以需要採用 atomic operation (原子操作) 加以修正,其主要思想就是預先擷取 (prefetch) 的技巧,大致實做程式碼如下:

Atomic 是種同步機制,不須透過 explicit lock (如 mutex),也能確保變數之間的同步。Linux 核心提供了對應的型態 `atomic_t`。而 gcc 也提供了內建的函式 (built-in functions),專門處理 atomics,如下:

上面的 "type" 可以是 int8 .. int64。

最常用到的就是「加」和「減」的操作,使用如下:

這是種輕量級的同步機制,若只是對一個變數去做同步,實在不需要透過 mutex。在真實硬體環境中,atomics 的效能會比 `pthread_mutex_t` 好許多。 

atomics 通常會伴隨著探討 memory barrier,這是因為編譯器進行最佳化時,往往會為了最佳化去變更指令的順序,但在特定的狀況下,往往會帶來後遺症,為了避免衝擊,gcc 也提供以下內建函式來處理 memory barrier:

在執行緒的動態減少後,原先執行緒上未能執行完的任務,只需要由 main thread 再次根據任務排程演算法重新分配至其他存活的 worker thread 隊列中即可,不存在上述問題,當然,此時可以同時執行 load-balancing 演算法加以最佳化。

(4) ring-buffer

ring-buffer 實做主要參考了 Linux 核心中 kfifo 的實做,如下圖所示:

環狀佇列長度為 2 的整數次方,out 和 in 下標一直遞增至越界後迴轉,其類型為 `unsigned int`,即 out 指標一直追趕 in 指標,out 和 in 映射至 FiFo 的對應下標處,其間的元素即為隊列元素。

ARM 處理器概況

(請利用四月第一週預習)

ARM 與 MIPS

 

ARM Processor Architecture

ARMv8 中文翻譯可見此:http://wiki.csie.ncku.edu.tw/embedded/ARMv8

A64 is a new 32-bit fixed length instruction set to support the AArch64  execution state. The following is a summary of the A64 ISA features.  

ARM, generically known as A32, is a fixed-length (32-bit) instruction  set. It is the base 32-bit ISA used in the ARMv4T, ARMv5TEJ and  ARMv6 architectures.  In these architectures it is used in applications  requiring high performance, or for handling hardware exceptions such as  interrupts and processor start-up.

The ARM ISA is also supported in the Cortex™-A and Cortex-R  profiles of the Cortex architecture for performance critical  applications, and for legacy code.  Most of its functionality is  subsumed into the Thumb instruction set with the introduction of Thumb-2  technology. Thumb (T32) benefits from improved code density. 

ARM instructions are 32-bits wide, and are aligned on 4-byte boundaries. 

Most ARM instructions can be "conditionalized" to only execute when  previous instructions have set a particular condition code. This means  that instructions only have their normal effect on the programmers’  model operation, memory and coprocessors if the N, Z, C and V flags in  the Application Program Status Register satisfy a condition specified in  the instruction. If the flags do not satisfy this condition, the  instruction acts as a NOP, that is, execution advances to the next  instruction as normal, including any relevant checks for exceptions  being taken, but has no other effect.  This conditionalization of  instructions allows small sections of if- and while-statements to be  encoded without the use of branch instructions.  

==>

A64’s Key differences from A32 are: 

==> 64-bit data model

ARM Architecture

ARM 是在全球中被廣泛使用的 processor cores,像是 PDA、手機、多媒體播放器、數位電視、相機等等。ARM processors 有許多 family,如 ARM7、 ARM9、 ARM11、ARMv7,同一個 family 的設計使用相似的設計原則及同一個common instruction set。他的設計哲學是用有限的硬體( 有限的 memory 和 physical size restrictions )資源達到 high code density,除此之外,還

ARM 的命名方式 (Cortex系列以前) - ARMxyzTDMIEJFS

(在 ARM Cortex-A/R/M之前的 "ARM Classic")

ps : TDMI 這四項基本功能成了任何新產品的標準配備,於是就不再使用這4個後綴。但是新的後綴不斷加入,包括定義存儲器界面的,定義高速快取的,以及定義"緊耦合存儲器(TCM)"的,於是形成了新一套命名法,這套命名法一直使用至今。比如ARM1176JZF-S,它實際上預設就支持TDMI功能,除此之外還支持JZF。

這套命名機制在 ARM Cortex-A/R/M 之後,徹底棄置。以 MMU 來說,ARM Cortex-A 系列都有 MMU,而 Cortex-M0/M0+/M3/M4 均缺乏 MMU,僅有選擇性的 MPU。Cortex-M7 開始提供 cache 和 TCM

ARM Classic

(在 ARM Cortex 系列出現之前)

ARM 採用 RISC

ARM architecture 從 Berkeley RISC design合併了幾個特點,但也有些並無採用。

  • Features used
  • Features rejected
  • ARM 的架構

    註: MAC = Multiply–accumulate operation

    ARM Register

    以下是ARM的 register,在User/System Mode時,可以使用r0~r15,其中r13為stack pointer,r14為link register,r15為program counter

    Current Program Status Register(CPSR) : 在user-level時,用於存取condition code bits

    溢位複習:

  • 1、輸入的數是無符號整數,我們通過觀察C判斷是否溢出
  • a) C=1

    <i>如果是加法操作,結果不正確,結果溢出

    <ii>如果是減法操作,結果正確,結果未溢出

    b) C=0

    <i>如果是加法操作,結果正確,結果未溢出

    <ii>如果是減法操作,結果不正確,結果未溢出。在這種情況下,結果是負數。然而,在無符號整數世界裡,負數不存在,我們認識這樣的操作是非法的。當然,如果認為答案是以有符號整數補碼的形式出現,則結果正確。

  • 2、輸入的數是有符號整數,我們通過觀察V判斷是否溢出
  • a) V=1,結果不正確,結果溢出

    b) V=0,結果正確,結果未溢出

    通用暫存器有6種 data types ( signed / unsigned) ( word /Half word/ byte),而在所有ARM的運算為32-bit,比較小的資料型態只有在資料傳送的運算中被支援。

    Program Counter ( PC ) 是儲存要被執行的位址,而所有指令皆為 32-bit wide 且 word aligned

    在 ARM 架構中支援了 ( 7+1  )種模式,如圖:

    Instruction sets

    裡面有 ARM / Thumb / Jazelle ,下圖為簡單介紹:

    (實際上 ARM 的 extension 遠比以下列出的多)

    Pipeline

    在執行時, PC 是 8 bytes ahead,也就是說 Pipeline 準備要做 Execute級( 位址是 0x8000)時,要讀取的下一個位置是 PC + 8 的位置(從範例中可清楚看見,即 DCD 指令的位址 0x8008)

    他有以下幾點特點:

    為何ARM的 `PC` 是指向下兩條指令?

    https://commons.wikimedia.org/wiki/File:Pipeline_MIPS.png

    Interrupts

    當發生 exception 或 interrupt 時,會觸發 Interrupt handler,此時,他會尋找 vector table 去做中斷時所要處理的 routine.

    下圖為中斷定義及其跳躍的起始位址:

    在 user-mode program 中,可以看到 15 個 32-bit general purpose registers (R0-R14), program counter (PC) 及 CPSR,在指令集中有定義一些指令可以改變 state。

    在開始深入探討前,先來看看他的 Memory system吧~

    Memory system

    剛剛有提到 Little Endian,他其實是 Byte ordering 的其中一種方式,endian指的是當物理上的最小單元比邏輯上的最小單元還要更小時,邏輯單元對映到物理單元的排佈關係。舉例來說:

    如果你在文件上看到一個雙字組的data,Ex: `long MyData=0x12345678`,要寫到從0x0000開始的記憶體位址時。

    1. 如果是Big Endian的系統: (TCP/IP)
    1. 如果是Little Endian的系統:

    比較的結果就是這樣:

    big-endian little-endian
    0x0000 0x12 0x78
    0x0001 0x34 0x56
    0x0002 0x56 0x34
    0x0003 0x78 0x12

    Features of ARM instruction set

    Instruction set

    可分成三大項:

    Data processing

    資料處理指令包含對資料做 移動、算數、邏輯、比較、乘法 的指令,且大部分的 data processing instructions 可以對一個 operand 做 shift,如圖:

  • Arithmetic operations:
  • Bit-wise logical operations:
  • Register movement operations:
  • Comparison operations:
  • 只設定在CPSR的 condition code bits(N, Z, C and V)

  • Immediate operands:
  • Reference: https://sourceware.org/ml/binutils/2014-02/msg00157.html

    Shifted register operands:

    舉例來說:

    位移 (shift) 主要分兩種:

    簡單來說,邏輯移位無論左移右移,一律都是把多出來的位數填零。算術運算左移跟邏輯移位一樣填零,右移需要考慮到 singed 的屬性,假若最高位是 1,則填補1,反之若最高位是 0,則填補0。

    範例:

    注意: ARM Toolchain (包含 arm-none-eabi/linux-gnueabi) 預設將 "int" 視為 "unsigned"

     

  • Condition flags
  • If S is specified, these instructions update the condition code bits 

    Ex:

  • Multiplies:
  • Encoding data processing instructions
  • 這裡可以看第 25-bit(#) 決定 operand 2 是以何種格式,如果 # = 1 就如圖下只有 1 種對應格式,如果 # = 0就需要再比對位置在第四個bit ( 決定2種格式 )

    Flow Control 

    決定哪一條指令將被執行

    B branch pc = label pc-relative offset within 32MB
    BL branch with link pc = label
    BX branch exchange pc = Rm & 0xfffffffe, T = Rm & 1
    BLX branch exchange with link pc = label, T = 1

    Mnemonic Name Condition flags
    EQ equal Z
    NE not equal z
    CS HS carry set/unsigned higher or the same C
    CC LO carry clear/unsigned lower c
    MI minus/negative N
    PL plus/positive or zero n
    VS overflow V
    VC no overflow v
    HI unsigned higer zC
    LS unsigned lower or same Z or c
    GE signed greater than or equal NV or nv
    LT signed less than Nv or nV
    GT signed greater than NzV or nzv
    LE signed less than or equal Z or Nv or nV
    AL always (unconditional) ingnored

    Branch Interpretation Normal uses
    B BAL Unconditional Always take this branch
    BEQ Equal Comparison equal or zero result
    BNE Not equal Comparison not eaual or non-zero result
    BPL Plus Result positive or zero
    BMI Minus Result minus or zero
    BLO Lower Unsigned comparison gave lower
    BHS or the same Unsigned comparison gave higher or same
    BVC Overflow clear Signed integer operation; no overflow occured
    BVS Overflow set Signed integer operation; overflow occured
    BGT Greater than Signed integer comparison gave greater than
    BGE Greater than or equal Signed integer comparison gave greater than or equal
    BLT Less than Signed integer comparison gave less than
    BLE Less or equal Signed integer comparison gave less than or equal
    BHI Higher Unsigned comparison gave higher
    BLS Lower or the same Unsigned comparison gave lower or same

    Data transfer instructions

    data processing 的 mov 指令是暫存器間互相傳送資料,而 data transfer instructions 是暫存器與 memory 間互相傳遞資料,而 data transfer instructions 有三種基本形式

    1. Single register load/store ,也就是對單一暫存器做 load/store
    2. Multiple register load/store,可以對多個暫存器做 load/store
    3. Single register swap: SWP(B), atomic instruction for semaphore
  • Syntax:
  • 2

    LDR load word into a register Rd <-- mem32[address]
    STR save byte or word from a register Rd --> mem32[address]
    LDRB load byte into a register Rd <-- mem8[address]
    STRB save byte from a register Rd --> mem8[address]
    LDRH load halfword into a register Rd <-- mem16[address]
    STRH save halfword into a register Rd --> mem16[address]
    LDRSB load signed byte into a register Rd <-- SignExtend
    LDRSH load signed halfword into a register Rd <-- SignExtend

    ps. 沒有 STRSB/STRSH 是因為 STRB/STRH 儲存 signed/unsigned 到記憶體位置( 存進去就不管他是有號無號,讀出來才要判別)

    Memory 定址可以透過暫存器和 offset,例:

    他有三種 Addressing modes

    Index method Data Base address register Example
    Preindex with writeback mem[ base + offset ] base + offset LDR r0,[r1, #4]!
    Preindex mem[ base + offset ] not updated LDR r0, [r1, #4]
    Postindex mem[ base ] base + offset LDR r0, [r1], #4
  • 圖解 Addressing modes
  • 以上是有 offset 的三種 addressing modes,接下來來看看 Register 的 addressing modes

    ps.有一個 pseudo instruction ADR 可以 load and address 到一個暫存器裡

  • Multiple register load/store
  • 意思就是一次可以存取很多個暫存器的值

    簡單的範例:

  • Syntax:
  • 用上表有點難看出變化,以下用圖來表示

    其中 R1 = 10, R2 = 20, R3 = 30,更新後的 R0 = 0x01c

    從這裡可以看到依序從最低位開始存,存完才將R0 + 4 ,最後,當存完R3的值之後,R0更新成 0x01c,因為上面指令有 `!` ,所以將最後值存在 R0中

    ps.: 如果沒有`!` ,則最後R0 = 0x010,後面的範例也是如此

    其中 R1 = 20, R2 = 30, R3 = 40,更新後的 R0 = 0x01c

    從這裡可以看到先將R0 + 4 後才開始存,然後依序往上加 ,最後,當R0更新成 0x01c也存完R3的值之後,因為上面指令有 `!` ,所以將最後值存在 R0中

    其中 R1 = 40, R2 = 50, R3 = 60,更新後的 R0 = 0x018

    從這裡可以看到依序從最位開始存,存完才將R0 - 4 ,最後,當存完R1的值之後,R0更新成 0x018,因為上面指令有 `!` ,所以將最後值存在 R0中

    其中 R1 = 30, R2 = 40, R3 = 50,更新後的 R0 = 0x018

    從這裡可以看到先將R0 - 4 後才開始存 ,最後,當R0更新成 0x018也存完R1的值之後,因為上面指令有 `!` ,所以將最後值存在 R0中

  • Multiple load/store registers 的應用
  • mode POP =LDM PUSH =STM
    Full ascending (FA) LDMFA LDMDA STMFA STMIB
    Full descending (FD) LDMFD LDMIA STMFD STMDB
    Empty ascending (EA) LDMEA LDMDB STMEA STMIA
    Empty descending (ED) LDMED LDMIB STMED STMDA