計算機操作系統(tǒng)(第三版)第二章復(fù)習課件

1、第二章進 程 管 理 進程基本概念引入狀態(tài)前趨圖進程控制進程同步進程通信同步與互斥臨界資源和臨界區(qū)同步機制四規(guī)則同步方法信號量管程類別經(jīng)典同步問題線程線程同步與控制用戶級與內(nèi)核級基本概念區(qū) 別區(qū)別消息管道共享存儲器8. 臨界資源：也稱獨占資源，是指在一段時間內(nèi)只允許一個臨界資源：也稱獨占資源，是指在一段時間內(nèi)只允許一個進程訪問的資源。進程訪問的資源。 線程的定義存在多種不同的提法。這些提法可以相互補線程的定義存在多種不同的提法。這些提法可以相互補充對線程的理解：充對線程的理解：線程是進程內(nèi)的一個執(zhí)行單元，比進程小。線程是進程內(nèi)的一個執(zhí)行單元，比進程小。線程是進程內(nèi)的一個可調(diào)度實體。線程是進程內(nèi)

2、的一個可調(diào)度實體。線程是程序或進程中相對獨立的一個控制流序列。線程是程序或進程中相對獨立的一個控制流序列。線程本身不能單獨運行，只能包含在進程中，只能在進程中線程本身不能單獨運行，只能包含在進程中，只能在進程中執(zhí)行。執(zhí)行。 系統(tǒng)開銷：由于創(chuàng)建進程進程時，系統(tǒng)都要為之分配或系統(tǒng)開銷：由于創(chuàng)建進程進程時，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、回收資源，如內(nèi)存空間、IO設(shè)備等，操作系統(tǒng)所付出的開銷設(shè)備等，操作系統(tǒng)所付出的開銷遠大于創(chuàng)建或撤銷線程時的開銷。遠大于創(chuàng)建或撤銷線程時的開銷。15. 經(jīng)典進程的同步問題經(jīng)典進程的同步問題 :生產(chǎn)者生產(chǎn)者消費者問題消費者問題讀者讀者-寫者問題寫者問題 哲學家進

3、餐問題哲學家進餐問題 關(guān)于關(guān)于PV問題的解題思路：主要是看進程等的信號和要發(fā)問題的解題思路：主要是看進程等的信號和要發(fā)出的信號是什么，等信號用出的信號是什么，等信號用P/wait，發(fā)信號用，發(fā)信號用V/signal。主要步驟是：主要步驟是： 分析清楚題目涉及的進程和它們之間的制約關(guān)系（同步或分析清楚題目涉及的進程和它們之間的制約關(guān)系（同步或互斥）?；コ猓?。 設(shè)置信號是（包括信號量的個數(shù)和初值及其物理含義），設(shè)置信號是（包括信號量的個數(shù)和初值及其物理含義），合作進程間需要收發(fā)幾條消息相應(yīng)就設(shè)置幾個信號量。合作進程間需要收發(fā)幾條消息相應(yīng)就設(shè)置幾個信號量。 給出進程相應(yīng)程序的算法描述或流程控制，并把

4、給出進程相應(yīng)程序的算法描述或流程控制，并把P/wait、V/signal操作加到程序的適當?shù)胤?。操作加到程序的適當?shù)胤健?某一進程若收不到另一進程給它提供的必要信息就不能繼續(xù)下去，這種情況表明了兩個進程之間在某些點上要交換信息，相互交流運行情況。這種制約關(guān)系稱為同步關(guān)系，基本形式是“進程進程”。 這種制約關(guān)系主要源于進程間的合作，同步設(shè)置在不同進程之間以達到多種進程間的同步 若某一進程要求使用某種資源，而該資源被另一進程使用。并且這一資源不允許兩個進程同時使用，那么該等待已占用資源釋放資源后再使用，這種制約關(guān)系稱為互斥，基本形式為“進程資源進程?！?這種制約關(guān)系源于多個同種進程需要互斥地共享某

