DAG任务同步中无锁机制实现方法研究

韩星星; 肖锋; 黄姝娟; 张文娟; 陈术山; 李天森

doi:10.19304/J.ISSN1000-7180.2022.0457

DAG任务同步中无锁机制实现方法研究

doi: 10.19304/J.ISSN1000-7180.2022.0457

1.
西安工业大学计算机科学与工程学院, 陕西西安 710021
2.
西安工业大学基础学院, 陕西西安 710021

基金项目: 国家自然基金面上项目（62171361）,陕西省重点研发计划一般项目（2022GY-119）,陕西省科技厅自然科学基础研究计划（2021JM-440）,陕西省西安市未央区科技项目（201925）

详细信息

作者简介:
韩星星：女,（1996-）,硕士研究生.研究方向为嵌入式系统、DAG任务图调度. E-mail：1187502522@qq.com

黄姝娟：女,（1975-）,博士,副教授.研究方向为嵌入式系统

张文娟：女,（1980-）,博士,副教授.研究方向为机器学习

陈术山：男,（1998-）,硕士研究生.研究方向为嵌入式系统、异构多核

李天森：男,（1996-）,硕士研究生.研究方向为嵌入式系统、混合关键任务调度

通讯作者:
男,（1976-）,博士,教授.研究方向为研究方向为智能信息处理. E-mail：xffriends@xatu.edu.cn

中图分类号: TP302
计量
- 文章访问数: 20
- HTML全文浏览量: 21
- PDF下载量: 2
- 被引次数: 0
出版历程
- 收稿日期: 2022-07-28
- 修回日期: 2022-10-20

Research on the implementation method of lock-free mechanism in DAG task synchronization

1.
School of Computer Science and Engineering, Xi’an Technological University, Xi’an 710021, Shaanxi, China
2.
Basic College, Xi’an Technological University, Xi’an 710021, Shaanxi, China

摘要

摘要:
随着多核嵌入式实时系统的发展,DAG任务同步问题得到了广泛的关注. 目前的任务同步方法大都采用锁机制,但锁机制存在许多问题,如自旋锁存在任务忙等状态,浪费CPU资源；使用互斥锁的任务若获取不到共享资源会被阻塞,产生上下文切换开销；顺序锁允许写任务有更高的优先级,但写任务不能频繁更新数据,否则读任务会产生饿死现象. 上述锁机制如果应用于多核平台下的DAG任务同步,不仅会影响系统整体执行效率,导致后继任务无法执行,严重时会引发死锁现象导致系统崩溃. 因此,提出了在DAG任务同步过程中使用DCAS无锁机制,有效避免了锁机制存在的问题. 在LITMUS^RT多核平台下,以多任务同时申请、填充和释放Vxworks网络缓冲区为例,对缓冲池中的三元组mBlk,clBlk,cluster分别使用DCAS无锁机制. 实验结果表明,相比传统锁机制,DCAS无锁机制在DAG任务同步方面有较好的效果,响应时间减少了10.4%,系统的整体执行效率提高了4.2%.
- 多核嵌入式实时系统 /
- 任务同步 /
- DAG任务 /
- 锁机制 /
- DCAS无锁机制
Abstract:
With the development of multi-core embedded real-time systems, the DAG task synchronization problem has received extensive attention. Most of the current task synchronization methods use the lock mechanism, but there are many problems in the lock mechanism, such as the spin lock in the task busy waiting state, which wastes CPU resources; If a task using a mutex cannot obtain a shared resource, it will be blocked, resulting in context switching overhead; Sequential locks allow write tasks to have higher priority, but write tasks cannot update data frequently, otherwise read tasks will starve to death. If the above lock mechanism is applied to the synchronization of DAG tasks on a multi-core platform, it will not only affect the overall execution efficiency of the system, but also cause subsequent tasks to fail to execute, and in severe cases, will lead to deadlocks and system crashes. Therefore, the DCAS lock-free mechanism is used in the DAG task synchronization process, and the while condition is used to avoid the ABA problem. Under the LITMUS^RT multi-core platform, taking multitasking to apply, fill and release Vxworks network buffers at the same time as an example, the triplet mBlk, clBlk, and cluster in the buffer pool respectively use the DCAS lock-free mechanism. The experimental results show that compared with the traditional lock mechanism, the DCAS lock-free mechanism has a better effect in DAG task synchronization, the response time is reduced by 10.4%, and the overall execution efficiency of the system is improved by 4.2%.
- multi-core embedded real-time system /
- task synchronization /
- DAG task /
- lock mechanism /
- DCAS lock-free mechanism

HTML全文

图 1 Vxworks网络协议栈存储池

Figure 1. Vxworks network protocol stack storage pool

下载: 全尺寸图片幻灯片

图 2 缓冲区申请与释放

Figure 2. Buffer application and release

下载: 全尺寸图片幻灯片

图 3 三元组数据包

Figure 3. Triple packet

下载: 全尺寸图片幻灯片

图 4 三元组的申请

Figure 4. Application of triples

下载: 全尺寸图片幻灯片

图 5 缓冲区的申请释放流程

Figure 5. Buffer application release process

下载: 全尺寸图片幻灯片

图 6 随机申请缓冲区过程

Figure 6. Random application buffer process

下载: 全尺寸图片幻灯片

图 7 响应时间对比

Figure 7. Response time comparison

下载: 全尺寸图片幻灯片

图 8 执行时间对比

Figure 8. Execution time comparison

下载: 全尺寸图片幻灯片

表 1 任务的平均响应时间

Table 1. Average response time for tasks

