Chap并發(fā)進(jìn)程臨界區(qū)管理學(xué)習(xí)教案

1、會計學(xué)1Chap并發(fā)進(jìn)程臨界區(qū)管理并發(fā)進(jìn)程臨界區(qū)管理多道程序設(shè)計程序的動態(tài)概念內(nèi)存管理提高性能和利用率提高CPU與I/O，I/O之間的并行度固定/動態(tài)分區(qū)、分頁/分段處理器管理/進(jìn)程抽象進(jìn)程抽象I/O設(shè)備管理設(shè)備抽象, I/O軟件的分層虛存抽象虛存抽象處理器調(diào)度虛擬分頁虛擬段頁式文件抽象文件抽象單/多線程結(jié)構(gòu)進(jìn)程中斷技術(shù)虛擬分段并發(fā)進(jìn)程, 同步與互斥(PV, 管程, 進(jìn)程通信)磁盤管理/調(diào)度死鎖問題, 必要條件, 預(yù)防, 避免, 檢測和解除文件邏輯結(jié)構(gòu)文件物理結(jié)構(gòu)文件目錄, 共享與保護(hù)虛擬文件系統(tǒng)I/O控制方式, 緩沖技術(shù)設(shè)備分配, 虛擬設(shè)備Spooling文件管理文件系統(tǒng)文件抽象文件抽象Ch

2、ap3Chap4Chap6Chap2Chap5Roadmap安全與保護(hù) Chap 7，網(wǎng)絡(luò)和分布式 Chap8第1頁/共42頁3第三章 同步、通信與死鎖3.1 并發(fā)進(jìn)程3.2 臨界區(qū)管理3.3 信號量與PV操作3.4 管程3.5 進(jìn)程通信3.6 死鎖3.7 Linux同步機(jī)制和通信機(jī)制3.8 Windows 2003同步機(jī)制和通信機(jī)制第2頁/共42頁4第3頁/共42頁5第4頁/共42頁6第5頁/共42頁7第6頁/共42頁8第7頁/共42頁9第8頁/共42頁10進(jìn)程進(jìn)程i1 i1p1p1i ip po oo1o1i2i2p2p2o2o2i3i3p3p3o3o3t1t1t2t2t3t3時間時間并行

3、工作并行工作i4i4t4t4i5i5P4P4第9頁/共42頁11第10頁/共42頁12第11頁/共42頁13nModularitynConvenience第12頁/共42頁14第13頁/共42頁15第14頁/共42頁16第15頁/共42頁17第16頁/共42頁18第17頁/共42頁19第18頁/共42頁20此時出現(xiàn)把同一張票賣給兩個旅客的情況，兩個旅客可能各自都買到一張同天同次航班的機(jī)票，可是，Aj的值實際上只減去1，造成余票數(shù)不正確。特別是，當(dāng)某次航班只有一張余票時，可能把一張票同時售給兩位旅客。 第19頁/共42頁21由于borrow和return共享代表主存物理資源的臨界變量X，對并發(fā)執(zhí)

4、行不加限制會導(dǎo)致錯誤，例如，一個進(jìn)程調(diào)用borrow申請主存，在執(zhí)行比較B和X大小的指令后，發(fā)現(xiàn)BX，但在執(zhí)行進(jìn)程進(jìn)入等待主存資源隊列前，另一個進(jìn)程調(diào)用return搶先執(zhí)行，歸還所借全部主存資源；這時，由于前一個進(jìn)程還未成為等待者，return中的釋放等主存資源進(jìn)程相當(dāng)于空操作，以后當(dāng)調(diào)用borrow的應(yīng)用進(jìn)程被置成等主存資源時，可能己經(jīng)沒有其他進(jìn)程再來歸還主存，從而，申請資源的進(jìn)程處于永遠(yuǎn)等待狀態(tài)。 第20頁/共42頁22第21頁/共42頁23第22頁/共42頁24第23頁/共42頁25第24頁/共42頁26第25頁/共42頁27第26頁/共42頁283.2 臨界區(qū)管理3.2.1 互斥與臨界

5、區(qū)互斥與臨界區(qū) 實現(xiàn)臨界區(qū)管理的幾種嘗試實現(xiàn)臨界區(qū)管理的幾種嘗試 實現(xiàn)臨界區(qū)管理的軟件方法實現(xiàn)臨界區(qū)管理的軟件方法 實現(xiàn)臨界區(qū)管理的硬件設(shè)施實現(xiàn)臨界區(qū)管理的硬件設(shè)施第27頁/共42頁29第28頁/共42頁30(3) 擇一而入、算法可行。第29頁/共42頁31進(jìn)程P1(P2)測試inside2(insidel)與隨后置insidel(inside2)之間，P2(P1)可能發(fā)現(xiàn)insidel(inside2)有值false，于是它將置inside2(insidel)為true，并且與進(jìn)程P1(P2)同時進(jìn)入臨界區(qū)。 兩個進(jìn)程可能都進(jìn)去兩個進(jìn)程可能都進(jìn)去第30頁/共42頁32延遲進(jìn)程P1(P2)對i

6、nside2(insidel)的測試，先置insidel(inside2)為true，用以封鎖P2(P1)，修正后的程序如下，不幸，它也是無效的，有可能每個進(jìn)程都把自己的標(biāo)志置成true，從而出現(xiàn)死循環(huán)，這時沒有進(jìn)程能在有限時間內(nèi)進(jìn)入臨界區(qū)，造成永遠(yuǎn)等待。 兩個進(jìn)程都進(jìn)不去兩個進(jìn)程都進(jìn)不去第31頁/共42頁33第32頁/共42頁34第33頁/共42頁35P0中執(zhí)行了中執(zhí)行了turn=1, 暫時進(jìn)不去，等暫時進(jìn)不去，等P1中執(zhí)行中執(zhí)行turn=0, P0可以進(jìn)去，可以進(jìn)去，P0使用完臨界區(qū)，退出臨界區(qū)的時候，將使用完臨界區(qū)，退出臨界區(qū)的時候，將turn=0(好像是多余的好像是多余的), 此時此時

7、P1還是進(jìn)不去，要等還是進(jìn)不去，要等p0執(zhí)行執(zhí)行turn=1，使得，使得P1有機(jī)會進(jìn)入臨界區(qū)，之后，有機(jī)會進(jìn)入臨界區(qū)，之后，P1退出臨界區(qū)的時候，退出臨界區(qū)的時候，turn=1，P0暫時進(jìn)不去，等在暫時進(jìn)不去，等在P1中執(zhí)行中執(zhí)行turn=0，P0可以再次進(jìn)入臨界區(qū)，因此，可以再次進(jìn)入臨界區(qū)，因此，P0和和P1使用臨界區(qū)的次序變成了完全一比一的交替方式，這只能是臨界區(qū)互斥使用的一個特例，不能滿足臨界區(qū)互斥使用的完全隨機(jī)性。使用臨界區(qū)的次序變成了完全一比一的交替方式，這只能是臨界區(qū)互斥使用的一個特例，不能滿足臨界區(qū)互斥使用的完全隨機(jī)性。第34頁/共42頁36第35頁/共42頁37第36頁/共42頁38第37頁/共42頁39在進(jìn)入臨界區(qū)之前，首先用TS指令測試s，如果沒有進(jìn)程在臨界區(qū)內(nèi)，則可以進(jìn)入，否則必須循環(huán)測試直到s為true；當(dāng)進(jìn)