臺灣博碩士論文加值系統

在這篇論文中，我們描述了一個可以將資源分配給批次工作和互動式工作，並讓它們同時運行的系統架構。在這個系統中，每個工作有各自的服務協議層級，違反服務協議層級會導致罰款。我們提出了一個可以量化批次工作和互動式工作的罰款的模型。以此模型為基礎，我們提出了一個估計批次工作和互動式工作的罰款，並降低總罰款的演算法。我們的實驗結果指出此系統可以正確的將資源分配給不同類型的工作，藉以有效地降低總罰款。

In this paper we describe a scheduling framework that allocates resources to both batch jobs and interactive jobs simultaneously in a private cloud with a static amount of resources. In the system, every job has an individual service level agreement (SLA), and violating the SLA incurs penalty. We propose a model to formally quantify the SLA violation penalty of both batch and interactive jobs. The analysis on the interactive jobs focuses on queuing analysis and response time. The analysis on batch jobs focuses on the non-preemptive job
scheduling for multiple processing units. Based on this model we also propose algorithms to estimate the penalty for both batch jobs and interactive jobs, and algorithms that reduce the total SLA violation penalty. Our experiment results suggest that our system effectively
reduces the total penalty by allocating the right amount of resources to heterogeneous jobs in a private cloud system.

口試委員會審定書 i
致謝 ii
中文摘要 iii
Abstract iv
Contents v
List of Figures vii
1 Introduction 1
2 Related Work 4
3 Models 6
3.1 Batch Job . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Interactive Job . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 Architecture 9
4.1 Supervisor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Decision Maker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4 Worker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.5 Client . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5 Resource Provisioning 12
5.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2.1 Estimating the Cost of Interactive Jobs . . . . . . . . . . . . . . 13
5.2.2 Estimating the Penalty of Batch Jobs . . . . . . . . . . . . . . . . 16
5.2.3 Determine m i and m b . . . . . . . . . . . . . . . . . . . . . . . 19
6 Experiment 21
6.1 Hardware Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.2 Workload Traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.3 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.3.1 Penalty Estimation of Batch Jobs . . . . . . . . . . . . . . . . . 22
6.3.2 SLA Violation Penalty of Batch Jobs . . . . . . . . . . . . . . . 24
6.3.3 SLA Violation Penalty of Batch Jobs Compared to LibraSLA . . 25
6.3.4 SLA Violation Penalty of Mixed Jobs . . . . . . . . . . . . . . . 26
7 Conclusion 32
Bibliography 33

[1] Michael Armbrust, O Fox, Rean Griffith, Anthony D Joseph, Y Katz, Andy Kon-
winski, Gunho Lee, David Patterson, Ariel Rabkin, Ion Stoica, et al. M.: Above the
clouds: a berkeley view of cloud computing. 2009.
[2] Tharam Dillon, Chen Wu, and Elizabeth Chang. Cloud computing: issues and chal-
lenges. In Advanced Information Networking and Applications (AINA), 2010 24th
IEEE International Conference on, pages 27–33. Ieee, 2010.
[3] Jian Li, Sen Su, Xiang Cheng, Meina Song, Liyu Ma, and Jie Wang. Cost-efficient
coordinated scheduling for leasing cloud resources on hybrid workloads. Parallel
Computing, 44:1–17, 2015.
[4] Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric
Tune, andJohnWilkes. Large-scaleclustermanagementatgooglewithborg. InPro-
ceedings of the Tenth European Conference on Computer Systems, page 18. ACM,
2015.
[5] Saurabh Kumar Garg, Srinivasa K Gopalaiyengar, and Rajkumar Buyya. Sla-based
resource provisioning for heterogeneous workloads in a virtualized cloud datacenter.
In Algorithms and Architectures for Parallel Processing, pages 371–384. Springer,
2011.
[6] Martin T Hagan, Howard B Demuth, Mark H Beale, et al. Neural network design.
Pws Pub. Boston, 1996.
[7] Chee Shin Yeo and Rajkumar Buyya. Service level agreement based allocation of
cluster resources: Handling penalty to enhance utility. In Cluster Computing, 2005.
IEEE International, pages 1–10. IEEE, 2005.
[8] Linlin Wu, Saurabh Kumar Garg, and Rajkumar Buyya. Sla-based resource alloca-
tion for software as a service provider (saas) in cloud computing environments. In
Cluster, Cloud and Grid Computing (CCGrid), 2011 11th IEEE/ACM International
Symposium on, pages 195–204. IEEE, 2011.
[9] Raymond Keith Clark. Scheduling dependent real-time activities. PhD thesis,
Carnegie Mellon University, 1990.
[10] Shuo Liu, Gang Quan, and Shangping Ren. On-line scheduling of real-time services
forcloudcomputing. InServices(SERVICES-1), 20106thWorldCongresson, pages
459–464. IEEE, 2010.
[11] Yue Yu, Shangping Ren, Nianen Chen, and Xing Wang. Profit and penalty aware
(pp-aware) scheduling for tasks with variable task execution time. In Proceedings
of the 2010 ACM Symposium on Applied Computing, pages 334–339. ACM, 2010.
[12] Hyeonjoong Cho, Binoy Ravindran, and E Douglas Jensen. On utility accrual pro-
cessor scheduling with wait-free synchronization for embedded real-time software.
In Proceedings of the 2006 ACM symposium on Applied computing, pages 918–922.
ACM, 2006.
[13] R Garey Michael and S Johnson David. Computers and intractability: a guide to the
theory of np-completeness. WH Freeman & Co., San Francisco, page 237, 1979.
[14] Michael L Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2012.
[15] Shrikant S Panwalkar and Wafik Iskander. A survey of scheduling rules. Operations
research, 25(1):45–61, 1977.
[16] Myunggwon Hwang, Dongjin Choi, and Pankoo Kim. Least slack time rate first:
New scheduling algorithm for multi-processor environment. In Complex, Intelligent and Software Intensive Systems (CISIS), 2010 International Conference on, pages
806–811. IEEE, 2010.
[17] San diego supercomputer center. http://www.sdsc.edu/.
[18] D Feitelson, D TALBY, and JP JONES. Standard workload format, 2007.
[19] The internet traffic archive. http://ita.ee.lbl.gov/.