`
xinklabi
  • 浏览: 1587837 次
  • 性别: Icon_minigender_1
  • 来自: 吉林
文章分类
社区版块
存档分类
最新评论

银行家算法(避免死锁的算法)

 
阅读更多

银行家算法[编辑]

 
 

银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。

 

 

背景[编辑]

在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。

进程[1][编辑]

 Allocation   Max   Available
   ABCD  ABCD  ABCD
 P1 0014  0656  1520 
 P2 1432  1942 
 P3 1354  1356
 P4 1000  1750

我们会看到一个资源分配表,要判断是否为安全状态,首先先找出它的Need,Need即Max(最多需要多少资源)减去Allocation(原本已经分配出去的资源),计算结果如下:

 NEED
 ABCD
 0642 
 0510
 0002
 0750

然后加一个全都为false的字段

 FINISH
 false
 false
 false
 false

接下来找出need比available小的(千万不能把它当成4位数 他是4个不同的数)

   NEED  Available
 ABCD  ABCD
 0642  1520
 0510<-
 0002
 0750

P2的需求小于能用的,所以配置给他再回收

  NEED  Available
 ABCD  ABCD
 0642  1520
 0000 +1432
 0002-------
 0750  2952

此时P2 FINISH的false要改成true(己完成)

 FINISH
 false
 true
 false
 false

接下来继续往下找,发现P3的需求为0002,小于能用的2952,所以资源配置给他再回收

  NEED  Available
 ABCD  A B C D
 0642  2 9 5 2
 0000 +1 3 5 4
 0002----------
 0750  3 12 10 6

同样的将P3的false改成true

 FINISH
 false
 true
 true
 false

依此类推,做完P4→P1,当全部的FINISH都变成true时,就是安全状态。

安全和不安全的状态[编辑]

如果所有过程有可能完成执行(终止),则一个状态(如上述范例)被认为是安全的。由于系统无法知道什么时候一个过程将终止,或者之后它需要多少资源,系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下,这是一个合理的假设,因为系统不是特别关注每个进程运行了多久(至少不是从避免死锁的角度)。此外,如果一个进程终止前没有获取其它能获取的最多的资源,它只是让系统更容易处理。

基于这一假设,该算法通过尝试寻找允许每个进程获得的最大资源并结束(把资源返还给系统)的进程请求的一个理想集合,来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。

伪代码(pseudo-code)[2][编辑]

P - 进程的集合

Mp - 进程p的最大的请求数目

Cp - 进程p当前被分配的资源

A - 当前可用的资源

while (P != ∅) {
    found = FALSE;
    foreach (p ∈ P) {
        if (Mp − Cp ≤ A) {
             /* p可以獲得他所需的資源。假設他得到資源後執行;執行終止,並釋放所擁有的資源。*/
             A = A + Cp ;
             P = P − {p};
             found = TRUE;
        }
    }
    if (! found) return FAIL;
}
return OK;
分享到:
评论

相关推荐

    操作系统银行家算法避免死锁

    银行家算法避免死锁 VM软件 Linux系统 C语言 成功编译 成功运行 内附完整课设报告,代码,运行cpp 附有哲学家进餐简略一题 原课设要求:死锁避免 (1)请设计一个程序演示死锁避免算法(银行家算法)。 (2)要求该...

    课程设计-模拟银行家算法避免死锁.doc

    银行家算法避免死锁知识点 银行家算法的背景和目的 在多道程序系统中,多个进程的并发执行可以提高系统的利用率和吞吐量,但是可能会发生死锁,导致进程无法继续执行。死锁是多个进程在运行过程中因争夺资源而造成...

    银行家算法避免死锁源代码(C#篇)

    本文档是使用C#编写的银行家算法避免死锁的程序设计。里面包含数组初始化,利用递归判断输入整数,输出安全序列等函数,希望对大家有帮助。如有错误,请多多指教~

    银行家算法(仿真模拟银行家算法对死锁的避免).zip

    仿真模拟银行家算法对死锁的避免。 所谓安全状态是指系统能按某种进程顺序,来为每个进程pi分配所需的资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利地...银行家算法就是一种最有代表性的避免死锁的算

    银行家算法避免死锁

    《银行家算法:避免死锁的艺术》 在操作系统设计中,死锁是一个至关重要的问题,它指的是多个进程因资源竞争而陷入无法继续执行的状态。银行家算法,由荷兰计算机科学家艾兹格·迪科斯彻(Edsger W. Dijkstra)提出...

    银行家算法避免死锁的过程.cpp

    模拟实现银行家算法避免死锁的过程。 模拟实现银行家算法避免死锁的过程。 2. 实验目的 理解银行家算法,掌握查找进程安全序列的过程,深入理解资源共享、资源分配、资源回收的概念。 实验原理 银行家算法是一种...

    安徽大学操作系统实验(三)银行家算法避免死锁,C语言编写,环境vs2008,已经调试过可运行,含实验报告,含具体流程图 ,内有详细注释和变量解释

    为了解决这个问题,银行家算法被引入,这是一种预防死锁的策略。本实验主要关注的就是银行家算法的实现,它在安徽大学的操作系统课程中作为实验项目进行,使用C语言编写,并在Visual Studio 2008环境下编译和调试...

    银行家算法实现死锁的避免.cpp

    《操作系统》第四版汤小丹等人编著,纯C语言编写实现银行家算法,可以自行设置进程相关数据,显示安全序列,可以多次申请资源查看是否安全

    银行家算法避免死锁 C# 操作系统课程设计

    本次课程设计通过编写和调试一个仿真模拟银行家算法避免死锁的程序,观察产生死锁的条件,并采用银行家算法,有效地避免死锁的发生。这是我们的操作系统课程设,用.net做的。 银行家算法避免死锁,其中有三个模块,...

    死锁避免——银行家算法

    这个程序主要通过模拟系统死锁避免的实现,使用银行家算法来避免死锁加深对死锁避免,系统安全状态等的理解。 (1)输入1执行算法,输入2退出程序,其他输入无效。算法要用到的资源种类有10种,每种资源的数目为1~10...

    仿真模拟银行家算法对死锁的避免

    1)模拟一个银行家算法; (2) 初始化,为系统的各个进程分配资源; (3) 计算此时的安全序列; (4)为某进程申请资源; (5) 预分配后,系统处于安全状态,则修改系统的资源分配情况; (6) 预分配后,系统...

    银行家算法死锁的避免.doc

    在银行家算法中,系统模拟银行贷款的过程来管理资源,确保系统始终能够避免死锁的发生。该算法的核心思想是预先分配资源,但不超过进程的最大需求,同时检查系统是否处于安全状态。 实验中,你需要设计一个系统,...

    模拟银行家算法实现死锁避免

    操作系统中的死锁问题一直是一个重要的研究领域,而模拟银行家算法是解决这一问题的一种有效方法。这个算法由艾兹格·迪杰斯特拉提出,它借鉴了银行贷款系统的概念,通过对资源分配进行预检查,来避免系统进入死锁...

    利用银行家算法避免死锁

    ### 银行家算法详解及其在避免死锁中的应用 #### 一、银行家算法简介 银行家算法是操作系统中一种经典的预防死锁的方法,主要用于解决资源分配问题中的安全性问题,确保系统不会进入不安全状态,从而避免死锁的...

    仿真银行家算法对死锁的避免

    银行家算法是避免死锁的一种重要方法,通过编写一个简单的银行家算法程序,加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。死锁的产生,必须同时满足四个条件,即一个资源每次...

    银行家算法避免死锁C语言代码实现

    银行家算法的实现,当输入每类资源的MAX和Allocation,计算是否存在安全序列

    计算机操作系统银行家算法避免死锁

    银行家算法避免死锁 银行家算法是一种避免死锁的重要方法,它可以 asegurar 系统的安全性和稳定性。在计算机操作系统中,银行家算法是一个经典的解决死锁问题的算法。下面我们将详细介绍银行家算法的原理、实现和...

Global site tag (gtag.js) - Google Analytics