操作系统学习PPT 第三章 处理机调度

时间片轮转算法(RR) 反馈排队算法(FB)
3.2.2 处理机调度时机

中断处理完毕，没有嵌套中断，即将返 回目态。
中断 中断
目态（Pi运行） 目态（Pj运行）
管态
返回 返回
…...
中断
管态
返回
Pi=Pj: 未发生进程切换； Pi<>Pj: 发生了进程切换。
3.2.2 处理机调度时机(Cont.)

separate ready queue for each processor,

not really balanced; each processor accesses Q on its own, master/slave assignment.

common ready queue Q for all processors
10
调度∕分派结构图
scheduler
susp wakeup receive
L
ready_q
pcb1
pcb2
pcb3
pcb4
pcb6
L
dispatcher CPU
11
进程调度的两种方式

非抢占方式
一旦处理机分配给某进程后，便让其一直执行， 直至完成或等待时，才把处理机另外分配

抢占方式
允许暂停某个正在执行的进程，将已分配给该进 程的处理机重新分配
Ci 6/5 1 i 1 Ti
6
所以系统是不可调度的。
3.3.1 最早截止期调度

EDF（Earliest Deadline First)

优先选择开始截止期最早的实时任务 可抢先 系统中保持一个实时任务优先级就绪队列，调度程 序选择对首任务分配处理机
开始截止时间 任务执行 任务到达
选择上升进程
– 按处理机调度算法
恢复上升进程的现场
– PCB 寄存器
– 先恢复通用寄存器和地址寄存器,最后恢复
PSW,PC – PSW和PC必须用一条指令恢复
3.3 实时调度(real-time scheduling)

实时任务：

具有明确时间约束的计算任务。 Eg.

某时刻前必须开始处理（开始截止时间） 某时刻前必须处理完毕（完成截止时间）
第三章 处理机调度


3.1 调度级别与多级调度 3.2 处理机调度 3.3 实时调度 3.4 多处理机调度
3.1调度级别与多级调度

一个批处理型作业，从进入系统并进入 在外存的后备队列上开始，直至作业运 行完毕，可能要经历三级调度： 高级调度 中级调度 低级调度
高级调度



又称为作业调度、长程调度、接纳调度 作用：把外存上处于后备队列中的作业 调入内存，并为它们创建进程、分配资 源、排在就绪队列上、准备执行 适用于批处理系统
ቤተ መጻሕፍቲ ባይዱ
（2）新进程进入内存后，首先放入第一队 列的末尾，按FCFS原则排队等待调度。 到该进程执行时，如果能在该时间片内 完成，则撤离系统，若未完成，则转入 第二队列的末尾，如此下去。
（3）仅当第i-1队列均空时，才会调度第i队 列的进程。如果在处理机为第i队列服务时 ，有新进程进入优先权较高的队列，则抢 占处理机，即把正在运行的进程放回到第i 队列的末尾。
响应比，响应比越高，优先权更高
响应比分析 （1）作业等待时间相同，有利于短作业 （2）要求服务时间相同，实现的是FCFS （3）长作业也可获得处理机。 （4）兼顾长短作业，但是增加系统开销。

3.2.1.4 时间片循环轮转算法


分时系统多采用 把就绪队列组成FIFO队列 把CPU分配给队首进程 规定它执行一个时间片 时间片完时排在队列末尾 就绪队列中的所有进程在一定时间内， 均可获得一个时间片

缺点:


专用处理器分配 动态调度
1、在采用等长时间片轮转处理机调度算法 的分时操作系统中，各终端用户所占有 处理机的时间相同，这种说法对么？
不对。处理机是分配给进程的，而不同 终端的用户可能有不同数量的进程，一 个拥有较多数量进程的终端显然比拥有 少量进程的终端获得CPU的时间要多。
2、某系统采用可抢占处理机的静态优先数 调度算法，请问何时会发生抢占处理机 的现象？
Ci N i 1 Ti
m
周期性实时事务

例：
– T1=100, T2=200, T3=500 (ms) – C1=50, C2=30, C3=100 (ms) – C1/T1+C2/T2+C3/T3=0.5+0.15+0.2=0.85<1 – 满足可调度的必要条件
周期性实时事务

单处理机系统中有6个硬实时任务，它 们的周期时间都是50ms，而每次处理时 间为10ms，则：

假定所有任务同时到达，平均等待时间最短。 长作业可能被饿死。（饥饿状态） 没有考虑作业的紧迫程度，不能及时处理。
3.2.1.3高优先权优先调度算法

