[理工] [OS] Dead Lock

[mickeyha (M*schief)]

洪逸 作業系統金寶典
p.5-59

47.Consider a snapshit if the system as shown below. Upon the

   next request, P1 makes a request for ( 0 4 2 0) and is granted

   immediately. What is the minimum number of initial instances

   (i.e. the total number of instances before any [rpcess enters the

   system) for each resource type to make sure system still in a

   safe after P1's request is granted? (答案請以(a b c d) 方式表示)





                        Allocation           Max
                         A B C D           A B C D
                P0       0 0 1 2           0 1 1 2
                P1       1 0 0 0           1 7 5 0
                P2       1 3 5 4           2 4 5 6
                P3       0 4 3 2           0 7 5 2
                P4       0 0 1 4           0 6 5 6


Ans:
                          Need
                         A B C D
                P0       0 1 0 0
                P1       0 7 5 0
                P2       1 1 0 2
                P3       0 3 2 0
                P4       0 6 4 2


                所以最少  = (3,12,12,12)

這題我嘗試過各種算法，
都解不出這個數字呀Q___Q
是要用到定理那兩個算式嗎？ (Maxi <= m , Maxi總合 < n+m這兩個...)
請大大解決
謝謝!!!!!!!!!!!!!


--
Why Not ：-P

http://whynot-p.blogspot.com/


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.248.50.179
※ 編輯: mickeyha        來自: 111.248.50.179       (11/01 23:11)
→ Eggchun:一開始把0420配給P1所以P1的NEED剩下0330,之後看NEED,最小
→ Eggchun:是P0(因為他只要1就可以完成),所以就假設目前只剩下0100
→ Eggchun:的資源可以給他使用,完成後釋出,所以現在有0113的資源,
→ Eggchun:因為0113的資源也沒有辦法配給現在需要資源的process,所以
→ Eggchun:再找一次需要最少資源便可完成的process,所以是p2,p2完成
→ Eggchun:後,就有2466的資源了,2466每個PROCESS都可以拿,所以只要把
→ Eggchun:剩下的PROCESS所佔有的資源全部加回,就可以得到3,12,12,12
→ Eggchun:我是這樣算的啦-.-  不知道有沒有其他方式XD?