死锁问题(DEADLOCK)课件

1、 operating IT systemDLNUDLNU死锁问题(DEADLOCK)3.9 死锁问题死锁问题(DEADLOCK)4.6.1 概述概述4.6.2 死锁的预防死锁的预防4.6.3 死锁的检测死锁的检测4.6.4 死锁的避免死锁的避免4.6.5 解决死锁问题的综合方解决死锁问题的综合方法法返回 operating IT systemDLNUDLNU死锁问题(DEADLOCK)3.9.1 概述概述可重用资源可重用资源(reusable resource)：每个时刻只有一个进程使用，每个时刻只有一个进程使用，但不会耗尽，在宏观上各个进程轮流使用。如但不会耗尽，在宏观上各个进程轮流使用。如

2、CPU、主存和辅存、主存和辅存、I/O通道、外设、数据结构如文件、数据库和信号量。有可能剥夺资通道、外设、数据结构如文件、数据库和信号量。有可能剥夺资源：由高优进程剥夺低优进程，或源：由高优进程剥夺低优进程，或OS核心剥夺进程。核心剥夺进程。死锁是指系统中多个进程无限制地等待死锁是指系统中多个进程无限制地等待.1. 死锁发生原因死锁发生原因对互斥资源的共享，并发执行的顺序不当对互斥资源的共享，并发执行的顺序不当 operating IT systemDLNUDLNU死锁问题(DEADLOCK). Request(B); Request(A); Release(A); Release(B);P2

3、. Request(A); Request(B); Release(B); Release(A);P1可重用资源死锁死锁发生：双方都拥有部分资源，同时在请求对方已占有的资源。如次序：P1 P2 P1 P2 operating IT systemDLNUDLNU死锁问题(DEADLOCK)2. 死锁发生条件只有只有4个条件都满足时，才会出现死锁。个条件都满足时，才会出现死锁。l互斥：互斥：任一时刻只允许一个进程使用资源任一时刻只允许一个进程使用资源l请求和保持：请求和保持：进程在请求其余资源时，不主动释放已进程在请求其余资源时，不主动释放已经占用的资源经占用的资源l非剥夺：非剥夺：进程已经占用的

4、资源，不会被强制剥夺进程已经占用的资源，不会被强制剥夺l环路等待：环路等待：环路中的每一条边是进程在请求另一进程环路中的每一条边是进程在请求另一进程已经占有的资源。已经占有的资源。 operating IT systemDLNUDLNU死锁问题(DEADLOCK)3.9.2 死锁的预防死锁的预防预防死锁的两种策略：预防死锁的两种策略：l预先静态分配法：（针对死锁的第预先静态分配法：（针对死锁的第2个条件）预先分配所需全部个条件）预先分配所需全部资源，保证不等待资源；资源，保证不等待资源；降低了对资源的利用率，降低进程的并发程度；降低了对资源的利用率，降低进程的并发程度；有可能无法预先知道所需资

5、源；有可能无法预先知道所需资源；l有序资源使用法：（针对死锁的第有序资源使用法：（针对死锁的第4个条件）把资源分类按顺序个条件）把资源分类按顺序排列，保证不形成环路；排列，保证不形成环路；限制进程对资源的请求；限制进程对资源的请求；资源的排序占用系统开销；资源的排序占用系统开销；预防是采用某种策略，限制并发进程对资源的请求，使系统在任预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。何时刻都不满足死锁的必要条件。 operating IT systemDLNUDLNU死锁问题(DEADLOCK)3.9.3 死锁的检测死锁的检测有向图G的顶点为资源或进程，从资

6、源R到进程P的边表示R已分配给P，从进程P到资源R的边表示P正因请求R而处于等待状态。有向图的循环表示死锁的存在。资源分配图的简化：l删除不处于等待状态的进程（即没有从该进程出发的边）。l依次删除当前的叶顶点。不可简化（简化后还存在边）的资源分配图存在死锁，其中的有边进程为死锁进程。保存资源的请求和分配信息，利用某种算法对这些信息加以检查，保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。死锁检测算法主要是检查是否有循环等待。以判断是否存在死锁。死锁检测算法主要是检查是否有循环等待。1. 资源分配图(resource allocation graph)算法 oper

