進程和處理機管理課件

1、第3章 進程和處理機管理 目錄 31 進程的概念和定義 32 進程的狀態(tài)和進程控制塊 3. 3 進程控制 34 進程的互斥與同步 3. 5 進程通信 36 進程調(diào)度 37 死鎖 38 線程31 進程的概念和定義 操作系統(tǒng)是一個動態(tài)系統(tǒng)，在持續(xù)的運動過程中完成各種使命、實現(xiàn)各項功能。因此，要了解操作系統(tǒng)各模塊間的動態(tài)連接關(guān)系和相互制約關(guān)系就不能用靜態(tài)的程序概念來刻畫操作系統(tǒng)。因此引進一個新的觀點進程觀點，以便鉆進操作系統(tǒng)內(nèi)部去觀察操作系統(tǒng)各模塊的動態(tài)變化情況。 311 為什么引入進程312 進程的定義311 為什么引入進程應該說，組織用戶使用計算機的機制是隨著計算機操作系統(tǒng)的發(fā)展而進化的。在監(jiān)督

2、程序時代是以作業(yè)形勢表示程序運行的。那時，作業(yè)以同步方式串行地運行每個作業(yè)步。當操作系統(tǒng)發(fā)展到分時系統(tǒng)時，為了開發(fā)同一個作業(yè)中不同作業(yè)步之間的并發(fā)，作業(yè)機制已不能滿足需要，因而引進了進程機制，讓進程來實現(xiàn)作業(yè)步的執(zhí)行。但隨著多處理機計算機的出現(xiàn)，用戶希望一個作業(yè)步中的程序還能夠同時在多個處理機上運行，因此進程的機制得到了進一步發(fā)展，讓一個進程同時擁有多個線程，讓多個線程在不同處理機上運行。 1. 算法我們可以把算法定義為：問題求解步驟的精確描述。算法具有如下性質(zhì)：解題算法是一個有窮動作序列；動作序列僅有一個初始動作；序列中每一個動作僅有一個后繼動作；序列終止表示問題解決還是沒有得到解決。2.

3、程序程序是對一個復雜的計算（問題）用一種形式化的語言對其初始數(shù)據(jù)與操作進行形式化描述的一個算法。 當一個程序在運行之際，可以區(qū)分出三個不同的實體。(1) 用來描述過程的一組指令，即“過程”；(2) 處理機，即執(zhí)行該過程的機構(gòu)；(3) 環(huán)境，即處理機能夠直接感知或能夠加以改造的那個外部世界?！耙磺新爮某绦虻闹笓]”。2. 程序因此,程序的主要特點是：(1) 按“過程”所規(guī)定的操作，以嚴格順序來執(zhí)行，每一步都應在下一步開始之前完成（不存在并行）。這一特點就是我們所說的程序的順序性。(2) 環(huán)境處在“程序”的完全控制之下，它決不以任何方式變化，除非這種變化是程序所采取的步驟導致的結(jié)果。這個特點被稱為程

4、序的封閉性。(3) 除了要求在合理的時間內(nèi)獲得結(jié)果外，任一操作所花費的時間對程序的運行而言是無關(guān)緊要的，即使在任一操作之間有一暫時間歇也沒有關(guān)系。程序所產(chǎn)生的結(jié)果是其輸入數(shù)據(jù)的函數(shù)而與時間無關(guān)。只要程序執(zhí)行的初始條件相同，其結(jié)果是可以再現(xiàn)的 。3. 程序的并行執(zhí)行和資源的共享為了合理地使用系統(tǒng)資源，充分發(fā)揮各種資源的作用，最大限度地提高系統(tǒng)的效率，引進多道程序設(shè)計技術(shù)。又由于計算機技術(shù)的不斷發(fā)展而出現(xiàn)了中斷技術(shù)、分時處理和各種新型結(jié)構(gòu)，如多CPU系統(tǒng)的出現(xiàn)，導致現(xiàn)代操作系統(tǒng)出現(xiàn)了許多諸如并發(fā)性、資源共享性等許多新的特征。（1）并行操作 （2）資源共享4. 程序并行執(zhí)行的特征程序的并行執(zhí)行雖然增

5、加了系統(tǒng)的處理能力和機器的利用率，但也產(chǎn)生了與順序程序不同的新特征。（1）失去了程序的封閉性（2）程序并行執(zhí)行時的相互制約關(guān)系312 進程的定義通過上述分析可知，程序在并行執(zhí)行時已不能描述不封閉性和“執(zhí)行-暫停-執(zhí)行”活動規(guī)律，需要有一種新的概念工具來描述下列特征： 能描述“計算”這一現(xiàn)象；能描述“執(zhí)行-暫停-再執(zhí)行”這一活動規(guī)律；能為并行執(zhí)行的“計算”的制約關(guān)系提供協(xié)調(diào)和共享資源的機構(gòu)。這樣的新概念稱為進程或任務。 2. 進程與程序的主要區(qū)別(1) 程序只是指令的有序集合，是靜態(tài)的描述，沒有運行的含義，所以程序是靜止的；進程是程序的一次運行活動，是動態(tài)的概念。(2) 進程是一個獨立運行的單位

