操作系統(tǒng)總復習及相關(guān)習題

第一章   引論

名詞解釋

1操作系統(tǒng)

操作系統(tǒng)是管理和控制計算機系統(tǒng)內(nèi)各種硬件和軟件資源，有效地組織多道程序運行的系統(tǒng)軟件（或程序集合），是用戶與計算機之間的接口。

2管態(tài)

當執(zhí)行操作系統(tǒng)程序時，處理機所處的狀態(tài)

3目態(tài)

當執(zhí)行普通用戶程序時，處理機所處的狀態(tài)。

4多道程序設(shè)計

在這種設(shè)計技術(shù)下，內(nèi)存中能同時存放多道程序，在管理程序的控制下交替的執(zhí)行。這些作業(yè)共享CPU和系統(tǒng)中的其他資源。

5并發(fā)

是指兩個或多個活動在同一給定的時間間隔中進行。它是宏觀上的概念。

6并行

是指兩個或多個活動在同一時刻同時執(zhí)行的情況。

7吞吐量

在一段給定的時間內(nèi)，計算機所能完成的總工作量。

8分時

就是對時間的共享。在分時系統(tǒng)中，分時主要是指若干并發(fā)程序?qū)PU時間的共享。

9實時

表示“及時”或“既時”。

10系統(tǒng)調(diào)用

是用戶在程序中能以“函數(shù)調(diào)用”形式調(diào)用的、由操作系統(tǒng)提供的子功能的集合。每一個子功能稱作一條系統(tǒng)調(diào)用命令。它是操作系統(tǒng)對外的接口，是用戶級程序取得操作系統(tǒng)服務(wù)的唯一途徑。

11特權(quán)指令

指指令系統(tǒng)中這樣一些指令，如啟動設(shè)備指令、設(shè)置時鐘指令、中斷屏蔽指令和清內(nèi)存指令，這些指令只能由操作系統(tǒng)使用。

12命令解釋程序

其主要功能是接收用戶輸入的命令，然后予以解釋并且執(zhí)行。

13脫機I/O

是指輸入/輸出工作不受主機直接控制，而由衛(wèi)星機專門負責完成I/O，主機專門完成快速計算任務(wù)，從而二者可以并行操作。

14聯(lián)機I/O

是指作業(yè)的輸入、調(diào)入內(nèi)存及結(jié)果輸出都在cpu直接控制下進行。

15資源共享

是指計算機系統(tǒng)中的資源被多個進程所功用。例如，多個進程同時占用內(nèi)存，從而對內(nèi)存共享；它們并發(fā)執(zhí)行時對cpu進行共享；各個進程在執(zhí)行過程中提出對文件的讀寫請求，從而對磁盤進行共享等等。

簡答題

1什么是操作系統(tǒng)？它的主要功能是什么？

答：操作系統(tǒng)是控制和管理計算機系統(tǒng)內(nèi)各種硬件和軟件資源，有效地組織多道程序運行的系統(tǒng)軟件（或程序集合），是用戶與計算機之間的接口。操作系統(tǒng)的主要功能有5個方面，即存儲管理、處理機管理、設(shè)備管理、文件管理和用戶接口。

2推動操作系統(tǒng)形成和發(fā)展的主要動力是什么？

答：推動操作系統(tǒng)發(fā)展的因素很多，主要可歸結(jié)為兩大方面：硬件技術(shù)更新和應(yīng)用需求擴大伴隨計算機器件的更新?lián)Q代和計算機體系結(jié)構(gòu)的發(fā)展，促使操作系統(tǒng)的性能和結(jié)構(gòu)有了顯著發(fā)展。 應(yīng)用需求促進了計算機技術(shù)的發(fā)展，也促進了操作系統(tǒng)的不斷更新升級。

3操作系統(tǒng)的基本特征是什么？

答：操作系統(tǒng)的基本特征是并發(fā)、共享和不確定。并發(fā)性是指兩個或多個活動在同一給定的時間間隔中進行；共享是指計算機系統(tǒng)中的資源被多個進程所共用；不確定性是指系統(tǒng)中各種事件發(fā)生順序的不可預測性。

4多道程序和多重處理有何區(qū)別？

答：多道程序是作業(yè)之間自動調(diào)度執(zhí)行、共享系統(tǒng)資源，并不是真正的同時執(zhí)行多個作業(yè)；而多重處理系統(tǒng)配置多個cpu，能真正同時執(zhí)行多道程序。要有效使用多重處理，必須采用多道程序設(shè)計技術(shù)，而多道程序設(shè)計原則上不一定要求多重處理系統(tǒng)的支持。

5試說明多道程序設(shè)計和多任務(wù)系統(tǒng)之間的關(guān)系

答：多道程序設(shè)計是利用外設(shè)與cpu能夠并行處理的特性，在主存同時存放多個程序，使之在系統(tǒng)中交叉地使用cpu，從而提高系統(tǒng)資源的利用率。而多任務(wù)系統(tǒng)主要指多進程交叉使用cpu。多道程序隱含了多任務(wù)處理，但多任務(wù)系統(tǒng)中不一定有多道程序。因為一個程序也可以采用多任務(wù)處理機制。

6不同類型的操作系統(tǒng)提供不同的功能。假定有如下的應(yīng)用環(huán)境，請你為它們選擇適合的操作系統(tǒng)。

（1）飛機的導航，（2）辦公自動化系統(tǒng)，（3）航空訂票系統(tǒng)，（4）復雜的科學計算，（5）圖書檢索系統(tǒng)

答：（1）飛機的導航系統(tǒng)，應(yīng)采用硬實時操作系統(tǒng)

（2）辦公自動化系統(tǒng)，應(yīng)采用分時操作系統(tǒng)

（3）航空訂票系統(tǒng)，應(yīng)采用軟實時操作系統(tǒng)

（4）復雜的科學計算，應(yīng)采用批處理系統(tǒng)

（5）圖書檢索系統(tǒng)，應(yīng)采用軟實時操作系統(tǒng)

7什么是批處理系統(tǒng)，它有什么特征？

答：批處理系統(tǒng)：操作員把用戶提交的作業(yè)分類，把一批作業(yè)編成一個作業(yè)執(zhí)行序列，由專門編制的監(jiān)督程序自動依次處理。其主要特征是：用戶脫機使用計算機、成批處理、多道程序運行。

8什么是分時系統(tǒng)，它有什么特征？

答：分時系統(tǒng)：把處理機的運行時間分成很短的時間片，按時間片輪轉(zhuǎn)的方式，把處理機分配給各進程使用。其主要特征是：交互性、多用戶同時性、獨立性。

9什么是實時系統(tǒng)？它有什么特征？

答：實時系統(tǒng)：在被控對象允許時間范圍內(nèi)做出響應(yīng) 。其主要特征是：對實時信息分析處理速度要比進入系統(tǒng)快、要求安全可靠、資源利用率低。

10什么是處理機的核心態(tài)和用戶態(tài)？為什么要設(shè)置這兩種不同的狀態(tài)？

答：當執(zhí)行操作系統(tǒng)程序時，處理機處于核心態(tài)。它有較高的特權(quán)，可以執(zhí)行所有的指令，包括一般用戶程序中不能使用的特權(quán)指令，從而能對所有寄存器和內(nèi)存進行訪問，啟動i/o操作等。

用戶程序是在用戶態(tài)下執(zhí)行，它的權(quán)限較低，只能執(zhí)行指令集中非特權(quán)指令。（2分）

設(shè)置這兩種不同狀態(tài)的目的是為了保護操作系統(tǒng)程序（特別是其內(nèi)核部分），防止受到用戶程序的損害。

11系統(tǒng)調(diào)用與過程調(diào)用在功能及實現(xiàn)上有什么相同點和不同點？

答：相同點：兩者都由程序代碼構(gòu)成，可直接用高級程序設(shè)計語言（如C,C++和Perl語言）來編制；使用方式相同——以函數(shù)調(diào)用的形式出現(xiàn)，調(diào)用時傳送參數(shù)。

    不同點：①代碼層次不同，過程調(diào)用不屬于操作系統(tǒng)的一部分，而系統(tǒng)調(diào)用是操作系統(tǒng)的一部分。②運行狀態(tài)不同。過程調(diào)用只能在用戶態(tài)下運行，不能進入核心態(tài)，而系統(tǒng)調(diào)用是在核心態(tài)下運行的。③進入方式不同。過程調(diào)用在用戶程序中調(diào)用，并直接在用戶空間內(nèi)執(zhí)行；而系統(tǒng)調(diào)用可以在用戶程序中調(diào)用，但是在用戶程序中執(zhí)行到系統(tǒng)調(diào)用時，會產(chǎn)生異常事件。實現(xiàn)處理機狀態(tài)從用戶態(tài)到核心態(tài)的轉(zhuǎn)變，從而進入操作系統(tǒng)核心空間去執(zhí)行系統(tǒng)調(diào)用的代碼。

12試說明特權(quán)指令和系統(tǒng)調(diào)用之間的區(qū)別與聯(lián)系。

答：特權(quán)指令是一類只能在核心態(tài)下執(zhí)行的機器指令。而系統(tǒng)調(diào)用不是機器指令，它往往以函數(shù)調(diào)用的形式出現(xiàn)，實現(xiàn)操作系統(tǒng)提供的子功能，它是操作系統(tǒng)與用戶的編程接口 。在用戶程序中可以使用系統(tǒng)調(diào)用來獲得操作系統(tǒng)服務(wù)，在系統(tǒng)調(diào)用代碼中可以使用特權(quán)指令

第二章  進程和線程

名詞解釋

1順序性

是指順序程序所規(guī)定的每個動作都在上個動作結(jié)束后才開始的特性。

2封閉性

是指只有程序本身的動作才能改變程序的運行環(huán)境。

3可再現(xiàn)性

是指程序的執(zhí)行結(jié)果與程序運行的速度無關(guān)。

4進程

程序在并發(fā)環(huán)境中的執(zhí)行過程。

5互斥

在邏輯上本來完全獨立的進程，由于競爭同一個資源而產(chǎn)生的相互制約的關(guān)系。

6同步

是指進程間共同完成一項任務(wù)時直接發(fā)生相互作用的關(guān)系。也就是說，這些具有伙伴關(guān)系的進程在執(zhí)行次序上必須遵循確定的規(guī)律。

7臨界資源

一次僅允許一個進程使用的資源。

8臨界區(qū)

在每個進程中訪問臨界資源的那段程序。

9線程

線程是進程中實施調(diào)度和分派的基本單位。

10管程

管程是一種高級同步機制，一個管程定義一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程在其上執(zhí)行的一組操作，這組操作能使進程同步和改變管程中的數(shù)據(jù)。

11進程控制塊

進程控制塊是進程存在的唯一標識，它保存了系統(tǒng)管理和控制進程所必須的信息，是進程動態(tài)特性的集中表現(xiàn)。

12原語

指操作系統(tǒng)中實現(xiàn)一些具有特定功能的程序段，這些程序段的執(zhí)行過程是不可分割的，即其執(zhí)行過程不允許被中斷。

13就緒態(tài)

進程已經(jīng)獲得了除cpu之外的全部資源，等待系統(tǒng)分配cpu，一旦獲得cpu，進程就可以變?yōu)檫\行態(tài)。

14運行態(tài)

正在cpu上執(zhí)行的進程所處的狀態(tài)。在單cpu系統(tǒng)中，任何時候最多只能有一個進程處于運行狀態(tài)。

15阻塞態(tài)

又稱等待態(tài)，指正在運行的進程因等待某個條件發(fā)生而不能運行時所處的狀態(tài)。處于阻塞態(tài)的進程在邏輯上是不能運行的，即使cpu空閑，它也不能占用cpu。

16進程通信

是指進程間的信息交換。

17同步機制

同步機構(gòu)是負責處理進程之間制約關(guān)系的機制，即操作系統(tǒng)中負責解決進程之間協(xié)調(diào)工作的同步關(guān)系（直接制約關(guān)系），以及共享臨界資源的互斥關(guān)系（間接制約關(guān)系）的執(zhí)行機構(gòu)。

簡答題

1在操作系統(tǒng)中為什么要引入進程概念？

答:  由于多道程序并發(fā)執(zhí)行時共享系統(tǒng)資源，共同決定這些資源的狀態(tài)，因此系統(tǒng)中各程序在執(zhí)行過程中就出現(xiàn)了相互制約的新關(guān)系，程序的執(zhí)行出現(xiàn)“走走停?！钡男聽顟B(tài)。用程序這個靜態(tài)的概念已不能如實反映程序并發(fā)執(zhí)行過程中的這些特征。為此，人們引入了“進程（Process）”這一概念來描述程序動態(tài)執(zhí)行過程的性質(zhì)。

進程和程序是兩個完全不同的概念。然而，進程與程序之間存在密切關(guān)系，進程的功能是通過程序的運行得以實現(xiàn)的，進程活動的主體是程序。進程不能脫離開具體程序而獨立存在。

2有人說，一個進程是由偽處理機執(zhí)行的一個程序，這話對嗎？為什么？

答：對。

因為偽處理機的概念只有在執(zhí)行時才存在，它表示多個進程在單處理機上并發(fā)執(zhí)行的一個調(diào)度單位。因此，盡管進程是動態(tài)概念，是程序的執(zhí)行過程，但是，在多個進程并行執(zhí)行時，仍然只有一個進程占據(jù)處理機執(zhí)行，而其他并發(fā)進程則處于就緒或等待狀態(tài)。這些并發(fā)進程就相當于由偽處理機執(zhí)行的程序。

3試比較進程和程序的區(qū)別

答：（1）進程是一個動態(tài)的概念，而程序是一個靜態(tài)的概念，程序是指令的有序集合，無執(zhí)行含義，進程則強調(diào)執(zhí)行的過程。

（2）進程具有并行特征（獨立性、異步性），程序則沒有。

（3）不同的進程可以包含同一個程序，同一程序在執(zhí)行中也可以產(chǎn)生多個進程。

4進程的基本狀態(tài)有哪些？試描繪進程狀態(tài)轉(zhuǎn)換圖。

答：進程至少有三種基本狀態(tài)：運行狀態(tài)、就緒狀態(tài)和阻塞狀態(tài)（或等待狀態(tài)） 。進程狀態(tài)轉(zhuǎn)換如下圖：

5并發(fā)進程間的制約有哪兩種？引起制約的原因是什么？

答：并發(fā)進程所受的制約有兩種：直接制約和間接制約。

直接制約是由并發(fā)進程相互共享對方的私有資源所引起的；間接制約是由競爭共有資源而引起的。

6什么是進程間的互斥？什么是進程間同步？

答：進程間的互斥是指：一組并發(fā)進程中的一個或多個程序段，因共享某一共有資源而導致它們必須以一個不許交叉執(zhí)行的單位執(zhí)行，即不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)。

