專業(yè)綜合操作系統(tǒng)練習題

1、1 專業(yè)綜合 操作系統(tǒng)操作系統(tǒng) 數(shù)信學院數(shù)信學院 張培欣張培欣 2 （一）進程與線程（一）進程與線程 （二）處理機調(diào)度（二）處理機調(diào)度 （三）同步與互斥（三）同步與互斥 （四）死鎖（四）死鎖 第二部分第二部分 進程管理進程管理 3 （三）同步與互斥（三）同步與互斥 4 1. 進程同步的基本概念進程同步的基本概念 多道程序系統(tǒng)中，進程之間有兩種形式的制約關(guān)系：多道程序系統(tǒng)中，進程之間有兩種形式的制約關(guān)系： （1）間接相互制約：源于資源共享）間接相互制約：源于資源共享 （2）直接相互制約：源于進程合作）直接相互制約：源于進程合作 進程同步：主要源于進程合作進程同步：主要源于進程合作 是進程之間的直

2、接制約關(guān)系是進程之間的直接制約關(guān)系 進程互斥：主要源于進程共享進程互斥：主要源于進程共享 是進程之間的間接制約關(guān)系是進程之間的間接制約關(guān)系 5 臨界資源：一次只允許一個進程使用的資源。臨界資源：一次只允許一個進程使用的資源。 如：打印機，公共變量如：打印機，公共變量 臨界區(qū)：在每個進程中，訪問臨界資源的那段程序。臨界區(qū)：在每個進程中，訪問臨界資源的那段程序。 同步機制遵循的準則：同步機制遵循的準則： 空閑讓進，忙則等待，有限等待，讓權(quán)等待空閑讓進，忙則等待，有限等待，讓權(quán)等待 當臨界區(qū)空閑時，進程可以立即進入，以便有效利用 臨界資源 當已有進程進入臨界區(qū)時，其它進程必須等待，以保 證互斥 對要

3、求進入的進程，應(yīng)在有限的時間內(nèi)使之進入，以 避免“死等” 對于等待的進程，它必須立即釋放處理機，以避免進 程忙等 6 2. 實現(xiàn)臨界區(qū)互斥的基本方法實現(xiàn)臨界區(qū)互斥的基本方法 進程互斥的硬件方法進程互斥的硬件方法 （1）檢測和設(shè)置（）檢測和設(shè)置（TS）指令）指令 （2）swap指令（或指令（或exchange） 交換兩個字（字節(jié)）交換兩個字（字節(jié)） 的內(nèi)容的內(nèi)容 用軟件實現(xiàn)的同步互斥機制用軟件實現(xiàn)的同步互斥機制 在進入?yún)^(qū)設(shè)置和檢查一些標志在進入?yún)^(qū)設(shè)置和檢查一些標志 （1）算法一：單標志法）算法一：單標志法 （2）算法二：雙標志法先檢查）算法二：雙標志法先檢查 （3）算法三：雙標志法后檢查）算法三

4、：雙標志法后檢查 （4）算法四：）算法四：Peterson算法算法 7 【例1】（錯誤解法） （turn是int型的變量，初始化為i或j） 算法一能夠保證同一時刻只有一個進程在臨界區(qū)中，但是 卻要求進程Pi和進程Pj輪流地訪問臨界區(qū)，若進程Pi不打算 進入臨界區(qū)，那么進程Pj在進入過一次臨界區(qū)后就再也不能 進入。所以不滿足空閑讓進和有限等待不滿足空閑讓進和有限等待的兩個準則。 8 【例2】（錯誤解法） （flag2是bool型的數(shù)組，兩個元素初始化為false） 算法二消除了算法一中需要兩個進程輪流訪問臨界區(qū)的錯 誤，但卻存在兩個進程都進不了臨界區(qū)的可能性，仍然不不 能滿足空閑讓進和有限等待。

5、能滿足空閑讓進和有限等待。 9 【例【例3】算法三（正確解法，又稱為】算法三（正確解法，又稱為Dekker算法）算法） （turn是是int型的變量，初始化為型的變量，初始化為i或或j；flag2是是bool型的數(shù)組，型的數(shù)組， 兩個元素初始化為兩個元素初始化為false） Dekker算法結(jié)合了算法一和算法二，實現(xiàn)了空閑讓進和忙則等算法結(jié)合了算法一和算法二，實現(xiàn)了空閑讓進和忙則等 待?；旧洗??；旧螪ekker算法是個正確的算法，能夠正常工作。算法是個正確的算法，能夠正常工作。 10 【例【例4】算法四（正確解法，又稱為】算法四（正確解法，又稱為Peterson算法）算法） （turn是是