6、，共享資源的實體，能與其他進程并發(fā)執(zhí)行，而程序則不然。操作系統(tǒng)中以資源管理的中心思想來看，進程可以看成是資源的顧客和使用者。(3) 一個程序可以對應多個進程，反過來，一個進程至少對應一段程序。邏輯上，每個進程有自己的處理機和程序，實際上兩個進程可以共享同一段程序或同一個處理機，所以進程不等價于程序，也不等價于處理機，它是執(zhí)行期間的對。(4) 靜態(tài)地觀察進程，其實體是由程序和數(shù)據(jù)兩部分構(gòu)成，與程序沒有什么區(qū)別。3. 進程的特征進程具有如下的特征：（1）動態(tài)特征進程的實質(zhì)是并行程序的一次執(zhí)行過程，因此，動態(tài)特征是進程的最基本的特征。其動態(tài)性表現(xiàn)在它可以由創(chuàng)建而產(chǎn)生、由調(diào)度而執(zhí)行、由于得不到資源而暫

7、停，由撤消而消亡。進程存在一個生命周期。（2）并行特征引入進程的目的是使程序能并行執(zhí)行，以提高資源的利用率。（3）獨立特征進程是獨立運行的單位，也是系統(tǒng)進行資源分配和調(diào)度的獨立單位。（4）異步特征進程按照各自獨立的，不可預知的速度向前推進，所以要求系統(tǒng)提供某種設(shè)施使進程間能協(xié)調(diào)操作和共享資源，保證它們協(xié)調(diào)運行。（5）結(jié)構(gòu)特征進程是有結(jié)構(gòu)的，體現(xiàn)在每個進程有一個記錄進程當前信息的進程控制塊（PCB Process Control Block）。每個進程都是由一個程序段和相應數(shù)據(jù)集以及進程控制塊三部分組成。在UNIX操作系統(tǒng)中將這三部分稱為“進程映象”，它把進程定義為：進程映象的執(zhí)行。引入進程這一

8、概念后，就可以很方便地動態(tài)地描述操作系統(tǒng)了，但引入進程也有不利之處：(1) 必須為設(shè)置進程付出一定的空間開銷，因為并行執(zhí)行的操作系統(tǒng)本身就復雜，如，必須設(shè)置進程管理并為并行執(zhí)行的各進程之間的同步和協(xié)調(diào)建立某些機構(gòu)，由于并行執(zhí)行就必須考慮避免死鎖等問題而使系統(tǒng)復雜化。另外，每個進程都必須有一個進程控制塊（PCB），它也占用了一部分內(nèi)存空間。(2) 必須為設(shè)置進程付出一定的時間開銷，因為運行一個復雜的系統(tǒng)軟件將花費更多的處理機時間。32 進程的狀態(tài)和進程控制塊321 進程的狀態(tài)進程是動態(tài)的，它存在著生命周期。它有誕生（創(chuàng)建）和滅亡（撤消）過程，在它的生命周期中又反映出它的執(zhí)行-暫停-再執(zhí)行的活動規(guī)

9、律，進程最主要的特征是具有狀態(tài)。進程在其活動期間具有兩種狀態(tài)：自由狀態(tài)和等待狀態(tài)。任一進程在任一時刻有且只有這兩種狀態(tài)之一。自由狀態(tài)又可分為：運行狀態(tài)和就緒狀態(tài)。321 進程的狀態(tài)就緒狀態(tài)（Ready） 該進程已經(jīng)獲得了除了處理機以外的全部資源并準備好運行，但由于進程數(shù)多于處理機數(shù)目，所以此進程不能占用處理機執(zhí)行，一旦為其分配到處理機該進程便立即執(zhí)行。 321 進程的狀態(tài)執(zhí)行狀態(tài)（Executive） 進程獲得了處理機等必要的資源，該進程已占用處理機，其程序正在處理機上執(zhí)行。321 進程的狀態(tài)阻塞狀態(tài)（Block） 正在執(zhí)行中的進程，由于發(fā)生了某一事件而使之暫時無法執(zhí)行下去（如，等待I/O操作

10、完成，或由于同步、互斥而等待）而處于暫停狀態(tài)，即該進程的運行受到了阻塞（即等待狀態(tài)或睡眠狀態(tài)）。 進程的三種不同狀態(tài) 就 緒阻 塞執(zhí) 行 進程的狀態(tài)322 進程的狀態(tài)演變進程的狀態(tài)不是一成不變的，它是隨著自身的推進和外界條件的變化而變化的。下圖為簡單的進程狀態(tài)演變圖及演變事由。進程調(diào)度執(zhí) 行就 緒阻 塞事件結(jié)束時間片到圖3-5 簡單的進程狀態(tài)演變圖應該說明的是:（1）在進程的生命周期中，處于執(zhí)行狀態(tài)的進程因為某一事件（如I/O請求等事件）出現(xiàn)而變成阻塞狀態(tài)，當該事件消除后，被阻塞的進程并不恢復到執(zhí)行狀態(tài)，而轉(zhuǎn)變?yōu)榫途w狀態(tài)等待再一次重新被進程調(diào)度程序調(diào)度。這是因為當該進程被阻塞時，為了使處理機不

11、空閑，進程調(diào)度程序立即將處理機分配給另一個處于就緒狀態(tài)的進程。（2）當進程從運行狀態(tài)變?yōu)榫途w或阻塞狀態(tài)時，必須保留它的運行的現(xiàn)場信息，以便將來恢復運行。（3）處于同一狀態(tài)的進程可以構(gòu)成隊列，系統(tǒng)中可以有一個運行隊列、但是在只有一個處理機的情況下，任一時刻處于運行狀態(tài)的進程只能有一個。系統(tǒng)中可以有一個或多個就緒隊列和若干個等待隊列，由于同一個原因而等待的進程應該屬于同一個等待隊列，相應每個隊列設(shè)有指針，指向相應隊列的首部。相應隊列指針名稱狀態(tài)現(xiàn)場優(yōu)先數(shù)指針Proc2Run870Proc3Block785Proc4Block750Proc5Block650Proc6Ready518Proc7Blo

