全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
电子学报  2013 

基于硬件CAS原语的高效多字无锁同步算法

DOI: 10.3969/j.issn.0372-2112.2013.11.003, PP. 2127-2134

Keywords: 无锁同步,多线程,并发算法

Full-Text   Cite this paper   Add to My Lib

Abstract:

共享内存体系结构下,为解决锁同步导致的并发性能瓶颈,本文提出了一种基于硬件CAS(比较交换)原语的无锁同步算法.该算法利用底层处理器提供的比较交换指令,实现了在多核多线程环境下对共享变量的非阻塞同步操作,通过采用全局标记值的方式,避免了传统设计中由于使用内存字标记导致的性能开销,同时确保数据在并发访问中的一致性.实验结果表明,本文算法可以高效地支持任意多字的CAS同步,提高了对共享数据的并发访问性能,具有较好的可扩展性.

References

[1]  杨际祥,谭国真,王荣生.多核软件的几个关键问题及其研究进展[J].电子学报,2010,38(9):2140-2146. Yang Jixiang,Tan Guo zhen,Wang Rongsheng.Some key issues and their research advances for multi-core software[J].Acta Electronica Sinica,2010,38(9):2140- 2146.(in Chinese)
[2]  王睿伯,卢锡城,卢凯,王绍刚.面向CC-NUMA体系结构的事务内存冲突规避方法[J].计算机学报,2011,34(4):676-683. Wang Ruibo,Lu Xicheng,Lu Kai,Wang Shaogang.CC-NUMA oriented conflict preventing method for transactional memory[J].Chinese Journal of Computers,2011,34(4):676-683.(in Chinese)
[3]  A Dragojevic,P Felber,V Gramoll,R Guerraoul.Why STM can be more than a research toy[J].Communications of the ACM,2011,54(4):70-77.
[4]  M Herlihy.Wait-free synchronization[J].ACM Transactions on Programming Languages and Systems,1991,13(1):124-149.
[5]  D Cederman,P Tsigas.Supporting lock-free composition of concurrent data objects[A].Proceedings of the 7th ACM International Conference on Computing Frontiers[C].New York:ACM,2010.53-62.
[6]  T L Harris,K Fraser,I A Pratt.A practical multi-word compare-and-swap operation[J].Lecture Notes in Computer Science,2002,2508:265-279.
[7]  H.Sundell.Wait-free multi-word compare-and-swap using greedy helping and grabbing[J].International Journal of Parallel Programming,2011,39(6):694-716.
[8]  M Herlihy,V Luchangco,P Martin,M Moir.Nonblocking memory management support for dynamic-sized data structures[J].ACM Transactions on Computer Systems,2005,23(2):146-196.
[9]  G Kliot,E Petrank,B Steensgaard.A lock-free,concurrent,and incremental stack scanning for garbage collectors[A].Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments[C].New York:ACM,2009.11-20.
[10]  A Adl-Tabatabai,C Kozyrakis,B Saha.Unlocking concurrency[J].ACM QUEUE,2006,4(10):24-33.
[11]  D Dechev,B Stroustrup.Scalable nonblocking concurrent objects for mission critical code[A].Proceedings of the 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications[C].New York:ACM,2009.597-612.
[12]  J Giacomoni,T Moseley,M Vachharajani.FastForward for efficient pipeline parallelism:a cache-optimized concurrent lock-free queue[A].Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming[C].New York:ACM,2008.43-52.
[13]  H Sundell,P Tsigas.Lock-free deques and doubly linked lists[J].Journal of Parallel and Dsitributed Computing,2008,68(7):1008-1020.
[14]  O Agesen,D L Detlefs,C H Flood,et.al.DCAS-based concurrent deques[A].Proceedings of the 12th annual ACM Symposium on Parallel Algorithms and Architectures[C].New York:ACM,2000.137-146.
[15]  A Israeli,L Rappoport.Disjoint-access-parallel implementations of strong shared memory primitives[A].Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing[C].New York:ACM,1994.151-160.
[16]  J H Anderson,S Ramamurthy,R Jain.Implementing wait-free objects on priority-based systems[A].Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing[C].New York:ACM,1997.229-238.
[17]  K Fraser,T Harris.Concurrent programming without locks[J].ACM Transactions on Computer Systems,2007,25(2):1-60.
[18]  K Fraser.Practical lock-freedom[D].Cambridge,United Kingdom:Cambridge University Computer Laboratory,2004.
[19]  Intel.IA-32 Intel Architecture Software Developer''s Manual,Volume3:System Programming Guide[R].Mt.Prospect IL:Intel Corporation,2002.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133