進程間的同步是指：異步環(huán)境下的一組并發(fā)進程因直接制約相互發(fā)送消息而進行相互合作、相互等待，是各進程按一定的速度執(zhí)行的過程。

7什么是臨界區(qū)和臨界資源？進程進入臨界區(qū)的調(diào)度原則是什么？

答：臨界資源——一次僅允許一個進程使用的資源

臨界區(qū)——在每個進程中訪問臨界資源的那段程序

一個進程進入臨界區(qū)的調(diào)度原則是：

① 如果有若干進程要求進入空閑的臨界區(qū)，一次僅允許一個進程進入

② 任何時候，處于臨界區(qū)內(nèi)的進程不可多于一個。如已有進程進入自己的臨界區(qū)，則其他所有試圖進入臨界區(qū)的進程必須等待

③ 進入臨界區(qū)的進程要在有限的時間內(nèi)退出，以便讓其他進程能及時進入自己的臨界區(qū)

④ 如果進程不能進入自己的臨界區(qū)，則應(yīng)讓出cpu，避免進程出現(xiàn)“忙等”現(xiàn)象.

8簡述信號量的定義和作用。P，V操作原語是如何定義的？

答：信號量一般是由兩個成員組成的數(shù)據(jù)結(jié)構(gòu)，其中一個成員是整型變量，表示該信號量的值，它與相應(yīng)資源的使用情況有關(guān)；另一個是指向PCB的指針。當多個進程都等待同一信號量時，它們就排成一個隊列，由信號量的指針項指出該隊列的隊首。（2分）

信號量通?？梢院唵畏从吵鱿鄳?yīng)資源的使用情況，它與P、V操作原語一起使用可實現(xiàn)進程的同步和互斥。（1分）

P,V操作原語有如下定義。

P(S)順序執(zhí)行下述兩個動作（1分）：

⑴信號量的值減1，即S=S-1;

⑵如果S>=0,則該進程繼續(xù)執(zhí)行。

如果S<0,則把該進程的狀態(tài)置為阻塞態(tài)，把相應(yīng)的PCB連入該信號量隊列的末尾，并放棄處理機，進行等待（直到其他進程在S上執(zhí)行V操作，把它釋放出來為止）。

V(S)順序執(zhí)行下述兩個動作（1分）：

⑴S值加1，即S=S+1;

⑵如果S>0,則該進程繼續(xù)運行；

如果S<=0,則釋放信號量隊列上的第一個PCB所對應(yīng)的進程（把阻塞態(tài)改為就緒態(tài)）,執(zhí)行V操作的進程繼續(xù)運行。

9什么是線程？它與進程有什么關(guān)系？

答：線程是進程中實施調(diào)度和分派的基本單位。

線程和進程之間有如下關(guān)系：

① 一個進程可以有多個線程，但至少有一個線程；而一個線程只能在一個進程的地址空間內(nèi)活動。

② 資源分配給進程，同一進程的所有線程共享該進程的所有資源。

③ 處理機分給線程，即真正在處理機上運行的是線程。

④ 線程在執(zhí)行過程中，需要協(xié)作同步。不同進程的線程間要利用消息通信的辦法實現(xiàn)同步。

10什么是管程？它由哪幾部分組成？有什么基本特性?

答：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程在其上執(zhí)行的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)。

一個管程由四個部分組成，它們是管程名稱、局部與管程的共享數(shù)據(jù)的說明、對數(shù)據(jù)進行操作的一組過程和對該共享數(shù)據(jù)賦初值的語句。

管程具有以下特性：

① 管程內(nèi)部的局部數(shù)據(jù)變量只能被管程內(nèi)定義的過程所訪問，不能被管程外面聲明的過程直接訪問

② 進程要想進入管程，必須調(diào)用管程內(nèi)的某個過程

③ 一次只能有一個進程在管程內(nèi)執(zhí)行，而其余調(diào)用該管程的進程都被掛起，等待該管程成為可用的。就是說，管程自身能有效地實現(xiàn)互斥。

綜合題

1如下圖所示的工作模型中，有三個進程p0,p1,p2和三個緩沖區(qū)B0,B1,B2. 進程之間借助于相鄰緩沖區(qū)進行消息傳遞：每個進程每次從緩沖區(qū)中取一條消息，經(jīng)加工處理后送入另一個緩沖區(qū)中，三個緩沖區(qū)分別可存放3,2,2個消息。初始時，僅緩沖區(qū)0有一個消息。試用P、V操作寫出三個進程之間的同步及互斥流程。

答：這是一個生產(chǎn)者/消費者問題，而且每個進程既是生產(chǎn)者，也是消費者。(2’)

為此，應(yīng)設(shè)置6個信號量：B0S1,B0S2,B1S1,B1S2,B2S1,B2S2,分別代表B0,B1,B2中是否有空緩沖和有數(shù)據(jù)。

B0S1,B0S2,B1S1,B1S2,B2S2:semaphore;

B0S1=2;B0S2=1;B1S1=2;B1S2=0;B2S1=2;B2S2=0;  (2’)

Cobegin  (`6’=2’*3)

P0 P1 P2

begin begin begin

P(B0S2) P(B1S2) P(B2S2)

從B0取一個數(shù)據(jù) 從B1取一個數(shù)據(jù) 從B2取一個數(shù)據(jù)

V(B0S2) V(B1S1) V(B2S1)

加工 加工 加工

P(B1S1) P(B2S1) P(B0S1)

將加工結(jié)果送B1 將加工結(jié)果送B2 將加工結(jié)果送B0

V(B1S2) V(B2S2) V(B0S2)

end end end

coend

這道題也可以增加互斥信號量，以便P0與P1之間互斥使用B0緩沖區(qū)，P1與P2之間互斥使用B1緩沖區(qū)，P2與P0之間互斥使用B0緩沖區(qū)。這里主要描述它們之間的同步關(guān)系。若考慮互斥共享緩沖區(qū)，請自己加上。

2設(shè)用三個隊列管理緩沖區(qū)池的使用情況，分別為空白緩沖隊列em，輸入緩沖隊列in，以及輸出緩沖隊列out。過程add_buf(type,numb)和take_buf(type,numb)分別用來把緩沖區(qū)numb插入type隊列和從type隊列中取出緩沖區(qū)numb。試描述進程從任一緩沖隊列中得到一個緩沖區(qū)的過程get_buf(type,numb)和釋放一個緩沖區(qū)numb進入緩沖隊列的過程put_buf(type,numb)。

答：假定用信號量s代表任一隊列的可用緩沖區(qū)個數(shù)。假定三個隊列的初值分別為n1,n2,n3。對任一隊列的操作必須互斥。因此再引入一個互斥使用任一隊列的信號量mutex，其初值為1。這里type代表隊列的類型，它的取值為輸入、輸出和空白。(4’)

當有進程希望從任一隊列取一個緩沖區(qū)時，過程get_buf(type,numb)的動作如下：

get_buf(type,numb)   (`3’)

begin

p(s)

p(mutex)

numb=take_buf(type,numb)

v(mutex)

end

當有進程希望向任一隊列送一個緩沖區(qū)時，過程put_buf(type,numb)的動作如下：

put_buf(type,numb)   (`3’)

begin

p(mutex)

add_buf(type,numb)

v(mutex)

v(s)

end. 

3設(shè)有一個售票廳，可容納100人購票。如果廳內(nèi)不足100人則允許進入，進入后購票，購票后退出。如果廳內(nèi)已有100人，則在廳外等候。試問：

1） 購票者之間是同步還是互斥？

用P、V操作表達購票者的工作過程。

解：1）購票者之間是互斥關(guān)系。(2’)

2） 一個售票廳可容納100人購票，說明最多允許100個購票者共享售票廳；可引入一個信號量empty，其初值為100。由于購票者必須互斥地進行購票，故應(yīng)再設(shè)一個mutex，其初值為1。(4’)

用P、V操作表達購票者的工作過程如下：(`4’)

empty,mutex:semaphore;

empty:=100; mutex:=1;

begin

p(empty)

p(mutex)

進入廳內(nèi)購票,購票后退出

v(empty)

v(mutex)

end.

4某招待所有100個床位，住宿者入住要先登記（在登記表上填寫姓名和床位號）．離去時要注銷登記（在登記表上刪去姓名和床位號）．請給出住宿登記及注銷過程的算法描述．

答：某招待所有100個床位，為了正確管理，引入一個信號量empty代表空床位數(shù)，初值為100；住宿者入住要先登記（在登記表上填寫姓名和床位號），顯然，登記表是一個臨界資源，必須互斥訪問，引入一個mutex，其初值為1。(4’)

住宿登記及注銷過程的算法描述如下：

住宿登記：(`3’)

begin

p(empty)  //檢查有無床位

p(mutex)  //申請登記

找出一個空床位將名字登入表中

v(mutex)

end

注銷過程：(`3’)

begin

p(mutex)   //申請退房

找出自己的登記項，并刪除該項的登記

v(mutex)

v(empty)

end.

5有一個閱覽室，共有100個座位。為了很好地利用它，讀者進入時必須先在登記表上進行登記。該表表目設(shè)有座位號和讀者姓名；離開時再將其登記項擦除。

試問：為描述讀者的動作，應(yīng)編寫幾個程序，應(yīng)設(shè)幾個進程、它們之間的關(guān)系怎樣？并請用P、V操作描述進程之間的同步算法。

解：為了描述閱覽室，用一個登記表來記錄其使用情況。表中共有100項。每當有讀者進入閱覽室時，為了正確地登記，各讀者應(yīng)互斥使用(1’)。為此設(shè)兩個信號量：mutex為互斥信號量，用來制約各讀者互斥地進行登記，其初值為1；empty為同步信號量，用來制約各讀者能同時進入閱覽室的數(shù)量，其初值為100  (2’)。

下面用兩個過程描述對表格應(yīng)執(zhí)行的動作：

登記過程：(`2’) 擦除過程：(`2’)

begin begin

P(empty) P(mutex)

P(mutex) 找到自己的登記項擦除

找到一個登記項登記 V(mutex)

V(mutex) V(empty)

end end

為了正確地描述讀者的動作，可以將讀者看成進程。若干讀者希望進入閱覽室時，調(diào)用登記過程，退出閱覽室時，調(diào)用擦除過程(1’)。

可見，一個程序可對應(yīng)多個讀者?？稍O(shè)的進程數(shù)由讀者數(shù)決定，其動作如下：(`2’)

begin

調(diào)用登記過程

進入閱覽室閱讀

準備退出

調(diào)用擦除過程

end.

6一條河上架設(shè)了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過；但不允許河對岸的兩個人同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。

解：假設(shè)一座橋由N個橋墩，也即最多允許有N個人同向過河，用一個計數(shù)器R記錄同時過河的人數(shù)(2’)。用S1信號量保護計數(shù)器，其初值為1，R的初值為0；互斥使用橋的信號量用S表示，其初值為1。(2’)

同步算法描述如下：

procedure goriver()

begin

L:P(S1); //為同時過河,申請對計數(shù)器計數(shù)

  If R>N begin V(S1); goto L; end  //同方向過河的人站滿橋墩時,重新申請計數(shù)

  R=R+1;

  If R==1 P(S); //申請過河

V(S1);   //釋放計數(shù)器的使用權(quán)           (3’)

占有一個橋墩,并順序過河到對岸;

P(S1);

  R=R-1;

  If R==0 V(S); //如果已經(jīng)無同向的人過河,釋放占用權(quán)

V(S1);                                                       (3’)

end.

7在一個飛機訂票系統(tǒng)中，多個用戶共享一個數(shù)據(jù)庫。各用戶可以同時查詢信息，若有一個用戶要訂票，須更新數(shù)據(jù)庫時，其余所有用戶都不可以訪問數(shù)據(jù)庫。請用P,V操作設(shè)計一個同步算法，實現(xiàn)用戶查詢與訂票功能。要求：當一個用戶訂票而需要更新數(shù)據(jù)庫時，不能因不斷有查詢者到來而使其長時間等待。利用信號量機制保證其正常執(zhí)行。

解：這是典型的讀者——寫者問題，查詢信息的用戶是讀者，訂票用戶是寫者，并且要求寫者優(yōu)先。(2’)

變量說明：(`2’)

計數(shù)變量

rc——正在運行的查詢者進程數(shù)目，初值為0.

信號量

Sw——控制訂票者進程的活動，初值為1.

Src——互斥使用rc變量，初值為1.

S——當訂票者到達時封鎖后續(xù)的讀進程，初值為1.

讀者進程

P(S)

P(Src)

rc=rc+1

if (rc==1) P(Sw)

V(Src)

V(S)             (2’)

查詢庫當中的信息

P(Src)

rc=rc-1;

if (rc==0) V(Sw)

V(Src)           (2’)

寫者進程  (`2’)

P(S)

P(Sw)

更新數(shù)據(jù)庫內(nèi)容

V(Sw)

V(S)

8某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下列問題：

(1)用PV操作管理這些并發(fā)進程時，應(yīng)怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。

(2)根據(jù)所定義的信號量，把應(yīng)執(zhí)行的PV操作填入下述空格中，以保證進程能夠正確地并發(fā)執(zhí)行。

COBEGIN PROCESS PI(I=1，2，……)

begin

進入售票廳；

購票；

退出；

end

COEND

(3)若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)。

答：(1)定義一信號量S，初始值為20。 (1’)

意義：(`3’=1’*3)

S>0 S的值表示可繼續(xù)進入售票廳的人數(shù)

S=0 表示售票廳中已有20名顧客(購票者)

S<0 |S|的值為等待進入售票廳的人數(shù)

(2)上空格為P(S)  (2’) ；下空格為V(S) (2’)

(3)S的最大值為20  (1’ )；S的最小值為20－n (1’ )

9在公共汽車上，司機和售票員各行其職，司機負責開車和到站停車；售票員負責售票和開門關(guān)門，當售票員關(guān)好車門后，駕駛員才能開車行使。試用P/V操作實現(xiàn)司機與售票員間的同步。

解答：semaphore mutex1=0,mutex2=0;  (2’)

  main(){

    cobegin

        driver()

        busman()

coend

}            (2’)

driver(){

    while(true){

    p(mutex1)

    啟動公共汽車

    正常開車

    到站停車

    v(mutex2)

}

}           (3’)

busman(){

    while(true){

    關(guān)車門

    v(mutex1)

    售票

    p(mutex2)

    開車門

    上下乘客

}

}            (3’)

10并發(fā)問題：設(shè)有兩個優(yōu)先級相同的進程p1, p2如下。令信號s1, s2的初值為0，已知z=2，試問p1, p2并發(fā)運行結(jié)束后x=? y=? z=?

   進程p1              進程p2

   y := 1                x := 1

   y := y+2              x := x+1

   v(s1)                 p(s1)

   z := y+1              x := x+y

   p(s2)                 v(s2)

   y := z+y              z := x+z

