武汉大学 操作系统期末考试复习笔记 - 图文(3)

一个作业可以分成若干顺序处理的加工步骤，每个步骤称为一个 作业步

多道程序的设计目标在于任何时候都有某些进程运行，使CPU利用率最大化。

CPU调度可能发生如下4种情况 从运行状态转到等待状态 从运行状态转到就绪状态 从等待状态转到就绪状态 进程终止

1,4两种情况的调度称为非抢占调度，2，3两种情况的调度称为抢占式调度 进程调度的两种方式：抢占方式，非抢占方式

抢占方式：又称波多方式。抢占原则有，优先权，时间片

分派程序：用来将对CPU的控制交给由短程调度程序选择的进程 分派延迟：分派程序终止一个进程的运行并启动另一个进程运行所花的时间，也成为调度时间

调度准则： CPU利用率

吞吐量（单位时间内运行完的程序数）

周转时间（进程从提交到运行结束的全部时间

等待时间（进程在就绪队列中等待调度的时间总和）

响应时间（从提交请求到系统首次产生响应所用的时间） 带全周转时间（作业周转时间与作业实际运行时间的比）

调度算法:（画图用到gantt图）

FCFS 先来先服务调度，适用于作业调度，进程调度 算法简单易于实现，不适用与短作业和I/O繁忙的作业

SJB 最短作业优先（抢占/非抢占）

适合短作业，对长作业不利，运行时间为估计 抢占SJB调度有时称为最短剩余时间优先调度，若到达新进程的CPU区间短于当前运行进程的剩余时间，则它将抢占CPU。 可能有饥饿

优先级调度（抢占/非抢占）

优先级的类型：静态优先级，动态优先级（确定原则：占用CPU时间，等待时间） 存在的问题：饥饿，低优先级的进程可能永远得不到运行 解决方法：老化，视进程等待时间的延长提高其优先级数

时间片轮转调度（RR）

每个进程得到小单位的CPU时间，称为时间片，通常为10-100毫 秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。

时间片大小：太大：退化为FCFS 太小：调度频繁系统开销大。现代操作系统的时间片一般为10-100ms，上下文切换时间一般少于10us。 确定时间片大小应考虑的因素：

系统对响应时间的要求：响应时间=时间片*进程数 就绪队列中的进程数目：时间片应与就绪进程数成反比 系统的处理能力：考虑响应时间在可承受范围内，系统速度快则时间片可以增长 时间片轮转算法的特点及改进：

虚拟时间片轮转法（针对偏重I/O的进程）： 新进程基于FCFS进入就绪队列，进程用完时间片后也进入就绪队列，进程因I/O阻塞进入I/O队列，I/O完成时进程进入附加队列，附加队列的优先级高于就绪队列，当进程从附加队列被调度时，其运行时间不超过上次发生中断时剩余的时间。

高响应比优先调度算法

响应比＝1＋作业等待时间/估计运行时间

多级队列调度

将就绪队列分为多个独立队列，每个队列有自己的调度算法，根据进程属性，一个进程被永久分配到一个队列

例如分为前台（交互式）RR算法，和后台（批处理）FCFS。前台的优先级高

多级反馈队列调度

进程能在不同的队列间移动。如果进程使用过多的CPU时间，那么它会被移动到更低优先级队列。此外，在较低优先级队列中等待时间过长的进程会被移到更高优先级队列

每个队列有不同优先级，第一队列最高，其余递减，每个队列的时间片大小也各不相同，优先级高的队列时间片短。 当一个新进程进入系统时，首先将它放入第1个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2队列的末尾，再同样地按先来先服务原则等待调度执行。如此下去，最后一个队列中使用时间片轮转调度算法。仅当第1个队列为空时，调度程序才调度第2队列中的进程运行；仅当第1个至第（i－1）个队列均为空时，才会调度第i个队列中的进程运行。当处理机正在为第i个队列中的某进程服务时，若又有新进程进入优先级较高的队列中，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行进程放回第i个队列末尾，重新将处理机分配给新进程。 多级反馈队列调度算法能较好满足各类用户的需求

公平分享调度算法：基于进程组来分配CPU时间，其实现思想是对系统中的每个用户赋予某种权值，根据用户权值大小，按比例分配处理机时间。

进程切换：在操作系统中凡是要进行中断处理和进程调度时，都将涉及到进程上下文的保存的恢复。

中断时：系统保存和恢复的是同一个进程的上下文 进程调度时恢复的是调度程序所选中进程的上下文

既考虑作业等待时间，又考虑作业执行时间的调度算法是 响应比高优先调度

Chapter 6 进程同步

进程同步：系统中各进程之间逻辑上的相互制约关系叫做进程同步

在多道程序系统中，进程之间存在着的不同制约关系可以划分为两类：同步和互斥

同步指进程间具有的一定逻辑关系；互斥是指进程间在使用共享资源方面的约束关系。

临界区问题：每个进程有一个访问共享数据的代码段，称为临界区（critical section）。需保证一个进程在其临界区执行时，不允许其他进程在其临界区执行。 临界资源：一段时间内仅允许一个进程使用的资源称为临界资源。如打印机，共享变量

同类临界区：所有与同一临界资源相关联的临界区

临界区问题的解决应满足：互斥，前进（如果没有进程在其临界区内执行，且有进程需要进入临界区，那么只有不在剩余区执行的进程可以参加选择，以确定下一个进入临界区的进程，且选择不能无限期延长），有限等待（在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区的次数必须是有限的）

访问临界资源应遵循的原则：空闲让进，忙则等待，有限等待，让权等待（当进程不能进入自己的临界区时，应释放处理机）

Peterson算法

enum boolean {false，true}；

boolean flag［2］ ＝{false，false}； int turn； P0：{

do {

flag[0]＝true； turn＝1； while （flag[1] && turn = = 1）；//实现互斥，前进 进程P0的临界区代码CS0 ； flag[0]＝false ； 进程P0的其他代码；} while (true) }

P1：{

do {

flag[1]＝true； turn＝0； while （flag[0] && turn = = 0）； 进程P1的临界区代码CS1 ； flag[1]＝false ； 进程P1的其他代码；} while (true) }

硬件同步：用硬件方法实现互斥的主要思想是保证检查操作与修改操作不被打断 禁止中断方法：当进程执行临界区代码时，禁止中断(很多缺点)