12、ck449Proc8Ready37nProc9Block290ProcnReady1026137runningreadyC1C2C3CmProc1Block894 進程隊列 時間片到進程調(diào)度事件結(jié)束某一事件用戶提交收容就緒阻塞完成用戶執(zhí)行進程狀態(tài)模型進程調(diào)度發(fā)生某一事件時間片到掛起喚醒執(zhí) 行活動就緒靜止就緒活動阻塞激活掛起喚醒激活掛起靜止阻塞創(chuàng)建具有掛起狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖323 進程控制塊（Process control block）在進程的生命周期中，進程可以處于各種不同的狀態(tài)，如何描述進程及其狀態(tài)？進程控制塊是表示進程存在的唯一實體。當創(chuàng)建一個進程時，必須為其設(shè)置一個進程控制塊（PCB）

13、，由它對進程進行管理和控制。不同系統(tǒng)的進程控制塊所包含的信息不盡相同，大體上都包括以下幾項：（1）進程標識符（Identification）（2）現(xiàn)行狀態(tài)（Status）（3）CPU狀態(tài)保護區(qū)（4）進程程序的起始地址（5）資源清單（6）進程優(yōu)先數(shù)（7）隊列指針或隊列表（8）進程的家族信息3. 3 進程控制 進程控制的功能是對系統(tǒng)中的全部進程實施有效的管理，它有創(chuàng)建進程和撤消進程的能力。 1 . 進程家族與分類 2 . 進程控制的基本操作331 進程家族與分類1. 進程家族進程的家族結(jié)構(gòu)有兩種：一種是非結(jié)構(gòu)系統(tǒng)；另一種是樹型結(jié)構(gòu)系統(tǒng) 。在非結(jié)構(gòu)系統(tǒng)中管理程序直接對全部進程實施管理，它可以實施創(chuàng)建

14、進程和撤消進程等操作。各進程之間的關(guān)系也是“平等”的。 在樹型結(jié)構(gòu)的進程家族中，一個父進程可以創(chuàng)建一個子進程而形成一個進程家族。如圖3-9（a）給出了非結(jié)構(gòu)系統(tǒng)進程家族示意圖;圖3-9（b）給出了樹型結(jié)構(gòu)的進程家族的示意圖。進程A進程n進程B管理程序(a)ABCDEFHGIJK(b) 進程家族的結(jié)構(gòu)1. 進程家族進程的家族結(jié)構(gòu)有兩種：一種是非結(jié)構(gòu)系統(tǒng)；另一種是樹型結(jié)構(gòu)系統(tǒng)。在非結(jié)構(gòu)系統(tǒng)中管理程序直接對全部進程實施管理，它可以實施創(chuàng)建進程和撤消進程等操作。各進程之間的關(guān)系也是“平等”的，如圖3-9（a）所示。在樹型結(jié)構(gòu)的進程家族中，一個父進程可以創(chuàng)建一個子進程而形成一個進程家族。圖3-9（b）給

15、出了樹型結(jié)構(gòu)的進程家族的示意圖。1. 進程家族進程A進程n進程B管理程序(a)ABCDEFBHGIJK(b)圖3-9 進程家族的結(jié)構(gòu)1. 進程家族樹型結(jié)構(gòu)的優(yōu)點是：（1）資源分配嚴格，子進程可以分配到父進程所擁有的資源，用完后立即歸還，一個進程家族所占有的全部資源應該在其祖先所擁有的資源范圍內(nèi)。（2）進程的控制靈活，當一個進程被分配完成某一任務時，它能夠創(chuàng)建若干進程去分別完成各子功能。（3）進程層次清晰，關(guān)系明確。所以，樹型結(jié)構(gòu)的系統(tǒng)獲得了廣泛應用。 2進程分類進程按服務對象可分為：系統(tǒng)進程與用戶進程。完成指定的系統(tǒng)功能的進程稱為系統(tǒng)進程；完成用戶作業(yè)所需做的工作的進程稱為用戶進程，如，編譯、

16、運行系統(tǒng)等。系統(tǒng)進程按其占內(nèi)存的情況又可分為：長存進程和暫存進程兩大類，長存進程的數(shù)據(jù)塊、程序塊等長期駐留在內(nèi)存；暫存進程的程序塊等不是長期駐留在內(nèi)存中，需要時才把它們調(diào)入內(nèi)存。332 進程控制的基本操作為了對進程進行控制和通信，在系統(tǒng)中必須設(shè)置一個機構(gòu)，它具有創(chuàng)建、撤消、進程通信和資源管理等功能，這樣的機構(gòu)稱為操作系統(tǒng)的內(nèi)核（Kernel），系統(tǒng)的其他部分是由它們建造的。內(nèi)核本身并非一個進程，而是一組基本原語操作，是由軟件實現(xiàn)的內(nèi)核功能，內(nèi)核通過執(zhí)行各種原語操作來實現(xiàn)各種控制和管理功能。內(nèi)核是硬件的首次延伸，它擴大了CPU的功能。原語是機器指令的延伸，是由若干條機器指令構(gòu)成的用以完成特定功能

