資源描述：
《操作系統(tǒng)授課講義-5.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在PPT專區(qū)-天天文庫。
1、第5章并行性----互斥和同步5.1概論5.1.1并行性的概念（并行程序設計）并行技術可以分為：硬件并行----指多種硬件設備并行工作，如CPU與通道并行、外部設備之間并行等。軟件并行----指多個程序或一個程序的各程序段的運行在時間上重疊（并行程序設計）。5.1.2程序并行性的表示1、有向圖串并行混合SFSFP1P2P3串行并行P1SFP2P3P4P5P6P1P7P8P5P4P2P32、并行語言荷蘭著名的計算機科學家Dijkstra在1965年提出并行語句記號：COBEGINS1;S2;......;SnCOEND其
2、中：COBEGIN/COEND相當一個括號，表示其中的所有語句S1、S2、......、Sn是可并行執(zhí)行的。可嵌套Si:簡單語句，復合語句，并行語句。編譯程序為每個并行語句Si設置一個進程。常見的并行語言：并行PASCAL，CSP/K語言，MODULA語言，擴充的Ada等3、程序并行性表示舉例算術表達式求值：(a―b)*(c―d)+(e/f)**2+*――/**2abcdefSFt3t2t1t5t4t6t1=a-bt2=c-dt3=e/ft4=t1*t2t5=t3**2t6=t4+t5BEGINCOBEGINt1=a-
3、bt2=c-dt3=e/fCOENDCOBEGINt4=t1*t2t5=t3**2COENDt6=t4+t5ENDSFt5t1t3t2t4t6問題：上面的表示具有最大的并行度嗎？請改寫程序。5.1.3并行程序設計的特點并行程序設計的根本特點:并行性,共享性順序程序設計并行程序設計順序運行模式進程并行，異步地在系統(tǒng)內運行，并以不同速度向前推進程序環(huán)境封閉性系統(tǒng)中同時存在多個進程，均可以異步訪問它所要訪問的共享資源，不再完全獨占，且程序（或進程）還可以被其他進程改變。程序運行結果確定性只有遵循并行程序設計的原則正確設計，才
4、可以保證其運行結果的確定性！否則將是不確定的，且是不可再現的。5.2進程間的同步與互斥5.2.1與時間有關的錯誤例1.編制一個卡片復制程序（進程的同步）設有N張卡片要復制，要求輸出的卡片與原先的卡片內容和順序完全一致。又假定緩沖區(qū)的容量只能存放一張卡片的信息。ST讀入ReadCopy復制打孔Punch卡片打孔機卡片輸入機該進程由三個子進程組成：讀入進程R復制進程C打孔進程P若R、C、P順序執(zhí)行，則輸出結果是正確的，但速度慢且資源利用率低。R1C1P1R2C2P2???若R、C、P并發(fā)執(zhí)行，則效率會提高，但輸出結果會不確
5、定。因為R、C、P的執(zhí)行順序完全是不可預料的。下面是我們希望的一種順序：R1C1P1R2C2P2R3C3P3假定現在的狀況如下：ST讀入ReadCopy復制打孔Punch卡片打孔機卡片輸入機①②①[問題]若此時處理機調度的執(zhí)行次序為：R、P、C或P、C、R或R、C、P，結果會怎么樣？例2.編制一個定票系統(tǒng)程序（進程的互斥）X+1的處理過程：(1)R:=x(2)R:=R+1(3)x:=R其中，R是累加器設x的初值是100CPU1CPU2內存已預定票數x終端1終端2假定有兩個終端在售票，其進程分別為P1：...;x:=x+
6、1;...P2：...;x:=x+1;...具體執(zhí)行過程為P1：...;R1:=x;R1:=R1+1;x:=R1;...P2：...;R2:=x;R2:=R2+1;x:=R2;...P1和P2兩個進程發(fā)生的時間不同，將會造成不同的結果。例如，R1:=x執(zhí)行完后R2:=x才執(zhí)行，這時會得到錯誤的結果x=101，而不是102。（在單處理機的情況考慮中斷也有類似的結果）產生上述與時間有關的錯誤的原因是：并發(fā)進程的執(zhí)行過程中存在公共變量，從而產生交互作用，相互影響。公共變量：允許若干個進程訪問和修改的變量，如數據、表格、隊列、
7、緩沖區(qū)等。它們可以是共享的物理資源，也可以是并發(fā)進程之間交換的數據（比如，例1中的緩沖區(qū)，例2中的變量x）。5.2.2進程間的關系在系統(tǒng)中具有公共變量的并發(fā)進程間存在著不同的相互制約關系，它們可歸結為兩種：（1）同步關系（直接制約）：多個進程共同完成一個任務,它們之間必須協(xié)同動作,互相配合,相互交換信息--進程通信（2）互斥關系（間接制約）：多個進程共享資源，互斥資源的使用具有排它性，因此進程間往往需要互相競爭，以使用這些互斥的資源。也可看成一種特殊的同步關系!重點討論互斥問題[問題]系統(tǒng)中任意兩個進程之間不是同步關系
8、，就是互斥關系，對嗎？5.2.3臨界段（臨界區(qū)）臨界資源(criticalresource)：每次只允許一個進程使用的資源（公共變量）（臨界資源是公共的）臨界區(qū)(criticalsection,CS)：每個進程中訪問臨界資源（公共變量）的那一段程序（每個進程有自己的臨界區(qū)）臨界區(qū)的設計原則：（1）每次至多只允許一個進程進入臨界區(qū)；
