Chinaunix首页 | 论坛 | 博客
  • 博客访问: 216777
  • 博文数量: 53
  • 博客积分: 25
  • 博客等级: 民兵
  • 技术积分: 1550
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-27 07:54
  • 认证徽章:
个人简介

IT民工一枚,为学弟学妹造福是我一直写博文的动力!为媳妇提供技术支持是我学习新技术的动力!为自己脱离贫困线,买到心仪的摩托车,有饭吃,有床睡,有妹把,笔耕不辍~~

文章分类

全部博文(53)

文章存档

2013年(54)

分类: 信息化

2013-05-25 16:18:05

一、处理机调度类型

处理机就是我们说的CPU了,那是系统中最关键的资源之一,所以其调度的过程影响到了系统的整体性能。一般的处理机调度可以根据调度对象分为长调度(作业调度)、中程调度(交换技术)、短程调度(进程调度)或者说进程状态切换更明白些。从调度算法角度,不同类型中的调度方法可以有相同的模型抽象出来,但是对于具体的问题,又有不同的算法实现。甚至于到了内存换页,磁盘调度都会考虑到这些调度算法的实现过程,他们的想法都是让最优的对象首先执行,提高系统的资源利用率。

实际上,调度过程与进程状态切换息息相关,从新建到加入就绪队列,可以看做长调度,从就绪到运行态就是短调度,从挂起态到激活态就是中程调度了。我们这里讨论的是进程调度,近程调度,CPU调度,都是一个事儿。

进程调度的任务是控制和协调进程之间对CPU的竞争,换句话说,调度过程就是从就绪队列中选择将要执行的进程的过程。调度算法要解决三个问题:如何调度?何时调度?调度过程?

常见的调度算法这里就不罗列了,遍地都是。说一下调度时机吧,考虑两个角度,系统协调者角度:进程终止;进程阻塞;I/O中断;时钟中断等各种让出CPU的事件。进程角度:新进程创建后进入就绪队列,可以被调度;实际上,就绪队列更新后会发生新的调度事件,也就是调度时机。甚至可以这样说,跟运行态相关联的状态列表发生变更的时候,都会有调度事件发生。

调度事件发生后,需要进行进程切换的活动,说到底,进程的切换源于进程状态的转变,进程状态切换又基于调度时机和调度事件的发生。那么,进程切换过程中有会有那些步骤呢?

1.保存进程上下文信息到将要切换出的进程PCB中;

2.用新状态和其他信息更新即将切换出CPU的进程PCB;

3.将切换出的进程移到合适的队列;

4.选择另一个进程,就绪队列中没有进程时,运行IDLE;

5.更新被选中的进程PCB;

6.将被选中的进程信息装入系统上下文。

二、设计调度算法的原则

我们考虑调度算法的依据是被调度对象的种类,也就是进程的类型。一般情况下,有

交互式进程:需要经常与用户交互,花大量时间等待用户输入,响应时间要短,在用户可以忍受的范围内;

批处理进程:不必与用户交互,通常后台运行,不必计算响应时间,关注的是系统吞吐率和执行效率;

实时进程:对响应时间有刚性需求,不能被低优先级进程阻塞。

由于不同的系统类型有不同的用户需求,从而导致不同的调度算法。我们在选择调度算法的时候,从这个基本点出发,并遵循下边的规则。

进程控制块中的相关信息 ;进程优先级及就绪队列的组织 ;时间片大小选择及设置;抢占式调度与非抢占式调度 ;衡量指标(周转时间、归一化周转时间) ;调度器的开销 ;能否恒定(不依赖于当前系统负载);调度机制和调度策略分离的原则 ;是否会产生“饥饿” 。

三、典型调度算法

现在比较火的就是基于优先级的调度策略,那么我们有必要将优先数提前讲一下。在系统中,有静态优先数和动态优先数两种,顾名思义,静态就是在进程创建之初便赋予了优先级,而且在其生命周期中不会改变,动态优先级就不同了,也是在进程创建时给出的优先级,但随着系统运行,优先数会进行重算。如果把两者比作常量和变量,理解起来会方便一些。

有了优先级,就会有高优先级对低优先级的抢断,这种资源的抢断叫做抢占,有两种占用CPU的方式:可抢占式,不可抢占式。这种方式是在进程创建之初定义的,有的系统干脆将抢占形式做到了系统中,也就是说某一个系统只能是抢占或非抢占的系统。当然现在看来,那已经过时了。不过系统一直保留一种自带的抢占CPU的方式,那就是时间片。

时间片就是根据系统时间,向就绪队列中的进行发放的可运行时间段。根据不同复杂度的系统,也会有可变时间片的出现。当然最关键的问题在于,如何设置时间片,一个时间片设置为多大。一般情况下,时间片的大小依据切换进程的开销,系统响应时间的要求,就绪进程的个数等多个因素来权衡。

讲完这些基本的概念,我们来看一下最重要的部分,调度算法,从三种不同的进程系统方向来区分:

批处理系统

先进先出:最简单高效公平的方式;

短作业优先:使用贪婪算法,但会导致长作业饿死;

短剩余时间优先:跟短作业相似,只不过会查看当前系统中各个进程的运行状态;

高响应比优先:作业周转时间/作业处理时间,数值越大表示等待越久,越急需上CPU。

交互式系统

轮转调度:根据系统分配给就绪队列中的每一个进程的时间片进行轮转调度;

优先级调度:为等待的进程分配优先级,高优先级可以中断低优先级的进程,抢占CPU执行,这样会使低优先级进程饿死;

多级队列:为进程等待按照优先级先后分为多个等待队列,同等优先级在同一个队列,同一个队列内部可以按照RR调度,也可以按照高响应比调度;

最短进程优先:跟短作业优先相似;

公平竞争共享:这是一个理想的状态,真正的公平是不存在的;

保证调度:跟公平共享相同,为了达到公平,系统总是计算各个进程的运行时间,然后让等待时间最久的上CPU

彩票调度:类似于彩票制度,系统给每一个进程发放调度号,然后每一次都会随机产生一个调度号,与调度号一致的进程得以运行。

实时调度

调度算法比较单一,为了达到及时响应,可以计算进程的紧急程度,为各个进程调度进行简单的分配,实际上,进程的调度和切换带来的开销对于实时系统来讲是致命的。所以,尽量少的进行调度就是最好的算法。
常见操作系统采用的调度策略:

UNIX动态优先级

BSD多级反馈调度队列

Windows基于优先级的抢占式多任务调度

Linux抢占式调度

Solaris综合调度算法

四、调度实例--windows

windows 中,调度对象是线程,上文已讲,windows是基于优先级的抢占式多任务调度算法,但是应该注意,不同的处理机个数,其调度算法是不同的。

就绪线程按照优先级进入等待队列;系统总是先运行优先级高的线程;同一个优先级的线程按RR进行调度。

线程调度时机

引用调度部分的一句话,当与运行态相关联的队列中发生变化时,就是调度时机了。还有一种情况是系统或者线程本身因为系统调用而改变了优先级,产生调度事件;

Windows中使用32个优先级,分为三类,实时优先级,可变优先级,系统线程。其中有几个特殊的优先级编号,比如0号优先级用于对系统中空闲的物理页面清零。

阅读(744) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册