银行家算法求取安全进程执行序列

Ⅰ 避免死锁的方法有哪些

1、避免给一个锁嵌套上锁，在持有一个锁的时候，不要再给这个锁上锁。如果使用多个锁，使用std::lock。

2、在持有锁时，不要调用别人提供的函数，因为你不清楚别人的代码怎么实现的，不知道它是不是在使用锁。

3、给多个锁上锁时，固定顺序。如果在给多个所上锁，并且无法使用std::lock，最好的做法就是在每一个线程中，都按照同样的顺序。

4、分层次来使用锁，把程序分成几个层次。区分每个层次中使用的锁，当一个线程已经持有更低层次的锁时，不允许使用高层次的锁。可以在程序运行时给不同的锁加上层次号，记录每个线程持有的锁。

(1)银行家算法求取安全进程执行序列扩展阅读：

解决方法

在系统中已经出现死锁后，应该及时检测到死锁的发生，并采取适当的措施来解除死锁。

死锁预防。

这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但是由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。

死锁避免。

系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。这是一种保证系统不进入死锁状态的动态策略。

死锁检测和解除。

先检测：这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源。检测方法包括定时检测、效率低时检测、进程等待时检测等。

然后解除死锁：采取适当措施，从系统中将已发生的死锁清除掉。

这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施，有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

Ⅱ 什么是死锁,简述死锁发生的四个必要条件,如何避免死锁

死锁是一种特定的程序状态，它发生在两个或多个进程永久性地等待对方释放资源，从而导致它们都无法继续执行。这种状态是由于进程间的竞争条件和不恰当的同步机制造成的。

死锁发生的四个必要条件是：

1. 互斥条件：至少有一个资源必须处于非共享模式，即一次只有一个进程能够使用。如果其他进程请求该资源，请求者只能等待，直到资源被释放。

2. 持有并等待：一个进程持有至少一个资源，但因等待另一进程释放其他资源而处于阻塞状态。这意味着进程不会释放它持有的任何资源，除非得到其他所需的资源。

3. 非抢占条件：资源不能被强制从一个进程中夺走。进程必须主动释放资源。这与操作系统的某些强制管理策略有关，但并不适用于所有情况。

4. 循环等待：存在一个进程等待循环，即进程集合{P1, P2, ..., Pn}中的P1正在等待由P2持有的资源，而P2又在等待由P3持有的资源，……，直到最后Pn在等待由P1持有的资源为止。这是一个循环依赖关系，导致所有相关进程都处于等待状态。

避免死锁的策略包括：

避免循环等待：通过确保系统始终处于安全状态来避免死锁。这可以通过银行家算法或其他资源分配算法来实现，以确保每次资源请求都能被满足而不会导致死锁。此外，还可以预先分配所有必要的资源给进程，从而减少请求和等待的可能性。这意味着一次性获取所有所需资源，然后进行操作，完成后释放所有资源给其他进程使用。这样的策略可以避免循环等待条件的发生。此外，合理设计系统并发级别和交互方式也可以减少死锁的发生概率。通过检测和恢复机制处理死锁：即使采取了预防措施，死锁仍然可能发生。因此，检测和解决死锁的策略也是必要的。这包括监视系统状态并检测死锁的发生，然后采取措施解决它，如撤销或中止导致死锁的进程。采用破坏四个必要条件之一的方式预防死锁：改变互斥条件是不可能的，但可以通过其他方式破坏四个必要条件中的某些条件来预防死锁。例如，可以通过使用超时来破坏等待条件，让一个进程持有多个资源的固定时间来迫使其他进程不得不放弃等待的资源；或者通过强制分配策略来破坏循环等待条件等。这些方法都需要系统管理员根据实际情况仔细选择和使用，以最大限度地减少死锁的风险。合理安排进程的执行顺序：通过合理安排并发执行的进程顺序，避免产生竞争条件和循环等待的情况。利用一次性封锁的策略来防止系统发生死锁，当要访问某项数据时一定要获取全部封锁方可进行任务执行；避免在中间某个过程中将所需封锁释放掉的情况发生。合理设置进程的优先级，保证不会出现互锁或者一个循环互锁的进程的组合产生以避免死锁问题出现等都可以帮助解决该问题。在实际编程中可能根据系统需要灵活运用以上方法中的一种或多种来实现防止死锁发生的目的从而保持系统稳定和数据的完整安全。

Ⅲ 什么是死锁，怎样引入死锁