6、int型的變量，初始化為型的變量，初始化為i或或j；flag2是是bool型的數(shù)型的數(shù) 組，兩個元素初始化為組，兩個元素初始化為false） Peterson算法與算法與Dekker算法類似，實現(xiàn)了空閑讓進、忙則等待和有限算法類似，實現(xiàn)了空閑讓進、忙則等待和有限 等待。相比而言，等待。相比而言，Dekker算法比較復雜，證明起來也比較困難，而算法比較復雜，證明起來也比較困難，而 Peterson算法較簡潔。算法較簡潔。 11 【例11】 （2010年聯(lián)考第27題） 進程P0和P1的共享變量定義及其初值為： boolean falg2; int turn=0; falg0=FALSE; falg

7、1=FALSE; 若進程P0和P1訪問臨界資源的類C偽代碼實現(xiàn)如下： void P0() /進程P0 while(TRUE) flag0= TRUE; turn=1; while(flag1 臨界區(qū); flag0=FALSE; void P1() /進程P1 while(TRUE) flag1= TRUE; turn=0; while(flag0 臨界區(qū); flag1=FALSE; 則并發(fā)執(zhí)行進程則并發(fā)執(zhí)行進程P0和和P1時產(chǎn)生的情形是時產(chǎn)生的情形是 A. 不能保證進程互斥進入臨界區(qū)、會出現(xiàn)不能保證進程互斥進入臨界區(qū)、會出現(xiàn)“饑餓饑餓”現(xiàn)象現(xiàn)象 B. 不能保證進程互斥進入臨界區(qū)、不會出現(xiàn)不能保

8、證進程互斥進入臨界區(qū)、不會出現(xiàn)“饑餓饑餓”現(xiàn)現(xiàn) 象象 C. 能保證進程互斥進入臨界區(qū)、會出現(xiàn)能保證進程互斥進入臨界區(qū)、會出現(xiàn)“饑餓饑餓”現(xiàn)象現(xiàn)象 D. 能保證進程互斥進入臨界區(qū)、不會出現(xiàn)能保證進程互斥進入臨界區(qū)、不會出現(xiàn)“饑餓饑餓”現(xiàn)象現(xiàn)象 0 0 0 0 0 0 0 0 12 3. 信號量信號量 信號量機制由：信號量機制由： 信號量信號量” “wait操作（操作（P操作）、操作）、signal操作操作(V操作操作)” 兩部分組成，可用來解決進程的互斥與同步。兩部分組成，可用來解決進程的互斥與同步。 P、V操作是原子操作，不可中斷。操作是原子操作，不可中斷。 （1）整型信號量）整型信號量 定義

9、：表示資源的個數(shù)的整型量定義：表示資源的個數(shù)的整型量S。除初始化外，。除初始化外， 僅能通過以下兩個原子操作來訪問。僅能通過以下兩個原子操作來訪問。 wait(S)（P操作）: While(S=0); S=S-1; signal(S)（V操作）: S=S+1; 13 3. 信號量信號量 （2）記錄型信號量）記錄型信號量 在記錄型信號量中，引入了代表資源數(shù)目的在記錄型信號量中，引入了代表資源數(shù)目的 整型變量整型變量value和用于鏈接所有等待該資源的進程和用于鏈接所有等待該資源的進程 鏈表鏈表L，記錄型數(shù)據(jù)結(jié)構(gòu)如下所示：，記錄型數(shù)據(jù)結(jié)構(gòu)如下所示： Typedef struct int value

10、; Queue L; semaphore; 若有若有semaphore S; 相應(yīng)的相應(yīng)的wait(S)和和signal(S)操作可描述為：操作可描述為： wait(S) S.value=S.value-1; if( S.value0) block(S.L); signal(S) S.value=S.value+1; if( S.value0表示有表示有S.value個資源可用；個資源可用； S.value=0表示無資源可用；表示無資源可用； S.value0 B. =0 D. 0）個單元的緩沖區(qū)。P1每次用produce() 生成一個正整數(shù)并用put()送入緩沖區(qū)某一空單元中；P2每次用 g

11、etodd()從該緩沖區(qū)中取出一個奇數(shù)并用countodd()統(tǒng)計奇數(shù) 個數(shù)；P3每次用geteven()從該緩沖區(qū)中取出一個偶數(shù)并用 counteven()統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的 同步與互斥活動，并說明所定義的信號量的含義。要求用偽代 碼描述。 【分析】本題目考查進程的同步與互斥。本題目是蘋果【分析】本題目考查進程的同步與互斥。本題目是蘋果-桔子問題的變形。桔子問題的變形。 進程進程P1可以看做是生產(chǎn)者，進程可以看做是生產(chǎn)者，進程P2和和P3可看做是消費者，可看做是消費者， 進程進程P1和和P2、P3共享大小為共享大小為N的緩沖區(qū)。的緩沖區(qū)。 進程進程P1、P2和和P3

12、需互斥使用緩沖區(qū)，需互斥使用緩沖區(qū)， P1進程需要與進程需要與P2進程、進程、P3進程同步。進程同步。 28 29 30 31 32 【例【例11】 在一輛公共汽車上，司機和售票員各行其職，在一輛公共汽車上，司機和售票員各行其職， 司機負責開車和到站停車；售票員負責售票和開、關(guān)門，當司機負責開車和到站停車；售票員負責售票和開、關(guān)門，當 售票員關(guān)好車門后，司機才能繼續(xù)開車行駛。試用售票員關(guān)好車門后，司機才能繼續(xù)開車行駛。試用P、V操操 作實現(xiàn)司機與售票員之間的同步。作實現(xiàn)司機與售票員之間的同步。 【分析】這里存在兩種同步關(guān)系：【分析】這里存在兩種同步關(guān)系： 司機到站停車后，售票員才能開門；司機到

13、站停車后，售票員才能開門； 售票員關(guān)好車門后，司機才能啟動汽車。售票員關(guān)好車門后，司機才能啟動汽車。 33 設(shè)初始狀態(tài)為停車，車門開。設(shè)初始狀態(tài)為停車，車門開。 設(shè)信號量：設(shè)信號量：close 表示門是否已關(guān)，能否啟動車輛表示門是否已關(guān)，能否啟動車輛 stop 表示車是否已停，能否開車門表示車是否已停，能否開車門 semaphore close=0,stop=1; main() Cobegin drive() While(true) P(close); 啟動車輛啟動車輛; 正常行駛正常行駛; 到站停車到站停車; V(stop); Conductor() While(true) 關(guān)車門；關(guān)車門；

14、 V(close); 售票售票; P(stop); 開車門開車門; 上下乘客上下乘客; 34 【例【例12】（】（2011年聯(lián)考第年聯(lián)考第45題）某銀行提供一個服務(wù)窗口和題）某銀行提供一個服務(wù)窗口和10個供顧客等待個供顧客等待 的座位。顧客到達銀行時，若有空座位則到取號機上領(lǐng)取一個號，等待叫號。取的座位。顧客到達銀行時，若有空座位則到取號機上領(lǐng)取一個號，等待叫號。取 號機每次僅允許一位顧客使用。當營業(yè)員空閑時，通過叫號選取一位顧客，并為號機每次僅允許一位顧客使用。當營業(yè)員空閑時，通過叫號選取一位顧客，并為 其服務(wù)。顧客和營業(yè)員的活動過程描述如下：其服務(wù)。顧客和營業(yè)員的活動過程描述如下： Cob

15、egin Process 顧客顧客i 從取號機獲得一個號碼；從取號機獲得一個號碼； 等待叫號；等待叫號； 獲得服務(wù)；獲得服務(wù)； Process 營業(yè)員營業(yè)員 while(TRUE) 叫號；叫號； 為顧客服務(wù)；為顧客服務(wù)； Coend 請?zhí)砑颖匾男盘柫亢驼執(zhí)砑颖匾男盘柫亢蚉、V（或（或wait()、signal()）操作，實現(xiàn)上述過程中的）操作，實現(xiàn)上述過程中的 互斥與同步。要求寫出完整過程，說明信號量的含義并賦初值。互斥與同步。要求寫出完整過程，說明信號量的含義并賦初值。 【分析】【分析】 （1）互斥關(guān)系：顧客需互斥使用取號機，）互斥關(guān)系：顧客需互斥使用取號機， 設(shè)一互斥信號量設(shè)一互斥信號

16、量mutex，初值為，初值為1; （2）同步關(guān)系：顧客需要獲得空座位等）同步關(guān)系：顧客需要獲得空座位等 待叫號，當營業(yè)員空閑時，將選取一位待叫號，當營業(yè)員空閑時，將選取一位 顧客并為其服務(wù)。顧客并為其服務(wù)。 35 Semaphore mutex=1; /互斥使用取號機互斥使用取號機 Semaphore empty=10; /空座位的數(shù)量空座位的數(shù)量 Semaphore full=0; /已占座位的數(shù)量已占座位的數(shù)量 Semaphore service=0; /等待叫號等待叫號 Cobegin process 顧客顧客i P(empty); P(mutex); 從取號機獲得一個號；從取號機獲得一

17、個號； V(mutex); V(full); P(service); /等待叫號等待叫號 獲得服務(wù)；獲得服務(wù)； process 營業(yè)員營業(yè)員 while(TRUE) P(full); V(empty); V(service); /叫號叫號 為顧客服務(wù)；為顧客服務(wù)； 36 【例【例13】有橋如圖所示，車流如箭頭所示，橋】有橋如圖所示，車流如箭頭所示，橋 上不允許兩車交匯，但允許同方向多輛車依次通上不允許兩車交匯，但允許同方向多輛車依次通 過（即橋上可以有多個同方向的車）。用過（即橋上可以有多個同方向的車）。用P、V 操作實現(xiàn)交通管理以防止橋上堵塞。操作實現(xiàn)交通管理以防止橋上堵塞。 橋橋 北北 南

18、南 【分析】本題目類似【分析】本題目類似“讀者讀者寫作寫作”問題，但又有所不同。問題，但又有所不同。 這個題目要解決：這個題目要解決： 南、北互斥（橋上不允許兩車交匯，相當于南、北互斥（橋上不允許兩車交匯，相當于“讀、寫互斥讀、寫互斥”），）， 需要設(shè)置一個互斥信號量需要設(shè)置一個互斥信號量mutex，初值為，初值為1； 南、南共享（相當于南、南共享（相當于“讀、讀共享讀、讀共享”），套用實現(xiàn)），套用實現(xiàn)“讀、讀共讀、讀共 享享”的模式，需要設(shè)置一個共享變量的模式，需要設(shè)置一個共享變量south，用于記錄當前橋上，用于記錄當前橋上 向南行駛過橋的車輛數(shù)目，初值為向南行駛過橋的車輛數(shù)目，初值為0，

19、再設(shè)置一個互斥信號量，再設(shè)置一個互斥信號量 smutex，實現(xiàn)對，實現(xiàn)對south的互斥訪問；的互斥訪問； 北、北共享（也相當于北、北共享（也相當于“讀、讀共享讀、讀共享”），需要設(shè)置一個共享），需要設(shè)置一個共享 變量變量north，用于記錄當前橋上向北行駛過橋的車輛數(shù)目，初值，用于記錄當前橋上向北行駛過橋的車輛數(shù)目，初值 為為0，再設(shè)置一個互斥信號量，再設(shè)置一個互斥信號量nmutex，實現(xiàn)對，實現(xiàn)對north的互斥訪問。的互斥訪問。 37 semaphore mutex=1, smutex=1, nmutex =1; int south=0, north=0; main() Cobegin

20、Tosouth(); Tonorth(); Coend Tosouth () While(1) P(smutex); if (south=0) P(mutex) ; /*當?shù)?輛向南的車輛過橋時，阻止向北車輛過橋*/ south+ V(smutex); 過橋； P(smutex); south-; If (south=0) V(mutex); /*當最后1輛向南的車輛過橋后，允許向北車輛過橋*/ V(smutex); Tonorth () While(1) P(nmutex); If (north=0) P(mutex); /*當?shù)?輛向北的車輛過橋時， 阻止向南車輛過橋*/ north+ V

21、(nmutex); 過橋； P(nmutex); north-; If (north=0) V(mutex); /*當最后1輛向北的車輛過橋后， 允許向南車輛過橋*/ V(nmutex); 38 1.（2010年聯(lián)考第年聯(lián)考第25題）題）設(shè)與某資源關(guān)聯(lián)的信號量初值為 3，當前值為1。若M表示該資源的可用個數(shù)，N表示等待該 資源的進程數(shù)，則M、N分別是（ ）。 A. 0、1 B. 1、0 C. 1、2 D. 2、0 【答案】【答案】B 練習練習 39 2. 設(shè)兩個進程共用一個臨界資源的互斥信號量mutex，當 mutex = -1 時表示（ ）。 A. 一個進程進入了臨界區(qū)，另一個進程等待 B.

22、 沒有一個進程進入臨界區(qū) C. 兩個進程都進入了臨界區(qū) D. 兩個進程都在等待 【答案】【答案】A 練習練習 40 3、（2011年聯(lián)考第32題）有兩個并發(fā)執(zhí)行的進程P1和P2， 共享初值為1的變量x。P1對x加1，P2對x減1。加1和減1操 作的指令序列分別如下所示。 /加1操作 /減1操作 Load R1,x /取x到寄存器中Load R2,x Inc R1 dec R2 Store x,R1 /將R的內(nèi)容存入x Store x,R2 兩個操作完成后，x的值（ ）。 A. 可能為-1 B. 只能為1 C. 可能為0、1、2 D. 可能為-1、0、1、2 【答案】【答案】C 練習練習 41 4、某車站售票廳，任何時刻最多可容納 20 名購票者進入，當 售票廳中少于 20 名購票者時，則廳外的購票者可立即進入，否 則需在外面等待。若把一個購票者看作一個進程，請回答下列問 題： (1) 用 PV 操作管理這些并發(fā)進程時，應(yīng)怎樣定義信號量，寫 出信號量的初值以及信號量各種取值的含義。 (2) 根據(jù)所定義的信號量，利用PV操作寫出能正確并發(fā)執(zhí)行 的進程。 (3) 若欲購票者最多為 n 個人，寫出信號量可能的變化范圍 ( 最大值和最小值 ) 。 42 4. 【分析】本題目考查進程的同步問題。