计算机操作系统第3章new.ppt

作业的概念一般用于早期批处理系统和现在的大型机、巨型机系统中。对于微机和工作站系统，一般不太使用作业的概念。 （2）进程调度中的三个基本机制 排队器 分派器 上下文切换机制 1) 非抢占方式(Non-preemptive Mode) 在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：① 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行； ② 执行中的进程因提出I/O请求而暂停执行；③ 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。 非抢占方式调度方式的优点是： 实现简单、系统开销小，适用于大多数的批处理系统环境。 但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。 作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为: FCFS算法对哪种作业有利？ 仅在要求不高的系统中才使用静态优先权 FCFS SJF 4、多级反馈队列调度算法是目前被公认的一种较好的进程调度算法 抢占式调度并动态分配优先权。 实时处理任务要求计算机在用户允许的时限范围内给出计算机响应信号。实时处理任务可分为 硬实时任务(hardreal—timetask) 软实时任务(softreal—timetask)。  硬实时任务要求计算 机系统必须在用户给定的时限内处理完毕 软实时任务允许计算机系统在用户给定的时限左右 处理完毕。 假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件： 系统才是可调度的。 解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统， 但须增强其处理能力， 以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为： 2. 抢占式调度算法 （1）基于时钟中断的抢占式优先权调度算法。 (2) 立即抢占(Immediate Preemption)的优先权调度算法。 在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。 1) 静态分配(Static Assignment)方式 一个进程被固定地分配到一个处理器上去执行。 优点： 进程调度开销小 缺点： 各处理器忙闲不均 2) 动态分配(Dynamic Assignment)方式 优点： 成组调度的性能优于自调度，并被应用到许多种处理机OS中。 所谓安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 (4) 需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Need［i,j］=Max［i,j］-Allocation［i,j］ (1) 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 (4) 如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的，否则称该图是不可完全简化的。 死锁定理 S为死