操作系统调度准则什么

2018-05-16 21:31:23 legendaryhaha 阅读数 1351

1.面向用户(User-oriented)的准则和评价

 

(1)周转时间(Turnaround Time)短

  它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始,

到作业完成为止的这段时间间隔。

  周转时间  Ti = 完成时间-到达(提交)时间

 

(2)响应时间(Response Time)快

响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开

始,直至系统首次产生响应为止的时间。

 

(3)截止时间(Deadline)的保证

 

它是用来评价实时系统的重要指标,截止时间是某任务必须执行的最迟时间,或完成

的最迟时间

 

(4)优先权(Enforcing Priorities)准则

在选择批处理、分时和实时系统的调度算法时,都可引用优先权准则,以便让那些紧

急的作业(或事件),得到及时的处理。在要求较严格的场合,往往还需选择抢占调

度方式,才能保证紧急作业得到及时的处理。

 

2。面向系统(System-oriented)的准则

 

(1)达到系统设计目标

系统的设计目标是选择算法的主要依据。例如批处理系统所追求的是充分发挥和提高

计算机的效率,分时系统则侧重于保护用户的请求及时给予响应,实时系统所关心的

是不要丢失实时信息并给予处理。

 

(2)系统吞吐量(throughput)大

这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数,它与

批处理作业的平均长度具有密切关系。

 

(3)处理机利用率(Processor Utilization)高

对于大中型多用户系统,由于CPU价格十分昂贵,所以处理机利用率成为衡量大、中

型系统性能的十分重要指标,但对单用户微机或某些实时系统,该准则就不那么重

要。

 

(4)各类资源的平衡利用(Balancing Resources)

在大中型系统中,有效地利用各类资源(包括CPU、外存、I/O设备等)也是一个重要

指标,对于微型机和某些实时系统,该准则也不重要。

 

进程的调度算法

先来先服务算法(FCFS)

按进程的先后次序进行调度,谁最先请求,就调度谁。

 

短进程优先算法(SJF)

每一调度都挑选要求运行时间最短的进程

 

高响应比算法(HRRN)

根据RP从大到小进行调度。记得每次调入一个进程后,再调入一个进程时要重新计算RP值。

 

 

 

 

 

 

 

 

 















 

 

 

2020-01-19 23:30:23 valada 阅读数 0

进程调度是操作系统的基本组成部分,是实现多道程序操作系统的基础。操作系统可以合理有效的进行各种任务进程的切换也是基于进程调度来实现的,所以说认识理解进程调度对于学习操作系统尤为重要,当然对于实际开发也是有影响的,掌握进程调度会让我们了解操作系统底层是如何进行任务调度切换的,对于开发程序很有启发意义。

在本场 Chat 中,我首先会介绍进程调度的基本概念,然后会介绍进程调度的一些选择比较准则,最后会介绍各种调度算法的原理,例如先来先服务算法、最短作业优先算法、抢占式/非抢占式优先级调度算法、时间片轮转调度算法等。

阅读全文: http://gitbook.cn/gitchat/activity/5e187d6fc0a3723fe26c60c6

您还可以下载 CSDN 旗下精品原创内容社区 GitChat App ,阅读更多 GitChat 专享技术内容哦。

FtooAtPSkEJwnW-9xkCLqSTRpBKX

2015-04-26 21:50:59 u014174955 阅读数 1835
1.调度的类型
按调度的层次:
长期(长程、作业、高级)调度;
中期(中级、中程)调度;
短期(短程、进程、低级)调度
OS的类型:
批处理调度
分时调度
实时调度
多处理机调度
等等

面向用户的准则
周转时间短
响应时间快
截止时间的保证
优先权准则
面向系统的准则
系统吞吐率高
处理机利用率好
各类资源的平衡利用


面向用户的准则:1、周转时间短

定义
作业周转时间(Turnaroundtime)是指从作业提交给系统开始,到作业完成为止的这段时间间隔。
包括:

1)作业在外存后备队列上等待作业调度的时间

2)进程在就绪队列上等待进程调度的时间(waitingtime)

3)进程在CPU上执行的时间