解答：（分析過程略 2’）從結(jié)果來看，兩個進程無論誰先誰后，結(jié)果都是一樣的。(2’)

    x = 5;  y = 12;  z = 9  (6’)

11 試用信號量機制來描述下述前趨圖

解答：首先定義信號量S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都為0，分別表示相對應(yīng)的進程是否完成：(2’)

COBEGIN   (`8’=1’*8)

Process M1:

begin

     V(S12)

     V(S13)

     V(S14)

  end

Process M2:

begin

     P(S12)

     V(26)

  end

Process M3:

begin

     P(S13)

     V(S36)

     V(S38)

  end

Process M4:

begin

     P(S14)

     V(S47)

  end

Process M5:

begin

     V(S57)

  end

Process M6:

begin

     P(S26)

     P(S36)

  end

Process M7:

begin

     P(S47)

     P(S57)

     P(S78)

  end

Process M8:

begin

     P(S38)

     P(S78)

  end

  COEND

12

試用信號量機制來描述下述前趨圖

解答：首先定義信號量S12,S13,S24,S25,S56,S46,S36的初值都為0，分別表示相對應(yīng)的進程是否完成(2’)：

COBEGIN   (`6’=1’*6)

Process M1:

begin

     V(S12)

     V(S13)

  end

Process M2:

begin

     P(S12)

     V(24)

     V(25)

  end

Process M3:

begin

     P(S13)

     V(S36)

  end

Process M4:

begin

     P(S14)

     V(S46)

  end

Process M5:

begin

      P(S25)

V(S56)

  end

Process M6:

begin

      P(S36)

P(S46)

      P(S56)

  end

  COEND

13設(shè)系統(tǒng)有三個并發(fā)進程R,C,P，共享一個能存放n個數(shù)據(jù)的環(huán)形緩沖區(qū)buf。進程R負責從輸入設(shè)備上讀數(shù)據(jù)，每讀一個后把它存放在緩沖區(qū)buf的一個單元中；進程C負責從緩沖區(qū)讀數(shù)據(jù)并進行處理，之后將處理結(jié)果再送入緩沖區(qū)的一個單元中；進程P負責從緩沖區(qū)讀進程C處理的結(jié)果并打印。請用P、V操作為三進程的正確執(zhí)行寫出同步算法。

解答：解決同步問題需設(shè)一個互斥信號量mux，用于控制三個進程互斥使用緩沖區(qū)，初值為1；再設(shè)三個同步信號量，用于控制對緩沖區(qū)的空閑數(shù)量和不同數(shù)據(jù)個數(shù)的記錄。S0表示緩沖區(qū)空閑個數(shù)，初值為n；S1表示緩沖區(qū)中輸入數(shù)據(jù)的個數(shù)，初值為0；S2表示緩沖區(qū)中輸出數(shù)據(jù)的個數(shù)，初值為0。(4’)

算法描述如下：(`6’=2’*3)

  進程R            進程C              進程P

  L1:               L2:                 L3:

P(S0)              P(S1)              P(S2)

P(mux)             P(mux)             P(mux)

讀一個數(shù)據(jù)         從緩沖區(qū)中取一個   從緩沖區(qū)中讀

送緩沖區(qū)           數(shù)據(jù)處理后放回去   輸出數(shù)據(jù)

V(mux)             V(mux)            V(mux)

V(S1)              V(S2)              V(S0)  打印

gotoL1:            gotoL2:             gotoL3:

第三章  死鎖

名詞解釋

1死鎖

是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發(fā)的事件而無限期地僵持下去的局面。

2饑餓

在系統(tǒng)中，每個資源占有者都在有限時間內(nèi)釋放它所占有的資源，但資源中存在某些申請者由于某種原因卻永遠得不到資源的一種錯誤現(xiàn)象。

3死鎖防止

要求進程申請資源時遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個必要條件中的一個或幾個，保證系統(tǒng)不會進入死鎖狀態(tài)。

4死鎖避免

對進程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查，并根據(jù)檢查結(jié)果決定是否進行資源分配。就是說，在資源分配過程中若預測有發(fā)生死鎖的可能性，則加以避免。這種方法的關(guān)鍵是確定資源分配的安全性。

5安全序列

針對當前分配狀態(tài)來說，系統(tǒng)至少能夠按照某種次序為每個進程分配資源（直至最大需求），并且使他們依次成功地運行完畢，這種進程序列{p1,p2,…,pn}就是安全序列。

簡答題

1計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是什么?死鎖發(fā)生的四個基本條件是什么？

答: 計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是：資源有限且操作不當 。死鎖發(fā)生的四個基本條件有互斥條件、請求保持條件（占有且等待條件）、非剝奪條件（不可搶占條件）和環(huán)路條件（循環(huán)等待條件） 。

2簡述發(fā)生死鎖的四個必要條件?

答： 四個必要條件是：互斥條件、占有且等待條件（請求保持條件）、不可搶占條件（非剝奪條件）和循環(huán)等待條件（環(huán)路條件）。

互斥條件——某個資源在一段時間內(nèi)只能由一個進程占有，不能同時被兩個及其以上的進程占有。

占有且等待條件——進程至少已經(jīng)占有一個資源，但又申請新的資源。

不可搶占條件——一個進程所占有的資源再用完之前，其他進程不能強行奪走資源，只能由該進程用完之后主動釋放。

循環(huán)等待條件——存在一個進程等待序列{P1,P2,…,Pn}，其中，P1等待P2所占有的某個資源，P2等待P3所占有的某個資源，……，而Pn等待P1所占有的某個資源，從而形成一個進程循環(huán)等待。

3什么是死鎖？解決死鎖的方法一般有那幾種?

答: 死鎖是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發(fā)的事件而無限期地僵持下去的局面。

解決死鎖問題的一般方法為：死鎖的預防、死鎖的避免、死鎖的檢測和恢復。

4死鎖預防的基本思想是什么?死鎖避免的基本思想是什么?

答:死鎖預防的基本思想是:要求進程申請資源是遵循某種協(xié)議,從而打破產(chǎn)生思索的四個必要條件中的一個或幾個,保證系統(tǒng)不會進入死鎖狀態(tài). 

死鎖避免的基本思想是:對進程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查,并根據(jù)檢查結(jié)果決定是否進行資源分配.就是說,在資源分配過程中若預測有發(fā)生死鎖的可能性,則加以避免.這種方法的關(guān)鍵是確定資源分配的安全性. 

5什么是死鎖的安全序列?何謂系統(tǒng)是安全的？

答：進程的安全序列{P1,P2,…,PN}是這樣組成的：若對于每個進程Pi（1<=I<=n），它需要的附加資源可以被系統(tǒng)中當前可用資源加上所有進程Pj（j<i）當前占有資源之和所滿足，則{ P1,P2,…,PN }為一個安全序列。

“系統(tǒng)是安全的”是指系統(tǒng)中的所有進程能夠按照某種次序分配資源，并且依次運行完畢。即系統(tǒng)中的進程處于安全序列中。

6資源按序分配法為什么能夠預防死鎖？

證明：采用反證法來證明。

若存在循環(huán)等待，設(shè)在環(huán)路上的一組進程為{P0,P1,P2,…,Pn}，這里Pi等待進程Pi+1占有資源Ri（下角標取模運算，從而，Pn等待p0占有的資源）。由于Pi+1占有資源Ri,又申請資源Ri+1,從而一定存在F(i)<F(i+1), 該式對所有的i都成立。于是就有：

        F(R0)<F(R1)<…<F(Rn)<F(R0)

由傳遞性得到：

        F(R0)<F(R0)

顯然，這是不可能的，因而，上述假設(shè)不成立，表明不會出現(xiàn)循環(huán)等待條件。

7死鎖和“饑餓”之間的主要差別是什么?

答：死鎖：多個并發(fā)進程相互等待對方占用的資源而產(chǎn)生的錯誤現(xiàn)象。

餓死：在系統(tǒng)中，由于系統(tǒng)采用的資源分配算法不當，雖然每個資源占有者都在有限時間內(nèi)釋放它所占的資源，但仍然使一些進程永遠得不到資源的一種錯誤現(xiàn)象。

綜合題

1設(shè)系統(tǒng)中有三種類型的資源（A,B,C）和五個進程（P1,P2,P3,P4,P5）,A資源的數(shù)量為17，B資源的數(shù)量為5，C資源的數(shù)量為20。在T0時刻系統(tǒng)狀態(tài)如表3-9所試。系統(tǒng)采用銀行家算法來避免死鎖。

①T0時刻是否為安全狀態(tài)？若試，請給出安全序列。

②在T0時刻，若進程P2請求資源（0，3，4），能否實現(xiàn)資源分配？為什么？

③在②的基礎(chǔ)上，若進程P4請求資源（2，0，1），能否實現(xiàn)資源分配？為什么?

④在③的基礎(chǔ)上，若進程P1請求資源（0，2，0），能否實現(xiàn)資源分配？為什么?

表3-9 T0時刻系統(tǒng)狀態(tài)

進程 最大資源需求量  已分配資源數(shù)量 系統(tǒng)剩余資源數(shù)量

A     B     C  A     B     C  A     B     C

P1  5     5      9  2     1      2  2     3      3

P2  5     3      6  4     0      2

P3  4     0     11  4     0      5

P4  4     2      5  2     0      4

P5  4     2      4  3     1      4

解：

①T0時刻是安全狀態(tài)，因為存在一個安全序列{P4,P5,P1,P2,P3}  (2’)

②不能實現(xiàn)資源分配，因為所剩余的資源數(shù)量不夠。  (2’)

③可以分配。當分配完成后，系統(tǒng)剩余的資源向量為（0，3，2），這時，仍可找到一個安全序列{P4,P5,P1,P2,P3}  (3’)

④不能分配。如果分配的話，則系統(tǒng)剩余的資源向量為（0，1，2），這時無法找到一個安全序列。(3’)

2在銀行家算法中，系統(tǒng)有5個進程和3個資源。若出現(xiàn)以下資源分配情況：

進程 資源最大請求 已分配資源

p0 7, 5, 3 0, 1, 0

p1 3, 2, 2 2, 1, 0

p2 9, 0, 2 3, 0, 2

p3 2, 2, 2 2, 1, 1

p4 4, 3, 3 0, 0, 2

系統(tǒng)剩余資源數(shù)量為(3,2,2)。

1） 該狀態(tài)是否安全(給出詳細的檢查過程)?

2） 如果進程依次有如下資源請求

p1:資源請求Request(1,0,2)?

p4:資源請求Request(3,3,0)?

p0:資源請求Request(0,1,0)?

則系統(tǒng)如何進行資源分配，才能避免死鎖？

解:

1)該系統(tǒng)狀態(tài)是否安全,主要看能否找到一個進程完成序列.若能找到,系統(tǒng)只要按照這個序列為進程分配資源,所有進程就都可順利完成;若找不到,系統(tǒng)狀態(tài)就是不安全的.為此,可先求出進程的剩余請求矩陣.

進程 資源最大需求 已分配資源 剩余資源請求

P0 7, 5, 3 0, 1, 0 7, 4, 3

P1 3, 2, 2 2, 1, 0 1, 1, 2

P2 9, 0, 2 3, 0, 2 6, 0, 0

P3 2, 2, 2 2, 1, 1 0, 1, 1

P4 4, 3, 3 0, 0, 2 4, 3, 1

系統(tǒng)剩余資源向量A=(3,2,2)，在進程剩余資源請求矩陣中找，是否有一行，其值都小于或等于A.若有，選進程P1，滿足它的全部資源請求，它在有限時間內(nèi)能釋放全部資源，并標記它為完成使系統(tǒng)剩余資源向量A=(5,3,2).之后再重復上述過程，從而找到了一個進城完成序列為：P1,P3,P4,P2,P0   (2’)。由此可見，系統(tǒng)狀態(tài)是安全的(2’)。

2）p1:資源請求Request(1,0,2)時，由1）可知，可以立即滿足它，使得A=(2,2,0),P1的分配向量為(3,1,2)，其剩余向量變?yōu)?0,1,0).  (2’)

p4:資源請求Request(3,3,0)時，由于系統(tǒng)剩余資源向量A=(2,2,0)，顯然不能滿足它的請求，因為系統(tǒng)剩余資源向量A小于P4的請求  (2’)

p0:資源請求Request(0,1,0)時，由于系統(tǒng)剩余資源向量A=(2,2,0)，若滿足它的請求，使得系統(tǒng)剩余資源向量A=(2,1,0)。之后，系統(tǒng)仍可以找到一個進程完成序列P1,P4,P0,P4,P2。故可以滿足它的請求。  (2’)

3系統(tǒng)有同類資源10個，進程p1、p2和p3需要該類資源的最大數(shù)量分別為8，6，7。它們使用資源的次序和數(shù)量如下圖所示。

1） 試給出采用銀行家算法分配資源時，進行第5次分配后各進程的狀態(tài)及各進程占用資源情況。

2） 在以后的申請中，那次的申請可以得到最先滿足?給出一個進程完成序列。

次序 進程 申請量 次序 進程 申請量

1 P1 3 5 P2 2

2 P2 2 6 P1 3

3 P3 4 7 P3 3

4 P1 2 8 P2 2

解：1）計算第5次分配后進程的狀態(tài)和占用資源情況：(`5’=1’*5)

① p1申請3個，滿足，系統(tǒng)還剩7個

②p2申請2個，滿足（因為系統(tǒng)的7個可以使p2運行完），系統(tǒng)還剩5個

③p3申請4個，因為若滿足它的請求，可能使以后的任何進程都不能運行完，故p3等待

④p1申請2個，滿足（系統(tǒng)還剩5個可以滿足p1的最大請求），系統(tǒng)還剩3個

⑤ p2申請2個，不能滿足，等待。此時系統(tǒng)的分配情況如下：

p1分配5個后正在運行，p2分配2個后等待分配2個，p3等待分配4個，系統(tǒng)還剩3個。

2）p1接著運行，p1申請3個可滿足(2’)。P1運行完成后，釋放資源，使系統(tǒng)的資源數(shù)量變?yōu)?個。首先將p3喚醒，滿足它的4個資源，系統(tǒng)還剩4個，可以喚醒p2，滿足它的2個請求。系統(tǒng)還剩2個。

P3申請3個，不能滿足，等待。

P2申請2個，系統(tǒng)滿足它，p2接著運行；p2完成，釋放資源，使系統(tǒng)資源變?yōu)?個。系統(tǒng)喚醒p3，滿足它的資源請求，最終p3完成，釋放資源，使資源數(shù)量恢復為10個。

找到的進程完成序列為p1,p2,p3。 (3’)

4設(shè)系統(tǒng)中有150個可用的同類資源。在某時刻系統(tǒng)中的進程已獲得的資源和最大請求資源如下所示，請用銀行家算法分別判斷完成下列請求時，系統(tǒng)是否安全？若安全，請給出進程的完成序列。如不安全，請說明原因。

  進程     最大需求量     當前已分配量

   p1          70              25

   p2          60              40

   p3          60              45

   p4          60               0