17、的一段程序，為了保證操作的正確性，原語在執(zhí)行期間是不可分割的。引入原語的目的是允許進程內(nèi)部并行操作，且可以動態(tài)地創(chuàng)建一個進程；允許系統(tǒng)生成許多不同的版本以適應不同用戶的需要，系統(tǒng)執(zhí)行時靈活組裝成不同的操作系統(tǒng)；使系統(tǒng)結(jié)構(gòu)清晰。用于對進程進行管理和控制操作的基本原語有：創(chuàng)建原語(Create)撤消原語（Destroy）以上兩個原語使進程從無到有，從有到無。喚醒原語（Wakeup）阻塞原語（Block）以上兩個原語使進程發(fā)生各種狀態(tài)變化。掛起原語（Suspend）激活原語 （Action)以上兩個原語使進程從活動到靜止,從靜止到活動。34 進程的互斥與同步 進程的狀態(tài)是基于一定的原因和條件而變化的

18、，而這些原因和條件又常常是由于進程之間的相互制約關(guān)系而引起的。系統(tǒng)中諸進程之所以有這種關(guān)系，主要原因是由于進程對資源的共享性，由于這種共享的特征，使系統(tǒng)中本來沒有邏輯關(guān)系的進程因為互相競爭資源而產(chǎn)生了制約關(guān)系。這種關(guān)系的基本形式是：“進程資源進程”，這是進程間通過資源而發(fā)生的一種間接關(guān)系。由于系統(tǒng)對進程所請求的許多資源常常是互斥滿足的，所以這種關(guān)系表現(xiàn)為互斥關(guān)系（競爭關(guān)系）。 系統(tǒng)中為了完成同一個任務而創(chuàng)建了若干進程，它們之間必然是伙伴進程（進程合作），如某作業(yè)的一組并行進程共同完成一項任務，有時它們要在某點上互相等待和互通消息，這種關(guān)系的基本形式是：“進程進程”，這是進程之間的一種直接關(guān)系，

19、表現(xiàn)了進程之間的協(xié)同工作的特性，稱為進程間的同步關(guān)系。 341 臨界區(qū)（Critical section）計算機中的某些資源是共享資源，但是有些共享資源具有如下特征：即一次僅允許一個進程使用，我們把一次僅允許一個進程使用的資源稱為“臨界資源”（Critical resource）。例如，有兩個進程A，B共享一臺打印機，若讓它們?nèi)我馐褂?，則可能將兩個進程的輸出結(jié)果交織在一起，很難區(qū)分。為了解決這一問題，可以在A進程使用打印機時先申請，一旦系統(tǒng)將打印機分配給A進程后就由它一直占用，此時若B進程也要使用打印機就必須等待，直到A進程用完釋放打印機后B進程方可使用，即它們必須互斥地使用打印機。這里打印機

20、就是一種臨界資源。訪問臨界資源的那段程序稱之為“臨界區(qū)”。為了使臨界資源互斥地被使用，必須使臨界區(qū)互斥地被執(zhí)行，即諸進程訪問臨界區(qū)時必須互斥。為了做到禁止一組進程同時訪問它們的臨界區(qū)，而提出了臨界區(qū)的準則如下：（1）不能假設(shè)各并發(fā)進程的相對執(zhí)行速度，即各并發(fā)進程享有平等的、獨立的競爭共有資源的權(quán)利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時，其他并發(fā)進程可以進入臨界區(qū)。（2）當有若干進程欲訪問它們的臨界區(qū)時，應在有限時間內(nèi)使一個進程訪問臨界區(qū)，不應互相阻塞而彼此都無法訪問，這就是有空讓進的原則，使共享資源能夠充分利用。（3）每次至多有一個進程處于臨界區(qū)內(nèi)，這體現(xiàn)了互斥的基本含義。（4

21、）進程僅在臨界區(qū)內(nèi)逗留有限時間，使等待訪問臨界區(qū)的進程是有限等待 。由上述準則得臨界區(qū)的調(diào)度原則如下：（1）當無進程訪問臨界區(qū)時，允許一個進程立即訪問其臨界區(qū)。（2）當某一進程已訪問了它的臨界區(qū)時，其他試圖訪問臨界區(qū)的進程必須等待。（3）當某一進程離開臨界區(qū)時，若有等待訪問臨界區(qū)的進程，則允許其中的一個進程進入臨界區(qū)訪問。342 進程互斥1. 互斥的加鎖實現(xiàn)這是一種借助一條硬指令Test和Set來實現(xiàn)互斥的一種同步機構(gòu)。此方法是對臨界區(qū)加鎖以實現(xiàn)互斥。當某個進程進入臨界區(qū)之后，為了阻止其他進程進入臨界區(qū)，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。并發(fā)進程在申請進入臨界區(qū)時，首先測試該臨界區(qū)是否是

22、上鎖的。如果該臨界區(qū)已被鎖住，則該進程要等到該臨界區(qū)開鎖之后才有可能進入臨界區(qū)。為此設(shè)置一個變量W，代表臨界區(qū)的狀態(tài)，W也稱為鎖或鎖位。當W=0時，表示臨界區(qū)可以進入；當W=1時，表示臨界區(qū)已被占用，企圖進入臨界區(qū)的進程必須等待。 關(guān)鎖原語Lock w:關(guān)鎖原語 l:if w =1 then goto l else w:=1；開鎖原語開鎖原語 unlock w: w:=0下面的程序表示了兩個并行的循環(huán)進程用關(guān)鎖和開鎖原語實現(xiàn)互斥的情況( CS1和CS2表示兩個進程的各自臨界區(qū))。Begin integer w; W:=0;Cobegin process1 Begin L1:lock w; CS

