数据操作系统中基于博弈的多资源分配算法

A Multiple Resource Allocation Algorithm Based on Game Theory in DataOS

数据操作系统需要对CPU和内存等多种系统资源进行管理,为了在公平的前提下,解决不同用户对上述资源的不同需求问题,本文基于完全信息的动态博弈提出了ICEEI算法。该方法通过构建博弈树并优化博弈树的方法解决数据操作系统中的多资源分配问题。该算法最符合实际的假设是认为任务是不可分的,即数据操作系统分配给每个用户的资源可完全满足任务的需求。对该算法的公平性进行了讨论,指出其满足共享激励和Pareto有效等性质。通过一系列的仿真实验,证明ICEEI可以很好地应对用户对资源需求的动态变化,并且与DRF相比在有些情况下具有更高的资源利用率。

We consider the problem of how a system allocates resources to different agents fairly and efficiently in Data OS, where the system contains different resource types such as CPU and Memory, and agents may have different demands for the resources. In this pa- per, we propose the ICEEI algorithm based on dynamic game theory with complete information which solves the multiple resource allo- cation problem . The algorithm assumes that the task is indivisible, such that the resources the system allocated to each agent fully sat- isfy the demand of each task. Then we consider the fairness problem of the algorithm and prove that it satisfies Sharing incentive and Pareto efficiency. In addition, we carry out experiments to verify the proposed algorithm, which show that the ICEEI allocation can effi- ciently adjusts to the dynamic change of agents＇ demand for resources, and use resources more efficiently