4)等待I/O操作完成的时间

   其中,第2、3、4项在一个作业的处理过程中,可能发生多次

用户和系统管理员对周转时间有不同的需求
定义:平均周转时间
qqq.jpg 

定义:带权周转时间:作业周转时间T与系统为它提供的实际服务时间Ts之比,即W=T/Ts
定义:平均带权周转时间

qqaaq.jpg 
通常将周转时间作为评价批处理系统的性能、选择作业调度方式和算法的准则
面向用户的准则:2、响应时间快
定义:
响应时间(Responsetime)

是从用户通过键盘提交一个请求开始,直至系统首次产生响应为止的的时间,或者说直到在屏幕上显示出结果为止的一段时间间隔。包括:
从键盘输入的请求信息传送到处理机的时间
处理机对请求信息进行处理的时间
将所形成的响应回送到终端显示器的时间
响应时间常用于评价分时操作系统的性能,是选择分时系统中进程调度算法的重要准则之一
面向用户的准则:3、截止时间的保证
定义:截止时间(Deadline)
是指某任务必须开始执行的最迟时间,或者必须完成的最迟时间。
截止时间是用来评价实时系统性能的重要指标,因而是选择实时调度算法的重要准则

实时系统
软实时系统(softreal-time)  vs  硬实时系统(hard real-time)
非实时系统
面向用户的准则:4、优先权准则
引入优先权

使用优先数表示优先权
优先权高者优先执行

必要时,引入抢占


面向系统的准则:1、系统吞吐率高
定义:吞吐率(Throughput)是指系统在单位时间内完成的作业数
是用于评价批处理系统性能的重要指标,也是用于选择批处理作业调度的重要准则

吞吐率与作业的平均长度有关
大型作业
中、小型作业
吞吐率与作业的调度算法也有关


面向系统的准则:2、处理机利用率好
CPU是稀缺资源
定义:处理器利用率CPUUtilization) =

11aaq.jpg 

进程调度方式和算法对CPU利用率起着十分重要的作业
对于大中型多用户系统,CPU利用率是衡量系统性能的重要指标
40%90%
面向系统的准则:3、各类资源的平衡利用
CPU之外的其他资源,例如内存、外存、I/O设备
2018-01-11 21:12:59 zy2317878 阅读数 399

写在前面:

这一部分学习调度方式的若干准则。在一个操作系统的设计中,应如何选择调度方式和算法,在很大程度上取决于操作
系统的类型及其目标。例如,在批处理系统、分时系统和实时系统中,通常都采用不同的调度方式和算法。选择调度方式和算法的准则,有的是面向用户的,有的是面向系统的。在系统学习这些知识之前,可以先看一个生活中常见的故事。

用打开水来理解这些算法

一栋楼里有一个开水间,大家都要去开水间打水,大家每个人拿的接水的容器都不一样,有的那水库,有的拿水杯。开水间放水的速率一样,那么拿水壶接水的时间就长,拿水杯接水的时间就短。

现在,大家都来接水了,按照先来后到的顺序排队,一个用完水龙头换下一个,那么这就是FCFS算法。谁先来,谁先用,即先来先服务,first come first serve。

后来,大家发现一个问题,只拿水杯的人万一前面有拿水壶的,就要等拿水壶的打完才能用,而自己就是一个水杯,很快就能用完水龙头,却被迫等了好长时间,所以,规定,大家用水杯的可以先去打水,那么这就是SPF或SJF算法。

再后来,大家发现让打水杯的先去接水确实照顾了只占用水龙头一会的人,但是,虽然那些拿水壶的人不是特别着急,但是,这个方法说白了,还是经常让拿水杯的去插拿水壶的人的队。插队是不好的,尤其是在某些人着急用开水的情况,所以,大家又出了一个规定,根据大家用水的优先权来判断谁先来用水龙头。这就是FPF算法。

有一天,一个拿水壶的人刚来打水,打了一会,来了一个拿水杯的人,如果他不急,就等水壶接满再换人,如果他很着急,那么水壶就先暂停接水,让水杯接满就走了,然后继续接水。这就是非抢占式与抢占式调度算法。

