基于资源碎片的协同预留算法研究
发布时间：2018-10-25 07:59
【摘要】：在分布式系统中,资源协同预留是保证系统服务质量的一项核心技术。然而在为用户预留资源的过程中,预留作业会将完整的资源切割为不连续的小块资源,形成资源碎片。这些资源碎片的形成和存在,降低了资源的利用率和作业的接纳率。在有截止时间约束的作业调度过程中,为作业安排不同的可用资源,即不同的调度方案,产生的资源碎片不尽相同,对后续任务的接纳也有不同的影响。通过对调度方案的优化,可以有效地提高作业接纳率和资源利用率。 本文分析了协同预留的研究历史及现状,研究了在多机单处理器的网格环境下资源碎片形成的原因,以及不同调度方案对作业接纳率和资源利用率的影响。以上述分析为基础,本文考虑当前作业调用的资源对整体资源的分割情况,将当前作业的分配与后续作业的接纳联系起来,提出了对不同规模的资源碎片赋予不同权重的资源碎片接纳能力量化方法。以此量化方法为标准,提出了基于碎片的Best Fit算法(FSB)和基于碎片的Worst Fit算法(FSW)两种提前预留算法,并对其性能进行了仿真实验研究。 在仿真实验中,研究了在不同的作业灵活性、平均持续时间、系统负载和资源数量条件下,这两种算法在作业接纳率、资源利用率和作业平均减缓三个方面的性能。与Best Fit、First Fit、Min_LIP和Min_TIP四个算法进行比较,证明了FSW和FSB算法在重负载下,可以取得较高的作业接纳率。FSW算法与FSB相比较,由于算法设计思路相同,作业接纳率与平均减缓和资源利用率的性能为严格的矛盾关系,FSW可以取得更高的作业接纳率,而平均减缓更高,资源利用率更低。
[Abstract]:In distributed systems, collaborative reservation of resources is a core technology to ensure the quality of service. However, in the process of reserving resources for users, the whole resources will be cut into discrete pieces of resources, forming resource fragments. The formation and existence of these resource fragments reduce the utilization rate of resources and the acceptance rate of jobs. In the process of job scheduling with deadline constraints, different available resources, that is, different scheduling schemes, have different effects on the admission of subsequent tasks. By optimizing the scheduling scheme, the job acceptance rate and resource utilization can be improved effectively. In this paper, the history and present situation of collaborative reservation are analyzed. The causes of resource fragmentation in multi-processor grid environment and the influence of different scheduling schemes on job acceptance rate and resource utilization are studied. Based on the above analysis, this paper considers the partition of the whole resource by the resources called by the current job, and links the allocation of the current job with the acceptance of the subsequent job. A quantization method of resource debris acceptance capacity with different weights for different scales of resource debris is proposed. Based on this quantization method, two early reservation algorithms, (FSB) based on fragment Best Fit and (FSW) based on Worst Fit, are proposed, and their performance is studied by simulation experiments. In the simulation experiment, the performance of the two algorithms in the three aspects of job acceptance rate, resource utilization and job average reduction is studied under different conditions of job flexibility, average duration, system load and resource quantity. Compared with the four algorithms of Best Fit,First Fit,Min_LIP and Min_TIP, it is proved that FSW and FSB can achieve high job acceptance rate under heavy load. Compared with FSB, the FSW algorithm has the same design idea. There is a strict contradiction between job acceptance rate and the performance of average slowing and resource utilization. FSW can obtain higher job acceptance rate, higher average slow down and lower resource utilization.
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338.8
本文编号：2293103
[Abstract]:In distributed systems, collaborative reservation of resources is a core technology to ensure the quality of service. However, in the process of reserving resources for users, the whole resources will be cut into discrete pieces of resources, forming resource fragments. The formation and existence of these resource fragments reduce the utilization rate of resources and the acceptance rate of jobs. In the process of job scheduling with deadline constraints, different available resources, that is, different scheduling schemes, have different effects on the admission of subsequent tasks. By optimizing the scheduling scheme, the job acceptance rate and resource utilization can be improved effectively. In this paper, the history and present situation of collaborative reservation are analyzed. The causes of resource fragmentation in multi-processor grid environment and the influence of different scheduling schemes on job acceptance rate and resource utilization are studied. Based on the above analysis, this paper considers the partition of the whole resource by the resources called by the current job, and links the allocation of the current job with the acceptance of the subsequent job. A quantization method of resource debris acceptance capacity with different weights for different scales of resource debris is proposed. Based on this quantization method, two early reservation algorithms, (FSB) based on fragment Best Fit and (FSW) based on Worst Fit, are proposed, and their performance is studied by simulation experiments. In the simulation experiment, the performance of the two algorithms in the three aspects of job acceptance rate, resource utilization and job average reduction is studied under different conditions of job flexibility, average duration, system load and resource quantity. Compared with the four algorithms of Best Fit,First Fit,Min_LIP and Min_TIP, it is proved that FSW and FSB can achieve high job acceptance rate under heavy load. Compared with FSB, the FSW algorithm has the same design idea. There is a strict contradiction between job acceptance rate and the performance of average slowing and resource utilization. FSW can obtain higher job acceptance rate, higher average slow down and lower resource utilization.
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338.8
【参考文献】
相关期刊论文 前2条
1 张伟哲;田志宏;张宏莉;何慧;刘文懋;;虚拟计算环境中的多机群协同调度算法[J];软件学报;2007年08期
2 李波;赵东风;沈斌;;支持资源预留的网格计算仿真平台[J];系统仿真学报;2006年S2期
，本文编号：2293103
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2293103.html