1.死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。
2.产生死锁的原因：
（1）竞争不可抢占性资源。
（2）竞争可消耗资源。
当系统中供多个进程共享的资源如打印机，公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。12

（3）进程推进顺序不当。
进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。12

如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。
一个线程也可引起死锁。12

3.产生死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 请求和保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不可抢占条件:进程已获得的资源，在末使用完之前，不能强行剥夺，只能在进程使用完时由自己释放。
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。因此可以写下如下的预防死锁的方法。
4.避免死锁的方法：
（1）破坏“互斥”条件:就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般“互斥”条件是无法破坏的。因此，在死锁预防里主要是破坏其他三个必要条件，而不去涉及破坏“互斥”条件。
（2）破坏“请求和保持”条件:在系统中不允许进程在已获得某种资源的情况下，申请其他资源。即要想出一个办法，阻止进程在持有资源的同时申请其他资源。
方法一：所有进程在运行之前，必须一次性地申请在整个运行过程中所需的全部资源。这样，该进程在整个运行期间，便不会再提出资源请求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不能满足进程的要求，即使其它所需的各资源都空闲也不分配给该进程，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件。
该方法优点：简单、易行且安全。
缺点：a.资源被严重浪费，严重恶化了资源的利用率。
b.使进程经常会发生饥饿现象。12

方法二：要求每个进程提出新的资源申请前，释放它所占有的资源。这样，一个进程在需要资源S时，须先把它先前占有的资源R释放掉，然后才能提出对S的申请，即使它可能很快又要用到资源R。
（3）破坏“不可抢占”条件：允许对资源实行抢夺。
方法一：如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占有的资源，如果有必要，可再次请求这些资源和另外的资源。
方法二：如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。只有在任意两个进程的优先级都不相同的条件下，该方法才能预防死锁。
（4）破坏“循环等待”条件：将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。这样做就能保证系统不出现死锁。
利用银行家算法避免死锁：
银行家算法:
设进程i提出请求Request[j]，则银行家算法按如下规则进行判断。
(1) 如果Request[j]≤Need[i,j]，则转向（2），否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Request[j]≤Available[j]，则转向（3）；否则表示尚无足够资源，Pi需等待。
(3) 假设进程i的申请已获批准，于是修改系统状态：
Available[j]=Available[j]-Request[i]
Allocation[i,j]=Allocation[i,j]+Request[j]
Need[i,j]=Need[i,j]-Request[j]
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
安全性算法：
(1) 设置两个工作向量Work=Available；Finish[i]=False
(2) 从进程集合中找到一个满足下述条件的进程，
Finish [i]=False;

Need[i,j]≤Work[j];

如找到，执行(3)；否则，执行(4)123456

(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work[j]=Work[j]+Allocation[i,j];

Finish[i]=True;

Go to step 2;123456

(4) 如所有的进程Finish[i]=true，则表示安全；否则系统不安全。
5.死锁的解除：
一旦检测出死锁，就应立即釆取相应的措施，以解除死锁。死锁解除的主要两种方法：
1) 抢占资源。从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
2) 终止（或撤销）进程。终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。
总结：
一般情况下,如果同一个线程先后两次调用lock,在第二次调用时,由于锁已经被占用,该线程会挂起等待别的线程释放锁,然而锁正是被自己占用着的,该线程又被挂起而没有机会释放锁,因此就永远处于挂起等待状态了,这叫做死锁(Deadlock)。另⼀一种典型的死锁情形是这样:线程A获得了锁1,线程B获得了锁2,这时线程A调⽤用lock试图获得锁2,结果是需要挂起等待线程B释放锁2,而这时线程B也调⽤用lock试图获得锁1,结果是需要挂起等待线程A释放锁1,于是线程A和B都永远处于挂起状态了。12

注意：
写程序时应该尽量避免同时获得多个锁,如果一定有必要这么做,则有一个原则:如果所有线程在需要多个锁时都按相同的先后顺序(常见的是按Mutex变量的地址顺序)获得锁,则不会出现死锁。比如一个程序中用到锁1、锁2、锁3,它们所对应的Mutex变量的地址是锁1<锁2<锁3,那么所有线程在需要同时获得2个或3个锁时都应该按锁1、锁2、锁3的顺序获得。如果要为所有的锁确定一个先后顺序比较困难,则应pthread_mutex_trylock调用代替pthread_mutex_lock 调用,以免死锁。