Linux2.6进程调度分析(1)-调度策略

2011年4月3日 由 edsionte 留言 »

对于分时操作系统而言,表面上看起来是多个进程同时在执行,而在系统内部则进行着从一个进程到另一个进程的切换动作。这样的进程并发执行涉及到进程切换(process switch)和进程调度(process scheduling)两大问题。本文主要说明Linux2.6中的普通进程调度策略(实时进程和普通进程在调度上稍有不同)问题,即系统何时进行进程切换以及选择哪一个进程进行切换。

1.调度策略

理想的进程调度目标应该是:进程响应时间尽可能的快,后台作业吞吐量高,避免某些进程出现饥饿现象,包括低优先级在内的所有进程都有被调度的可能。由此看来,进程调度的工作就是要处理好这几个方面的协调关系,使进程调度的综合性能达到最佳。

与进程调度最为密切的因素是进程的优先级,进程优先级通过一个数值来实现,每个进程都与一个值相关联。调度程序根据进程的优先级将CPU适当的分配给某一个进程。进程的优先级又跟进程的许多因素有关,接下来我们将依次分析这些因素与进程优先级的关系。

1.1进程的分类

进程可以被分为两种类型:I/O消耗型和CPU消耗型。前种类型的进程频繁使用I/O设备,并且大部分时间处于等待状态,以得到新的I/O请求,比如键盘活动等。后一种类型的进程则大部分时间都在占用CPU,对I/O设备并没有过多的需求。

为了使系统有较强的响应能力,I/O消耗型进程必须很快能被唤醒,以实现进程的切换。否则,用户会感到系统反应迟钝。对于CPU消耗型进程,由于它们常常位于后台运行,并且没有过多的I/O需求,因此系统并不需要对这类进程做出快速反应。

正如上面所说的,调度程序通常要处理好这两类进程之间的调度关系:系统既要有迅速的响应能力,又要有最大的CPU利用率(高吞吐量)。这种满足关系其实是矛盾的,如果系统要达到最大利用率,那么CPU就会被一直占用,这样就不能对I/O请求做出迅速响应。调度程序为了调和这种冲突,通常会倾向于I/O消耗型进程。也就是说,调度程序会优先调用这类进程以提高系统的响应能力,而尽量将CPU消耗型进程压后执行。但这并不意味着这类进程就被调度程序忽略。

1.2时间片

Linux的调度是基于分时技术的,多个进程以“时间多路复用”的形式运行,CPU的时间被划分成一小段,即所谓的时间片(slice)。每个进程都会得到一个时间片,在具体某个时间片内,一个进程会独享CPU时间。如果该进程在这个时间片内没有运行完毕,调度程序就会切换该进程使得其他拥有时间片的进程运行。

时间片的划分对系统来说也是一件难事,既不能过长又不能过短。过长的时间片会导致系统的响应能力下降;而过短的时间片会导致系统频繁发生进程切换,由此将带来不必要的处理器消耗。显然,I/O消耗型进程希望时间片越短越好,这样那些等待I/O的进程就能被迅速切换;而CPU消耗型进程则希望时间片越长越好,这样它们就可以一直占用CPU。因此,I/O消耗型进程和CPU消耗型进程的矛盾再一次显现出来。

Linux调度程序解决这种矛盾的方法是,提供一个较长的默认时间片,但是却提高交互进程的优先级,以使得这些进程运行的更频繁。在Linux的调度算法中,每个进程在诞生时总是继承父进程一半的时间片,而之后的时间片则是调度程序根据进程的静态优先级而分配。

1.3优先级

我们上面说过,调度程序在选取下一个执行的进程时依据的是进程的优先级。通过上面对进程的划分可以看出,不同类型的进程应该有不同的优先级。每个进程与生俱来(即从父进程那里继承而来)都有一个优先级,我们将其称为静态优先级。普通进程的静态优先级范围从100到139,100为最高优先级,139为最低优先级。

当进程用完了时间片后,系统就会为该进程分配新的时间片(即基本时间片),静态优先级本质上决定了时间片分配的大小。静态优先级和基本时间片的关系如下:

静态优先级<120,基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)
静态优先级>=120,基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

其中MIN_TIMESLICE为系统规定的最小时间片。从该计算公式可以看出,静态优先级越高(值越低),进程得到的时间片越长。其结果是,优先级高的进程会获得更长的时间片,而优先级低的进程得到的时间片则较短。

进程除了拥有静态优先级外,还有动态优先级,其取值范围是100到139。当调度程序选择新进程运行时就会使用进程的动态优先级,动态优先级和静态优先级的关系可参考下面的公式:

动态优先级=max(100 , min(静态优先级 – bonus + 5) , 139)

从上面看出,动态优先级的生成是以静态优先级为基础,再加上相应的惩罚或奖励(bonus)。这个bonus并不是随机的产生,而是根据进程过去的平均睡眠时间做相应的惩罚或奖励。

所谓平均睡眠时间(sleep_avg,位于task_struct结构中)就是进程在睡眠状态所消耗的总时间数,这里的平均并不是直接对时间求平均数。平均睡眠时间随着进程的睡眠而增长,随着进程的运行而减少。因此,平均睡眠时间记录了进程睡眠和执行的时间,它是用来判断进程交互性强弱的关键数据。如果一个进程的平均睡眠时间很大,那么它很可能是一个交互性很强的进程。反之,如果一个进程的平均睡眠时间很小,那么它很可能一直在执行。另外,平均睡眠时间也记录着进程当前的交互状态,有很快的反应速度。比如一个进程在某一小段时间交互性很强,那么sleep_avg就有可能暴涨(当然它不能超过MAX_SLEEP_AVG),但如果之后都一直处于执行状态,那么sleep_avg就又可能一直递减。

理解了平均睡眠时间,那么bonus的含义也就显而易见了。交互性强的进程会得到调度程序的奖励(bonus为正),而那些一直霸占CPU的进程会得到相应的惩罚(bonus为负)。其实bonus相当于平均睡眠时间的缩影,此时只是将sleep_avg调整成bonus数值范围内的大小。

参考:

1.深入理解LINUX内核(第三版) ;(美)博韦,西斯特 著; 陈莉君 张琼声 张宏伟译; 中国电力出版社;

2.Linux内核设计与实现;(美)拉芙(Love,R.)著,陈莉君 等译;机械工业出版社;

广告位

发表评论

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key