計算機操作系統(tǒng)復(fù)習題目(2)

1、第二章 進程管理（三） 進程同步5、經(jīng)典同步問題1、生產(chǎn)者消費者問題生產(chǎn)者消費者問題是一種同步問題的抽象描述。計算機系統(tǒng)中的每個進程都可以消費（使用）或生產(chǎn)（釋放）某類資源。這些資源可以是硬件資源，也可以是軟件資源。當某一進程使用某一資源時，可以看作是消費，稱該進程為消費者。而當某一進程釋放某一資源時，它就相當于生產(chǎn)者。問題1：設(shè)某計算進程CP和打印進程IOP共用一個單緩沖區(qū)，CP進程負責不斷地計算數(shù)據(jù)并送入緩沖區(qū)T中，IOP進程負責不斷地從緩沖區(qū)T中取出數(shù)據(jù)去打印。通過分析可知，、必須遵守以下同步規(guī)則： (1)當進程把計算結(jié)果送入緩沖區(qū)時，IOP進程才 能從緩沖區(qū)中取出結(jié)果去打印;(2)當I

2、OP進程把緩沖區(qū)中的數(shù)據(jù)取出打印后，進程才能把下一個計算結(jié)果送入緩沖區(qū).(3)為此設(shè)有兩個信號量Sa=0，Sb=1，Sa表示緩沖區(qū)中有無數(shù)據(jù)，Sb表示緩沖區(qū)中有無空位置。兩個進程的同步可以描述如下：問題2：一組生產(chǎn)者通過具有N個緩沖區(qū)的共享緩沖池向一組消費者提供數(shù)據(jù)。問題分析”： 為解決生產(chǎn)者消費者問題，應(yīng)該設(shè)兩個同步信號量，一個說明空緩沖區(qū)的數(shù)目，用empty表示，初值為有界緩沖區(qū)的大小N，另一個說明已用緩沖區(qū)的數(shù)目，用full表示，初值為。由于在此問題中有M個生產(chǎn)者和N個消費者，它們在執(zhí)行生產(chǎn)活動和消費活動中要對有界緩沖區(qū)進行操作。由于有界緩沖區(qū)是一個臨界資源，必須互斥使用，所以，另外還需

3、要設(shè)置一個互斥信號量mutex，其初值為。問題的解：注意：在每個程序中用于實現(xiàn)互斥的P(mutex)和V(mutex)必須成對的出現(xiàn)對資源信號量empty和full的P和V操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。在每個程序中的多個P操作順序不能顛倒。先同步后互斥。2、哲學家就餐問題有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子。每個哲學家的行為是思考，感到饑餓，然后吃通心粉。為了吃通心粉，每個哲學家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子。1、為防止死鎖發(fā)生可采取的措施：最多允許4個哲學家同時坐在桌子周圍；僅當一個

4、哲學家左右兩邊的筷子都可用時，才允許他拿筷子（AND信號量）；給所有哲學家編號，奇數(shù)號的哲學家必須首先拿左邊的筷子，偶數(shù)號的哲學家則反之。設(shè)chopstick 5為5 個信號量，初值為均1。設(shè)信號量S ，初值為4S用于封鎖第5個哲學家給所有哲學家編號，奇數(shù)號的哲學家必須首先拿左邊的筷子，偶數(shù)號的哲學家則反之；設(shè)chopstick 5為5 個信號量，初值均為1；Philosopher i：repeat 思考； if i mod 2 =1 then P(chopsticki); P(chopstick(i+1) mod 5)； 進食； V(chopsticki); V(chopstick(i+1)

5、 mod 5)； if i mod 2 =0 then P(chopstick(i+1) mod 5)； P(chopsticki); 進食； V(chopstick(i+1) mod 5)； V(chopsticki); Until false;3、讀者寫者問題（1）有兩組并發(fā)進程: 讀者和寫者,共享一組數(shù)據(jù)區(qū)（2）要求： 允許多個讀者同時執(zhí)行讀操作 不允許讀者、寫者同時操作 不允許多個寫者同時操作讀者寫者問題的解法：設(shè)有兩個信號量wmutex=1，rmutex=1另設(shè)一個全局變量readcount =0wmutex用于讀者和寫者、寫者和寫者之間的互斥readcount表示正在讀的讀者數(shù)目r

6、mutex用于對readcount 這個臨界資源的互斥訪問讀者： repeat P(rmutex); if (readcount=0) then P (wmutex); readcount := readcount+1; V(rmutex); 讀; P(rmutex); readcount:= readcount-1; if (readcount=0) then V(wmutex); V(rmutex); until false;寫者： repeat P(wmutex); 寫; V(wmutex); until false;同步與互斥的解題思路分清哪些是互斥問題（互斥訪問臨界資源的），哪些是同

