4、处理机调度

• 2.短作业（进程）优先调度算法(Shortest Job/Process First，SJF/SPF） –(1) 算法描述 • 对预计执行时间短的作业（进程）优 先分派处理机。通常后来的短作业不 抢先正在执行的作业。 • 是对FCFS算法的改进，其目标是减少 平均周转时间。
• (2) SJF的特点 –优点： • 比FCFS改善平均周转时间和平均带权周转 时间，缩短作业的等待时间； • 提高系统的吞吐量； – 缺点： • 对长作业非常不利，可能长时间得不到执 行； • 未能依据作业的紧迫程度来划分执行的优 先级； • 难以准确估计作业（进程）的执行时间， 从而影响调度性能。
进程
P1 P2 P3 P4
P1 0 2 P2 4
到达时间
0.0 2.0 4.0 5.0
执行时间
7 4 1 4
• 最短剩余时间优先（抢先式SJF）
P3 5 P2 7 P4 11 P1 16
• 平均等待时间 = (9 + 1 + 0 +2)/4 = 3 • 平均周转时间＝（16＋5＋1＋6）/4=7
3.2.2 优先权调度算法(Priority Scheduling)
10.00 10.10 2 1
10.25 0.25
作 业 1 2 3
提交 运行 开始 完成时 周转 带权周转 时间 时间 时间 间 时间 时间 10.00 10.10 2 1 10 12 12.00 13.00 13.25 2 2.9 3 2/2 2.9/1 3/0.25
10.25 0.25 13
截止时间
• 实时系统的重要指标。 • 开始截止时间和完成截止时间 • 某任务必须开始执行的最迟时间，或必 须完成的最迟时间。
优先权原则

进程管理
进程管理
【解答】 ①系统资源总数向量为（9, 3, 6） 各进程对资源需求矩阵为： ②采用银行家算法进行计算分析可知：
进程管理
2、调度算法
现有如下作业序列：作业1（提交时间8.00，运行时间 1.00）；作业2（提交时间8.30，运行时间3.00）；作 业3（提交时间9.00，运行时间0.10）；作业4（提交 时间9.30，运行时间0.50）（单位：小时，以十进制 计）。 试用先来先服务和短作业优先调度算法处 理该作业序列，问哪种作业调度算法性能更好（要求给 出计算的数据和必要的步骤）。(华中科技大学2001年 试题)
处理机调度作业
进程管理
1、银行家算法
某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3 和P4这4个进程对资源的占用和需求情况见表2.2，此刻 系统的可用资源向量为（2, 1, 2），问题：(中科院软 件所1999年试题) ①将系统中各种资源总数和此刻各进程对各资源的需求 数目用向量或矩阵表示出来；②如果此时P1和P2均发出 资源请求向量Request(1, 0, 1)，为了保持系统安全 性，应该如何分配资源给这两个进程？说明你所采用策 略的原因；③如果②中两个请求立刻得到满足后，系统 此刻是否处于死锁0
40
50
60
70
80
90
J1: IO2(30ms), CPU(10ms), IO1(30ms), CPU(10ms). J2: IO1(20ms), CPU(20ms), IO2(40ms). J3: CPU(30ms), IO1(20ms).
进程管理
【解答】 （1） 由上图可知：J1从开始到完成的时间是0～ 80msJ2从开始到完成的时间是0～90msJ3从开始到 完成的时间是0～90ms （2） 三个作业全部完成时CPU的利用率是：

等待事件
4.1.2 作业与进程
作业是用户向计算机提交任务的任务实体 进程是计算机为了完成用户任务实体而设置
的执行实体，是系统分配资源的基本单位
第四章 处第理9机页调度
4.2 作业调度
作业调度主要是完成作业从后备状态到执行状态的转 变，以及从执行状态到完成状态的转变
第四章 处第理1机0页调度
第四章 处第理1机9页调度
4.3.2 进程调度的时机
(1) 正在执行的进程执行完毕。 (2) 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。 (3) 执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用
了V原语操作激活了等待资源的进程队列。 (4) 执行中进程提出I／O请求后被阻塞。 (5) 在分时系统中时间片已经用完。 (6) 在执行完系统调用
第四章 处第理1机2页调度
图4.3 作业调度中状态的转换过程 第四章 处第理1机3页调度
4.2.2 作业调度目标与性能衡量
作业调度的功能最主要的是从后备作业队列中选取一批作 业进入执行状态。
调度目标主要是以下4点: (1) 对所有作业应该是公平合理的； (2) 应使设备有高的利用率； (3) 每天执行尽可能多的作业； (4) 有较快的响应时间。
主要功能是按照一定的策略选择一个处于就绪状态的进程， 使其获得处理机执行。根据不同的系统设计目的，有各种各样 的选择策略，例如系统开销较少的静态优先数调度法，适合于 分时系统的轮转法和多级反馈轮转法等。这些选择策略决定了 调度算法的性能 (3) 进行进程上下文切换
一个进程的上下文（context）包括进程的状态、有关变量 和数据结构的值、硬件寄存器的值和PCB以及有关程序等
高级调度"。从用户工作流程的角度，一次提交的若干个流程， 其中每个程序按照进程调度。时间上通常是分钟、小时或天 (2) 交换调度：中级调度，从存储器资源的角度。将进程的部分 或全部换出到外存上，将当前所需部分换入到内存。指令和数据 必须在内存里才能被CPU直接访问。 (3)进程或线程调度：低级调度（微观调度），又称为"微观调度 "、"低级调度"。从CPU资源的角度，执行的单位。时间上通常 是毫秒。因为执行频繁，要求在实现时达到高效率

1、处理机管理有哪些主要功能？它们的主要任务是什么？答：处理机管理的主要功能是：进程管理、进程同步、进程通信和处理机调度；进程管理：为作业创建进程，撤销已结束进程，控制进程在运行过程中的状态转换。

进程同步：为多个进程（含线程）的运行进行协调。

通信：用来实现在相互合作的进程之间的信息交换。

处理机调度：（1）作业调度。

从后备队里按照一定的算法，选出若干个作业，为他们分配运行所需的资源（首选是分配内存）。

（2）进程调度：从进程的就绪队列中，按照一定算法选出一个进程，把处理机分配给它，并设置运行现场，使进程投入执行。

2、前趋图是一个有向无循环图，记为DAG，用于描述进程之间执行的前后关系。

3、试说明PCB 的作用，为什么说PCB 是进程存在的惟一标志？PCB 是进程实体的一部分，是操作系统中最重要的记录型数据结构。

作用是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，成为能与其它进程并发执行的进程。

OS是根据PCB对并发执行的进程进行控制和管理4、试说明进程在三个基本状态之间转换的典型原因1）就绪状态→执行状态：进程分配到CPU资源2）执行状态→就绪状态：时间片用完3）执行状态→阻塞状态：I/O请求4）阻塞状态→就绪状态：I/O完5、为什么要在OS 中引入线程？在操作系统中引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性，提高CPU的利用率。

进程是分配资源的基本单位,而线程则是系统调度的基本单位。

6、试说明线程具有哪些属性1)轻型实体2）独立调度和分派的基本单位3）可并发执行4）共享进程资7、试从调度性，并发性，拥有资源及系统开销方面对进程和线程进行比较1）调度性。

线程在OS 中作为调度和分派的基本单位，进程只作为资源拥有的基本单位。

2）并发性。

进程可以并发执行，一个进程的多个线程也可并发执行。

3）拥有资源。

进程始终是拥有资源的基本单位，线程只拥有运行时必不可少的资源，本身基本不拥有系统资源，但可以访问隶属进程的资源。