[数据结构与算法]银行家算法的Python实现

'''银行家算法
    Dijkstra在1965年提出的银行家算法是著名的死锁避免算法
    博客地址：https://www.cnblogs.com/wkfvawl/p/11929508.html
'''
import pandas as pd


class Bank:

    def __init__(self, **resources: int):
        '''
        @param: resources
            资源的数量
        '''
        self.resources = pd.DataFrame(resources, index=["total"])
        self.allocation = pd.DataFrame(
            [], index=self.resources.keys(), dtype=int)
        self.maxs = pd.DataFrame([], index=self.resources.keys(), dtype=int)

    def _avaliable(self, allocation):
        aval = self.resources - allocation.sum(axis=1)
        aval.index = ["avaliable"]
        return aval

    def _safe_check(self, allocation):
        if allocation.empty:
            return True

        aval = self._avaliable(allocation)
        need = self._need(allocation)

        for custom in allocation.columns:
            t = need[custom] <= aval
            if (t.all(axis=None)):
                temp = allocation.copy().drop(columns=[custom])
                if self._safe_check(temp):
                    return True

        return False

    def is_safe(self):
        '''是否安全
        '''
        return self._safe_check(self.allocation)

    def lend(self, custom, **need_resources: int):
        allocation = self.allocation.copy()

        for resource, number in need_resources.items():
            allocation[custom][resource] += number

        if self._safe_check(allocation):
            self.allocation = allocation
            print(custom, need_resources, "已分配")
        else:
            print(custom, need_resources, "不安全，拒绝分配")

    def _need(self, allocation):
        return self.maxs - allocation

    def add_custom(self, name, **max_resources: int):
        '''
        @param: name
            客户名称
        @param: max_resources
            申请资源的最大额度
        '''
        self.maxs = pd.concat([self.maxs, pd.DataFrame(
            {name: max_resources})], axis=1).fillna(0).astype(int)
        self.allocation[name] = 0

    def table(self):
        '''列出资源和进程表格信息'''
        print(pd.concat([self.maxs.T, self.allocation.T, self._need(self.allocation).T], axis=1, keys=[
              "max", "allocation", "need"]))
        print(pd.concat([self._avaliable(self.allocation), self.resources]))



def main():
    bank = Bank(R1=9, R2=3, R3=6)

    bank.add_custom("p1",  R1=3, R2=2, R3=2)
    bank.add_custom("p2",  R1=6, R2=1, R3=3)
    bank.add_custom("p3",  R1=3, R2=1, R3=4)
    bank.add_custom("p4",  R1=4, R2=2, R3=2)

    bank.lend("p1", R1=1)
    bank.lend("p2", R1=5, R2=1, R3=1)
    bank.lend("p3", R1=2, R2=1, R3=1)
    bank.lend("p4", R1=0, R2=0, R3=2)


    # 1. 此刻是否安全
    print(bank.is_safe())

    # 2. p2发出请求（1，0，1），是否安全
    bank.lend("p2", R1=1, R2=0, R3=1)

    # 3. p1发出请求（1，0，1），是否安全
    bank.lend("p1", R1=1, R2=0, R3=1)

    # 4. p3发出请求（0，0，1），是否安全
    bank.lend("p3", R1=0, R2=0, R3=1)



if __name__ == "__main__":
    main()