Load-link/store-conditional

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

歷史

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

實現

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

Alpha: ldl_l/stl_c , ldq_l/stq_c
PowerPC: lwarx/stwcx , ldarx/stdcx
MIPS架構: ll/sc
ARM架構: ldrex/strex (ARMv6 , v7), ldxr/stxr (ARM version 8)
RISC-V: lr/sc

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

參見

非阻塞同步（英語：Non-blocking synchronization）
事務主記憶體（Transactional memory）

參考文獻

^ Larus, James R.; Rajwar, Ravi. Transactional Memory. Morgan & Claypool. 2007: 55. ISBN 978-1-59829-124-7.
^ 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）.
^ 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 （頁面存檔備份，存於網際網路檔案館）
^ 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）.

Jensen, Eric H.; Hagensen, Gary W.; Broughton, Jeffrey M. A New Approach to Exclusive Data Access in Shared Memory Multiprocessors (PDF) (技術報告). Lawrence Livermore National Laboratory. November 1987 [2017-11-22]. UCRL-97663. （原始內容 (PDF)存檔於2017-02-02）.
Bruner, John D.; Hagensen, Gary W.; Jensen, Eric H.; Pattin, Jay C.; Broughton, Jeffrey M. Cache Coherence on the S-1 AAP (PDF) (技術報告). Lawrence Livermore National Laboratory. 11 November 1987 [2017-11-22]. UCRL-97646. （原始內容 (PDF)存檔於2017-02-02）.
Detlefs, D.; Martin, P.; Moir, M.; Steele, Jr., Guy L. Lock-free reference counting. PODC '01 Proceedings of the twentieth annual ACM symposium on Principles of distributed computing. ACM. 2001: 190–9. ISBN 1-58113-383-9. doi:10.1145/383962.384016.
Reinholtz, Kirk. Atomic Reference Counting Pointers. C/C++ Users Journal. December 2004. ^{[永久失效連結]}
Sites, R. L. Alpha AXP architecture. Comm. ACM. February 1993, 36 (2): 33–44. doi:10.1145/151220.151226.

[LarusRajwar2007-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）.

[1]

[2]

[3]

[4]