5、種系統(tǒng)資源，互斥是設(shè)置在同種進程之間以達到互斥地訪問資源的目的。信號量及P、V操作討論1) 信號量的物理含義S0表示有S個資源可用S=0表示無資源可用 S0則| S |表示S阻塞（等待）隊列中的進程個數(shù)Wait（S）或）或P(S)：表示申請一個資源表示申請一個資源、或等消息、或等消息signal （S）或）或V(S)：表示釋放一個資源表示釋放一個資源、或發(fā)消息、或發(fā)消息信號量的初值應(yīng)該大于等于信號量的初值應(yīng)該大于等于0信號量及 Wait 或或P、 signal 或或V操作討論2) Wait / signal 或或P/V操作應(yīng)該成對出現(xiàn)，有一個 Wait 或或P操作就一定有一個 signal 或

6、或V操作當為互斥操作時，它們同處于同類進程當為同步操作時，則在不同類進程中出現(xiàn)如果 Wait(S1)或 P(S1)和 Wait(S2)或 P(S2) 兩個操作在一起，那么 Wait或或 P操作的順序至關(guān)重要,一個同步 Wait或或 P操作與一個互斥 Wait或或 P操作在一起時同步 Wait或或 P操作在互斥 Wait或或 P操作前，而兩個 signal或或 V操作無關(guān)緊要.信號量及 Wait 或或P、 signal 或或V操作討論一、填空題(1)從靜態(tài)角度上看，進程是由_、_、_三部分組成。(2)正在執(zhí)行的進程由于用完其時間片而被暫停執(zhí)行，此時進程應(yīng)從執(zhí)行狀態(tài)變成為_。(3)臨界區(qū)是指進程中

7、用于_的那段代碼。(4)設(shè)有6個進程共享同一互斥段，若最多允許有3個進程進入互斥段，則所采用的互斥信號量的初值為_。(9)有3個進程共享同一程序段，而每次最多允許兩個進程進入該程序段，若用P、V操作作同步機制，則信號量S的取值范圍為_。PCB程序段數(shù)據(jù)段就緒狀態(tài)訪問臨界資源32, 1, 0, -11、若信號量S的初值為2，當前值為-1，則表示有（ ）等待進程。A、0個 B、1個 C、2個 D、3個2、分配到必要的資源并獲得處理機時的進程狀態(tài)是分配到必要的資源并獲得處理機時的進程狀態(tài)是 ( ) 。 A、就緒狀態(tài)、就緒狀態(tài) B、執(zhí)行狀態(tài)、執(zhí)行狀態(tài) C、阻塞狀態(tài)、阻塞狀態(tài) D、撤銷狀態(tài)、撤銷狀態(tài) 3

8、 3、在進程狀態(tài)轉(zhuǎn)換時，下列（、在進程狀態(tài)轉(zhuǎn)換時，下列（ ）轉(zhuǎn)換是不可能發(fā)生的。）轉(zhuǎn)換是不可能發(fā)生的。 A A、就緒態(tài)、就緒態(tài)運行態(tài)運行態(tài) B B、運行態(tài)、運行態(tài)就緒態(tài)就緒態(tài) C C、運行態(tài)、運行態(tài)阻塞態(tài)阻塞態(tài) D D、阻塞態(tài)、阻塞態(tài)運行態(tài)運行態(tài) 4 在一個單處理機系統(tǒng)中，若有個用戶進程，在非管態(tài)的在一個單處理機系統(tǒng)中，若有個用戶進程，在非管態(tài)的某一時刻，處于就緒某一時刻，處于就緒 狀態(tài)的用戶進程最多有（）個。狀態(tài)的用戶進程最多有（）個。 A. 5 B. 6 C. 1 D. 4 BBDA5.wait5.wait操作可能導(dǎo)致：操作可能導(dǎo)致：( )( )。A.A. 進程就緒進程就緒 B.B. 進程

9、結(jié)束進程結(jié)束 C.C. 進程阻塞進程阻塞 D.D. 新進程創(chuàng)建新進程創(chuàng)建C6.( ) 是一種只能進行是一種只能進行wait 操作和操作和 signal 操作的特殊變量。操作的特殊變量。 A、調(diào)度、調(diào)度 B、進程、進程 C、同步、同步 D、信號量、信號量 1.PCB（進程控制塊）是標志進程存在的數(shù)據(jù)結(jié)構(gòu)。（進程控制塊）是標志進程存在的數(shù)據(jù)結(jié)構(gòu)。（ ）2.操作系統(tǒng)中進程是一個獨立運行的單位，是系統(tǒng)進行資源操作系統(tǒng)中進程是一個獨立運行的單位，是系統(tǒng)進行資源分配和調(diào)度的基本單位（分配和調(diào)度的基本單位（ ） 3.創(chuàng)建線程比創(chuàng)建進程開銷小。（創(chuàng)建線程比創(chuàng)建進程開銷小。（ ）4. 進程存在的唯一標志是它是否