这个算法比之前就复杂一些了。大家刚开始就制定优先权嘛,比如,根据用水需求来分,需要服务会议的人可以先接水,需要烧水做饭的人先接水等等。还根据接水的多少来确定,少的先接,多的后接。还根据用水的紧迫性来分,有的人好几天没喝水了就先接,有的人家里还有水就后接。这就是采用静态优先权来判断了,

但是楼里的人越来越多,大家用水的情况也越来越复杂,人们发现就算是这样,也会总有人用不上水,于是就通过判断等待用水的时间来优先,比如有的人等了好几天,就不能再被插队了,就优先用水,这就是动态优先权了。

面向用户的准则

为了满足用户的需求所应遵循的一些准则。

(1)周转时间短
通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。周转时间,是指从作业被提交给系统开始,到作业完成为止的这段时间间隔(称为作业周转时间)。

包括四部分时间:作业在外存后备队列上等待(作业)调度的时间,进程在就绪队列上等待进程调度的时间,进程在 CPU 上执行的时间,以及进程等待 I/O 操作完成的时间。

平均周转时间描述为:
这里写图片描述
作业的周转时间 T 与系统为它提供服务的时间 Ts 之比,即 W = T/Ts,称为带权周转时间,而平均带权周转时间则可表示为:
这里写图片描述

(2)响应时间快
响应时间的长短用来评价分时系统的性能,这是选择分时系统中进程调度算法的重要准则之一。响应时间,是从用户通过键盘提交一个请求开始,直至系统首次产生响应为止的时间,或者说,直到屏幕上显示出结果为止的一段时间间隔。

包括三部分时间:从键盘输入的请求信息传送到处理机的时间,处理机对请求信息进行处理的时间,以及将所形成的响应信息回送到终端显示器的时间。

(3)截止时间的保证
这是评价实时系统性能的重要指标,因而是选择实时调度算法的重要准则。截止时间,是指某任务必须开始执行的最迟时间,或必须完成的最迟时间。对于严格的实时系统,其调度方式和调度算法必须能保证这一点,否则将可能造成难以预料的后果。

(4)优先权准则
在批处理、分时和实时系统中选择调度算法时,都可遵循优先权准则,以便让某些紧急的作业能得到及时处理。在要求较严格的场合,往往还须选择抢占式调度方式,才能保证紧急作业得到及时处理。

面向系统的准则

(1)系统吞吐量高
用于评价批处理系统性能的另一个重要指标,因而是选择批处理作业调度的重要准则。吞吐量是指在单位时间内系统所完成的作业数,因而它与批处理作业的平均长度具有密切关系。

(2)处理机利用率好
在实际系统中,CPU 的利用率一般在 40%(系统负荷较轻)到 90%之间。在大、中型系统中,在选择调度方式和算法时,应考虑到这一准则。但对于单用户微机或某些实时系统,则此准则就不那么重要了。

(3)各类资源的平衡利用
在大、中型系统中,不仅要使处理机的利用率高,而且还应能有效地利用其它各类资源,如内存、外存和 I/O 设备等。选择适当的调度方式和算法可以保持系统中各类资源都处于忙碌状态。但对于微型机和某些实时系统而言,该准则并不重要。

先来先服务(FCFS)调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用 FCFS 算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

FCFS 算法比较有利于长作业(进程),而不利于短作业(进程)。下表列出了 A、B、C、D 四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间,并计算出各自的周转时间和带权周转时间。

这里写图片描述

CFS 调度算法有利于 CPU 繁忙型的作业,而不利于 I/O 繁忙型的作业(进程)。CPU 繁忙型作业是指该类作业需要大量的 CPU 时间进行计算,而很少请求 I/O。通常的科学计算便属于 CPU 繁忙型作业。I/O 繁忙型作业是指 CPU进行处理时需频繁地请求 I/O。目前的大多数事务处理都属于 I/O 繁忙型作业。

短作业(进程)优先(SJ(P)F)调度算法

短作业(进程)优先调度算法 SJ(P)F,是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。

这里写图片描述

