計(jì)算機(jī)操作系統(tǒng)復(fù)習(xí)題目(2)

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

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

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

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

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

6、mutex用于對(duì)readcount 這個(gè)臨界資源的互斥訪問(wèn)讀者： 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;寫(xiě)者： repeat P(wmutex); 寫(xiě); V(wmutex); until false;同步與互斥的解題思路分清哪些是互斥問(wèn)題（互斥訪問(wèn)臨界資源的），哪些是同

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

8、嚴(yán)格要求。 同步與互斥的解題步驟（1）確定進(jìn)程。包括進(jìn)程的數(shù)量、進(jìn)程的工作內(nèi)容，可以用流程圖描述。（2）確定同步互斥關(guān)系。根據(jù)是否使用的是臨界資源，還是處理的前后關(guān)系，確定同步與互斥，然后確定信號(hào)量的個(gè)數(shù)、含義，以及對(duì)信號(hào)量的P、V操作。（3）用類C語(yǔ)言描述同步或互斥算法。第二章 進(jìn)程同步舉例例題1：下面是兩個(gè)并發(fā)執(zhí)行的進(jìn)程，他們能正確運(yùn)行嗎？若不能，請(qǐng)舉例說(shuō)明，并改正。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是一個(gè)臨界資源，沒(méi)有保護(hù)。int x;Semaphore mutex=1;/訪問(wèn)X的互斥信號(hào)量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)者 消費(fèi)者問(wèn)題演變。一個(gè) buffer ，一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者只生產(chǎn)一個(gè)東西，消費(fèi)者只進(jìn)行一次消費(fèi)，即：生產(chǎn)者只進(jìn)行一次 putdata 操作，消費(fèi)者只進(jìn)行一次 getdata 操作。例題2

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

11、odd()從該緩沖區(qū)中取出一個(gè)奇數(shù)并用countodd（）統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；P3每次用geteven（）從該緩沖區(qū)中取出一個(gè)偶數(shù)并用counteven（）統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步互斥活動(dòng)，并說(shuō)明所定義的信號(hào)量的含義（要求用偽代碼描述）。例題4答案：【答案】（1）緩沖區(qū)是一互斥資源，因此設(shè)互斥信號(hào)量mutex。（2）同步問(wèn)題：P1、P2因?yàn)槠鏀?shù)的放置與取用而同步，設(shè)同步信號(hào)量odd；P1、P3因?yàn)榕紨?shù)的放置與取用而同步，設(shè)同步信號(hào)量even；P1、P2、P3因?yàn)楣蚕砭彌_區(qū)，設(shè)同步信號(hào)量empty。Semaphore mutex=1;Semaphore odd=0,even=0

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

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

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

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

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

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

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

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

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

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

22、占用處理機(jī)的時(shí)間，應(yīng)該采用阻塞等待的方法。改進(jìn)的鎖實(shí)現(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 而阻塞的進(jìn)程的隊(duì)列 。 insert( * , X.L)將當(dāng)前進(jìn)程的進(jìn)程號(hào)插入到 X 。L ， remove(X . L) 是從 X . L 中移出一個(gè)進(jìn)程號(hào)。例題7:多個(gè)進(jìn)程對(duì) 信號(hào)量 S

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

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

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

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

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

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

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

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

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

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

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

34、B C DP0001200125 2 0P110001750P213542356P300140656c. 如果從進(jìn)程P1發(fā)來(lái)一個(gè)請(qǐng)求(0,4,2,0)，這個(gè)請(qǐng)求能否立刻被滿足?如安全，請(qǐng)給出一個(gè)安全序列。a.Need矩陣如右圖b.此刻的安全性因?yàn)檎业揭粋€(gè)安全序列P0，P2，P1，P3，故當(dāng)前系統(tǒng)處于安全狀態(tài)。c.P1發(fā)出請(qǐng)求(0,4,2,0)（1）進(jìn)行兩個(gè)判斷：（0，4，2，0）小于P1的Need（0，7，5，0）； （0，4，2，0）小于當(dāng)前的剩余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） 利用安全性算法檢查此時(shí)系統(tǒng)是否安全。因?yàn)檎业揭粋€(gè)安全序列P0，P2，P1，P3，故系統(tǒng)處于安全狀態(tài)，可以將P1請(qǐng)求的資源立該分配給P1。10、死鎖和饑餓的主要區(qū)別是什么？ （武漢理工大學(xué)2006）饑餓與死鎖有一定聯(lián)系：二者都是由于競(jìng)爭(zhēng)資源而引起的，但又有明顯差別，主要表現(xiàn)在如下幾個(gè)方面：(1) 從進(jìn)程狀態(tài)考慮，死鎖進(jìn)程都處于等待狀態(tài)，忙式等待(處于運(yùn)行或就緒狀態(tài))的進(jìn)程并非處于等待狀態(tài)，但卻可能產(chǎn)生饑餓現(xiàn)象；(2) 死鎖進(jìn)程等待永遠(yuǎn)不會(huì)被釋放的資源，饑餓

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

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

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

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

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

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

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

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

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

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

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

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

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