周期	响应时间
周期	PEDF-CAS	PEDF-LOCK	GEDF-CAS	GEDF-LOCK
3	22080	22540	22159	23127
3	21837	22633	19062	23859
5	21781	22724	20482	23322
5	21978	23476	21816	22037
6	21480	23138	21457	22111
6	21010	23925	16779	21252
8	16649	22603	17774	21759
8	15977	22743	16842	19743
20	20763	23552	21856	22371
20	20561	21463	20554	22101
25	20856	22231	19915	22589

下载: 导出CSV

表 2 任务的平均执行时间

Table 2. Average execution time of tasks

周期	执行时间
周期	PEDF-CAS	PEDF-LOCK	GEDF-CAS	GEDF-LOCK
3	7892	8059	7791	7959
3	7888	8181	7688	8158
5	7808	8074	7730	7942
5	7619	8123	7950	8052
6	7596	8030	7909	8012
6	7770	8296	7985	8182
8	7900	8331	7613	8033
8	7728	8160	7832	8281
20	7934	8115	7583	8728
20	7825	8212	7809	8085
25	7829	8142	7876	7960

下载: 导出CSV

参考文献(14)

[1]	梁秋玲, 张向利, 张红梅, 等. 基于多核处理器的关联任务并行感知调度算法[J]. 计算机工程,2021,47(7):212-217. DOI: 10.19678/j.issn.1000-3428.0057225. LIANG Q L, ZHANG X L, ZHANG H M, et al. Parallel perceptual scheduling algorithm for related tasks based on multi-core processors[J]. Computer Engineering,2021,47(7):212-217. DOI: 10.19678/j.issn.1000-3428.0057225.
[2]	曹晟. 面向嵌入式智能设备的多核操作系统任务调度算法的研究与实现[D]. 北京: 北京邮电大学, 2021. CAO S. Research and implementation of scheduling algorithm in multi-core operating system for embedded intelligent devices[D]. Beijing: Beijing University of Posts and Telecommunications, 2021.
[3]	张杨, 张冬雯, 仇晶. 面向Java锁机制的字节码自动重构框架[J]. 计算机科学,2015,42(11):84-89. DOI: 10.11896/j.issn.1002-137X.2015.11.017. ZHANG Y, ZHANG D W, QIU J. Automated refactoring framework for Java locks[J]. Computer Science,2015,42(11):84-89. DOI: 10.11896/j.issn.1002-137X.2015.11.017.
[4]	徐永新. 多核并行计算中锁机制的影响研究[J]. 电子技术与软件工程,2020(22):156-158. XU Y X. Research on the influence of lock mechanism in multi-core parallel computing[J]. Electronic Technology and Software Engineering,2020(22):156-158.
[5]	张杨, 董士程. 面向并发程序中锁机制的智能化推荐方法[J]. 计算机应用,2021,41(6):1597-1603. DOI: 10.11772/j.issn.1001-9081.2020121929. ZHANG Y, DONG S C. Intelligent recommendation method for lock mechanism in concurrent program[J]. Journal of Computer Applications,2021,41(6):1597-1603. DOI: 10.11772/j.issn.1001-9081.2020121929.
[6]	谢文韬. 基于无锁结构的大容量数据高性能检索系统研究[D]. 南京: 东南大学, 2017. XIE W T. Realization of a high performance data retrieval system for big data based on lock free structure[D]. Nanjing: Southeast University, 2017.
[7]	TSIGAS P. Lock-free concurrent data structures and how to model their performance[C]//Proceedings of the 19th International Conference on Application of Concurrency to System Design (ACSD). Aachen, Germany: IEEE, 2019.
[8]	金琪. 高性能消息队列中无锁数据结构的设计与实现[D]. 南京: 南京邮电大学, 2021. JIN Q. Design and implementation of lock-free data structures in high-performance message queue[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2021.
[9]	吴恩慈. 基于优化的CAS算法实现线程安全的HashMap[J]. 软件,2019,40(6):185-190. DOI: 10.3969/j.issn.1003-6970.2019.06.043. WU E C. Thread-safe HashMapstructure based on optimized CAS algorithm[J]. Computer Engineering & Software,2019,40(6):185-190. DOI: 10.3969/j.issn.1003-6970.2019.06.043.
[10]	于欣. 基于无锁方法的二叉搜索树算法研究[D]. 石家庄: 河北科技大学, 2019. YU X. The research ofbinary search tree algorithm based on lock-free method[D]. Shijiazhuang: Hebei University of Science & Technology, 2019.
[11]	王俊昌, 王振, 付雄. 基于无锁数据结构的FIFO队列算法[J]. 计算机工程,2018,44(8):315-320. DOI: 10.19678/j.issn.1000-3428.0050269. WANG J C, WANG Z, FU X. FIFO queue algorithm based on lock-free data structure[J]. Computer Engineering,2018,44(8):315-320. DOI: 10.19678/j.issn.1000-3428.0050269.
[12]	孙静, 张亚平, 李鹏飞, 等. 基于Transpose规则的无锁自组织链表算法[J]. 计算机工程,2017,43(9):23-28. DOI: 10.3969/j.issn.1000-3428.2017.09.005. SUN J, ZHANG Y P, LI P F, et al. Lock-free self-organizing linked-list algorithm based on Transpose rule[J]. Computer Engineering,2017,43(9):23-28. DOI: 10.3969/j.issn.1000-3428.2017.09.005.
[13]	ZHANG D L, DECHEVD. A lock-free priority queue design based on multi-dimensional linked lists[J]. IEEE Transactions on Parallel and Distributed Systems,2016,27(3):613-626. DOI: 10.1109/TPDS.2015.2419651.
[14]	MINISKAR N R, LIU F, VETTER J S. A memory efficient lock-free circular queue[C]//Proceedings of 2021 IEEE International Symposium on Circuits and Systems (ISCAS). Daegu, Korea: IEEE, 2021.