7、步問題（具有前后執(zhí)行順序要求的）。對互斥問題要設(shè)置互斥信號量，不管有互斥關(guān)系的進程有幾個或幾類，通常只設(shè)置一個互斥信號量，且初值為1，代表一次只允許一個進程對臨界資源訪問。對同步問題要設(shè)置同步信號量，通常同步信號量的個數(shù)與參與同步的進程種類有關(guān)，即同步關(guān)系涉及幾類進程，就有幾個同步信號量。同步信號量表示該進程是否可以開始或該進程是否已經(jīng)結(jié)束。在每個進程中用于實現(xiàn)互斥的PV操作必須成對出現(xiàn)；用于實現(xiàn)同步的PV操作也必須成對出現(xiàn)，但可以分別出現(xiàn)在不同的進程中；在某個進程中如果同時存在互斥與同步的P操作，則其順序不能顛倒，必須先執(zhí)行對同步信號量的P操作，再執(zhí)行對互斥信號量的P操作，但V操作的順序沒有

8、嚴格要求。 同步與互斥的解題步驟（1）確定進程。包括進程的數(shù)量、進程的工作內(nèi)容，可以用流程圖描述。（2）確定同步互斥關(guān)系。根據(jù)是否使用的是臨界資源，還是處理的前后關(guān)系，確定同步與互斥，然后確定信號量的個數(shù)、含義，以及對信號量的P、V操作。（3）用類C語言描述同步或互斥算法。第二章 進程同步舉例例題1：下面是兩個并發(fā)執(zhí)行的進程，他們能正確運行嗎？若不能，請舉例說明，并改正。int x;Process_P1int y,z;x=1;y=0;if(x>=1)y=y+1;z=y;Process_P2int t,u;x=0;t=0;if(x<=1)t=t+2;u=t;例題1答案：不能正確執(zhí)行。

9、X是一個臨界資源，沒有保護。int x;Semaphore mutex=1;/訪問X的互斥信號量Process_P1 int y,z;wait(mutex);x=1;y=0;if(x>=1) y=y+1;signal(mutex);z=y；Process_P2int t,u;wait(mutex)x=0;t=0;if(x<=1)t=t+2;signal(mutex)u=t;例題2：生產(chǎn)者 消費者問題演變。一個 buffer ，一個生產(chǎn)者，一個消費者，生產(chǎn)者只生產(chǎn)一個東西，消費者只進行一次消費，即：生產(chǎn)者只進行一次 putdata 操作，消費者只進行一次 getdata 操作。例題2

10、答案：var full:semaphore:=0;buffer: array 1 of item;producer:beginputdata ；V (full);endconsumer:beginP (full);getdata;end例題3：一個 buffer ，多個生產(chǎn)者，多個消費者，多個生產(chǎn)者和消費者都在不斷地存取 buffer ，即生產(chǎn)者不斷地進行 putdata 操作，消費者不斷地進行 getdata 操作。例題4：三個進程P1 P2 P3互斥使用一個包含N（N>0)個單元的緩沖區(qū)。P1每次用produce()生成一個正整數(shù)并用put()送入緩沖區(qū)某一空單元中；P2每次用get

11、odd()從該緩沖區(qū)中取出一個奇數(shù)并用countodd（）統(tǒng)計奇數(shù)個數(shù)；P3每次用geteven（）從該緩沖區(qū)中取出一個偶數(shù)并用counteven（）統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步互斥活動，并說明所定義的信號量的含義（要求用偽代碼描述）。例題4答案：【答案】（1）緩沖區(qū)是一互斥資源，因此設(shè)互斥信號量mutex。（2）同步問題：P1、P2因為奇數(shù)的放置與取用而同步，設(shè)同步信號量odd；P1、P3因為偶數(shù)的放置與取用而同步，設(shè)同步信號量even；P1、P2、P3因為共享緩沖區(qū)，設(shè)同步信號量empty。Semaphore mutex=1;Semaphore odd=0,even=0

12、;Semaphore empty=N;Semaphore metux=1;/緩沖區(qū)操作互斥信號量Semaphore odde=0,even=0;/奇數(shù) 偶數(shù)進程的同步信號量Semaphore empty=N;/空緩沖區(qū)單元個數(shù)信號量P1()X=produce();/生成一個數(shù) wait(empty);/判斷緩沖區(qū)是否有空緩沖區(qū) wait(mutex);/互斥訪問緩沖區(qū) put(); if(X%2=0) signal(even);/如果是偶數(shù)向P3發(fā)出信號 else signal(odd);/如果是奇數(shù)向P2發(fā)出信號 signal(mutex);/使用完緩沖區(qū)釋放P2()wait(odd);/是

13、否已產(chǎn)生一個奇數(shù) wait(mutex);/互斥訪問緩沖區(qū) getodd(); countodd()=countodd()+1; signal(mutex);/使用完緩沖區(qū)釋放 signal(empty);/向P1發(fā)出信號，多出一個空單元P3()wait(even);/是否已產(chǎn)生一個偶數(shù) wait(mutex);/互斥訪問緩沖區(qū) geteven(); counteven()=counteven()+1; signal(mutex);/使用完緩沖區(qū)釋放 signal(empty);/向P1發(fā)出信號，多出一個空單元例：有3個并發(fā)進程R、M、P，它們共享同一個緩沖區(qū)，假定緩沖區(qū)只能存放一條記錄。進程