23、1; Unlock; Program1; Goto L1; End Process2 Begin L2: lock w; CS2; Unlock; Program2; Goto L2; EndCoendEnd這樣的一個同步機構(gòu)能有效地保證進程互斥地訪問臨界區(qū)，但對于不能進入臨界區(qū)的進程卻在不斷地測試鎖位W，以等待它為零，這就造成了處理機時間的浪費。改進的方法是將忙式等待改成忙式掛起，當某進程所需臨界資源被占用時，應使該進程阻塞，把它插入到等待隊列中，此時CPU分配給其他進程，一旦該資源被釋放就立即檢查等待隊列，若等待隊列空，則開鎖表示資源可以使用；若等待隊列不空，則從該等待隊列中移出一個進程，

24、將其置于就緒狀態(tài)并插入就緒隊列。修改后的關(guān)鎖和開鎖原語如下： 關(guān)鎖原語Lock w: if w =1 then 測試W的值 Begin Block(n); insert(wl,n);scheduler 若臨界區(qū)中有進程，則阻塞自己并插入到等待隊列中，此時CPU空閑，引起進程調(diào)度。 End Else w:=1; 若臨界區(qū)中無進程，則關(guān)鎖表示占用開鎖原語 臨界區(qū)；Unlock w: if wlnull then 若等待隊列不空，則 Begin Remove(wl,q); 從等待隊列中移出q， Status(q):=ready; 將進程q置于就緒狀態(tài)， Insert(rl,q); 將其插入就緒隊列。

25、 End W:=0; 開鎖。2信號量和P,V操作荷蘭計算機科學家E.W.Dijkstra于1965年提出了信號量的概念，并引入兩個新的原語操作P和V（P和V分別是荷蘭語Passeren和Verhoog的第一個字母，相當于英文的Pass和Increment的意思）。采用P,V操作原語，大大簡化了進程的同步和互斥的實現(xiàn)。P和V這兩個原語操作在非負整形變量上，這些變量稱為信號量。 信號量是表示資源的物理實體，是一個與隊列有關(guān)的整形變量，其值僅能由P和V操作來改變。操作系統(tǒng)利用它的狀態(tài)對進程和資源進行管理。按信號量的用途不同可將其分為： 公用信號量。 它聯(lián)系著一組并行進程，初始值為1，每個進程都可以對

26、它施加P或V操作，通常它是為實現(xiàn)進程的互斥而設(shè)置。 私用信號量。 它聯(lián)系著一組共行進程，初始值為0或某個正整數(shù)n，僅允許擁有它的進程對它施加P操作，通常用來實現(xiàn)進程的同步。P操作P操作記為P(S),其中S為一個信號量的值， 每執(zhí)行一次P操作，就意味著申請一個單位的資源，由于信號量的值用來表示資源數(shù)量，所以執(zhí)行一次P操作，信號量的值就減1。此時若S0，則進程繼續(xù)執(zhí)行；若S0則阻塞該進程，并將其插入到該信號量的等待隊列中等待。 Procedure P(S)Begin Lock out interrupts; 關(guān)中斷； S:=S-1; 信號量的值減1； If S0 then begin 如果s0，說

27、明已經(jīng)沒有此類資源，故進程 Status(q):=block; q的申請得不到滿足，將其阻塞； Insert(Q,q); 將q插入到該資源的等待隊列中；否則繼續(xù) Unlock interrupts; 開中斷；End;請讀者注意，程序中為什么判斷S0則進程繼續(xù)執(zhí)行；若S0則從信號量的等待隊列中移出一個進程并賦予該進程為就緒狀態(tài)，將其插入到就緒隊列中。 Procedure V(S)Begin Lock out interrupts; 關(guān)中斷； S:=S+1; 信號量的值加1； If S0 then begin 如果S0，說明有等待該資源的進程；Remove(Q,r); 則將該進程從等待隊列中移出；

28、Status:=ready; 并將其狀態(tài)改為就緒；Insert(RL,r); end; 插入到就緒隊列； Unlock interrupts; 開中斷； End;也請讀者仔細分析一下，在V操作中為什么判斷S0，而不是S0？信號量的特征為： 信號量的值一般表示單位資源的數(shù)量，若S0時其絕對值表示該資源上等待的進程數(shù)目。 一個信號量的初始值不能置為負，但在執(zhí)行n次P操作后它可以變?yōu)樨撝?，此時表示系統(tǒng)中已沒有這類資源，因此，請求該資源的進程將被阻塞，將其排在該信號量的等待隊列上，此時信號量S的絕對值等于該信號量隊列上的進程數(shù)目。 信號量的值=信號量的初始值-P操作的次數(shù)+V操作的次數(shù)。 執(zhí)行V操作就

29、意味著釋放一個單位的資源，若S0則表示信號量請求隊列中仍有請求該資源而被阻塞的進程，因此，應將該隊列的第一個進程喚醒，使之狀態(tài)轉(zhuǎn)換為就緒。利用信號量實現(xiàn)進程互斥首先討論兩個循環(huán)執(zhí)行的進程P1和P2，在它們都要訪問它們的臨界區(qū)時如何做到互斥。為使這兩個進程能夠做到互斥地訪問臨界區(qū)，寫出如下的算法程序。其中S為公用信號量，其初始值為1。 Begin Cobegin P1: begin L1:P(S)CS1;V(S);Program1;Goto L1EndP2:begin L2:p(S); CS2; V(S); Program2; Goto L2 EndCoend End上述例子中對于這兩個進程而言

