簡易檢索 / 詳目顯示
| 研究生： |
吳邁龍 Wu, Mai-Lung |
|---|---|
| 論文名稱： |
已知與未知工作量排程最佳化工作流程時間的ℓ2範數 Optimizing the ℓ2-Norm of Job Flow Time with Clairvoyant and Non-Clairvoyant Schedules |
| 指導教授： | 郭桐惟 |
| 口試委員: |
孫士勝
王超 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
資訊學院 - 資訊科學系 Department of Computer Science |
| 論文出版年： | 2026 |
| 畢業學年度： | 114 |
| 語文別： | 英文 |
| 論文頁數： | 48 |
| 中文關鍵詞： | 線上排程 、L2-範數 、流程時間 、自適應框架 、非全知排程 、ℓ2-範數 |
| 外文關鍵詞： | Online Scheduling, L2-Norm, Flow Time, Adaptive Framework, Non-clairvoyant Scheduling, ℓ2-Norm |
| 相關次數： | 點閱：14 下載：0 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在線上排程中，沒有任何單一策略能在所有工作負載下表現良好。SRPT 能最小化平均流程時間，但當短工作持續到達時，大工作可能遭受飢餓；FCFS 依到達順序處理工作以防止飢餓，卻在大工作阻塞眾多小工作時造成浪費。流程時間的 ℓ₂-範數介於兩者之間：其平方懲罰對長延遲的抑制比平均值更為積極，但又不像最大值那樣僅關注單一最差工作。針對此目標，目前最佳的全知結果為 BAL，其競爭比為 O(n¹ᐟ³)——然而 BAL 需要事先得知工作總數，且其保障隨 n 增長而衰退。在非全知設定中，工作大小在完成前未知，現有演算法主要針對 ℓ₁-範數進行設計與分析，ℓ₂-範數作為策略選擇準則尚未被探索。本論文提出一個自適應框架，週期性地以近期工作負載歷史重播兩個競爭候選策略，並選擇 ℓ₂-範數較低者。三種實例展示此構想：Dynamic_BAL（BAL 對 FCFS，全知）、Dynamic（SRPT 對 FCFS，全知，無需工作總數）、以及 RFDynamic（RMLF 對 FCFS，非全知，採用池化模擬處理未知工作大小）。在 Bounded Pareto 與 Truncated Normal 工作負載、系統負載 0.75 至 1.50 的範圍內，每個實例在多數配置下均能匹配或優於其任一候選策略單獨使用的表現。
1. Introduction 1
1.1 Background and Motivation 1
1.2 Two Problem Settings 2
1.3 Research Contributions 3
1.4 Thesis Organization 4
2. Background 5
2.1 Motivating Examples 5
2.2 Clairvoyant Scheduling Algorithms 8
2.2.1 SRPT 8
2.2.2 FCFS 8
2.2.3 BAL 9
2.3 Non-Clairvoyant Scheduling Algorithms 9
2.3.1 MLFQ and RMLF 10
2.4 Summary: The Need for Adaptation 11
3. Adaptive Framework Design 12
3.1 Overview 12
3.2 Core Mechanisms 13
3.2.1 Batch-Based Execution 13
3.2.2 Lookback and Policy Selection 13
3.3 Clairvoyant Evaluation: Direct Replay 14
3.4 Non-Clairvoyant Evaluation: Pool-Based Simulation 15
3.4.1 The Challenge 15
3.4.2 Bootstrap Phase 15
3.4.3 Job Size Pool and Incomplete-Job Filling 15
3.4.4 Simulation-Based Evaluation and Unified Pseudocode 16
4. Experimental Evaluation 18
4.1 Experimental Setup 18
4.1.1 Job Arrival Process 18
4.1.2 Job Size Distributions 18
4.1.3 Baselines and Metrics 18
4.2 Clairvoyant Results: Dynamic_BAL and Dynamic 19
4.3 Non-Clairvoyant Results: RFDynamic 24
4.4 Lookback Sensitivity Analysis 28
4.5 Batch Size Sensitivity Analysis 30
4.6 Time-Varying Workload 32
4.7 Summary 34
4.8 Discussion 34
5. Related Work 36
5.1 Minimizing Flow Time: Clairvoyant Setting 36
5.2 Minimizing Flow Time: Non-Clairvoyant Setting 37
5.3 Learning-Augmented Scheduling 39
5.4 Summary 40
6. Conclusion 41
6.1 Summary of Contributions 41
6.2 Future Work 42
Reference 43
1. Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Operating Systems: Three Easy Pieces. Arpaci-Dusseau Books, 2018.
2. Baruch Awerbuch, Yossi Azar, Stefano Leonardi, and Oded Regev. Minimizing the flow time without migration. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pages 198--205, 1999.
3. Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 1070--1080, 2021.
4. Nikhil Bansal and Bouke Cloostermans. Minimizing maximum flow-time on related machines. Theory of Computing, 12(1):1--14, 2016.
5. Nikhil Bansal and Kedar Dhamdhere. Minimizing weighted flow time. ACM Transactions on Algorithms, 3(4):39, 2007.
6. Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, and Amitabh Sinha. Non-clairvoyant scheduling for minimizing mean slowdown. In Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 2607 of Lecture Notes in Computer Science, pages 260--270. Springer, 2003.
7. Nikhil Bansal and Mor Harchol-Balter. Analysis of SRPT scheduling: Investigating unfairness. In Proceedings of ACM SIGMETRICS, pages 279--290, 2001.
8. Nikhil Bansal and Kirk Pruhs. Server scheduling in the Lp norm: A rising tide lifts all boats. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 242--250, 2003.
9. Nikhil Bansal and Kirk Pruhs. Server scheduling in the weighted ℓp norm. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN), pages 434--443, 2004.
10. Nikhil Bansal and Kirk Pruhs. The geometry of scheduling. SIAM Journal on Computing, 43(5):1684--1698, 2014.
11. Nikhil Bansal, Lars Rohwedder, and Ola Svensson. Flow time scheduling and prefix Beck-Fiala. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 331--342, 2022.
12. Luca Becchetti and Stefano Leonardi. Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. Journal of the ACM, 51(4):517--539, 2004.
13. Luca Becchetti, Stefano Leonardi, and Alberto Marchetti-Spaccamela. Semi-clairvoyant scheduling. Theoretical Computer Science, 324(2--3):325--335, 2004.
14. Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Kirk Pruhs. Online weighted flow time and deadline scheduling. Journal of Discrete Algorithms, 4(3):339--352, 2006.
15. Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Kirk Pruhs. Flow time minimization. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 766--768. Springer, 2016.
16. Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, and Tjark Vredeveld. Average-case and smoothed competitive analysis of the multilevel feedback algorithm. Mathematics of Operations Research, 31(1):85--108, 2006.
17. Michael A. Bender, Soumen Chakrabarti, and S. Muthukrishnan. Flow and stretch metrics for scheduling continuous job streams. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270--279, 1998.
18. Michael A. Bender, S. Muthukrishnan, and Rajmohan Rajaraman. Improved algorithms for stretch scheduling. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 762--771, 2002.
19. Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predictions. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 3506--3538, 2024. ICML 2024 / arXiv:2405.01013.
20. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
21. Chandra Chekuri, Ashish Goel, Sanjeev Khanna, and Amit Kumar. Multi-processor scheduling to minimize flow time with ϵ resource augmentation. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 363--372, 2004.
22. Chandra Chekuri and Sanjeev Khanna. Approximation schemes for preemptive weighted flow time. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 297--305, 2002.
23. Qingyun Chen, Sungjin Im, and Aditya Petety. Online scheduling via gradient descent for weighted flow time minimization. In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3802--3841, 2025.
24. Edward G. Coffman and Peter J. Denning. Operating Systems Theory. Prentice-Hall, 1973.
25. Richard W. Conway, William L. Maxwell, and Louis W. Miller. Theory of Scheduling. Addison-Wesley, 1967.
26. Fernando J. Corbató, Marjorie Merwin-Daggett, and Robert C. Daley. An experimental time-sharing system. In Proceedings of the Spring Joint Computer Conference (SJCC), pages 335--344, 1962.
27. Mark E. Crovella and Azer Bestavros. Self-similarity in world wide web traffic: Evidence and possible causes. IEEE/ACM Transactions on Networking, 5(6):835--846, 1997.
28. Mark E. Crovella, Robert Frangioso, and Mor Harchol-Balter. Connection scheduling in web servers. In USENIX Symposium on Internet Technologies and Systems, pages 243--254, 1999.
29. Jeffrey Dean and Luiz André Barroso. The tail at scale. Communications of the ACM, 56(2):74--80, 2013.
30. Jeff Edmonds. Scheduling in the dark. Theoretical Computer Science, 235(1):109--141, 2000.
31. Jeff Edmonds, Donald D. Chinn, Tim Brecht, and Xiaotie Deng. Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pages 120--129, 1997.
32. Jeff Edmonds, Sungjin Im, and Benjamin Moseley. Online scalable scheduling for the ℓk-norms of flow time without conservation of work. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 109--119, 2011.
33. Daniel Golovin, Anupam Gupta, Amit Kumar, and Kanat Tangwongsan. All-norms and all-Lp-norms approximation algorithms. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 199--210, 2008.
34. Mor Harchol-Balter. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013.
35. Kenneth Hoganson and Joseph Brown. Intelligent mitigation in multilevel feedback queues. In Proceedings of the 55th Annual ACM Southeast Conference (ACMSE), pages 138--141, 2017.
36. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive flow time algorithms for polyhedral scheduling. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 506--524, 2015.
37. Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 285--294, 2021.
38. Sungjin Im and Benjamin Moseley. Online scalable algorithm for minimizing ℓk-norms of weighted flow time on unrelated machines. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 95--108, 2011.
39. Sungjin Im, Benjamin Moseley, and Kirk Pruhs. Online scheduling with general cost functions. SIAM Journal on Computing, 43(1):126--143, 2014.
40. Sven Jäger, Alexander Lindermayr, and Nicole Megow. The power of proportional fairness for non-clairvoyant scheduling under polyhedral constraints. In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3901--3930, 2025.
41. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. Journal of the ACM, 47(4):617--643, 2000.
42. Bala Kalyanasundaram and Kirk Pruhs. Minimizing flow time nonclairvoyantly. Journal of the ACM, 50(4):551--567, 2003.
43. Hans Kellerer, Thomas Tautenhahn, and Gerhard J. Woeginger. Approximability and nonapproximability results for minimizing total flow time on a single machine. SIAM Journal on Computing, 28(4):1155--1166, 1999.
44. Tung-Wei Kuo. Minimizing ℓ2 norm of flow time by starvation mitigation. In Proceedings of the 36th International Workshop on Combinatorial Algorithms (IWOCA), pages 362--375. Springer, 2025. Earlier version: arXiv:2112.14403.
45. Alexandra Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Minimalistic predictions to schedule jobs with online precedence constraints. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 18563--18583, 2023.
46. Stefano Leonardi and Danny Raz. Approximating total flow time on parallel machines. Journal of Computer and System Sciences, 73(6):875--891, 2007.
47. Alexander Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant scheduling. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 357--368, 2022.
48. Alexander Lindermayr, Nicole Megow, and Martin Rapp. Speed-oblivious online scheduling: Knowing (precise) speeds is not necessary. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 21312--21334, 2023.
49. Richard McDougall and Jim Mauro. Solaris Internals: Solaris 10 and OpenSolaris Kernel Architecture. Prentice Hall, 2007.
50. Marshall Kirk McKusick, George V. Neville-Neil, and Robert N. M. Watson. The Design and Implementation of the FreeBSD Operating System. Addison-Wesley, 2014.
51. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 646--662. Cambridge University Press, 2021.
52. Rajeev Motwani, Steven J. Phillips, and Eric Torng. Non-clairvoyant scheduling. Theoretical Computer Science, 130(1):17--47, 1994.
53. Michael L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 5th edition, 2016.
54. Kirk Pruhs. Competitive online scheduling for server systems. ACM SIGMETRICS Performance Evaluation Review, 35(4):52--58, 2007.
55. Kirk Pruhs, Jiří Sgall, and Eric Torng. Online scheduling. In Joseph Y.-T. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 15. CRC Press, 2004.
56. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 9684--9693, 2018.
57. Mark E. Russinovich, David A. Solomon, and Alex Ionescu. Windows Internals. Microsoft Press, 2012.
58. Linus E. Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16(3):687--690, 1968.
59. Linus E. Schrage and Louis W. Miller. The queue M/G/1 with the shortest remaining processing time discipline. Operations Research, 14(4):670--684, 1966.
60. Bianca Schroeder and Mor Harchol-Balter. Web servers under overload: How scheduling can help. ACM Transactions on Internet Technology, 6(1):20--52, 2006.
61. Ziv Scully, Isaac Grosof, and Michael Mitzenmacher. Uniform bounds for scheduling with job size estimates. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 114:1--114:30, 2022.
62. Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202--208, 1985.
63. Adam Wierman and Mor Harchol-Balter. Classifying scheduling policies with respect to unfairness in an M/GI/1. In Proceedings of ACM SIGMETRICS, pages 238--249, 2003.
全文公開日期 2031/04/09