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