SJF 调度算法能有效地降低作业的平均等待时间,提高系统吞吐量。SJ(P)F 调度算法也存在不容忽视的缺点

  • 该算法对长作业不利,如作业 C 的周转时间由 10 增至 16,其带权周转时间由 2 增至 3.1。更严重的是,如果有一长作业(进程)进入系统的后备队列(就绪队列),由于调度程序总是优先调度那些(即使是后进来的)短作业(进程),将导致长作业(进程)长期不被调度。
  • 该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)会被及时处理。
  • 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意地缩短其作业的估计运行时间,致使该算法不一定能真正做到短作业优先调度。

高优先权优先(FPF)调度算法

为了照顾紧迫型作业,使之在进入系统后便获得优先处理,引入了最高优先权优先(FPF)调度算法。

此算法常被用于批处理系统中,作为作业调度算法,也作为多种操作系统中的进程调度算法,还可用于实时系统中。当把该算法用于作业调度时,系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时,该算法是把处理机分配给就绪队列中优先权最高的进程,这时,又可进一步把该算法分成如下两种。

(1) 非抢占式优先权算法
在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中。

(2) 抢占式优先权调度算法
系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程。这种抢占式的优先权调度算法能更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中,以及对性能要求较高的批处理和分时系统中。

对于最高优先权优先调度算法,其关键在于:它是使用静态优先权,还是用动态优先权,以及如何确定进程的优先权。

(1)静态优先权
静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。一般地,优先权是利用某一范围内的一个整数来表示的。例如,0~7 或 0~255 中的某一整数,又把该整数称为优先数,只是具体用法各异:有的系统用“0”表示最高优先权,当数值愈大时,其优先权愈低;而有的系统恰恰相反。

静态优先权法简单易行,系统开销小,但不够精确,很可能出现优先权低的作业(进程)长期没有被调度的情况。因此,仅在要求不高的系统中才使用静态优先权。

(2)动态优先权
动态优先权是指在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。例如,我们可以规定,在就绪队列中的进程,随其等待时间的增长,其优先权以速率 a 提高。

若所有的进程都具有相同的优先权初值,则显然是最先进入就绪队列的进程将因其动态优先权变得最高而优先获得处理机,此即FCFS 算法。若所有的就绪进程具有各不相同的优先权初值,那么,对于优先权初值低的进程,在等待了足够的时间后,其优先权便可能升为最高,从而可以获得处理机。当采用抢占式优先权调度算法时,如果再规定当前进程的优先权以速率 b 下降,则可防止一个长作业长期地垄断处理机。

确定进程优先权的依据有如下三个方面:

  • (1) 进程类型。通常,系统进程(如接收进程、对换进程、磁盘 I/O 进程)的优先权高于一般用户进程的优先权。
  • (2) 进程对资源的需求。如进程的估计执行时间及内存需要量的多少,对这些要求少的进程应赋予较高的优先权。
  • (3) 用户要求。这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。

高响应比优先调度算法

为每个作业引入前面所述的动态优先权,并使作业的优先级随着等待时间的增加而以速率 a 提高,则长作业在等待一定的时间后,必然有机会分配到处理机。该优先权的变化规律可描述为:
这里写图片描述