(1) 進程p4當前請求25個資源；

(2) 之后p4又提出35個資源的請求。

解答：系統(tǒng)當前剩余資源量為：150 – 25 – 40 – 45 = 40  (2’)

(1) 可以滿足(2’)，假定先分配p4的25個資源，系統(tǒng)還剩15個。將這15個資源可先分配給p3，p3達到最大請求，釋放60個；之后可以分配給其他任何進程，系統(tǒng)中的進程都能順利完成。由此可見，p2請求的25個資源可以滿足，且能找到完成序列：p3，p1，p2，p4，…(4’)

(2) 當p4再提出35個資源請求時，系統(tǒng)還剩15，顯然不能滿足它的請求，讓其阻塞等待。(2’)

5系統(tǒng)中有五個進程，分別為p1\p2\p3\p4\p5，四類資源分別為r1\r2\r3\r4。某一時刻，系統(tǒng)剩余資源向量A=(1，2，3，0)。

（1） 用銀行家算法試判斷系統(tǒng)當前狀態(tài)是否安全？

（2） 當進程p3提出對資源r3的剩余請求時，能否滿足她？

（3） 系統(tǒng)初始配置的各類資源分別為多少？

  ，   .

解答：系統(tǒng)剩余資源向量 A=(1, 2, 3, 0) ?，F(xiàn)在需求出各進程的剩余資源請求矩陣:

   (2’)

(1) 詳細步驟省略。由于系統(tǒng)存在一個進程完成的安全序列P1\P3\P4\P2\P5(2’)，故系統(tǒng)狀態(tài)是安全的(2’)。

(2) 進程P3提出對資源R3的剩余請求為1，由于系統(tǒng)剩余資源向量A=(1,2, 3, 0)，故可以假定分配給它。如果能找到一個安全序列，就可以真正進行分配。當分配給P3一個資源時，系統(tǒng)剩余資源向量A=(1 ,2 ,2 , 0)。由此可見，仍然可以找到一個與(1)相同的安全序列。故可以滿足P3的請求。(3’)

(3) 系統(tǒng)初始配置的各類資源分別為(3 ,9 , 12 , 12 )。(1’)

               第四章  調(diào)度

名詞解釋

1作業(yè)

用戶在一次上機過程中要求計算機系統(tǒng)所做工作的集合。

2周轉(zhuǎn)時間

是指從作業(yè)進入系統(tǒng)開始，到作業(yè)退出系統(tǒng)所經(jīng)歷的時間。

3響應(yīng)時間

是分時系統(tǒng)的一個技術(shù)指標，指從用戶輸入命令到系統(tǒng)對命令開始執(zhí)行和顯示所需要的時間。

4作業(yè)調(diào)度

作業(yè)調(diào)度的主要任務(wù)是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)換。

5進程調(diào)度

也稱低級調(diào)度程序，它完成進程從就緒狀態(tài)到運行狀態(tài)的轉(zhuǎn)化。實際上，進程調(diào)度完成一臺物理的cpu轉(zhuǎn)變成多臺虛擬（或邏輯）的cpu的工作。

6交換調(diào)度

是基于系統(tǒng)確定的某個策略，將主存中處于等待狀態(tài)或就緒狀態(tài)的某個或某些進程交換到外存交換區(qū)中，以便將外存交換區(qū)上具備運行條件的進程換入主存，準備執(zhí)行。引入交換調(diào)度的目的是為了解決主存緊張和提高主存的利用效率。

7剝奪式調(diào)度

當一個進程正在執(zhí)行時，系統(tǒng)基于某種策略強行將處理機從占有者進程剝奪而分配給另一個進程的調(diào)度。這種調(diào)度方式系統(tǒng)開銷大，但系統(tǒng)能及時響應(yīng)請求。

8非剝奪式調(diào)度

系統(tǒng)一旦把處理機分配給某個進程之后，該進程一直運行下去，直到該進程完成或因等待某個事件發(fā)生時，才將處理機分配給其他進程。這種調(diào)度方式實現(xiàn)簡單，系統(tǒng)開銷小，但系統(tǒng)性能不夠好。

簡答題

1作業(yè)由哪幾部分組成？各有什么功能？

答：作業(yè)由三部分組成：程序、數(shù)據(jù)和作業(yè)說明書。

程序和數(shù)據(jù)完成用戶所要求的業(yè)務(wù)處理工作，作業(yè)說明書則體現(xiàn)用戶的控制意圖。

2試比較作業(yè)和進程的區(qū)別

答：一個進程是一個程序?qū)δ硞€數(shù)據(jù)集的執(zhí)行過程，是分配資源的單位。作業(yè)是用戶需要計算機完成某項任務(wù)，而要求計算機所做工作的集合。一個作業(yè)的完成要經(jīng)過作業(yè)提交、作業(yè)收容、作業(yè)執(zhí)行和作業(yè)完成4個階段。而進程是已提交完畢的程序所執(zhí)行過程的描述，是資源分配的基本單位。 

其主要區(qū)別關(guān)系如下： 

（1）作業(yè)是用戶向計算機提交任務(wù)的任務(wù)實體。在用戶向計算機提交作業(yè)之后，系統(tǒng)將它放入外存中的作業(yè)等待隊列中等待執(zhí)行。而進程則是完成用戶任務(wù)的執(zhí)行實體，是向系統(tǒng)申請分配資源的基本單位。任一進程，只要它被創(chuàng)建，總有相應(yīng)的部分存在內(nèi)存中。

（2）一個作業(yè)可由多個進程組成。且必須至少由一個進城組成，但反過來不成立。

（3）作業(yè)的概念主要用在批處理系統(tǒng)中。像UNIX這樣的分時系統(tǒng)中，則沒有作業(yè)概念。則進程的概念則用在幾乎所有的多道程序系統(tǒng)中。

3高級調(diào)度與低級調(diào)度的主要功能是什么？為什么要引入中級調(diào)度？

答:高級調(diào)度的主要功能是根據(jù)一定的算法,從輸入的一批作業(yè)中選出若干作業(yè),分配必要的資源,如內(nèi)存、外設(shè)等，為它建立相應(yīng)的用戶作業(yè)進程和為其服務(wù)的系統(tǒng)進程（如輸入/輸出進程），最后把它們的程序和數(shù)據(jù)調(diào)入內(nèi)存，等待進程調(diào)度程序?qū)ζ鋱?zhí)行調(diào)度，并在作業(yè)完成后做善后處理工作。

低級調(diào)度的主要功能是根據(jù)一定的算法將cpu分派給就緒隊列中的一個進程。

為了使內(nèi)存中同時存放的進程數(shù)目不至于太多，有時需要把某些進程從內(nèi)存移到外存上，以減少多道程序的數(shù)目，為此設(shè)立了中級調(diào)度.

4處理機調(diào)度一般分為哪三級？其中哪一級調(diào)度必不可少？為什么？

答：處理機調(diào)度一般可分為高級調(diào)度（作業(yè)調(diào)度）、中級調(diào)度和低級調(diào)度（進程調(diào)度） 。其中進程調(diào)度必不可少 。

    進程只有在得到CPU之后才能真正活動起來，所有就緒進程經(jīng)由進程調(diào)度才能獲得CPU的控制權(quán)。實際上，進程調(diào)度完成一臺物理的CPU轉(zhuǎn)變成多臺虛擬機（或邏輯）的CPU的工作，進程調(diào)度的實現(xiàn)策略往往決定了操作系統(tǒng)的類型，其算法優(yōu)劣直接影響整個系統(tǒng)的性能。

5作業(yè)調(diào)度與進程調(diào)度之間有什么差別？二者間如何協(xié)調(diào)工作？

答：作業(yè)調(diào)度與進程調(diào)度之間的差別主要是：作業(yè)調(diào)度是宏觀調(diào)度，它所選擇的作業(yè)只是具有獲得處理機的資格，但尚未占有處理機，不能立即在其上實際運行；而進程調(diào)度是微觀調(diào)度，動態(tài)地把處理機實際地分配給所選擇的進程，使之真正活動起來。另外，進程調(diào)度相當頻繁，而作業(yè)調(diào)度執(zhí)行的次數(shù)一般很少。

作業(yè)調(diào)度從外存的后背隊列中選擇一批作業(yè)調(diào)入內(nèi)存，為它們創(chuàng)建進程，這些進程被送入就緒隊列。進程調(diào)度從就緒隊列中選出一個進程來，并把它的狀態(tài)改為運行態(tài)，把cpu分配給它。當運行進程要等待某一事件時，就讓出cpu，進入相應(yīng)的阻塞隊列，并進行進程調(diào)度。運行進程完成后，由作業(yè)調(diào)度進行善后處理工作。

綜合題

1假定在單CPU條件下要執(zhí)行的作業(yè)如下表所示。

表 作業(yè)列表

作 業(yè) 運 行 時 間 優(yōu) 先 級

1 10 3

2 1 1

3 2 3

4 1 4

5 5 2

作業(yè)到來的時間是按作業(yè)編號順序進行的（即后面作業(yè)依次比前一個作業(yè)遲到一個時間單位）。

①用一個執(zhí)行時間圖描述使用非搶占式優(yōu)先級算法時各自執(zhí)行這些作業(yè)的情況：

②對于該算法，各個作業(yè)的周轉(zhuǎn)時間是多少?平均周轉(zhuǎn)時間是多少？

③對于該算法，各個作業(yè)的帶權(quán)周轉(zhuǎn)時間是多少？平均帶權(quán)周轉(zhuǎn)時間是多少？

解：⑴

非搶占式優(yōu)先級

(3’)

⑵和⑶

非搶占式優(yōu)先級  (`7’=1’*7)

JOB ts tr te T W

J1 0 10 10 10 1

J2 1 1 19 18 18

J3 2 2 13 11 5.5

J4 3 1 11 8 8.0

J5 4 5 18 14 2.8

12.2

2.06

2在一個有兩道作業(yè)的批處理系統(tǒng)中，作業(yè)調(diào)度采用短作業(yè)優(yōu)先級調(diào)度算法，進程調(diào)度采用搶占式優(yōu)先級調(diào)度算法。設(shè)作業(yè)序列如表4-9所示。

表4-9 作業(yè)列表

作業(yè)名 到達時間 預估計時間（分鐘） 優(yōu)先數(shù)

A 8:00 40 10

B 8:20 30 5

C 8:30 50 8

D 8:50 20 12

其中給出的作業(yè)優(yōu)先數(shù)即為相應(yīng)進程的優(yōu)先數(shù)。其數(shù)值越小，優(yōu)先級越高。要求：

①列出所有作業(yè)進入內(nèi)存的時間及結(jié)束時間。

②計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。

解：①

(4’)

②   (`6’=1’*6)

JOB ts tsr te T

A 8:00 8:00 9:10 70

B 8:20 8:20 8:50 30

C 8:30 9:10 10:00 90

D 8:50 8:50 10:20 90

70

2.2625

3有A、B、C、D、E，共5個待運行作業(yè)，各自估計的運行時間為9，6，3，5，x。試問采用哪種運行次序使得平均響應(yīng)時間為最短？（答案依賴于x）

解答：

由于短作業(yè)優(yōu)先調(diào)度算法可以使作業(yè)的平均周轉(zhuǎn)時間最短，同樣使作業(yè)的平均響應(yīng)時間為最短。  (5’)

  下面對x的取值進行討論：(`5’=1’*5)

  當0<x<=3時，作業(yè)的運行順序應(yīng)為E(x),C(3),D(5),B(6),A(9);

  當3<x<5時，作業(yè)的運行順序應(yīng)為C(3),E(x),D(5),B(6),A(9);

  當5<=x<=6時，作業(yè)的運行順序應(yīng)為C(3),D(5),E(x),B(6),A(9);

  當6<x<=9時，作業(yè)的運行順序應(yīng)為C(3),D(5),B(6),E(x),A(9);

  當x>9，作業(yè)的運行順序應(yīng)為C(3),D(5),B(6),A(9),E(x)

4有一個具有如下作業(yè)流的批處理處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先，進程調(diào)度采用基于優(yōu)先數(shù)的搶先式調(diào)度算法。下表給出的是作業(yè)序列和相應(yīng)進程的優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。

作業(yè)名    到達時間   估計運行時間/min   優(yōu)先數(shù)

   1          8:00          40              4

   2          8:20          30              2

   3          8:30          50              3

   4          8:50          20              5

(1) 列出所有作業(yè)進入內(nèi)存時間及完成時間

(2) 計算作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間

解答：

(1)作業(yè)進入內(nèi)存時間與結(jié)束時間如下所示：(`4’=1’*4)

作業(yè)名   進入內(nèi)存時間   結(jié)束時間

   1         8:00          9:10

   2         8:20          8:50

   3         9:10          10:00

   4         8:50          10:20        

