Linux kernel : 從 spinlock 到 atomic 到 Ameba
收錄在 AIoT Ameba 2020 - Just for Fun
--
緣由:
當我們對一個變數做計算時, CPU 通常的動作是:
(1) 從 memory 將變數值讀到暫存器
(2) CPU 通過暫存器做計算
(3) 將值寫回 memory
這也就是所謂的 read - modify - write 的動作
但這若在多工環境下, 可能會有問題, 例如: github-atomic1
我們做兩個 thread, 一個對 sum 加 1, 一個對 sum 減 1, 兩個都做三次, sum 初始值為 0.
正常來說最後 sum 值應該還是 0.
我們故意在計算完後, 呼叫 schedule() 強迫切換 thread,
可以發現, 這樣執行起來, sum 的值並非預期. 最後變成了 -2, 而非 0
[90334.635512] hello_init: pid=14949
[90334.635699] hello_init: pid=14949, before sum=0
[90334.635714] work_handler1: pid=12886, sum=1
[90334.635717] work_handler1: pid=12886, sum=2
[90334.635719] work_handler2: pid=13336, sum=0
[90334.635722] work_handler1: pid=12886, sum=1
[90334.635724] work_handler2: pid=13336, sum=-1
[90334.635727] work_handler2: pid=13336, sum=-2
[90334.635773] hello_init: pid=14949, after sum=-2
1. interrupt disable
我們用在 MCU 常用的手法, 把 interrupt 關閉看看 - github-atomic2
可以使用 raw_local_irq_save() / raw_local_irq_restore()
2. UP v.s SMP
Linux 上的 UP 指的是 uni-processor 單個 CPU,
相對於 SMP - symmetric multi-processors 多個 CPU 而言.
上述 禁制中斷 這方式, 在多核的 cpu 上會有問題 (SMP)
這是因為我們雖然在該 CPU 上禁制了 interrupt, 該 cpu不會執行別的 thread,
但其他 CPU 仍可執行
所以如果我們把次數三次放大到 十萬次, 來增加它發生的機率,
可以發現執行結果 sum 不是 0
[104815.844974] hello_init: pid=19042, before sum=0
[104815.850770] hello_init: pid=19042, after sum=-20814
3. spin_lock v.s. spin_lock_irqsave()
差別在於 spin_lock_irqsave() 會禁制中斷,
這問題發生在, 如果這 lock 會在 中斷函式 中使用的話,
有可能當 thread 執行 spin_lock 時, 中斷來臨, 跳到中斷函式也執行 spin_lock
這樣就會變成雙層請求死鎖
因為我們這範例只有在 thread 中使用 lock, 所以可以用 spin_lock - github-atomic3
可以發現, 即便次數放大到一百萬次, 最後 sum 結果為 0
4. ticket spin_lock
Linux 的 spin lock 使用的是 ticket spin_lock 的方式,
將 slock 分成 now_serving (owner) 和 next_ticket (next)
一開始初始化, slock 為 0, 當做 lock() 時, 會將 next +1 給下一個 thread,
並判斷 owner 和 next 值是否相同, 如果相同代表該 thread 有權拿到 lock,
如果不相同就繼續等待.
例如 :
(1) thread 1 一開始 owner:0 , next: 0, 先把 next 變成 1,
並比較 原 next(0) 和 owner 值 是否相同, 因為都是 0, 所以拿到 lock,
(2) thread 2 做 lock 時, owner :0 , next:1 -> 2, 便繼續等待.
(3) 當 thread 1做完 unlock() 時, 會將 owner 值 +1, 此時 thread 2 比較 owner / 原 next 均為 1,
則拿到 lock.
5. atomic
可以發現, lock 計算時, 也是做 +1 動作, 那怎麼確保在做 +1 的時候, 其他 CPU 不會執行呢.
也就是確保 read - modify - write 這一系列動作的完整性, 中間不會被插隊
這就是 atomic operation 的原由. atom 原子的意思, 也就代表不可分割.
而這仰賴 CPU 的指令支援.
(1) 在 x86, 用的是 lock bus 的方式,
可以發現, 在 assembly, 會在動作上多一個 LOCK#, 來告訴 CPU 這 load / store 讀寫記憶體,
需要搭配 bus lock, 讓其他 CPU 不能在這時候做 load / store
細節可以參考這篇:
https://xem.github.io/minix86/manual/intel-x86-and-64-manual-vol3/o_fe12b1e2a880e0ce-259.html
PS: cache 的部分, 會透過 cache coherence 的機制來達成一致.
(2) Ameba 的 CPU 是 ARM cortex-m, ARM 是透過 ldrex / strex 來達成
這邊的 ex 指的就是 exclusive , 例如我們看 ARM mbed 的 RTOS - RTX 做法:
https://github.com/ARM-software/CMSIS_5/blob/develop/CMSIS/RTOS2/RTX/Source/rtx_core_cm.h
LDREX 和 STREX 是配對使用, ARM cpu 會讓第二次執行 STREX 失敗, 只讓第一次的 STREX 成功
可以參考之前 Ameba 這篇: ARM Cortex-M Instruction Set Architecture
的 synchronization / lock acquire
所以原本程式可以簡化如下, 執行結果一樣是正確的
github-atomic4
--
緣由:
當我們對一個變數做計算時, CPU 通常的動作是:
(1) 從 memory 將變數值讀到暫存器
(2) CPU 通過暫存器做計算
(3) 將值寫回 memory
這也就是所謂的 read - modify - write 的動作
但這若在多工環境下, 可能會有問題, 例如: github-atomic1
我們做兩個 thread, 一個對 sum 加 1, 一個對 sum 減 1, 兩個都做三次, sum 初始值為 0.
正常來說最後 sum 值應該還是 0.
可以發現, 這樣執行起來, sum 的值並非預期. 最後變成了 -2, 而非 0
[90334.635512] hello_init: pid=14949
[90334.635699] hello_init: pid=14949, before sum=0
[90334.635714] work_handler1: pid=12886, sum=1
[90334.635717] work_handler1: pid=12886, sum=2
[90334.635719] work_handler2: pid=13336, sum=0
[90334.635722] work_handler1: pid=12886, sum=1
[90334.635724] work_handler2: pid=13336, sum=-1
[90334.635727] work_handler2: pid=13336, sum=-2
[90334.635773] hello_init: pid=14949, after sum=-2
1. interrupt disable
我們用在 MCU 常用的手法, 把 interrupt 關閉看看 - github-atomic2
可以使用 raw_local_irq_save() / raw_local_irq_restore()
2. UP v.s SMP
Linux 上的 UP 指的是 uni-processor 單個 CPU,
相對於 SMP - symmetric multi-processors 多個 CPU 而言.
上述 禁制中斷 這方式, 在多核的 cpu 上會有問題 (SMP)
這是因為我們雖然在該 CPU 上禁制了 interrupt, 該 cpu不會執行別的 thread,
但其他 CPU 仍可執行
所以如果我們把次數三次放大到 十萬次, 來增加它發生的機率,
可以發現執行結果 sum 不是 0
[104815.844974] hello_init: pid=19042, before sum=0
[104815.850770] hello_init: pid=19042, after sum=-20814
3. spin_lock v.s. spin_lock_irqsave()
差別在於 spin_lock_irqsave() 會禁制中斷,
這問題發生在, 如果這 lock 會在 中斷函式 中使用的話,
有可能當 thread 執行 spin_lock 時, 中斷來臨, 跳到中斷函式也執行 spin_lock
這樣就會變成雙層請求死鎖
因為我們這範例只有在 thread 中使用 lock, 所以可以用 spin_lock - github-atomic3
可以發現, 即便次數放大到一百萬次, 最後 sum 結果為 0
4. ticket spin_lock
Linux 的 spin lock 使用的是 ticket spin_lock 的方式,
將 slock 分成 now_serving (owner) 和 next_ticket (next)
一開始初始化, slock 為 0, 當做 lock() 時, 會將 next +1 給下一個 thread,
並判斷 owner 和 next 值是否相同, 如果相同代表該 thread 有權拿到 lock,
如果不相同就繼續等待.
例如 :
(1) thread 1 一開始 owner:0 , next: 0, 先把 next 變成 1,
並比較 原 next(0) 和 owner 值 是否相同, 因為都是 0, 所以拿到 lock,
(2) thread 2 做 lock 時, owner :0 , next:1 -> 2, 便繼續等待.
(3) 當 thread 1做完 unlock() 時, 會將 owner 值 +1, 此時 thread 2 比較 owner / 原 next 均為 1,
則拿到 lock.
5. atomic
可以發現, lock 計算時, 也是做 +1 動作, 那怎麼確保在做 +1 的時候, 其他 CPU 不會執行呢.
也就是確保 read - modify - write 這一系列動作的完整性, 中間不會被插隊
這就是 atomic operation 的原由. atom 原子的意思, 也就代表不可分割.
而這仰賴 CPU 的指令支援.
(1) 在 x86, 用的是 lock bus 的方式,
需要搭配 bus lock, 讓其他 CPU 不能在這時候做 load / store
細節可以參考這篇:
https://xem.github.io/minix86/manual/intel-x86-and-64-manual-vol3/o_fe12b1e2a880e0ce-259.html
PS: cache 的部分, 會透過 cache coherence 的機制來達成一致.
(2) Ameba 的 CPU 是 ARM cortex-m, ARM 是透過 ldrex / strex 來達成
這邊的 ex 指的就是 exclusive , 例如我們看 ARM mbed 的 RTOS - RTX 做法:
https://github.com/ARM-software/CMSIS_5/blob/develop/CMSIS/RTOS2/RTX/Source/rtx_core_cm.h
LDREX 和 STREX 是配對使用, ARM cpu 會讓第二次執行 STREX 失敗, 只讓第一次的 STREX 成功
可以參考之前 Ameba 這篇: ARM Cortex-M Instruction Set Architecture
的 synchronization / lock acquire
所以原本程式可以簡化如下, 執行結果一樣是正確的
github-atomic4
留言
張貼留言