《Linu内核进程抢占式调度的博弈决策》由会员分享，可在线阅读，更多相关《Linu内核进程抢占式调度的博弈决策（5页珍藏版）》请在金锄头文库上搜索。
1、Linux 内核进程抢占式调度的博弈决策林攀(江苏大学 计算机科学与通信工程学院 江苏 镇江)摘要:以博弈论的思想来解读Linux 2.6内核进程调度的策略，在博弈树构造 中寻找纳什均衡，已达到计算机资源协调，实现资源的最优化；通过研 究非实时进程的时间片策略，分析进程调度的策略，在做出策略后它们 的是否实现调度设计目标，把博弈理论中得声誉名词引入进程调度中， 衡量决策的优良性能指标，用复出的内部机制，让超时的进程得到复出 的机会。关键词:进程调度；博弈论；声誉； 复出引言 从古代开始，数学家研究室内游戏，试图构造一个最优的游戏策略，至到20 世纪中期左右，计算机之父约翰冯诺依曼提出了新的研究
2、成果，一个真正的， 严谨的，模型化的关于策略环境的理论产生了，被称为博弈论(Game Thory)， 目前博弈论广泛应用到数学、经济、社会学、生物、计算机等学科，它主要研究 决策主体的行为发生相互作用的时候主体的决策以及这些决策之间的均衡问题， 数学家纳什提出的纳什均衡是博弈论的核心，这是一种有着深刻意义的理念，越 来越到底认可，经济学家和数学家不断研究。自由开放 Linux 操作系统凭借其开源代码的优势，得到广泛的认可，内核一 直不断完善，尤其 Linux 2.6 在内核实现了抢占式优先级算法，一个优良的调度 算法必须同时兼顾以下几个互相冲突的目标：(1)响应时间尽可能短、系统吞吐 量可能的
3、高、考虑进程死锁公平的问题、异常处理的能力等，一个算法的策略决 定了该算法是否实现上述的目标，在计算机运行的当前环境，做出在哪个时间段 选择那种新进程的规则集就是调度策略1。近年来, 很多学者将经济学中的博弈 论应用于任务分配中较好地解决了智能体的资源分配问题，依据因对博弈论的贡 献而获得诺贝尔经济学奖的RobertAumann教授的说法，博弈论就是研究互动决 策的理论。所谓互动决策，即各行动方(player)的决策是相互影响的，每个人在决策 的时候必须将他人的决策纳入自己的决策考虑之中 ，当然也需要把别人对于自己 的考虑纳入考虑之中 ， 在如此迭代考虑情形下进行决策 ，选择最有利于自己的战
4、略2( strategy)，以至于不愿意改变策略。把博弈理论引入的内核进程抢占式算法 中，并且提出一个概念声誉(Reputation)个分量。进程博弈树 我们把决策有先有后的博弈，叫做序贯决策博弈2，因为有次序性质，所以 我们这里不采用矩阵收益表示方法，而采用是扩展式的 “树型”，根和分支点是 决策节点(decision node),树梢即各枝梢是末端节点(terminal node),博弈的树 型表示”，就是要在每个决策节点处说明这是谁的决策点，并且说明在这个决策 点供它选择的策略或行动是什么，而且在末端节点，意味着博弈结束。在 linux2.6 中采用的是新调度机制基于两个优先级参数策略：
5、静态优先级与动态优先级。静 态优先级是用于计算机进程的时间片，而动态优先级是作为调度器选择当前“合图1 进程博弈树适”进程的直接依据。图 1 是一个典型的博弈树，节点 A 是 决策的起点，在启动进程运行时，就面临 着做出决策，通过rt_task()算法的判断是 实时进程还是普通的进程，从而A-B还是 A-C。B是非实时进程的时间片的策略， 它的时间片由进程的静态决定，当在B节 点时， 需要在非对称信息集里查看 shedular_tick()函数，时间片是否为0,产 生了 D、E 两个节点， C 是实时进程的时 间片，根据实时进程策略的不同，设置不 同的时间片，体现了极大的灵活性，F、G 分别是
6、 SHED_FIFO 和 SCHED_RR 调度策略。在 linux 内核里进程的动态博弈树并不是完全的树，其博弈树典型地还可以 具有各种形式，在内核中调度器会根据优先级，时间片等会呈现非对称的树，可 能会茂盛和稀疏的树。在理想的情况下，负载能力均衡的是最优二叉树，总之， “树”的生长方向，就是博弈进行就是博弈进行的方向，“进程树”的生长，反 映博弈决策时刻的进程,一个成功进程的调度存在纳什均衡，纳什均衡就是参与 者不愿意改变选择，否则它的收益(payoffs)会降低，是所有博弈者的一个策 略组合，其中一个策略组成要成为纳什均衡，必须使这个组合的每个策略和其他 的策略构成最优反映函数(best
7、 response),在进程调度中，调度器按着设计提 出的目标要求，进行进程策略组合， 必然找到纳什均衡点，但是当进程被阻塞， 且拥有某些临界资源的情况，当前进程通常是不能释放处理器、进入睡眠状态，进而会导致系统死锁，这就不是纳什均衡，对于它们来说，不是最优函数，损失 收益就是使其他的进程得不到处理器的权利，资源浪费、死循环等。不良的进程 表现，一个进程策略的所得并不一定意味着计算机内部资源遭受损失，更不一定 意味使它的进程运行要遭受同样数量的损失，总之，不同进程策略的收益不存在 “零和博弈”的简单的不协调的合作关系，这里包含着一个哲理，当进程选择策 略，它们彼此之间可能存在某种共同的利益，这
8、样它们都能顺利运行，不会出现 死锁，异常等槽糕的情况，蕴含博弈它们之间是 一种“双赢”或“多赢”的博 弈理念，把这种和谐理念运用到进程博弈树中，所有调度算法同时兼顾几个互相 冲突的目标，保证进程间的公平，避免饿死现象。BA图 3 树与子树图 2 进程博弈树三例复出机制著名学者泽尔滕(R.Selten) 提出了子博弈精炼纳什均衡 的概念，意思是在一个博弈的 所有作为纳什均衡的策略组 合当中，那些局限在每个子博 弈上都仍然是哪个子博弈的 纳什均衡的策略组合2。如图， 是划分后的其中的一个子博 弈树，它的含义是通过检查进 程的动态优先级是否大于MAX_RT_PRIO来判断是否是 普通的进程，选择了非
9、实时进 程的时间片策略，在时钟中断 处理中，调用的 schedule tick ( )函数，负责减少当前进程的剩余时间片，并检测剩余时间是否为0，如果为0 (D 表 示 ,E 表示不为 0 )、表示进程已经用完了为它分配的时间片，为了下次还可以运行，此时重 新计算其的时间片和动态优先级，然后把该进程插入运行队列中得超时优先级数组 expired 中，且以 TIF_NEED_RESCHED, 为进程标示以便在时钟中断返回时激活调度进程选择下一 个进程投入运行，在右图中，是一个子博弈图，探寻最可能发生的并且具有最好的稳定性的 结果，根据定义当利用博弈树考察一个纳什均衡时，只有其中的某一个子博弈上它
10、不再是纳 税均衡，就可以说所考察的纳什均衡不再是子博弈精炼纳什均衡，对这个子博弈没有稳定性的结果，但不是这个博弈的子博弈精炼纳什均衡。调度器的随机执 行，稳定性的结果存在着概论。在内部机制里，设置睡眠时间sleep_avg来计算进程的奖励 时间，定义取值0 到 10 的变化，由于非实时进程的动态优先级以静态优先级为基础辅助奖 惩记录，所以用户还可以调整进程的静态优先级来影响动态优先级，下面根据所处的策略点 采取非实时时间片计算：Task_timeslice(task_ *p)If (p-static_priostatic_prio);Elsereturn SCALE_PRIO(DEF_TIME
11、SLICE,p-static_prio);/* NICE_TO_PRIO=120. 非实时进程的时间片是固定的公式 */在超时优先级数组expired中，有些进程和其他的进程比较，表现良好，它又急需投入 到处理机运行，需要设置一个具有人性化的博弈策略，可以建议采用复出(Realive)机制， 设置历史记录history()函数，保存那些进程的ID,进程描述符、优先级、奖励值的等选 项，综合它们的各项指标成为一个进程的声誉(Reputation)，声誉是让一个超时的进程重新 获得重生的权利，马上放到运行队列，等候处理机的资源，不再等时钟中断返回时激活调度 进程选个下一个进程投入运行，下面是一段伪
12、代码：Int History()If(best-prior& given values& last performance) / 条件的判断Enter into running queen and capture CUPThenOut of over-time . it have no right of alive / 进入下轮Exit(0)图表 4从上面的算法提取一个简单的模型，它就是著名的霍特林模型(HeteHing Model)，此模型 描述的进程为了可以复活的机会形成对立形势：在中点1/2进程的收益向两侧逐步减小。任 何一方单独偏离目前的位置(1/2),即单独改变策略，都不会得到进一步
13、的好处， 1/2 出是超 时进程数组的最大收益，也就是唯一可以复活的进程。结束语Linux 的抢占式进程算法，是效率较高的一种算法，随着 linux 发展，可能朝着多级反馈 队列调度，综合了时间片轮转调度和抢占式优先权调度的优点，即：优先权高的进程先运行 给定的时间片，相同优先权的进程轮流运行给定的时间片。同时随着博弈研究的深入，它和 计算机学科的联系越来越紧密，用博弈的思想理解linux的进程调度，来描述进程的动态过 程是必然的趋势，假如把他们与人工智能结合起来，设计进程调度策略，更是人类智能思维 的结晶。参考文献：1 河秦、王洪涛linux 2.6内核标准教程M.人民邮电出版社，20082 王则柯、葛菲纳什均衡-动态博弈的初步讨论M人民邮电出版社，20093 涂志勇 博弈论M.北京大学出版社，20094 Stategy: An Introduction to Game Theory M.费方域等译 格致出版社上海三联书店上海人民出版社，2010