10、處于運行狀態(tài)。（進程存在的唯一標志是它是否處于運行狀態(tài)。（ ） 5. 在操作系統(tǒng)中引入線程概念的主要目的是處理進程與進程在操作系統(tǒng)中引入線程概念的主要目的是處理進程與進程之間的競爭（之間的競爭（ ）.DTTTFF1.進程控制塊的作用是什么？進程控制塊的作用是什么？PCB中應(yīng)包括哪些信息？中應(yīng)包括哪些信息？答：答： 進程控制塊的作用是：進程控制塊用于保存每個進程和進程控制塊的作用是：進程控制塊用于保存每個進程和資源的相關(guān)信息，以便于操作系統(tǒng)管理和控制進程和資源。資源的相關(guān)信息，以便于操作系統(tǒng)管理和控制進程和資源。 PCB中應(yīng)包括：中應(yīng)包括：1、進程標識信息：本進程的標識、父進程、進程標識信息：本

11、進程的標識、父進程的標識、進程所屬用戶的標識。的標識、進程所屬用戶的標識。2、處理機狀態(tài)信息。保存進、處理機狀態(tài)信息。保存進程的運行現(xiàn)場信息，包括用戶可用寄存器的信息；控制和狀程的運行現(xiàn)場信息，包括用戶可用寄存器的信息；控制和狀態(tài)寄存器的信息；棧指針。態(tài)寄存器的信息；棧指針。2. 請畫圖說明進程三種基本狀態(tài)之間的轉(zhuǎn)換，并指出轉(zhuǎn)換原因。請畫圖說明進程三種基本狀態(tài)之間的轉(zhuǎn)換，并指出轉(zhuǎn)換原因。 3. 何謂臨界資源？何謂臨界資源？ 答：臨界資源：也稱獨占資源，是指在一段時間內(nèi)只允許一答：臨界資源：也稱獨占資源，是指在一段時間內(nèi)只允許一個進程訪問的資源。例如打印機，也可以是進程共享的數(shù)據(jù)、個進程訪問的資

12、源。例如打印機，也可以是進程共享的數(shù)據(jù)、變量等。變量等。 4.什么是臨界區(qū)？什么是臨界區(qū)？答：每個進程中訪問臨界資源的那段程序稱為臨界區(qū)。每答：每個進程中訪問臨界資源的那段程序稱為臨界區(qū)。每次只準許一個進程進入臨界區(qū)，進入后不允許其他進程進次只準許一個進程進入臨界區(qū)，進入后不允許其他進程進入入。 5、簡述進程同步與互斥的概念與區(qū)別。、簡述進程同步與互斥的概念與區(qū)別。 所謂進程同步是指多個相互合作的進程，在一些關(guān)鍵點上所謂進程同步是指多個相互合作的進程，在一些關(guān)鍵點上可能需要互相等待或互相交換信息，這種相互制約關(guān)系稱為進可能需要互相等待或互相交換信息，這種相互制約關(guān)系稱為進程同步。程同步。 在操

13、作系統(tǒng)中，當一個進程進入臨界區(qū)使用臨界資源時，在操作系統(tǒng)中，當一個進程進入臨界區(qū)使用臨界資源時，另一個進程必須等待，當占用臨界資源的進程退出臨界區(qū)后，另一個進程必須等待，當占用臨界資源的進程退出臨界區(qū)后，另一個進程才允許去訪問此臨界資源，稱進程之間的這種相互另一個進程才允許去訪問此臨界資源，稱進程之間的這種相互制約關(guān)系為進程互斥。制約關(guān)系為進程互斥。 其實互斥是進程同步的一種特殊情況，互斥也是為了達其實互斥是進程同步的一種特殊情況，互斥也是為了達到讓進程之間協(xié)調(diào)推進的目的。到讓進程之間協(xié)調(diào)推進的目的。應(yīng)用題應(yīng)用題1.購物問題。某超級市場，可容納購物問題。某超級市場，可容納100個人同時購物，個