14、R負責從輸入設(shè)備讀信息，每讀入一個記錄后，就把它放進緩沖區(qū)；進程M在緩沖區(qū)中加工讀入的記錄；進程P把加工后的記錄打印輸出。讀入的記錄經(jīng)加工輸出后，緩沖區(qū)又可以存放下一個記錄。試寫出他們能夠正確執(zhí)行的并發(fā)程序。（華南理工大學2006年）【答案】此題類似與生產(chǎn)者消費者問題緩沖區(qū)進程R從設(shè)備讀入進程P打印進程M進行加工三進程之間的合作關(guān)系三進程之間的合作關(guān)系由圖中可知有三個同步關(guān)系：讀進程與加工進程的同步，加工進程與打印進程的同步，打印進程與讀進程之間的同步，每一個同步設(shè)置一個同步信號量。設(shè)置一個信號量m1，表示緩沖區(qū)是否有未被處理的記錄，初值為0，未被處理則由進程M進行處理，在加工進程加工之前加P

15、操作，在讀進程加入未處理記錄之后加V操作；設(shè)置一個信號量m2，表示緩沖區(qū)是否有被處理過的記錄，初值為0，如果有處理過的記錄則由進程P取走記錄進行打印，在打印進程取數(shù)據(jù)之前加P操作，在加工進程處理完記錄之后加V操作；設(shè)置一個信號量empty表示緩沖區(qū)是否為空，其初值是1，如果為空則進程R可讀入數(shù)據(jù)，在打印數(shù)據(jù)取走記錄之后加V操作，在讀入進程放記錄之前加P操作。設(shè)置一個互斥信號量mutex，使各進程互斥的訪問緩沖區(qū),初值為1。注意先同步后互斥。P（R）：（讀入進程）BeginRepeat 讀入一個記錄 P(empty); P(mutex); 將記錄放入緩沖區(qū); V(mutex); V（m1）Unt

16、il false;EndP（M）：（加工進程）BeginRepeat P(m1); P(mutex); 在緩沖區(qū)中加工記錄; V(mutex); V（m2）Until false;EndP（P）：（打印進程）BeginRepeat P(m2); P(mutex); 將緩沖區(qū)中記錄取出; V(mutex); V（empty）; 打印記錄；Until false;End例：用P、V操作實現(xiàn)下述問題的解。桌上有一個盤子，可以存放一個水果。父親總是放蘋果到盤子中，而母親總是放香蕉到盤子中：一個兒子專等吃盤中的香蕉，而一個女兒專等吃盤中的蘋果?！敬鸢浮吭诒绢}中，父親、母親、兒子和女兒共用一個盤子，盤子一

17、次只能放一個水果。當盤子為空時，父親及母親均可試著將一個水果放入盤子中，但一次只能有一個人成功放入水果。若放入盤子中的是香蕉，則允許兒子吃，女兒必須等待；若放入盤子中的是蘋果，則允許女兒吃，兒子必須等待。 在本題中，應(yīng)設(shè)置三個信號量dish、apple、banana，信號量dish表示盤子是否為空，其初值為1；信號量apple表示盤中是否有蘋果，其初值為0；信號量banana表示盤中是否有香蕉，其初值為0。進程之間的同步描述如下：semaphore dish=1;semaphore apple=0; semaphore banana=0;father ()while (true)p(dish)

18、;將蘋果放入盤中;v(apple);mother ()while (true)p(dish);將香蕉放入盤中;v(banana);son ()while (true)p (banana);從盤中取出香蕉;v (dish);吃香蕉;daughter ()while (ture)p (apple);從盤中取出蘋果;v (dish);吃蘋果;哲學家就餐擴展刀1刀2乙甲叉2丙丁叉1食品哲學家甲請哲學家乙、丙、丁到某處討論問題，約定全體到齊后開始討論；在討論的間隙思維哲學家進餐，每人進餐時都需使用刀、叉各一把，餐桌上的布置如圖所示。請用信號量及P、V操作說明這四位哲學家的同步、互斥過程?！敬鸢浮吭诒绢}中

19、，思維哲學家討論問題期間的生活方式為交替地進行討論和進餐。由于刀和叉資源均為2，而哲學家有四位，這就會出現(xiàn)資源競爭，為此應(yīng)對他們的進餐進行同步控制。在本題解決方案中規(guī)定：所有哲學家先申請使用刀，申請到刀后在申請使用叉，刀和叉都拿到后才能進餐。在本題中，應(yīng)設(shè)置四個信號量fork1、fork2、knife1、knife2，其初值均為1，分別表示資源叉1、叉2、刀1、刀2是否可用。進程之間的同步描述如下：semaphore fork1=1;semaphore fork2=1;semaphore knife1=1;semaphore knife2=1;pa()while(true) p(knife1)

20、;p(fork1); 進餐； v(knife1); v(fork1); 討論問題； Pb() while(true) p(knife2); p(fork1); 進餐； v(knife2); v(fork1); 討論問題； pc() while(true) p(knife2); p(fork2); 進餐； v(knife2); v(fork2); 討論問題； pd() while(true) p(knife1); p(fork2); 進餐； v(knife1); v(fork2); 討論問題； 例題5生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個箱子里，現(xiàn)要用自動分揀系統(tǒng)把黑子和白子分開，

