操作系統(tǒng)第3章處理機(jī)調(diào)度與死鎖-習(xí)題ppt課件

1、第三章 處理機(jī)調(diào)度與死鎖 27. 試?yán)糜涗浶托盘?hào)量寫出一個(gè)不會(huì)出現(xiàn)死鎖的哲學(xué)家進(jìn)餐問題的算法。處理方法有三： 至多允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐，來保證至少有一個(gè)哲學(xué)家可以進(jìn)餐，最終總會(huì)放下他所用的筷子，從而更多的哲學(xué)家可以進(jìn)餐； 僅當(dāng)哲學(xué)家的左、右兩只筷子都可用時(shí)，才允許他進(jìn)餐； 規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，再拿右邊的筷子；偶數(shù)號(hào)哲學(xué)家先拿他右邊的筷子，再拿其左邊的筷子。這樣，1、2號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子，3、4號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子哲學(xué)家順時(shí)針就座，筷子也順時(shí)針放置，且1號(hào)筷子在1號(hào)哲學(xué)家左邊，這樣他們總是先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲得后，再競(jìng)爭(zhēng)偶數(shù)號(hào)筷子，最后總能保證一位哲學(xué)家能拿到兩只筷子。第三章

2、 處理機(jī)調(diào)度與死鎖 采用方案，我們添加一位效力生信號(hào)量room，讓他只允許四位哲學(xué)家同時(shí)進(jìn)入餐廳。var chopstick: array0, , 4 of semaphore := (1, 1, 1, 1, 1); room: semaphore := 4; i:=integer;第三章 處理機(jī)調(diào)度與死鎖 procedure philosopher (i: integer);beginrepeat think; wait(room); wait(chopsticki) ; wait(chopstick(i+1) mod 5) ; eat; signal(chopstick(i+1) mod

3、5) ; signal(chopsticki); signal(room);until false;end第三章 處理機(jī)調(diào)度與死鎖 begin parbegin philosopher (0); philosopher (1); philosopher (2); philosopher (3); philosopher (4); parendend第三章 處理機(jī)調(diào)度與死鎖 另一種方法：var chopstick: array0, , 4 of semaphore := (1, 1, 1, 1, 1); mutex: semaphore := 1; i:=integer;第三章 處理機(jī)調(diào)度與死鎖

4、 procedure philosopher (i: integer);beginrepeat think; wait(mutex); wait(chopsticki) ; wait(chopstick(i+1) mod 5) ; signal(mutex); eat; signal(chopstick(i+1) mod 5) ; signal(chopsticki); until false;end第三章 處理機(jī)調(diào)度與死鎖 21. 在銀行家算法的例子中，假設(shè)P0發(fā)出的懇求向量由Request(0, 2, 0)改為Request(0, 1, 0)，問系統(tǒng)可否將資源分配給它？答：P0懇求資源：P

5、0發(fā)出懇求向量Requst0(0，1，0)，系統(tǒng)按銀行家算法進(jìn)展檢查： Request0(0, 1, 0)Need0(7, 4, 3); Request0(0, 1, 0)Available(2, 3, 0); 系統(tǒng)暫時(shí)先假定可為P0分配資源，并修正有關(guān)數(shù)據(jù)，Available=(2, 3, 0)-(0, 1, 0)=(2, 2, 0)第三章 處理機(jī)調(diào)度與死鎖 進(jìn)程AllocationNeedAvailableP00 2 07 3 32 2 0P13 0 20 2 0P23 0 2 6 0 0 P32 1 1 0 1 1 P40 0 2 4 3 1 第三章 處理機(jī)調(diào)度與死鎖 進(jìn)程WorkNee

6、dAllocationWork+AllocationFinishP1 2 2 0 0 2 0 3 0 2 5 2 2trueP3 5 2 2 0 1 1 2 1 1 7 3 3trueP0 7 3 3 7 3 3 0 2 0 7 5 3trueP2 7 5 3 6 0 0 3 0 210 5 5trueP410 5 5 4 3 1 0 0 210 5 7true進(jìn)展平安性檢查，可以找到一個(gè)平安序列P1，P3，P0，P2，P4。可以將P0所懇求的資源分配給它。第三章 處理機(jī)調(diào)度與死鎖 另外還可找到的平安序列有：P1，P3，P4，P2，P0，P1，P3，P2，P4，P0， P1，P3，P4，P0，

7、P2。第三章 處理機(jī)調(diào)度與死鎖 22. 在銀行家算法中，假設(shè)出現(xiàn)下述資源分配情況：ProcessAllocationNeedAvailableP00 0 3 40 0 1 2 1 6 2 2P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6第三章 處理機(jī)調(diào)度與死鎖 試問：1該形狀能否平安？2假設(shè)進(jìn)程P2提出懇求Request(1, 2, 2, 2)后，系統(tǒng)能否將資源分配給它？答：(1) 系統(tǒng)按銀行家算法進(jìn)展檢查：第三章 處理機(jī)調(diào)度與死鎖 ProcessWorkNeedAllocationWork+Allocation

8、FinishP0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 trueP3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 trueP1 1 9 8 6 1 7 5 0 1 0 0 0 2 9 8 6 trueP2 2 9 8 6 2 3 5 6 1 3 5 43 12 13 10 trueP43 12 13 10 0 6 5 6 0 0 1 43 12 14 14 true進(jìn)展平安性檢查，可以找到一個(gè)平安序列P0，P3，P1，P2，P4。所以系統(tǒng)是平安的。第三章 處理機(jī)調(diào)度與死鎖 另外還可找到的平安序列有：P0，P3，P4，P1，P2，P0，P3，P1，P4，P2， P0，P3，P1，P2，P4。第三章 處理機(jī)調(diào)度與死鎖 答：(2) P2懇求資源：懇求向量Requst(1, 2, 2, 2)，系統(tǒng)按銀行家算法進(jìn)展檢查： Request(1, 2, 2, 2)Need2(2, 3, 5, 6); Request(1, 2, 2, 2)Available(1, 6, 2, 2); 系統(tǒng)暫時(shí)先假定可為P2分配資源，并修正有關(guān)數(shù)據(jù)，Available=(1, 6, 2, 2)-(1, 2, 2, 2)=(0, 4, 0, 0)第三章 處理機(jī)調(diào)度與死鎖 進(jìn)展平安性檢查，可用資源Available(0, 4, 0, 0)已不能滿足任何進(jìn)程的需求，故