操作系統(tǒng)-進(jìn)程管理.doc

4.4 進(jìn)程的相互制約關(guān)系 在多道程序的環(huán)境中，系統(tǒng)中的多個(gè)進(jìn)程可以并發(fā)執(zhí)行，同時(shí)它們又要共享系統(tǒng)中的資源，這些資源有些是可共享使用的，如磁盤(pán)，有些是以獨(dú)占方式使用的，如打印機(jī)。由此將會(huì)引起一系列的矛盾，產(chǎn)生錯(cuò)綜復(fù)雜的相互制約的關(guān)系。 產(chǎn)生這種錯(cuò)綜復(fù)雜的相互制約關(guān)系的原因有二： 資源共享 進(jìn)程合作進(jìn)程間的關(guān)系 進(jìn)程之間有兩種關(guān)系： 第一種是競(jìng)爭(zhēng)關(guān)系，從而有進(jìn)程的互斥(Mutual Exclusion)是解決進(jìn)程間競(jìng)爭(zhēng)關(guān)系的手段。 第二種是協(xié)作關(guān)系，某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作。進(jìn)程的同步(Synchronization)是解決進(jìn)程間協(xié)作關(guān)系的手段。進(jìn)程間的關(guān)系 進(jìn)程的互斥(Mutual Exclusion)是指若干個(gè)進(jìn)程要使用同一共享資源時(shí)，任何時(shí)刻最多允許一個(gè)進(jìn)程去使用，其它要使用該資源的進(jìn)程必須等待，直到占有資源的進(jìn)程釋放該資源。 臨界區(qū)管理可以解決進(jìn)程互斥問(wèn)題，后續(xù)課程將詳細(xì)介紹臨界區(qū)的解決方案。進(jìn)程間的關(guān)系 進(jìn)程的同步(Synchronization)是解決進(jìn)程間協(xié)作關(guān)系的手段。指一個(gè)進(jìn)程的執(zhí)行依賴于另一個(gè)進(jìn)程的消息，當(dāng)一個(gè)進(jìn)程沒(méi)有得到來(lái)自于另一個(gè)進(jìn)程的消息時(shí)則等待，直到消息到達(dá)才被喚醒。 不難看出，進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系，即逐次使用互斥共享資源。進(jìn)程間的關(guān)系 對(duì)于協(xié)作關(guān)系有如下例子： 設(shè)input 、process、和output三個(gè)進(jìn)程分工協(xié)作完成讀入數(shù)據(jù)、加工處理和打印輸出任務(wù)，這是一種典型的協(xié)作關(guān)系。 操作系統(tǒng)要確保諸進(jìn)程在執(zhí)行次序上協(xié)調(diào)一致： 沒(méi)有輸入完一塊數(shù)據(jù)之前不能加工處理 沒(méi)有加工處理完一塊數(shù)據(jù)之前不能打印輸出等等 每個(gè)進(jìn)程都要接收到它進(jìn)程完成一次處理的消息后，才能進(jìn)行下一步工作。4.5.1 互斥的概念 引例： 宿舍固定電話的使用 打印機(jī)的使用 還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源。臨界資源說(shuō)明 例1：兩個(gè)進(jìn)程A、B共享一臺(tái)打印機(jī) 若不加以控制，兩個(gè)進(jìn)程的輸出結(jié)果可能交織在一起，很難區(qū)分。 臨界資源說(shuō)明 例2：兩個(gè)進(jìn)程共享一個(gè)變量x 設(shè)：x代表某航班機(jī)座號(hào)，p1和p2兩個(gè)售票進(jìn)程，售票工作是對(duì)變量x加1。 這兩個(gè)進(jìn)程在一個(gè)處理機(jī)C上并發(fā)執(zhí)行，分別具有內(nèi)部寄存器r1和r2 ，兩個(gè)進(jìn)程共享一個(gè)變量x時(shí)，兩種可能的執(zhí)行次序： 說(shuō)明 以前的課程也講到了與時(shí)間有關(guān)的錯(cuò)誤，其實(shí)就是因?yàn)楣蚕碜兞浚@個(gè)共享的變量就是臨界資源。 如果不對(duì)臨界資源加以控制，那么就可能出現(xiàn)錯(cuò)誤，這就是本節(jié)要解決的問(wèn)題。什么是臨界資源 特點(diǎn)：當(dāng)兩個(gè)進(jìn)程公用一個(gè)變量時(shí)，它們必須順序地使用，一個(gè)進(jìn)程對(duì)公用變量操作完畢后，另一個(gè)進(jìn)程才能去訪問(wèn)和修改這一變量。 一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。 哪些臨界資源？ 臨界資源： 物理設(shè)備，如輸入機(jī)、打印機(jī)、磁帶機(jī)等都具有這種性質(zhì)。 軟件資源，如公用變量、數(shù)據(jù)、表格、隊(duì)列等也都具有這一特點(diǎn)。什么是臨界區(qū) 臨界區(qū)：在每個(gè)進(jìn)程中，訪問(wèn)臨界資源的那段程序能夠從概念上分離出來(lái)，稱為臨界區(qū)或臨界段。 它就是進(jìn)程中對(duì)公共變量(或存儲(chǔ)區(qū))進(jìn)行審查與修改的程序段，稱為相對(duì)于該公共變量的臨界區(qū)。什么是臨界區(qū)什么是臨界區(qū)什么是互斥？ 互斥：在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問(wèn)某一存儲(chǔ)區(qū)域時(shí)，就不允許其他進(jìn)程來(lái)讀出或者修改存儲(chǔ)區(qū)的內(nèi)容，否則，就會(huì)發(fā)生后果無(wú)法估計(jì)的錯(cuò)誤。 進(jìn)程間的這種相互制約關(guān)系稱為互斥。進(jìn)入臨界區(qū)的準(zhǔn)則：進(jìn)入臨界區(qū)的準(zhǔn)則： (1)每次至多有一個(gè)進(jìn)程處于臨界區(qū)； (2)當(dāng)有若干個(gè)進(jìn)程欲進(jìn)入臨界區(qū)時(shí)，應(yīng)在有限的時(shí)間內(nèi)使其進(jìn)入； (3)進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時(shí)間。4.5.2 鎖和上鎖、開(kāi)鎖操作 解決進(jìn)程互斥的最簡(jiǎn)單的辦法是加鎖。 什么是鎖用某假設(shè)變量w代表某種資源的狀態(tài)，w稱為“鎖”。鎖位值： 為“0”表示資源可用 為1表示資源已被占用（不可用） 。 在系統(tǒng)中為每個(gè)臨界資源設(shè)置一個(gè)鎖位。4.5.2 鎖和上鎖、開(kāi)鎖操作 當(dāng)一個(gè)進(jìn)程使用某個(gè)臨界資源之前必須完成下列操作： 1、考察鎖位的值(是0還是1)； ； 2、若原來(lái)的值是為“0”，將鎖位置為“1” ，此為上鎖操作 （表示占用該資源）； 3、若原來(lái)值是為“1”，（該資源已被別人占用），則不改變?cè)瓉?lái)的值，循環(huán)檢測(cè)等待。 4、當(dāng)某進(jìn)程使用完資源后，將鎖位置為“0 ” ，稱為開(kāi)鎖操作，此時(shí)別的等待進(jìn)程一旦檢測(cè)到w的不為1了，則表示可以使用臨界資源了。4.5.2 鎖和上鎖、開(kāi)鎖操作說(shuō)明 在上述簡(jiǎn)單的關(guān)鎖原語(yǔ)中，goto語(yǔ)句使得lock(w)原語(yǔ)的進(jìn)程占用處理機(jī)而等待進(jìn)入互斥段（稱為忙等待busy waiting)測(cè)試法，浪費(fèi)CPU時(shí)間。 。 為此，可將上述上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)做進(jìn)一步修改。 修改后的原語(yǔ)如下所示：改進(jìn)的lock和unlock算法鎖和上鎖、開(kāi)鎖操作 設(shè)臨界區(qū)的類名為w。為了保證每一次臨界區(qū)中只能有一個(gè)程序段被執(zhí)行，又設(shè)鎖定位keyw。keyw表示該鎖定位屬于類名為w的臨界區(qū)。 加鎖后的臨界區(qū)程序描述如下： lock(keyw)/上鎖 unlock(keyw) /開(kāi)鎖 經(jīng)過(guò)鎖處理，任何時(shí)候都不可能有兩個(gè)及以上的進(jìn)程進(jìn)入臨界去。4.5.3 用上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)互 假設(shè)有兩個(gè)進(jìn)程共享打 印機(jī)，兩個(gè)進(jìn)程中使用 打印機(jī)的程序段為臨界 區(qū)。 為保證打印的正確，設(shè) 置打印機(jī)的鎖print， 其初值為“0”，表示打印機(jī)可用。4.5.3 用上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)互斥4.6.1 信號(hào)燈的概念 前面介紹的方法雖能保證互斥，可正確解決臨界區(qū)調(diào)度問(wèn)題，但有明顯缺點(diǎn)： 對(duì)不能進(jìn)入臨界區(qū)的進(jìn)程，采用忙式等待(busy waiting)測(cè)試法，浪費(fèi)CPU時(shí)間。 將測(cè)試能否進(jìn)入臨界區(qū)的責(zé)任推給各個(gè)競(jìng)爭(zhēng)的進(jìn)程會(huì)削弱系統(tǒng)的可靠性，加重了用戶編程負(fù)擔(dān)。4.6.1 信號(hào)燈的概念 1965年荷蘭的計(jì)算機(jī)科學(xué)家Dijkstra提出了新的同步工具信號(hào)量和P、V操作。 他將交通管制中多種顏色的信號(hào)燈管理交通的方法引入操作系統(tǒng)，讓兩個(gè)或多個(gè)進(jìn)程通過(guò)信號(hào)量(Semaphore) 展開(kāi)交互。 進(jìn)程在某一特殊點(diǎn)上停止執(zhí)行直到得到一個(gè)對(duì)應(yīng)的信號(hào)量，通過(guò)信號(hào)量這一設(shè)施，任何復(fù)雜的進(jìn)程交互要求可得到滿足，這種特殊的變量就是信號(hào)量。4.6.1 信號(hào)燈的概念 信號(hào)量?jī)H能由同步原語(yǔ)對(duì)其進(jìn)行操作，原語(yǔ)是操作系統(tǒng)中執(zhí)行時(shí)不可中斷的過(guò)程、即原子操作(Atomic Action)。 Dijkstra發(fā)明了兩個(gè)同步原語(yǔ)：P操作和V操作(荷蘭語(yǔ)中“測(cè)試(Proberen)” 和“增量(Verhogen)” 的頭字母，此外還用的符號(hào)有：wait和signal；up和down；sleep和wakeup等。 本書(shū)中采用Dijkstra最早論文中使用的符號(hào)P和V。利用信號(hào)量和P、V操作既可以解決并發(fā)進(jìn)程的競(jìng)爭(zhēng)問(wèn)題，又可以解決并發(fā)進(jìn)程的協(xié)作問(wèn)題。信號(hào)燈的分類 信號(hào)量按其用途可分為兩種： 公用信號(hào)量：聯(lián)系一組并發(fā)進(jìn)程，相關(guān)的進(jìn)程均可在此信號(hào)量上執(zhí)行P和V操作。初值常常為1，用于實(shí)現(xiàn)進(jìn)程互斥。 私有信號(hào)量：聯(lián)系一組并發(fā)進(jìn)程，僅允許此信號(hào)量擁有的進(jìn)程執(zhí)行P操作，而其他相關(guān)進(jìn)程可在其上施行V操作。初值常常為0或正整數(shù)，多用于并發(fā)進(jìn)程同步。信號(hào)燈的分類 信號(hào)量按其取值可分為兩種： 二元信號(hào)量：僅允許取值為0和1，主要用于解決進(jìn)程互斥問(wèn)題（非我即你，通常用一個(gè)布爾量來(lái)表示）。 一般信號(hào)量：允許取值為非負(fù)整數(shù)，主要用于解決進(jìn)程間的同步問(wèn)題。4.6.1 信號(hào)燈的概念 信號(hào)燈的定義： 信號(hào)燈是一個(gè)確定的二元組（s,q），s 是一個(gè)具有非負(fù)初值的整型變量，q 是一個(gè)初始狀態(tài)為空的排隊(duì)站。 S代表資源的實(shí)體。在實(shí)際應(yīng)用中應(yīng)準(zhǔn)確地說(shuō)明s的意義和初值，每個(gè)信號(hào)燈都有一個(gè)隊(duì)列，其初始狀態(tài)為空。4.6.2 P、V操作 信號(hào)燈的值僅能由P、V操作來(lái)改變， 對(duì)信號(hào)燈的P操作記為：P(S)，P操作是一個(gè)原子操作。 對(duì)信號(hào)燈的V操作記為：V(S), V操作是一個(gè)原子操作。 在實(shí)際操作系統(tǒng)中，一般情況下是由機(jī)器硬件提供P、V操作的指令，當(dāng)然是原子操作，若機(jī)器不提供P、V操作的指令，則操作系統(tǒng)提供P、V操作原語(yǔ)。信號(hào)量值的物理意義 信號(hào)燈是整型變量。 變量值 0 時(shí)，表示綠燈，進(jìn)程執(zhí)行。 變量值 0:其數(shù)值代表可用的資源數(shù)量 S=0：代表無(wú)資源可用，但也沒(méi)有等待的進(jìn)程，即也沒(méi)有申請(qǐng)資源的進(jìn)程 S0:其數(shù)值代表可用的資源數(shù)量 S=0：代表無(wú)資源可用，但也沒(méi)有等待的進(jìn)程，即也沒(méi)有申請(qǐng)資源的進(jìn)程 S=0,不能為負(fù)值多緩沖的生產(chǎn)者消費(fèi)者問(wèn)題 問(wèn)題描述：若干進(jìn)程通過(guò)有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，“生產(chǎn)者”進(jìn)程不斷寫(xiě)入，而“消費(fèi)者”進(jìn)程不斷讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作。 即滿足如下條件：（1）消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的。（2）生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的。 生產(chǎn)者消費(fèi)者的例子 例1： 計(jì)算進(jìn)程和打印進(jìn)程 計(jì)算進(jìn)程 cp不斷產(chǎn)生數(shù)據(jù)，是生產(chǎn)者；打印進(jìn)程 iop不斷打印數(shù)據(jù)，是消費(fèi)者。 例2： 通信問(wèn)題 發(fā)消息進(jìn)程 send不斷產(chǎn)生消息，是生產(chǎn)者； 收消息進(jìn)程 receive不斷接收消息，是消費(fèi)者多生產(chǎn)者-消費(fèi)者問(wèn)題圖示生產(chǎn)者與消費(fèi)者 生產(chǎn)者：當(dāng)有界緩沖區(qū)中無(wú)空位置時(shí)，要等待； 向有界緩沖區(qū)放入物品后，要發(fā)消息（V操作）。 消費(fèi)者：當(dāng)有界緩沖區(qū)中無(wú)物品時(shí)，要等待； 從有界緩沖區(qū)取出物品后，要發(fā)消息（P操作） 。多緩沖區(qū)的P-C問(wèn)題之間的關(guān)系 一、同步關(guān)系： 對(duì)于生產(chǎn)者進(jìn)程：產(chǎn)生一個(gè)數(shù)據(jù)，當(dāng)要送入緩沖區(qū)時(shí)，要檢查緩沖區(qū)是否已滿，若未滿，則可將數(shù)據(jù)送入緩沖區(qū)，并通知消費(fèi)者進(jìn)程；否則，等待； 對(duì)于消費(fèi)者進(jìn)程：當(dāng)它去取數(shù)據(jù)時(shí)，要看緩沖區(qū)中是否有數(shù)據(jù)可取，若有則取走一個(gè)數(shù)據(jù)，并通知生產(chǎn)者進(jìn)程，否則，等待。 這種相互等待，并互通信息就是典型的進(jìn)程同步。多緩沖區(qū)的P-C問(wèn)題之間的關(guān)系 二、互斥關(guān)系 緩沖區(qū)又是個(gè)臨界資源，在多個(gè)進(jìn)程在生產(chǎn)產(chǎn)品時(shí)，它不允許在緩沖區(qū)的某一個(gè)單元同時(shí)存放產(chǎn)品 也不允許多個(gè)進(jìn)程同時(shí)消費(fèi)緩沖區(qū)的某一個(gè)單元產(chǎn)品，因此，還有個(gè)互斥的問(wèn)題。多生產(chǎn)者-消費(fèi)者問(wèn)題的一般解答 信號(hào)燈設(shè)置 兩個(gè)同步信號(hào)燈empty:表示空緩沖區(qū)的數(shù)目，初值為有界緩沖區(qū)的大小n； full :表示滿緩沖區(qū)的數(shù)目，其初值為0； 一個(gè)互斥信號(hào)燈- mutex：互斥信號(hào)燈，初值為1。同步描述程序描述程序描述多生產(chǎn)者-消費(fèi)者問(wèn)題的flash動(dòng)畫(huà)思考與說(shuō)明 如果我們把生產(chǎn)者進(jìn)程中的兩個(gè)P操作交換次序，即那么會(huì)有什么問(wèn)題嗎？參見(jiàn)下圖的程序參考：主程序并行程序思考與說(shuō)明 在這個(gè)問(wèn)題中P操作的次序是很重要的，如果我們把生產(chǎn)者進(jìn)程中的兩個(gè)P操作交換次序，即那么就會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。 分析如下：分析說(shuō)明 在某個(gè)時(shí)刻,消費(fèi)者消費(fèi)的比較快，把所有的產(chǎn)品消費(fèi)完，有:empty=n,mutex=1,full=0 接著消費(fèi)者進(jìn)程運(yùn)行到1處，使得mutex=0,運(yùn)行到2處full=-10，消費(fèi)者進(jìn)程等待 在接著生產(chǎn)者進(jìn)程運(yùn)行到3處，由于生產(chǎn)了一個(gè)產(chǎn)品，故空位置-1，empty=n-1， 運(yùn)行到4初,由于p(mutex)操作，mutex=mutex-1=-10表示有S個(gè)資源可用 S=0表示無(wú)資源可用 S0則| S |表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù) P(S)：表示申請(qǐng)一個(gè)資源 V(S)：表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0信號(hào)量及P、V操作討論（續(xù)1） 2) P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作 當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程 當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn) 如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要,一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前 而兩個(gè)V操作無(wú)關(guān)緊要信號(hào)量及P、V操作討論（續(xù)2） 3）P.V操作的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 簡(jiǎn)單，而且表達(dá)能力強(qiáng)（用P.V操作可解決任何同步互斥問(wèn)題） 缺點(diǎn)： 不夠安全；P.V操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問(wèn)題時(shí)實(shí)現(xiàn)復(fù)雜回顧：哲學(xué)家就餐問(wèn)題問(wèn)題描述： 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤(pán)通心粉，每人面前有一只空盤(pán)子，每?jī)扇酥g放一只筷子 每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉 為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子哲學(xué)家就餐問(wèn)題解法（1）#define N 5 void philosopher (int i) while (true) 思考； 取forki; 取fork(i+1) % 5； 進(jìn)食； 放forki; 放fork(i+1) % 5； 回顧：哲學(xué)家就餐問(wèn)題為防止死鎖發(fā)生可采取的措施： 最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周?chē)?僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子（） 給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之 為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿哲學(xué)家就餐問(wèn)題解法（2）#define N 5#define THINKING 0#define HUNGRY 1#define EATING 2#typedef int semaphore;int stateN;semaphore mutex=1;/叉子操作要互斥的信號(hào)量semaphore sN;/每一個(gè)哲學(xué)家是否能吃為一個(gè)信號(hào)量statei= THINKING ；/初始化i=0-4si=0;/ 初始化i=0-4void test(int i) if (statei = HUNGRY) & (state (i-1) % 5!=EATING) & (state (i+1) % 5!=EATING) statei=EATING; V(si); void philosopher (int i) while (true) 思考; P(mutex); statei = HUNGRY; test(i); V(mutex); P(si); 拿左筷子； 拿右筷子； 進(jìn)食； 放左筷子； 放右筷子； P(mutex) state i = THINKING； test(i-1 % 5); test(i+1 % 5); V(mutex); state i = THINKINGs i = 0經(jīng)典問(wèn)題（1）讀者寫(xiě)者問(wèn)題 問(wèn)題描述：有兩組并發(fā)進(jìn)程: 讀者和寫(xiě)者,共享一組數(shù)據(jù)區(qū) 要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作 不允許讀者、寫(xiě)者同時(shí)操作 不允許多個(gè)寫(xiě)者同時(shí)操作第一類：讀者優(yōu)先如果讀者到： 1）無(wú)讀者、寫(xiě)者，新讀者可以讀 2）有寫(xiě)者等，但有其它讀者正在讀，則新讀者也可以讀 3）有寫(xiě)者寫(xiě)，新讀者等如果寫(xiě)者到： 1）無(wú)讀者，新寫(xiě)者可以寫(xiě) 2）有讀者，新寫(xiě)者等待 3）有其它寫(xiě)者，新寫(xiě)者等待第一類讀者寫(xiě)者問(wèn)題的解法讀者不固定情況：第一類讀者寫(xiě)者問(wèn)題的解法/初始化mutex1=1；W=1；count=0；讀者：Readeriwhile (true) P(mutex1); readcount +; if (readcount=1) P (w);/禁止寫(xiě) V(mutex1); 讀 P(mutex1); readcount -; if (readcount=0) V(w);/可以允許寫(xiě) V(mutex1);寫(xiě)者：Writej while (true) P(w); 寫(xiě) V(w); 實(shí)例訓(xùn)練 有N個(gè)讀者和兩個(gè)編輯同時(shí)處理一篇文章。 對(duì)于讀操作是可以同時(shí)進(jìn)行的，若有讀者正在讀這篇文章，編輯就不能工作； 若編輯正在處理這篇文章，讀者就不能作讀操作。 編輯與編輯的工作也是互斥的，試用信號(hào)燈及P、V操作寫(xiě)出讀者與編輯之間協(xié)同工作的程序描述。說(shuō)明 讀者寫(xiě)者問(wèn)題，它為數(shù)據(jù)庫(kù)訪問(wèn)建立了一個(gè)模型。例如，設(shè)想一個(gè)飛機(jī)定票系統(tǒng)，其中有許多競(jìng)爭(zhēng)的進(jìn)程試圖讀寫(xiě)其中的數(shù)據(jù)。說(shuō)明 在讀者優(yōu)先的進(jìn)程中：現(xiàn)在假設(shè)一個(gè)寫(xiě)者到來(lái)，由于寫(xiě)操作是排他的，所以它不能訪問(wèn)數(shù)據(jù)庫(kù)，而是被掛起。 隨后其他的讀者到來(lái)，這樣只要有一個(gè)讀者活躍，隨后而來(lái)的讀者都被允許訪問(wèn)數(shù)據(jù)庫(kù)。這樣的結(jié)果是只要有讀者陸續(xù)到來(lái)，它們一來(lái)就被允許進(jìn)入，而寫(xiě)者將一直被掛起直到?jīng)]有一個(gè)讀者為止。 假如每2秒鐘來(lái)一個(gè)讀者，而其操作時(shí)間為5秒鐘，則寫(xiě)者將永遠(yuǎn)不能訪問(wèn)數(shù)據(jù)庫(kù)，或者我們說(shuō)寫(xiě)者發(fā)生了饑餓現(xiàn)象。 思考 思考題：請(qǐng)大家試著寫(xiě)出寫(xiě)者優(yōu)先的解法，并且考慮一下，能不能設(shè)計(jì)出一種算法使得無(wú)論對(duì)讀者還是寫(xiě)者都是公平的，不會(huì)存在任何一方可能的饑餓現(xiàn)象。 寫(xiě)者優(yōu)先（第二類讀寫(xiě)/者問(wèn)題） 寫(xiě)者優(yōu)先： 條件： 1）多個(gè)讀者可以同時(shí)進(jìn)行讀 2）寫(xiě)者必須互斥（只允許一個(gè)寫(xiě)者寫(xiě)，也不能讀者寫(xiě)者同時(shí)進(jìn)行） 3）寫(xiě)者優(yōu)先于讀者（一旦有寫(xiě)者，則后續(xù)讀者必須等待沒(méi)有進(jìn)入計(jì)數(shù)的進(jìn)程，喚醒時(shí)優(yōu)先考慮寫(xiě)者）解1 讀者數(shù)量固定 如果讀者數(shù)是固定的，我們可采用下面的算法： rwmutex：用于寫(xiě)者與其他讀者/寫(xiě)者互斥的訪問(wèn)共享數(shù)據(jù) rmutex： 設(shè)該信號(hào)量初始值設(shè)為10，表示最多允許10個(gè)讀者進(jìn)程同時(shí)進(jìn)行讀操作寫(xiě)者優(yōu)先寫(xiě)者優(yōu)先解2 讀者數(shù)不固定 如果讀者數(shù)不固定，采用下面的算法： 設(shè)置三個(gè)互斥信號(hào)量： rwmutex 用于寫(xiě)者與其他讀者/寫(xiě)者互斥的訪問(wèn)共享數(shù)據(jù) rmutex 用于讀者互斥的訪問(wèn)讀者計(jì)數(shù)器readcount nrmutex 用于寫(xiě)者等待已進(jìn)入讀者退出，所有讀者退出前互斥寫(xiě)操作4.8 進(jìn)程通信 并發(fā)進(jìn)程之間的交往本質(zhì)上是互相交換信息。有些情況下進(jìn)程之間交換的信息量很少，例如僅僅交換某個(gè)狀態(tài)信息。 有些情況下進(jìn)程之間交換大批數(shù)據(jù)，例如傳送一批信息或整個(gè)文件。進(jìn)程之間互相交換信息的工作稱之為進(jìn)程通信IPC(InterProcess Communication)。4.8.1 概述P.V操作實(shí)現(xiàn)的是進(jìn)程之間的低級(jí)通訊，所以P.V為低級(jí)通訊原語(yǔ)。它只能傳遞簡(jiǎn)單的信號(hào)，不能傳遞交換大量信息如果要在進(jìn)程間傳遞大量信息則要用Send / Receive原語(yǔ)（高級(jí)通訊原語(yǔ)）進(jìn)程通信的方式1-共享內(nèi)存共享內(nèi)存： 相互通信的進(jìn)程間設(shè)有公共內(nèi)存，一組進(jìn)程向該公共內(nèi)存中寫(xiě)，另一組進(jìn)程從公共內(nèi)存中讀，通過(guò)這種方式實(shí)現(xiàn)兩組進(jìn)程間的信息交換。如圖所示：共享內(nèi)存 內(nèi)存中開(kāi)辟一個(gè)共享存儲(chǔ)區(qū)，諸進(jìn)程通過(guò)該區(qū)實(shí)現(xiàn)通信,這是進(jìn)程通信中最快的方法。進(jìn)程通信的方式2-消息傳遞 有時(shí)進(jìn)程間可能需要交換更多的信息，例如，一個(gè)輸入輸出操作請(qǐng)求，要求把數(shù)據(jù)從一個(gè)進(jìn)程傳送給另一個(gè)進(jìn)程，這種大量的信息傳遞可使用一種高級(jí)通信方式消息傳遞（message passing）來(lái)實(shí)現(xiàn)。 由于操作系統(tǒng)隱蔽了許多實(shí)現(xiàn)細(xì)節(jié)，通過(guò)消息傳遞機(jī)制通信，能簡(jiǎn)化程序編制的復(fù)雜性，方便易用，得到了廣泛應(yīng)用。進(jìn)程通信的方式2-消息傳遞 消息傳遞機(jī)制至少需要提供兩條原語(yǔ)send和receive，前者向一個(gè)給定的目標(biāo)發(fā)送一個(gè)消息，后者則從一個(gè)給定的源接受一條消息。 如果沒(méi)有消息可用，則接收者可能阻塞直到一條消息到達(dá)，或者也可以立即返回，并帶回一個(gè)錯(cuò)誤碼。消息傳遞方式消息傳遞： 系統(tǒng)為進(jìn)程提供了兩個(gè)高級(jí)通訊原語(yǔ)send和receive send：當(dāng)要進(jìn)行消息傳遞時(shí)執(zhí)行 receive：當(dāng)接收者要接收消息時(shí)執(zhí)行消息傳遞的方式 消息傳遞系統(tǒng)的變體很多，常用的有直接通信（消息緩沖區(qū)）方式和間接通信（信箱）方式 Unix的pipeline和socket機(jī)制屬于一種信箱方式的變體。下圖是消息傳遞機(jī)制通信模型。消息傳遞模式：消息傳遞模式分兩大類：(a)消息緩沖（直接通信 ） (b)信箱通信（間接通信）(a)消息緩沖（直接通信 ） 在消息緩沖方式下，在內(nèi)存中開(kāi)設(shè)緩沖區(qū)，發(fā)送進(jìn)程將消息送入緩沖區(qū)，接收進(jìn)程接收傳遞來(lái)的緩沖區(qū)。 企圖發(fā)送或接收消息的每個(gè)進(jìn)程必須指出信件發(fā)給誰(shuí)或從誰(shuí)那里接收消息，可用send原語(yǔ)和receive原語(yǔ)為實(shí)現(xiàn)進(jìn)程之間的通信，這兩個(gè)原語(yǔ)定義如下： send（P，消息）：把一個(gè)消息發(fā)送給進(jìn)程P receive（Q，消息）：從進(jìn)程Q接收一個(gè)消息(a)消息緩沖（直接通信 ） 這樣，進(jìn)程P和Q通過(guò)執(zhí)行這兩個(gè)操作而自動(dòng)建立了一種聯(lián)結(jié)，并且這一種聯(lián)結(jié)僅僅發(fā)生在這一對(duì)進(jìn)程之間。 消息可以有固定長(zhǎng)度或可變長(zhǎng)度兩種： 固定長(zhǎng)度便于物理實(shí)現(xiàn)，但使程序設(shè)計(jì)增加困難； 而消息長(zhǎng)度可變使程序設(shè)計(jì)變得簡(jiǎn)單，但使物理實(shí)現(xiàn)復(fù)雜化。(b)信箱通信（間接通信） 采用信箱通信（間接通信）方式時(shí)，進(jìn)程間發(fā)送或接收消息通過(guò)一個(gè)信箱來(lái)進(jìn)行，消息可以被理解成信件，每個(gè)信箱有一個(gè)唯一的標(biāo)識(shí)符。 當(dāng)兩個(gè)以上的進(jìn)程有一個(gè)共享的信箱時(shí)，它們就能進(jìn)行通信。(b)信箱通信（間接通信） 一個(gè)進(jìn)程也可以分別與多個(gè)進(jìn)程共享多個(gè)不同的信箱，這樣，一個(gè)進(jìn)程可以同時(shí)和多個(gè)進(jìn)程進(jìn)行通信。在間接通信方式“發(fā)送”和“接收”原語(yǔ)的形式如下： send（A，信件）：把一封信件（消息）傳送到信箱A。 receive（A，信件）：從信箱A接收一封信件（消息）。(b)信箱通信 信箱是存放信件的存儲(chǔ)區(qū)域，每個(gè)信箱可以分成信箱特征和信箱體兩部分: 信箱特征指出信箱容量、信件格式、指針等； 信箱體用來(lái)存放信件，信箱體分成若干個(gè)區(qū)，每個(gè)區(qū)可容納一封信。 信箱使用規(guī)則 若發(fā)送信件時(shí)信箱已滿，則發(fā)送進(jìn)程被置為“等信箱”狀態(tài)，直到信箱有空時(shí)才被釋放 若取信件時(shí)信箱中無(wú)信，則接收進(jìn)程被置為“等信件”狀態(tài)，直到有信件時(shí)才被釋放4.9 線程 1. 什么是線程(thread)-有時(shí)稱輕量級(jí)進(jìn)程(lightweight process LWP),是一個(gè)CPU調(diào)度單位,是進(jìn)程中的一個(gè)執(zhí)行路徑。 它由線程ID，程序計(jì)數(shù)器、寄存器集合和堆棧組成。 它與同屬于一個(gè)進(jìn)程的其它線程共享其代碼段、數(shù)據(jù)段和其它操作系統(tǒng)的資源（如打開(kāi)文件和信號(hào)）Single and Multithreaded ProcessesSingle Threaded and Multithreaded ModelsCombinations of Threads and Processes4.9 線程 線程可以這樣來(lái)描述： 進(jìn)程中的一條執(zhí)行路徑； 它有自己私用的堆棧和處理機(jī)執(zhí)行環(huán)境 它與父進(jìn)程共享分配給父進(jìn)程的主存； 它是單個(gè)進(jìn)程所創(chuàng)建的許多個(gè)同時(shí)存在的線程中的一個(gè)。4.9 線程