21、該系統(tǒng)由兩個并發(fā)執(zhí)行的進程組成。功能如下：進程A專門揀黑子，進程B專門揀白子；每個進程每次只揀一個子，當一個進程在揀子時不允許另一個進程去揀子。Begins：semaphore；s：=1；process A； processBBegin beginL1：P(s)； L2：P(s)；揀黑子； 揀白子；V(s)； V(s)；goto L1； goto L2；end； end；例題6如下鎖的實現(xiàn)方法存在什么缺點？如何改進？LOCK(X) UNLOCK(X) do while X=1 ; X=0;X=1 例題6答案:【解 】存在的缺點是 ： 當鎖是關(guān)閉時 ， 采用的是循環(huán)等待的方法 ，這樣的等待還是要

22、占用處理機的時間，應(yīng)該采用阻塞等待的方法。改進的鎖實現(xiàn)如下：LOCK(X) UNLOCK(X) if X . value=1 if not empty(X . L) insert( * , X.L); P=remove(X . L);Block ( * ) Wakeup(P) else X.Value=1 else X . Value=0 這里 X . value 是鎖的值 ， X 。L 是存放由于鎖 X 而阻塞的進程的隊列 。 insert( * , X.L)將當前進程的進程號插入到 X 。L ， remove(X . L) 是從 X . L 中移出一個進程號。例題7:多個進程對 信號量 S

23、 進行了 5 次 P 操作 ， 2 次 V 操作后 ， 現(xiàn)在信號量的值- 3 ，與信號量 S 相關(guān)的處于阻塞狀態(tài)的進程有幾個？信號量的初值是多少？【解】(1) 因為 S 的當前值是 -3 ，因此因為 S 處于阻塞狀態(tài)的進程有 3 個；(2) 因為每進行一次 P(S ) 操作 ， S 的值都減 1 ， 每執(zhí)行 1 次 V 操作 S 的值加 1 ， 故信量的初值為 -3+5-2=0 ;例題8:如果信號量的初值是，現(xiàn)在信號量的值是 - ，那么系統(tǒng)中的相關(guān)進程至少執(zhí)行了幾個 (S) 操作？ 與信號 量 S 相關(guān)的處于阻塞狀態(tài)的進程有幾個？如果要使信號量 S 的值大于 0 ，應(yīng)該進行怎樣的操作？【解】(

24、1) 因為每執(zhí)行一次 P 操作 S 的值減 1 ， 5- （ -5 ） =10 ，在這期間有可能有進程執(zhí)行 V操作，使 S 的值加 1 ，所以至少執(zhí)行了 10 次 P(S) ；(2) 5 個；(3) 6 個 V(S) 或 5 個以上。例題9:設(shè)與某資源相關(guān)聯(lián)的信號量初值為3，當前值為1，若M表示該資源的可用個數(shù)， N表示等待該資源的進程數(shù)，則M，N分別是（）。(2010年統(tǒng)考)A、0，1 B、1，0 C、1，2 D、2，0【答案】B【解析】信號量初值為3，表示系統(tǒng)中擁有資源個數(shù)為3，當前值為1，表明已經(jīng)分配出去兩個，還有一個沒有分配出去，則該資源可用個數(shù)為1，既然有可用的資源就不存在等待該資源

25、的進程，所以為0。例題10。( )是可以用來解決臨界區(qū)問題 A.銀行家算法 B.測試與設(shè)置（Test-and-Set） C.時間片輪轉(zhuǎn)算法 D.LRU算法 【答案】B例題11（2010統(tǒng)考）進程P0和P1的共享變量定義及其初值為 boolean flat2; int turn=0; flag0=FALSE;flat1=FALSE; 若進程P0和P1訪問臨界資源的類C代碼實現(xiàn)如下void P0()/P0進程 while(TURE); flat0=TRUE;turn=1; while(flag1&&turn=1); 臨界區(qū) flat0=FALSE; void P1()/P1進程 w

26、hile(TRUE)flat1=TRUE;turn=0; while(flag0&&turn=0); 臨界區(qū) flat1=FALSE; 例：則并發(fā)執(zhí)行進程P0和P1時產(chǎn)生的情況是（ ） A.不能保證進程互斥進入臨界區(qū)、會出現(xiàn)“饑餓”現(xiàn)象 B.不能保證進程互斥進入臨界區(qū)、不會出現(xiàn)“饑餓”現(xiàn)象 C.能保證進程互斥進入臨界區(qū)、會出現(xiàn)“饑餓”現(xiàn)象 D.能保證進程互斥進入臨界區(qū)、不會出現(xiàn)“饑餓”現(xiàn)象【答案】D例題12在操作系統(tǒng)中，P、V操作是一種 。A. 機器指令 B. 系統(tǒng)調(diào)用命令 C.作用控制命令 D. 低級進程通信原語【答案】D【解析】P、V操作交換的信息量小，是低級進程通信原語。

27、例題13用P、V操作管理臨界區(qū)時，信號量的初值定義為 。A. -1 B.0 C.1 D.任意值【答案】C【解析】臨界資源的訪問應(yīng)互斥進行，故信號量初值為1。例題14對于兩個并發(fā)進程，設(shè)互斥信號量為mutex，若mutex=0，則 。A.表示沒有進程進入臨界區(qū)B.表示有一個進程進入臨界區(qū)C.表示有一個進程進入臨界區(qū)，另一個進程等待進入D.表示有兩個進程進入臨界區(qū)【答案】B【解析】互斥信號量的初值為1：當有一個進程進入臨界區(qū)且沒有進程等待進入臨界區(qū)時，互斥信號量的值為0；當有一個進程進入臨界區(qū)且有一個進程等待進入臨界區(qū)時，互斥信號量的值為-1。例題15、有m個進程共享同一臨界資源，若使用信號量機制

