cpu
的竞争,即按一定的调度算法从就绪队列中选择一个进程,把cpu
的使用权交给被选中的进程。如果没有就绪进程,系统会安排一个系统空闲进程或idle
进程进入cpu
运行。N
个进程就绪、等待上cpu
运行 * M
个cpu
, M>=1
* 需要决策:给哪个进程分配哪一个cpu
?cpu
中运行:调度过程(进程的上下文切换)cpu
在运行时会发生很多事件:
I/O
、I/O
中断abort
异常 这些事件发生后-->当前运行的进程暂停执行-->硬件机制响应后-->进入操作系统,处理相应的事件-->结束处理后:某些进程的状态会发生变化,也可能又创建了一些新的进程-->就绪队列改变了-->需要进程调度根据预设的调度算法从就绪队列选择一个进程
进程调度的时机有四个: cpu
相关寄存器。 总的来说,切换进程包括了对原来运行进程各种状态的保存和对新的进程各种状态的恢复。 上下文切换具体步骤: 场景:进程A
下cpu
,进程B
上cpu
。 * 保存进程A
的上下文环境(程序计数器、程序状态字、其他寄存器......) * 用新状态和其他相关信息更新进程A
的PCB
* 把进程A
移至合适的队列(就绪、阻塞......) * 将进程B
的状态设置为运行态 * 从进程B
的PCB
中恢复上下文(程序计数器、程序状态字、其他寄存器......) 上下文切换的开销: * 直接开销:内核完成切换所用的cpu
时间 * 保存和恢复寄存器.... * 切换地址空间(相关指令开销较大) * 间接开销 * 高速缓存(Cache
)、缓冲区缓存(Buffer Cache
)和TLB
(Translation Lookup Buffer
)失效。什么情况下需要仔细斟酌调度算法?
调度算法的衡量指标
cpu
利用率:cpu
做有效工作的时间比例二、设计调度算法前的要点
cpu
调度有关的信息I/O
密集型与cpu
密集型进程优先级和优先数是不同的,优先级表现了进程的重要性和紧迫性,优先数实际上是一个数值,反映了某个优先级。
说明:创建多个进程后按照不同的优先级进行排列,cpu
调度优先级较高的进程进行执行。
说明:所有进程创建之后都进入到第一级就绪队列,随着进程的运行,可能会降低某些进程的优先级,如某些进程的时间片用完了,那么就会将其降级。
cpu
,提供给具有更高优先级的进程使用。I/O
密集型或I/O
型(I/O-bound
) 频繁的进程I/O
,通常会花费很多时间等待I/O
操作的完成。cpu
密集型或cpu
型或计算密集型(cpu-bound
) 需要大量的cpu
时间进行计算一个时间段,分配给调度上cpu
的进程,确定了允许该进程运行的时间长度。那么如何选择时间片?有一下需要考虑的因素:
cpu
能力引起低级调度的原因 有四种情况都会发生CPU调度 当一个进程从运行态切换成等待态时 当一个进程从运行态切换成就绪态时 当一个进程从等待态切换成就绪态时 当一个进程中止时。也就是说当一个进程由运行状态变为非运行状态 或者一个进程变为就绪状态时都会引起低级调度 .
FCFS-First Come First Serve
) (作业调度,进程调度)SJF-Shortest Job First
) (作业调度,进程调度)FRTN-Shortest Remaining Time Next
)HRRN-Highest Response Ratio Next
)
在批处理系统中调度算法主要考虑的是吞吐量、周转时间、cpu
、公平/平衡。cpu
那能否改变调度顺序来提供效率呢?
优缺点:
SJF
调度算法可以得到最短的平均周转时间R
之后,总是选择R
最高的进程执行。RR-Round Robin
)HPF-Highest Priority First
)Multiple feedback queue
)Shortest Process Next
) ## 4.1 时间片轮转调度算法
说明:首先当前进程是B
,当B
的时间片用完后就被放在队列的尾部,此时当前进程就是F
。 * 目标 为短任务改善平均响应时间 * 解决问题的思路 * 周期性的切换 * 每个进程分配一个时间片 * 时钟中断-->轮转 如何选择合适的时间片? * 太长:大于典型的交互时间
就是进程所需时间小于时间片,那么就会剩余一段时间。如果大部分进程都像这样,那么此算法就退化成了先来先服务算法。同时会延长段进程的响应时间。 * 太短:小于典型的交互时间
这种情况下进程的响应时间也会延长。同时不断的切换也会浪费时间。 优缺点: * 公平 * 有利于交互式计算,响应时间快 * 由于进程切换,时间片轮转算法要花费较高的开销 * 对不同大小的进程是有利的,但是对相同大小的进程呢?例子如下:
小结:此算法往往不区分是I/O
密集型还是cpu
密集型,所以会给I/O```密集型进程带来一下不公平,下面看虚拟轮转算法。 虚拟轮转法:
说明:按照之前的时间片算法,对于I/O
型进程时是不公平的,因为它总是用不完时间片,但是调度之后都要重新进入就绪队列进行排队,这样显然不公平。于是就设计了上图的调度算法。为I/O
型进程专门设计了一个辅助队列,当一个I/O
进程运行完之后不进入就绪队列,而是进入辅助队列,同时cpu
也优先去调度辅助队列中的进程,知道辅助队列中为空,才去就绪队列中选择进程。 ## 4.2 最高优先级调度算法 * 选择优先级最高的进程投入运行 * 通常:系统进程优先级高于用户进程;前台进程优先级高于后台进程;操作系统更偏好I/O
型进程。 * 优先级可以是静态的,也可以动态调整,优先数可以决定优先级 * 就绪队列可以按照优先级组织 * 实现简单,但是不公平 优先级反转问题: 主要出现在基于优先级的抢占式调度算法中。表现为,一个低优先级进程持有一个高优先级进程所需要的资源,使得高优先级进程等待低优先级进程运行。例如:
UNIX
的一个分支BSD5.3
版所采用的调度算法cpu
,进入下一级就绪队列cpu
的进程进入相应的等待队列,一旦等待的事件发生,该进程回到原来一级就绪队列以上所说都是属于非抢占式的,如果允许抢占,则当有一个优先级更高的进程就绪时,可以抢占cpu
,被抢占的进程回到原来一级就绪队列的末尾。
说明:当一个进程总是用完时间片,那么其就会一直降级,这样我们就可以知道这是一个cpu
型进程,于是就区分出了cpu
型和I/O
型进程,同时可以知道这种调度算法偏好I/O
型进程。当然也做了一些弥补,即优先级低的进程时间片较大。
各种调度算法的比较
cpu
上执行cpu之
间迁移时的开销
1、高速缓存失效、TLB
失效
2、尽可能使进程总是在同一个cpu
上执行 cpu
上,假如进程上次在cpu1
上执行,本次被调度到cpu2
,则会增加高速缓存失效、TLB
失效;如果每个进程尽量调度到指定的cpu
上,各种失效就会减少。基本思想:
cpu
系统中允许多个线程并行运行引发线程调度的条件: 之前我们提到了四个条件:
这里还有两个条件:
Affinity
)处理机集合(比如允许一个线程在多个处理机上执行,但是如果其他的处理机空闲,则此线程也不能在其上进行执行)Windows线程优先级:
线程的时间配额:
Windows
将重新给该线程分配一个新的时间配额,让它继续执行。实质就是不会一定让一个线程一直运行直到其结束,首先给其分配一个时间配额,运行完之后再次检查,如果没有运行完则再次分配时间配额,让其运行,这个过程不是连续的,是有间断的。时间配额的一种特殊作用:
CPU
型)CPU
时间了CPU
时间多一些而已。调度策略:
cpu
会选择新的线程进行执行。cpu
后将运行剩余的时间配额
这里的实时优先级和可变优先级有什么区别????难道实时优先级就是按创建顺序产生的优先级,而可变优先级就是优先级可变的?A
的时间配额用完 A
的优先级没有降低
1、如果队列中有其他就绪线程,选择下一个线程执行,A
回到原来的就绪队列末尾
2、如果队列中没有其他就绪线程,系统会给A重新分配时间配额,让其继续执行A
的优先级降低,此时Windows
将选择一个更高优先级的线程执行线程优先级提升与时间配额调整: 为什么一个线程的时间配额用完后其优先级会被降低,这是因为之前此线程的优先级被提升过。
Windows
的调度策略 Windows
会提升线程的当前优先级:
1、I/O
操作完成
2、信号量或事件等待结束
3、前台进程中的线程完成了一个等待操作
4、由于窗口活动而唤醒窗口线程
5、线程处于就绪态超过了一定的时间还没有运行(即“饥饿”现象)
在Windows
中线程优先级的提升只是针对可变优先级范围内(1-15)的线程优先级几个线程优先级提升的例子:
1、I/O
操作完成后的线程优先级提升
I/O
操作后,Windows
将临时提升等待该操作线程的优先级,保证该线程能更快上CPU
运行进行数据处理Wdm.h
”或“Ntddk.h
”中I/O
请求的响应时间要求是一致的,响应时间要求越高,优先级提升幅度越大I/O
请求时通过内核函数IoCompleteRequest
来指定优先级提升的幅度I/O
操作完成唤醒等待线程时会将该线程的时间配额减一</div>