imported>InternetArchiveBot：Fixing 2 dead IA links per WP:DEADIABOOKLINKS (20260528dark)) #IABot (v2.0.9.5) (GreenC bot

2026-05-28T12:40:56Z

Fixing 2 dead IA links per WP:DEADIABOOKLINKS (20260528dark)) #IABot (v2.0.9.5) (GreenC bot

新页面

{{expand|time=2017-11-22T12:31:58+00:00}}
{{expert|time=2017-11-22T12:31:58+00:00}}
{{NoteTA
|G1=IT
}}
在電腦科學中,'''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后没有被修改）。这被用于实现{{tsl|en|Non-blocking_algorithm|无锁算法}}与[[read-modify-write]]原子操作。

==历史==
LL/SC最初是Jensen, Hagensen, Broughton在[[勞倫斯利佛摩國家實驗室]]为[http://forum.stanford.edu/wiki/index.php/S-1_project S-1 AAP multiprocessor] {{Wayback|url=http://forum.stanford.edu/wiki/index.php/S-1_project |date=20201124011715 }}而设计。

==实现==
LL/SC指令被下述架构支持：
* [[DEC Alpha|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对。<ref name="LarusRajwar2007">{{cite book |first=James R. |last=Larus |first2=Ravi |last2=Rajwar |title=Transactional Memory |url=https://archive.org/details/transactionalmem0000laru |year=2007 |publisher=Morgan & Claypool |isbn=978-1-59829-124-7 |pages=[https://archive.org/details/transactionalmem0000laru/page/55 55]}}</ref> 嵌套的LL/SC机制用于提供MCAS原语（多字Compare-And-Swap，字可以是分布的）。<ref>{{cite techreport |first=Keir |last=Fraser |title=Practical lock-freedom |institution=University of Cambridge Computer Laboratory |number=UCAM-CL-TR-579 |page=20 |date=February 2004 |url=https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf |format=PDF |access-date=2017-11-22 |archive-date=2020-11-12 |archive-url=https://web.archive.org/web/20201112020700/https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf |dead-url=no }}</ref> 2013年Trevor Brown, Faith Ellen, Eric Ruppert软件实现了多地址LL/SC扩展。<ref>{{cite book |first=Trevor |last=Brown |first2=Faith |last2=Ellen |first3=Eric |last3=Ruppert |chapter=Pragmatic primitives for non-blocking data structures |chapterurl=http://www.cs.utoronto.ca/~tabrown/podc13/fullpaper.pdf |title=PODC '13 Proceedings of the 2013 ACM symposium on Principles of distributed computing |publisher=ACM |year=2013 |isbn=978-1-4503-2065-8 |pages=13–22 |doi=10.1145/2484239.2484273 |deadurl=yes |archiveurl=https://web.archive.org/web/20150203093554/http://www.cs.utoronto.ca/~tabrown/podc13/fullpaper.pdf |archivedate=2015-02-03 |access-date=2017-11-22 }} See also [http://www.cse.yorku.ca/~ruppert/talks/srdc-2013.pdf slides] {{Wayback|url=http://www.cse.yorku.ca/~ruppert/talks/srdc-2013.pdf |date=20210901005750 }}</ref>这被用来优化二叉搜索树。<ref>{{cite book |first=Trevor |last=Brown |first2=Faith |last2=Ellen |first3=Eric |last3=Ruppert |chapter=A general technique for non-blocking trees |chapterurl=http://www.cs.toronto.edu/~tabrown/chromatic/fullpaper.pdf |title=PPoPP '14 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming |publisher=ACM |year=2014 |isbn=978-1-4503-2656-8 |pages=329–342 |doi=10.1145/2555243.2555267 |access-date=2017-11-22 |archive-date=2019-10-24 |archive-url=https://web.archive.org/web/20191024002441/http://www.cs.toronto.edu/~tabrown/chromatic/fullpaper.pdf |dead-url=no }}</ref>

==参见==
*{{tsl|en|Non-blocking synchronization|非阻塞同步}}
*[[事务内存]]（Transactional memory）

== 参考文献 ==
{{Reflist}}
{{refbegin}}
*{{cite techreport |first=Eric H. |last=Jensen |first2=Gary W. |last2=Hagensen |first3=Jeffrey M. |last3=Broughton |title=A New Approach to Exclusive Data Access in Shared Memory Multiprocessors |institution=Lawrence Livermore National Laboratory |number=UCRL-97663 |date=November 1987 |url=https://e-reports-ext.llnl.gov/pdf/212157.pdf |format=PDF |access-date=2017-11-22 |archive-url=https://web.archive.org/web/20170202203202/https://e-reports-ext.llnl.gov/pdf/212157.pdf |archive-date=2017-02-02 |dead-url=yes }}
*{{cite techreport |first=John D. |last=Bruner |first2=Gary W. |last2=Hagensen |first3=Eric H. |last3=Jensen |first4=Jay C. |last4=Pattin |first5=Jeffrey M. |last5=Broughton |title=Cache Coherence on the S-1 AAP |institution=Lawrence Livermore National Laboratory |number=UCRL-97646 |date=11 November 1987 |url=https://e-reports-ext.llnl.gov/pdf/212414.pdf |format=PDF |access-date=2017-11-22 |archive-url=https://web.archive.org/web/20170202203224/https://e-reports-ext.llnl.gov/pdf/212414.pdf |archive-date=2017-02-02 |dead-url=yes }}
*{{cite book |first=D. |last=Detlefs |first2=P. |last2=Martin |first3=M. |last3=Moir |first4=Guy L. |last4=Steele, Jr. |chapter=Lock-free reference counting |title=PODC '01 Proceedings of the twentieth annual ACM symposium on Principles of distributed computing |url=https://archive.org/details/proceedingsoftwe0000acms_i1v1 |publisher=ACM |year=2001 |isbn=1-58113-383-9 |pages=[https://archive.org/details/proceedingsoftwe0000acms_i1v1/page/190 190]–9 |doi=10.1145/383962.384016}}
*{{cite journal |first=Kirk |last=Reinholtz |title=Atomic Reference Counting Pointers |journal=[[C/C++ Users Journal]] |volume= |issue= |pages= |year=December 2004 |url=http://www.cuj.com/documents/s=9724/cuj0412f/ }}{{dead link|date=2018年2月 |bot=InternetArchiveBot |fix-attempted=yes }}
*{{cite journal |first=R. L. |last=Sites |title=Alpha AXP architecture |journal=Comm. ACM |volume=36 |issue=2 |pages=33–44 |date=February 1993 |doi=10.1145/151220.151226 }}
{{refend}}

[[Category:并发控制]]
[[Category:编译原理]]

Load-link/store-conditional - 版本历史

imported>InternetArchiveBot：​Fixing 2 dead IA links per WP:DEADIABOOKLINKS (20260528dark)) #IABot (v2.0.9.5) (GreenC bot

imported>InternetArchiveBot：Fixing 2 dead IA links per WP:DEADIABOOKLINKS (20260528dark)) #IABot (v2.0.9.5) (GreenC bot