銀行家算法例題——四步走解題.doc

銀行家算法例題系統(tǒng)中原有三類資源A、B、C和五個進(jìn)程P1、P2、P3、P4、P5，A資源17，B資源5，C資源20。當(dāng)前（T0時刻）系統(tǒng)資源分配和進(jìn)程最大需求如下表。 資源進(jìn)程AllocationMaxA B CA B CP1 2 1 2 5 5 9P2 4 0 2 5 3 6 P3 4 0 5 4 0 11 P4 2 0 4 4 2 5P5 3 1 44 2 41、現(xiàn)在系統(tǒng)T0時刻是否處于安全狀態(tài)？2、是否可以允許以下請求？(1)T1時刻：P2 Request2=(0,3,4)(2)T2時刻：P4 Request4=(2,0,1)(3)T3時刻：P1 Request1=(0,2,0)注：T0 T1 T2 T3時刻是前后順序，后一時刻是建立在前一時刻的基礎(chǔ)上。解：由題設(shè)可知Need=Max-Allocation AvailableA=17-(2+4+4+2+3)=2(原有-分配) 同理AvailableB=3,AvailableC=3 可得T0時刻資源分配表如下所示（表中數(shù)據(jù)順序均為A B C）：ProcessAllocationMaxNeedAvailableP1 2 1 2 5 5 93 4 72 3 3P2 4 0 2 5 3 61 3 4 P3 4 0 5 4 0 110 0 6 P4 2 0 4 4 2 52 2 1 P5 3 1 4 4 2 41 1 01、判斷T0時刻是否安全，需要執(zhí)行安全算法找安全序列，過程如下表：WorkNeedAllocationWork+AllocationFinishP42 3 32 2 12 0 44 3 7TrueP34 3 70 0 64 0 58 3 12TrueP28 3 121 3 44 0 212 3 14 TrueP512 3 141 1 03 1 415 4 18TrueP115 4 183 4 72 1 217 5 20TrueT0時刻能找到一個安全序列P4,P3,P2,P5,P1,故T0時刻系統(tǒng)處于安全狀態(tài)。2、判斷T1 T2 T3時刻是否滿足進(jìn)程請求進(jìn)行資源分配。（1）T1時刻，P2 Request2=(0,3,4)/第一步 判斷條件滿足Request2=(0,3,4)=Need2(1,3,4)不滿足Request2=(0,3,4)=Available(2,3,3)故系統(tǒng)不能將資源分配給它，此時P2必須等待。（2）T2時刻，P4 Request4=(2,0,1)/第一步 判斷條件滿足Request4=(2,0,1)=Need4(2,2,1) 滿足Request4=(2,0,1)=Available(2,3,3)/第二步 修改Need、Available、Allocation的值 Available=Available-Request4= (0,3,2) Allocation4=Allocation4+Request4=(4,0,5) Need4=Need4-Request4=(0,2,0)/第三步 執(zhí)行安全算法，找安全序列(注解：先寫上work，其初值是系統(tǒng)當(dāng)前進(jìn)行試分配后的Available(0,3,2) ，找五個進(jìn)程中Need小于work的進(jìn)程，比如Need4=Work滿足，則將P4寫在第一行的最前面，同時寫出P4的Need和 Allocation，以此類推)WorkNeedAllocationWork+AllocationFinishP40 3 20 2 04 0 54 3 7TrueP24 3 71 3 44 0 28 3 9TrueP38 3 90 0 64 0 512 3 14TrueP512 3 141 1 03 1 415 4 18TrueP115 4 183 4 72 1 217 5 20True/第四步 在此時刻（T2時刻）存在安全序列P4,P2,P3,P5,P1,則滿足Request4請求，將Request4=(2,0,1)分配給P4。（3）T3時刻，P1 Request1=(0,2,0)/第一步 判斷條件滿足Request1=(0,2,0)=Need1(3,4,7) 滿足Request1=(0,2,0)=Available(2,3,3)/第二步 修改Need、Available、Allocation的值 Available=Available-Request1= (0,1,2) (T2時刻基礎(chǔ)上) Allocation=Allocation1+Request1=(2,3,0) Need1=Need1-Request1=(3,2,7)/第三步 執(zhí)行安全算法，找安全序列對于所有Needi均不小于Work(初值是Available (0,1,2)，找不到安全序列，故系統(tǒng)不能將資源分配給它，P1必須等待。歸納總結(jié)銀行家算法解題總結(jié)為四步走：第一步：判斷銀行家算法中的條件，看是否滿足，如果滿足跳轉(zhuǎn)第二步（判斷條件）Requesti=NeediRequesti=Available第二步：試圖分配，修改Need、Available、Allocation的值（修改NAA）Available=Available-Requesti Allocationi=Allocationi+RequestiNeedi=Needi-Reque