跳到主要內容

臺灣博碩士論文加值系統

(44.200.194.255) 您好!臺灣時間:2024/07/19 04:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張明鈿
論文名稱:在異質多處理器上針對即時系統具有容錯能力之動態排程演算法
論文名稱(外文):A Fault-Tolerant Dynamic Scheduling Algorithm for Real-Time Systems on Heterogeneous Multiprocessor
指導教授:陳正陳正引用關係
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:48
中文關鍵詞:異質多處理器即時系統容錯動態排程演算法
外文關鍵詞:Heterogeneous multiprocessorReal-time systemFault-tolerantdynamic task scheduling algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:158
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
即時系統已經廣泛地被應用在許多需要嚴格地符合時間要求的環境中。在即時系統中的工作必須在時間限制內完成,否則可能造成嚴重的後果。由於對穩定性的高度要求,容錯能力也是即時系統所必須具備的。由於工作在進入系統後才能開始被排程,因此需要的是動態的排程演算法。本論文即是提出一個在異質多處理器上針對即時系統具有容錯能力的動態排程演算法。我們將會提出一個以工作可排程的時間與所需要的執行時間作為考量的heuristic函式,來決定工作排程的優先順序。針對為達到容錯目的所用的backup,我們也提出新的排程策略,稱為MNO。經由動態地模擬一個即時系統,結果顯示我們提出的方法能夠決定出更恰當的排程順序,而且挪出更多的可排程時間給後來的工作,使得較多的工作能夠在時間限制前完成執行。並且在不同的環境中,不需要搭配任何參數也能得到較好的結果。
Real-time systems are being increasingly used in several applications which are time critical. Tasks corresponding to these applications have deadlines to be met. Fault-tolerance is an important requirement of such systems, due to the catastrophic consequences of not tolerating faults. In this thesis, we propose an algorithm do dynamically schedule arriving real-time tasks with PB fault-tolerant requirement on to a set of heterogeneous multiprocessor. Our algorithm, named density first with minimum non-overlap scheduling algorithm (DNA), proposes two performance improving techniques. First, a new heuristic function, called density, takes account of the needed computation time and schedulable time of a task. The task with the maximum density value will be given the highest priority. Second, the MNO strategy for backup scheduling will minimize the time reserved for backups. In the result of dynamic simulation, we can find that our algorithm has fewer rejected tasks and more general and suitable for any kind of environment.
摘要……………………………………………………………………………………i Abstract………………………………………………………………………………..ii Acknowledgments………………………………..…………………………………...iii Table of Contents…..…………………………………………………………………iv List of Figures.………………………………………………………………………..vi List of Tables.………………………………………………………………………...vii Chapter 1. Introduction………………………………………………………………..1 Chapter 2. System Model and Fundamental Background…………………………......4 2.1 System Model and Assumptions……………………………………………..4 2.1.1 Task Model……………………………………………………………4 2.1.2 Scheduler Model……………………………………………………...5 2.1.3 Fault Tolerance Model………………………………………………..6 2.2 Related Work…………………………………………………………………7 Chapter 3. Density First with Minimum Non-overlap Scheduling Algorithm……….12 3.1 A New Heuristic Function…………………………………………………..12 3.2 Minimum Non-Overlap (MNO) for Backup………………………………..18 3.3 The DNA Algorithm………………………………………………………...20 Chapter 4. Simulation and Performance Evaluations………………………………...24 4.1 Simulation Construction…………………………………………………….24 4.1.1 Task Generator……………………………………………………….24 4.1.2 Simulator…………………………………………………………….26 4.2 Performance Evaluations……………………………………………………28 4.2.1 The Effect of Task Load………………………………………..........29 4.2.2 The Effect of Laxity…………………………………………………29 4.2.3 The Effect of the Number of Processor……………………………...31 4.2.4 The Effect of Fault Probability………………………………………31 Chapter 5. Conclusion and Future Work……………………………………………..34 5.1 Conclusion…………………………………………………………………..34
5.2 Future Work…………………………………………………………………35 Bibliographies……………………………………………………………………......36
[1] Krithi Ramamritham, John A. Stankovic, and Perng-fei Shiah, "Efficient Scheduling Algorithms for Real-time Multiprocessor Systems," IEEE Trans. on Parallel and Distributed Systems, vol. 1, no. 2, pp. 184-194, Apr. 1990.
[2] G. Manimaran and C. Siva Ram Murthy, "A Fault-tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-time Systems and Its Analysis," IEEE Trans. on Parallel and Distributed Systems, vol. 9, no. 11, pp. 1137-1152, Nov. 1998.
[3] Sunondo Ghosh, Rami Melhem, and Daniel Mosse, "Fault-tolerance Through Scheduling of Aperiodic Tasks in Hard Real-time Multiprocessor Systems," IEEE Trans. on Parallel and Distributed Systems, vol. 8, no. 3, pp. 272-284, Mar. 1997.
[4] Xiao Qin, Hong Jiang, and David R. Swanson, "An Efficient Fault-tolerant Scheduling Algorithm for Real-time Tasks with Precedence Constraints in Heterogeneous Systems," Proc. International Conference on Parallel Processing, pp. 360-368, 2002.
[5] J.W.S. Liu, W.K. Shih, K.J. Lin, R. Bettati, and J.Y. Chung, “Imprecise Computations,” Proc. IEEE, vol. 82, no. 1, pp. 83-94, Jan. 1994.
[6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman, 1979.
[7] M.L. Dertouzos and A.K. Mok, “Multiprocessor On-Line Scheduling of Hard Real-Time Tasks,” IEEE Trans. Software Eng., vol. 15, no. 12, pp. 1,497-1,506, Dec. 1989.
[8] Yi-Hsuan Lee and Cheng Chen, “Effective Fault-tolerant Scheduling Algorithm for Real-time Tasks on Heterogeneous Systems,” Proc. National Computer Symposium, pp. 302, 2003.
[9] C.M. Krishna and K.G. Shin, Real-Time Systems, McGraw-Hill Int’l, 1997.
[10] Y. Oh and S. Son, “Multiprocessor support for Real-Time Fault-Tolerant Scheduling,”Proc. IEEE Workshop Architectural Aspects of Real-Time Systems, pp. 76-80, Dec. 1991.
[11] T. –Y. Yen and W. Wolf, Hardware-Software Co-Synthesis of Distributed Embedded Systems, Kluwer Academic Publishers, 1996.
[12] A.K. Mok, Fundamental Design Problems of Distributed Systems for Hard Real-Time Environments, Doctoral Thesis TR-297, MIT, Laboratory for Computer Science, Cambridge, Mass., 1983.
[13] Chi-Sheng Shih and Jane W.S. Liu, “State-Dependent Deadline Scheduling,” Proc. IEEE Real-Time Systems Symposium, pp. 3-14, Dec. 2002.
[14] K. Ramamritham and J.A. Stankovic, “Scheduling Algorithms and Operating Systems Support for Real-Time Systems,” Proc. IEEE, vol. 82, no. 1, pp. 55-67, Jan. 1994.
[15] L.V. Mancini, “Modular Redundancy in a Message Passing System,” IEEE Trans. Software Eng., vol. 12, no. 1, pp. 79-86, Jan. 1986.
[16] K.G. Shin and P. Ramanathan, “Real-Time Computing: A New Discipline of Computer Science and Engineering,” Proc. IEEE, vol. 82, no. 1, pp. 6-24, Jan. 1994.
[17] Averill Law and W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill, 1999.
[18] Babak Hamidzadeh and Yacine Atif, “Dynamic Scheduling of Real-time Tasks, by Assignment”, IEEE Concurrency, vol. 6, issue 4, pp. 14-25, Oct. – Dec. 1998.
[19] T. Tsuchiya, Y. Kakuda, and T. Kikuno, “A new Fault-Tolerant Scheduling Technique for Real-Time Multiprocessor Systems,” Proc. 2nd International Workshop on Real-Time Computing and Applications, pp. 197-202, Oct. 1995.
[20] R. Al-Omari, Arun K. Somani, and G. Manimaran, “A New Fault-tolerant Technique for Improving Schedulability in Multiprocessor Real-time Systems”, Proc. 15th International Parallel and Distributed Processing Symposium, pp. 32-39, Apr. 2001.
[21] R. Al-Omari, G. Manimaran, and Arun K. Somani, “An Efficient Backup-overloading forFault-tolerant Scheduling of Real-time Tasks”, Proc. IEEE Workshop on Fault-tolerant Parallel and Distributed Systems, pp. 1291-1295, 2000.
[22] A. Girault, H. Kalla, M. Sighireanu, and Y. Sorel, “An Algorithm for Automatically Obtaining Distributed and Fault-Tolerant Static Schedules,” Proc. International Conference on Dependable Systems and Networks, pp. 159-168. June 2003.
[23] Y. Sorel, “Massively Parallel Computing Systems with Real Time Constraints ‘The Algorithm Architecture Adequation’ Methodology,” Proc. Massively Parallel Computing Systems, pp. 44-53, May 1994.
[24] A. Girault, C. Lavarenne, M. Sighireanu, and Y. Sorel, “Fault-Tolerant Static Scheduling for Real-Time Distributed Embedded Systems,” Proc. 21st International Conference on Distributed Computing Systems, pp. 695-698, Apr. 2001.
[25] Y. Oh and S. H. Son, “Scheduling Real-Time Tasks for Dependability,” J. Operational Research Society, vol. 48, no. 6, pp. 629-639, Jun. 1997.
[26] Chi-Sheng Shih, Lui Sha, and Jane W.S. Liu, “Scheduling Tasks with Variable Deadlines,” Proc. 7th Real-Time Technology and Applications Symposium, pp. 120-122, 2001.
[27] G. Manimaran, C. Siva Ram Murthy, M. Vijay, and K. Ramamritham, “New Algorithms for Resource Reclaiming form Precedence Constrained Tasks in Multiprocessor Real-Time Systems,” J. Parallel and Distributed Computing, vol. 44, no. 2, pp. 123-132, Aug. 1997.
[28] I. Ekmecic, I. Tartalja, and V. Milutinovic, “A Survey of Heterogeneous Computing: Concepts and Systemds,” Proc. IEEE, vol. 84, pp. 1127-1144, Aug. 1996.
[29] B.W. Johnson, Design and Analysis of Fault Tolerant Digital Systems, Addison Wesley, 1989.
[30] C.M. Krishna and K.G. Shin, “On Scheduling Tasks With Quick Recovery From Failure,” IEEE Trans. Computers, vol. 35, no. 5, pp. 448-455, 1986.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top