可預測與搶佔優先權之旋轉鎖定演算法

從多工處理問世之後，最被關切的議題之一即是如何改善多工處理器系統的忙碌等待同步化的問題。利用分享記憶體存取以及使用回報中斷管理來協調並體現多重CPU的功能並非一件易事，故而出現許多對於旋轉鎖定的研究。本論文著眼於予即時系統使用的優先佇列旋轉鎖定的互斥演算法進行研究。由於在即時系統上使用忙碌等待同步化方法時必須考慮到其他不確定的因素，因而導致發展旋轉鎖定演算法的難度也隨之提高許多。旋轉鎖定的概念發展已久，在本論文中我們會討論搶佔性，比較處理器在佇列上的優先權以及在忙碌造成的中斷狀態下，多個CPU的優先權重新排列。在本研究中，我們會使用MOSS排程模擬軟體來模擬我們所提出的經過改良的旋轉定演算法排程並將我們的模擬結果與未經改良過的旋轉鎖定演算法進行效能的比較。未來尚須進行更多對於本研究分析、比較與改良，冀望使本研究可以到達更盡善盡美之境地。

關鍵字

旋轉鎖定；互斥；中斷；擷取鎖定；釋放鎖定

並列摘要

Since the inception of multiprocessing, one of the biggest concerns have been regarding how to improve the busy-wait synchronization techniques of multiprocessor systems. Incorporating multiple CPUs with shared memory access and coordinating them with their interrupt response management has been difficult to do and has led to a wide array of research regarding spin locks. This paper focuses on a spin lock algorithm that is based upon a prioritized queuing spin lock mutual exclusion algorithm for real-time systems. Busy-wait synchronization techniques must take into account other factors when it is designed for real-time systems, thus adding yet another aspect into the difficulty of designing such algorithms. There are many similar previous works of spin lock algorithms that this paper will make use of. All of them will be briefly discussed in detail. Some ideas to be discussed include preemptibility, implementing a spin-lock queue that is predictable based upon higher priority using a pointer to the lock holder, comparing the priority of the processors wishing to acquire the lock to ensure that higher priority processors are processed first, and updating the queue based on priorities while the processor is busy servicing interrupts. The proposed algorithm’s scheduling concept will be simulated using the MOSS Scheduling Simulator to show the efficiency of this algorithm as compared to the previous algorithms this paper is based upon. A conclusion will be reached regarding the effectiveness of the proposed algorithm as well as suggestions for further research. This paper will be organized in the following fashion. Chapter 1 will be an overview of the concept and purpose. Chapter 2 will review in some detail some of the previous algorithms that have inspired this paper. Chapter 3 will discuss in detail the proposed algorithm. Chapter 4 will discuss the experimental procedures. Chapter 5 will compare the experimental results. Finally, Chapter 6 will be the conclusion of this paper.

並列關鍵字

spin lock ； mutual exclusion ； preemption ； acquire_lock ； release_lock

參考文獻

[3] Daniel S. Bernstein, Shlomo Zilberstein, Theodore Perkins, and Lev Finkelstein. “Scheduling Contract Algorithms on Multiple Processors.” In Proceedings of the 18th National Conference on Artificial Intelligence, 2002.

[4] Brian N. Bershad. “Practical Considerations for Non-Blocking Concurrent Objects.” In Proceedings of the 13th International Conference on Distributed Computing Systems, May 1993, pp. 264-274.

[9] Theodore Johnson and Krishna Harathi. “A Simple Correctness Proof of the MCS Contention-Free Lock.” Information Processing Letters, Vol. 48, No. 5, 1993, pp. 215-220.

[12] E. P. Markatos and T. J. LeBlanc. “Multiprocessor Synchronization Primitives With Priorities.” In Proceedings of the 8th IEEE Workshop on Real-Time Operating Systems and Software, 1991, pp. 148-157.

[13] John M. Mellor-Crummey and Michael L. Scott. “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.” ACM Transactions on Computer Systems, Vol. 9, No. 1, February 1991, pp. 21-65.

國際替代計量

可預測與搶佔優先權之旋轉鎖定演算法

全文下載

主題瀏覽