Re: [問題] Lock的用法

看板ASM (組合語言)作者 (ggg)時間15年前 (2010/01/02 11:13), 編輯推噓1(1012)
留言13則, 2人參與, 最新討論串5/5 (看更多)
※ 引述《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
抱歉(1)看不懂; (2)不就是 producer-consumer problem?
01/02 11:29, 1F

01/02 11:54, , 2F
FIFO就是producer/consumer用的queue.共寫同一個變數就
01/02 11:54, 2F

01/02 11:59, , 3F
有先後與插斷問題,故用LOCK機制排除,但軟體lock比硬複雜!
01/02 11:59, 3F
※ 編輯: ggg12345 來自: 140.115.4.12 (01/02 12:25)

01/04 21:15, , 4F
FIFO Queue 可以有多個 enqueuer/dequeuers
01/04 21:15, 4F

01/04 21:16, , 5F
一方寫另一方讀是特例 等同於producer-consumer problem
01/04 21:16, 5F

01/05 16:02, , 6F
bakery algorithm屬N個process排隊使用共用臨界區的soft
01/05 16:02, 6F

01/05 16:12, , 7F
MX lock方法,掛號處因共用會更新出同號,用uid產生total
01/05 16:12, 7F

01/05 16:16, , 8F
order來仲裁排序,以阻擋他方使用臨界區的機制就是互斥鎖
01/05 16:16, 8F

01/05 16:23, , 9F
這算法用到單調上升的計數器,對有限bit置數器會增加麻煩.
01/05 16:23, 9F

01/05 16:47, , 10F
producer/consumer是單對的送收,對相關變數不必用到lock
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
文章代碼(AID): #1BFhdj14 (ASM)
文章代碼(AID): #1BFhdj14 (ASM)