請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/39359完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 郭大維 | |
| dc.contributor.author | Shi-Wu Lo | en |
| dc.contributor.author | 羅習五 | zh_TW |
| dc.date.accessioned | 2021-06-13T17:26:46Z | - |
| dc.date.available | 2010-01-21 | |
| dc.date.copyright | 2005-01-21 | |
| dc.date.issued | 2005 | |
| dc.date.submitted | 2005-01-12 | |
| dc.identifier.citation | [1] N. C. Audsley, A. Burns, M. F. Richardson, and A. J. Wellings. “ Hard real-time scheduling: the deadline monotonic
approach,” In Proceeding of the Eighth RTOSS, May 1991. [2] B. Andersson and J. Jonsson. “Fixed-Priority Preemptive Multiprocessor Scheduling: To Partition or not to Partition,” In Proceeding of the 7th Inter- national Conference on Real-Time Systems and Applications, 2000. [3] E. G. Coffman, M. R. Garey and D. S. Johnson. “Approximation algorithms for bin packing: A survey,” in Approximation Algorithms for NP-Hard Problems, Dorit S. Hochbaum (editor), PWS Publishing Company, pp. 46–93. 1997. [4] Z. Deng and J. Liu and J. Sun. “A Scheme for Scheduling Hard Real-Time Applications in Open System Environment,” In Proceeding of 9th Euromicro Workshop on Real-Time Systems, pp. 191–199, Jun. 1997. [5] Z. Deng and J. W.-S. Liu. “Scheduling Real-Time Applications in an Open Environment,” In Proceeding of the 18th IEEE Real-Time Systems Symposium, IEEE Computer Society Press, Dec. 1997. [6] G. K. Dorai and D. Yeung and S. Choi. “Optimizing SMT Processors for High Single-Thread Performance,” Journal of Instruction-Level Parallelism, Vol.5, pp. 1–35, Apr. 2003. [7] G. K. Dorai, D. Yeung. “Transparent Threads: Resource Sharing in SMT Processors for High Single-Thread Performance,” In Proceeding of intl. Conf. on Parallel Architectures and Compilation Techniques (PACT’02), Sep. 2002. [8] B. Fields, J. Gast, L. Spencer. “Using Priority to Increase Throughput of Explicitly Parallel Applications on SMT,” http://www.cs.wisc.edu/~jgast/talks/smtserv.htm [9] M. R. Garey and D. S. Johnson. “Computers and Intractability–A Guide to the Theory of NP-Completeness,” W. H. Freeman And Company, New York, 1979. [10] C. E. Kozyrakis and D. A. Patterson. “A New Direction for Computer Architecture Research,” IEEE Computer Magazine, pp. 24–32, Nov. 1998. [11] C. L. Liu and Layland. “Scheduling algorithms for multiprogramming in a hard real-time environment,” Journal of the ACM, vol. 20, pp.46–61, 1973. [12] D. T. Marr, F. Binns, D. L. Hill, G. Hinton, D. A. Koufaty, J. A. Miller, M. Upton. “Hyper-Threading Technology Architecture and Microarchitecture,”Intel Technology Journal, pp. 4–15, Feb. 2002. [13] Y. K. Chen, M. Holliman, E. Debes, S. Zheltov, A. Knyazev, S. Bratanov, R. Belenov, and I. Santos. “Media Applications on Hyper-Threading Technology,” Intel Technology Journal, pp. 47–57, Feb. 2002. [14] D. Oh and T. P. Baker “Utilization bounds for n-processor rate-monotonic scheduling with static processor assignment,” Technical Report, Department of Computer Science, Florida State University, 1996. [15] S. Eggers. “Simultaneous Multithreading Project,”http://www.cs.washington.edu/research/smt/ [16] A. Snavely, D. M. Tullsen, and G. Voelker. “Symbiotic Jobscheduling with Priorities for a Simultaneous Multithreading Processor,” In Proceeding of the International Conference on Measurement and Modeling of Computer Systems, Jun. 2002. [17] R. Jain, C. Hughes, and S. Adve. “Soft real-time scheduling on simultaneous multithreaded processors,” In Proceeding of the 23rd IEEE Real-Time Systems Symposium, pp. 134–145, Dec. 2002. [18] S. Lauzac, R. Mellhem and D. Mosse. “Comparison of Global and Partitioning Schemes for Scheduling Rate Monotonic Tasks on a Multiprocessor,” In 10th Euromicro Workshop on Real Time Systems, pp. 188–195, 1998. [19] S. E. Raasch and S. K. Reinhardt. “Applications of Thread Prioritization in SMT Processors,” In Proceeding of theWorkshop on Multithreaded Execution and Compilation, 1999 [20] D. M. Tullsen, S. J. Eggers, and H. M. Levy. “Simultaneous Multithreading: Maximizing On-Chip Parallelism,” 22nd Annual International Symposium on Computer Architecture, pp. 392–403, June 1995. [21] D. M. Tullsen, S. J. Eggers, J. S. Emer, H. M. Levy, J. L. Lo, and R. L. Stamm. “Exploiting choice: Instruction fetch and issue on an implementable simultaneous multithreading processor,” In Proceeding of the 23rd Annual International Symposium on Computer Architecture, pp. 191–202, May 1996. [22] J. V. Busquets-Mataix and J. J. Serrano and A. Wellings. “Hybrid Instruction Cache Partitioning for Preemptive Real- Time Systems,” In Proceeding of the 9th Euromicro Workshop on Real Time Systems, Jun. 1997. [23] D. B. Kirk. “SMART (Strategic Memory Allocation for Real-Time Cache Design),” In Proceeding 10th Real-Time Systems Symp., pp. 229–237, Dec. 1989. [24] J. Liedtke, H. Hartig and M. Hohmuth. “OS-Controlled Cache Predictability for Real-Time Systems,” In Proceeding of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS ’97), 1997. [25] F. Mueller. “Compiler support for software-based cache partitioning,” In Proceeding ACM Workshop on Languages, Compilers and Tools for Real-Time Systems (LCTES’95), Jun. 1995. [26] S. Kaxiras, G. Narlikar, A. D. Berenbaum, and Z. Hu. “Comparing Power Consumption of an SMT and a CMP DSP for Mobile PhoneWorkloads,” In Proceeding of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems, 2001. [27] J. Seng, D. Tullsen, and G. Z. N. Cai. “Power-Sensitive Multithreaded Architecture,” In Proceeding of the 7th ASPLOS, 1996. [28] L. Hammond, B. A. Nayfeh, and K. Olukotun. “A Single- Chip Multiprocessor,” In IEEE Computer Special Issue on Billion -Transistor Processors, Sep.1997. [29] FJ Cazorla, P. MW Knijnenburg, R. Sakellariou, E. Fernandez, A. Ramirez and M. Valero. “Predictable performance in SMT processors,” In Proceeding of the first Conference on Computing Frontiers, 2004. [30] G. Thambidorai, D. Yeung, S. Choi. “Optimizing SMT Processors for High Single-Thread Performance,” Jornal of Instruction-Level Parallelism, vol. 5, 2003. [31] A. Anantaraman, K. Seth, K. Patil, E. Rotenberg, F. Mueller. “Virtual simple architecture (VISA): exceeding the complexity limit in safe real-time systems,”In Proceeding of the 30th Annual International Symposium on Computer Architecture, pp. 350–361, June 2003. [32] R. Rajkumar, L. Sha, J. Lehoczky. “Real-Time Synchronization Protocols for Multiprocessors,” Proceeding IEEE Real-Time Systems Symposium, pp. 259–269, 1988. [33] L. Sha, R. Rajkumar, J. Lehoczky. “Priority Inheritance Protocols: An Approach to Real-Time System Synchronization,” IEEE Transaction on Computers, vol. 39, pp. 1175–1185, 1990. [34] T. P. Baker. “Stack-based scheduling of real-time processes,” Journal of Real-Time Systems, vol. 3, pp. 67–99, March 1991. [35] D. M. Tullsen, J. L. Lo, Susan J. Eggers, H. M. Levy. “Supporting Fine-Grained Synchronization on a Simultaneous Multithreading Processor,” International Symposium on High Performance Computer Architecture, pp. 54–58, 1999. [36] T. W. Kuo, J. Wu, H. C. Hsih. “Real-Time Concurrency Control in a Multiprocessor Environment,” IEEE Transaction on Parallel and Distributed Systems, vol. 13, pp. 659–671, 2002. [37] Microsoft Corporation. “Windows Support for Hyper-Threading Technology,”white paper, 2003. [38] Red Hat Corporation. “Red Hat Enterprize Linux version 3 Technical Summary,” Technical Summary, Oct. 2003. [39] The Linux Kernel Archives. “The Stable Linux Kernel 2.6.9,” www.kernel.org. [40] S. W. Lo, T. W. Kuo, K. Y. Lam. “Real-Time Task Scheduling for SMT Systems,” submitted for publication. [41] I. Rhee and G. Martin. “A Scalable Realtime Synchronization Protocol for Distributed Systems,” in 16th IEEE Real-time System Symposium, 1995. [42] P. Gai, G. Lipari, M. D. Natale. “MinimizingMemory Utilization of Real-Time Task Sets in Single and Multi-Processor Systems-on-a-chip,” Proceedings of Real-Time Systems Symposium, 2001. [43] A. K. Mok. “Fundamental design problems of distributed systems for the hard real time environments,” Ph.D. dissertation, M.I.T., 1983. [44] Specification Ver 2.0. “Intelligent I/O (I2O) Architecture Specifications,” I2O SIGTM, 1999. [45] J. S. Bucy and G. R. Ganger and et al, “The DiskSim Simulation Environment Version 3.0 Reference,” Technical Report CMU-CS-03-102, Carnegie Mellon University Computer Science Department, Jan. 2003. [46] A. Silberschatz P.B. Glavin and G. Gagne. “Operating System Concepts,” 6th Edition, Addison Wesley, 2001 [47] D. M. Jacobson and J. Wilkes. “Disk scheduling algorithms based on rotational position,” Technical Report HPL-CSP-91- 7, Hewlett-Packard Laboratories, Mar. 1991. [48] M. Andrews, M. A. Bender, L. Zhang. “New Algorithms for the Disk Scheduling Problem,” Proceeding on the 37th Annual Symposium on Foundations of Computer Science, pp. 550–559, Oct. 1996. [49] ZDNet Corp. http://www.zdnet.com/etestinglabs/stories/benchmarks/0,8829,2326114,00.html [50] K. Ramamritham. “Real-time Databases,” International Journal of Distributed and Parallel Databases, vol. 1, pp. 199– 226, 1993. [51] O. Ulusoy. “Real-Time Data Management for Mobile Computing,” Proceedings of International Workshop on Issues and Applications of Database Technology (IADT’98), July 1998. [52] S. Thomas, S. Seshadri and J. R. Haritsa. “Integrating Standard Transactionsin Real-Time Database Systems,” Information Systems, vol. 21, pp. 3–28, 1996. [53] O. Ulusoy, and G.G. Belford. “Real-time Transaction Scheduling in Database Systems,” Information Systems, vol. 18, pp. 559–580, 1993. [54] R. K. Abbott and H. Garcia-Molina. ”Scheduling I/O Requests with Deadlines: a Performance Evaluation,” IEEE 11th Real -Time Systems Symposium, pp. 113–124, Dec. 1990. [55] J. Bruno, J. Brustoloni, E. Gabber, B. Ozden, and A. Silberschatz. “Disk Scheduling with Quality of Service Guarantees, ” IEEE International Conference on Multimedia Computing and Systems, pp. 400–405, Jun. 1999. [56] R.-I. Chang, W.-K. Shih, and R.-C. Chang. “Deadline-Modification-SCAN with Maximum-Scannable-Groups for Multimedia Real-Time Disk Scheduling,” IEEE 19th Real-Time Systems Symposium, pp. 40–49, Dec. 1998. [57] S. Chen, J. A. Stankovic, J. F. Kurose, and D. F. Towsley. “Performance Evaluation of Two New Disk Scheduling Algorithms for Real-Time Systems,”Journal of Real-Time Systems, vol. 3, pp. 307–336. 1991. [58] P. Chang, H. Jin, X. Zhou, Q. Chen, and J. Zhang. “HUST-RAID: High Performance RAID in Real-Time System,” IEEE Pacific Rim Conference on Communication, Computers, and signal Processing, pp. 59–62, Aug. 1999. [59] K. Hwang and H. Shih. “Real-Time Disk Scheduling Based on Urgent Group and Shortest Seek Time First,” the 5th Euromicro Workshop on Real-Time Systems, pp. 124–130, Jun. 1993. [60] A. L. N. Reddy and J. C. Wyllie. “I/O Issues in Multimedia System,” IEEE Transactions on Computers, vol. 27, pp. 69– 74, 1994. [61] G. Weikum and P. Zabback. “Tuning of Stripping Units in Disk-Array-Based File Systems,” Interoperability in Multidatabase Systems(IMS), pp. 280–287, 1991. [62] A. L. N. Reddy and J. Wyllie. “Disk Scheduling in Multimedia I/O System,”In Proceedings of ACM Multimedia, pp. 225– 234, Aug. 1993. [63] C. Ruemmler and J.Wilkes. “An Introduction to Disk Drive Modeling,” IEEE Computer, vol.27, pp. 17–29, 1994 [64] Maxtor Corp. http://www.maxtor.com/en/products/scsi/atlas 10k family/index.htm [65] P. S. Yu, M. S. Chen, and D. D. Kandlur. “Design and Analysis of a Grouped Sweeping Scheme for Multimedia Data,” 3rd International Workshop on Network and Operating Systems Support for Digital Audio and Video, pp. 38–49, Nov. 1992. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/39359 | - |
| dc.description.abstract | 近幾年來支援「服務品質」已經成為各種電腦系統的主要特色。這本論文以「即時排程問題」的角度探討服務品質支援，我們的討論包含了中央處理器（處理器）及「獨立（/非昂貴）磁碟多重陣列」（硬碟陣列），協調這些元件（處理器及磁碟陣列）以提供一個整合型服務。我們首先討論到的是「同時多執行緒」處理器（多執行緒處理器）架構上的即時資源排程問題。這樣的架構已經廣泛的使用在各種系統平台上。更具體來說，我們提出在多執行緒處理器上的即時工作排程，我們所討論的每個工作都有工作期限。此外我們也探討如果這些工作可能存取共享資料那麼這些工作該如何同步。我們隨後所探討的是：以磁碟陣列為基礎的輸出入磁碟系統組件上的即時要求排程，這排程的目的是減少錯失比率及改善平均回覆時間。我們考慮磁碟間所可能發生的資料相依性以降低回覆時間以提供更好的系統服務。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T17:26:46Z (GMT). No. of bitstreams: 1 ntu-94-D89922015-1.pdf: 568345 bytes, checksum: d0b6dea28e043ab5d7673286a8655213 (MD5) Previous issue date: 2005 | en |
| dc.description.tableofcontents | 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 101 | |
| dc.language.iso | en | |
| dc.subject | 磁碟陣列 | zh_TW |
| dc.subject | 即時工作排程 | zh_TW |
| dc.subject | 多執行緒處理器 | zh_TW |
| dc.subject | disk array | en |
| dc.subject | real-time task scheduling | en |
| dc.subject | simultaneously multithreading | en |
| dc.title | 具服務品質保證之資源排程 | zh_TW |
| dc.title | Resource Scheduling with Quality of Service Guarantees | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 93-1 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 施吉昇,逄愛君,陳添福,薛智文,劉邦鋒,楊佳玲,林風 | |
| dc.subject.keyword | 即時工作排程,多執行緒處理器,磁碟陣列, | zh_TW |
| dc.subject.keyword | disk array,simultaneously multithreading,real-time task scheduling, | en |
| dc.relation.page | 106 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2005-01-12 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-94-1.pdf 未授權公開取用 | 555.02 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。