28、實現(xiàn)對臨界資源的互斥訪問，則信號量值的變化范圍是 ?！敬鸢浮?至 -（m-1）【解析】臨界資源應(yīng)互斥使用，互斥信號量m的初值為1。當沒有進程使用臨界資源時，m值為1；有一個進程使用臨界資源且無進程等待使用該資源時，m值為0；有一個進程使用臨界資源且有一個進程等待使用該資源時，m值為-1；依次類推，最多可能有m-1個進程等待使用該臨界資源。例題16、設(shè)有4個進程共享一程序段，而每次最多允許2個進程進入該程序段，則信號量的取值范圍是 【答案】2至-2?！窘馕觥繛樵试S2個進程進入該程序段，信號量的初值應(yīng)為2；當有1個進程進入該程序段且無其他進程申請進入該程序段時，信號量值為1；當有2個進程進入該程序

29、段且無其他進程申請進入該程序段時，信號量值為0；當有2個進程進入該程序段且有2個進程申請進入該程序段時，信號量值為-2。例題17。在 OS 中引入管程的目的是什么？解 ：在 OS 中引入管程的目的是為了更簡便 、 更可靠地解決進程之間的同步 、 互斥問題 。在未引入管程之前 ， 進程間的同步 、 互斥問題是由程序員處理的 。 例如 ， 在臨界區(qū)的前后插入 P 、 V 操作。但是，由程序員處理同步、互斥問題有可能引入種種人為的錯誤。管程主要是管理對共享數(shù)據(jù)的操作和使用 ， 即把對共享數(shù)據(jù)互斥使用的控制這一任務(wù)從程序員身上 ， 交由編譯程序去處理 ， 這樣既方便了編程 ， 又不會產(chǎn)生人為的同步 、

30、 互斥上的錯誤。例題18、下述哪個選項不是管程的組成部分 。A.局部于管程的共享數(shù)據(jù)結(jié)構(gòu)B.對管程內(nèi)數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程C.管程外過程調(diào)用管程內(nèi)數(shù)據(jù)結(jié)構(gòu)的說明D.對局部于管程的數(shù)據(jù)結(jié)構(gòu)設(shè)置初始值的語句【答案】C【解析】管程由局部于管程的共享變量說明、對管程內(nèi)數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程以及對局部于管程的數(shù)據(jù)設(shè)置初始值的語句組成。例題19、每個管程管理 若干 臨界資源，進程要進入管程，其方法是調(diào)用特定的入口程序，管程內(nèi)部任何時刻只允許一個 進程處于活動狀態(tài)，活動進程調(diào)用管程內(nèi)的過程，不活動的管程處在條件變量上，條件變量類似于信號量，也有wait和signal操作。四、死鎖1、某計算機系統(tǒng)中有

31、8臺打印機，由K個進程競爭使用，每個進程最多需要3臺打印機。該系統(tǒng)可能會發(fā)生死鎖的最小值是（2009考研統(tǒng)考） A2 B3 C4 D52、在一個系統(tǒng)中，3個進程共享4臺設(shè)備，這些設(shè)備是臨界資源，假定每個進程至少需要兩臺設(shè)備，該系統(tǒng)是否會發(fā)生死鎖？（武漢理工大學2008）【答案】不會3、在 （ ） 的情況下，系統(tǒng)出現(xiàn)死鎖。A. 計算機系統(tǒng)發(fā)生了重大故障B. 有多個封鎖的進程同時存在C. 若干進程因競爭資源而無休止地相互等待他方釋放已占有的資源D. 資源數(shù)遠遠小于進程數(shù)或進程同時申請的資源數(shù)遠遠超過資源總數(shù)【答案】C【解析】死鎖是指多個進程因競爭系統(tǒng)資源或相互通信而處于永久阻塞狀態(tài)，若無外力作用，

32、這些進程都將無法向前推進。4、為多道程序提供的可共享資源不足時，可能出現(xiàn)死鎖。但是，不適當?shù)?_ 也可能產(chǎn)生死鎖。A. 進程優(yōu)先權(quán)B. 資源的線性分配C. 進程推進順序D. 分配隊列優(yōu)先權(quán)【答案】C【解析】產(chǎn)生死鎖的原因是系統(tǒng)資源不足及進程推進順序非法，故本題答案為C。5、產(chǎn)生死鎖的四個必要條件是：互斥、（ ）、循環(huán)等待和不剝奪。A. 請求與阻塞B. 請求與保持C. 請求與釋放D. 釋放與阻塞【答案】B6、為進程一次性分配其所需的資源是一種（）方法，它能使系統(tǒng)不發(fā)生死鎖。（武漢理工大學2008）A死鎖預(yù)防 B.死鎖檢測 C.死鎖避免 D.死鎖解除【答案】A7、銀行家算法在解決死鎖問題中是用于（

