《操作系统死锁》课件

操作系统死锁操作系统死锁是指多个进程互相等待对方释放资源，导致所有进程都无法继续执行的状态，也称为死循环。死锁会严重影响系统的性能，甚至导致系统崩溃，因此理解和预防死锁对于操作系统设计和使用至关重要。死锁概念及特征1死锁定义死锁是指多个进程因竞争资源而相互等待，导致所有进程都无法继续执行的现象。2死锁特征死锁存在四个必要条件：互斥、请求和保持、不可剥夺、循环等待。3死锁后果死锁会导致系统资源浪费，系统性能下降，甚至系统崩溃。4解决死锁可以通过预防、避免、检测和恢复等方法来解决死锁问题。死锁产生的必要条件互斥条件资源在同一时间只能被一个进程使用。请求和保持条件进程至少已经占有了一个资源，并请求其他资源。不可剥夺条件进程已经占有的资源不能被其他进程强行夺走，只有进程自己才能释放。环路等待条件多个进程形成一个循环等待资源的链，每个进程都在等待链中下一个进程所占有的资源。资源分配图资源分配图是描述系统中资源和进程之间关系的一种图形表示方法。它使用节点和边来表示资源、进程以及它们之间的分配关系。每个节点代表一个进程或一个资源，每个边代表一个资源分配关系。资源分配图分析死锁资源分配图每个进程都表示为一个节点，每个资源也表示为一个节点。进程节点指向资源节点，表示该进程正在使用该资源。循环等待如果存在一个循环路径，那么就会发生死锁。例如，进程P1占有资源R1，并请求资源R2，而进程P2占有资源R2，并请求资源R1。环路检测可以通过遍历资源分配图，寻找循环路径来判断是否发生了死锁。如果发现环路，那么就说明系统处于死锁状态。死锁检测算法定义死锁检测算法用于识别系统中是否存在死锁状态。该算法定期检查系统状态，并通过分析资源分配情况来判断是否发生死锁。检测算法通常需要维护一个资源分配图，该图描述了系统中每个进程对每个资源的请求和占用情况。步骤建立资源分配图通过图遍历算法寻找循环依赖如果存在循环依赖，则表示发生了死锁类型主要有两种类型的检测算法：基于资源分配图的算法和基于等待关系的算法。基于资源分配图的算法更直观，而基于等待关系的算法更易于实现。银行家算法安全状态银行家算法通过检查系统是否处于安全状态来预防死锁。安全状态是指系统能够按顺序完成所有进程，而不会出现死锁。资源分配银行家算法允许进程在需要时请求额外的资源。然而，它会先检查系统是否能够满足该请求，并确保系统仍然处于安全状态。资源回收当一个进程完成时，它将释放其持有的所有资源，使这些资源可供其他进程使用。银行家算法实例1可用资源假设系统有三个资源类型：A、B、C，其可用资源分别为：3,3,22进程需求假设系统有五个进程：P1、P2、P3、P4、P5，每个进程所需的资源数量如下：进程ABC已分配P17531,2,0P23222,1,1P39023,0,2P42222,1,0P54330,0,13安全状态当进程P1、P3、P4、P5、P2依次完成时，系统始终处于安全状态，不会出现死锁。死锁预防策略破坏互斥条件某些资源不可能由多个进程共享。破坏请求和保持条件进程必须在运行前获得所有需要的资源，不允许在运行过程中请求资源。破坏环路等待条件为系统中的所有资源指定唯一的顺序，并要求进程按顺序请求资源。实现资源有序分配进程在请求资源时必须按照顺序，防止循环等待条件出现。破坏互斥条件共享资源允许多个进程同时访问同一个资源。例如，一个共享文件可以被多个进程同时读取。非共享资源例如打印机，同一时间只能被一个进程使用。这通常会导致死锁。破坏请求和保持条件11.请求和保持条件当一个进程在等待被分配资源时，它可能仍然持有其他资源。22.资源请求进程需要向操作系统请求资源，以便完成其任务。33.资源保持当进程等待资源分配时，它仍然保持已分配的资源。44.破坏方法要求进程在请求资源之前释放所有已分配的资源。破坏环路等待条件环路等待条件所有进程必须以相同的顺序请求资源。例如，进程A请求资源R1然后R2，进程B请求R2然后R1。破坏环路等待可以引入一个全局顺序，所有进程都必须按照此顺序请求资源。例如，进程A请求资源R1然后R2，进程B请求资源R1然后R2。实现资源有序分配1资源类型排序根据资源类型进行排序，例如磁盘、内存、CPU。2资源分配顺序按顺序分配资源，避免资源分配冲突。3资源释放顺序释放资源时保持与分配顺序一致，避免出现死锁。有序分配资源可以防止资源分配冲突，从而避免死锁。死锁避免策略安全状态系统处于安全状态时，可以保证所有进程都能完成。资源分配在分配资源时，需要判断是否会进入不安全状态。银行家算法银行家算法是一种常用的死锁避免策略。安全序列安全序列是指系统中所有进程按顺序执行，且不会导致死锁的执行顺序。如果系统存在一个安全序列，则系统处于安全状态，否则处于不安全状态。安全状态不一定意味着系统没有死锁，但可以有效降低死锁风险。1安全系统处于安全状态0不安全系统处于不安全状态安全状态检查1安全状态系统资源充足2安全序列按顺序执行3安全状态系统安全安全状态检查用于判断系统是否处于安全状态。安全状态意味着系统资源充足，存在一个安全序列，所有进程可以按序执行并完成。只有在安全状态下，系统才能避免死锁。死锁恢复策略杀死死锁进程选择一个或多个死锁进程，并将其终止。此方法简单粗暴，但会造成资源浪费，并且可能导致数据丢失。资源抢占从死锁进程中抢占资源，分配给其他进程。此方法需要慎重选择抢占资源的进程和资源，并确保抢占过程不会导致系统崩溃。回滚将死锁进程回滚到之前的一个状态，释放资源，并重新开始执行。回滚需要记录进程的状态和资源使用情况，可能比较复杂。杀死死锁进程杀死死锁进程杀死死锁进程是解决死锁的一种简单粗暴的方法，但也存在缺陷。潜在风险杀死死锁进程会导致数据丢失，进程执行状态的丢失，以及系统资源的浪费。慎用只有在死锁无法通过其他方法解决，且数据丢失可以接受的情况下，才考虑杀死死锁进程。资源抢占选择牺牲者当死锁发生时，选择一个或多个进程作为牺牲者，释放其持有的资源。回滚操作需要将被抢占进程恢复到先前状态，以便释放资源。这可能涉及回滚执行，恢复数据等。代价高昂资源抢占可能导致性能损失和数据不一致，需要谨慎选择和实施。资源分配图实例分析资源分配图是描述系统中资源分配状态的图形模型。它可以直观地展示每个进程当前占有的资源和正在等待的资源。通过分析资源分配图，我们可以判断系统是否处于死锁状态。例如，系统中存在两个进程P1和P2，以及两种资源R1和R2。P1占有R1，P2占有R2，P1正在等待R2，P2正在等待R1。此时系统处于死锁状态。死锁状态监测动态监测实时监控系统资源状态，识别潜在死锁迹象。异常检测当检测到系统资源竞争异常，触发报警机制。数据分析分析死锁发生频率、原因和影响，为优化系统提供参考。死锁检测算法原理11.资源分配图死锁检测算法基于资源分配图，该图显示系统中所有进程和资源的分配情况。22.循环等待算法检测资源分配图中是否存在循环等待，如果有，则表示系统处于死锁状态。33.可达性分析算法分析每个进程是否可以获得所需资源，如果所有进程都无法获得资源，则系统处于死锁状态。44.死锁检测算法通过分析资源分配图，算法可以判断系统是否处于死锁状态，并找到处于死锁状态的进程和资源。死锁检测算法实现1算法流程算法首先检查系统中每个进程是否持有资源，然后根据资源分配情况构建资源分配图。2循环检测算法循环遍历每个进程，检查是否能够获得其所需的全部资源，若能，则标记该进程为安全状态。3结果判定若所有进程均标记为安全状态，则系统处于无死锁状态；否则，系统处于死锁状态。死锁预防和避免对比死锁预防死锁预防是指在系统设计阶段采取措施，防止死锁发生。通过限制资源分配或使用策略来消除死锁产生的条件。死锁避免死锁避免是指在系统运行时动态地检查资源分配情况，避免系统进入死锁状态。系统会根据当前状态和未来请求，动态调整资源分配，确保不会发生死锁。死锁恢复方法优缺点杀死死锁进程简单易行，但可能导致资源浪费，丢失工作进度。资源抢占需要选择合适的进程和资源，可能导致系统性能下降。回滚恢复到之前的安全状态，需要记录系统状态，可能增加系统开销。进程饥饿问题饥饿现象进程长期得不到CPU分配，无法执行饥饿进程一直处于等待状态饥饿原因优先级调度算法，低优先级进程长期得不到执行资源分配不公平，某些进程长期无法获得资源进程优先级与死锁1优先级分配操作系统可以为进程分配不同的优先级。2高优先级高优先级进程更容易获得资源，更容易被调度运行。3低优先级低优先级进程可能会被长时间阻塞，无法获得所需资源，从而导致死锁。4死锁问题优先级分配机制可能导致死锁，因为高优先级进程可能会阻止低优先级进程获取资源。层次化资源分配分层管理将系统中的资源划分为多个层次，每个层次都包含不同的资源类型。分层访问进程访问资源时，需要先申请较高级别的资源，再申请较低级别的资源。降低死锁概率通过分层管理和分层访问，可以有效地降低死锁发生的概率。示例例如，可以将内存、磁盘、文件系统等资源划分到不同的层次，并制定相应的访问规则。死锁相关案例分析死锁问题在现实世界中经常出现，例如多个应用程序争夺资源，可能会导致系统死锁，导致应用程序崩溃。举例来说，在数据库系统中，如果两个事务同时锁定同一数据行，可能会导致死锁。如果两个事务都等待对方