郭斯彥臺灣大學：電機工程學研究所林青頤Lin, James Ching-IJames Ching-ILin2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53172從多工處理問世之後，最被關切的議題之一即是如何改善多工處理器系統的忙碌等待同步化的問題。利用分享記憶體存取以及使用回報中斷管理來協調並體現多重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.Table of Contents ……...………………………………………………………………………….3 List of Figures ……………………………………………………………………………………..5 Abstract …………...………………………………………………………………………………7 Chapter 1 …..……………………………………………………………………………………..9 Introduction …………...…………………………………………………………………………..9 Chapter 2 …..…………………………………………………………………………………....13 Previous Works ……...…………………………………………………………………………..13 2.1 Previous Spin Lock Algorithms ………………………………………………….13 2.2 MCS Spin Lock Algorithm ...……………………………………………………17 2.3 Takada and Sakamura’s Spin Lock Algorithm ……...…………………………..18 2.4 Prioritized Multiprocessor Spin Lock ……………………………………………20 2.5 Interruptible Scheduling Contract Algorithm ……………………………………23 Chapter 3 …..……………………………………………………………………………………25 The Proposed Algorithm …..……………………………………………………………………25 3.1 Overview …..……………………………………………………………………25 3.2 Preemption …..………………………………………………………………….28 3.3 Data Structures ……..…………………………………………………………...31 3.4 Aquire_lock Operation ………………………………………………………….34 3.5 Release_lock Operation …..……………………………………………………39 3.6 Correctness of the Algorithm …...…………………………………………….…40 Chapter 4 …..……………………………………………………………………………………41 Experimental Procedures …...…………………………………………………………………...41 4.1 Background …...…………………………………………………………………41 4.2 Procedures …...……………………………………………………………….......42 4.3 Measurement Parameters …...…………………………………………………...43 Chapter 5 …..……………………………………………………………………………………45 Experimental Results ……...…………………………………………………………………….45 5.1 Introduction ...……………………………………………………………………45 5.2 Results ……………………………………………………………………………45 5.3 Analysis ……...…………………………………………………………………..52 Chapter 6 …..……………………………………………………………………………………53 Conclusion ...……………………………………………………………………………………53 References ………………………………………………………………………………………..55 List of Figures Figure 1.1: A function-distributed multiprocessor system ...………………..……………………9 Figure 2.1: The Compare_and_swap algorithm for spin locks ….……….……………………...16 Figure 2.2: Constructing interruptible algorithm B by scheduling contract algorithm A on three Processors …..…..…………………..……………………………………………...23 Figure 3.1: The Preemption State Flow Diagram …..…….……………………………………29 Figure 3.2: The different transitions in the state flow diagram ……….…………………………30 Figure 3.3: The Record Structure for the algorithm ……………………………………………32 Figure 3.4: The data structures necessary for the algorithm ...……….….……………………...33 Figure 3.5: The Queue Data Structure of the algorithm ………………………………………..33 Figure 3.6: The different stages in the Acquire_lock operation ………………………………..35 Figure 3.7: The Acquire_lock operation procedure ……...…………………………………….37 Figure 3.8: The Release_lock operation procedure …..………….…………………………….39 Figure 4.1: The BBN Butterfly 1 …...…………………………………………………………...41 Figure 4.2: The Sequent Symmetry Model B …………….……………………………………41 Figure 5.1: Prioritized Preemptive Scheduling Algorithm (Average Times) …….……………47 Figure 5.2: Prioritized Preemptive Scheduling Algorithm (Worst-case Times) ...…...…………47 Figure 5.3: Prioritized Non-Preemptive Scheduling Algorithm (Average Times) ...……………49 Figure 5.4: Prioritized Non-Preemptive Scheduling Algorithm (Worst-case Times) ……..…...49 Figure 5.5: FIFO Preemptive Scheduling Algorithm (Average Times) …..……………………51 Figure 5.6: FIFO Preemptive Scheduling Algorithm (Worst-case Times) …...…...…………….51304911 bytesapplication/pdfen-US旋轉鎖定互斥中斷擷取鎖定釋放鎖定spin lockmutual exclusionpreemptionacquire_lockrelease_lockthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53172/1/ntu-94-R92921124-1.pdf