Chap并發(fā)進程臨界區(qū)管理學習教案

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

2、ap3Chap4Chap6Chap2Chap5Roadmap安全與保護 Chap 7，網絡和分布式 Chap8第1頁/共42頁3第三章 同步、通信與死鎖3.1 并發(fā)進程3.2 臨界區(qū)管理3.3 信號量與PV操作3.4 管程3.5 進程通信3.6 死鎖3.7 Linux同步機制和通信機制3.8 Windows 2003同步機制和通信機制第2頁/共42頁4第3頁/共42頁5第4頁/共42頁6第5頁/共42頁7第6頁/共42頁8第7頁/共42頁9第8頁/共42頁10進程進程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此時出現把同一張票賣給兩個旅客的情況，兩個旅客可能各自都買到一張同天同次航班的機票，可是，Aj的值實際上只減去1，造成余票數不正確。特別是，當某次航班只有一張余票時，可能把一張票同時售給兩位旅客。 第19頁/共42頁21由于borrow和return共享代表主存物理資源的臨界變量X，對并發(fā)執(zhí)

4、行不加限制會導致錯誤，例如，一個進程調用borrow申請主存，在執(zhí)行比較B和X大小的指令后，發(fā)現BX，但在執(zhí)行進程進入等待主存資源隊列前，另一個進程調用return搶先執(zhí)行，歸還所借全部主存資源；這時，由于前一個進程還未成為等待者，return中的釋放等主存資源進程相當于空操作，以后當調用borrow的應用進程被置成等主存資源時，可能己經沒有其他進程再來歸還主存，從而，申請資源的進程處于永遠等待狀態(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ū) 實現臨界區(qū)管理的幾種嘗試實現臨界區(qū)管理的幾種嘗試 實現臨界區(qū)管理的軟件方法實現臨界區(qū)管理的軟件方法 實現臨界區(qū)管理的硬件設施實現臨界區(qū)管理的硬件設施第27頁/共42頁29第28頁/共42頁30(3) 擇一而入、算法可行。第29頁/共42頁31進程P1(P2)測試inside2(insidel)與隨后置insidel(inside2)之間，P2(P1)可能發(fā)現insidel(inside2)有值false，于是它將置inside2(insidel)為true，并且與進程P1(P2)同時進入臨界區(qū)。 兩個進程可能都進去兩個進程可能都進去第30頁/共42頁32延遲進程P1(P2)對i

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

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