請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38810
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 郭斯彥 | |
dc.contributor.author | James Ching-I Lin | en |
dc.contributor.author | 林青頤 | zh_TW |
dc.date.accessioned | 2021-06-13T16:47:17Z | - |
dc.date.available | 2010-07-04 | |
dc.date.copyright | 2005-07-04 | |
dc.date.issued | 2005 | |
dc.date.submitted | 2005-06-28 | |
dc.identifier.citation | [1] http://www.ontko.com/moss/sched/user_guide.html
[2] Anant Agarwal, Ricardo Bianchini, David Chaiken, Kirk L. Johnson, David Kranz, John Kubiatowicz, Beng-Hong Lim, Kenneth Mackenzie, and Donald Yeung. “The MIT Alewife Machine: Architecture and Performance.” In Proceedings of the 22nd International Symposium on Computer Architecture, June 1995, pp. 2-13. [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. [5] Eric A. Brewer, Chrysanthos N. Dellarocas, Adrian Colbrook, and William E. Weihl. “PROTEUS: A High-Performance Parallel-Architecture Simulator.” In Proceedings of the 12th ACM Sigmetrics and Performance Conference, June 1992. [6] E. A. Brewer and C. N. Dellarocas. “PROTEUS user documentation.” Technical Report, MIT Laboratory for Computer Science, December 1992. [7] E. Douglas Jensen, C. Douglass Locke, and Hideyuki Tokuda. “A Time-Driven Scheduling Model for Real-Time Operating Systems.” In Proceedings of the 6th IEEE Real-Time Systems Symposium, December 1985, pp. 112-122. [8] Theodore Johnson and Krishna Harathi. “A Prioritized Multiprocessor Spin Lock.” In Proceedings of the IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 9, September 1997. [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. [10] Theodore Johnson and Krishna Harathi. “Interruptible Critical Sections.” Technical Report 94-007, Department of Computer and Information Science and Engineering, University of Florida, 1994. [11] Theodore Johnson and Krishna Harathi. “The Performance of Holding Versus Releasing Locks in a Multiprogrammed Multiprocessor.” Technical Report 95-013, Department of Computer and Information Science and Engineering, University of Florida, 1995. [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. [14] John M. Mellor-Crummey and Michael L. Scott. “Synchronization Without Contention.” In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, April 1991, pp. 269-278. [15] Clifford W. Mercer and Hideyuki Tokuda. “Preemptibility in Real-Time Operating Systems.” In Proceedings of the 13th IEEE Real-Time Systems Symposium, December 1992, pp. 78-87. [16] Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne. Operating System Concepts with Java. Wiley, John & Sons, Inc., October 2003, Chapter 6. [17] Daniel Stodolsky, J. Bradley Chen, and Brian N. Bershad. “Fast Interrupt Priority Management in Operating System Kernels.” In Proceedings of the Second Usenix Workshop on Microkernels and Other Kernel Architectures, September 1993, pp. 105-110. [18] Hiroaki Takada and Ken Sakamura. “A Bounded Spin Lock Algorithm with Preemption.” Technical Report 93-02, Department of Information Science, Faculty of Science, University of Tokyo, July 1993. [19] Hiroaki Takada and Ken Sakamura. “Predictable Spin Lock Algorithms with Preemption.” In Proceedings of the 11th IEEE Workshop on Real-Time Operating Systems and Software, May 1994, pp. 2-6. [20] Hiroaki Takada and Ken Sakamura. “Real-Time Scalability of Nested Spin Locks.” In Proceedings of the 2nd Real-Time Computing Systems and Applications, October 1995, pp. 160-167. [21] Hiroaki Takada, Cai-Dong Wang, and Ken Sakamura. “Issues for Realizing a Scalable Real-Time Kernel for Function-Distributed Multiprocessors.” In Proceedings of the Work in Progress Session of the 17th IEEE Real-Time Systems Symposium, December 1996, pp. 23-26. [22] Andrew S. Tanenbaum. Modern Operating Systems, 2nd Edition. Prentice Hall, February 2001. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38810 | - |
dc.description.abstract | 從多工處理問世之後,最被關切的議題之一即是如何改善多工處理器系統的忙碌等待同步化的問題。利用分享記憶體存取以及使用回報中斷管理來協調並體現多重CPU的功能並非一件易事,故而出現許多對於旋轉鎖定的研究。本論文著眼於予即時系統使用的優先佇列旋轉鎖定的互斥演算法進行研究。由於在即時系統上使用忙碌等待同步化方法時必須考慮到其他不確定的因素,因而導致發展旋轉鎖定演算法的難度也隨之提高許多。旋轉鎖定的概念發展已久,在本論文中我們會討論搶佔性,比較處理器在佇列上的優先權以及在忙碌造成的中斷狀態下,多個CPU的優先權重新排列。在本研究中,我們會使用MOSS排程模擬軟體來模擬我們所提出的經過改良的旋轉定演算法排程並將我們的模擬結果與未經改良過的旋轉鎖定演算法進行效能的比較。未來尚須進行更多對於本研究分析、比較與改良,冀望使本研究可以到達更盡善盡美之境地。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T16:47:17Z (GMT). No. of bitstreams: 1 ntu-94-R92921124-1.pdf: 304911 bytes, checksum: aac57e12708c597b9c702efb81947f22 (MD5) Previous issue date: 2005 | en |
dc.description.tableofcontents | 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) …...…...…………….51 | |
dc.language.iso | en | |
dc.title | 可預測與搶佔優先權之旋轉鎖定演算法 | zh_TW |
dc.title | A Predictable and Preemptible, Prioritized Spin Lock
Algorithm | en |
dc.type | Thesis | |
dc.date.schoolyear | 93-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 顏嗣鈞,雷欽隆,蔡智強,袁世一 | |
dc.subject.keyword | 旋轉鎖定,互斥,中斷,擷取鎖定,釋放鎖定, | zh_TW |
dc.subject.keyword | spin lock,mutual exclusion,preemption,acquire_lock,release_lock, | en |
dc.relation.page | 57 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2005-06-28 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 297.76 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。