30、，信號量的取值僅有1，0，-1 這3個值。當S=1時，表示臨界區(qū)中無進程；當S=0時，表示臨界區(qū)中有一個進程；當S=-1時，表示有一個進程進入了臨界區(qū)，另一個進程等待進入而阻塞。343 進程的同步1. 進程同步的概念同步是指進程執(zhí)行在時間上的先后次序的限制條件。系統(tǒng)中的諸進程共同完成一個任務，它們相互合作，協(xié)調(diào)運行，有時在它們之間還需要交換信息。因此有的進程必須等待另一個進程發(fā)來消息后才能繼續(xù)執(zhí)行，它們在某點上要互相等待。 緩沖區(qū)(臨界資源)取數(shù)據(jù)送數(shù)據(jù)發(fā)信號給打印進程發(fā)信號給計算進程計算進程打印進程 計算進程與打印進程通過單緩沖區(qū)協(xié)同工作 生產(chǎn)者與消費者問題一個作為生產(chǎn)者的進程生產(chǎn)消息，然后

31、把它放入共享的緩沖區(qū)中。相應地，一個消費者進程從緩沖區(qū)中取走消息進行處理。假設(shè)該緩沖區(qū)可以存放n個大小相等的消息（即由n個緩沖器組成，每個緩沖器中存放一個消息）。如下圖所示 ： 生產(chǎn)者和消費者利用n個緩沖器工作的情況n個緩沖區(qū)生產(chǎn)者消費者生產(chǎn)者P(empty)P(mutex)P(mutex)P(full)V(full)V(mutex)V(mutex)V(empty)生產(chǎn)者和消費者的同步規(guī)則如下：生產(chǎn)者企圖將一個消息放入已滿的緩沖區(qū)時要等消費者取走一個消息之后；消費者企圖從空的緩沖器中取走消息時，要等生產(chǎn)者放入一個之后。為此，設(shè)置兩個私用信號量empty 和full，用于進程之間的同步。其中，e

32、mpty信號量表示可用的空緩沖器的數(shù)目，初始值為n，full信號量表示消息數(shù)目，初始值為0。緩沖器是共享的臨界資源，要求兩個進程互斥地對其操作，故設(shè)置一個公用信號量mutex，初始值為1（表示沒有進程進入臨界區(qū)），它用于實現(xiàn)進程互斥。生產(chǎn)者與消費者對于n個緩沖器的互斥與同步問題的描述如下： begin semaphore mutex,empty,full; mutex:=1;empty:=n;full:=0; cobegin producer:begin L1:produce next message; P(empty); P(mutex); Add to buffer; V(mutex);

33、V(full); Goto L1; End; Consumer:beginL2:P(full); P(mutex); Take from buffer; V(mutex); V(empty); Consume product; Goto L2; End; Coend;如果將生產(chǎn)者進程或消費者進程中的P(empty)和P(mutex)或P(full)和P(mutex)的次序顛倒，會造成死鎖而使兩個進程都無法執(zhí)行。這是因為若生產(chǎn)者（消費者）進程先執(zhí)行P(mutex)操作，就意味著它將申請臨界區(qū)資源，如果它不阻塞可以繼續(xù)執(zhí)行,當執(zhí)行到P(empty)（或P(full)）而阻塞時，必須啟動另外一個進程

34、執(zhí)行，另一個進程當執(zhí)行到P(mutex)時，也會因為臨界區(qū)的互斥而阻塞，從而導致兩個進程都無法執(zhí)行下去，故產(chǎn)生死鎖。請讀者分析一下V操作的次序可否顛倒。實際使用的是將n個緩沖器構(gòu)成一個環(huán)形緩沖區(qū)，如圖3-13所示。工作時只要不是生產(chǎn)者進程的速度過快，以至于使緩沖區(qū)全滿，或者消費者進程執(zhí)行的速度過快而使緩沖區(qū)全空，那么緩沖區(qū)的容量將是無限大的。它將使緩沖區(qū)由有界變?yōu)闊o界。圖3-13 環(huán)形緩沖區(qū)生產(chǎn)者(往空緩沖區(qū)中送消息)消費者(從滿緩沖區(qū)中取消息)。圖3-13 環(huán)形緩沖區(qū)生產(chǎn)者(往空緩沖區(qū)中送消息)消費者(從滿緩沖區(qū)中取消息)3. 5 進程通信 進程之間的信息交換稱為進程通信。進程之間的所有通信

35、情況都歸結(jié)為互斥和同步兩類，而嚴格說來，互斥也是一種同步，是一種很特殊的同步，前面已經(jīng)討論過。同步又可以分為信號同步和信件同步兩種。信號同步：發(fā)送者只給對方發(fā)送一簡單信號（同步的雙方互相明白該信號的寓意）。信件同步：發(fā)送者給對方發(fā)送一復雜信件。例如，用戶進程要輸出結(jié)果時，請求輸出進程為它服務，用戶進程將要輸出的信息在內(nèi)存中的頭地址、輸出信息的個數(shù)、輸出格式以及在哪一臺設(shè)備上輸出等信息作為一個信件發(fā)送給輸出進程，輸出進程在尚未收到信件之前暫停執(zhí)行，收到信件后，分析信件并按要求完成輸出工作。交通控制程序提供了專門的機構(gòu)來實現(xiàn)進程通信，這種機構(gòu)通常叫做通信原語 。通信原語通常分為低級通信原語和高級通