7、ating IT systemDLNUDLNU死锁问题(DEADLOCK)2. 死锁检测的缺点死锁检测的缺点通过撤消代价最小的进程，以解除死锁。通过撤消代价最小的进程，以解除死锁。挂起某些死锁进程，并抢占它的资源，以解除死锁。挂起某些死锁进程，并抢占它的资源，以解除死锁。在解除死锁时，常常造成进程终止或重新起动在解除死锁时，常常造成进程终止或重新起动（重新申请资源（重新申请资源）3. 死锁的恢复死锁的恢复撤消进程的原则：撤消进程的原则：进程优先级；进程优先级；系统会计过程给出的运行代价；系统会计过程给出的运行代价； operating IT systemDLNUDLNU死锁问题(DEADLOC

8、K)3.9.4 死锁的避免死锁的避免在分配资源时判断是否会出现死锁，在分配资源时判断是否会出现死锁，如不会死锁，则分配资源。如不会死锁，则分配资源。1. 银行家算法（银行家算法（Dijkstra, 1965）问题）问题一个银行家把他的固定资金（一个银行家把他的固定资金（capital）贷）贷给若干顾客。只要不出现一个顾客借走所给若干顾客。只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全有资金后还不够，银行家的资金应是安全的。银行家需一个算法保证借出去的资金的。银行家需一个算法保证借出去的资金在有限时间内可收回。在有限时间内可收回。 operating IT systemDLNUDL

9、NU死锁问题(DEADLOCK)2. 银行家算法银行家算法假定顾客分成若干次进行；并在第一次借款时，能假定顾客分成若干次进行；并在第一次借款时，能说明他的最大借款额。说明他的最大借款额。具体算法：具体算法：l顾客的借款操作依次顺序进行，直到全部操作完顾客的借款操作依次顺序进行，直到全部操作完成；成；l银行家对当前顾客的借款操作进行判断，以确定银行家对当前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）；其安全性（能否支持顾客借款，直到全部归还）；l安全时，贷款；否则，暂不贷款。安全时，贷款；否则，暂不贷款。3. 银行家算法的特点银行家算法的特点允许互斥、部分分配和不可抢

10、占，可提高资源利用率；允许互斥、部分分配和不可抢占，可提高资源利用率；要求事先说明最大资源要求，在现实中很困难；要求事先说明最大资源要求，在现实中很困难； operating IT systemDLNUDLNU死锁问题(DEADLOCK)4.6.5 解决死锁问题的综合方法解决死锁问题的综合方法资源归类：将各种资源归入若干个不同的资源类资源归类：将各种资源归入若干个不同的资源类(resource group)中，如：外存交换区空间，中，如：外存交换区空间，进程资源（可分配的设备，如磁带机，文件），主进程资源（可分配的设备，如磁带机，文件），主存空间，内部资源（如存空间，内部资源（如I/O通道）通

11、道）资源排序：在不同资源类之间规定次序，对不同资资源排序：在不同资源类之间规定次序，对不同资源类中的资源采用线性按序申请的方法源类中的资源采用线性按序申请的方法针对性优化：对同一资源类中的资源，采用适当的针对性优化：对同一资源类中的资源，采用适当的方法。如：方法。如：l进程资源避免，进程资源避免，l外存交换区空间，主存，内部资源预防外存交换区空间，主存，内部资源预防 operating IT systemDLNUDLNU死锁问题(DEADLOCK) 进程其他方面的举例进程其他方面的举例4.7.1 UNIX4.7.2 Windows NT返回 operating IT systemDLNUDLN

12、U死锁问题(DEADLOCK) UNIX系统加载：加载自举程序（磁盘中的引导块）加载系统加载：加载自举程序（磁盘中的引导块）加载UNIX核心映象核心映象（几百（几百KB到几到几MB的文件）核心初始化（初始化设备驱动程序，建的文件）核心初始化（初始化设备驱动程序，建立立OS核心的数据结构）核心的数据结构）lSolaris 2.3中核心为中核心为/kernel/unix（通过（通过/ufsboot载入）；载入）；RedHat Linux 2.0.18中为中为/boot/vmlinuz建立建立0、1号进程：建立号进程：建立0号进程（始终运行于核心态，完成内外存交换）号进程（始终运行于核心态，完成内外

