基于資源碎片的協(xié)同預留算法研究
發(fā)布時間：2018-10-25 07:59
【摘要】：在分布式系統(tǒng)中,資源協(xié)同預留是保證系統(tǒng)服務質量的一項核心技術。然而在為用戶預留資源的過程中,預留作業(yè)會將完整的資源切割為不連續(xù)的小塊資源,形成資源碎片。這些資源碎片的形成和存在,降低了資源的利用率和作業(yè)的接納率。在有截止時間約束的作業(yè)調度過程中,為作業(yè)安排不同的可用資源,即不同的調度方案,產(chǎn)生的資源碎片不盡相同,對后續(xù)任務的接納也有不同的影響。通過對調度方案的優(yōu)化,可以有效地提高作業(yè)接納率和資源利用率。 本文分析了協(xié)同預留的研究歷史及現(xiàn)狀,研究了在多機單處理器的網(wǎng)格環(huán)境下資源碎片形成的原因,以及不同調度方案對作業(yè)接納率和資源利用率的影響。以上述分析為基礎,本文考慮當前作業(yè)調用的資源對整體資源的分割情況,將當前作業(yè)的分配與后續(xù)作業(yè)的接納聯(lián)系起來,提出了對不同規(guī)模的資源碎片賦予不同權重的資源碎片接納能力量化方法。以此量化方法為標準,提出了基于碎片的Best Fit算法(FSB)和基于碎片的Worst Fit算法(FSW)兩種提前預留算法,并對其性能進行了仿真實驗研究。 在仿真實驗中,研究了在不同的作業(yè)靈活性、平均持續(xù)時間、系統(tǒng)負載和資源數(shù)量條件下,這兩種算法在作業(yè)接納率、資源利用率和作業(yè)平均減緩三個方面的性能。與Best Fit、First Fit、Min_LIP和Min_TIP四個算法進行比較,證明了FSW和FSB算法在重負載下,可以取得較高的作業(yè)接納率。FSW算法與FSB相比較,由于算法設計思路相同,作業(yè)接納率與平均減緩和資源利用率的性能為嚴格的矛盾關系,FSW可以取得更高的作業(yè)接納率,而平均減緩更高,資源利用率更低。
[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 張偉哲;田志宏;張宏莉;何慧;劉文懋;;虛擬計算環(huán)境中的多機群協(xié)同調度算法[J];軟件學報;2007年08期
2 李波;趙東風;沈斌;;支持資源預留的網(wǎng)格計算仿真平臺[J];系統(tǒng)仿真學報;2006年S2期
，本文編號：2293103
本文鏈接：http://sikaile.net/kejilunwen/jisuanjikexuelunwen/2293103.html
最近更新
教材專著