14、人同時購物，入口處備有籃子，每個購物者可持一個籃子入內(nèi)購入口處備有籃子，每個購物者可持一個籃子入內(nèi)購物。出口處結(jié)賬，并歸還籃子（出、入口僅容納一物。出口處結(jié)賬，并歸還籃子（出、入口僅容納一人通過）。請用人通過）。請用 wait（P）、）、signal（V）操作完成）操作完成購物算法。購物算法。答：答： 同步信號量同步信號量S 表示同時在超級市場購物的人數(shù)；表示同時在超級市場購物的人數(shù)； 信號量信號量mutex1 表示入口臨界資源；表示入口臨界資源； 信號量信號量mutex2 表示出口臨界資源。表示出口臨界資源。 只要只要S=100,顧客便可進入超級市場。顧客便可進入超級市場。S=100 mut

15、ex1/ mutex2的初始值為的初始值為1Var S, mutex1, mutex2: semaphore; S:=100; mutex1:=1; mutex2:=1 process Pi: begin wait(S); wait(mutex1);進入口處，取一只籃子；進入口處，取一只籃子； signal(mutex1);選購商品選購商品; wait(mutex2);結(jié)賬，并歸還籃子；結(jié)賬，并歸還籃子； signal(mutex2); signal(S); end2、某處有一東、西向單行道，其上班交通并不繁忙。試用某處有一東、西向單行道，其上班交通并不繁忙。試用wait和和signal操作正

16、確實現(xiàn)該東、西向單行道的管理：當有車操作正確實現(xiàn)該東、西向單行道的管理：當有車由東向西（或由西向東）行駛時，另一方向的車需要等待；由東向西（或由西向東）行駛時，另一方向的車需要等待；同一方向的車可連續(xù)通過；當某一方向已無車輛在單行道行同一方向的車可連續(xù)通過；當某一方向已無車輛在單行道行駛時，則另一方向的車可以駛?cè)雴涡械溃ㄒ髮懗鲂盘柫亢倳r，則另一方向的車可以駛?cè)雴涡械溃ㄒ髮懗鲂盘柫亢x和程序描述義和程序描述 ）。）。解：單車道意味著雙向車流必須互斥地通過橋。解：單車道意味著雙向車流必須互斥地通過橋。 設(shè)置信號量設(shè)置信號量mutex控制雙向車流對橋的互斥使用。初值控制雙向車流對橋的互斥使用。

17、初值mutex=1。 定義兩個計數(shù)器定義兩個計數(shù)器C1和和C2，分別記錄由東向西行的車輛數(shù)，分別記錄由東向西行的車輛數(shù)和由西向東行的車輛數(shù)。和由西向東行的車輛數(shù)。設(shè)置信號量設(shè)置信號量S1控制計數(shù)器控制計數(shù)器C1的互斥使用。初值的互斥使用。初值S1=1。設(shè)置信號量設(shè)置信號量S2控制計數(shù)器控制計數(shù)器C2的互斥使用。初值的互斥使用。初值S2=1。Semaphore： S1=1, S2=1, mutex=1;int: C1 =0; C2 = 0;cobegin由東向西行的車輛：由東向西行的車輛：beginwait (S1); C1 = C1+1;if ( Cl = = l ) then wait (m

18、utex); signal ( S1 ); 過橋過橋;wait (S1); C1 = C1-1;if ( C1 = = 0) then signal ( mutex ); signal (S1); end由西向東行的車輛：由西向東行的車輛：beginwait (S2); C2 = C2+1;if ( C2 = = l ) then wait (mutex); signal ( S2 ); 過橋過橋;wait (S2); C2 = C2-1;if ( C2 = = 0) then signal ( mutex ); signal(S2); endcoend第二章第二章習題課習題課二、應(yīng)用題5.某寺廟有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚飲用。水缸可以容納10桶水，水取自同一井水。水井狹窄，每次只能容一個桶取水。水桶總數(shù)為3個。每次入、出水缸僅一桶，且不可同時進行。試給出有關(guān)取水、入水的算法描述。process 小和尚: begin repeat P(empty);P(count);