33、）。（武漢理工大學2008）A預(yù)防死鎖 B.避免死鎖 C.檢測死鎖 D.解除死鎖【答案】B8、在（）的情況下不可能產(chǎn)生死鎖的。（武漢理工大學2008）A多道程序環(huán)境中系統(tǒng)資源有限 B.使用同類臨界資源的并發(fā)進程隨機交替運行 C.規(guī)定進程一旦得到了需要的所有資源才投入運行 D.就緒隊列中已無等待的進程【答案】C9、考慮某個系統(tǒng)在如下時刻的狀態(tài)。（浙江大學2007），使用銀行家算法回答下面的問題：能否立刻被滿足?如安全，請給出一個安全序列。a. Need矩陣是怎樣的?b. 系統(tǒng)是否處于安全狀態(tài)?如安全，請給出一個安全序列。AllocationA B C DMaxA B C DAvailableA

34、B C DP0001200125 2 0P110001750P213542356P300140656c. 如果從進程P1發(fā)來一個請求(0,4,2,0)，這個請求能否立刻被滿足?如安全，請給出一個安全序列。a.Need矩陣如右圖b.此刻的安全性因為找到一個安全序列P0，P2，P1，P3，故當前系統(tǒng)處于安全狀態(tài)。c.P1發(fā)出請求(0,4,2,0)（1）進行兩個判斷：（0，4，2，0）小于P1的Need（0，7，5，0）； （0，4，2，0）小于當前的剩余Available（1，5，2，0）(2)假定分配給P1，修改P1的allocation及Need數(shù)據(jù)，還有系統(tǒng)的Available數(shù)據(jù)。P1的a

35、llocation變?yōu)椋? ，4 ，2 ，0），P1的Need變?yōu)椋?，3，3，0），系統(tǒng)的Available變?yōu)椋?，1，0，0）。（3） 利用安全性算法檢查此時系統(tǒng)是否安全。因為找到一個安全序列P0，P2，P1，P3，故系統(tǒng)處于安全狀態(tài)，可以將P1請求的資源立該分配給P1。10、死鎖和饑餓的主要區(qū)別是什么？ （武漢理工大學2006）饑餓與死鎖有一定聯(lián)系：二者都是由于競爭資源而引起的，但又有明顯差別，主要表現(xiàn)在如下幾個方面：(1) 從進程狀態(tài)考慮，死鎖進程都處于等待狀態(tài)，忙式等待(處于運行或就緒狀態(tài))的進程并非處于等待狀態(tài)，但卻可能產(chǎn)生饑餓現(xiàn)象；(2) 死鎖進程等待永遠不會被釋放的資源，饑餓

36、進程等待會被釋放但卻不會分配給自己的資源，表現(xiàn)為等待時限沒有上界(排隊等待或忙式等待)；(3) 死鎖一定發(fā)生了循環(huán)等待，而饑餓則不然。這也表明通過資源分配圖可以檢測死鎖存在與否，但卻不能檢測是否有進程饑餓(4) 死鎖一定涉及多個進程，而饑餓的進程可能只有一個。11、進行PO和P1的共享變量定義及其初值為：booleam flag2;Int turn=0;flag0=false; flag1=false;若進行P0和P1訪問臨界資源的類C代碼實現(xiàn)如下：void p0() / 進程p0      void p1 () / 進程p1 

