政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/152034

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/152034

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 113318/144297 (79%)
Visitors : 51012130 Online Users : 928

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Informatics > Department of Computer Science > Theses > Item 140.119/152034

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/152034

Title:	MCSH-2P：一種具有標準Lock API的高效MCS Lock演算法 MCSH-2P：An Efficient MCS Lock Algorithm with Standard Lock API
Authors:	李庭慶 Li, Ting-Ching
Contributors:	張宏慶 Jang, Hung-Chin 李庭慶 Li,Ting-Ching
Keywords:	自旋鎖隊列鎖 MCS鎖鎖介面吞吐量延遲可擴展性 Spin locks Queued locks MCS lock Locking API Throughput Latency Scalability
Date:	2024
Issue Date:	2024-07-01 12:30:03 (UTC+8)
Abstract:	Concurrency以及Lock演算法是現代計算機科學的基礎，在多執行緒的系統下都免不了使用Lock演算法。MCS演算法是由Mellor-Crummy以及Scott提出高效率並且廣泛運用的Lock演算法。MCS演算法有First-Come First-Served以及Cache-Friendly等優秀性質，然而MCS演算法實作上會需要額外的參數來管理Lock的狀態，在API設計上也不符合標準Lock API。因此先後分別由不同研究者提出MCS-K42以及MCSH等標準Lock API演算法，這些演算法在吞吐量以及延遲的表現都劣於MCS演算法。因此本論文旨在提出新的演算法不僅有標準Lock API性質甚至能在吞吐量與延遲的表現皆能比肩MCS演算法。為了達成目標，本論文結合MCSH、MCS-K42以及QSpinlock等標準Lock API演算法的特性提出MCSH-2P演算法，提出的演算法在acquire方法中會類似MCSH演算法的acquire方法，release方法則會類似QSpinlock的release方法只有單純的store指令，而Lock結構則類似於MCS-K42演算法的兩個指標結構。為驗證本論文算法是否有達到預期目標，模擬實驗採用C++進行模擬，模擬實驗設計不同的執行緒競爭環境來確保真實的Lock演算法使用情形，從實驗結果可以發現本論文相較於其他有標準Lock API演算法整體上有更高的吞吐量以及更低的延遲，甚至與MCS演算法在吞吐量以及延遲的有相近的效能。最後提出本論文研究可改善之部分，將其歸納給未來研究學者可繼續往更高吞吐量、更低延遲及符合現實執行緒競爭環境等方向研究。 Concurrency and lock algorithms are fundamental in modern computer science, and the use of lock algorithms is inevitable in systems with multiple threads. The MCS algorithm, proposed by Mellor-Crummey and Scott, is an efficient and widely used lock algorithm. The MCS algorithm has excellent properties such as First-Come First-Served and Cache-Friendly. However, the implementation of the MCS algorithm requires additional parameters to manage the lock's state, and its API design does not conform to standard lock APIs. Therefore, researchers have proposed standard lock API algorithms such as MCS-K42 and MCSH, but these algorithms perform worse than the MCS algorithm in terms of throughput and latency. This paper aims to propose a new algorithm that not only has the properties of a standard lock API but also can match the performance of the MCS algorithm in terms of both throughput and latency. To achieve this goal, this paper combines the characteristics of standard lock API algorithms such as MCSH, MCS-K42, and QSpinlock to propose MCSH-2P lock algorithm. The proposed algorithm has an acquire method similar to the MCSH algorithm's acquire method and a release method similar to the QSpinlock's release method, which only uses a simple store instruction. The lock structure is similar to the two-pointer structure of the MCS-K42 algorithm. To verify whether the algorithm proposed in this paper achieves the expected goals, simulation experiments are conducted using C++. Different thread competition environments are designed in the simulation experiments to ensure a realistic use of lock algorithms. The experimental results show that compared to other standard lock API algorithms, the algorithm proposed in this paper has higher overall throughput and lower latency, and even has performance similar to the MCS algorithm in terms of both throughput and latency. Finally, suggestions for improvement are proposed, which can be summarized for future research scholars to continue research in the directions of higher throughput, lower latency, and compliance with realistic thread competition environments.
Reference:	[1] M. Abadi and L. Lamport, "The existence of refinement mappings," Theoretical Computer Science, vol. 82, no. 2, pp. 253-284, 1991. [2] H. Akkan, M. Lang, and L. Ionkov, "HPC runtime support for fast and power efficient locking and synchronization," in 2013 IEEE International Conference on Cluster Computing (CLUSTER), 2013, pp. 1-7. [3] M. Auslander, D. Edelsohn, O. Krieger, B. Rosenburg, and R. Wisniewski, "Enhancement to the MCS lock for increased functionality and improved programmability," ed, 2003. [4] S. Boyd-Wickizer, M. F. Kaashoek, R. Morris, and N. Zeldovich, "Non-scalable locks are dangerous," in Proceedings of the Linux Symposium, 2012, pp. 119- 130. [5] D. Dice, "Malthusian locks," in Proceedings of the Twelfth European Conference on Computer Systems, 2017, pp. 314-327. [6] D. Dice, D. Hendler, and I. Mirsky, "Lightweight contention management for efficient compare-and-swap operations," in European Conference on Parallel Processing, 2013, pp. 595-606. [7] D. Dice and A. Kogan, "Compact NUMA-aware locks," in Proceedings of the Fourteenth EuroSys Conference 2019, 2019, pp. 1-15. [8] D. Dice and A. Kogan, "TWA--Ticket Locks Augmented with a Waiting Array," in Euro-Par 2019: Parallel Processing: 25th International Conference on Parallel and Distributed Computing, G{\"o}ttingen, Germany, August 26--30, 2019, Proceedings 25, 2019, pp. 334-345. [9] D. Dice and A. Kogan, "Fissile locks," in International Conference on Networked Systems, 2020, pp. 192-208. [10] D. Dice and A. Kogan, "Hemlock: Compact and scalable mutual exclusion," in Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021, pp. 173-183. [11] D. Dice, V. J. Marathe, and N. Shavit, "Lock cohorting: a general technique for designing NUMA locks," ACM SIGPLAN Notices, vol. 47, no. 8, pp. 247-256, 2012. [12] E. W. Dijkstra, "Cooperating Sequential Processes, Technical Report EWD123," 1965. [13] E. W. Dijkstra, "Solution of a problem in concurrent programming control," Commun. ACM, vol. 8, no. 9, p. 569, sep 1965. [Online]. Available: https://doi.org/10.1145/365559.365617. [14] U. Drepper, "Futexes are tricky," Futexes are Tricky, Red Hat Inc, Japan, vol. 4, 2005. [15] R. Dvir and G. Taubenfeld, "Mutual exclusion algorithms with constant RMR complexity and wait-free exit code," in 21st International Conference on Principles of Distributed Systems (OPODIS 2017), 2018. [16] B. Falsafi, R. Guerraoui, J. Picorel, and V. Trigonakis, "Unlocking energy," in 2016 USENIX Annual Technical Conference (USENIX ATC 16), 2016, pp. 393- 406. [17] R. Guerraoui, H. Guiroux, R. Lachaize, V. Quma, and V. Trigonakis, "Lock-- unlock: Is that all? a pragmatic analysis of locking in software systems," ACM Transactions on Computer Systems (TOCS), vol. 36, no. 1, pp. 1-149, 2019. [18] W. H. Hesselink and P. A. Buhr, "MCSH, a lock with the standard interface," ACM Transactions on Parallel Computing, vol. 10, no. 2, pp. 1-23, 2023. [19] P. Jayanti, S. Jayanti, and S. Jayanti, "Towards an ideal queue lock," in Proceedings of the 21st International Conference on Distributed Computing and Networking, 2020, pp. 1-10. [20] S. Kashyap, I. Calciu, X. Cheng, C. Min, and T. Kim, "Scalable and practical locking with shuffling," in Proceedings of the 27th ACM Symposium on Operating Systems Principles, 2019, pp. 586-599. [21] L. Lamport, "A fast mutual exclusion algorithm," ACM Transactions on Computer Systems (TOCS), vol. 5, no. 1, pp. 1-11, 1987. [22] H. Lee, Local-spin mutual exclusion algorithms on the DSM model using fetch store objects. 2003. [23] W. Long, "qspinlock: Introducing a 4-byte queue spinlock implementation," Articles/561775, 2013. [24] P. Magnusson, A. Landin, and E. Hagersten, "Queue locks on cache coherent multiprocessors," in Proceedings of 8th International Parallel Processing Symposium, 1994, pp. 165-171. [25] J. M. Mellor-Crummey and M. L. Scott, "Algorithms for scalable synchronization on shared-memory multiprocessors," ACM Transactions on Computer Systems (TOCS), vol. 9, no. 1, pp. 21-65, 1991. [26] Y. Patel, L. Yang, L. Arulraj, A. C. Arpaci-Dusseau, R. H. Arpaci-Dusseau, and M. M. Swift, "Avoiding scheduler subversion using scheduler-cooperative locks," in Proceedings of the Fifteenth European Conference on Computer Systems, 2020, pp. 1-17. [27] D. P. Reed and R. K. Kanodia, "Synchronization with eventcounts and sequencers," Communications of the ACM, vol. 22, no. 2, pp. 115-123, 1979. [28] I. Rhee, "Optimizing a FIFO, scalable spin lock using consistent memory," in 17th IEEE Real-Time Systems Symposium, 1996, pp. 106-114. [29] L. Rudolph and Z. Segall, "Dynamic decentralized cache schemes for MIMD parallel processors," in Proceedings of the 11th Annual International Symposium on Computer Architecture, 1984, pp. 340-347. [30] M. L. Scott, "Non-blocking timeout in scalable queue-based spin locks," in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 31-40. [31] M. L. Scott, Shared-memory synchronization. Morgan \& Claypool Publishers, 2013. [32] M. L. Scott and W. N. Scherer, "Scalable queue-based spin locks with timeout," ACM SIGPLAN Notices, vol. 36, no. 7, pp. 44-52, 2001. [33] L. B. Torvalds, "No nuances, just buggy code (was: related to Spinlock implementation and the Linux Scheduler)," ed: \url{https://www.realworldtech.com/forum/?threadid=189711&curpostid=189 723}, 2020. [34] T. Wang, M. Chabbi, and H. Kimura, "Be my guest: MCS lock now welcomes guests," in Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2016, pp. 1-12
Description:	碩士國立政治大學資訊科學系 109753209
Source URI:	http://thesis.lib.nccu.edu.tw/record/#G0109753209
Data Type:	thesis
Appears in Collections:	[Department of Computer Science ] Theses

Files in This Item:

File	Description	Size	Format
320901.pdf		2545Kb	Adobe PDF	0	View/Open

All items in 政大典藏 are protected by copyright, with all rights reserved.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - Feedback