由于等待时间与服务时间之和就是系统对该作业的响应时间,故该优先权又相当于响应比 RP。据此,又可表示为:
这里写图片描述

  • (1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业。
  • (2)当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。
  • (3)对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高,从而也可获得处理机。

基于时间片的轮转调度算法

在分时系统中,为保证能及时响应用户的请求,必须采用基于时间片的轮转式进程调度算法。在早期,分时系统中采用的是简单的时间片轮转法;进入 20 世纪 90年代后,广泛采用多级反馈队列调度算法。

在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把 CPU 分配给队首进程,并令其执行一个时间片。时间片的大小从几 ms 到几百 ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之,系统能在给定的时间内响应所有用户的请求。

在时间片轮转算法中,时间片的大小对系统性能有很大的影响,如选择很小的时间片将有利于短作业,因为它能较快地完成,但会频繁地发生中断、进程上下文的切换,从而增加系统的开销;反之,如选择太长的时间片,使得每个进程都能在一个时间片内完成,时间片轮转算法便退化为 FCFS 算法,无法满足交互式用户的需求。一个较为可取的大小是,时间片略大于一次典型的交互所需要的时间。这样可使大多数进程在一个时间片内完成。

多级反馈队列调度算法

多级反馈队列调度算法则不必事先知道各种进程所需的执行时间,而且还可以满足各种类型进程的需要,因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中,调度算法的实施过程如下所述。

(1) 应设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低。在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。

图1. 多级反馈队列调度算法
这里写图片描述

(2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按 FCFS 原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按 FCFS原则等待调度执行;…….如此下去,当一个长作业(进程)从第一队列依次降到第 n 队列后,在第 n 队列中便采取按时间片轮转的方式运行。

(3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;仅当第 1~(i-1)队列均空时,才会调度第 i 队列中的进程运行。如果处理机正在第 i 队列中为某进程服务时,又有新进程进入优先权较高的队列(第 1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第 i 队列的末尾,把处理机分配给新到的高优先权进程。

多级反馈队列调度算法具有较好的性能,能很好地满足各种类型用户的需要。
(1) 终端型作业用户。
(2) 短批处理作业用户。
(3) 长批处理作业用户。

2013-10-02 17:19:04 health747474 阅读数 3107
1.调度的类型
按调度的层次:
长期(长程、作业、高级)调度;
中期(中级、中程)调度;
短期(短程、进程、低级)调度
OS的类型:
批处理调度
分时调度
实时调度
多处理机调度
等等

面向用户的准则
周转时间短
响应时间快
截止时间的保证
优先权准则
面向系统的准则
系统吞吐率高
处理机利用率好
各类资源的平衡利用


面向用户的准则:1、周转时间短

定义
作业周转时间(Turnaroundtime)是指从作业提交给系统开始,到作业完成为止的这段时间间隔。
包括:

1)作业在外存后备队列上等待作业调度的时间

2)进程在就绪队列上等待进程调度的时间(waitingtime)

3)进程在CPU上执行的时间

4)等待I/O操作完成的时间

   其中,第2、3、4项在一个作业的处理过程中,可能发生多次

用户和系统管理员对周转时间有不同的需求
定义:平均周转时间
qqq.jpg 

定义:带权周转时间:作业周转时间T与系统为它提供的实际服务时间Ts之比,即W=T/Ts
定义:平均带权周转时间

qqaaq.jpg 
通常将周转时间作为评价批处理系统的性能、选择作业调度方式和算法的准则
面向用户的准则:2、响应时间快
定义:
响应时间(Responsetime)

是从用户通过键盘提交一个请求开始,直至系统首次产生响应为止的的时间,或者说直到在屏幕上显示出结果为止的一段时间间隔。包括:
从键盘输入的请求信息传送到处理机的时间
处理机对请求信息进行处理的时间
将所形成的响应回送到终端显示器的时间
响应时间常用于评价分时操作系统的性能,是选择分时系统中进程调度算法的重要准则之一
面向用户的准则:3、截止时间的保证
定义:截止时间(Deadline)
是指某任务必须开始执行的最迟时间,或者必须完成的最迟时间。
截止时间是用来评价实时系统性能的重要指标,因而是选择实时调度算法的重要准则

实时系统
软实时系统(softreal-time)  vs  硬实时系统(hard real-time)
非实时系统
面向用户的准则:4、优先权准则
引入优先权

使用优先数表示优先权
优先权高者优先执行

必要时,引入抢占


面向系统的准则:1、系统吞吐率高
定义:吞吐率(Throughput)是指系统在单位时间内完成的作业数
是用于评价批处理系统性能的重要指标,也是用于选择批处理作业调度的重要准则

吞吐率与作业的平均长度有关
大型作业
中、小型作业
吞吐率与作业的调度算法也有关


面向系统的准则:2、处理机利用率好
CPU是稀缺资源
定义:处理器利用率CPUUtilization) =

11aaq.jpg 

进程调度方式和算法对CPU利用率起着十分重要的作业
对于大中型多用户系统,CPU利用率是衡量系统性能的重要指标
40%90%
面向系统的准则:3、各类资源的平衡利用
CPU之外的其他资源,例如内存、外存、I/O设备