linux内核进程抢占式调度的博弈决策

《linux内核进程抢占式调度的博弈决策》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Linux内核进程抢占式调度的博弈决策林攀(江苏大学计算机科学与通信工程学院江苏镇江)摘要:以博弈论的思想来解读Linux2.6内核进程调度的策略，在博弈树构造中寻找纳什均衡，己达到计算机资源协调，实现资源的最优化；通过研究非实吋进程的吋间片策略，分析进程调度的策略，在做出策略后它们的是否实现调度设计R标，把博弈理论屮得声誉名词引入进程调度屮，衡量决策的优良性能指标，用复出的内部机制，让超时的进程得到复出的o关键词:进彳5周度；博弈论；声誉；复出引言从古代开始，数学家研究室内游戏，试阁构造一个最优的游戏策略，至到20世纪中期左右，计算机之父约翰•冯诺依曼提出了新的研宄成果，一个真

2、正的，严谨的，模型化的关于策略环境的理论产生了，被称为博弈论［21(GameThOry),目前博弈论广泛应用到数学、经济、社会学、生物、计算机等学科，它主要研究决策主体的行为发生相互作用的时候主体的决策以及这些决策之间的均衡问题，数学家纳什提出的纳什均衡是博弈论的核心，这是一种有着深刻意义的理念，越来越到底认可，经济学家和数学家不断研宄。自由幵放Linux操作系统凭借其开源代码的优势，得到广泛的认可，内核一直不断完善，尤其Linux2.6在内核实现了抢占式优先级算法，一个优良的调度算法必须同时兼顾以下几个互相冲突的目标：(1)响应时间尽可能短、系统吞吐量可能的高、考虑进程死锁公平

3、的问题、异常处理的能力等，一个算法的策略决定了该算法是否实现上述的目标，在计算机运行的当前环境，做出在哪个吋间段选择那种新进程的规则集就是调度策略m。近年来，很多学者将经济学中的博弈论应用于任务分配中较好地解决了智能体的资源分配问题，依据因对博弈论的贡献而获得诺贝尔经济学奖的RobertAumann教授的说法，博弈论就是研究互动决策的理论。所谓互动决策，即各行动方(player)的决策是相互影响的，每个人在决策的时候必须将他人的决策纳入自己的决策考虑之中，当然也需要把别人对于自己的考虑纳入考虑之中，在如此迭代考虑情形下进行决策，选择最有利于自己的战Linux内核进程抢占式调度的博

4、弈决策林攀(江苏大学计算机科学与通信工程学院江苏镇江)摘要:以博弈论的思想来解读Linux2.6内核进程调度的策略，在博弈树构造中寻找纳什均衡，己达到计算机资源协调，实现资源的最优化；通过研究非实吋进程的吋间片策略，分析进程调度的策略，在做出策略后它们的是否实现调度设计R标，把博弈理论屮得声誉名词引入进程调度屮，衡量决策的优良性能指标，用复出的内部机制，让超时的进程得到复出的o关键词:进彳5周度；博弈论；声誉；复出引言从古代开始，数学家研究室内游戏，试阁构造一个最优的游戏策略，至到20世纪中期左右，计算机之父约翰•冯诺依曼提出了新的研宄成果，一个真正的，严谨的，模型化的关于策略环

5、境的理论产生了，被称为博弈论［21(GameThOry),目前博弈论广泛应用到数学、经济、社会学、生物、计算机等学科，它主要研究决策主体的行为发生相互作用的时候主体的决策以及这些决策之间的均衡问题，数学家纳什提出的纳什均衡是博弈论的核心，这是一种有着深刻意义的理念，越来越到底认可，经济学家和数学家不断研宄。自由幵放Linux操作系统凭借其开源代码的优势，得到广泛的认可，内核一直不断完善，尤其Linux2.6在内核实现了抢占式优先级算法，一个优良的调度算法必须同时兼顾以下几个互相冲突的目标：(1)响应时间尽可能短、系统吞吐量可能的高、考虑进程死锁公平的问题、异常处理的能力等，一个算

6、法的策略决定了该算法是否实现上述的目标，在计算机运行的当前环境，做出在哪个吋间段选择那种新进程的规则集就是调度策略m。近年来，很多学者将经济学中的博弈论应用于任务分配中较好地解决了智能体的资源分配问题，依据因对博弈论的贡献而获得诺贝尔经济学奖的RobertAumann教授的说法，博弈论就是研究互动决策的理论。所谓互动决策，即各行动方(player)的决策是相互影响的，每个人在决策的时候必须将他人的决策纳入自己的决策考虑之中，当然也需要把别人对于自己的考虑纳入考虑之中，在如此迭代考虑情形下进行决策，选择最有利于自己的战以至于不愿意改变策略。把博弈理论引入的内核进程抢占式算法中，并且

7、捉出一个概念声誉(Reputation)—个分量。进程博弈树我们把决策有先有后的博弈，叫做序贯决策博弈［21,因为有次序性质，所以我们这里不采用矩阵收益表示方法，而采用是扩展式的“树型”，根和分支点是决策节点(decisionnode),树梢即各枝梢是末端节点(terminalnode),博弈的“树型表示”，就是要在每个决策节点处说明这是谁的决策点，并且说明在这个决策点供它选择的策略或行动是什么，而且在末端节点，意味着博弈结束。在linux2.6中采用的是新调度机制基于两个优先级