操作系统复习4

1、高级调度（High Scheduling）

又称作业调度或长程调度(Long-Term Scheduling),接纳调度(Admission Scheduling)

主要在早期批处理阶段，处理在外存上的作业。

决定外存后备队列中的哪些作业调入内存;

为它们创建进程、分配必要的资源;

将新创建的进程排在就绪队列上，准备执行。

* 管理的方面比较多。

批处理系统：作业进入系统后先驻留外存，故需要有作业调度。

分时系统：为及时响应，作业由终端直接送入内存，故不需作业调度。

实时系统中，通常也不需作业调度。

2、低级调度（Low Level Scheduling）

也称为进程调度、微观调度或短程调度（Short-Term Scheduling）

决定内存就绪队列中的哪个进程获得处理机，进行分配工作。是最基本的一种调度，在三种基本OS中都有

1、先来先服务调度算法FCFS

(First Come First Service)

一种最简单的调度算法，按先后顺序进行调度。既可用于作业调度，也可用于进程调度。

按照作业提交，或进程变为就绪状态的先后次序分派CPU；

新作业只有当当前作业或进程执行完或阻塞才获得CPU运行

被唤醒的作业或进程不立即恢复执行，通常等到当前作业或进程出让CPU。 （所以，默认即是非抢占方式）

不利于短作业（进程）

2. 短作业（进程）优先调度算法SJF/SPF

3. 高优先权优先调度算法HPFHighest Priority First

SJF/SPF的不足：

1. 对短作业有利，但同时造成了对长作业的不利。

    2.由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。

    3.未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）的及时处理。

3. 高优先权优先调度算法HPFHighest Priority First

照顾紧迫性作业，使其获得优先处理而引入调度算法。常用于批处理系统中的作业调度算法，以及多种操作系统中的进程调度算法

分两种方式：

非抢占式优先权算法

抢占式优先权算法 关键点：新作业产生时

高响应比优先调度算法HRRNHighest Response Raito Next

短作业优先算法是一种比较好的算法（相当于根据作业长度设定的静态优先权算法），适用于短作业较多的批处理系统中，其主要不足是长作业的运行得不到保证。

HRRN为每个作业引入动态优先权，使作业的优先级随着等待时间的增加而以速率a提高：

  优先权 =（等待时间+要求服务时间)/要求服务时间

  = 响应时间 / 要求服务时间

同时到达的作业优先权相同。

初始t=0，随着时间增长，如果等待时间 t 相同，执行时间愈短的优先权愈高，利于短作业。

对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长也可获得处理机。长作业有照顾。

当执行时间相同的作业，优先权的高低决定于其等待时间的长短，也就是先来先服务。

基于时间片的轮转调度算法RR (Round Robin)

分时系统新需求：及时响应用户的请求；采用基于时间片的轮转式进程调度算法。

早期分时系统采用的是简单的时间片轮转法，进入90年代后广泛采用多级反馈队列调度算法。

将系统中所有的就绪进程按照FCFS原则，排成一个队列。

每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。

在一个时间片结束时，发生时钟中断。

调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前就绪的队首进程。

多级反馈队列算法FB

(Multiple-level Feed Back Queue)

1）设置多个就绪队列，各队列有不同的优先级,优先级从第一个队列依次降低。

2） 赋予各队列进程执行时间片大小不同, 优先权越高，时间片越短。

3）当一个新进程进入内存，引发的调度过程

准备调度：先将它放入第一个队列的末尾，按FCFS原则排队等待调度。

IF时间片内完成，便可准备撤离系统；

IF时间片内未能完成，调度程序便将该进程转入第二队列的末尾等待再次被调度执行。

当第一队列中的进程都执行完，系统再按FCFS原则调度第二队列。在第二队列的稍放长些的时间片内仍未完成，再依次将它放入第三队列。

依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。