【正文】 if (readcount == 0) V(wsem)。 設(shè)想當一個讀者在使用數(shù)據(jù)庫時，另一個讀者也來訪問數(shù)據(jù)庫，由于同時允許多個讀者同時進行讀操作， 所 以第二個讀者也被允許進入，同理第三個及隨后更多的讀者都被允許進入。 semaphore mrc=l, mwc= 1, wr=1, wsem=1, rsem=l。 READ。, V(mwc)。 writecount++。 V(mrc)。 對于修改頻繁的問題，應采用寫者優(yōu)先算法。 中國最大的管理資源中心 54 } 其中： 變量 readcount 記錄當前正在訪問該對象的讀者個數(shù)； 互斥信號量 mutex 用來互斥對 readcount 的修改； 互斥信號量 wsem 用于寫者互斥， 它也可由當前第一個要求訪問該對象的讀者和最后一個退出訪問的讀者使用，但它不被中間的那些讀者使用。 P(mutex)。 所有類似的這類問題都可歸結(jié)為“讀者 — 寫者問題”。 PC. put(item)。 count++。 注意：在此模塊中無論是生產(chǎn)者還是消費者，關(guān)于 P 操作的次序不能顛倒，否則可能造成死鎖。 滿 j i 空 圖 11 生產(chǎn)者與消費者問題 下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費者關(guān)系的形式描述，設(shè)： ① 公用信號量 mutex：初值為 1，用于實現(xiàn)臨界區(qū)互斥； ② 生產(chǎn)者私用信號量 empty：初值為 n，指示空緩沖塊數(shù)目； ③ 消費者私用信號量， full初值為 0，指示滿緩沖塊數(shù)目； ④ 整型量 i和 j：初值均為 0， i指示空緩沖塊序號頭指針， j指示滿 緩沖塊序號頭指針。事實上，計算機 系統(tǒng)中的許多問題都可歸結(jié)為生產(chǎn)者與消費者問題，例如：對于需要輸出打印文件的某用戶進程和相對于打印機的管理進程，對各臨界資源的各種操作 中國最大的管理資源中心 50 該用戶進程是生產(chǎn)者，而后者便是消費者；同理，若該用戶進程需要讀入一個磁盤文件，相對于磁盤管理進程，該用戶進程是消費者，而磁盤管理進程則是生產(chǎn)者。為了實現(xiàn)對臨界資源的互斥訪問，管程每次只允許一個進程進入其內(nèi)（即訪問管程內(nèi)的某個過程），這是由編譯系統(tǒng)保證的。 1971 年 提出了秘書進程的概念 ，后經(jīng) Hansen 和 Hoare改變成管程并加以實現(xiàn)。當 P2進程執(zhí)行了 V(S1)操作后，P1進程才可向緩沖區(qū) B 輸入下一個數(shù)據(jù)。 信號量和 P/V操作是實現(xiàn)進程互斥與同步的非常有效的方法。 P/V操作由 P 操作原語和 V操作原語組成，其意義是在一個被稱之為信號燈變量的 S 上定義了兩個操作，該變量的值只能由 P 操作和 V操作進行修改。 ③ 釋放臨界資源，置 X 為 0（開鎖）。 同步機制 解決同步問題有若干種方法，有些方法既可以用作同步，也可以用作互斥。 while( flag[0]amp。 turn = 1。 flag[0] = false。 } 臨界區(qū) 中國最大的管理資源中心 44 turn = 1。如果 P2試圖使用與 P1 相同的資源，由于互斥機制，它將被拒絕訪問。 ? 非常簡單且易于證明。 while ( 1 ) { keyi = 1。 exchange指令定義如下： void exchange(int register, int memory) { int temp。如果 i為 0，則用 1取代并返回 true，這可以表示臨界資源未被使用時，進程占用臨界資源；如果 i為 1， i值不變，返回 false，這可以表示臨界資源已被使用時，進程不能再占用臨界資源。但該方法代價太高，因為 CPU被限制于只能交替執(zhí)行程序，執(zhí)行效率明顯降低。系統(tǒng)只能 讓它們按次序交替使用，而不能同時使用，即只有進程 A執(zhí)行完 CS1 程序段釋放了 V之后，才允許 B 進程執(zhí)行 CS2 程序段來使用 V，我們把公用變量 V 稱為臨界資源，把 CS1 和 CS2 這種必須互斥執(zhí)行的程序段稱為相對于臨界資源 V的臨界區(qū)。把因間接制約而導致交替執(zhí)行的過程稱為進程間的互斥。 4. 喚醒進程原語 當某進程所需要的資源出現(xiàn)時，由釋放資源的進程調(diào)用喚醒原語，喚醒等待該資源的進程。前三種由系統(tǒng)內(nèi)核直接調(diào)用創(chuàng)建原語創(chuàng)建新進程，后一種由用戶調(diào)用操作系統(tǒng)提供的系統(tǒng)調(diào)用完成創(chuàng)建任務，如 Linux中的 fork( )系統(tǒng)調(diào)用。 ?? 圖 8 進程家族結(jié)構(gòu)圖 在操作系統(tǒng)中，某些被進程調(diào)用的操作，例如隊列操作、對信號燈的操作、檢查啟動外設(shè)操作等，一旦開始執(zhí)行，就不能被中斷，否則就會出現(xiàn)操作錯誤，造成系統(tǒng)混亂。 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB8 PCB9 …… 執(zhí)行指針 就緒表指針 阻塞表指針 5 7 ?? 3 9 ?? 中國最大的管理資源中心 38 ④ 在進程調(diào)度中，系統(tǒng)進程的優(yōu)先級高于用戶進程。 ④ 進程具有獨立性。進程的動態(tài)性不僅表現(xiàn)在“程序的執(zhí)行”， 而且還表現(xiàn)在它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡的生命周期。按線性方式組織 PCB的情況如圖 5。這一部分指出資源需求、分配和控制信息。指出進程當前所處的狀態(tài)，作為進程調(diào)度、分配 CPU的依據(jù)。 掛起 時間片到 激活 掛起 釋放 激活 釋放 掛起 圖 4 具有掛起狀態(tài)的進程狀態(tài)變遷圖 在通常的操作系統(tǒng)中， PCB應包含如下一些信息： ① 進程標識信息。處于靜止就緒狀態(tài)的進程，若用激活原語激活后，該進程將轉(zhuǎn)變?yōu)榛顒泳途w狀態(tài)。 具有掛起狀態(tài) 的進程狀態(tài)轉(zhuǎn)換 在許多系統(tǒng)中，進程除了具有上述三種基本狀態(tài)以外，又增加了一些新狀態(tài)，其中最重要的是掛起狀態(tài)，引入掛起狀態(tài)的主要原因是內(nèi)存資源不足。被阻塞的進程在其被阻塞的原因獲得解除后，并不能立即投人運行，需要通過進程調(diào)度程序統(tǒng)一調(diào)度才能獲得 CPU，于是將其狀態(tài)由阻塞狀 態(tài)變成就緒狀態(tài)繼續(xù)等待 CPU。對于單 CPU 系統(tǒng)而言，因為處于就緒狀態(tài)的進程往往不止一個，同一時刻就緒 執(zhí)行 阻塞 中國最大的管理資源中心 34 只能有一個就緒進程獲得 CPU。處于該狀態(tài)的 進程不能參加競爭 CPU，因為此時即使分配給它 CPU，它也不能運行。 進程狀態(tài)及其轉(zhuǎn)換 1. 進程的三種基本狀態(tài)及其轉(zhuǎn)換 有了進程的概念，就可以用動態(tài)的觀點分析進程的狀態(tài)變化及相互制約關(guān)系。進程是現(xiàn)代操作系統(tǒng)中的一個最基本也是最重要的概念，掌握這個概念對于理解操作系統(tǒng)實質(zhì)，分析、設(shè)計操作系統(tǒng)都有其非常重要的意義。使用程序這一概念只能是簡單、孤立、靜止地研究分析它們，而不能深刻地揭示它們之間的內(nèi)在活動、相互聯(lián)系及狀態(tài)變化。這就是說，系統(tǒng)中各個并發(fā)程序活動具有獨立性的一面，但在兩個并發(fā)程序活動之間有時也會有相互依賴和相互制約關(guān)系。 程序的并發(fā)執(zhí)行所表現(xiàn)出的特性說明以下兩個問題： ⑴ 程序和計算機執(zhí)行程序的活動不再一一對應 程序和計算機執(zhí)行程序的活動是兩個概念，程序是指令的有序集合，是靜態(tài)的概念；而計算機執(zhí)行程序的活動是指令序列在 CPU 上的執(zhí)行過程，或 CPU 按照程序執(zhí)行指令序列的過程。此時我們可以寫出如下程序，其中 parbegin 表示多個程序可以并發(fā)執(zhí)行。在該例中 I1先于 Cl和 I2， Cl先于 Pl和 C2， Pl先于 P2， I2 先于 C2 和 I3，??。所謂可再現(xiàn)性是指當該程序重復執(zhí)行時，必將獲得相同的結(jié)果。 ② 獨占資源。例如，用戶要求計算機完成一道程序的運行時，通常先輸入用戶的程序和數(shù)據(jù)，然后運行程序進行計算，最后將結(jié)果打印出來 。我們目前使用的計算機幾乎都是單 CPU的機器，但是都能為我們同時完成幾件不同的工作，就是采用的CPU 分時原理。本章就來闡述有關(guān)進程的問題。在某一時段同時發(fā)生幾件事的現(xiàn)象稱為并發(fā)。程序的這兩種不同的執(zhí)行方式，體現(xiàn)出不同的特性。執(zhí)行順序如圖 1所示。程序的執(zhí)行結(jié)果與其執(zhí)行速度無關(guān)。硬件的并行操作技術(shù)為程序的并發(fā)執(zhí)行提供了物質(zhì)基礎(chǔ)。 多道程序的并發(fā)執(zhí)行大大地提高 了 系統(tǒng)的處理能力，改善了系統(tǒng)資源的利用效率。 } 由于觀察者和報告 者各自獨立地并行工作， n=n+1的操作，既可以在報告者的 print (n) 和 n=0操作之前，也可以在其后，還可以在 print (n) 和 n=0之間，即可能出現(xiàn)以下三種執(zhí)行序列： ① n=n+1； print(n) ； n=0； ② print(n) ； n=0 ； n=n+1； ③ print(n) ； n=n+1 ； n=0； 假設(shè)在開始某個循環(huán)之前， n 的值為 s，則在完成一個循環(huán)后，對上述三個執(zhí)行序列打印機打印的 n 值和執(zhí)行后的 n 值如下表所示： 表 1 執(zhí)行序列 ① ② ③ 打印的 值 s+1 s s 執(zhí)行后的值 0 1 0 由上表可見，由于觀察者和報告者的執(zhí)行速度不同，導致了計算結(jié)果的不同，這就是說，程序并發(fā)執(zhí)行已喪失了順序執(zhí)行所保持的封閉性和可再現(xiàn)性。例如在分時系統(tǒng)中，內(nèi)存中一個編譯程序的副本同時為幾個用戶作業(yè)編 中國最大的管理資源中心 32 譯時，該編譯程序的幾次執(zhí)行，便對應了幾個“計算”。例如，一個正在執(zhí)行的程序段需要另一程序段的計算結(jié)果，只有當另一程序段在某一時刻送來計算結(jié)果時，正在執(zhí)行的程序段才能繼續(xù)執(zhí)行下去，否則它就一直等待，無法執(zhí)行。為此，在操作系統(tǒng)中引入了“進程”的概念。 ③ 進程是這樣的計算部分，它可以與別的進程并發(fā)執(zhí)行（ Madniek and Donovan）。 ① 運行狀態(tài)。該進程運行所需的一切資源，除 CPU 以外，都得到滿足，但因 CPU個數(shù)少于進程個數(shù)，所以該進程不能運行，而必須等待分配 CPU資源，一旦 獲得 CPU 就立即投入運行。 ② 運行→阻塞。 ④ 運行 →就緒。可有以下幾種情況： ① 活動就緒→靜止就緒。 具有掛起狀態(tài)的進程狀態(tài)變遷過程如圖 4。有的系統(tǒng)用進程標識名作為進程的外部標識，它通常由創(chuàng)建者給出；用進程標識數(shù)作為進程的內(nèi)部標識，通常由系統(tǒng)給出。進程調(diào)度程序根據(jù)優(yōu)先數(shù)的大小，確定優(yōu)先級的高低，并把 CPU控制權(quán)交給優(yōu)先級最高的進程。 ⑧ 其它信息。 ③ 索引表方式：系統(tǒng)按照進程的狀態(tài)分別建立就緒索引表、阻塞索引表等，通過索引表來管理系統(tǒng)中的進程。多個進程實體同存于內(nèi)存中，在一段時間內(nèi)可以同時運行。系統(tǒng)中的進程，按照各自的、不可預知的速度向前推進。進程控制的職能是對系統(tǒng)中的全 部進程實行有效的管理，其主要是對一個進程進行創(chuàng)建、撤銷以及在某些進程狀態(tài)間的轉(zhuǎn)換控制。原語一旦開始執(zhí)行，就要連續(xù)執(zhí)行完，中間不允許中斷。 撤銷原語撤銷的是標志進程存在的進程控制塊 PCB，而不是進程的程序段。 3 進程互斥與同步 并發(fā)執(zhí)行的多個進程，是在異步環(huán)境下運行的 ，每個進程都以各自獨立的、不可預知的速度向前推進。因此必須保護這些資源，避免兩個或多個進程同時訪問這類資源。因此，使用臨界資源的代碼結(jié)構(gòu) 為： 進入?yún)^(qū) 臨界區(qū) 退出區(qū) 有了臨界資源和臨界區(qū)的概念，進程間的互斥可以描述為禁止兩個或兩個以上的進程同時進入訪問同一臨界資源的臨界區(qū)。如 testset指令和 exchange指令。