跳到主要內容

臺灣博碩士論文加值系統

(44.220.62.183) 您好!臺灣時間:2024/02/29 04:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林昀葦
研究生(外文):Yun-Wei Lin
論文名稱:多處理器系統下的「最小至最大權值問題」之公平排程演算法
論文名稱(外文):Min-to-Max-Weight Fair Scheduling Algorithm on Multiprocessors
指導教授:石維寬石維寬引用關係
指導教授(外文):Wei-Kuan Shih
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:45
中文關鍵詞:多處理器系統公平性排班演算法最小權值最大權值近似最優化
外文關鍵詞:MultiprocessorFair Scheduling AlgorithmMinimum WeightMaximum WeightNear-Optimal
相關次數:
  • 被引用被引用:0
  • 點閱點閱:154
  • 評分評分:
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
隨著Multiprocessor系統的日漸普及,如何針對在其中執行的Task做Schedule,也逐漸成為一個重要的議題;為了確保這些Task都能獲得公平的待遇,Schedule的Fairness必須被考慮。Task對執行量的需求,可以使用weight=(E/P)來表示,其中P是Task的Period長度,E則是此Period長度中Task應該要執行的時間。給定每個Task一個Minimum Weight 和一個Maximum Weight,所謂的「Min-to-Max-Weight Fairness」就是在Multiprocessor的環境下,要求每個Task的執行時間,都得被限制在由此下限和上限所導出的範圍內。
在先前的相關研究中,「Min-to-Max-Weight Fairness」從未被明確定義過,也沒有Optimal(或Near-Optimal)的Scheduling Algorithm可以滿足它。此外,先前的研究成果也無法確保每個Task都有執行到其理想上限值的可能;也就是說,每個Task的實際可能最大執行時間,不但無法保證與其理想上限值相等,其間的差距也從未被明確定義過。
此篇論文明確定義了「Min-to-Max-Weight Fairness」,並針對之提出一個Near-Optimal的Scheduling Algorithm,同時提供相關的証明來佐證。此Algorithm包含了三個步驟:Imprecise Computation分解、Network Flow Graph轉換、Schedule建構;這三步驟能夠確保每個Task的實際可能最大執行時間,都會等於其理想上限值(或最多少1)。除了這個暫時性的「少1」情況,其餘所使用的方法都能夠Optimally地減少Task的實際執行時間與其理想上限值間的差距;因此,我們提出的Scheduling Algorithm不但能永遠滿足「Min-to-Max-Weight Fairness」,其與Optimal的情況相比,最多也只會差1而已。
Relate a task to a weight = (E/P), where E is its required execution during its period length P. Min-to-Max-Weight Fairness is a fair scheduling issue on multiprocessors, defining each task’s execution as a value within a specified range (implied by its minimum weight and maximum weight). In prior works, this problem was stated as a result rather than a specific problem to solve. No optimal (or near-optimal) scheduling algorithm for Min-to-Max-Weight Fairness was proposed, in the sense of minimizing the difference between tasks’ actual execution time and their maximum bounds. Moreover, tasks were not guaranteed to have the chance to reach their own maximum bounds. In other words, the utmost values of tasks’ actual execution were neither guaranteed nor defined with formal descriptions.
In this paper, we formally define Min-to-Max-Weight Fairness, propose a near-optimal scheduling algorithm for it, and provide related proofs. Our algorithm contains three steps: imprecise computation decomposition, network flow graph formulation, and schedule construction. Comprising these three steps, our algorithm always schedule tasks to satisfy Min-to-Max-Weight Fairness, and assure each task of a possible utmost execution time equal to (or 1 unit less than) its maximum bound. Despite this 1-unit limitation, our algorithm optimally minimizes the difference between tasks’ actual execution time and their maximum bounds. In conclusion, we provide a near-optimal algorithm with 1 unit difference at most.
List of Figures...................................IV
Abstract...........................................1
Chapter 1. Introduction................................2
Chapter 2. Preliminaries...............................7
2.1. P-fairness and ER-fairness....................7
2.2. QR-fairness...................................9
2.3. Min-to-Max-Weight Fairness...................11
Chapter 3. Scheduling Algorithms......................12
3.1. Imprecise Computation Decomposition............12
3.1.1. Windows Evaluation of Mandatory Subtasks...13
3.1.2. Windows Evaluation of Optional Subtasks....16
3.1.3. Example....................................23
3.2. Network Flow Graph Formulation.................26
3.2.1. The basic Network Flow Graph G(ε)..........26
3.2.2. The complete Network Flow Graph G(ε)’.....29
3.3. Schedule Construction..........................33
3.4. Complexity.....................................35
Chapter 4. Proof......................................36
4.1. Near-Optimal windows settings..................36
4.2. Correctness of imprecise computation...........40
4.3. Equivalence of Network Flow Graph..............41
Chapter 5. Conclusion.................................43
Reference .............................................44
[1] S. Baruah, N. Cohen, C.G. Plaxton, and D. Varvel, “Proportionate progress: A notion of fairness in resource allocation,” Algorithmica, 15:600–625, 1996.
[2] S. Baruah, J. Gehrke, and C.G. Plaxton, “Fast scheduling of periodic tasks on multiple resources,” In Proceedings of the 9th International Parallel Processing Symposium, pages 280–288, April 1995.
[3] J. Anderson and A. Srinivasan, “Early-release fair scheduling,” In Proceedings of the 12th Euromicro Conference on Real-Time Systems, pages 35–43, June 2000.
[4] J. Anderson and A. Srinivasan, “Mixed Pfair/ERfair scheduling of asynchronous periodic tasks,” In Proceedings of the 13th Euromicro Conference on Real-Time Systems, pages 76–85, June 2001.
[5] J. Anderson, A. Block, and A. Srinivasan, “Quick Release Fair Scheduling,” Proceedings of the 24th IEEE Real-time Systems Symposium, IEEE Computer Society Press, pages 130-141, December 2003.
[6] A. Chandra, M. Adler, P. Goyal, and P. Shenoy, “Surplus fair scheduling: A proportional-share CPU scheduling algorithm for symmetric multiprocessors,” In Proceedings of the Fourth Symposium on Operating System Design and Implementation (OSDI 2000), pages 45–58, October 2000.
[7] Wei-Kuan Shih, Jane W. S. Liu, Jen-Yao Chung, and Donald W. Gillies, “Scheduling Tasks with Ready Times and Deadlines to Minimize Average Error,” Technical Report No. UIUCDCS-R-89-1478, Department of Computer Science, University of Illinois, 1988, also in ACM Operating Systems Review, July 1989.
[8] J. Blazewicz and G. Finke, "Minimizing mean weighted execution time loss on identical and uniform processors", Information Processing Letters, Vol. 24, pp. 259-263, March 1987.
[9] Tarjan, R. E., Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Pennsylvania, 1983.
[10] R. McNaughton, "Scheduling with deadlines and loss functions," Management Science, Vol. 12, pp. 1-12, 1959.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top