Re: [問題] Lock的用法

[ggg12345 (ggg)]

※ 引述《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 的檢驗也是一樣, 頂多造
成收方慢一點取出.


→ ksmrt0123:抱歉(1)看不懂; (2)不就是 producer-consumer problem?
→ ggg12345:FIFO就是producer/consumer用的queue.共寫同一個變數就
→ ggg12345:有先後與插斷問題,故用LOCK機制排除,但軟體lock比硬複雜!
※ 編輯: ggg12345        來自: 140.115.4.12         (01/02 12:25)