郭大維臺灣大學：資訊工程學研究所羅習五Lo, Shi-WuShi-WuLo2007-11-262018-07-052007-11-262018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/54097近幾年來支援「服務品質」已經成為各種電腦系統的主要特色。這本論文以「即時排程問題」的角度探討服務品質支援，我們的討論包含了中央處理器（處理器）及「獨立（/非昂貴）磁碟多重陣列」（硬碟陣列），協調這些元件（處理器及磁碟陣列）以提供一個整合型服務。我們首先討論到的是「同時多執行緒」處理器（多執行緒處理器）架構上的即時資源排程問題。這樣的架構已經廣泛的使用在各種系統平台上。更具體來說，我們提出在多執行緒處理器上的即時工作排程，我們所討論的每個工作都有工作期限。此外我們也探討如果這些工作可能存取共享資料那麼這些工作該如何同步。我們隨後所探討的是：以磁碟陣列為基礎的輸出入磁碟系統組件上的即時要求排程，這排程的目的是減少錯失比率及改善平均回覆時間。我們考慮磁碟間所可能發生的資料相依性以降低回覆時間以提供更好的系統服務。Quality-of-Service (QoS) support has become important features for various computer systems in recent years. This thesis explores real-time resource scheduling issues for QoS support starting from a central processing unit (CPU) to redundant inexpensive/independent array disks (RAID) together in providing collaborative services. We first exploit real-time resource scheduling issues for computer systems with an advanced simultaneously multithreading (SMT) architecture, that are widely adopted in many system platforms. Specifically, we propose real-time task scheduling algorithms for SMT processors with the considerations of timing constraints and task synchronization to control the access of shared data. We then conduct a performance study on real-time request scheduling for disk-array-based I/O module disk systems to minimize the miss ratio and to improve the average response time. We consider potential data dependency among disks with an objective to minimize response time such that better system services are possible.1 Introduction 8 1.1 Real-Time Scheduling for Simultaneous Multithreading Processors . 8 1.1.1 Simultaneous Multithreading . . . . . . . . . . . . . . . . . 8 1.1.2 Scheduling and Synchronization Problems . . . . . . . . . . 10 1.2 Time-Constrained Scheduling for Multiple I/O Devices . . . . . . . 13 1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . 15 2 Priority Driven Scheduling for SimultaneouslyMultithreading Proces- sors 16 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.1 The Processor Models . . . . . . . . . . . . . . . . . . . . . 17 2.2.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Real-Time SMT Scheduling . . . . . . . . . . . . . . . . . . . . . . 22 2.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3.2 Real-Time SMT Scheduling Algorithms . . . . . . . . . . . . 23 2.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4.1 Performance Metrics and Data Sets . . . . . . . . . . . . . . 42 2.4.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . 44 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3 Data Sharing Protocols for SimultaneouslyMultithreading Proces- sors 48 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3 LP-Time Inheritance Protocols . . . . . . . . . . . . . . . . . . . . 56 3.3.1 LP-Time Inheritance Protocol (LPTIP) - Basic Approach . . 56 3.3.2 The Properties of LPTIP . . . . . . . . . . . . . . . . . . . . 60 3.3.3 LP-Time Inheritance Protocol with Priority Cap (LPTIP/PC) 65 3.3.4 The Definition of the LP-Time Inheritance Protocol with a Priority Cap . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4 Time-Constrained Scheduling for Multiple I/O Devices: Perfor- mance Evaluation 72 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.2 The Multi-Disk System . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.3 The Real-Time Scheduling Algorithm in Multi-Disks . . . . . . . . 74 4.4 On-The-Way Scheduling and Pre-fetching . . . . . . . . . . . . . . . 78 4.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 83 4.5.1 Performance Metrics and Data Sets . . . . . . . . . . . . . . 83 4.5.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . 87 4 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5 Conclusion and Future Work 95 A The TH-Selection Algorithm 97 B The Intel Pentium-4 Processor 98 Bibliography 101Bibliography 101568345 bytesapplication/pdfen-US即時工作排程多執行緒處理器磁碟陣列disk arraysimultaneously multithreadingreal-time task schedulingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54097/1/ntu-94-D89922015-1.pdf