37、60;                  while （TRUE） while （TRUE）flag0=TRUE; turn=1; flag1=TRUE; turn=0;While (flag1&&(turn=1) While (flag0&&(turn=0);臨界區(qū)； 臨界區(qū)；flag0=FALSE; flag1=FALSE;  則并發(fā)執(zhí)行進程PO和P1時產(chǎn)生的情況是（ ）A、不能保

38、證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象B、不能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象C、能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象D、能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象【答案】A 12、采用資源剝奪法可以解除死鎖，還可以采用 （ ）方法解除死鎖。A. 執(zhí)行并行操作B. 撤消進程C. 拒絕分配新資源D. 修改信號量【答案】B13、發(fā)生死鎖的必要條件有4個，要防止死鎖的發(fā)生，可以通過破壞這4個必要條件之一來實現(xiàn)，但破壞 （ ）條件是不太實際的。A. 互斥B. 不可搶占C. 部分分配D. 循環(huán)等待【答案】A14、資源的按序分配策略可以破壞 （ ） 條件。A. 互斥使用資源B.

39、占有且等待資源C. 非搶奪資源D. 循環(huán)等待資源【答案】D15、某系統(tǒng)中有3個并發(fā)進程都需要4個同類資源，則該系統(tǒng)必然不會發(fā)生死鎖的最少資源是（ ）A、9 B、10C、11 D、12【答案】C16、某系統(tǒng)中有11太磁帶機，X個進程共享此磁帶機設(shè)備，每個進程最多請求使用3臺，則系統(tǒng)必然不會死鎖的最大X值是（ ）A、4 B、5C、6 D、7【答案】B17、系統(tǒng)的資源分配圖在下列情況中，無法判斷是否處于死鎖的情況有（）出現(xiàn)了環(huán)路沒有環(huán)路每種資源只有一個，并出現(xiàn)環(huán)路每個進程節(jié)點至少有一條請求邊A、 B、C、 D、以上答案都不正確【答案】C18、下列關(guān)于死鎖的說法正確的有（）死鎖狀態(tài)一定是不安全狀態(tài)產(chǎn)生

40、死鎖的根本原因是系統(tǒng)資源分配不足和進程推進順序非法資源的有序分配策略可以破壞死鎖的循環(huán)等待條件采用資源剝奪法可以解除死鎖，還可以采用撤銷進程方法解除死鎖A、 B、C、 D、四個說法都對【答案】D19、【2011聯(lián)考】考了一個找安全序列的問題第3章 存儲器管理（1）4 非連續(xù)分配方式分頁管理方式分段管理方式段頁式管理方式4.1頁面與頁表頁面（用戶程序劃分） 把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁（page） 。從0開始編制頁號，頁內(nèi)地址是相對于0編址內(nèi)存空間 按頁的大小劃分為大小相等的區(qū)域，稱為塊或內(nèi)存塊（物理頁面，頁框） 在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可

41、以不相鄰接的物理塊中。由于進程的最后一頁經(jīng)常不滿一塊而形成了不可利用的碎片稱之為“頁內(nèi)碎片” 邏輯上相鄰的頁，物理上不一定相鄰地址結(jié)構(gòu)用戶程序的劃分是由系統(tǒng)自動完成的，對用戶是透明的。一般，一頁的大小為2的整數(shù)次冪，因此，地址的高位部分為頁號，低位部分為頁內(nèi)地址頁表將頁號和頁內(nèi)地址轉(zhuǎn)換成內(nèi)存地址，必須要有一個數(shù)據(jù)結(jié)構(gòu)，用來登記頁號和塊的對應(yīng)關(guān)系和有關(guān)信息。這樣的數(shù)據(jù)結(jié)構(gòu)稱為頁表。頁表的作用就是實現(xiàn)從頁號到物理塊號的地址映射。頁表內(nèi)容頁表包含以下幾個表項：頁號：登記程序地址空間的頁號。塊號：登記相應(yīng)的頁所對應(yīng)的內(nèi)存塊號其它：登記與存儲信息保護有關(guān)的信息。地址變換機構(gòu)地址變換機構(gòu)的任務(wù)是實現(xiàn)從邏輯

42、地址到物理地址的轉(zhuǎn)換。即把程序地址轉(zhuǎn)換成內(nèi)存地址，這個轉(zhuǎn)換過程是在程序執(zhí)行過程中完成的，是動態(tài)地址映射。在現(xiàn)代計算機系統(tǒng)中，由系統(tǒng)提供的地址映射硬件機構(gòu)來完成地址映射工作。例計算時要注意：若給出的地址字為16進制，則將其轉(zhuǎn)換為二進制，然后，根據(jù)頁長及程序地址字的長度，分別取出程序地址字的高幾位和低幾位就得到頁號及頁內(nèi)地址。如頁長為2K，程序地址字為16位，則高5位為頁號，低11位為頁內(nèi)地址。（如 09C4)若給出的地址字為10進制，則用公式： 程序地址字/頁長 商為頁號，余數(shù)為頁內(nèi)地址。如程序地址為8457， 頁長為4KB，則8457/4096可得：商為2，余數(shù)為256?？毂砗吐?lián)想存儲器在前述

43、的頁地址變換過程中有一個嚴重的問題，那就是每一次對內(nèi)存的訪問都要訪問頁表，頁表是放在內(nèi)存中的，也就是說每一次訪問內(nèi)存的指令至少要訪問兩次內(nèi)存，運行速度要下降一半。第一次訪問內(nèi)存中的頁表，從中找到指定頁的物理塊號，再將塊號與頁內(nèi)偏移量W拼接，形成物理地址第二次訪問內(nèi)存時，才是從第一次所得地址中獲得所需數(shù)據(jù)（獲向此地址中寫入數(shù)據(jù)）解決這個問題的一種方法是把頁表放在一組快速存儲器中（Cache），從而加快訪問內(nèi)存的速度。我們把這種快速存儲器組成的頁表稱為快表，把存放在內(nèi)存中的頁表稱為慢表?？毂碛纸新?lián)想存儲器（associative memory）或 TLB（Translation lookaside

44、 buffers）用以存放當前訪問的那些頁表項兩級頁表和多級頁表當頁表項很多時，僅采用一級頁表需要大片連續(xù)空間，可將頁表也分頁，并對頁表所占的空間進行索引形成外層頁表。由此構(gòu)成二級頁表。更進一步可形成多級頁表。 頁式存儲管理方案小結(jié)優(yōu)點：解決了碎片問題 便于管理可以使程序和數(shù)據(jù)存放在不連續(xù)的主存空間缺點：不易實現(xiàn)共享 不便于動態(tài)連接 頁表都有可能占用較大的存儲空間。要求有相應(yīng)的硬件支持，從而增加了系統(tǒng)成本，也增加了系統(tǒng)開銷（2） 分段管理方式引入段式管理方式主要是為了滿足用戶和程序員的需要方便用戶：用戶希望邏輯分段信息共享、信息保護、動態(tài)增長、動態(tài)連接分段系統(tǒng)基本原理分段用戶程序劃分 按程序自

