Chinaunix首页 | 论坛 | 博客
  • 博客访问: 160931
  • 博文数量: 171
  • 博客积分: 2510
  • 博客等级: 少校
  • 技术积分: 1990
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-05 10:49
文章分类

全部博文(171)

文章存档

2011年(9)

2010年(162)

我的朋友

分类: LINUX

2011-03-28 14:54:30

1 前言

处 理机(CPU)是整个计算机系统的核心资源,在多进程的操作系统中,进程数往往多于处理机数,这将导致各进程互相争夺处理机。进程调度对系统功能的实现及 各方面的性能都有着决定性的影响,其实质就是把处理机公平、合理、高效地分配给各个进程。调度是实现多任务并发执行的必要手段,不同的操作系统有着不同的 调度目标。在传统的Unix类分时系统中,保证多个进程公平地使用系统资源,提供较好的响应时间是调度的主要目标;而在强实时操作系统中,总是优先级高的 任务优先获得处理机的使用权。

Linux具有内核稳定、功能强大、可裁减、低成本 等特点,非常适合嵌入式应用。但是Linux内核本身并不具备强实时特性,且内核体积较大,因此,想要把Linux用于嵌入式系统,必须对Linux进行 实时化、嵌入式化。Linux结合实时进程和非实时进程(普通进程)自身的特点,综合了上述几种调度策略,实现了高效、灵活的进程调度。

2 Linux进程调度分析

2.1 Linux进程状态的描述

Linux将进程状态描述为如下五种:

TASK_RUNNING:可运行状态。处于该状态的进程可以被调度执行而成为当前进程。

TASK_INTERRUPTIBLE:可中断的睡眠状态。处于该状态的进程在所需资源有效时被唤醒,也可以通过信号或定时中断唤醒。

TASK_UNINTERRUPTIBLE:不可中断的睡眠状态。处于该状态的进程仅当所需资源有效时被唤醒。

TASK_ZOMBIE:僵尸状态。表示进程结束且已释放资源,但其task_struct仍未释放。

TASK_STOPPED:暂停状态。处于该状态的进程通过其他进程的信号才能被唤醒。

2 调度方式

Linux中的每个进程都分配有一个相对独立的虚拟地址空间。该虚存空间分为两部分:用户空间包含了进程本身的代码和数据;内核空间包含了操作系统的代码和数据。

Linux 采用“有条件的可剥夺”调度方式。对于普通进程,当其时间片结束时,调度程序挑选出下一个处于TASK_RUNNING状态的进程作为当前进程(自愿调 度)。对于实时进程,若其优先级足够高,则会从当前的运行进程中抢占CPU成为新的当前进程(强制调度)。发生强制调度时,若进程在用户空间中运行,就会 直接被剥夺CPU;若进程在内核空间中运行,即使迫切需要其放弃CPU,也仍要等到从它系统空间返回的前夕才被剥夺CPU。

3 调度策略

3.1 三种调度策略

(1)SCHED_OTHER。SCHED_OTHER是面向普通进程的时间片轮转策略。采用该策略时,系统为处于TASK_RUNNING状态的每个进程分配一个时间片。当时间片用完时,进程调度程序再选择下一个优先级相对较高的进程,并授予CPU使用权。

(2)SCHED_FIFO。 SCHED_FIFO策略适用于对响应时间要求比较高,运行所需时间比较短的实时进程。采用该策略时,各实时进程按其进入可运行队列的顺序依次获得 CPU。除了因等待某个事件主动放弃CPU,或者出现优先级更高的进程而剥夺其CPU之外,该进程将一直占用CPU运行。

(3)SCHED_RR。SCHED_RR策略适用于对响应时间要求比较高,运行所需时间比较长的实时进程。采用该策略时,各实时进程按时间片轮流使用CPU。当一个运行进程的时间片用完后,进程调度程序停止其运行并将其置于可运行队列的末尾。

3.2  进程调度依据

Linux 只有一个可运行队列,处于TASK_RUNNING状态的实时进程和普通进程都加入到这个可运行队列中。Linux的进程调度采用了动态优先级和权值调控 的方法,既可实现上述三种调度策略,又能保证实时进程总是比普通进程优先使用CPU。描述进程的数据结构task_struct中用以下几个数据作为调度 依据:

Struct task_struct { …… volatile long need_resched; /*是否需要重新调度*/  long counter; /*进程当前还拥有的时间片*/long nice; /*普通进程的动态优先级,来自UNIX系统*/unsigned long policy; /*进程调度策略*/unsigned long rt_priority; /*实时进程的优先级*/……};

counter的值是动态变化的,进程运行时,每一个时钟滴答后,其值减1。当counter值为0时,表示该进程时间片已用完,该进程回到可运行队列中,等待再次调度。

为 保证实时进程优于普通进程,Linux采取加权处理法。在进程调度过程中,每次选取下一个运行进程时,调度程序首先给可运行队列中的每个进程赋予一个权值 weight。普通进程的权值就是其counter和优先级nice的综合,而实时进程的权值是它的rt_priority的值加1000,确保实时进程 的权值总能大于普通进程。调度程序检查可运行队列中所有进程的权值,选取权值最大者作为下一个运行进程,保证了实时进程优先于普通进程获得CPU。 Linux使用内核函数goodness()对进程进行加权处理:

Static inline goodness (struct task_struct * pint this_cpu, struct mm_struct *this_mm){ Int weight; Weight=-1;/*判断如果任务的调度策略被置为SCHED_YIELD的话,则置权值为-1,返回。系统调用SCHED_YIELD表示为“礼 让”进程,其权值为最低*/ If (p->policy & SCHED_YIELD) goto out;/*先对普通进程进行处理(由于多数是普通进程,这样做有利于提高系统效率)*/If (p->policy==SCHED_OTHER){ weight=p->counter; /*返回权值为进程的counter值*//*如果当前进程的counter为0,则表示当前进程的时间片已用完,直接返回*/ If (! weight) Goto out;#Ifdef CONFIG_SMP If (p->processor==this_cpu) Weight+=PROC_CHANGE_PENALTY;#Endif/*对进程权值进行微调,如果进程的内存空间使用当前正在运行的进程的内存空间, 则权值额外加1*/  If (p->mm==this_mm||! p->mm) Weight+=1;/*将权值加上20与进程优先级nice的差。普通进程的权值主要由counter值和nice值组成*/  Weight+=20-p->nice; Goto out;} /*对实时进程进行处理,返回权值为rt_priority+1000,确保优先级高于普通进程*/Weight=1000+p-> rt_priority; Out:return weight; }

从 goodness()函数可以看出,对于普通进程,其权值主要取决于剩余的时间配额和nice两个因素。nice的规定取值范围为19~-20,只有特权 用户才能把nice值设为负数,而表达式(20-p->nice)掉转方向成为1~40。所以,综合的权值在时间片尚未用完时基本上是两者之和。如 果是内核进程,或者其用户空间与当前进程相同,则权值将额外加1作为奖励。对于实时进程,其权值为1000+p->rt_priority,当 p->counter达到0时该进程将移到队列的尾部,但其优先级仍不少于1000。可见当有实时进程就绪时,普通进程是没机会运行的。

由此可以看出,通过goodness()函数,Linux从优先考虑实时进程出发,实现了多种调度策略的统一处理,其设计思想可谓非常巧妙。

阅读(539) | 评论(0) | 转发(0) |
0

上一篇:Linux系统在信息家电(IA)上的应用

下一篇:没有了

给主人留下些什么吧!~~