西安工业大学 机构 计算机科学与工程学院,陕西,西安,710032
纸质出版:2016
移动端阅览
黄姝娟, 容晓峰, 茹媛, 张雅. 一种采用Lock-Free同步机制的数据结构的研究[J]. 微电子学与计算机, 2016, 33(10): 72-77.
HUANG Shu-juan, RONG Xiao-feng, RU Yuan, et al. A Lock-Free Synchronization Mechanism for Shared Data Structure[J]. 2016, 33(10): 72-77.
随着多核芯片在嵌入式实时系统中的广泛应用
采用传统锁机制对共享数据的访问会引起死锁、优先级翻转以及CPU饥饿现象
进而会影响系统整体性能的发挥
严重时还会导致不可估量的损失发生.为此
针对Skip-list的共享数据结构提出了一种Lock-Free的同步机制方法
对该方法的线性一致性进行了证明
并将其应用于混合关键任务的共享优先级调度队列中.经过实验
该方法在吞吐量、核利用率以及平均响应时间方面优于传统的基于锁机制的方法
有效地提升了多核运行的效率.
With the multi-core chip wildly used in the embedded real-time system
the traditional lock synchronization may cause deadlock
priority inversion and cpu starvation. It may degrade performance and cause inestimable loss to the real-time system. This paper proposed a lock-free alogrithm for the Skip-list data structure and gave the proof for its linear consistency and used it as a shared priority queue for mixed-critical system. The experimental results show that this method has much better than the lock mechanism on average response time and utilization rate of multi-core processor and have the higher system throughput rate.
Bonnichsen L F, Karlsson S, Probst C W. ELB-trees an efficient and lock-free B-tree derivative[C]//Proceedings of the 6thIEEE International Workshop onMulti-/Many-core Computing Systems (MuCoCoS)[s. l. ]: IEEE, 2013: 1-10.
SirajoAbdullahiBakura, AminuMohammed. Lock-free hybrid concurrency control strategy for mobile environment[J]. Proceedings of the 6thInternational Conference on Adaptive Science % Technology (ICAST), 2014, 66(5): 1-5. DOI: 1
NirShavit, ItayLotan. Skiplist-based concurrent priority queues[C]//Proceedings of the 14th International Parallel and Distributed Processing Symposium. Washington, DC, USA: IEEE, 2000: 263-268.
Deli Zhang, Damian Dechev. A lock-free priority queue design based on multi-dimensional linked lists[J]. Journal of IEEE Transactions on Parallel and Distributed Systems, 2015, 27(3): 1-14. DOI: 1
Youngjoong Cho, Dongwoo Lee, HyungKooK Jun, et al. Lock-free memory allocator without garbage collection on multicore embedded devices[C]//Proceedings of the International Conference on Consumer Electronics (ICCE). Istanbul, Turkey: IEEE, 2014: 428-429.
KristijanDragic, Daniel Bauer. A survey of concurrent priority queue algorithms[C]//Proceedings of the International Symposium on Parallel and Distributed Processing(ISPDP). Switzerband: IEEE, 2008: 1-6.
AleksandarProkopec, Dmitry Petrashko, MartinOdersky. Efficient lock-free work-stealing Iterators for data-parallel collections[C]//Proceedings of the 23rd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP). Lausanne, Switzerland: IEEE. 2015: 248-252.
Pooja Aggarwal, Smruti R Sarangi. Lock-free and wait-free slot scheduling algorithms[C]//Proceedings of the 27th International Parallel and Distributed Processing Symposium(IPDPS). Washington, DC, USA: ACM, 2013: 961-972.
Amos Israeli, LihuRappoport. Efficient wait-free implementation of a concurrentpriority queue[C]//Proceedings of the 7th International Workshop Distributed Algorithms(WDAG). Lausanne, Switzerland: IEEE, 1993: 1-17.
SundellHäkan, TsigasPhilippas. Fast and lock-free concurrent priority queues for multi-thread systems[J]. Journal of Parallel and Distributed Computing, 2005, 65(1): 609-627. DOI: 609
Herlihy M P, Wing J M, Linerizability: A correctness condition for concurrent objects[J]. Journal of ACM Transactions on Programming Languages and Systems, 1990, 12(1): 463-492. DOI: 463
Nhan Nguyen, PhilippasTsigas. Lock-Free cuckoo hashing[C]//Proceedings of the 34thInternational Conference on Distributed Computing Systems (ICDCS). Madrid, Spain: IEEE, 2014: 627-636.
Gerhard Schellhorn, Simon Baumler. Formal verification of lock-free algorithms[C]//Proceedings of the 9th International Conference on Application of Concurrency to System Design(ACSD). Washington, DC, USA: ACM, 2009: 13-18.
0
浏览量
8
下载量
0
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010602201714号