Performance Analysis of RCU-Style Non-Blocking Synchronization Mechanisms on a Manycore-Based Operating System

被引:0
作者
Kim, Changhui [1 ]
Choi, Euteum [1 ]
Han, Mingyun [1 ]
Lee, Seongjin [1 ]
Kim, Jaeho [1 ]
机构
[1] Gyeongsang Natl Univ, Dept AI Convergence Engn, Jinju Si 52828, South Korea
来源
APPLIED SCIENCES-BASEL | 2022年 / 12卷 / 07期
基金
新加坡国家研究基金会;
关键词
manycore; synchronization; locks; lock-free; operating system (OS); multi-version concurrency control (MVCC);
D O I
10.3390/app12073458
中图分类号
O6 [化学];
学科分类号
0703 ;
摘要
There have been recent advances in multi-core machines with tens and hundreds of cores, and there is an increasing emphasis on the software structure. Many different synchronization mechanism techniques have been developed to improve the performance and the scalability of manycore systems. As the non-blocking algorithms are promising in overcoming performance limits in traditional lock-based blocking synchronization mechanisms, we are observing an increased usage ratio and a number of non-blocking synchronization algorithms. For example, the usage ratio of RCU increased sharply in recent years. Since RCU exhibits low write performance and is difficult to use, the research community introduced RLU and MV-RLU synchronization algorithms to address the issues. RLU and MV-RLU, which are called RCU-style synchronization mechanisms, are promising in terms of providing easy-to-use APIs (Application Programming Interfaces) and better performance in manycore machines. To expand the applicability of RCU-style mechanisms, we need to measure the performance and analyze their measurements in various environments. To meet the goal, we evaluate them at the user and kernel level in sv6 variant, which is a research operating system on a manycore system. In order to enable RCU-style synchronization algorithms in sv6 variant, we implemented and modified some of the libraries and memory allocators in sv6 variant. We use micro-benchmarks that exploit a linked list and hash table to measure the performance while experimenting with parameters of the benchmarks and types of data structures. In most of the experiments, we observed that MV-RLU is scalable. MV-RLU exhibits about thirteen times better throughput than RCU in the case of running 70 threads. In addition, we compare the operation procedures and APIs of each RCU-style synchronization algorithm to analyze the pros and cons of the algorithms.
引用
收藏
页数:20
相关论文
共 50 条
[1]  
[Anonymous], 2013, P ACM SIGMOD INT C M, DOI [DOI 10.1145/2463676.2463710, 10.1145/2463676.2463710]
[2]   Concurrent Updates with RCU: Search Tree as an Example [J].
Arbel, Maya ;
Attiya, Hagit .
PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14), 2014, :196-205
[3]  
Baumann A, 2009, SOSP'09: PROCEEDINGS OF THE TWENTY-SECOND ACM SIGOPS SYMPOSIUM ON OPERATING SYSTEMS PRINCIPLES, P29
[4]   Scaling a file system to many cores using an operation log [J].
Bhat, Srivatsa S. ;
Eqbal, Rasha ;
Clements, Austin T. ;
Kaashoek, M. Frans ;
Zeldovich, Nickolai .
PROCEEDINGS OF THE TWENTY-SIXTH ACM SYMPOSIUM ON OPERATING SYSTEMS PRINCIPLES (SOSP '17), 2017, :69-86
[5]  
Boyd-Wickizer S., 2012, P LIN S SAN DIEG CA, P119
[6]  
Boyd-Wickizer S., 2008, OSDI, V8, P43
[7]  
Chabbi M, 2015, ACM SIGPLAN NOTICES, V50, P215, DOI [10.1145/2688500.2688503, 10.1145/2858788.2688503]
[8]  
Chuck Moore AMD Corporate Fellow & Technology Group CTO, 2011, DAT PROC EX CLASS CO
[9]   The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors [J].
Clements, Austin T. ;
Kaashoek, M. Frans ;
Zeldovich, Nickolai ;
Morris, Robert T. ;
Kohler, Eddie .
SOSP'13: PROCEEDINGS OF THE TWENTY-FOURTH ACM SYMPOSIUM ON OPERATING SYSTEMS PRINCIPLES, 2013, :1-17
[10]   The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors [J].
Clements, Austin T. ;
Kaashoek, M. Frans ;
Zeldovich, Nickolai ;
Morris, Robert T. ;
Kohler, Eddie .
ACM TRANSACTIONS ON COMPUTER SYSTEMS, 2015, 32 (04)