Load-link/store-conditional

在電腦科學中,load-linked/store-conditional(LL/SC),也會被稱作load-reserved/store-conditional (LR/SC)load-linkstore-conditional (LL/SC)是一對用於並行同步訪問主記憶體的CPU指令。Load-link返回主記憶體位置處的當前值,隨後的store-conditional在該主記憶體位置處儲存新值(如果從load-link後沒有被修改)。這被用於實現無鎖演算法英語Non-blocking_algorithmread-modify-write原子操作。

歷史

編輯

LL/SC最初是Jensen, Hagensen, Broughton在勞倫斯利佛摩國家實驗室S-1 AAP multiprocessor頁面存檔備份,存於互聯網檔案館)而設計。

實現

編輯

LL/SC指令被下述架構支援:

LL/SC的硬件實現典型地不允許巢狀LL/SC對。[1] 巢狀的LL/SC機制用於提供MCAS原語(多字Compare-And-Swap,字可以是分佈的)。[2] 2013年Trevor Brown, Faith Ellen, Eric Ruppert軟件實現了多地址LL/SC擴充。[3]這被用來最佳化二叉搜尋樹。[4]

參見

編輯

參考文獻

編輯
  1. ^ Larus, James R.; Rajwar, Ravi. Transactional Memory. Morgan & Claypool. 2007: 55. ISBN 978-1-59829-124-7. 
  2. ^ Fraser, Keir. Practical lock-freedom (PDF) (技術報告). University of Cambridge Computer Laboratory: 20. February 2004 [2017-11-22]. UCAM-CL-TR-579. (原始內容存檔 (PDF)於2020-11-12). 
  3. ^ Brown, Trevor; Ellen, Faith; Ruppert, Eric. Pragmatic primitives for non-blocking data structures (PDF). PODC '13 Proceedings of the 2013 ACM symposium on Principles of distributed computing. ACM. 2013: 13–22 [2017-11-22]. ISBN 978-1-4503-2065-8. doi:10.1145/2484239.2484273. (原始內容 (PDF)存檔於2015-02-03).  See also slides頁面存檔備份,存於互聯網檔案館
  4. ^ Brown, Trevor; Ellen, Faith; Ruppert, Eric. A general technique for non-blocking trees (PDF). PPoPP '14 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM. 2014: 329–342 [2017-11-22]. ISBN 978-1-4503-2656-8. doi:10.1145/2555243.2555267. (原始內容存檔 (PDF)於2019-10-24).