云计算环境下多截止期工作调度算法研究  

Scheduling Jobs with Multiple Deadlines in Cloud

作　　者：刘志民 陈建二 LIU Zhimin;CHEN Jianer(School of Computer Science and Cyber Engineering,Guangzhou University,Guangzhou 510006,China)

机构地区：[1]广州大学计算机科学与网络工程学院,广州510006

出　　处：《计算机科学》2024年第S02期727-733,共7页Computer Science

摘　　要：随着大数据对人们生活的影响逐渐增大,数据存储和计算需求不断增加,云计算的兴起有效地满足了这一需求。在实时性要求较高的云计算系统中,来自客户端的资源请求被视为具有截止期限和一定收益的两阶段工作,云服务器被视为两阶段机器。不同资源请求的截止期限通常不同,如果云中心能在资源请求的截止期限之前完成该请求,就可以获得相应的收益。现有的以收益最大化作为优化目标的两阶段工作调度均是在一个公共截止期限制下进行的,而实际情况往往是不同的资源请求可能有不同的截止期限。基于当前云计算应用和数据中心数据处理的需求,建立了云计算系统中工作调度的新数学模型。首次提出了具有多个截止期的两阶段工作在多处理机上的调度问题,并给出了一个近似比为(3 k+ε)的多项式时间近似算法。当机器数目为固定常数时,近似比进一步降低为(k+ε),其中k是一个固定常数,即截止期的个数,ε是大于0的任意常数。针对特殊的T-处理时间大于R-处理时间模型,在单个两阶段机器上,给出了一个近似比为2的伪多项式时间近似算法,进一步降低了算法的近似比。With the increasing impact of big data on people's lives,the demand for data storage and computation continues to grow,and the emergence of cloud computing effectively meets this demand.In cloud computing systems with high real-time requirements,resource requests from clients are regarded as 2-stage jobs with deadlines and certain profits,while cloud servers are seen as 2-stage machines.The deadlines for different resource requests are usually different,and if the cloud center can complete the request before the deadline,it can obtain corresponding profits.Existing 2-stage jobs scheduling algorithms that aim to maximize revenue are conducted under a common deadline constraint,whereas in reality,different resource requests may have varying deadlines.Based on the demand in the research and applications in cloud computing and data centers,we build a mathematical model for job scheduling in cloud computing.We study the problem of scheduling 2-stage jobs with multiple deadlines on multiple 2-stage machines.Let k be the number of deadlines of the jobs.When k is a constant,a polynomial-time approximation algorithm with approximation ratio(3k+ε)is provided.When the number of machines is a fixed constant,the approximation ratio is further improved to(k+ε),where ε>0 is an arbitrary constant.Therefore,when k is a constant,the problem has a constant ratio polynomial-time approximation algorithm.In the case where T-processing time is greater than R-processing time,a pseudo-polynomial time approximation algorithm with approximation ratio 2 is presented,further improving the approximation ratio.

关 键 词：云计算 多阶段工作 多处理机调度 近似算法 算法分析 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]