云计算任务调度的时间感知模型研究

云计算资源序列用｛R1，R2，…，Rj，…Rm｝表示，任务类别表示为i，数量表示为n。对于每个任务i，其资源需求量为Di，优先级为Pi，效用函数为Ui，纳什谈判的目标是最大化所有任务总的效用，并保证根据任务的不同优先级使其在最晚完成时间内执行完毕。同时，如果资源因为某种原因未能成功分配给指定任务，系统迅速寻找新的虚拟机并尽最大可能满足任务对于资源的需求。纳什均衡表示为公式（5-25）：

其中，ci表示任务i所获得的资源。

纳什谈判为公式（5-25）提供了唯一的最优解，并且具有有效性，即利用所有可利用的资源。纳什谈判尽可能保证非递减的趋势，但增加任何一个ci难免会减少其他任务的资源分配，为了实现资源分配的公平性，公式（5-25）转变为公式（5-26）：

根据用户对于任务最晚完成时间的不同要求，将最晚完成时间分为三类：

Ⅰ类最晚完成时间：必须为任务分配足够的资源，以保证任务必须在用户规定的时间内完成。

Ⅱ类最晚完成时间：允许任务的完成时间超过用户规定的最晚完成时间，分配资源后，此时的效用值相应降低。

Ⅲ类最晚完成时间：用户没有强制规定任务的完成时间，该任务的执行不必满足任何期限，资源在何时分配均有效。

以上三类任务最晚完成时间分类的表示为公式（5-27）～公式（5-29）：

Ⅰ类最晚完成时间：设ci（t）为在单位时隙t内被分配到任务i的资源。在Ⅰ类最晚完成时间情况下，任务的效用由总的资源所唯一确定，该资源为任务从提交到执行到最晚完成时间整个过程中所得的资源总量。(www.xing528.com)

其中，ci由完成任务i需要的总资源量Di进行归一化表示，是完成的时间限制。对于具有Ⅰ类最晚完成时间的任务，由于每个任务必须至少获得的总资源量为Di，则ci≥1。

Ⅱ类最晚完成时间：

其中，φ为基于应用类型和客户期望的衰减系数。Ti（t）是时间权重函数，虽然在Ⅱ类最晚完成时间中，允许任务的完成时间超过用户规定的最晚完成时间，但这样做会造成效用降低，因此设定时间权重函数，当在用户给定的最晚完成时间内任务已经执行完毕，此种情况同Ⅰ类最晚完成时间表示一致；当超过用户给定的最晚完成时间后，时间权重函数呈指数形式降低。

Ⅲ类最晚完成时间：

其中，代表纳什均衡的时间范围。

同Ⅱ类最晚完成时间一样，在Ⅲ类最晚完成时间的情况下，没有对于资源分配的最小量要求。当φ=0时，Ⅱ类最晚完成时间转化为Ⅲ类最晚完成时间，当φ=+∞，Ⅱ类最晚完成时间转化为Ⅰ类最晚完成时间。

结合上述分类情况，得出公式（5-31）自适应纳什均衡优化问题BR：

BR是经典纳什均衡优化问题的扩展，其考虑了资源配置的公平性，当Ui满足一定条件，如线性或对数函数，易证BR是凸问题，具有最优解。