SEDF-FF:多核心系統之有效率的即時Linux排程器｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	許鴻平 Hung‐ping - Hsu
論文名稱：	SEDF-FF:多核心系統之有效率的即時Linux排程器 SEDF-FF:An Efficient Real-time Linux Scheduler for Multi-core Systems
指導教授：	王乃堅 Nai-jian Wang 陳雅淑 Ya-shu Chen
口試委員:	姚立德 Leeh-ter Yao 吳晉賢 Chin-hsien Wu
學位類別：	碩士 Master
系所名稱：	電資學院 - 電機工程系 Department of Electrical Engineering
論文出版年：	2010
畢業學年度：	98
語文別：	中文
論文頁數：	92
中文關鍵詞：	多處理器、調配器、排程器、即時系統.
外文關鍵詞：	Multiprocessor, dispatcher, scheduler, real-time system.
相關次數：	點閱：254 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

上一筆

由於嵌入式系統的核心數量越來越多，使得有效率的多核心系統即時排程器變成一個相當重要的研究議題。有別於以往的研究，本研究著重於多核心即時排程器的實作效能分析，並提出SEDF-FF排程器實作模型以提高工作的時間響應性。我們以Linux作業系統為平台，新增即時排程器與調度架構，並實現Global和Partitioning兩種調度架構的EDF-FF與SEDF-FF即時排程器於四核心嵌入式系統平台(ARM11 MPCore)，完整探討與測量實際環境中排程器調用所需耗費的時間複雜度。我們利用各種變異的工作組別與JPEG圖形程式進行效能評估，實驗結果顯現多核心即時排程演算法於實作模型上的問題與不可忽略的時間成本，並顯示本論文提出的SEDF-FF排程器能有效縮短工作調度的延遲時間。

With the number of cores increased on embedded systems, multi-core real-time task scheduling has been widely explored in terms of various optimization problems. With a very different goal, this research considers the implementation issues of the multi-core real-time scheduler. We propose a SEDF-FF scheduler implementation model to improve the response time of task scheduling. We also present a way to implement real-time schedulers under Linux operating system. For discussing and analyzing the timing complexity of schedulers, both global and partitioning EDF-FF schedulers are realized on the 4-core embedded system platform (ARM11 MPCore). The capability of the proposed methodology is evaluated by various task sets and JPEG decoders, for which encouraging results and scheduler overhead were presented.

摘要	 ...................................................... i
Abstract ..................................................... ii
誌謝	 .................................................... iii
目錄	 ..................................................... iv
圖表目錄	 ..................................................... vi
第一章緒論	............................................... 1
1	研究動機與目的	....................................... 1
2	研究背景與方法	....................................... 3
3	論文組織	............................................... 7
第二章   系統模型和實作議題	....................................... 8
1	即時作業系統的背景介紹	............................... 8
2	多核心處理器的排程演算法相關研究	...................... 12
3	實作上相關議題探討	...................................... 16
第三章   即時排程演算法在Linux上的實作	...................... 18
1	Linux對即時行程的支援	.............................. 19
1.1   行程控制區塊的修改	...................................... 21
1.2   系統函式的新增	...................................... 22
1.3   行程產生器	...................................... 25
2	排程器設計方式	...................................... 27
2.1   Linux於排程調用的相關函式	.............................. 27
2.2   Linux排程調用的流程	.............................. 28
2.3   嵌入EDF排程演算法	...................................... 29
3	調配器設計	...................................... 40
3.1   嵌入調配器演算法	...................................... 40
3.2   同步及非同步的處理器時間影響	.............................. 41
3.3   調配器效能改善	...................................... 48
第四章   效能評估與分析	...................................... 55
1	實驗設定	.............................................. 55
1.2   效能評估單位	...................................... 56
2     實驗結果討論	  .................................... 60
2.1   搜尋出最高優先權EDF工作之效能分析	 ..................... 60
2.2   EDF工作插入等待佇列之效能分析	  .................... 61
2.3   調配器之效能分析 ........................................ 62
2.4   觀察EDF工作之執行時間變化對排程器效能之影響 .................. 64
2.5   整體排程器效能之分析	.............................. 66
2.6   整體處理器之利用率分析	.............................. 75
3     實際案例探討：JPEG	 ..................................... 76
第五章	結論與未來展望	 ..................................... 79
1     結論	  ............................................ 79
2     未來展望	.............................................. 79
第六章	參考引用	.............................................. 81
作者簡介	...................................................... 85

                                

[1] C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multi-Programming in a Hard Real-Time Environment,“ Journal of the Association for Computing Machinery Vol. 20, No. 1, pp. 40-61, 1973.

[2] M. Garey and D. Johnson, Computers and Intractability, W.H. Freman, New York, 1979.

[3] J. M. Lopez, J. L. Diaz, M. Garcia, and D. F. Garcia, “Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems,” In Proc. 12th Euromicro Conf. Real-Time Systems, pp. 25-33, 2000.

[4] S. K. Dhall and C. L. Liu, “On a Real-Time Scheduling Problem,“ Operations Research, Vol. 26, No. 1, pp. 127-140, 1978.

[5] S. K. Baruah, J. E. Gehrke, and G. Plaxton, “Fast Scheduling of Periodic Tasks on Multiple Resources,” In International Parallel Processing Symposium, pp. 280-288, 1995.

