本文選題：云計(jì)算　切入點(diǎn)：任務(wù)調(diào)度算法　出處：《山東師范大學(xué)》2014年碩士論文

【摘要】：云計(jì)算是一種新的計(jì)算模式，它通過服務(wù)的形式為用戶提供各種資源。云計(jì)算的正常運(yùn)行離不開虛擬化技術(shù)。云計(jì)算中，利用虛擬化技術(shù)，將物理服務(wù)器的資源映射到虛擬機(jī)層，在一個(gè)服務(wù)器上部署多個(gè)虛擬機(jī)，利用虛擬機(jī)來執(zhí)行用戶任務(wù)，這樣不但提高了服務(wù)器的資源利用率，同時(shí)保證了不同用戶的應(yīng)用程序的獨(dú)立性。 近年來，越來越多的企業(yè)架構(gòu)了自己的云服務(wù)器，云計(jì)算系統(tǒng)需要有滿足自身用戶需要的資源分配和任務(wù)調(diào)度策略，目前還沒有相關(guān)的任務(wù)調(diào)度標(biāo)準(zhǔn)。因此，對(duì)云計(jì)算環(huán)境下的任務(wù)調(diào)度算法研究具有重要的理論和現(xiàn)實(shí)意義。本文分析了云計(jì)算環(huán)境下的任務(wù)調(diào)度法算的研究現(xiàn)狀，總結(jié)了云計(jì)算這一新興商業(yè)模式的獨(dú)有的特點(diǎn)，對(duì)現(xiàn)有調(diào)度算法存在的問題進(jìn)行了深入分析，然后分別針對(duì)獨(dú)立型和依賴型兩類任務(wù)，提出了兩種任務(wù)調(diào)度算法。此外，考慮了用戶對(duì)云計(jì)算中心虛擬機(jī)資源的不同偏好性，針對(duì)多用戶類，設(shè)計(jì)了多準(zhǔn)則的任務(wù)調(diào)度算法�？傮w來說，本文主要完成了以下工作： ⑴針對(duì)云計(jì)算環(huán)境下的獨(dú)立型任務(wù)，現(xiàn)有的調(diào)度方法一般包括遺傳算法、蟻群算法、模擬退火算法等智能算法，，這些算法收斂的速度較快，但是容易陷入局部最優(yōu)，并且算法過度依靠適應(yīng)度函數(shù)的設(shè)計(jì)，算法復(fù)雜度較高�？紤]到這類隨機(jī)算法的劣勢，我們從博弈論的角度分析云計(jì)算環(huán)境下的任務(wù)調(diào)度問題，設(shè)計(jì)了一個(gè)任務(wù)調(diào)度博弈模型，將所有用戶任務(wù)作為博弈的參與者，所選擇的虛擬機(jī)作為博弈策略，以任務(wù)處理時(shí)延作為博弈參與者的效用函數(shù)。找到了博弈的勢函數(shù)，證明了博弈是一個(gè)勢博弈，并且博弈存在Nash均衡，利用數(shù)學(xué)分析，證明了該博弈的穩(wěn)定點(diǎn)就是勢函數(shù)的最小值點(diǎn)。此外，提出了一種基于勢博弈的任務(wù)調(diào)度算法，算法能夠求解博弈到達(dá)穩(wěn)定點(diǎn)時(shí)各個(gè)虛擬機(jī)上的任務(wù)量分布狀態(tài)。仿真實(shí)驗(yàn)表明，該調(diào)度算法能降低任務(wù)的整體處理時(shí)延，并且能使系統(tǒng)的負(fù)載均衡程度自適應(yīng)于用戶任務(wù)量的變化，當(dāng)任務(wù)量較少時(shí)，開啟較少的虛擬機(jī)資源，減少系統(tǒng)的開銷，當(dāng)任務(wù)量較多時(shí)，開啟較多的虛擬機(jī)資源，保證任務(wù)的QoS。此外，考慮了虛擬機(jī)的閾值限制，對(duì)所提算法進(jìn)行了擴(kuò)展，將虛擬機(jī)閾值限制這一參數(shù)加入到算法中，使得算法更具有一般性。 ⑵針對(duì)依賴型任務(wù)，分析了任務(wù)的DAG圖，主要研究了Fork-Join型任務(wù)圖，針對(duì)該類任務(wù)，基于網(wǎng)絡(luò)博弈論中的Wardrop均衡原理，給出了以全體用戶任務(wù)處理時(shí)延作為代價(jià)函數(shù)的博弈分析，考慮網(wǎng)絡(luò)中全體用戶任務(wù)，將求解全體用戶的系統(tǒng)最優(yōu)問題轉(zhuǎn)化為求解單個(gè)用戶的用戶最優(yōu)問題，設(shè)計(jì)了一個(gè)針對(duì)該任務(wù)的調(diào)度算法，該算法能夠求解Wardrop均衡理論中的系統(tǒng)最優(yōu)狀態(tài)。最后，對(duì)此算法進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)表明，相比于單個(gè)用戶最優(yōu)的求解算法，該算法能夠較快的完成用戶任務(wù)，并且使整個(gè)云計(jì)算用戶任務(wù)達(dá)到系統(tǒng)最優(yōu)。 ⑶針對(duì)云計(jì)算用戶任務(wù)對(duì)虛擬機(jī)資源具有不同的偏向性，對(duì)多用戶類多準(zhǔn)則的任務(wù)調(diào)度進(jìn)行了研究。在云計(jì)算環(huán)境下，有些用戶偏向于選擇處理時(shí)延小的虛擬機(jī)資源，有些用戶偏向于選擇費(fèi)用低的虛擬機(jī)資源，有些用戶偏向于選擇更加安全的虛擬機(jī)資源。根據(jù)用戶的偏好性不同，將網(wǎng)絡(luò)中的用戶分為多類用戶，只考慮費(fèi)用和時(shí)間這兩種指標(biāo)，為這多類用戶同時(shí)競爭虛擬機(jī)資源時(shí)設(shè)計(jì)了博弈模型，找到了博弈的勢函數(shù)，證明了該博弈為一個(gè)勢博弈，同時(shí)證明了博弈存在Nash均衡，并且Nash均衡與勢函數(shù)的最大值等價(jià)。最后，提出了一種基于多用戶類多準(zhǔn)則的任務(wù)調(diào)度算法，求解博弈達(dá)到均衡時(shí)的各個(gè)虛擬機(jī)上任務(wù)量的狀態(tài)分布。算法的仿真實(shí)驗(yàn)表明，所提算法具有收斂性，算法的求解結(jié)果與所有自私用戶經(jīng)過自由博弈后所得到的穩(wěn)定狀態(tài)是相同的，進(jìn)一步說明了該算法的有效性及可行性。
[Abstract]:Cloud computing is a new computing mode, it is in the form of services to provide users with a variety of resources. The normal operation of cloud computing cannot do without virtualization. Cloud computing, the use of virtualization technology, the resource mapping of physical servers to virtual machine layer on a server to deploy multiple virtual machines. To perform user tasks using the virtual machine, it will not only improve the utilization of server resources, while ensuring the independence of the application of different users.
In recent years, more and more enterprise architecture its own cloud server, cloud computing system has to meet the need of resource allocation and task scheduling strategy to meet the needs of users, there is no task scheduling standards. Therefore, it has important theoretical and practical significance to the research of cloud computing task scheduling algorithm under the environment. This paper analyzes the research the status of task scheduling method in cloud computing environment is summarized, which is an emerging business model of the unique characteristics of cloud computing, on the existing scheduling problems in-depth analysis, and then according to the independent type and the dependent two kinds of task, put forward two kinds of task scheduling algorithms. In addition, taking into account the different the user preference of virtual machine resources on Cloud Computing Center, for many users, the task scheduling algorithm design standards. In general, this paper mainly completed the following work:
The independent task for cloud computing environment, the existing scheduling method generally includes genetic algorithm, ant colony algorithm, simulated annealing algorithm and other intelligent algorithms, the algorithm converges faster, but easy to fall into local optimum, and the algorithm is too dependent on the design of fitness function, the complexity of the algorithm is higher. Considering the stochastic algorithm the disadvantage, we analyze the problem of cloud computing task scheduling environment, designed a task scheduling game model, all user tasks as the player of the game, the selected virtual machine as the game strategy, the task of processing delay as a utility function of game participants. Find the potential function of the game that proves that the game is a potential game, and the game of the Nash equilibrium, using mathematical analysis, proved that the stable point of the game is the potential function of the minimum point in addition, Presents a task scheduling algorithm based on potential game, each virtual machine algorithm can solve the game task distribution reaches the stable point. Simulation results show that the overall processing delay of the scheduling algorithm can reduce task, and make changes in the load balance of the system is adaptive to the degree of user task amount, when the quantity of task less, less open virtual machine resources, reduce the cost of the system, when the task quantity is more and more open virtual machine resources, ensure the task of QoS. in addition, considering the threshold limit of the virtual machine, the proposed algorithm is extended to the virtual machine threshold limits the parameter added to the algorithm. The algorithm is more general.
For dependent tasks, task analysis DAG, mainly studies the Fork-Join task graph for this kind of task, Wardrop equilibrium principle of network game theory based on the given by the user task processing time delay as the game analysis of the cost function, considering all the users in the network, the optimal solution of all the user into a single user user optimal problem solving, a task scheduling algorithm for the system design, the algorithm can solve the Wardrop equilibrium theory in optimal state. Finally, this algorithm in the simulation experiment, experimental results show that the algorithm compared to the single user optimum, this algorithm can quickly complete the task of the user, and the users of cloud computing task to achieve optimal system.
According to the users of cloud computing tasks with different bias of virtual machine resources, task scheduling for multi user multi criterion is studied. In the cloud computing environment, some users tend to choose the processing resources of virtual machine small delay, some users tend to choose low cost virtual machine resources, some users tend to virtual machine resources to choose more safe. According to different user preferences, the network users are divided into many types of users, only consider the two indicators of cost and time, for the multi class user and virtual machine resources design competition game model, find the potential function of the game, the game is proved a potential game, and prove the existence of Nash equilibrium game, and the maximum value of the equivalent Nash equilibrium and potential function. Finally, put forward a task scheduling algorithm for multi user multi criterion based on solving the game reached The amount of task distribution on each virtual machine scale. Simulation results show that the algorithm, the proposed algorithm has convergence algorithm for solving steady state results and are all selfish users through free after the game is the same, and further illustrates the effectiveness and feasibility of the algorithm.

【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP393.01

【引證文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

1 任新新;基于結(jié)構(gòu)優(yōu)化的虛擬網(wǎng)映射算法研究[D];山東師范大學(xué);2015年

本文編號(hào)：1712399