36、信原語兩類。低級通信原語如關(guān)鎖與開鎖原語以及上一節(jié)所介紹的PV操作原語等。它們只能完成簡單的信號傳遞，通信的效率低。高級通信原語如消息緩沖或信箱等通信手段完成的通信，這些通信方法是以較高的效率傳遞大批信息。351 消息緩沖（message buffer） Hansen于1973年首先提出用消息緩沖作為進程通信的基本手段，并在RC 4000系統(tǒng)中實現(xiàn)了。 消息緩沖是進程之間的高級通信工具，它實現(xiàn)了以較高的效率在進程之間傳遞大批數(shù)據(jù)的的直接通信方式。為了實現(xiàn)這種通信方式，系統(tǒng)必須提供相應的原語。如發(fā)送消息（send）原語和讀取消息（read）原語。所謂消息就是一組信息。消息緩沖區(qū)是包含如下信息的緩

37、沖區(qū)： （1）指向發(fā)送進程的指針Sptr；（2）指向下一個消息緩沖區(qū)的指針Nptr；（3）消息長度Size；（4）消息正文Text。 352 信箱（mailbox）信箱是用以存放信件的。利用信箱通信就是由發(fā)送進程申請建立一個與接收進程鏈接的信箱，然后發(fā)送進程將欲發(fā)送的消息送往信箱中，接收進程從信箱中取出消息，從而完成進程之間的信息交換。設(shè)置信箱的最大好處就是發(fā)送進程和接收進程之間沒有處理時間上的限制。一個信箱可以看作是發(fā)送進程和接收進程之間的大小固定的私有數(shù)據(jù)結(jié)構(gòu)，它不像消息緩沖區(qū)那樣被系統(tǒng)內(nèi)所有的進程所共享。信箱邏輯上可以分成兩部分，即有關(guān)信箱描述的信箱頭和由若干個格子組成的信箱體，其中每個

38、格子可以存放一個信件。格子的數(shù)目和每個格子的大小由創(chuàng)建信箱時確定。 36 進程調(diào)度 進程調(diào)度是本章中敘述的核心層中原語調(diào) 用的一個例行程序。在多道程序系統(tǒng)中， 用戶進程數(shù)往往多于處理機數(shù)目從而導致 多個進程爭奪處理機，同時，系統(tǒng)進程也 要使用處理機。因此就應該按照一定的算法，動態(tài)地把處理機分配給就緒隊列中的某個進程。這個任務由進程調(diào)度程序完成。 361 進程調(diào)度的功能進程調(diào)度的功能可歸結(jié)如下：（1）記住系統(tǒng)中所有進程的狀態(tài)、優(yōu)先級和所用資源情況。作為進程調(diào)度的準備，進程管理模塊必須將系統(tǒng)中各進程的執(zhí)行情況和狀態(tài)特征等記錄在各進程的進程控制塊表中，并根據(jù)各進程的狀態(tài)特征和資源要求，將各進程的進程

39、控制塊表排成相應的隊列。進程調(diào)度模塊通過進程控制塊中所記載的信息來掌握系統(tǒng)中所有進程的執(zhí)行情況和狀態(tài)特征。（2）根據(jù)各進程的情況，當處理機空閑時，按照確定的進程調(diào)度算法將處理機分配給處于就緒狀態(tài)的某個進程并確定分配給它多長時間。（3）將處理機交給選中的進程并啟動執(zhí)行。 362 引起進程調(diào)度的原因引起進程調(diào)度的原因有以下幾種：（1）正在執(zhí)行的進程執(zhí)行完畢。系統(tǒng)將收回該進程所占用的全部資源，包括處理機資源。如果此時不從就緒隊列中重新選擇一個進程占用處理機，將使得處理機空閑，從而造成處理機資源的極大浪費。（2）執(zhí)行中的進程自己調(diào)用了阻塞原語將自己阻塞起來進入睡眠等待狀態(tài)。（3）執(zhí)行中的進程提出了I/

40、O請求后被阻塞。（4）執(zhí)行中的進程執(zhí)行了某種原語操作而阻塞，如P操作、關(guān)鎖原語操作等。（5）在分時系統(tǒng)中，分配給該進程運行的時間片已經(jīng)用完。（6）在執(zhí)行完系統(tǒng)調(diào)用，當系統(tǒng)程序返回用戶進程時，可認為系統(tǒng)進程執(zhí)行完畢，從而可以調(diào)度選擇一個新的用戶進程執(zhí)行。（7）在可剝奪方式下，就緒隊列中的某進程的優(yōu)先級變得高于當前執(zhí)行進程的優(yōu)先級時會引起進程調(diào)度。363 進程調(diào)度算法1. 最高優(yōu)先級優(yōu)先（HPF）調(diào)度算法2. 輪轉(zhuǎn)法（Round robin）最高優(yōu)先級優(yōu)先（HPF）調(diào)度算法（1）進程類型（2）作業(yè)要求的資源（3）外部優(yōu)先級和作業(yè)到達時間2.輪轉(zhuǎn)法（Round robin）（1）簡單輪轉(zhuǎn)法 系統(tǒng)響應

41、時間：當進程數(shù)目一定時，時間片正比于系統(tǒng)響應時間。 就緒隊列中的進程數(shù)目：當響應時間一定時，時間片反比于就緒隊列中的進程數(shù)目。 進程轉(zhuǎn)換時間 計算機處理能力（2）可變時間片輪轉(zhuǎn)法（3）多隊列輪轉(zhuǎn)法37 死鎖371 死鎖問題的提出及舉例372 產(chǎn)生死鎖的原因373 解決死鎖問題的三種途徑374 系統(tǒng)狀態(tài)圖和進程資源圖375 死鎖的預防376 死鎖的檢測377 死鎖的解除371 死鎖問題的提出及舉例死鎖問題是Dijkstra于1965年在研究銀行家算法時首先提出來的，后來Havender等人又進一步認識這一現(xiàn)象并將其發(fā)展。實際上，死鎖是一個具有普遍性的現(xiàn)象，在各個領(lǐng)域乃至日常生活中也屢見不鮮。研究

