跳到主要内容

处理机调度

银行家算法​

可用资源向量Available​

Available=(R1...Rm)Available=\begin{pmatrix} R1 \\ ... \\ Rm \end{pmatrix}

其中Available[j]=K 表示系统Rj类资源有K个

最大需求矩阵Max​

如果Max[i,j]=K，则表示第i个进程需要Rj类资源的最大数目为K

分配矩阵Allocation​

也叫做占有矩阵。它定义了系统中每一进程已占有的每一类资源数。

如果Allocation[i,j]=K，则表示第i个进程当前已分得Rj类资源的数目为K。

申请矩阵Need​

每一个进程还需要的各类资源数。如果Need[i,j]=K，则表示第i个进程还需要Rj类资源K个，才能完成其任务。

Need[i,j]=Max[i,j]−Allocation[i,j]Need[i,j]=Max[i,j]-Allocation[i,j]
Need=Max−AllocationNeed=Max-Allocation

银行家算法的核心是这之后的安全性检测算法

安全性监测算法​

工作向量work​

系统可用资源向量Work。初始置Work=Available。

work记录系统中各类资源的当前可用数目，是available的替身

以简化

进程可完成标志向量finish​

表示系统能否运行完成

  • 若Finish[i]=true，则表示第i个进程能够获得足够的资源，运行完成；
  • 设初值Finish[i]=false，i=0,1,2,…,n-1。
  • 当有足够资源分配给第i个进程时，再令Finish[i]=true。

finish 记录进程是否可完成或者说是否可加人安全序列

算法实现步骤​

终于懂了大专为什么是大专捏，讲这个步骤都不讲是为什么这样做，其核心本质是什么,根本理解不了=>

警告

这个子算法实质上就是个寻找安全序列的过程,如果找到就返回逻辑真值(表示系统状态“安全”),否则返回逻辑假值

  1. 设置两个工作向量。设置工作向量Work、完成向量Finish，并赋初值。work=available

  2. 进行安全性检查(目的是：若按进程编号的顺序找到了一个可加人安全序列的进程,即满足条件finish;=false 且 need,< work 的进程 P,则假设该进程不久将完成任务归还资源)

    • 从进程集合中查找一个能满足下述条件的进程i：
      • Finish[i]=false并且Need[i]≤Work；
      • 若找到这样的进程，执行步骤（3）；
      • 若找不到这样的进程，则转步骤（4）。

  3. Work= Work+Allocation[i];//释放资源

    Finish[i]= true;

    返回步骤（2）。因为进程Pi若能执行完成，则能够释放它所占的资源。

  4. 若所有进程的Finish[i]=true都满足，则表示系统处于安全状态，正式将资源分配给进程Pi；

    通过运算过程同时可以找到一个安全序列。

    否则，系统处于不安全状态，系统不能进行这次试探性分配，恢复原来的资源分配状态，让进程Pi等待。

例题​

image-20230625202608616

系统资源总数向量total＝available+Allocation=(17,5,20)

当前Work向量=(2,3,3)

need矩阵已经给出

完成向量finish(false,false,false,false,false)

因为need[P4]<=work

所以P4可以满足对资源的请求

finish[4]=1

work=work+allocation[4]=(4,5,4)

因为。。。

2.need>>work，不能实现资源分配

​