《计算机操作系统》（孙雅如版）全套PPT电子课件教案- 第2章 处理机管理.ppt

但是，在实际应用中，一个进程常常需要独占地访问不止一种资源。例如，两个进程各占有一个I/O设备，又申请对方所占的I/O设备，则两个进程都将被阻塞，而且不能解除；又如，两个进程分别对一个数据库中的两个记录加锁以备使用，又试图对对方锁定的记录加锁，也将使得两个进程都被阻塞且不能解除；另外，进程在通信时，互相申请对方尚未产生的消息也会使得两个进程都被阻塞且不能解除。系统中存在各种进程被阻塞而且不能解除的情况，通称为死锁，软、硬件资源的申请都可能导致死锁。 (2) 请求I/O服务时，进程需要暂时放弃CPU，以免出现CPU的“忙等待”； (3) 某些原语操作，如P操作等； (4) 进程完成； (5) 在可剥夺（抢占）调度中，新建进程较执行进程优先级高。 进程调度原因如图2-45所示。 图2-45 进程调度原因 2．调度过程 1) 保护现场 将程序状态字PSW、内存管理寄存器、通用寄存器、程序计数器PC、堆栈指针等CPU当前状态送到PCB表中保存，即将中断现场信息保存。 2) 调度 按一定策略从就绪队列中选择出将要执行的进程的PCB表，从就绪队列中摘下，送执行状态。 3) 现场恢复 将选中进程的PCB表中存放的信息取出，重布现场，使它能够从上次被中断处执行。 2.4.3 进程调度算法 1．先来先服务（FCFS）算法 在先来先服务算法中，进程到达就绪队列时按先后顺序排队。选择进程去执行时，始终选队首进程。进程获得CPU后，直至执行完或发生某等待事件，才释放CPU。 先来先服务算法的实现过程如图2-46所示。 设置信号量： 就绪队列互斥信号量s，初值为1； 就绪队列中进程个数n，初值为0。 图2-46 先来先服务算法实现 2．最短CPU执行期优先调度算法 最短CPU执行期优先调度算法的做法是：每次调度时，从就绪队列中找出下一个CPU执行期最短的进程优先调度。最短CPU执行期优先调度算法的实现过程与先来先服务算法基本一样，只是选择进程的方法不一样。 该调度算法的难点在于预测进程的下一个CPU执行期是很不容易的。 3．优先级调度算法 在优先级调度算法中，每个进程被赋予一个整数，代表优先级。通常数值大的优先级低，数值小的优先级高。优先级调度算法分为静态优先级调度和动态优先级调度两种调度算法。 在静态优先级调度算法中，创建进程时，根据进程的情况或要求赋予进程一个优先级，进程运行过程中优先级不再改变。每次调度时，就绪队列中优先级最高的进程被率先调度，同级的采用先来先服务（FCFS）。 确定优先级的原则可以参考以下几点： 用户要求：用户可以根据作业情况提出自己的优先级要求； 资源利用率：请求I/O服务密集的进程优先级较高； 系统内部要求：系统进程的优先级高于用户进程的优先级。 在动态优先级调度算法中，创建进程时赋予进程一个优先级，进程在运行过程中优先级根据某种规则或者某种算法在发生变化。每次调度时，仍然是从就绪队列中选择优先级最高的进程率先调度，同级的采用先来先服务（FCFS）。 优先数的确定：进程运行前被赋予一个优先数。运行中根据进程等待时间的长短、执行时间的多少、输入与输出信息量的大小等通过计算得到新的优先数。 比如有优先数计算公式如下（数值大的优先级低，数值小的优先级高）： 优先数=优先数? a×等待时间? b×要求运行时间?c×输出行数 若a0，体现先来先服务；b0，体现长进程优先；b0，体现短进程优先；c0，照顾输出多的进程。可以通过对a、b、c取不同的值来体现系统对哪一类进程采取优先政策。 4．时间片轮转法 时间片轮转法是一种简单而又公平的算法，使用最为广泛。 在时间片轮转调度算法中，每个进程按先进先出的原则进入就绪队列，每次调度时，用执行指针指向就绪队列队首进程的PCB表，并将其摘下，重布现场，给以时间片q让其运行。进程运行时间片q后，可能出现以下几种情况： (1) 进程完成：调度另一个进程运行。 (2) 进程未完成：进程的执行被时钟中断，排到就绪队列尾部，调度另一个进程运行。 (3) 因I/O等原因而被阻塞：排在阻塞队列中，调度另一个进程。当被解封后，进程的PCB表从阻塞队列摘下，排到就绪队列尾部。 在时间片轮转调度算法中，进程切换的原因如图2-47所示。 图2-47 进程切换原因 每次调度一个新进程时，都要做切换工作。切换工作所用的时间属于系统管理开销时间。因此，在时间片轮转法中，时间片q长度