A Lock-Free Synchronization Mechanism for Shared Data Structure

HUANG Shu-juan; RONG Xiao-feng; RU Yuan; ZHANG Ya

Chinese

您当前的位置：

首页 >

文章列表页 >

A Lock-Free Synchronization Mechanism for Shared Data Structure

更新时间：2026-09-04

- A Lock-Free Synchronization Mechanism for Shared Data Structure
- Vol. 33, Issue 10, Pages: 72-77(2016)
- 作者机构：
  
  西安工业大学机构计算机科学与工程学院,陕西,西安,710032
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：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.
黄姝娟, 容晓峰, 茹媛, 张雅. 一种采用Lock-Free同步机制的数据结构的研究[J]. 微电子学与计算机, 2016, 33(10): 72-77. DOI：

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. DOI：

摘要

随着多核芯片在嵌入式实时系统中的广泛应用

采用传统锁机制对共享数据的访问会引起死锁、优先级翻转以及CPU饥饿现象

进而会影响系统整体性能的发挥

严重时还会导致不可估量的损失发生.为此

针对Skip-list的共享数据结构提出了一种Lock-Free的同步机制方法

对该方法的线性一致性进行了证明

并将其应用于混合关键任务的共享优先级调度队列中.经过实验

该方法在吞吐量、核利用率以及平均响应时间方面优于传统的基于锁机制的方法

有效地提升了多核运行的效率.

Abstract

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.

关键词

Keywords

references

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Lightweight countermeasures against Spectre attacks on the branch prediction unit

Steganography model guided by attention mechanism and improved dense convolution

A feature-oriented context understanding and slice analysis network for tuberculosis detection

Microservices anomaly detection based on the correlation of monitoring metrics

Research on the design of blockchain-based AI-generated content traceability framework

Related Author

No data

Related Institution

No data

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