操作系统原理及应用（Linux） 王红 第3章 处理机调度与死锁新.ppt

第3章 处理机调度与死锁 教学内容 3.1 分级调度 3.2 作业调度 3.3 进程调度 3.4 调度算法 3.5 LINUX系统的调度算法 3.6 死锁问题 3.7 死锁的预防与避免 3.8 利用银行家算法避免死锁 3.9 死锁的检测与解除 3.1 分级调度 3.1.1 调度的层次 2．对换 3．进程调度 3.1.2 作业与进程的关系 作业是用户向计算机提交任务的任务实体。一个作业是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。一个作业总是由一个或多个进程组成的。作业分解为进程的过程是：系统首先为一个作业创建一个根进程。然后，在执行作业控制语句时，根据任务要求，系统或根进程为其创建相应的子进程。最后，进行进程调度，为各子进程分配资源和调度各子进程执行，以完成作业要求的工作。 3.2 作业调度 3.2.1 作业调度的功能 3.2.2 调度算法的评价及准则 1．面向用户的准则 2．面向系统的准则 （２）响应时间快 2．面向系统的准则 3.3 进程调度 3.3.2 进程调度的时机 3.3.3 进程上下文的切换 3.3.4 Linux系统中进程调度发生的时机 3.4 调度算法 3．高响应比优先调度算法 3.4.2 多道批处理系统的调度算法 3.4.3 优先级调度算法 解： （1）各作业进入时间和结束时间如下： 3.4.4 轮转调度算法 2．多级队列调度算法 3．多级反馈队列调度算法 4．多级反馈队列调度算法的几点说明 3.5 Linux系统的调度算法 3.5.1 Linux系统的进程调度策略 3.5.2 Linux系统的优先级调度策略 3.5.3 实时进程的调度策略 3.6 死锁问题 3.6.2 产生死锁的原因及必要条件 不可剥夺性资源是指：进程一旦占有该资源，就不可抢占，不管其它进程的优先权是否高于当前进程，只能在该进程用完后自行释放，这种资源如打印机、磁带机等。大多数情况下，我们所讲引起的死锁的资源竞争，是指对于不可剥夺性资源的竞争。另外一种因资源竞争而死锁的资源，是一些临时性资源，也称为消耗性资源。这种资源被另一进程使用很短时间而以后便无用的资源，如消息等。 （2）进程推进顺序不当 2．死锁产生的必要条件 （1）互斥条件 对于一个排它性资源，某一时刻最多只能由一个进程占有，不能同时分配给两个以上的进程。必须要在占有该资源的进程放弃该资源后，其它进程才能占有该资源。如打印机是临界资源，各进程必须互斥地使用。 （2）占有且申请条件 （4）环路条件 3.6.3 解决死锁问题的基本方法 为保证系统的正常运行，应事先采取措施，预防或避免死锁的发生。在系统已出现死锁后，要及时检测到死锁并解除死锁。目前用于处理死锁问题的方法有以下几种： 1．死锁的预防 2．死锁的避免 3．死锁的检测 4．死锁的解除 3．死锁的检测 4．死锁的解除 3.7 死锁的预防与避免 3.7.1 死锁的预防 １．摒弃占有且申请条件 （2）释放已占资源策略 ２．摒弃不可抢占条件 ３．摒弃环路条件 3.7.2 死锁的避免 1．安全状态 2．由安全状态向不安全状态的转化 3．银行家算法 3.8 利用银行家算法避免死锁 3.8.2 银行家算法的实现 2．银行家算法的描述 3．安全性算法 安全算法的步骤： 3.8.3 银行家算法的应用 3.9 死锁的检测与解除 3.9.1 死锁检测的时机 3.9.2 死锁的检测 2．资源分配图的简化 3．死锁定理 某系统状态S为死锁状态的充分必要条件是：当且仅当S状态的资源分配图是不可完全简化的。即：如果资源分配图中不存在环路，则系统不存在死锁；如果资源分配图中存在环路，则系统中可能产生死锁，如果不可再简化，则系统产生死锁。 4．死锁检测中的算法 3.9.3 死锁的解除 1．终止进程 当死锁解除后，应当在适当的时机让被终止的进程重新执行。当重启运行进程时应让进程从头开始执行，也有的系统在进程执行的过程中设置校验点，当重新启动时让进程回退到发生死锁之前的那个校验点开始执行。设置校验点的办法对执行时间长的进程来说是有必要的，但系统的开销较大。 2．抢占资源 （3）进程的“饿死” 如果经常从同一个进程中抢占资源，则该进程总是处于资源不足的状态而不能完成，该进程就会被“饿死”。因此，一般情况下总是从已执行时间短的进程中抢夺资源，以免该现象的发生。 此外，还有进程回退策略，即让参与死锁的进程回退到没有发生死锁前的某一点处，并由此点处继续执行，以求再次执行时不再发生死锁。虽然这是个较理想的办法，但是操作起来系统开销极大，要有堆栈这样的机构记录进程的每一步变化，以便