操作系統(tǒng)概念習(xí)題集錦操作系統(tǒng)概念習(xí)題集錦/NUMPAGES36操作系統(tǒng)概念習(xí)題集錦操作系統(tǒng)概念習(xí)題集錦1引論小結(jié)1．計算機系統(tǒng)由硬件和軟件組成。硬件是計算機系統(tǒng)的物質(zhì)基礎(chǔ)，操作系統(tǒng)是硬件之上的第一層軟件，是支撐其他所有軟件運行的基礎(chǔ)。2．多道程序設(shè)計是指在內(nèi)存中同時存放多道程序，這些程序在管理程序的控制下交替運行，共享處理機及系統(tǒng)中的其他資源。在單處理機系統(tǒng)中多道程序運行的特點是：·多道：計算機內(nèi)存中同時存放多道相互獨立的程序?！ず暧^上并行：同時進入系統(tǒng)的多道程序都處于運行過程中，即它們先后開始了各自的運行，但都未運行完畢?！の⒂^上串行：內(nèi)存中的多道程序輪流占有CPU，交替執(zhí)行。3．操作系統(tǒng)是一組控制和管理計算機硬件和軟件資源，合理地組織計算機工作流程，以及方便用戶的程序的集合。4．操作系統(tǒng)有三種基本類型，即批處理操作系統(tǒng)、分時操作系統(tǒng)及實時操作系統(tǒng)?！づ幚聿僮飨到y(tǒng)能對一批作業(yè)自動進行處理，在批處理系統(tǒng)中引入多道程序設(shè)計技術(shù)就形成了多道批處理系統(tǒng)。多道批處理系統(tǒng)的主要特征是用戶脫機使用計算機、成批處理及多道程序運行?！ぴ诜謺r操作系統(tǒng)中，處理機的運行時間被分成很短的時間片，系統(tǒng)按時間片輪流把處理機分配給各聯(lián)機作業(yè)使用，若某個作業(yè)在分配給它的時間片內(nèi)不能完成其計算，則該作業(yè)暫時停止運行，把處理機讓給另一個作業(yè)使用，等待下一輪時再繼續(xù)其運行。分時系統(tǒng)的特征是同時性、交互性、獨立性和及時性?！崟r系統(tǒng)能及時響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)完成對該事件的處理，并控制所有實時設(shè)備和實時任務(wù)協(xié)調(diào)一致地工作。實時系統(tǒng)的主要特征是響應(yīng)及時和可靠性高。5．操作系統(tǒng)的特征是并發(fā)性、共享性、虛擬性及不確定性。·并發(fā)是指兩個或多個事件在同一時間間隔內(nèi)發(fā)生?！す蚕硎侵赶到y(tǒng)中的資源供多個用戶共同使用。·虛擬是指把一個物理實體變?yōu)槿舾蓚€邏輯實體。·不確定性是指系統(tǒng)中各種事件發(fā)生的時間及順序是不可預(yù)測的。6．操作系統(tǒng)的主要功能包括處理機管理、存儲器管理、設(shè)備管理和文件管理。處理機管理的主要功能包括：進程控制、進程同步、進程通信及調(diào)度。存儲器管理的主要功能包括：內(nèi)存分配、內(nèi)存保護、地址映射及內(nèi)存擴充。設(shè)備管理的主要功能包括：設(shè)備分配、設(shè)備驅(qū)動及設(shè)備獨立性。文件管理的主要功能包括：文件存儲空間的管理、目錄管理、文件操作管理及文件保護。7．操作系統(tǒng)提供兩種類型的用戶接口：命令接口提供一組操作命令供用戶直接或間接控制作業(yè)的運行；程序接口提供一組系統(tǒng)調(diào)用供用戶在程序中請求操作系統(tǒng)服務(wù)。習(xí)題1（1）什么是操作系統(tǒng)？從資源管理的角度看，操作系統(tǒng)應(yīng)具有哪些功能？（2）操作系統(tǒng)有哪幾種基本類型？它們各有何特點？（3）什么是多道程序設(shè)計技術(shù)？多道程序設(shè)計技術(shù)的特點是什么？（4）簡述并發(fā)與并行的區(qū)別。（5）簡述操作系統(tǒng)在計算機系統(tǒng)中的位置。（6）操作系統(tǒng)有哪些特征？（7）操作系統(tǒng)是隨著多道程序設(shè)計技術(shù)的出現(xiàn)逐步發(fā)展起來的，要保證多道程序的正確運行，在技術(shù)上要解決哪些基本問題？（8）用戶與操作系統(tǒng)之間存在哪幾種接口？（9）有一臺計算機，具有1MB內(nèi)存，操作系統(tǒng)占用200KB，每個用戶進程各占200KB。如果用戶進程等待I/O的時間為80%，若增加1MB內(nèi)存，則CPU的利用率提高多少？（10）一個計算機系統(tǒng)，有一臺輸入機和一臺打印機，現(xiàn)有兩道程序投入運行，且程序A先開始做，程序B后開始運行。程序A的運行軌跡為：計算50ms、打印100ms、再計算50ms、打印100ms，結(jié)束。程序B的運行軌跡為：計算50ms、輸入80ms、再計算100ms，結(jié)束（假設(shè)開始時刻為0）。試說明：①兩道程序運行時，CPU有無空閑等待？若有，在哪段時間內(nèi)等待？為什么會等待？②程序A、B有無等待CPU的情況？若有，指出發(fā)生等待的時刻。2進程描述與控制小結(jié)1．一個程序通常由若干個操作組成，這些操作必須按照某種先后次序執(zhí)行，僅當(dāng)前一個操作執(zhí)行完成后才能執(zhí)行后繼操作，這類計算過程就是程序的順序執(zhí)行過程。程序順序執(zhí)行時具有如下特征：·順序性：處理機的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，當(dāng)上一個操作完成后下一個操作才能開始。·封閉性：程序一旦開始運行，其執(zhí)行結(jié)果不受外界因素影響。·可再現(xiàn)性：只要程序執(zhí)行時的初始條件和執(zhí)行環(huán)境相同，當(dāng)程序重復(fù)執(zhí)行時，都將獲得相同的結(jié)果。2．程序的并發(fā)執(zhí)行是指若干個程序或程序段同時在系統(tǒng)中運行，這些程序或程序段的執(zhí)行在時間上是重疊的，一個程序或程序段的執(zhí)行尚未結(jié)束，另一個程序或程序段的執(zhí)行已經(jīng)開始。程序并發(fā)執(zhí)行時有如下特征：·間斷性：程序在并發(fā)執(zhí)行時具有“執(zhí)行—暫停執(zhí)行—執(zhí)行”這種間斷性的活動規(guī)律?！なシ忾]性：并發(fā)執(zhí)行的程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行失去封閉性。·不可再現(xiàn)性：程序并發(fā)執(zhí)行時，由于失去了封閉性，也將導(dǎo)致失去其運行結(jié)果的可再現(xiàn)性。3．進程是程序在一個數(shù)據(jù)集合上的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。進程具有以下特征：·動態(tài)性：進程是一個動態(tài)的概念，是程序在處理機上的一次執(zhí)行過程?！げl(fā)性：多個進程實體同時存在于內(nèi)存中，在一段時間內(nèi)并發(fā)執(zhí)行。·獨立性：進程是能獨立運行的基本單位，也是系統(tǒng)進行資源分配和調(diào)度的獨立單位。·異步性：系統(tǒng)中的各進程以獨立的、不可預(yù)知的速度向前推進?！そY(jié)構(gòu)性：從結(jié)構(gòu)上看，進程由程序段、數(shù)據(jù)段和一個進程控制塊組成。4．進程控制塊是描述進程屬性的數(shù)據(jù)結(jié)構(gòu)，進程控制塊中通常包含進程名、進程當(dāng)前狀態(tài)、進程隊列指針、程序和數(shù)據(jù)地址、進程優(yōu)先級、CPU現(xiàn)場保護區(qū)、通信信息、家族關(guān)系、資源清單等信息。5．進程有三種基本狀態(tài)：·就緒狀態(tài)：進程已獲得除處理機外的所有資源，一旦獲得處理機就可以立即執(zhí)行。·執(zhí)行狀態(tài)：進程獲得必要的資源并正在處理機上執(zhí)行。·阻塞狀態(tài)：進程因等待某事件的發(fā)生而暫時無法執(zhí)行下去。6．進程控制的職責(zé)是對系統(tǒng)中的所有進程實施有效的管理。常見的進程控制原語有進程創(chuàng)建、進程撤消、進程阻塞和進程喚醒。7．操作系統(tǒng)內(nèi)核是基于硬件的第一次軟件擴充?，F(xiàn)代操作系統(tǒng)中把一些與硬件緊密相關(guān)或運行頻率較高的模塊以及公用的一些基本操作安排在靠近硬件的軟件層次中，并使它們常駐內(nèi)存以提高操作系統(tǒng)的運行效率，通常把這部分軟件稱為操作系統(tǒng)內(nèi)核。操作系統(tǒng)內(nèi)核的主要功能包括中斷、時鐘管理、進程管理、存儲器管理、設(shè)備管理等。8．原語是由若干條機器指令構(gòu)成的一段程序，用以完成特定功能，這段程序在執(zhí)行期間不可分割。9．計算機系統(tǒng)中有兩種運行狀態(tài)：核心態(tài)和用戶態(tài)。核心態(tài)是操作系統(tǒng)管理程序執(zhí)行時機器所處的狀態(tài)。用戶態(tài)是用戶程序執(zhí)行時機器所處的狀態(tài)。10．線程是進程內(nèi)一個相對獨立的、可調(diào)度的執(zhí)行單元。線程自己基本上不擁有資源，只擁有一點在運行時必不可少的資源（如程序計數(shù)器、一組寄存器和棧），但它可以與同屬一個進程的其他線程共享進程擁有的全部資源。習(xí)題2（1）進程的定義是什么？它最少有哪幾種狀態(tài)？（2）什么是管態(tài)？什么是目態(tài)？（3）試畫出下面四條語句的前趨圖：S1：a=x+2；S2：b=y+4；S3：c=a+b；S4：d=c+6；（4）試?yán)肂ernstein條件證明解答題3中的語句S1和S2可以并發(fā)執(zhí)行，而語句S3和S4不能并發(fā)執(zhí)行。（5）進程與線程的主要區(qū)別是什么？（6）進程控制塊何時產(chǎn)生？何時消除？它有什么作用？（7）已知一個求值公式(A2+3B)/(B+5A)，若A，B已賦值，試畫出該公式求值過程的前趨圖。（8）試對下列系統(tǒng)任務(wù)作出比較：①創(chuàng)建一個進程與創(chuàng)建一個線程；②兩個進程間通信與同一進程中兩個線程間通信；③同一進程中兩個線程的上下文切換與不同進程中兩個線程的上下文切換。（9）在一個分時操作系統(tǒng)中，進程可能出現(xiàn)如圖1所示的變化，請把產(chǎn)生每一種變化的具體原因填在表1的相應(yīng)框中。、表1進程狀態(tài)變化原因變化原因（1）（2）（3）（4）（5）運行運行就緒隊列數(shù)據(jù)資源等I/O傳輸（1）（2）（3）（4）（5）圖1進程狀態(tài)變化圖3進程同步與通信小結(jié)1．進程之間的相互制約關(guān)系有兩類：直接制約及間接制約。進程之間因相互合作而產(chǎn)生的制約關(guān)系稱為直接制約關(guān)系，進程之間因共享資源而產(chǎn)生的相互制約關(guān)系稱為間接制約關(guān)系。2．一次僅允許一個進程使用的資源稱為臨界資源。進程中訪問臨界資源的那段代碼稱為臨界區(qū)。3．對臨界資源的訪問過程可以分成四個部分：進入?yún)^(qū)、臨界區(qū)、退出區(qū)及剩余區(qū)。4．訪問臨界資源的進程必須滿足如下條件：·當(dāng)有若干進程要求進入它們的臨界區(qū)時，應(yīng)在有限時間內(nèi)使一個進程進入臨界區(qū)?！っ看沃炼嘤幸粋€進程處于臨界區(qū)內(nèi)?！みM程在臨界區(qū)內(nèi)僅逗留有限的時間。5．多個相互合作的進程在一些關(guān)鍵點上可能需要互相等待或互相交換信息，這種相互制約關(guān)系稱為進程同步。當(dāng)一個進程正在使用某資源時，其他希望使用該資源的進程必須等待，當(dāng)該進程用完資源并釋放后，才允許其他進程去訪問此資源，進程之間的這種相互制約關(guān)系為互斥。6．鎖是一個代表資源狀態(tài)的變量，通常用0表示資源可用，用1表示資源已被占用。利用鎖機制解決互斥問題的方法是：上鎖、訪問臨界資源、開鎖。7．信號量由兩個成員構(gòu)成，其中一個是具有非負(fù)初值的整型變量，另一個是初始狀態(tài)為空的隊列。除信號量的初值外，信號量的值僅能由P、V操作改變。8．信號量值的含義是：當(dāng)其大于0時表示系統(tǒng)中當(dāng)前可用資源的數(shù)目；當(dāng)其小于0時，其絕對值表示系統(tǒng)中因請求該資源而阻塞等待的進程數(shù)目。9．設(shè)s為一個信號量，P（s）的主要功能是：先執(zhí)行s=s-1；若s≥0則進程繼續(xù)運行；若s＜0則阻塞該進程，并將它插入該信號量的等待隊列中。V（s）的主要功能是：先執(zhí)行s=s+1；若s＞0則進程繼續(xù)執(zhí)行；若s≤0則從該信號量等待隊列中移出第一個進程，使其變?yōu)榫途w狀態(tài)并插入就緒隊列，然后再返回原進程繼續(xù)執(zhí)行。10．管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)。管程由局部于管程的共享數(shù)據(jù)結(jié)構(gòu)說明、對這些數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程以及對這些數(shù)據(jù)結(jié)構(gòu)設(shè)置初值的語句組成。11．管程具有以下基本特性：·局部于管程的數(shù)據(jù)只能被局部于管程內(nèi)的過程所訪問。·一個進程只有通過調(diào)用管程內(nèi)的過程才能進入管程訪問共享數(shù)據(jù)?！っ看蝺H允許一個進程在管程內(nèi)執(zhí)行某個內(nèi)部過程。12．進程通信是指進程之間的信息交換。高級進程通信方式是指進程之間以較高的效率傳送大量數(shù)據(jù)。13．目前常用的高級進程通信方式有：共享存儲器系統(tǒng)、消息傳遞系統(tǒng)以及管道通信系統(tǒng)。14．根據(jù)消息傳遞系統(tǒng)實現(xiàn)方式不同可以分為：·直接通信方式：發(fā)送進程直接把消息發(fā)送給接收進程，并將它掛在接收進程的消息緩沖隊列上，接收進程從消息緩沖隊列中取得消息。·間接通信方式：發(fā)送進程把消息發(fā)送到信箱中，接收進程從信箱中取得消息。習(xí)題3（1）什么是臨界資源？什么是臨界區(qū)？對臨界資源的訪問有哪些原則？（2）請給出P、V操作的定義。如何用P、V操作實現(xiàn)進程間的互斥？（3）請用P、V操作寫出一個不會出現(xiàn)死鎖的哲學(xué)家進餐問題的解？（4）什么是管程？它由哪幾部分組成？（5）高級進程通信方式有哪幾類？各自如何實現(xiàn)進程間通信？（6）設(shè)有六個進程P1、P2、P3、P4、P5、P6，它們有如圖3.5所示的并發(fā)關(guān)系。試用P、V操作實現(xiàn)這些進程間的同步。圖3.5六個合作進程的并發(fā)關(guān)系（7）有一單向行駛的公路橋，每次只允許一輛汽車通過。當(dāng)汽車到達橋頭時，若橋上無車，便可上橋；否則需等待，直到橋上的汽車下橋為止。若每一輛汽車為一個進程，請用P、V操作保證汽車按要求過橋。（8）今有三個并發(fā)進程R、M、P，它們共享了一個可循環(huán)使用的緩沖區(qū)B，緩沖區(qū)B共有N個單元。進程R負(fù)責(zé)從輸入設(shè)備讀信息，每讀一個字符后，把它存入到緩沖區(qū)B的一個單元中；進程M負(fù)責(zé)處理讀入的字符，若發(fā)現(xiàn)讀入的字符中有空格符，則把它改成“，”；進程P負(fù)責(zé)把處理后的字符取出并打印輸出。當(dāng)緩沖區(qū)單元中的字符被進程P取出后，則又可用來存放下一次讀入的字符。請用P、V操作為同步機制寫出它們能正確并發(fā)執(zhí)行的程序。（9）在生產(chǎn)者-消費者問題中，如果對調(diào)生產(chǎn)者描述中的兩個P操作會發(fā)生什么情況？如果對調(diào)生產(chǎn)者描述中的兩個V操作的順序又會發(fā)生什么情況？（10）一個快餐廳有4類職員：①領(lǐng)班：接受顧客點菜；②廚師：準(zhǔn)備顧客的飯菜；③打包工：將做好的飯菜打包；④出納員：收款并提交食品。每個職員可被看作一個進程，試用一種同步機制寫出能讓四類職員正確并發(fā)運行的程序。（11）設(shè)公共汽車上，司機和售票員的活動分別如下：①司機的活動：啟動車輛：正常行車；到站停車。②售票員的活動：關(guān)車門；售票；開車門。在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關(guān)系？用信號量和P、V操作實現(xiàn)它們的同步。（12）消息通信有哪幾種方式？試說明消息緩沖通信機構(gòu)的基本工作過程。4調(diào)度與死鎖小結(jié)1．作業(yè)是用戶在一次解題或一個事務(wù)處理過程中要求計算機系統(tǒng)所做工作的集合，包括用戶程序、所需的數(shù)據(jù)及命令等。計算機系統(tǒng)在完成一個作業(yè)的過程中所做的一項相對獨立的工作稱為一個作業(yè)步。2．調(diào)度有三個層次：作業(yè)調(diào)度、進程調(diào)度和交換調(diào)度?！ぷ鳂I(yè)調(diào)度的主要任務(wù)是按一定的原則從外存上處于后備狀態(tài)的作業(yè)中選擇一個或多個，給它們分配內(nèi)存、輸入/輸出設(shè)備等必要的資源，并建立相應(yīng)的進程，以使該作業(yè)具有獲得競爭處理機的權(quán)利?！みM程調(diào)度的主要任務(wù)是按照某種策略和方法從就緒隊列中選取一個進程，將處理機分配給它?！そ粨Q調(diào)度的主要任務(wù)是按照給定的原則和策略，將處于外存對換區(qū)中的重又具備運行條件的進程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存的暫時不能運行的進程交換到外存對換區(qū)。3．周轉(zhuǎn)時間是指從作業(yè)提交到作業(yè)完成之間的時間間隔。帶權(quán)周轉(zhuǎn)時間是指作業(yè)周轉(zhuǎn)時間與作業(yè)實際運行時間的比。4．作業(yè)有提交、后備、運行和完成四種狀態(tài)。提交狀態(tài)是指用戶作業(yè)正由輸入設(shè)備向系統(tǒng)外存輸入。后備狀態(tài)是指作業(yè)在外存后備隊列中等待調(diào)度。運行狀態(tài)是指作業(yè)在內(nèi)存中運行。完成狀態(tài)是指作業(yè)已完成了其計算任務(wù)，正準(zhǔn)備撤離計算機系統(tǒng)。5．進程調(diào)度方式有兩種：搶占方式和非搶占方式?！屨挤绞绞侵府?dāng)一個進程正在處理機上執(zhí)行時，若有某個更為重要或緊迫的進程需要使用處理機，則立即暫停正在執(zhí)行的進程，將處理機分配給更重要或緊迫的進程。·非搶占方式是指當(dāng)某一個進程正在處理機上執(zhí)行時，即使有某個更為重要或緊迫的進程進入就緒隊列，仍然讓正在執(zhí)行的進程繼續(xù)執(zhí)行，直到該進程完成或發(fā)生某種事件而進入阻塞狀態(tài)時，才把處理機分配給更為重要或緊迫的進程。6．常見的調(diào)度算法有：·先來先服務(wù)：按作業(yè)或進程到達的先后順序進行調(diào)度。·短作業(yè)優(yōu)先：按作業(yè)或進程運行時間的長短進行調(diào)度，優(yōu)先調(diào)度運行時間最短的作業(yè)或進程?！?yōu)先級調(diào)度算法：按作業(yè)或進程的優(yōu)先級進行調(diào)度，優(yōu)先調(diào)度優(yōu)先級高的作業(yè)或進程。進程優(yōu)先級分為兩種：靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級。靜態(tài)優(yōu)先級是在創(chuàng)建進程時確定的，確定之后在整個進程運行期間不再改變。動態(tài)優(yōu)先級是指在創(chuàng)建進程時，根據(jù)進程的特點及相關(guān)情況確定一個優(yōu)先級，在進程運行過程中再根據(jù)情況的變化調(diào)整優(yōu)先級。·時間片輪轉(zhuǎn)調(diào)度算法用于進程調(diào)度，該算法將處理機時間分為很短的時間片，按時間片輪流將處理機分配給就緒隊列中的各進程使用?！じ唔憫?yīng)比優(yōu)先調(diào)度算法主要用于作業(yè)調(diào)度，該算法選擇響應(yīng)比最高的作業(yè)投入運行。·多級隊列調(diào)度算法的思想是將就緒隊列劃分為若干個子隊列，每個進程固定屬于一個就緒隊列，每個就緒隊列采用一種調(diào)度算法，不同的隊列可以采用不同的調(diào)度算法?！ざ嗉壏答侁犃姓{(diào)度算法的實現(xiàn)思想是：在系統(tǒng)中設(shè)置多個就緒隊列，第1個隊列的優(yōu)先級最高，第2個隊列次之，其余隊列的優(yōu)先級逐次降低；每個隊列中進程的時間片與優(yōu)先級成反比；當(dāng)新進程進入系統(tǒng)時將它放入第1個隊列末尾，按先來先服務(wù)的原則排隊等待調(diào)度。當(dāng)輪到該進程執(zhí)行時，如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第2個隊列的末尾，依此類推，最后一個隊列中使用時間片輪轉(zhuǎn)調(diào)度算法；處理機調(diào)度采用搶占式優(yōu)先級調(diào)度算法，當(dāng)處理機正在執(zhí)行第i個隊列中的某進程時，若其處理機被搶占則該進程仍然回到第i個隊列末尾。7．死鎖是指多個進程因競爭系統(tǒng)資源或相互通信而處于永久阻塞狀態(tài)，若無外力作用，這些進程都將無法向前推進。8．死鎖產(chǎn)生的原因是競爭資源和進程推進順序非法。9．死鎖產(chǎn)生有以下四個必要條件：互斥條件、不剝奪條件、請求和保持條件、循環(huán)等待條件。10．死鎖的處理方法有以下幾種：忽略死鎖、預(yù)防死鎖、避免死鎖、檢測及解除死鎖。11．死鎖的預(yù)防是通過設(shè)置某些限制條件以破壞產(chǎn)生死鎖的四個必要條件之一來實現(xiàn)的，但互斥條件不能破壞。12．死鎖的避免是通過某種方法防止系統(tǒng)進入不安全狀態(tài)來實現(xiàn)的。銀行家算法是典型的死鎖避免算法。13．通過對資源分配圖的簡化可以檢測系統(tǒng)是否存在死鎖。常用的解除死鎖方法有兩種：資源剝奪法、撤消進程法。習(xí)題4（1）產(chǎn)生死鎖的必要條件是什么？解決死鎖問題常用哪幾種措施？（2）某進程被喚醒后立即投入運行，我們就說這個系統(tǒng)采用的是剝奪調(diào)度方法，對嗎？為什么？（3）何謂高級調(diào)度、中級調(diào)度和低級調(diào)度？（4）什么是有序資源分配方法？為什么有序資源分配方法可以防止死鎖？（5）設(shè)系統(tǒng)中僅有一類獨占型資源，進程一次只能申請一個資源。系統(tǒng)中多個進程競爭該類資源。試判斷下述哪些情況會發(fā)生死鎖，為什么？1）資源數(shù)為4，進程數(shù)為3，每個進程最多需要2個資源。2）資源數(shù)為6，進程數(shù)為2，每個進程最多需要4個資源。（6）單道批處理系統(tǒng)中，有四個作業(yè)，其有關(guān)情況如表2所示。若采用先來先服務(wù)、短作業(yè)優(yōu)先、響應(yīng)比高者優(yōu)先調(diào)度算法，試分別計算其平均周轉(zhuǎn)時間T和平均帶權(quán)周轉(zhuǎn)時間W。表2作業(yè)的提交時間和運行時間作業(yè)J1J2J3J4提交時間/h8.08.68.89.0運行時間/h2.00.60.20.5（7）何謂JCB？其作用是什么？JCB至少包括哪些內(nèi)容？（8）在單CPU和兩臺輸入/輸出設(shè)備（I1,I2）多道程序設(shè)計環(huán)境下，同時有三個作業(yè)J1，J2，J3運行。這三個作業(yè)使用CPU和輸入/輸出設(shè)備的順序和時間如下所示：J1：I2（30ms）；CPU（10ms）；I1（30ms）；CPU（10ms）；I2（20ms）J2：I1（20ms）；CPU（20ms）；I2（40ms）J3：CPU（30ms）；I1（20ms）；CPU（10ms）；I1（10ms）假定CPU，I1，I2都能并行工作，J1優(yōu)先級最高，J2次之，J3優(yōu)先級最低，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU，但不能搶占I1、I2。試求：1）三個作業(yè)從開始到完成分別需要多少時間？2）從開始到完成的CPU利用率。3）每種I/O設(shè)備的利用率。（9）表3給出了系統(tǒng)某時刻的資源分配情況：表3資源分配表資源情況進程已分配資源還需要的資源剩余資源r1r2r3r1r2r3r1r2r3ABCDE311000110101000100012300010210120試問：1）該狀態(tài)是否安全?2）如果進程B提出請求RequestB(0，1，0)，系統(tǒng)能否將資源分配給它？3）如果進程E提出請求RequestE(0，1，0)，系統(tǒng)能否將資源分配給它？（10）考慮一個共有150個存儲單元的系統(tǒng)，如下分配給三個進程，P1最大需求70，己占有25；P2最大需求60，己占有40；P3最大需求60，己占有45。使用銀行家算法，以確定下面的每個請求是否安全。如果安全，找出安全序列；如果不安全，給出結(jié)果分配情況。1）P4進程到達，P4最大需求60，最初請求25個。2）P4進程到達，P4最大需求60，最初請求35個。（11）產(chǎn)生死鎖的四個必要條件是否都是獨立的？或者一個或多個條件的成了蘊含了另一個或一些條件的成立？（12）一個系統(tǒng)有m個同類資源，由n個進程共享，并且1）Needi>0，對于i=1,2,…,n；2）所有進程對該類資源的需求總和小于m+n，證明該系統(tǒng)無死鎖。5存儲管理小結(jié)1．存儲分配有三種方式：直接分配方式、靜態(tài)分配方式和動態(tài)分配方式。直接分配指程序員在編寫程序或編譯程序?qū)υ闯绦蚓幾g時采用內(nèi)存物理地址；靜態(tài)分配指在作業(yè)裝入內(nèi)存時確定它們在內(nèi)存中的位置，作業(yè)一旦進入內(nèi)存后在整個運行過程中不能在內(nèi)存中移動，也不能再申請內(nèi)存空間；動態(tài)分配指在裝入時確定作業(yè)在內(nèi)存中的位置，但在其執(zhí)行過程中可根據(jù)需要申請附加的內(nèi)存空間。2．程序中的地址稱為邏輯地址，邏輯地址的集合稱為地址空間；內(nèi)存中物理單元的地址稱為物理地址，物理地址的集合稱為存儲空間。3．地址變換是指將作業(yè)地址空間中的邏輯地址變換成存儲空間中的物理地址，也稱為地址映射、地址重定位。4．重定位分為兩類：靜態(tài)重定位和動態(tài)重定位。靜態(tài)重定位是在程序裝入時進行重定位；動態(tài)重定位是在程序執(zhí)行過程中，每當(dāng)訪問指令或數(shù)據(jù)時，將要訪問的邏輯地址轉(zhuǎn)換成物理地址。5．單一連續(xù)分配是一種最簡單的存儲管理方式，這種存儲管理方式將內(nèi)存分為兩個連續(xù)存儲區(qū)域，其中的一個存儲區(qū)域固定分配給操作系統(tǒng)使用，另一個存儲區(qū)域給用戶作業(yè)使用。6．按分區(qū)數(shù)目的變化情況可將分區(qū)存儲管理劃分為：固定分區(qū)存儲管理和動態(tài)分區(qū)存儲管理。固定分區(qū)存儲管理將內(nèi)存空間劃分為若干個固定大小的分區(qū)，每個分區(qū)中可以裝入一道程序；動態(tài)分區(qū)存儲管理是在作業(yè)進入內(nèi)存時，根據(jù)作業(yè)的大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適應(yīng)作業(yè)的需要。7．目前常用的動態(tài)分區(qū)分配算法有以下四種：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法及最壞適應(yīng)算法?！な状芜m應(yīng)算法要求空閑分區(qū)按地址遞增的次序排列，在進行內(nèi)存分配時，從空閑分區(qū)表或空閑分區(qū)鏈?zhǔn)组_始順序查找，直到找到第一個能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)大小從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表或空閑分區(qū)鏈中。·循環(huán)首次適應(yīng)算法是首次適應(yīng)算法的變形，在為作業(yè)分配內(nèi)存空間時，從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直到找到第一個能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)大小從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表或空閑分區(qū)鏈中?！ぷ罴堰m應(yīng)算法要求空閑分區(qū)按容量大小遞增的次序排列，在進行內(nèi)存分配時，從空閑分區(qū)表或空閑分區(qū)鏈?zhǔn)组_始順序查找，直到找到第一個能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)大小從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表或空閑分區(qū)鏈中。·最壞適應(yīng)算法要求空閑分區(qū)按容量大小遞減的次序排列，在進行內(nèi)存分配時，先檢查空閑分區(qū)表或空閑分區(qū)鏈中的第一個空閑分區(qū)，若第一個空閑分區(qū)小于作業(yè)要求的大小，則分配失??；否則從該空閑分區(qū)中劃出與作業(yè)大小相等的一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表或空閑分區(qū)鏈中。8．動態(tài)分區(qū)存儲管理系統(tǒng)中，分區(qū)回收時有四種情況：上鄰接、下鄰接、上、下鄰接和不鄰接，前三種情況下還需要進行分區(qū)的合并。9．碎片是指內(nèi)存中無法利用的存儲空間。碎片分為內(nèi)部碎片和外部碎片：內(nèi)部碎片是指分配給作業(yè)的存儲空間中未被利用的部分，外部碎片是指系統(tǒng)中無法利用的小存儲塊。10．拼接是指通過移動把多個分散的小分區(qū)拼接成一個大分區(qū)。11．存儲保護是為了防止一個作業(yè)有意或無意地破壞操作系統(tǒng)或其他作業(yè)。12．在分頁存儲管理系統(tǒng)中，作業(yè)地址空間劃分成若干大小相等的頁，相應(yīng)地將內(nèi)存的存儲空間分成與頁大小相等的塊，在為作業(yè)分配存儲空間時，總是以塊為單位來分配，可以將作業(yè)中的某一頁放到內(nèi)存的某一空閑塊中。13．在分段存儲管理系統(tǒng)中，作業(yè)的地址空間劃分為若干個邏輯分段，每個分段是一組邏輯意義相對完整的信息集合，每個分段都有自己的名字，每個分段都從0開始編址并采用一段連續(xù)的地址空間。內(nèi)存分配以段為單位，每段分配一個連續(xù)的內(nèi)存區(qū)，但各段之間不要求連續(xù)。14．在段頁式存儲管理系統(tǒng)中，作業(yè)的地址空間首先被分成若干個邏輯分段，每段都有自己的段號，然后再將每段分成若干個大小固定的頁，內(nèi)存空間分成若干個和頁面大小相同的物理塊，對內(nèi)存的分配以物理塊為單位。習(xí)題5（1）存儲管理的主要功能是什么？（2）在內(nèi)存管理中，“內(nèi)零頭”和“外零頭”各指的是什么？在固定式分區(qū)分配、可變式分區(qū)分配、頁式虛擬存儲系統(tǒng)、段式虛擬存儲系統(tǒng)中，各會存在何種零頭？為什么？（3）在段式存儲管理和段頁式存儲管理中，邏輯地址是如何表示的？從用戶角度來看分別為幾維空間？（4）什么叫重定位？重定位有哪幾種類型？采用內(nèi)存分區(qū)管理時，如何實現(xiàn)程序運行時的動態(tài)重定位？（5）考慮一個分頁表系統(tǒng)，其頁表存放在內(nèi)存。①如果一次內(nèi)存的訪問時間是200ns，訪問一頁內(nèi)存需要多少時間？②如果引入快表，并且75%的頁表引用發(fā)生在快表中，假設(shè)快表的訪問時間忽略不計，則內(nèi)存的有效訪問時間是多少？（6）使用伙伴系統(tǒng)分配一個1MB的內(nèi)存塊。①畫圖說明內(nèi)存中下面的作業(yè)請求、返回過程：作業(yè)A請求70KB；作業(yè)B請求35KB；作業(yè)C請求80KB；返回作業(yè)A；作業(yè)D請求60KB；返回作業(yè)B；返回作業(yè)D；返回作業(yè)C。②給出返回作業(yè)B的二叉樹表示。6虛擬存儲器小結(jié)1．虛擬存儲器是指具有請求調(diào)入和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。常見的虛擬存儲器實現(xiàn)方案有請求分頁存儲管理、請求分段存儲管理和請求段頁式存儲管理。2．局部性原理是指程序執(zhí)行時，在一個較短的時間內(nèi)僅使用程序代碼的一部分，相應(yīng)地程序所訪問的存儲空間也局限于某個區(qū)域。3．缺頁中斷是一個比較特殊的中斷，它與一般中斷的區(qū)別主要表現(xiàn)在：在指令的執(zhí)行期間產(chǎn)生和處理缺頁中斷，一條指令可以產(chǎn)生多個缺頁中斷。4．常見的頁面置換算法有：·最佳置換算法選擇內(nèi)存中不再訪問或在最長時間以后才需要訪問的頁面予以淘汰?！は冗M先出置換算法選擇內(nèi)存中駐留時間最長的頁面予以淘汰?！ぷ罱罹梦词褂盟惴ㄟx擇最近一段時間內(nèi)最長時間沒有被訪問過的頁面予以淘汰。5．抖動現(xiàn)象是指系統(tǒng)把大部分時間用在了頁面的調(diào)入/換出上，而幾乎不能完成任何有效的工作。習(xí)題6（1）設(shè)有8頁的邏輯地址空間，每頁有1024字節(jié)，它們被映射到32塊的物理存儲區(qū)中。那么，邏輯地址的有效位是多少？物理地址至少是多少位。（2）在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：3、4、2、1、4、3、1、4、3、1、4、5，并采用LRU頁面置換算法。設(shè)分給該作業(yè)的存儲塊數(shù)為3，試求出在訪問過程中發(fā)生缺頁中斷的次數(shù)及缺頁率。（3）假定某頁式管理系統(tǒng)的內(nèi)存容量為64KB，分成16塊，塊號為0，1，2，3，4，…，15。設(shè)某作業(yè)有4頁，其頁號為0，1，2，3，被分別裝入內(nèi)存的2、4、1、6塊。試：1）寫出該作業(yè)每一頁在內(nèi)存中的起始地址。2）有多個邏輯地址[0，100]、[1，50]、[2，0]、[3，60]，試計算出相應(yīng)的內(nèi)存地址。（方括號內(nèi)的第一個元素為頁號，第二個元素為頁內(nèi)位移）（4）在某段式存儲管理系統(tǒng)中，有一作業(yè)的段表如表6.5所示，求邏輯地址[0，65]，[1，55]，[2，90]，[3，20]對應(yīng)的內(nèi)存地址（按十進制）。（其中方括號中的第一個元素為段號，第二個元素為段內(nèi)位移）表6.5段表段號段長內(nèi)存起始地址狀態(tài)0123200501001506008501000-0001（5）一個32位地址的計算機系統(tǒng)使用二級頁表，虛地址被分為9位頂級頁表，11位二級頁表和偏移。試問：頁表長度是多少？虛地址空間共有多少個頁面？（6）某計算機有緩存、內(nèi)存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在緩存中，訪問它需要Ans；如果在內(nèi)存但不在緩存，需要Bns將其裝入緩存，然后才能訪問；如果不在內(nèi)存而在輔存，需要Cns將其讀入內(nèi)存，然后，用Bns再讀入緩存，然后才能訪問。假設(shè)緩存命中率為（n-1）/n，內(nèi)存命中率為（m-1）/m，則數(shù)據(jù)平均訪問時間是多少？（7）一臺機器有48位虛地址和32位物理地址，若頁長為8KB，問頁表共有多少個頁表項?如果設(shè)計一個反置頁表，則有多少個頁表項?（8）有兩臺計算機P1和P2，它們各有一個硬件高速緩沖存儲器C1和C2，且各有一個主存儲器M1和M2。其性能為：C1C2M1M2存儲容量4KB4KB2MB2MB存取周期60ns80ns1μs0.9μs若兩臺機器指令系統(tǒng)相同，它們的指令執(zhí)行時間與存儲器的平均存取周期成正比。如果在執(zhí)行某個程序時，所需指令或數(shù)據(jù)在高速緩沖存儲器中存取到的概率P是0.7，試問：這兩臺計算機哪個速度快？當(dāng)P=0.9時，處理器的速度哪個快？7設(shè)備管理小結(jié)1．按設(shè)備的共享屬性可以將設(shè)備分為獨占設(shè)備、共享設(shè)備和虛擬設(shè)備?！お氄荚O(shè)備是指在一段時間內(nèi)只允許一個用戶進程使用的設(shè)備?！す蚕碓O(shè)備是指在一段時間內(nèi)允許多個進程使用的設(shè)備?！ぬ摂M設(shè)備是指通過虛擬技術(shù)將一臺獨占設(shè)備改造成若干臺邏輯設(shè)備，供若干個用戶進程同時使用，通常把這種經(jīng)過虛擬技術(shù)處理后的設(shè)備稱為虛擬設(shè)備。2．設(shè)備獨立性又稱設(shè)備無關(guān)性，是指應(yīng)用程序獨立于物理設(shè)備。3．按信息交換單位可以將設(shè)備分為字符設(shè)備和塊設(shè)備。字符設(shè)備處理信息的基本單位是字符，塊設(shè)備處理信息的基本單位是字符塊。4．I/O通道是指專門負(fù)責(zé)輸入/輸出工作的處理機。通道所執(zhí)行的程序稱為通道程序。根據(jù)信息交換方式的不同，可以將通道分成以下三種類型：字節(jié)多路通道、數(shù)據(jù)選擇通道、數(shù)據(jù)多路通道。5．常用的輸入/輸出控制方式有程序直接控制方式、中斷控制方式、DMA控制方式和通道控制方式。6．中斷是指計算機系統(tǒng)內(nèi)發(fā)生了某一急需處理的事件，使得CPU暫時中止當(dāng)前正在執(zhí)行的程序而轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，待處理完畢后又返回到原來被中斷處繼續(xù)執(zhí)行。7．緩沖的引入緩和了CPU與設(shè)備速度不匹配的矛盾；提高了設(shè)備和CPU的并行操作程度；減少了設(shè)備對CPU的中斷頻率，放寬了對中斷響應(yīng)時間的限制。8．與設(shè)備分配相關(guān)的主要數(shù)據(jù)結(jié)構(gòu)有：設(shè)備控制表、控制器控制表、通道控制表和系統(tǒng)設(shè)備表。9．設(shè)備分配中主要采用先請求先服務(wù)和優(yōu)先級高者優(yōu)先兩種算法。10．設(shè)備分配的安全性是指在設(shè)備分配中應(yīng)保證不發(fā)生死鎖。11．設(shè)備分配有靜態(tài)分配方式和動態(tài)分配方式兩種。靜態(tài)分配是在用戶作業(yè)開始執(zhí)行之前，由系統(tǒng)一次分配該作業(yè)所要求的全部設(shè)備、設(shè)備控制器和通道。動態(tài)分配是在進程執(zhí)行過程中根據(jù)需要進行設(shè)備分配。12．Spooling的意思是同時外部設(shè)備聯(lián)機操作，又稱為假脫機輸入輸出操作，是操作系統(tǒng)中采用的一項將獨占設(shè)備改造成共享設(shè)備的技術(shù)。Spooling系統(tǒng)的組成包括三部分：輸入井和輸出井、輸入緩沖區(qū)和輸出緩沖區(qū)、輸入進程和輸出進程。13．I/O設(shè)備管理軟件一般分為四層：中斷處理程序、設(shè)備驅(qū)動程序、與設(shè)備無關(guān)軟件和用戶空間的軟件。習(xí)題7小結(jié)（1）為什么要設(shè)置內(nèi)存I/O緩沖區(qū)？通常有哪幾類緩沖區(qū)？（2）什么是設(shè)備驅(qū)動程序？其功能是什么？（3）在設(shè)備管理中，何謂設(shè)備獨立性？如何實現(xiàn)設(shè)備獨立性？（4）DMA控制方式與中斷控制方式有什么不同？（5）簡述中斷處理過程。（6）計算機系統(tǒng)中，屏幕顯示分辨率為640×480，若要存儲一屏256彩色的圖像，需要多少字節(jié)存儲空間？8文件管理1．文件系統(tǒng)是指操作系統(tǒng)中與文件管理有關(guān)的軟件和數(shù)據(jù)的集合。文件系統(tǒng)由三部分組成：與文件管理有關(guān)的軟件、被管理的文件以及實施文件管理所需的數(shù)據(jù)結(jié)構(gòu)。2．文件結(jié)構(gòu)是指文件的組織形式，文件結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩種。文件的邏輯結(jié)構(gòu)是從用戶觀點出發(fā)所看到的文件組織形式，文件的物理結(jié)構(gòu)是指文件在外存上的存儲組織形式。3．文件的邏輯結(jié)構(gòu)可以分為兩種形式：記錄式文件和流式文件。記錄式文件由一組相關(guān)記錄組成，流式文件由一系列字符組成。4．常見的文件物理結(jié)構(gòu)有順序結(jié)構(gòu)、鏈接結(jié)構(gòu)和索引結(jié)構(gòu)?！ろ樞蚪Y(jié)構(gòu)將一個邏輯文件的信息存放在外存的連續(xù)物理塊中。以順序結(jié)構(gòu)存放的文件稱為順序文件?！ゆ溄咏Y(jié)構(gòu)將一個邏輯文件的信息存放在外存的多個物理塊中，同時用指針將存放同一個文件的物理塊鏈接起來。采用鏈接結(jié)構(gòu)存放的文件稱為鏈接文件?！に饕Y(jié)構(gòu)將一個邏輯文件的信息存放于外存的多個物理塊中，并為每個文件建立一個索引表，索引表中的每個表項存放文件信息所在的邏輯塊號和與之對應(yīng)的物理塊號。采用索引結(jié)構(gòu)存放的文件稱為索引文件。5．文件的存取方法有：順序存取法、直接存取