计算机科学

首页 > 计算机科学

Load-link/store-conditional

2018-08-30 10:04:05     所属分类:编译原理

load-linkstore-conditional (LL/SC)是一对用于并发同步访问内存的CPU指令。Load-link返回内存位置处的当前值,随后的store-conditional在该内存位置处保存新值(如果从load-link后没有被修改)。这被用于实现无锁算法英语Non-blocking_algorithm与read-modify-write原子操作。

LL/SC与compare-and-swap在理论上是等价的。[1]

目录

  • 1 历史
  • 2 实现
  • 3 参见
  • 4 参考文献

历史

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对。[2] 嵌套的LL/SC机制用于提供MCAS原语(多字Compare-And-Swap,字可以是分布的)。[3] 2013年Trevor Brown, Faith Ellen, Eric Ruppert软件实现了多地址LL/SC扩展。[4]这被用来优化二叉搜索树。[5]

参见

  • 非阻塞同步英语Non-blocking synchronization
  • 事务内存(Transactional memory)

参考文献

  1. ^ Anderson, James H.; Moir, Mark. Universal constructions for multi-object operations. PODC '95 Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. ACM. 1995: 184–193. ISBN 0-89791-710-3. doi:10.1145/224964.224985.  See their Table 1, Figures 1 & 2 and Section 2 in particular.
  2. ^ Larus, James R.; Rajwar, Ravi. Transactional Memory. Morgan & Claypool. 2007: 55. ISBN 978-1-59829-124-7. 
  3. ^ Fraser, Keir. Practical lock-freedom (PDF) (Technical report). University of Cambridge Computer Laboratory: 20. February 2004. UCAM-CL-TR-579. 
  4. ^ 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. ISBN 978-1-4503-2065-8. doi:10.1145/2484239.2484273. (原始内容 (PDF)存档于2015-02-03).  See also slides
  5. ^ 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. ISBN 978-1-4503-2656-8. doi:10.1145/2555243.2555267. 
  • Jensen, Eric H.; Hagensen, Gary W.; Broughton, Jeffrey M. A New Approach to Exclusive Data Access in Shared Memory Multiprocessors (PDF) (Technical report). Lawrence Livermore National Laboratory. November 1987. UCRL-97663. 
  • Bruner, John D.; Hagensen, Gary W.; Jensen, Eric H.; Pattin, Jay C.; Broughton, Jeffrey M. Cache Coherence on the S-1 AAP (PDF) (Technical report). Lawrence Livermore National Laboratory. 11 November 1987. UCRL-97646. 
  • 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. 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/340111.html

上一篇:LL分析器
下一篇:字节码
相关推荐