死锁问题(DEADLOCK).ppt

3.9 死锁问题(DEADLOCK) 4.6.1 概述 4.6.2 死锁的预防 4.6.3 死锁的检测 4.6.4 死锁的避免 4.6.5 解决死锁问题的综合方法 3.9.1 概述 可重用资源(reusable resource)：每个时刻只有一个进程使用，但不会耗尽，在宏观上各个进程轮流使用。如CPU、主存和辅存、I/O通道、外设、数据结构如文件、数据库和信号量。有可能剥夺资源：由高优进程剥夺低优进程，或OS核心剥夺进程。 2. 死锁发生条件 只有4个条件都满足时，才会出现死锁。 互斥：任一时刻只允许一个进程使用资源 请求和保持：进程在请求其余资源时，不主动释放已经占用的资源 非剥夺：进程已经占用的资源，不会被强制剥夺 环路等待：环路中的每一条边是进程在请求另一进程已经占有的资源。 3.9.2 死锁的预防 预防死锁的两种策略： 预先静态分配法：（针对死锁的第2个条件）预先分配所需全部资源，保证不等待资源； 降低了对资源的利用率，降低进程的并发程度； 有可能无法预先知道所需资源； 有序资源使用法：（针对死锁的第4个条件）把资源分类按顺序排列，保证不形成环路； 限制进程对资源的请求； 资源的排序占用系统开销； 3.9.3 死锁的检测 有向图G的顶点为资源或进程，从资源R到进程P的边表示R已分配给P，从进程P到资源R的边表示P正因请求R而处于等待状态。有向图的循环表示死锁的存在。 资源分配图的简化： 删除不处于等待状态的进程（即没有从该进程出发的边）。 依次删除当前的叶顶点。 不可简化（简化后还存在边）的资源分配图存在死锁，其中的有边进程为死锁进程。 2. 死锁检测的缺点 通过撤消代价最小的进程，以解除死锁。 挂起某些死锁进程，并抢占它的资源，以解除死锁。 3.9.4 死锁的避免 2. 银行家算法 假定顾客分成若干次进行；并在第一次借款时，能说明他的最大借款额。 具体算法： 顾客的借款操作依次顺序进行，直到全部操作完成； 银行家对当前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）； 安全时，贷款；否则，暂不贷款。 4.6.5 解决死锁问题的综合方法 资源归类：将各种资源归入若干个不同的资源类(resource group)中，如：外存交换区空间，进程资源（可分配的设备，如磁带机，文件），主存空间，内部资源（如I/O通道） 资源排序：在不同资源类之间规定次序，对不同资源类中的资源采用线性按序申请的方法 针对性优化：对同一资源类中的资源，采用适当的方法。如： 进程资源－－避免， 外存交换区空间，主存，内部资源－－预防 进程其他方面的举例 4.7.1 UNIX 4.7.2 Windows NT UNIX 系统加载：加载自举程序（磁盘中的引导块）－－加载UNIX核心映象（几百KB到几MB的文件）－－核心初始化（初始化设备驱动程序，建立OS核心的数据结构） Solaris 2.3中核心为/kernel/unix（通过/ufsboot载入）；RedHat Linux 2.0.18中为/boot/vmlinuz 建立0、1号进程：建立0号进程（始终运行于核心态，完成内外存交换）－－建立1号进程init（普通进程，系统中其余进程都是它的直接或间接后代） 运行起动脚本（通常是一些shell程序，用于创建或终止特定的进程）－－为每个终端创建监控进程 Solaris 2.3的起动脚本在/etc/rc*文件和目录，以及/etc/init.d目录；RedHat Linux 2.0.18中为/etc/rc*文件和目录 用户可以对起动脚本进行修改 2. 终端登录序列 init（1号进程）通过fork和exec运行终端监控程序getty getty在Solaris 2.3中为ttymon getty检测到终端开启，对终端进行初始化并读取终端参数，提示输入用户名 输入用户名之后，getty通过exec运行login程序 login在/etc/passwd文件中查找用户名，提示输入口令 输入口令之后，login设置用户的当前工作目录，改变进程的gid和 uid（此前的init, getty和login均具有超级用户的uid和gid，改变时须最后改uid） 通过exec执行用户的shell程序并运行用户的登录shell脚本 init总是等待子进程（即getty, login和shell）终止，在用户退出而其shell终止后，init重新fork和exec运行终端监控程序getty 3. 孤儿进程(orphan) 父进程先终止，则正在运行的子进程变为孤儿进程。系统自动将孤儿进程的父进程指向1号进程。此后，由1号进程通过wiat等待孤儿进程终止，并回收其PCB表项。 若子进程先终止，而父进程不通过wait()系统调用回收其PCB，则子进程变为