优先权调度算法的类型 优先权的类型 高响应比优先算法
优先权调度算法的类型 （1）非抢占式（用于批处理系统和某些对实

时性要求不严的系统）
3.2.1进程调度算法


根据系统的资源分配策略所规定的资源 分配算法。 不同的系统和系统目标，通常采用不同 的调度算法。
周转时间：从作业提交给系统开始，到 作业完成为止的时间间隔。 包括： （1）在外存后备队列上等待调度的时间 （2）进程在就绪队列上等待调度的时间 （3）进程在CPU上执行的时间 （4）进程等待I/O操作完成的时间

吞吐量：单位时间内系统所完成的作业 数。 评价批处理系统的重要指标。 与作业的平均长度有关。
3.2.1.1 先到先服务算法(FCFS)


作业调度中每次从后备队列中，算则一 个或多个最先进入该队列的作业调入内 存，为它们分配资源，创建进程，然后 放入就绪队列 进程调度时每次从就绪队列中，选择一 个最先进入该队列的进程分配处理机使 之运行，直到完成或阻塞后，才放弃处 理机。

性能：

终端型作业用户（作业小，可能在第一队列完成） 短批处理作业用户（周转时间短） 长批处理用户
作业调度算法

适合批作业调度的算法



先到先服务算法(FCFS) 优先数调度算法(HPF) 短作业优先调度算法(SJF) 最高响应比优先调度算法(HRN)

不适合批作业调度的算法


（2）抢占式（更好的完成紧迫作业要求，用于
要求比较严格的实时系统）
优先权的类型 （1）静态（创建进程时确定，运行期间不 变；确定依据：系统进程高于用户，要 求资源较少的，用户要求） 简单，开销小，但是不够精确 （2）动态（随进程推进或等待时间增加而 改变）


高响应比优先算法(HRN) 引入动态优先权，并使作业优先级随着时间 的增加而以某种速度提高。 该优先权的变化规律 优先权=（等待时间+服务时间）/服务时间
1
1 3
4
2
3
4
2
1 23
4
3.4 多处理机调度

问题：

M processes (threads) N processors
all processors are identical (homogeneous)

SMP：symmetric multi-processors


目标：load-sharing
非抢占方式引起进程调度的因素


进程执行完毕，或因为发生某事件而不能再继 续执行 执行中的进程因提出I/O请求而暂停执行 在进程通信或同步过程中执行了某种原语操作
抢占原则
（1）优先权选择 （2）短作业优先 （3）时间片原则（分时系统）
选择调度方式和调度算法的准则


面向用户的准则： 周转时间快；响应时间快；截止时间的 保证；优先权准则 面向系统的准则： 系统吞吐量高；处理机利用率好；资源 平衡利用
低级调度


也称为进程调度、短程调度 作业决定就绪队列中的哪个进程应获得 处理机，然后由分派程序执行把处理机 分配给该进程的具体操作 所有OS中都必须配置的
中级调度


又称为中程调度 目的：提高内存利用率和系统吞吐量 作用：使暂时不能运行的进程从内存调 至外存，进入就绪驻外存状态或挂起状 态。把外存上又具备运行条件的进程， 重新调入内存，并修改为就绪状态，挂 在就绪队列上。 又称为对换。
当一个新创建进程或一个被唤醒进程的优 先数比正在运行的进程优先数高时，可 能发生抢占处理机现象。
3、某系统采用最高响应优先比的调度算法， 某个时刻根据用户要求创建一个进程P，进程 P在其存在过程中一次经历了如下过程，分析 其生命过程中状态转化：
（1）进程调度选中了进程P占用处理机运 行，P运行中提出资源申请，要求增加使 用量，没有得到。 （2）进程等待一段时间后得到内存。 （3）进程调度再次选中P占用处理机运行 （4）有紧急进程Q进入，系统停止P的运 行，将处理机分配给进程Q （5）进程Q运行完，进程调度再次选中了 进程P占用处理机运行。 （6）进程P运行完。

必然引起进程切换的中断
– 进程自愿结束, exit() – 进程被强行终止； 非法指令，越界，kill – 进程等待(等待I/O，被抢占，执行原语，时
间片用完，缺页）

可能引起进程切换的中断
– 时钟 – 系统调用
3.2.3 处理机调度过程

保存下降进程的现场（程序执行次序）
– 系统栈PCB