13、存交换）建立建立1号进程号进程init（普通进程，系统中其余进程都是它的直接或间接（普通进程，系统中其余进程都是它的直接或间接后代）后代）运行起动脚本（通常是一些运行起动脚本（通常是一些shell程序，用于创建或终止特定的进程）程序，用于创建或终止特定的进程）为每个终端创建监控进程为每个终端创建监控进程lSolaris 2.3的起动脚本在的起动脚本在/etc/rc*文件和目录，以及文件和目录，以及/etc/init.d目录；目录；RedHat Linux 2.0.18中为中为/etc/rc*文件文件和目录和目录l用户可以对起动脚本进行修改用户可以对起动脚本进行修改1. 系统引导系统引导 ope

14、rating IT systemDLNUDLNU死锁问题(DEADLOCK)2. 终端登录序列init（1号进程）通过号进程）通过fork和和exec运行终端监控程序运行终端监控程序gettylgetty在在Solaris 2.3中为中为ttymongetty检测到终端开启，对终端进行初始化并读取终端参检测到终端开启，对终端进行初始化并读取终端参数，提示输入用户名数，提示输入用户名l输入用户名之后，输入用户名之后，getty通过通过exec运行运行login程序程序login在在/etc/passwd文件中查找用户名，提示输入文件中查找用户名，提示输入口令口令l输入口令之后，输入口令之后，lo

15、gin设置用户的当前工作目录，改变进程的设置用户的当前工作目录，改变进程的gid和和 uid（此前的（此前的init, getty和和login均具有超级用户的均具有超级用户的uid和和gid，改变时须最后改改变时须最后改uid）l通过通过exec执行用户的执行用户的shell程序并运行用户的登录程序并运行用户的登录shell脚本脚本init总是等待子进程（即总是等待子进程（即getty, login和和shell）终止，）终止，在用户退出而其在用户退出而其shell终止后，终止后，init重新重新fork和和exec运运行终端监控程序行终端监控程序getty operating IT sys

16、temDLNUDLNU死锁问题(DEADLOCK)3. 孤儿进程孤儿进程(orphan)父进程先终止，则正在运行的子进程变为孤儿进程。父进程先终止，则正在运行的子进程变为孤儿进程。系统自动将孤儿进程的父进程指向系统自动将孤儿进程的父进程指向1号进程。此后，号进程。此后，由由1号进程通过号进程通过wiat等待孤儿进程终止，并回收等待孤儿进程终止，并回收其其PCB表项。表项。l若子进程先终止，而父进程不通过若子进程先终止，而父进程不通过wait()系统系统调用回收其调用回收其PCB，则子进程变为，则子进程变为僵化进程僵化进程（ps命令列出命令列出），直到父进程终），直到父进程终止时该子进程的止时该

17、子进程的PCB才被释放。才被释放。 operating IT systemDLNUDLNU死锁问题(DEADLOCK)4. 守护进程(daemon)在后台执行，与控制终端脱离，不需通过用户登录。通常是：等待某个事件发生（如接受网络连接请求），或周期性地执行特定任务（如cron进程定期执行指定的操作） operating IT systemDLNUDLNU死锁问题(DEADLOCK) Windows NT系统引导序列系统引导序列预引导：预引导：l加电自检加电自检l加载硬盘主引导区加载硬盘主引导区l加载分区中的引导扇区加载分区中的引导扇区l加载加载ntldr文件文件(NT loader)NT系统引

18、导：系统引导：l起动最小文件系统起动最小文件系统Minifilel读入读入boot.ini文件并据此显示起动选择项文件并据此显示起动选择项l加载用户选定的操作系统（如选择加载用户选定的操作系统（如选择MS DOS则则加载加载bootsect.dos）l运行运行l加载加载ntoskrnl.exe，接收收集的硬件配置信，接收收集的硬件配置信息并初始化息并初始化Windows NT operating IT systemDLNUDLNU死锁问题(DEADLOCK)NT系统建立：系统建立：l加载加载HAL和和kernel（依据（依据Registry加载适当的设备驱动程序）加载适当的设备驱动程序）l初始化初始化kernel和驱动程序；保存和驱动程序；保存CurrentControlSet，创建但不保存，创建但不保存CloneControlSet；利用收集的信息建立注册硬件表；利用收集的信息建立注册硬件表（蓝屏（蓝屏blue screen）l起动任务管理程序起动