分享
 
 
 

[初探linux2.6内核-进程调度][04.07.08]

王朝system·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

Linux2.6版本中的进程调度作了不小的改变。

1、引入调度域概念

每一个CPU都有一个“基本”的调度域(struct sched_domain)。函数cpu_sched_domain(i)和宏this_sched_domain()用来表示可以使用的cpu域。域的层次结构均是通过->parent指针所指向的基础域而构建的。->parent指针要保证以NULL结束,而且应当为每个CPU分配域结构以便于CPU的增加。

在每一个调度域的范围内都拥有几个CPU(存于->span中)。调度域的范围意思是:“在各CPU之间达到负载的平衡”。一个域的范围必须不小于它的子域范围,而且CPU i的基础域范围至少为i。位于域层次结构最顶层的域的范围将覆盖系统中的所有CPU。

每一个调度域都必须有一个或多个CPU组(struct sched_group),用->groups指针链接成一个环形。而这些组的cpumask在域范围内都必须是相同的。任意的两个组的cpumask交集必须为空集(即不相同)。->groups指针所指向的组必须包含这个域所拥有的CPU。而当某些组被建立后,它们可能因为包含一些只读数据而被CPU所分享。

在组之间会发生调度域的平衡操作。这个时候,每一个组将被当成一个整体。组的负载将被定义为其每一个CPU的负载总和。所以当组与组的负载不平衡时,将发生调度域的平衡操作,在组与组之间进行平衡。

在kernel/sched.c中,rebalance_tick在每一个CPU上周期性的运行。这个函数在CPU的基础调度域内检查是否重新达到了平衡。如果是, 则将在那个域内运行load_balance。而rebalance_tick将接着检查父调度域(如果有的话),进而是父调度域的父调度域,如此下去。

“基础”域的“范围”将构成域层次结构的第一级。在SMT情况下,将跨度所有的物理CPU,而每个组将有一个虚拟CPU。

Linux 2.6内核为多程序提供了一种不同的途径,即NUMA(Non Uniform Memory Access)。这种方法中,内存和处理器是相互连接的,但对于每一个处理器,某些内存是“关闭”的,而某些内存则“更远”。这意味着当内存竞争出现时,“更近”的处理器对就近的内存有更高的使用权。2.6版内核提供了一套功能来定义内存和处理器之间的拓扑关系。调度程序可以利用这些信息来为任务分配本地内存。这样将减少内存竞争造成的瓶颈,提高吞吐量。

在SMP中,基础域的父域将跨度所有节点上的物理CPU。而每个组将有一个物理CPU。通过NUMA,SMP域的父域将跨度整个机器,而每个组将有每个节点的cpumask。或者,你可以采用多级NUMA或Opteron。

2、新的调度器算法O(1)

a)ultra-scalable O(1) 调度器优点:

-即使在高负载的时候也能有比较好的交互性能

-在1-2个进程调度和唤醒上有更好的性能

-公平性:没有哪个进程拥有极多的CPU占有时间

-优先级:重要任务优先级高,反之亦然

-SMP效率:如果有任务,将不会有空闲的CPU

-SMP相关:进程将尽可能的在一个CPU上运行,进程不会在不同的CPU上频繁迁移

b)新调度算法带来的改变:

-完全的O(1)调度算法:取消了重算循环(recalculation loop)和优先级循环(goodness loop)

-真正的SMP:取消了runqueue_lock,而采用每个CPU均有独立的runqueues和locks-两个独立的CPU上的任务可以同时(并行的)被唤醒、调度 和上下文切换,不再需要任何的interlock。所有要调度的相关数据均能最大范围的划分进来。

-更好的SMP相关[映射]:旧的调度器有个特别的缺点,就是当有更高优先级或实时任务时,任务会在CPU间任意的迁移。而其原因就是时间片重 算循环(timeslice recalculation loop)首先需要计算当前正在运行的每个任务的时间片开销。时间片重算算法要求在所有的进程都用尽它们的时间片后,新时间片才会被重新计算。在一个多CPU系统中,当进程用完它们的时间片后不得不等待重算,以得到新的时间片。但是当这种情况发生时,有可能会造成一部分CPU空闲出来而不运行任何任务。只有当最后一个只有一个时间片的任务用完它的那个时间片后,重算循环才被激活,而其它的CPU才可以继续执行任务-在CPU空闲运转几个时钟间隔后。因此,CPU越多,效果越恶劣。

另外,还有一种情况会引起同样的效果:当有一个全局运行队列中的某任务“时间片剩余”,空闲的CPU将开始运行该任务,但该任务初始时并不 是运行于该CPU的(因为和该CPU相关[映射]的任务的时间片已经用完了),也就是指当空闲CPU开始执行那些时间片尚未用尽的、处于等待状态的进程时,会导致进程在处理器之间“迁移”。

新的调度器以单个CPU为单元来分配时间片,从而解决了这个问题,取消了全局同步和重算循环。

-批处理调度。

-平衡负载,降低那些超出CPU负载能力的进程的优先级,从而不会崩溃,也不会产生调度风暴

-O(1) RT 调度。

-在父进程之前,运行已创建的子进程

c)新调度器的运行机制

-每个CPU均有两个具有优先级的队列。一个“活动”队列,一个“过期”队列。活动队列中包含所有映射于该CPU并具有时间片的任务。而过期队列包含所有已经使用完时间片的任务(依然是一个有序队列)。活动队列和过期队列不能直接访问,而是通过每个CPU的运行队列结构中的两个指针来访问。调度程序不需每次都扫描所有的任务,而是在一个任务变成就绪状态时将其放到“活动”的队列中。当调度程序运行时,只选择活动队列中最有利的任务来执行。这样,调度可以在一个恒定的时间里完成。当任务执行时,它会得到一个时间片,或者在其转到另一线程之前得到一段时间的CPU使用权。当时间片用完后,任务会被转移到“过期”的队列中。在该队列中,任务会根据其优先级进行排序。 当活动队列中的任务均被运行完时,我们就交换两个指针,从而使得先前的过期队列成为活动队列,同样先前空闲的活动队列将转变为过期队列。因此,可以看得出来,“活动”队列中总是排好了顺序的任务队列,如此提高了速度。

-有一个64-bit位图的缓存用来存放队列索引。因此查找最高级的任务用两个x86 BSFL bit-search 指令就可以完成。

分离队列的方法使得我们能控制活动任务和过期任务的数量,而且当时间片使用完后,可以迅速的重算时间片。因为访问队列是通过运行队列中的两个指针,交换指针基本上是非常快的,所以交换两个队列将相当的快速。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有