本文共 4662 字,大约阅读时间需要 15 分钟。
当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理
这些任务的顺序,这就是“调度”研究的问题。作业
:一个具体的任务 低级调度
—— 按照某种策略从就绪队列中选取一个进程,将处理机分配给它。进程调度是操作系统中最基本的一种调度
,在一般的操作系统中都必须配置进程调度。进程调度的频率很高
,一般几十毫秒一次。
中级调度
——按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出、调入内存,因此中级调度发生的频率要比高级调度更高。
暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列.
中级调度,就是决定将哪个挂起状态的进程从外存重新调回内存。 注意和高级调度区分,虽然同样是从外存调到内存,但高级调度是调入,中级调度是调回。
高级调度
。按一定的原则从外存的作业后备队列中挑选一个作业调入内存,并创建进程。每个作业只调入一次,调出一次。
作业调入时会建立PCB,调出时才撤销PCB。
暂时调到外存等待的进程状态为挂起状态(挂起态,suspend)挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。
注意“挂起”和“阻塞”的区别,两种状态都是暂时不能获得CPU的服务,但挂起态是将进程映像调到外存去了,而阻塞态下进程映像还在内存中。
进程在操作系统内核程序临界区中不能进行调度与切换√
进程处于临界区时不能进行处理机调度×
内核程序临界区访问的临界资源如果不尽快释放的话,极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。
普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。
非剥夺调度方式
,又称非抢占方式。即,只允许进程主动放弃处理机。在运行过程中即便有更紧迫 的任务到达,当前进程依然会继续使用处理机,直到该进程终止或主动要求进入阻塞态。
剥夺调度方式
,又称抢占方式。当一个进程正在处理机上执行时,如果有一个更重要或更紧迫的进 程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给更重要紧迫的那个进程。
利用率 = 忙碌的时间/总时间
系统吞吐量
:单位时间内完成作业的数量
周转时间
,是指从作业被提交给系统开始,到作业完成为止的这段时间间隔。 它包括四个部分:作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等 待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项 在一个作业的整个处理过程中,可能发生多次。
(作业)周转时间 = 作业完成时间 – 作业提交时间
平均周转时间 = 各作业周转时间之和/作业数
带权周转时间 = 作业周转时间/作业实际运行的时间 = (作业完成时间 – 作业提交时间)/作业实际运行的时间
平均带权周转时间 = 各作业带权周转时间之和/作业数
等待时间
,指进程/作业处于等待处理机状态时间之和,等待时间越长,用户满意度越低
等待时间=周转时间-运行时间
注意
:本例中的进程都是纯计算型的进程,一个进程到达后要么在等待,要么在运行。如果是又有计算、又有I/O操作的进程,其等待时间就是周转时间-运行时间-I/O操作的时间
对于进程来说,等待时间就是指进程建立后等待被服务的时间之和,在等待I/O完成的期间其实进 程也是在被服务的,所以不计入等待时间。
对于作业来说,不仅要考虑建立进程后的等待时间,还要加上作业在外存后备队列中等待的时间。
响应时间,
指从用户提交请求到首次产生响应所用的时间。
算法规则
:按照作业/进程到达的先后顺序进行服务
特点
:非抢占式的算法、不会饥饿、公平 优点
:公平、算法实现简单 缺点
:排在长作业(进程)后面的短作业需要等待很长时 间,带权周转时间很大,对短作业来说用户体验不好。即,FCFS算法对长作业有利,对短作业不利 有利于CPU 繁忙型的作业,而不利于I/O繁忙型的作业。
进程是I/O繁忙型,运行过程中要频繁访问IO端口,即可能会频繁放弃CPU,所以占用CPU的时间不会长,一旦放弃CPU,则必须等待下次调度。若进程是CPU繁忙型,则一旦占有CPU,就可能会运行很长时间.
算法思想
:追求最少的平均等待时间,最少的平均周转时间、最少的平均带权周转时间
算法规则
:最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短) 是否可抢占
:SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法(SRTN) 优点
:“最短的”平均等待时间、平均周转时间 缺点
:不公平。对短作业有利,对长作业不利。可能产生饥饿现象。另外,作业/进程的运行时间是由用户提供的,并不一定真实,不一定能做到真正的短作业优先 是否会导致饥饿
:会。如果源源不断地有短作业/进程到来,可能使长作业/进程长时间得不到服务,产生“饥饿”现象。如果一直得不到服务,则称为“饿死” 注意几个小细节
:
算法规则
:在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务,响应比 = (等待时间+要求服务时间)/ 要求服务时间
是否可抢占
:非抢占式的算法。因此只有当前运行的作业/进程主动放弃 处理机时,才需要调度,才需要计算响应比 优点
:综合考虑了等待时间和运行时间(要求服务时间),对于长作业来说,随着等待时间越来越久,其响应比也会 越来越大,从而避免了长作业饥饿的问题 是否会导致饥饿
:不会 算法规则
:按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完, 则剥夺处理机,将进程重新放到就绪队列队尾重新排队。
特点
:用于进程调度(只有作业放入内存建立了相应的进程后, 才能被分配处理机时间片) 是否可抢占
:若进程未能在时间片内运行完,将被强行剥夺处理机使用权,因此时间片轮转调度算法属于抢占式的算法。由时钟 装置发出时钟中断来通知CPU时间片已到。 优点
:公平;响应快,适用于分时操作系统; 缺点
:由于高频率的进程切换,因此有一定开销;不区分 任务的紧急程度。 是否会导致饥饿
:不会 静态优先级
:创建进程时确定,之后一直不变。
动态优先级
:创建进程时有一个初始值,之后会根据情况动态地调整优先级。 算法规则
:每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程 是否可抢占
:抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可,而抢占式还需在就绪队列变化时,检查是否会发生抢占。 优点
:用优先级区分紧急程度、重要程度,适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。 缺点
:若源源不断地有高优先级进程到来,则可能导致饥饿 是否会导致饥饿
:会 如何合理地设置各类进程的优先级?:
系统进程优先级高于用户进程 前台进程优先级高于后台进程 操作系统更偏好 I/O型进程(或称 I/O繁忙型进程)
如果采用的是动态优先级,什么时候应该调整?
如果某进程在就绪队列中等待了很长时间,则可以适当提升其优先级 如果某进程占用处理机运行了很长时间,则可适当降低其优先级 如果发现一个进程频繁地进行I/O操作,则可适当提升其优先级 随着进程执行时间的增加其优先权随之降低,随着作业等待时间的增加其优先权相应上升。
算法规则
:
是否可抢占
:抢占式的算法。在 k 级队列的进程运行过程中,若更上级的队列 (1~k-1级)中进入了一个新进程,则由于新进程处于优先级更高的 队列中,因此新进程会抢占处理机,原来运行的进程放回 k 级队列 队尾。
优点
:对各类型进程相对公平(FCFS的优点);每个新到达的进程都可以 很快就得到响应(RR的优点);短进程只用较少的时间就可完成 (SPF的优点);不必实现估计进程的运行时间(避免用户作假); 可灵活地调整对各类进程的偏好程度,比如CPU密集型进程、I/O密 集型进程(拓展:可以将因I/O而阻塞的进程重新放回原队列,这样I/O型进程就可以保持较高优先级) 是否会导致饥饿
:会 转载地址:http://rzmzi.baihongyu.com/