两种调度算法的公平性与交互性比较与研究

《两种调度算法的公平性与交互性比较与研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、两种调度算法的公平性与交互性比较与研究在本文中，我们对两不同的算法的公平性，交互性，多处理器下的表现进行了系统的分析与测试。它们是：O(1)，CFS。　　关键词调度算法；公平性；交互性　　TP39A1674-6708（2011）54-0199-02　　1对两个LINEX调度算法的分析　　1.1O(1)调度算法　　O(1)调度用两个数组来存储运行的任务：运行数组和等待数组。调度算法选择运行数组中优先级最高的任务来执行。当任务的时间片用完，任务被排队进入等待数组。当运行数组为空时，这两个数组的指针将会相互交换，这时等待数组将会变成运行数组

2、。　　1.1.1公平性　　O(1)是一个依赖于时间的优先级调度算法。每个任务的初始时间片的计算基于它的静态优先级　　　　　　对于多处理器的加载平衡，一个基于它的初始时间片加权因子in，计算出这些任务的最大LAG值和平均LAG值。图1是n为2，4，8，16的结果。　　MaxMinAvg　　O(1)183741122　　CFS123118120.33　　　　就像我们上面讨论的那样，三度算法在长时间的运行过程中表现出了很好的公平性，而CFS在三个算法中给出了最小的平均LAG值.　　2.2交互性结果　　O(1)表现出了明显的不公平性因为任务集

3、A中的任务因为长时间的睡眠被认为是交互任务而被赋予了较高的优先集，因此它们总是被执行而很少进入等待队列.　　CFS通过给一个额外的SYSCTL_SCHED_LATENCY的时间段运行来奖励交互任务，所以任务集A比任务集B占用更多的cpu时间。SD-I的表现和CFS相近，因为一个唤醒的任务排到第一个被允许的优先级水平，所以得到了一些格外的优先级水平来执行。　　根据ring-test的测试，O(1)算法会鼓励一个能分叉出大量的线程的任务以偷取CPU时间,导致对其它任务的不公平。　　2.3加载平衡性　　当我们运行10个任务，每个任务是一个无

4、限循环，在测试平台上运行10min，每个任务分配t秒的CPU时间。O（1）算法在这种情况下不会去处理任务在CPU之间的平衡。这导致在有6个CPU每个是1个任务还有2个CPU，每个是2个任务。而CFS算法会将有2个任务的CPU上的一个任务拉给只有一个任务的CPU,从而得到更好的平衡。