[6] S. K. Baruah, N. Cohen, C. G. Plaxton, and D. Varvel, “Proportionate progress: a notion of fairness in resource allocation,” Algorithmica, Vol. 15, No. 6, pp. 600-625, 1996.

[7] B. Andersson, S. Baruah, and J. Jonsson, “Static-priority scheduling on multiprocessors,” In Proc. 22nd IEEE International Real-Time Systems Symposium, pp. 193-202, 2001.

[8] B. Andersson and J. Jonsson, “The Utilization Bounds of Partitioned and Pfair Static-Priority Scheduling on Multiprocessors are 50%,“ In Proc. 15th Euromicro Conf. on Real-Time Systems, pp. 33-40, 2003.

[9] B. Andersson, “Global static-priority preemptive multiprocessor scheduling with utilization bound 38%,” In Proc. 12th International Conf. on Principles of Distributed Systems, Vol. 5401, pp. 73-88, 2008.

[10] K. Shin and P. Ramanathan, “Real-Time Computing: A New Discipline of Computer Science and Engineering,” In Proc IEEE, Vol. 82, No. 1, pp. 6-24, 1994.

[11] T. P. Baker and D. Oh, “Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor Assignment,” Real Time Systems, Vol. 15, No. 2, pp. 183-192. 1998.

[12] A. Burchard, J. Liebeherr, Y. Oh, and S. Son, “New strategies for assigning real-time tasks to multiprocessor systems,” IEEE Transactions on Computers, Vol. 44, No. 12, pp. 1429-1442, 1995.

[13] Y. Oh and S. Son, “Allocating fixed-priority periodic tasks on multiprocessor systems,” Real-Time Systems, Vol. 9, No. 3, pp. 207-239, 1995.

[14] S. S’aez, J. Vila, and A. Crespo, “Using exact feasibility tests for allocating real-time tasks in multiprocessor systems,” In Proc. 10nd Euromicro Workshop on Real-Time Systems, pp. 53-60, 1998.

[15] B. Andersson and E. Tovar, “Multiprocessor Scheduling with Few Preemptions,” In Proc.12th IEEE International Conf. on Embedded and Real-Time Computing Systems and Applications, pp. 322-334, 2006.

[16] S. Kato and N. Yamasaki, “Real-Time Scheduling with Task Splitting on Multiprocessors,” In Proc. 13th IEEE International Conf. on Embedded and Real-Time Computing Systems and Applications (RTCSA), pp. 441-450, 2007.

[17] J. Calandrino, H. Leontyev, A. Block, U. Devi, and J. Anderson, “LITMUSRT: A testbed for empirically comparing real-time multiprocessor schedulers,” In Proc. 27th IEEE International Real-Time Systems Symposium, pp. 111-123, 2006.

[18] O. U. P. Zapata, P. M. Alvarez, “EDF and RM multiprocessor Scheduling algorithms: survey and performance evaluation,” CINVESTAV-IPN, Seccion de Computacion, September 18, 2004.

[19] B. Andersson, “Static Priority Scheduling in Multiprocessors,” PhD Thesis, Department of Comp.Eng, Chalmers University, 2003.

[20] S. Lauzac, R. Melhem, and D. Mosse, “Comparison of Global and Partitioning Schemes for Scheduling Rate Monotonic Tasks on a Multiprocessor,” In Proc. 10th Euromicro Workshop on Real Time Systems, pp. 188-195, 1998.

[21] G. C. Buttazzo, “Rate monotonic vs. EDF: judgment day,” Real-Time Systems, Vol. 29, No. 1, pp.5-26, 2005.

[22] B. Andersson and K. Bletsas, “Sporadic multiprocessor scheduling with few preemptions,” In Proc. 20th Euromicro Conference on real-time systems, pp. 243-252, 2008.

[23] B. Andersson, K. Bletsas, and S. Baruah, “Scheduling Arbitrary-Deadline Sporadic Task Systems on Multiprocessors,” In Proc. 29th IEEE International Real-Time Systems Symposium, pp. 385-394, 2008.

[24] H. Cho, B. Ravindran, E. Douglas Jensen, “An Optimal Real-Time Scheduling Algorithm for Multiprocessors,” In Proc. 27th IEEE International Real-Time Systems Symposium, pp. 101-110, 2006.

[25] S. Baruah, “Techniques for Multiprocessor Global Schedulability Analysis,” In Proc. 28th IEEE International Real-Time Systems Symposium, pp. 119-128, 2007.

[26] D.Faggioli and F.Checconi, “An EDF scheduling class for the Linux kernel,” European Commission under the ACTORS project (FP7-ICT-216586), 2009.

[27] D. Faggioli, M. Trimarchi, F. Checconi, M.Bertogna, and A. Mancina, “An Implementation of the Earliest Deadline First Algorithm in Linux,” In Proc. 24th ACM SAC, pp. 1984-1989, 2009.

[28] F.Checconi, T. Cucinotta, D.Faggioli, and G. Lipari, “Hierarchical Multiprocessor CPU Reservations for the Linux Kernel,” In Proc. 5th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Dublin, Ireland, 2009.

[29] T. P. Baker, “A stack-based resource allocation policy for real time processes,” In Proc. 11th IEEE International Real-Time Systems Symposium, pp. 191-200, 1990.

[30] Z. Deng, J. W. S. Liu, and J. Sun, “A scheme for scheduling hard real-time applications in open system environment,” In Proc. 9th Euromicro Workshop on Real-Time Systems, pp. 191-199, 1997.

簡易檢索 / 詳目顯示

相關論文