45、身的邏輯關(guān)系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段段內(nèi)也從0開始編址，段內(nèi)地址是連續(xù)的。段的長度由相應(yīng)的邏輯信息組的長度決定，因而各段長度不等。邏輯地址：由段號和段內(nèi)地址組成內(nèi)存劃分 內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，稱為物理段，每個物理段由起始地址和長度確定內(nèi)存分配 以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少分配多少），但各段之間可以不連續(xù)存放段表段映射表。每個程序有一個段表 程序的每個段在表中占有一個表項，其中記錄了該段在內(nèi)存中的起始地址和段的長度?？煞旁趦?nèi)存中，也可放在寄存器中。 段表是用于實現(xiàn)從邏輯段到物

46、理內(nèi)存區(qū)的映射。段號012段首址段長度58K20K100K110K260K140K 3、 地址變換機構(gòu)段地址映射過程為：系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址和段表長度TL。取出段號S和段內(nèi)位移W。若S>TL，段號太大越界。根據(jù)段表始址找到段表，查找段號為S的表目，得到該段在內(nèi)存的起始地址。檢查段內(nèi)地址d是否起過該段的段長SL。若超過越界。把段首地址與段內(nèi)位移相加，形成內(nèi)存物理地址。同頁地址變換一樣，在段地址變換過程中，也有兩次訪問內(nèi)存的問題。為了加快訪問內(nèi)存的速度也可采用快速存儲器組成快表。段式存儲管理方案小結(jié)優(yōu)點： 便于動態(tài)申請內(nèi)存 管理和使用統(tǒng)一化 便于共享 便于動態(tài)鏈接缺點：產(chǎn)

47、生外部碎片（3） 段頁式存儲管理方式產(chǎn)生背景: 結(jié)合頁式段式優(yōu)點，克服二者的缺點基本原理地址變換過程基本原理用戶程序劃分按段式劃分（對用戶來講，按段的邏輯關(guān)系進行劃分；對系統(tǒng)講，按頁劃分每一段）段號段內(nèi)地址頁號頁內(nèi)地址邏輯地址內(nèi)存劃分按頁式存儲管理方案內(nèi)存分配以頁為單位進行分配段表：記錄了每一段的頁表始址和頁表長度頁表：記錄了邏輯頁號與內(nèi)存塊號的對應(yīng)關(guān)系（每一段有一個，一個程序可能有多個頁表）內(nèi)存分配管理：同頁式管理地址變換過程在段頁式系統(tǒng)中，為了獲得一條指令數(shù)據(jù)，須三次訪問內(nèi)存。1、訪問內(nèi)存中的段表，從中取得頁表始址2、訪問內(nèi)存中的頁表，從中取出該頁所在的物理塊號，將該塊號與頁內(nèi)地址一起形成

48、指令或數(shù)據(jù)的物理地址3、從物理地址中取出指令或數(shù)據(jù)?？毂砜偨Y(jié)固定分區(qū)的分配方式會產(chǎn)生內(nèi)零頭，因為是找出一個滿足作業(yè)要求的空閑分區(qū)分配給作業(yè)，大小不一定剛好合適，分區(qū)中有一部分存儲空間會被浪費。在可變式分區(qū)分配中，是按照作業(yè)的大小找出一個分區(qū)來分配如果大于作業(yè)申請的空間，則一分為二，剩下的一分部作為系統(tǒng)的空閑分區(qū)，有可能很小無法利用而成為外零頭。為了解決外零頭的問題，提出了離散的分配方式，在分頁式存儲管理中，存儲空間被分面與頁大小相等的物理塊，作業(yè)的大小不可能都是物理塊的整數(shù)倍，因此在作業(yè)的最后一頁中有可能有部分空間未被利用，屬于內(nèi)零頭。分段式存儲管理中，其內(nèi)存分配方式類似于動態(tài)分區(qū)的分配，因此

49、會產(chǎn)生外零頭。段頁式存儲管理中，其內(nèi)存分配方式類似于頁式的分配，因此會產(chǎn)生內(nèi)零頭。練習題1、在計算機系統(tǒng)存儲層次中，訪問速度最快的是（）。A. 高速緩存 B. 主存 C. 磁盤緩存 D.寄存器 【答案】D一般計算機系統(tǒng)中，存儲層次分為寄存器，主存，輔存三級。下列不屬于主存一級的是（）A. 高速緩存 B. 主存 C. 磁盤緩存 D. 磁盤 【答案】D2、磁盤緩存實際上占用了（）空間。（云南大學2008）A.高速緩存 B.主存 C.磁盤 D.可移動存儲介質(zhì)【答案】B【解析】磁盤緩存用于緩和磁盤的I/O速度遠低于對主存的訪問速度的矛盾，磁盤緩存實際上是從主存空間中劃出一塊區(qū)域，用來暫存頻繁使用的一部分磁盤數(shù)據(jù)和信息。2、在固定分區(qū)分配中，每個分區(qū)的大小是（）A.相同 B.隨作業(yè)大小變化 C.可以不同但預(yù)先固定 D.可以不同但根據(jù)作業(yè)大小固定【答案】C3 把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存的物理地址的過程稱做（）。 （武漢科技學院2008） A. 編譯 B連接 C. 運行