Re: [問題] Lock的用法
※ 引述《ksmrt0123 (ksmrt)》之銘言:
: Atomic instruction在shared memory multi-processor系統中是
: process synchronization (如 mutual exclusion)之基礎. 最基本的
: atomic instruction是shared memory read/write. 但read/write
: 並不夠powerful, 用read/write來實作synchronization一方面可能
: performance不夠好, 一方面有些好的演算法特性用(如FIFO ordering)
: 已經證明只用read/write是無法作出來的. ^^^^^^^^^^^^^^^^^^^^^^^^^
: 這邊講錯了 只用atomic read/write
: 是可以作出FIFO ordering的mutual
: exclusion algorithm:
: http://www.viswiki.com/en/Lamport's_bakery_algorithm
===================================================================
這可能是表達上的問題. 畫蛇填足補充一下, 有錯請更正.
第一個假設是: 硬體的 write operation 是設計成不會同時寫入同一個位址.
再深入假設對記憶體送出位址線訊號(address), 資料訊號(data) 及請求
read/write 命令訊號是不可再被分割的(atomic operation 之意, 但這在
x86 multi-processor shared bus 不成立).
1.假設兩個 processor 共用一段記憶體, 且兩者都會對該共用記憶體做更
新的動作, 也就是做 read-modify-write operation.
此時, 對該共用記憶區想要有正確的運作結果, 就面臨必需用 mutual
exclusive flag 來通知協調另一方不要同時做更新動作(就是互斥之意).
而 mutual exclusive flag 本身就是一個 shared variable, 如果做通知
協調的事, 就有對 flag 做 read-modify-write 的動作需求. 這種需求
解決辦法之一是用 lock 機制, 讓 read-modify-write 不可分割的一口氣
做完.
2.FIFO queue 也是一種記憶體使用與運作形式, 是一方送(寫)進去, 另一
方取(讀)出來, 這種共用形式是否要用到 mutual exclusive lock flag ?
答案是:如果只限一個送, 另一個同時收, 就可以不必用到.
queue 的送收雙方各自維持一個指標指到 queue 的頭尾, 從頭讀取
從尾存入. 收送兩方可能會同時讀到頭尾這兩個指標, 但不會同時共
用寫到同一個指標做同時更新, 而是寫到各自分開管理的頭或尾指標
所以, 收送雙方通訊用的 FIFO queue 如果只用 atomic read/write operation
的記憶體來實現(或模擬), 是不必使用到 mutual exclusive lock 這種機制.
FIFO queue 的本質就是一方寫, 另一方讀, 寫只會寫到不同的空位. 對頭與
尾兩指標變數也是只做如此的運作.
如果 read/write operation 可以再被分割, 兩者交錯到近乎同時運作.
即使讀出的值沒有立即反應同時寫進的值, 影響到的只是檢查 FIFO queue
是 full 或 empty 的判斷. 例如收方已取出, 送方未立即發覺, 頂多就是
誤認仍然是 full, 造成延遲寫入. 同理, empty 的檢驗也是一樣, 頂多造
成收方慢一點取出.
→
01/02 11:29, , 1F
01/02 11:29, 1F
→
01/02 11:54, , 2F
01/02 11:54, 2F
→
01/02 11:59, , 3F
01/02 11:59, 3F
※ 編輯: ggg12345 來自: 140.115.4.12 (01/02 12:25)
推
01/04 21:15, , 4F
01/04 21:15, 4F
→
01/04 21:16, , 5F
01/04 21:16, 5F
→
01/05 16:02, , 6F
01/05 16:02, 6F
→
01/05 16:12, , 7F
01/05 16:12, 7F
→
01/05 16:16, , 8F
01/05 16:16, 8F
→
01/05 16:23, , 9F
01/05 16:23, 9F
→
01/05 16:47, , 10F
01/05 16:47, 10F
→
01/05 18:21, , 11F
01/05 18:21, 11F
→
01/05 18:22, , 12F
01/05 18:22, 12F
→
01/05 18:23, , 13F
01/05 18:23, 13F
討論串 (同標題文章)
ASM 近期熱門文章
PTT數位生活區 即時熱門文章