(2)各作業(yè)的周轉(zhuǎn)時間為：   (`4’=1’*4)

作業(yè)A：9:10 – 8:00 = 70 min

作業(yè)B：8:50 – 8:20 = 30 min

作業(yè)C：10:00 – 8:30 = 90 min

作業(yè)D：10:20 – 8:50 = 90 min         

作業(yè)的平均周轉(zhuǎn)時間為：(70+30+90+90)/4=70 min    (1’)

作業(yè)的平均帶權(quán)周轉(zhuǎn)時間為：(70/40+30/30+90/50+90/20)/4=2.26 min   (1’)

                 第五章 存儲管理

名詞解釋

1物理地址

內(nèi)存中各存儲單元的地址由統(tǒng)一的基地址順序編址，這種地址稱為物理地址。

2邏輯地址

用戶程序經(jīng)編譯之后的每個目標模塊都以0為基地址順序編址，這種地址稱為邏輯地址。

3邏輯地址空間

由程序中邏輯地址組成的地址范圍叫做邏輯地址空間。

4物理地址空間

由內(nèi)存中的一系列存儲單元所限定的地址范圍稱作內(nèi)存空間。

5重定位

把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存物理地址的過程叫做重定位。

6靜態(tài)重定位

在目標程序裝入內(nèi)存時所進行的重定位。

7動態(tài)重定位

在程序執(zhí)行期間，每次訪問內(nèi)存之前進行的重定位。

8內(nèi)部碎片

在一個分區(qū)內(nèi)部出現(xiàn)的碎片（即被浪費的空間）稱作內(nèi)部碎片。如固定分區(qū)法會產(chǎn)生內(nèi)部碎片。

9外部碎片

在所有分區(qū)之外新產(chǎn)生的碎片稱作外部碎片，如在動態(tài)分區(qū)法實施過程中出現(xiàn)的越來越多的小空閑塊，由于它們太小，無法裝入一個小進程，因而被浪費掉。

10碎片

在分區(qū)法中，內(nèi)存出現(xiàn)許多容量太小、無法被利用的小分區(qū)稱作“碎片”。

11緊縮

移動某些已分區(qū)的內(nèi)容，使所有作業(yè)的分區(qū)緊挨在一起，而把空閑區(qū)留在另一端，這種技術(shù)稱為緊縮。

12可重定位地址

當含有它的程序被重定位時，將隨之被調(diào)整的一種地址。

13固定分區(qū)法

內(nèi)存中分區(qū)的個數(shù)固定不變，各個分區(qū)的大小也固定不變，但不同分區(qū)的大小可以不同，每個分區(qū)只可裝入一道作業(yè)。

14動態(tài)分區(qū)法

各個分區(qū)是在相應(yīng)作業(yè)要求進入內(nèi)存時才建立的，使其大小恰好適應(yīng)作業(yè)的大小。

15可再入代碼

也稱純代碼，是指那些在其執(zhí)行過程本身不做任何修改的代碼，通常由指令和常數(shù)組成。

16虛擬存儲器

虛擬存儲器是用戶能作為可編程內(nèi)存對待的虛擬存儲空間，在這種計算機系統(tǒng)中實現(xiàn)了用戶邏輯存儲器與物理存儲器的分離，它是操作系統(tǒng)給用戶提供的一個比真實內(nèi)存空間大得多的地址空間。

17抖動

頁面抖動是系統(tǒng)中頻繁進行頁面置換的現(xiàn)象。即如果一個進程沒有一定數(shù)量的內(nèi)存塊，它很快就發(fā)生缺頁。此時，它必須淘汰某頁。由于所有這些頁面都正在使用，所以剛被淘汰出去的頁很快又被訪問，因而要把它重新調(diào)入?？墒钦{(diào)入不久又再被淘汰出去，這樣再訪問，再調(diào)入，如此反復，使得整個系統(tǒng)的頁面替換非常頻繁，以致大部分機器時間都用在來回進行的頁面調(diào)度上，只有一小部分時間用于進程的實際運算方面。

18工作集

工作集是一個進程在某一小段時間內(nèi)訪問頁面的集合。利用工作集模型可防止抖動，也可以進行頁面置換。

19程序局部性原理

在相對短的一段時間內(nèi)，進程集中在一組子程序或循環(huán)中之行，導致所有的存儲器訪問局限于進程地址空間的一個固定子集。這種現(xiàn)象就叫做程序局部性原理。

20快表

又叫“聯(lián)想存儲器”。在分頁系統(tǒng)中，由于頁表是存放在主存中的，因此cpu存取一個數(shù)據(jù)時要訪問兩次主存。這樣使計算機的處理速度降低約一倍。為了提高地址變換速度，在地址變換機構(gòu)中增設(shè)一個具有并行查找能力的高速緩沖存儲器，用以存放當前訪問的頁表項。這樣的高速緩沖存儲器就是快表。

21交換

交換系統(tǒng)指系統(tǒng)根據(jù)需要把主存中暫時不運行的某個（或某些）作業(yè)部分或全部移到外存。而把外存中的某個（或某些）作業(yè)移到相應(yīng)的主存區(qū)，并使其投入運行。

22換頁

指系統(tǒng)根據(jù)某種策略選擇某頁出主存，將某頁調(diào)入主存的過程。

23實存

實存是指計算機配置的物理存儲器，它直接向cpu提供程序和數(shù)據(jù)。

24虛存

虛存是指系統(tǒng)向用戶程序提供的編程空間，其大小由cpu的地址長度決定。

簡答題

1解釋固定分區(qū)法和動態(tài)分區(qū)法的基本原理。

答：固定分區(qū)法——內(nèi)存中分區(qū)的個數(shù)固定不變，各個分區(qū)的大小也固定不變，但不同分區(qū)的大小可以不同。每個分區(qū)只可裝入一道作業(yè)。

動態(tài)分區(qū)法——各個分區(qū)是在相應(yīng)作業(yè)要進入內(nèi)存時才建立的，使其大小恰好適應(yīng)作業(yè)的大小。

2說明內(nèi)部碎片和外部碎片的不同之處

答：內(nèi)存中出現(xiàn)的其容量太小、無法被利用的小分區(qū)稱作碎片 。內(nèi)部碎片和外部碎片出現(xiàn)的位置不同 。內(nèi)部碎片出現(xiàn)在一個分區(qū)的內(nèi)部（即被浪費的空間），如固定分區(qū)法會產(chǎn)生內(nèi)部碎片 。外部碎片出現(xiàn)在所有分區(qū)之外，是新增的小分區(qū)，如在動態(tài)分區(qū)法實施過程中會出現(xiàn)外部碎片 。

3動態(tài)重定位分區(qū)管理方式中如何實現(xiàn)虛-實地址映射？

答：作業(yè)裝入內(nèi)存時，是將該用戶的程序和數(shù)據(jù)原封不動地裝入到內(nèi)存中 。當調(diào)度該進程在cpu上執(zhí)行時，操作系統(tǒng)就自動將該進程在內(nèi)存的起始地址裝入基址寄存器，將進程的大小裝入限長寄存器 。當執(zhí)行指令時，如果地址合法，則將相對地址與基址寄存器中的地址相加，所得結(jié)果就是真正要訪問的內(nèi)存地址；如果地址越界，則發(fā)出相應(yīng)中斷，進行處理 。

4什么是虛擬存儲器？它有哪些基本特征？

答:虛擬存儲器是用戶能作為可編址內(nèi)存對待的虛擬存儲空間,在這種計算機系統(tǒng)中實現(xiàn)了用戶邏輯存儲器與物理存儲器的分離,它是操作系統(tǒng)給用戶提供的一個比真實內(nèi)存空間大得多的地址空間。

虛擬存儲器的基本特征是:虛擬擴充——不是物理上,而是邏輯上擴充了內(nèi)存容量;部分裝入——每個作業(yè)不是全部一次性地裝入內(nèi)存,而是只裝入一部分;離散分配——不必占用連續(xù)的內(nèi)存空間,而是”見縫插針”;多次對換——所需的全部程序和數(shù)據(jù)要分成多次調(diào)入內(nèi)存。

5引入虛擬存儲器后，除了獲得主存“擴充”的好處，還有什么好處？

答：引入虛存后，程序的地址空間都是虛地址的集合，只有在程序運行中通過硬件地址轉(zhuǎn)換機構(gòu)和操作系統(tǒng)的相應(yīng)軟件，才能將虛地址變換成主存的實地址，這將為主存的分配帶來更大的靈活性。另外，虛、實地址分開，用戶程序不能干擾實地址的生成，從而實現(xiàn)了存儲器的保護 。

6什么是分頁？什么是分段？二者有何主要區(qū)別？

答：分頁是由系統(tǒng)將一個進程的邏輯地址空間劃分成若干大小相等的部分，每一部分稱做一個頁面。

分段是用戶根據(jù)作業(yè)的邏輯關(guān)系進行自然劃分，每個分段是作業(yè)中相對獨立的一部分。

分段和分頁都是非連續(xù)的存儲管理方法，

分頁和分段的主要區(qū)別有：

①頁是信息的物理單位，段是信息的邏輯單位。

②頁面的大小由系統(tǒng)確定，并且各頁大小都相同；各段長度因段而已，由用戶決定。

③分頁的作業(yè)地址空間是一維的，分段的作業(yè)的地址空間是二維的。

④分頁的活動對用戶是不可見的，而分段是用戶可見的活動。

7在分頁系統(tǒng)中頁面大小由誰決定？頁表的作用是什么？如何將邏輯地址轉(zhuǎn)換成物理地址？

答:在分頁系統(tǒng)中頁面大小由硬件決定。

頁表的作用是:實現(xiàn)從頁號到物理塊號的地址映射。

邏輯地址轉(zhuǎn)換成物理地址的過程是:用頁號P去檢索頁表，從頁表中得到該頁的物理塊號，把它裝入物理地址寄存器中。同時，將頁內(nèi)陸址d直接送入物理地址寄存器的塊內(nèi)陸址字段中。這樣，物理地址寄存器中的內(nèi)容就是由二者拼接成的實際訪問內(nèi)存地址，從而完成了從邏輯地址到物理地址的轉(zhuǎn)換。

8什么是belady現(xiàn)象？

答：belady現(xiàn)象是指在使用FIFO算法進行內(nèi)存頁面置換時 ，在未給進程或作業(yè)分配足它所要求的全部頁面的情況下，有時出現(xiàn)的分配的頁面數(shù)增多，缺頁次數(shù)發(fā)而增加的奇怪現(xiàn)象。

9請求分頁技術(shù)的基本思想是什么？它與簡單分頁技術(shù)之間有何根本區(qū)別？

答：請求分頁技術(shù)的基本思想是：當一個進程的部分頁面在內(nèi)存時就可調(diào)度它運行；在運行過程中若用到的頁面尚未在內(nèi)存，則把它們動態(tài)換入內(nèi)存。這樣，就減少了對換時間和所需內(nèi)存數(shù)量，允許增加程序的道數(shù)。

請求分頁技術(shù)是在簡單分頁技術(shù)基礎(chǔ)上發(fā)展起來的，兩者根本區(qū)別是：請求分頁提供虛擬存儲器，而簡單分頁系統(tǒng)并未提供虛擬存儲器。

10為什么分段技術(shù)比分頁技術(shù)更容易實現(xiàn)程序或數(shù)據(jù)的共享和保護？

答： 每一段在邏輯上是相對完整的一組信息，分段技術(shù)中的共享是在段一級出現(xiàn)的。這樣，任何共享的信息就可以單獨成為一段。同樣，段中所有內(nèi)容可以用相同的方式進行使用，從而規(guī)定相同的保護權(quán)限。 然而，頁是信息的物理單位，在一頁中可能存在邏輯上互相獨立的兩組或多組信息，各有不同的使用方式和存取權(quán)限，因而，對分頁難以進行共享和保護。

11何謂工作集？它有什么作用？

答：工作集是一個進程在某一小段時間內(nèi)訪問頁面的集合。

利用工作集模型可防止抖動，也可以進行頁面置換。

12什么是頁面抖動？系統(tǒng)怎樣檢測是否出現(xiàn)抖動？一旦檢測到抖動？系統(tǒng)如何消除它？

答：頁面抖動是系統(tǒng)頻繁進行頁面置換的現(xiàn)象。整個系統(tǒng)的頁面替換非常頻繁，以致大部分機器時間都用在來回進行的頁面調(diào)度上，只有一小部分時間用于進程的實際運算方面。

操作系統(tǒng)監(jiān)督每個進程的工作集，并給它分配工作集所需的內(nèi)存塊。若有足夠多的額外塊，就可以裝入并啟動另外的進程。如果工作集增大了，超出可用塊的總數(shù)，即系統(tǒng)中全部進程對內(nèi)存塊的總請求量大于可用內(nèi)存塊的總量，將出現(xiàn)抖動，因為某些進程得不到足夠的內(nèi)存塊。

一旦檢測到抖動，操作系統(tǒng)要選擇一個進程讓它掛起，把它的頁面寫出去，把它占用的內(nèi)存塊分給別的進程。被掛起的進程將在以后適當時機重新開始執(zhí)行。

綜合題

1考慮下面頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 當內(nèi)存塊數(shù)量分別為3時，試問LRU,FIFO,OPT三種置換算法的缺頁次數(shù)各是多少？（注意，所有內(nèi)存最初都是空的，凡第1次用到的頁面都產(chǎn)生一次缺頁）

答：

LRU

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

1 1 1 4 4 4 5 5 5 1 1 1 7 7 7 2 2 2 2 2

2 2 2 2 1 1 1 2 2 2 2 2 6 6 6 1 1 1 6

3 3 3 3 3 6 6 6 6 3 3 3 3 3 3 3 3 3

× × × × × × × × × × × × × × ×

(2’)

FIFO

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

1 1 1 4 4 4 4 6 6 6 6 3 3 3 3 2 2 2 2 6

2 2 2 2 1 1 1 2 2 2 2 7 7 7 7 1 1 1 1

3 3 3 3 5 5 5 1 1 1 1 6 6 6 6 6 3 3

× × × × × × × × × × × × × × × ×

(2’)

OPT

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3

2 2 2 2 2 2 2 2 2 2 2 7 7 7 2 2 2 2 2

3 4 4 4 5 6 6 6 6 6 6 6 6 6 1 1 1 6

× × × × × × × × × × × (2’)

內(nèi)存塊數(shù) 置換算法

FIFO LRU OPT

3 16 15 11        (3’)

2考慮下面存儲訪問序列，該程序大小為460字：10，11，104，170，73，309，185，245，246，434，458，364 設(shè)頁面大小是100字，請給出該訪問序列的頁面走向。又設(shè)該程序基本可用內(nèi)存是200字，采用FIFO置換算法，求出缺頁率。如果采用LRU算法，缺頁率是多少？如果采用最優(yōu)淘汰算法，其缺頁率又是多少？

解:

該序列的頁面走向為：0、1、0、3、1、2、4、3。  (1’)

FIFO

0 1 0 3 1 2 4 3

0 0 0 3 3 3 4 2

1 1 1 1 2 2 3

× × × × × ×    (2’)

LRU

0 1 0 3 1 2 4 3

0 0 0 0 1 1 4 4

1 1 3 3 2 2 3

× × × × × × ×    (2’)

OPT

0 1 0 3 1 2 4 3

0 0 0 3 3 3 3 3

1 1 1 1 2 4 4

× × × × × (2’)

算法 FIFO LRU OPT

缺頁次數(shù) 6 7 5

缺頁率 6/12=0.5 7/12=0.583 5/12=0.417     (3’)

3設(shè)某頁系統(tǒng)中，頁幀大小為100字。一個程序大小為1200字，可能的訪問序列如下：

10，205，110，735，603，50，815，314，432，320，225，80，130，270

系統(tǒng)采用LRU算法。當為其分配4個主存塊時，給出該作業(yè)駐留的各個頁的變化情況及頁故障數(shù)。

答：

首先將邏輯地址變換成頁號。這樣10，205，110，735，603，50，815，314，432，320，225，80，130，720，通過除以頁的大小100，頁號分別為0，2，1，7，6，0，8，3，4，2，0，1，2。(3’)

系統(tǒng)為運行進程分配4個主存塊，采用LRU算法，因此可以列表給出進程的缺頁情況：

0 2 1 7 6 0 8 3 4 3 2 0 1 2

0 2 1 7 6 0 8 3 4 3 2 0 1 2

0 2 1 7 6 0 8 3 4 3 2 0 1

0 2 1 7 6 0 8 8 4 3 2 0

0 2 1 7 6 0 0 8 4 3 3

F F F F F F F F F S F F F S      (5’)

由上表可見，被淘汰的頁依次為0，2，1，7，6，0，8，4。缺頁次數(shù)為12次 (2’)

4某請求頁式管理系統(tǒng)，用戶編程空間有40個頁面，每個頁面為200H字節(jié)。假定某時刻用戶頁表中虛頁號和物理塊號對照表如下：

虛頁號 0 2 5 17 20

物理塊號 5 20 8 14 36

求虛地址0A3CH、223CH分別對應(yīng)的物理地址。

答：

虛地址0A3CH轉(zhuǎn)換成十進制數(shù)為2620，每個頁為200H，即512B，由2620/512可得，頁號為5，頁內(nèi)陸址為60。查頁表可知，其主存塊號為8。(3’)

因此地址為2620的物理地址為：8*512+60=4156。(2’)

虛地址223CH轉(zhuǎn)換成十進制數(shù)為8762，由8762/512可得，其頁號為17，頁內(nèi)陸址為58。查頁表可知，其主存塊號為14。(3’)

因此地址為8762的物理地址為14*512+58=7226。(2’)

5某系統(tǒng)采用頁式存儲管理策略，擁有邏輯空間32頁，每頁2KB；擁有物理空間1MB。

1） 寫出邏輯地址的格式

2） 若不考慮訪問權(quán)限位，進程的頁表有多少項？每項至少多少位？

3） 如果物理空間減少一半，頁表結(jié)構(gòu)應(yīng)作怎樣的改？

答：

1）邏輯空間32頁，占5個二進制位。每頁2KB，占11位。故描述邏輯空間需要16位(2’)。

15 … 11 10 … 0

邏輯地址的格式：[       |                  ]   (1’)

2)進程的頁表有32項，每項的位數(shù)由主存的分塊數(shù)決定(2’)。1MB的空間可劃分為512個2KB的塊，每個塊用9個二進制位表示(2’)。

3）如果物理空間減少一半時，主存地址需要19位表示，仍大于邏輯空間的大小，故頁表結(jié)構(gòu)可以不變。(3’)

6有一虛擬存儲系統(tǒng)，采用先進先出（FIFO）的頁面淘汰算法。在主存忠為每一個作業(yè)進程開辟3頁。某作業(yè)運行中使用的操作數(shù)所在的頁號依次為：4，3，2，1，4，3，5，4，3，2，1，5。

1） 該作業(yè)運行中總共出現(xiàn)多少次缺頁？

2） 若每個作業(yè)進程在主存擁有4頁，又將產(chǎn)生多少次缺頁？

3） 如何解釋所出現(xiàn)的現(xiàn)象？

解：

先進先出算法的實質(zhì)是：總是選擇作業(yè)中在主存駐留時間最長的一頁進行淘汰。

若在主存中為每一作業(yè)進程開辟3頁，對于題中的頁面訪問過程，其頁面調(diào)度過程如下所示

4 3 2 1 4 3 5 4 3 2 1 5

頁面1 4 4 4 1 1 1 5 5 5 5 5 5

頁面2 3 3 3 4 4 4 4 4 2 2 2

頁面3 2 2 2 3 3 3 3 3 1 1

缺頁中斷 F F F F F F F F F         (3’)

1） 該作業(yè)運行中總共出現(xiàn)9次缺頁(1’)

2） 在主存擁有4頁，又將產(chǎn)生10次缺頁(1’)。其頁面調(diào)度過程見下圖：

4 3 2 1 4 3 5 4 3 2 1 5

頁面1 4 4 4 4 4 4 5 5 5 5 1 1

頁面2 3 3 3 3 3 3 4 4 4 4 5

頁面3 2 2 2 2 2 2 3 3 3 3

頁面4 1 1 1 1 1 1 2 2 2

缺頁中斷 F F F F F F F F F F        (3’)

3)從這個例子可以看出，當主存中為每一作業(yè)進程開辟4頁時，出現(xiàn)了缺頁次數(shù)反而增加的現(xiàn)象。這種現(xiàn)象稱為Belady現(xiàn)象。(2’)

7關(guān)于存儲管理，試問：

（1） 在分頁、分段和段頁式存儲管理中，當訪問一條指令或數(shù)據(jù)時，需要訪問內(nèi)存幾次？各做什么處理？

（2） 假設(shè)一個分頁存儲系統(tǒng)具有快表，多數(shù)活動頁表都可以存在其中，頁表放在內(nèi)存中，內(nèi)存訪問時間是1us。若快表的命中率是85%，快表的訪問時間為0.1us，則有效存取時間為多少？若快表命中率為50%，那么有效存取時間為多少？

解答：（1）分頁需要訪問2次，第一次訪問頁表，第二次執(zhí)行訪內(nèi)操作(2’)；分段需要訪問2次，第一次訪問段表，第二次執(zhí)行訪內(nèi)操作；段頁式需要訪問3次，第一次訪問段表，第二次訪問頁表，第三次執(zhí)行訪內(nèi)操作(2’)。

（2）當快表的命中率為85%時，執(zhí)行一次訪內(nèi)操作需要的時間：

   T=1*0.85+2*(1-0.85)=1.15(us)   (3’)

當快表的命中率為50%時，執(zhí)行一次訪內(nèi)操作需要的時間：

   T=1*0.5+2*(1-0.5)=1.5(us)   (3’)

8在一個采用頁式虛擬存儲管理的系統(tǒng)中，有一用戶作業(yè)，它依次要訪問的字地址序列是：115，228，120，88，446，102，321，432，260，167，若該作業(yè)的第0頁已經(jīng)裝入主存，現(xiàn)分配給該作業(yè)的主存共300字，頁的大小為100字，請回答下列問題：

（1）按FIFO調(diào)度算法將產(chǎn)生多少次缺頁中斷，依次淘汰的頁號為多少，缺頁中斷率為多少。

（2）按LRU調(diào)度算法將產(chǎn)生多少次缺頁中斷，依次淘汰的頁號為多少，缺頁中斷率為多少。

答：

頁面走向為：1，2，1，0，4，1，3，4，2，1

（1）按FIFO調(diào)度算法將產(chǎn)生5次缺頁中斷；依次淘汰的頁號為：0，1，2； 缺頁中斷率為：5/10=50%    (3’)

1 2 1 0 4 1 3 4 2 1

0 0 0 0 0 4 4 4 4 4 4

1 1 1 1 1 1 3 3 3 3

2 2 2 2 2 2 2 2 1

× × × × ×      (2’)

（2）按LRU調(diào)度算法將產(chǎn)生6次缺頁中斷；依次淘汰的頁號為：2，0，1，3； 缺頁中斷率為：6/10=60%   (3’)

1 2 1 0 4 1 3 4 2 1

0 0 0 0 0 0 0 3 3 3 3

1 1 1 1 1 1 1 1 2 2

2 2 2 4 4 4 4 4 1

× × × × × ×   (2’)

9一臺計算機含有65536字節(jié)的存儲空間，這一空間被分成許多長度為4096字節(jié)的頁。有一個程序，其代碼段為32768字節(jié)，數(shù)據(jù)段為16386字節(jié)，棧段為15870字節(jié)。試問該機器的主存空間適合這個進程嗎？如果將每頁改成512字節(jié)，合適嗎？

答：

當存儲空間每塊為4096B時，共可分成16塊。其中：

程序代碼段占：32768/4096=8塊；   (1’)

數(shù)據(jù)段占：16386/4096=5塊；  (1’)

棧段占：15870/4096=4塊；  (1’)

合計為：8+5+4=17塊；  (1’)

故該機器的主存空間不適合這個作業(yè)。 (1’)

當存儲空間每塊為512B時，共可分成128塊。其中：

程序代碼段占：32768/512=64塊； (1’)

數(shù)據(jù)段占：16386/512=32塊； (1’)

棧段占：15870/512=31塊； (1’)

故合計為：64+32+31=127塊。 (1’)

故該機器的主存空間是適合這個作業(yè)的。 (1’)

10一個請求分頁系統(tǒng)中，內(nèi)存的讀/寫周期為8納秒，當配置有快表時，查快表需要1納秒，內(nèi)外存之間傳送一個頁面的平均時間為5000納秒。假定快表的命中率為75%，頁面失效率為10%，求內(nèi)存的有效存取時間。

答：

訪問主存的時間可用下面公式表示：

訪問主存時間=主存的命中率*（快表的命中率*訪問快表的時間+執(zhí)行實際操作訪問主存的時間）+頁面失效率*頁面失效時的訪問時間   (6’)

因此 TA=(1-0.1)*[0.75*1+(1-0.75)*(8+1)+8]+0.1*5000   (4’)

11在一個虛擬存儲器系統(tǒng)中，一次訪問主存的時間用TA1表示，一個訪問外存的時間用TA2表示。假定TA1=10^-7秒，TA2=10^-2秒。試問，為了使訪問效率達到80%以上，命中率H至少應(yīng)該達到多少？

答：

訪問效率：e=TA1/TA=0.8   (2’)

TA=TA1/0.8=1.25*10^-7 s    ( 2’)

TA=H*TA1+(1-H)*TA2=H(TA1-TA2)+TA2  

H=(TA-TA2)/(TA1-TA2)  (2’)

解得  H=(1.25*10^-7-10^-2)/(10^-7 – 10^-2)=0.999975  (2’)

因此，為了使訪問效率達到80%以上，命中率H至少應(yīng)該達到0.999975。(2’)

                第六章  文件系統(tǒng)

名詞解釋

1邏輯記錄

用戶構(gòu)造文件時使用的一個信息單位。通常以邏輯記錄為單位存取文件。

2物理記錄

文件存儲器上組織信息的一個單位。它是文件存儲器識別信息的單位。

3文件

是命名的相關(guān)信息的集合體，它通常存放在外存（如磁盤、磁帶）上，可以作為一個獨立單位存放并實施相應(yīng)的操作（如打開、關(guān)閉、讀、寫等）。

4文件系統(tǒng)

操作系統(tǒng)中負責操縱和管理文件的一整套設(shè)施，它實現(xiàn)文件的共享和保護，方便用戶“按名存取”。

5目錄項

為了加快對文件的檢索，把文件控制塊集中在一起進行管理。這種文件控制塊的有序集合稱為文件目錄。當然，文件控制塊也是其中的目錄項。

6目錄文件

全由目錄項構(gòu)成的文件成為目錄文件。

7路徑

在樹形目錄結(jié)構(gòu)中，從根目錄出發(fā)經(jīng)由所需子目錄到達指定文件的通路。

8當前目錄

為節(jié)省文件檢索的時間，每個用戶可以指定一個目錄作為當前工作目錄，以后訪問文件時，就從這個目錄開始向下順序檢索。這個目錄就稱作當前目錄。

9文件的邏輯組織

用戶對文件的觀察和使用是從自身處理文件數(shù)據(jù)時所采用的組織方式來看待文件組織形式。這種從用戶觀點出發(fā)所見到的文件組織形式稱為文件的邏輯組織。

10文件的物理組織

文件在存儲設(shè)備上的存儲組織形式稱為文件的物理組織。

11文件控制塊

用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，其中包括文件名、文件類型、位置、大小等信息。文件控制塊與文件一一對應(yīng)，即在文件系統(tǒng)內(nèi)部，給每個文件唯一地設(shè)置一個文件控制塊，核心利用這種結(jié)構(gòu)對文件實施各種管理。

12存取權(quán)限

用戶或系統(tǒng)為文件規(guī)定的誰能訪問，以及如何訪問的方式

簡答題

1什么是文件、文件系統(tǒng)？文件系統(tǒng)有哪些功能？

答：在計算機系統(tǒng)中，文件被解釋為一組賦名的相關(guān)字符流的集合，或者是相關(guān)記錄的集合。

文件系統(tǒng)是操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)。

文件系統(tǒng)的功能是為用戶建立文件，撤銷、讀寫修改和復制文件，以及完成對文件的按名存取和進行存取控制。

2文件系統(tǒng)一般按什么分類？可以分為那幾類？

答：文件系統(tǒng)一般按性質(zhì)，用途，組織形式，文件中的信息流向或文件的保護級別等分類：按文件的性質(zhì)與用途可以分為系統(tǒng)文件，庫文件和用戶文件。按文件的組織形式可以分為普通文件，目錄文件和特殊文件。按文件中的信息流向可以分為輸入文件，輸出文件和輸入/輸出文件。按文件的保護級別可以分為只讀文件，讀寫文件，可執(zhí)行文件和不保護文件。

3什么是文件的邏輯結(jié)構(gòu)，什么是記錄？

答：文件的邏輯結(jié)構(gòu)就是用戶可見的結(jié)構(gòu)，可分為字符流式的無結(jié)構(gòu)文件和記錄式的有結(jié)構(gòu)文件兩大類。

記錄是一個具有特定意義的信息單位，它由該記錄在文件中的邏輯地址（相對位置）與記錄名所對應(yīng)的一組關(guān)鍵字，屬性及其屬性值所組成。

4什么是文件目錄？文件目錄中包含那些信息？

答：一個文件的文件名和對該文件實施控制管理的說明信息稱為該文件的說明信息，又稱為該文件的目錄。

文件目錄中包含文件名、與文件名相對應(yīng)的文件內(nèi)部標識以及文件信息在文件存儲設(shè)備上第一個物理塊的地址等信息。另外還可能包含關(guān)于文件邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、存取控制和管理等信息。

5文件系統(tǒng)中目錄結(jié)構(gòu)主要有哪幾種？分別說明各自的實現(xiàn)思想？

答：文件系統(tǒng)中的目錄結(jié)構(gòu)主要有：單級目錄結(jié)構(gòu)，二級目錄結(jié)構(gòu)，樹形目錄結(jié)構(gòu)和非循環(huán)圖目錄結(jié)構(gòu)。

單級目錄結(jié)構(gòu)——在這種組織方式下，全部文件都登記在同一目錄中。

二級目錄結(jié)構(gòu)——在主文件目錄中登載了各個用戶的名稱，每個用戶有自己的用戶文件目錄。

樹形目錄結(jié)構(gòu)——在這種結(jié)構(gòu)中，只有一個根目錄，每一級目錄可以是下級目錄的說明，也可以是包含文件的說明。從根開始一層一層地擴展下去，就形成一個樹形層次結(jié)構(gòu)。

非循環(huán)圖目錄結(jié)構(gòu)——樹形目錄結(jié)構(gòu)的自然推廣就是非循環(huán)圖目錄結(jié)構(gòu)，它允許一個文件或目錄可在多個父目錄中占有項目，但并不構(gòu)成環(huán)路。

6什么是文件控制塊?它與文件有何關(guān)系？

答：文件控制塊——用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，其中包括文件名、文件類型、位置、大小等信息。

文件控制塊與文件一一對應(yīng)，即在文件系統(tǒng)內(nèi)部，給每個文件唯一地設(shè)置一個文件控制塊，核心利用這種結(jié)構(gòu)對文件實施各種管理。

7文件系統(tǒng)中的目錄結(jié)構(gòu)有哪幾種基本形式？各有何優(yōu)缺點？

答：文件系統(tǒng)中的目錄結(jié)構(gòu)有：單級目錄結(jié)構(gòu)、二級目錄結(jié)構(gòu)、樹形目錄結(jié)構(gòu)和非循環(huán)圖目錄結(jié)構(gòu)，UNIX采用非循環(huán)圖目錄結(jié)構(gòu)，即帶鏈接的樹形目錄結(jié)構(gòu)。

文件系統(tǒng)目錄結(jié)構(gòu) 優(yōu)點 缺點

單級目錄結(jié)構(gòu) 簡單、能實現(xiàn)按名存取 查找速度慢；不允許重名；不便于共享

二級目錄結(jié)構(gòu)           允許重名；提高了檢索目錄的速度 仍不利于文件共享

樹形目錄結(jié)構(gòu)           文件的層次和隸屬關(guān)系清晰，便于 只能在用戶級對文件進行臨時共享

實現(xiàn)不同級別的存取保護和文件系統(tǒng)

的動態(tài)裝卸

非循環(huán)圖目錄結(jié)構(gòu) 具有樹形結(jié)構(gòu)的優(yōu)點，而且實現(xiàn)對 管理較復雜

文件的永久共享

8常用的磁盤空閑區(qū)管理技術(shù)有哪幾種？試簡要說明各自的實現(xiàn)思想。

答：常用的磁盤空閑區(qū)管理技術(shù)有：空閑空間表達法、空閑塊鏈接法、位示圖法和空閑塊成組鏈接法。

空閑空間表法——所有連續(xù)的空閑盤塊在表中占據(jù)一項，其中標出第一個空閑塊號和該項中所包含的空閑塊個數(shù)，以及相應(yīng)的物理塊號。利用該表可進行盤塊的分配和文件的刪除時盤塊的回收

空閑塊鏈接法——所有的空閑盤塊鏈在一個隊列中，用一個指針（空閑區(qū)頭）指向第一個空閑塊，而各個空閑塊中都含有下一個空閑塊的塊號，最后一塊的指針項計為NULL，表示鏈尾。分配和釋放盤塊都在鏈首進行

位示圖法——利用一串二進制的值來反映磁盤空間的分配情況，每個盤塊都對應(yīng)一位。如果盤塊是空閑的，對應(yīng)位是0；如盤塊已分出去，則對應(yīng)位是1。

空閑塊成組鏈法——把所有空閑盤塊按固定數(shù)量分組，組與組之間形成鏈接關(guān)系，最后一組的塊號（可能不滿一組）通常放在內(nèi)存的一個專用棧結(jié)構(gòu)中。這樣，對盤塊的分配和釋放是在棧中進行（或構(gòu)成新的一組）.

9什么是文件共享？文件鏈接如何實現(xiàn)文件共享？

答：文件的共享是指系統(tǒng)允許多個用戶（進程）共同使用某個或某些文件。

文件鏈接是給文件起別名，即將該文件的目錄項登記在鏈接目錄中。這樣，訪問該文件的路徑就不只一條。不同的用戶（進程）就可以利用各自的路徑來共享同一文件。

10什么是文件后備？數(shù)據(jù)轉(zhuǎn)儲方法有哪兩種？按時間劃分，后備分哪幾種？

答：文件的后備就是把硬盤上的文件轉(zhuǎn)儲到其他外部介質(zhì)上。

將磁盤上的數(shù)據(jù)轉(zhuǎn)儲到磁帶上有兩種方式：物理轉(zhuǎn)儲和邏輯轉(zhuǎn)儲。物理轉(zhuǎn)儲是從磁盤上第0塊開始，把所有的盤塊按照順序?qū)懙酱艓希攺椭仆曜詈笠粔K時，轉(zhuǎn)儲結(jié)束。邏輯轉(zhuǎn)儲方式是從一個或多個指定的目錄開始，遞歸地轉(zhuǎn)儲自某個日期以來被修改過的所有文件和目錄。

通常有以下三種備份策略：完全備份、增量備份和更新備份。

完全備份也稱簡單備份，即每隔一定時間就對系統(tǒng)作一次全面的備份；增量備份使每隔一段較短的時間進行一次備份，但僅僅備份在這段時間間隔內(nèi)修改過的數(shù)據(jù)；更新備份是備份從上次進行完全備份后至今更改的全部數(shù)據(jù)文件。

11文件系統(tǒng)的一般格式是怎樣的？其中引導塊和超級塊的作用各是什么？

答：文件系統(tǒng)的一般由引導塊、超級塊、空閑空間管理、I節(jié)點、根目錄、文件數(shù)據(jù)區(qū)

引導塊的作用是引導操作系統(tǒng)。它包括一個小程序，用于讀入該分區(qū)上相應(yīng)操作系統(tǒng)的引導部分，從而把該分區(qū)中的操作系統(tǒng)裝入內(nèi)存。

超級塊的作用是對整個文件系統(tǒng)進行控制和管理。它包含有關(guān)文件系統(tǒng)的全部關(guān)鍵參數(shù)。當計算機加電進行引導或第一次遇到該文件系統(tǒng)時，就把超級塊中的信息讀入內(nèi)存。超級塊中包含標識文件系統(tǒng)類型的幻數(shù)、文件系統(tǒng)中的盤塊數(shù)量、修改標記及其他關(guān)鍵管理方面的信息。

                第七章  設(shè)備管理

名詞解釋

1輸入井

是指為使設(shè)備與cpu速度相匹配，系統(tǒng)在磁盤上設(shè)置的多個緩沖區(qū)，以實現(xiàn)設(shè)備與cpu之間的數(shù)據(jù)交換。輸入井主要用來存放由輸入設(shè)備輸入的信息。

2緩沖池

又叫公共緩沖區(qū)，也是系統(tǒng)在磁盤上設(shè)置的多個緩沖區(qū)。它既可以用于輸入，也可以用于輸出，較好地克服了專用緩沖區(qū)的缺點。一方面提高了緩沖區(qū)的利用率，另一方面也提高了設(shè)備與cpu的并行操作程度。

3虛擬設(shè)備

它是利用共享設(shè)備上的一部分空間來模擬獨占設(shè)備的一種I/O技術(shù)。

4存儲設(shè)備

它們是指計算機用來存儲信息的設(shè)備，如此盤（硬盤和軟盤）、磁帶等。

5輸入輸出設(shè)備

是計算機用來接收來自外部世界信息的設(shè)備，或者將計算機加工處理好的信息送向外部世界的設(shè)備。例如鍵盤、打印機、卡片輸入機。

6設(shè)備的無關(guān)性

也稱設(shè)備獨立性，就是說，用戶程序應(yīng)與實際使用的物理設(shè)備無關(guān)，由操作系統(tǒng)來考慮因?qū)嶋H設(shè)備不同而需要使用不同的設(shè)備驅(qū)動程序等問題。

7通道

為使CPU擺脫繁忙的I/O事務(wù)，現(xiàn)代大、中型計算機都設(shè)置了專門處理I/O操作的機構(gòu)，這就是通道。

8 RAID

稱作廉價磁盤冗余陣列，即利用一臺磁盤陣列控制器來統(tǒng)一管理和控制一組磁盤驅(qū)動器（幾臺到幾十臺），組成一個高可靠性、快速大容量的磁盤系統(tǒng)。采用該技術(shù)可以獲取更高的可靠性和更快的數(shù)據(jù)傳輸速率，而不是價格上更便宜。

簡答題

1為什么要引入緩沖技術(shù)？設(shè)置緩沖區(qū)的原則是什么？

答：引入緩沖區(qū)的主要目的是：⑴緩和CPU與I/O設(shè)備間速度不匹配的矛盾。⑵提高它們之間的并行性。⑶減少對CPU的中斷次數(shù)，放寬CPU對中斷響應(yīng)時間的要求。

    設(shè)置緩沖區(qū)的原則是：如果數(shù)據(jù)到達率與離去率相差很大，則可采用單緩沖方式；如果信息的輸入與輸出速率相同（或者相差不大）時，則可用雙緩沖區(qū)；對于陣發(fā)性的輸入/輸出，可以設(shè)立多個緩沖區(qū)。

2操作系統(tǒng)中設(shè)備管理的功能是什么？

答：對各種外部設(shè)備進行管理是操作系統(tǒng)的一個重要任務(wù)，也是其基本組成部分。

操作系統(tǒng)中設(shè)備管理的功能是：

① 監(jiān)視設(shè)備狀態(tài)；

② 進行設(shè)備分配；

③ 完成I/O操作；

④ 緩沖管理與地址轉(zhuǎn)換。

3什么是緩沖？為什么要引入緩沖？

答：緩沖即是使用專用硬件緩沖器或在內(nèi)存中劃出一個區(qū)域用來暫時存放輸入輸出數(shù)據(jù)的器件。

引入緩沖是為了匹配外設(shè)和cpu之間的處理速度，減少中斷次數(shù)和cpu的中斷處理時間，同時解決dma或通道方式時的數(shù)據(jù)傳輸瓶頸問題。

4 I/O設(shè)備通?？煞譃槟膬纱箢?？各自傳輸?shù)男畔挝挥惺裁刺攸c？

答：I/O設(shè)備通?？煞譃樽址O(shè)備和塊設(shè)備。

字符設(shè)備通常以獨占方式分配，信息的傳輸單位是字符或字節(jié)。塊設(shè)備通常采用共享方式分配，信息的傳輸是以塊為單位進行傳輸?shù)摹?

5什么是I/O控制？,I/O操作的四種控制方式是什么？

答：I/O控制是指從用戶進程的輸入/輸出請求開始，給用戶進程分配設(shè)備和啟動有關(guān)設(shè)備進行I/O操作，并在I/O操作完成之后響應(yīng)中斷,直至善后處理為止的整個系統(tǒng)控制過程 。

I/O操作的四種控制方式分別是：程序直接控制方式、中斷I/O控制方式、DMA控制方式、I/O通道控制方式 。

6 I/O控制可用那幾種方式實現(xiàn)，各有什么優(yōu)缺點？

答：I/O控制過程可用三種方式實現(xiàn)：作為請求I/O操作的進程實現(xiàn)；作為當前進程的一部分實現(xiàn)；由專門的系統(tǒng)進程——I/O進程完成。

第一種方式請求對應(yīng)I/O操作的進程能很快占據(jù)處理機，但要求系統(tǒng)和I/O操作的進程具有良好的實時性。第二種方式不要求系統(tǒng)具有高的實時性，但I/O控制過程要由當前進程負責。第三種方式增加了一個額外的進程開銷，但用戶不用關(guān)心I/O控制過程。

7設(shè)備分配技術(shù)主要有哪些？常用的設(shè)備分配算法是什么？

答：設(shè)備分配技術(shù)主要有：獨占分配、共享分配和虛擬分配。

常用的設(shè)備分配算法是：先來先服務(wù)算法和優(yōu)先級高的優(yōu)先服務(wù)算法。

8實現(xiàn)SPOOLing系統(tǒng)的硬件前提是什么？SPOOLing系統(tǒng)的主要功能是什么？

答：實現(xiàn)SPOOLING系統(tǒng)的首先要有硬件支持：要提供大容量的磁盤，要有中斷和通道裝置，以便使外圍設(shè)備與中央處理器能夠并行工作。 它是為了滿足多道程序或多進程隊獨占設(shè)備的共享使用而引入的，其主要功能即是：將獨占設(shè)備改造為共享設(shè)備，實現(xiàn)虛擬設(shè)備 。

9簡述處理I/O請求的主要步驟。

答：處理I/O請求是一個系統(tǒng)獲取用戶I/O請求轉(zhuǎn)發(fā)給相應(yīng)外設(shè)完成的過程 ，其具體的處理步驟如下：

①用戶進程發(fā)出I/O操作；

②系統(tǒng)接受這個I/O請求，轉(zhuǎn)去執(zhí)行操作系統(tǒng)的核心程序；

③設(shè)備驅(qū)動程序具體完成I/O操作；

④I/O完成后,系統(tǒng)進行I/O中斷處理，然后用戶進程重新開始執(zhí)行

10設(shè)備驅(qū)動程序主要執(zhí)行什么功能？

答：設(shè)備驅(qū)動進程嚴格執(zhí)行設(shè)備驅(qū)動程序中規(guī)定的各種功能 ，即接受用戶的I/O請求 ；取出請求隊列中隊首的請求，將相應(yīng)的設(shè)備分配給它 ；啟動該設(shè)備工作，完成指定的I/O操作 ；處理來自設(shè)備的中斷 。

11 I/O軟件的設(shè)計目標？它是如何劃分層次的？各層的功能是什么？

答：I/O軟件的設(shè)計目標：

①與設(shè)備無關(guān)

②對文件和設(shè)備應(yīng)統(tǒng)一命名

③層次結(jié)構(gòu)

④效率高

I/O軟件可分為如下4個層次：中斷處理程序、設(shè)備驅(qū)動程序、與設(shè)備無關(guān)的操作系統(tǒng)軟件和用戶級軟件 。各層功能為：

①中斷處理程序——分析中斷原因，并依據(jù)中斷原因調(diào)用相應(yīng)的處理程序

②設(shè)備驅(qū)動程序——它接受來自上層、與設(shè)備無關(guān)軟件的抽象讀寫請求，并將該I/O請求排在請求隊列的隊尾，還要檢查I/O請求的合法性；取出請求隊列中對首請求，將相應(yīng)設(shè)備分配給它；向該設(shè)備控制器發(fā)送命令，啟動該設(shè)備工作，完成指定的I/O操作；處理來自設(shè)備的中斷

③與設(shè)備無關(guān)的操作系統(tǒng)軟件——其基本功能是執(zhí)行所有驅(qū)動器共同的I/O功能和對用戶級軟件提供統(tǒng)一軟件

④用戶級軟件——多數(shù)I/O軟件都在操作系統(tǒng)中，用戶空間中也有一小部分。通常，它們以庫函數(shù)形式出現(xiàn)，在用戶程序中可以調(diào)用它們

12什么叫尋道？訪問磁盤時間由哪幾部分組成?其中哪一個是磁盤調(diào)度的主要目標？為什么？

答:  把磁頭從當前位置移到相應(yīng)的磁道上或柱面上，這個操作過程叫做尋道。

訪問磁盤一般要有三部分時間：尋道時間、旋轉(zhuǎn)延遲時間和傳輸時間。

尋道時間是磁盤調(diào)度的主要目標。

傳輸時間是硬件設(shè)計時就固定的，尋道時間和旋轉(zhuǎn)延遲時間與信息在磁盤上的位置有關(guān)。因為磁頭臂是機械移動，所以對大多數(shù)磁盤來說，尋道時間遠大于旋轉(zhuǎn)延遲時間與傳輸時間之和，它是影響磁盤調(diào)度的主要因素。

13什么是RAID？采用RAID技術(shù)的優(yōu)點是什么？

答：RAID稱作廉價磁盤冗余陣列，即利用一臺磁盤陣列控制起來統(tǒng)一管理和控制一組磁盤驅(qū)動器（幾臺到幾十臺），組成一個高可靠性、快速大容量的磁盤系統(tǒng)。

采用RAID技術(shù)可以獲取更高的可靠性和更快的數(shù)據(jù)傳輸速率，而不是價格上更便宜。

綜合題

1假定一個硬盤有100個柱面，每個柱面有10個磁道，每個磁道有15個扇區(qū)。當進程要訪問磁盤的12345扇區(qū)時，計算磁盤的三維物理扇區(qū)號。

解：

每個柱面的扇區(qū)數(shù)為：10*15=150  (3’)

12345/150=82余45,故12345扇區(qū)所在的柱面為82  (3’)

再將45/15，其商為3，余數(shù)為0，(3’)

故求得12345扇區(qū)所在的磁盤地址為：82柱面，3磁道，0扇區(qū)。(1’)

2假設(shè)移動頭磁盤有200個磁道（0-199號）。目前正在處理143號磁道上的請求，而剛剛處理結(jié)束的請求是125號，如果下面給出的順序是按FIFO排成的等待服務(wù)隊列順序：86，147，91，177，94，150，102，75，130   那么，下列各種磁盤調(diào)度算法來滿足這些請求所需的總磁頭移動量是多少？ 假設(shè)移動頭磁盤有200個磁道（0-199號）。目前正在處理143號磁道上的請求，而剛剛處理結(jié)束的請求是125號，如果下面給出的順序是按FIFO排成的等待服務(wù)隊列順序：86，147，91，177，94，150，175，130   1）FCFS,   2)SSTF

解：

1） FCFS:125à143—86—147—91—177—94—150—102—75—130    (2’)

滿足這些請求所需要的總磁頭移動量為

(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(102-75)+(130-75)

=57+61+65+86+83+56+48+27+55=529   (3’)

2) SSTF:125à143—147—150—130—102—94—91—86—75—177   (2’)

滿足這些請求所需的總磁頭移動量為

(150-143)+(150-75)+(177-75)=7+75+102=182  (3’)

3假設(shè)移動頭磁盤有200個磁道（0-199號）。目前正在處理143號磁道上的請求，而剛剛處理結(jié)束的請求是125號，如果下面給出的順序是按FIFO排成的等待服務(wù)隊列順序：86，147，91，177，94，150，102，75，130   那么，下列各種磁盤調(diào)度算法來滿足這些請求所需的總磁頭移動量是多少？

1)SCAN,   2)C-LOOK

解：

1)SCAN:125à143—147—150—177—199—130—102—94—91—86—75   (2’)

(199-143)+(199-75)=56+124=180   (3’)

2)C-LOOK:125à143—147—150—177 —75—86—91—94—102—130   (2’)

滿足這些請求所需要的總磁頭移動量為

177-143+177-75+130-75=33+102+55=190   (3’)

4假設(shè)一個磁盤由200個磁道，編號從0~199。當前磁頭正在143道上服務(wù)，并且剛剛完成了125道的請求。如果尋道請求隊列的順序是：86，147，91，177，94，150，102，175，130 問：為完成上述請求，下列算法各自磁頭移動的總量是多少？   

①FCFS       ②SSTF   

解：

⑴FCFS磁頭移動順序:

143 à 86 à 147 à 91 à 177 à 94 à 150 à 102 à 175 à 130    (2’)

   57   61    56   86    83   56    48    73    45

磁頭移動總量: 57+61+56+86+83+56+48+73+45=565    (3’)

⑵SSTF磁頭移動順序

143 à 147 à 150 à 130 à 102 à 94 à 91 à 86 à 175 à 177  (2’)

   4     3     20    28    8    3    5    89    2

磁頭移動總量: 4+3+20+28+8+3+5+89+2=162     ( 3’)

5假設(shè)一個磁盤由200個磁道，編號從0~199。當前磁頭正在143道上服務(wù)，并且剛剛完成了125道的請求。如果尋道請求隊列的順序是：86，147，91，177，94，150，102，175，130 問：為完成上述請求，下列算法各自磁頭移動的總量是多少？

① SCAN       ② C-SCAN

解：

（1）SCAN磁頭移動順序

143 à 147 à 150 à 175 à 177 à 199 à130 à 102 à 94 à 91 à 86     (2’)

   4     3     25     2     22   69    28    8    3    5

磁頭移動總量: 4+3+25+2+22+69+28+8+3+5=169   (3’)

（2）C-SCAN磁頭移動順序

143 à 147 à 150 à 175 à 177 à 199 à 0 à 86 à 91 à 94 à 102 à 130    (2’)

   4     3     25    2     22    199  86  5    3    8     28

磁頭移動總量: 4+3+25+2+22+199+86+5+3+8+28=385  (3’)

6磁盤請求以10，22，20，2，40，6，38柱面的次序到達磁盤驅(qū)動器。尋道時每個柱面移動需要6ms，計算以下尋道次序和尋道時間：

①先到先服務(wù)        ②電梯調(diào)度算法（起始移動向上）

   所有情況下磁臂的起始位置都是柱面20。

解:

尋道時間=柱面（磁道）移動總量×6ms

1） 先到先服務(wù)算法的調(diào)度順序：

20 à 10 à 22 à 20 à 2 à 40 à 6 à 38  (2’)

  10   12   2    18  38   34  32

柱面移動總量=10+12+2+18+38+34+32=146   (2’)

尋道時間=146×6ms=876ms   (1’)

2） 電梯算法的調(diào)度順序：

20 à 22 à 38 à 40 à 10 à 6 à 2     (2’)

  2    16   2    30   4   4

柱面移動總量=2+16+2+30+4+4=58   (2’)

尋道時間=58×6ms=348ms  (1’)

7某系統(tǒng)文件存儲空間共有80個柱面，20磁道/柱面，6塊/磁道，每塊有1K字節(jié)。用位示圖表示。每張位示圖為64個字，其中有4個包含的是控制信息。位示圖中的位若為1，表示占用；為0表示空閑。試給出分配和回收一個盤塊的計算公式。

解：每個柱面的塊數(shù)為：20*6=120（塊）(1’)

計算該文件系統(tǒng)的磁盤塊：80*120=9600（塊）(1’)

每張位示圖為64個字，其中有4個字包含的是控制信息。假定每個字為16位。每張可以記錄的塊數(shù)為：(64-4)*16=960（塊）(1’)

總共有9600塊，用位示圖表示，需要占用9600位，每張位示圖可記錄960塊，需要的位示圖數(shù)位：9600/960=10（張），用0~9進行編號。(1’)

1） 分配一個盤塊的計算公式 (3’)

相對塊號=位圖的張?zhí)?960+字號*16+位號

柱面號=（相對塊號/每個柱面的塊數(shù)）的商=（相對塊號/120）的商

磁盤號=（相對塊號/每個柱面的塊數(shù)）的余數(shù)的商

扇區(qū)號=（（相對塊號/每個柱面的塊數(shù)）的余數(shù)）的余數(shù)

2） 回收一個盤塊的計算公式 (3’)

先將三維地址轉(zhuǎn)換為相對塊號，再將相對塊號轉(zhuǎn)換為位圖的字號和位號。

相對塊號=柱面號*120+磁盤號*6+扇區(qū)號

字號=（相對塊號/16）的商

位號=（相對塊號/16）的余數(shù)

               第八章  中斷和信號機制

名詞解釋

1 中斷

是指CPU對系統(tǒng)發(fā)生的某個事件做出的一種反應(yīng)，CPU暫停正在執(zhí)行的程序，保留現(xiàn)場后自動地轉(zhuǎn)去執(zhí)行相應(yīng)的處理程序，處理完該事件后，如被中斷進程的優(yōu)先級最高，則返回斷點繼續(xù)執(zhí)行被“打斷”的程序。

2中斷源

引起中斷的事件或發(fā)出中斷請求的來源稱為中斷。

3中斷請求

中斷源向CPU提出進行處理的請求。

4中斷向量

通常包括相應(yīng)中斷處理程序入口地址和中斷處理時處理機狀態(tài)字。

5異常

它是指來自cpu內(nèi)部的事件或程序執(zhí)行中的事件引起的中斷

6程序性中斷

是指因錯誤地使用指令或數(shù)據(jù)而引起的中斷，用于反映程序執(zhí)行過程中發(fā)現(xiàn)的例外情況，例如，非法操作碼，無效地址、運算溢出，等等。

7斷點

發(fā)生中斷時，被打斷程序的暫停點稱為斷點。

8中斷響應(yīng)

發(fā)生中斷時，cpu暫停執(zhí)行當前的程序，轉(zhuǎn)去處理中斷。這個由硬件對中斷請求做出反應(yīng)的過程，稱為中斷響應(yīng)。

9中斷屏蔽

是指在提出中斷請求之后，cpu不予響應(yīng)的狀態(tài)。它常常用來在處理某個中斷時防止同級中斷的干擾，或在處理一段不可分割的、必須連續(xù)執(zhí)行的程序時防止意外事件把它打斷。

10中斷禁止

是指在可引起中斷的事件發(fā)生時系統(tǒng)不接收該中斷的信號，因而就不可能提出中斷請求而導致中斷。簡言之，就是不讓某些事件產(chǎn)生中斷。

11軟中斷

又稱信號機制，它是在軟件層次上對中斷機制的一種模擬，其中，信號的發(fā)送者相當于中斷源，而接收者（必定是一個進程）相當于cpu。

簡答題

1什么是中斷？什么叫中斷處理？什么叫中斷響應(yīng)？

答：中斷是指計算機在執(zhí)行期間，系統(tǒng)內(nèi)發(fā)生任何非尋常的或非預期的急需處理事件，使得cpu暫時中斷當前正在執(zhí)行的程序而轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，待處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行的過程。

Cpu轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序的過程稱為中斷處理。

Cpu收到中斷請求后轉(zhuǎn)到相應(yīng)的事件處理程序稱為中斷響應(yīng)。

2什么叫關(guān)中斷？什么叫開中斷？什么叫中斷屏蔽？

答：把cpu內(nèi)部的處理機狀態(tài)字psw的中斷允許位清除從而不允許cpu響應(yīng)中斷叫做關(guān)中斷。

設(shè)置cpu內(nèi)部的處理機狀態(tài)字psw的中斷允許位從而允許cpu響應(yīng)中斷叫做開中斷。

中斷屏蔽是指中斷請求產(chǎn)生之后，系統(tǒng)用軟件方式有選擇地封鎖部分中斷而允許其余部分的中斷仍能得到響應(yīng)。

3什么是陷阱？什么是軟中斷？

答：陷阱指處理機和內(nèi)存內(nèi)部產(chǎn)生的中斷，它包括程序運算引起的各種錯誤，如地址非法、檢驗錯、頁面失效。存取訪問控制錯、從用戶態(tài)到核心態(tài)的切換等都是陷阱的例子。

軟中斷是通信進程之間用來模擬硬中斷的一種信號通信方式。

4中斷響應(yīng)主要做哪些工作？由誰來完成？

答：中斷響應(yīng)主要做的工作是：

①中止當前程序的執(zhí)行；

②保存原程序的斷點信息（主要是程序計數(shù)器PC和程序狀態(tài)寄存器PS的內(nèi)容）；

③轉(zhuǎn)到相應(yīng)的處理程序

中斷響應(yīng)由硬件實施。

5敘述缺頁中斷和一般中斷的區(qū)別？

答：缺頁中斷也是中斷的一種，既然是中斷都應(yīng)保護當前運行程序的現(xiàn)場信息，中斷完成后恢復被中斷的現(xiàn)場。但缺頁中斷是當前運行進程自己產(chǎn)生的中斷，且當前指令還未執(zhí)行完，故中斷處理將所需的頁調(diào)入主存后，應(yīng)該恢復該進程重新執(zhí)行被中斷的這條指令。

對一般中斷，中斷源與當前正在執(zhí)行的進程無關(guān)，故正在執(zhí)行的進程執(zhí)行完當前這條指令后才響應(yīng)中斷。中斷處理完成后，可能恢復被中斷的進程，也可能調(diào)度其他進程的運行。即使恢復被中斷進程的運行，恢復后執(zhí)行的指令也是中斷發(fā)生時的下一條指令。

6什么是軟中斷？

答：軟中斷是對硬中斷的一種模擬，發(fā)送軟中斷就是向接收進程的proc結(jié)構(gòu)中的相應(yīng)項發(fā)送一個特定意義的信號 。軟中斷必須等到接收進程執(zhí)行時才能生效 。

7進程在什么時候處理它接收到的軟中斷信號？進程接收到軟中斷信號后放在什么地方？

答：進程在再次被調(diào)度執(zhí)行時先檢查是否收到軟中斷，若進程接收到了軟中斷信號則優(yōu)先處理軟中斷 。進程把接收到軟中斷信號存放在proc結(jié)構(gòu)的相應(yīng)項中 。

8中斷處理的主要步驟是什么？

答：中斷處理的一般步驟是:

保存被中斷程序的現(xiàn)場，

分析中斷原因，

轉(zhuǎn)入相應(yīng)處理程序進行處理，

恢復被中斷程序現(xiàn)場（即中斷返回）。

9什么叫系統(tǒng)調(diào)用？執(zhí)行用戶程序中的系統(tǒng)調(diào)用時，相應(yīng)進程的狀態(tài)會發(fā)生什么變化？

答：系統(tǒng)調(diào)用是用戶在程序中能以“函數(shù)調(diào)用”形式調(diào)用的、由操作系統(tǒng)提供的子功能的集合。每一個子功能稱作一條系統(tǒng)調(diào)用命令。它是操作系統(tǒng)對外的接口，是用戶級程序取得操作系統(tǒng)服務(wù)的唯一途徑。

執(zhí)行到用戶程序中的系統(tǒng)調(diào)用時，相應(yīng)進程的狀態(tài)從用戶態(tài)變?yōu)楹诵膽B(tài)。

10在用戶程序執(zhí)行過程中，CPU接到盤I/O中斷。對此，系統(tǒng)（硬件和軟件）要進行相應(yīng)處理，試列出其主要處理過程。

答：硬件主要處理過程是：cpu中止當前程序的正常執(zhí)行；保存原程序的程序計算器pc和程序狀態(tài)寄存器ps的內(nèi)容：取出盤I/O中斷向量，轉(zhuǎn)到相應(yīng)的處理程序。

軟件主要處理過程是：保存被中斷程序的現(xiàn)場（如通用寄存器的內(nèi)容）：分析中斷原因，由中斷向量得到盤I/O中斷的處理程序地址；運行盤I/O中斷處理程序，判斷I/O工作是否完成，如正常完成，則作I/O結(jié)束處理；執(zhí)行完中斷處理程序，核心恢復前面保存的現(xiàn)場，進程回到用戶態(tài)。