42、死鎖問題是保證操作系統(tǒng)正確可靠運行必須考慮的課題。并行進程的執(zhí)行雖然改善了系統(tǒng)資源的利用率，提高了系統(tǒng)的處理能力。但并行執(zhí)行的風險增大了，因為并發(fā)進程執(zhí)行的結(jié)果與時間有關(guān)，且對臨界資源的管理或操作不當（如在生產(chǎn)者與消費者問題中的P 操作的次序顛倒時等等）就會產(chǎn)生死鎖。銀行家算法問題 假設(shè)某銀行擬將一定數(shù)量的資金供給一定數(shù)量的顧客共享使用。規(guī)定：（1） 每個顧客必須預先申請他對資金的最大需求量，但不得超過銀行共享資金的總和；（2）每個顧客的借款方式是一個單位一個單位地進行，每次交易借款額為一個資金單位；（3）銀行對顧客提出的每次交易，將根據(jù)當時的資金數(shù)量，依照一定的原則，或立即成交或讓顧客等待一

43、段時間后再成交，但須確保顧客等待的時間是有限的，每個顧客的借款總額不得超過其最大申請量；（4）當且僅當每個顧客的借款總額達到他的最大申請量后，他才能且必須在有限時間內(nèi)歸還其全部借款。如果在某一時刻銀行能與所有的顧客成交，則稱此時刻的狀態(tài)是安全的，如果永遠不具有成交的可能性，則說是不安全的。顧客的狀態(tài)可用他的現(xiàn)時借款額和進一步申請額來刻畫：剩余申請量=最大申請量-已借款額銀行的狀態(tài)則可用它的限定的資金總額和庫存的資金來刻畫：庫存資金=資金總額-各顧客已借款額之和假設(shè)銀行共有10個資金，現(xiàn)有3個顧客與銀行進行交易，這3個顧客分別為甲、乙和丙,顧客甲的最大申請額為8個資金，顧客乙的最大申請額為3個資

44、金，顧客丙的最大申請額為9個資金，都不超過銀行的現(xiàn)有資金總和。現(xiàn)在銀行已經(jīng)借給顧客甲 4個資金，借給顧客乙2個資金，借給顧客丙2個資金。那么，顧客甲還需要資金4個，顧客乙還需要資金1個，顧客丙尚需資金7個，銀行庫存資金為2個，狀態(tài)如下圖（a）所示。 如果銀行現(xiàn)在和顧客乙進行交易，即借給顧客乙1個資金，顧客乙就已經(jīng)達到了其最大申請量3個資金，在有限時間內(nèi)顧客乙將這3個資金全部歸還給銀行，此時，銀行庫存資金就變成了4個，此時的狀態(tài)如下圖（b）所示。接著銀行和顧客甲進行成交，即將庫存的4個資金借給顧客甲，顧客甲就達到了其最大申請量，在有限時間內(nèi)顧客甲歸還他所借的資金，使庫存資金變成8個，其狀態(tài)如下圖

45、（c）所示。然后，銀行和顧客丙進行交易，借給顧客丙7個資金，顧客丙也達到了其最大申請量，用完后歸還，此時，銀行收回了全部10個資金。銀行的最終狀態(tài)如下圖（d）所示?？梢姲凑者@樣的交易方式進行，系統(tǒng)是安全的。圖3-16 銀行和顧客安全交易過程(d)銀行與 丙成交(c)銀行與 甲成交(a)某時刻 狀態(tài)(b)銀行與 乙成交庫存庫存丙存庫甲丙4(4)42(7)82(7)10甲庫存乙丙4(4)22(1)2(7)如果不按照上述方式交易，如，當系統(tǒng)處于下圖（a）狀態(tài)時，銀行草率地把庫存的2個資金借給了丙1個，此時的狀態(tài)如下圖（b）。由于此時銀行的庫存還有1個資金，然后，銀行再和顧客乙完成交易，即借給顧客乙1

46、個資金，顧客乙就達到了其最大申請量，用完后歸還其所借的3個資金。這時，銀行的庫存只有3個資金，狀態(tài)如下圖(c)，銀行使用這3個資金無論是與顧客甲還是與顧客丙都無法交易下去，因為這兩個顧客都得不到最大滿足，也就是說，銀行永遠也不能收回其全部資金。我們說銀行按照這樣的交易方式進行交易是不安全的。 圖 3-17銀行和顧客不安全交易過程(c) 與乙成交后(b) 借給丙一個后(a) 某一時刻甲庫存丙甲庫存乙丙甲庫存乙丙4(4)22(1)2(7)4(4)12(1)3(6)4(4)33(6)死鎖的定義：當某進程提出資源請求后，使得若干進程在無外力作用下，永遠不能再繼續(xù)前進，我們稱這種情況為系統(tǒng)發(fā)生了死鎖或僵局?；虍攦蓚€或兩個以上的進程因競爭系統(tǒng)資源而無休止的相互等待時，稱這些進程是死鎖的，或處于死鎖狀態(tài)。 372 產(chǎn)生死鎖的原因系統(tǒng)之所以產(chǎn)生死鎖，主要原因是系統(tǒng)中多道程序共享的系統(tǒng)資源不足，所以，當進程提出資源請求時，才會發(fā)生死鎖