南京大學(xué)模擬題

1、南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系操作系統(tǒng)期末試卷（2003年12月28）一、簡答題1、 列出I/O控制方式。2、 列出文件的共享方式。3、 列出幾種實(shí)時(shí)調(diào)度算法。4、 列舉系統(tǒng)發(fā)生死鎖的必要條件。5、 虛擬存儲(chǔ)器的容量與什么有關(guān)?6、 列出可變分區(qū)搜索分配算法。7、 列出影響缺頁中斷率的主要因素。8、 列出管程的主要特性。二、問答題1、假設(shè)有一個(gè)操作系統(tǒng)采用層次結(jié)構(gòu)組成，它運(yùn)行在裸機(jī)上，并有以下層次組成：作業(yè)管理、設(shè)備管理、內(nèi)存管理、命令管理、文件管理、進(jìn)程調(diào)度及內(nèi)核支撐功能，試給出一種由底向上的正確層次。2、試從資源管理的觀點(diǎn)，敘.述操作系統(tǒng)的功能和任務(wù)。3、敘述操作系統(tǒng)中引入”進(jìn)程”和”線程”的

2、主要目的。4、敘述進(jìn)程通信及其分類。5、敘述SPOOLING系統(tǒng)的技術(shù)特點(diǎn)、組成和數(shù)據(jù)結(jié)構(gòu)。6、敘述內(nèi)存映射文件的基本原理和優(yōu)點(diǎn)。7、解釋微內(nèi)核與單內(nèi)核操作系統(tǒng)，說明微內(nèi)核結(jié)構(gòu)設(shè)計(jì)的主要優(yōu)點(diǎn)。8、來自處理器和主存內(nèi)部的中斷稱“異?！保信e它的分類及主要區(qū)別?三、計(jì)算題1、如果一個(gè)操作系統(tǒng)采用LFU頁面置換算法的一個(gè)變種：每個(gè)頁框?qū)?yīng)一個(gè)計(jì)數(shù)器，用來計(jì)數(shù)曾經(jīng)裝入過一個(gè)頁框的頁面?zhèn)€數(shù)，當(dāng)有多個(gè)候選淘汰頁面所在的頁框計(jì)數(shù)器具有相同的最小值時(shí)，按FIFO進(jìn)行。現(xiàn)在有一個(gè)進(jìn)程分到了4個(gè)頁框，則對如下頁面走向求出缺頁中斷次數(shù)及淘汰的頁號。 1 , 2 , 3 ,4 , 5 ,3 , 4, 1, 6,7,

3、8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 7, 22、假定在某移動(dòng)臂磁盤上，剛剛處理了訪問38號柱面的請求，目前正在40號柱面讀信息，并且有下述請求序列等待訪問磁盤。試分別使用電梯調(diào)度算法和最短尋找時(shí)間優(yōu)先算法列出實(shí)際處理上述請求的次序。請求次序12345678欲訪問的柱面號77209594452916583、某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100K，磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時(shí)間。現(xiàn)有作業(yè)序列如下：作業(yè)號 進(jìn)入輸入井時(shí)間 運(yùn)行時(shí)間 主存需求量 磁帶需求 打印機(jī)需求 1 8:00 25分鐘 15K 1 1 2

4、 8:20 10分鐘 30K 0 1 3 8:20 20分鐘 60K 1 0 4 8:30 20分鐘 20K 1 0 5 8:35 15分鐘 10K 1 1 作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動(dòng)已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時(shí)間。現(xiàn)求：(1)作業(yè)被調(diào)度的先后次序?(2)全部作業(yè)運(yùn)行結(jié)束的時(shí)間?(3)作業(yè)平均周轉(zhuǎn)時(shí)間?(4)最大作業(yè)周轉(zhuǎn)時(shí)間?四、信號量、P-V題1、桌上有一只盤子，最多可以容納兩個(gè)水果，每次僅能放入或取出一個(gè)水果。爸爸向盤子中放蘋果(apple)，媽媽向盤子中放桔子(orange)，兩個(gè)兒子專等吃盤子中的桔子，兩個(gè)女兒專等吃盤子中的蘋果。試用：信號

5、量和P、V操作編寫實(shí)現(xiàn)爸爸、媽媽、兒子、女兒間正確工作的程序。2、在一個(gè)盒子里有數(shù)量相等的黑、白兩種棋子，現(xiàn)有兩個(gè)進(jìn)程P1和P2，其中P1專揀白子，P2專揀黑子；規(guī)定每個(gè)進(jìn)程每次只揀一個(gè)子；一個(gè)進(jìn)程揀子時(shí)，另一個(gè)進(jìn)程不能去揀；P1和P2必須交替揀子；按黑先白后次序揀子。請用Monitor寫出實(shí)現(xiàn)該自動(dòng)分揀系統(tǒng)和進(jìn)程P1、P2的調(diào)用程序。南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系操作系統(tǒng)期末試卷（2004年12月28）一、解釋題1. 解釋操作系統(tǒng)為用戶提供了虛擬機(jī)。2. 解釋并發(fā)與并行，并說明兩者關(guān)系。3. 解釋多道程序與多重處理，并說明兩者關(guān)系。4. 解釋模式切換與進(jìn)程切換，并說明兩者關(guān)系。5. 解釋死鎖與“

6、饑餓”。6. 解釋管程及其組成 。7. 解釋中斷及異常。8. 解釋硬中斷和軟中斷。二、問答題1. 敘述LRU、NRU和LFU三種頁面置換算法的思想，并各給出一種可能的實(shí)現(xiàn)方案。2. 敘述操作系統(tǒng)的安全策略、安全模型和安全機(jī)制。3. 在一個(gè)分布式系統(tǒng)中，如何對系統(tǒng)中的事件進(jìn)行一致性排序?4. 試解釋多級頁表與反置頁表。5. 簡述操作系統(tǒng)虛擬性在設(shè)備管理中的應(yīng)用。6. 用墊腳石過河，每塊墊腳石僅允許一個(gè)人使用，當(dāng)兩人在河中相遇且都互不退讓時(shí)，則出現(xiàn)了死鎖。試寫出產(chǎn)生死鎖的4個(gè)必要條件，并就“過河問題”給出破壞死鎖的4個(gè)必要條件的方法。三、計(jì)算題1. 使用位示圖：0行開始共20行、0列開始共30列來

7、表示空閑盤塊狀態(tài)，設(shè)首盤塊號為1。假如當(dāng)分配一個(gè)盤塊號為140時(shí)，其在位示圖中的行、列數(shù)應(yīng)為多少?當(dāng)釋放一個(gè)盤塊號為 301 時(shí)，其所在位示圖中的行、列數(shù)為多少?2. 在一個(gè)操作系統(tǒng)中，如果一個(gè)盤塊的大小為1KB，每個(gè)盤塊號占 4 個(gè)字節(jié)，采用直接地址(為10塊)、一次間接、二次間接及三次間接的成組鏈接法保存文件。那么，一個(gè)進(jìn)程要訪問偏移量為287744B處的數(shù)據(jù)時(shí)，需要經(jīng)過幾次間接?3. 在一個(gè)請求分頁存儲(chǔ)管理系統(tǒng)中，某程序的頁面走向?yàn)椋?，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。假設(shè)分得的頁框數(shù)是3，并且開始時(shí)頁框中是空的，則分別采用最佳替換算法和LRU

8、頁面替換算法，在訪問過程中發(fā)生缺頁中斷率各為多少?4. 磁盤調(diào)度采用SCAN調(diào)度算法，設(shè)任務(wù)隊(duì)列欲訪問的柱面號為66、65、124、14、122、37、183、98。試計(jì)算服務(wù)結(jié)束時(shí)，磁頭總共移動(dòng)了多少個(gè)柱面。假設(shè)磁盤共有200個(gè)柱面(編號0-199)，開始服務(wù)時(shí)，磁頭剛從60移到66柱面。四、綜合題1有5個(gè)作業(yè)依次進(jìn)入系統(tǒng)，到達(dá)時(shí)間、運(yùn)行時(shí)間、所需內(nèi)存容量列于下表。設(shè)內(nèi)存容量為100KB，采用可變分區(qū)存儲(chǔ)管理，且作業(yè)在主存不能移動(dòng)。作業(yè)調(diào)度采用先來先服務(wù)算法，作業(yè)對應(yīng)的進(jìn)程調(diào)度采用內(nèi)存中的就緒進(jìn)程平分CPU時(shí)間，不計(jì)作業(yè)對換及其他系統(tǒng)開銷。試求各作業(yè)(進(jìn)程)開始執(zhí)行時(shí)間、完成時(shí)間、周轉(zhuǎn)時(shí)間填

9、入表中。(可直接填入下表。)作業(yè) 提交時(shí)間 需運(yùn)行時(shí)間 作業(yè)長度 開始執(zhí)行時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間J1 10:00 25 15J2 10:20 30 60 J3 10:20 25 40J4 10:30 15 20J5 10:35 10 302請用信號量編程解決以下的“過獨(dú)木橋”問題：同一方向的行人可連續(xù)過橋，當(dāng)某一方向有人過橋時(shí)，另一方向的行人必須等待；當(dāng)某一方向無人過橋時(shí)，另 一方向的行人可以過橋。3假設(shè)有如右圖所示的工作模型，有三個(gè)并發(fā)進(jìn)程P1、P2和P3，兩個(gè)單緩沖B1和B2。進(jìn)程P1負(fù)責(zé)不斷從輸入設(shè)備讀數(shù)據(jù)，若讀入的數(shù)據(jù)為正數(shù)，則直接送入B2，否則應(yīng)先將數(shù)據(jù)送入B1，經(jīng)P2取出加工后再

10、送入B2，P3從B2中取信息輸出。請用信號量操作描述進(jìn)程P1、P2、P3實(shí)現(xiàn)同步的算法。許昌學(xué)院2008-2009學(xué)年第一學(xué)期期末考試試題一、選擇題1、在現(xiàn)代操作系統(tǒng)中引入了（ ），從而使并發(fā)和共享成為可能。A.單道程序 B. 磁盤 C. 對象 D.多道程序 2、( )操作系統(tǒng)允許在一臺(tái)主機(jī)上同時(shí)連接多臺(tái)終端，多個(gè)用戶可以通過各自的終端同時(shí)交互地使用計(jì)算機(jī)。 A.網(wǎng)絡(luò) B.分布式 C.分時(shí) D.實(shí)時(shí)3、從用戶的觀點(diǎn)看，操作系統(tǒng)是（ ）。 A. 用戶與計(jì)算機(jī)硬件之間的接口 B.控制和管理計(jì)算機(jī)資源的軟件 C. 合理組織計(jì)算機(jī)工作流程的軟件 D.計(jì)算機(jī)資源的的管理者 4、當(dāng)CPU處于管態(tài)時(shí)，它可以

11、執(zhí)行的指令是（ ）。 A. 計(jì)算機(jī)系統(tǒng)中的全部指令 B. 僅限于非特權(quán)指令 C. 僅限于訪管指令 D. 僅限于特權(quán)指令5、用戶在程序中試圖讀取某文件的第100個(gè)邏輯塊時(shí)，使用操作系統(tǒng)提供的（ ）接口。 A. 系統(tǒng)調(diào)用 B.圖形用戶接口 C.原語 D.鍵盤命令6、下列幾種關(guān)于進(jìn)程的敘述，（ ）最不符合操作系統(tǒng)對進(jìn)程的理解？A.進(jìn)程是在多程序并行環(huán)境中的完整的程序。 B.進(jìn)程可以由程序、數(shù)據(jù)和進(jìn)程控制塊描述。C.線程是一種特殊的進(jìn)程。 D.進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。7、當(dāng)一個(gè)進(jìn)程處于（ ）狀態(tài)時(shí)，稱其為等待（或阻塞）狀態(tài)。 A. 它正等待中央處

12、理機(jī) B. 它正等待合作進(jìn)程的一個(gè)消息 C. 它正等待分給它一個(gè)時(shí)間片 D. 它正等待進(jìn)入內(nèi)存8、一個(gè)進(jìn)程釋放一種資源將有可能導(dǎo)致一個(gè)或幾個(gè)進(jìn)程（ ）。A.由就緒變運(yùn)行 B.由運(yùn)行變就緒 C.由阻塞變運(yùn)行 D.由阻塞變就緒9、下面關(guān)于線程的敘述中，正確的是（ ）。A.不論是系統(tǒng)支持線程還是用戶級線程，其切換都需要內(nèi)核的支持。 B.線程是資源的分配單位，進(jìn)程是調(diào)度和分配的單位。 C.不管系統(tǒng)中是否有線程，進(jìn)程都是擁有資源的獨(dú)立單位。 D.在引入線程的系統(tǒng)中，進(jìn)程仍是資源分配和調(diào)度分派的基本單位。10、設(shè)有3個(gè)作業(yè)，它們同時(shí)到達(dá)，運(yùn)行時(shí)間分別為T1、T2和T3,且T1T2T3，若它們在單處理機(jī)系統(tǒng)

13、中按單道運(yùn)行，采用短作業(yè)優(yōu)先調(diào)度算法，則平均周轉(zhuǎn)時(shí)間為（ ）。 A. T1+T2+T3 B. (T1+T2+T3)/3 C. T1+T2/3+2*T3/3 D.T3/3+2*T2/3+T111、在下面的I/O控制方式中，需要CPU干預(yù)最少的方式是（ ）。A程序I/O方式 B中斷驅(qū)動(dòng)I/O控制方式 C直接存儲(chǔ)器訪問DMA控制方式 DI/O通道控制方式12、有m個(gè)進(jìn)程共享同一臨界資源，若使用信號量機(jī)制實(shí)現(xiàn)對一臨界資源的互斥訪問，則信號量的變化范圍是（ ）。A.1至 (m-1) B.1至m-1 C.1至m D.1至m13、對資源編號，要求進(jìn)程按照序號順序申請資源，是破壞了死鎖必要條件中的哪一條？（

14、）A. 互斥 B. 請求與保持 C. 不可剝奪 D. 循環(huán)等待14、某系統(tǒng)采用了銀行家算法，則下列敘述正確的是（ ）。A.系統(tǒng)處于不安全狀態(tài)時(shí)一定會(huì)發(fā)生死鎖 B.系統(tǒng)處于不安全狀態(tài)時(shí)可能會(huì)發(fā)生死鎖C.系統(tǒng)處于安全狀態(tài)時(shí)可能會(huì)發(fā)生死鎖 D.系統(tǒng)處于安全狀態(tài)時(shí)一定會(huì)發(fā)生死鎖15、CPU輸出數(shù)據(jù)的速度遠(yuǎn)遠(yuǎn)高于打印機(jī)的打印速度，為解決這一矛盾，可采用（）A并行技術(shù) B緩沖技術(shù) C虛擬存儲(chǔ)器技術(shù) D覆蓋技術(shù)16、下面最有可能使得高地址空間成為大的空閑區(qū)的分配算法是（ ）。A.首次適應(yīng)法 B.最佳適應(yīng)法 C.最壞適應(yīng)法 D.循環(huán)首次適應(yīng)法17、在下面關(guān)于虛擬存儲(chǔ)器的敘述中，正確的是（ ）。A.要求程序運(yùn)行

15、前必須全部裝入內(nèi)存且在運(yùn)行過程中一直駐留在內(nèi)存B.要求程序運(yùn)行前不必全部裝入內(nèi)存且在運(yùn)行過程中不必一直駐留在內(nèi)存C.要求程序運(yùn)行前不必全部裝入內(nèi)存但是在運(yùn)行過程中必須一直駐留在內(nèi)存D.要求程序運(yùn)行前必須全部裝入內(nèi)存但在運(yùn)行過程中不必一直駐留在內(nèi)存18、采用段式存儲(chǔ)管理的系統(tǒng)中，若地址用24位表示，其中8位表示段號，則允許每段的最大長度是（ ）。A.224 B.216 C.28 D.23219、在可變式分區(qū)分配方案中，某一作業(yè)完成后，系統(tǒng)收回其主存空間，并與相鄰空閑區(qū)合并，為此需修改空閑區(qū)表，造成空閑區(qū)數(shù)減1的情況是（ ）。A.無上鄰空閑區(qū)，也無下鄰空閑區(qū) B.有上鄰空閑區(qū)，但無下鄰空閑區(qū)C.有

16、下鄰空閑區(qū)，但無上鄰空閑區(qū) D.有上鄰空閑區(qū)，也有下鄰空閑區(qū)20、MS-DOS系統(tǒng)中的磁盤文件物理結(jié)構(gòu)屬于（ ）。A. 連續(xù)文件 B. 鏈接文件 C. 索引文件 D. 散列文件二、填空題21、 操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中的一個(gè)_，它管理和控制計(jì)算機(jī)系統(tǒng)中的_。22、 進(jìn)程主要由_、_和_三部分內(nèi)容組成，其中_是進(jìn)程存在的惟一標(biāo)識，而_部分也可以為其它進(jìn)程共享。23、在一個(gè)具有2個(gè)處理器的操作系統(tǒng)中共有n 個(gè)進(jìn)程，在不考慮進(jìn)程狀態(tài)過渡的情況下，阻塞進(jìn)程隊(duì)列中最多有_ 個(gè)進(jìn)程。某一時(shí)刻，處于執(zhí)行狀態(tài)的進(jìn)程為0個(gè)，且當(dāng)前處理機(jī)空閑，處于就緒狀態(tài)的進(jìn)程有_ 個(gè)。24、當(dāng)處理器空閑時(shí)，調(diào)度程序從 _ 進(jìn)程隊(duì)

17、列中選擇一個(gè)進(jìn)程給其分配CPU，處于_狀態(tài)的進(jìn)程是不會(huì)獲得CPU的。25、在響應(yīng)比最高者優(yōu)先的作業(yè)調(diào)度算法中，當(dāng)各個(gè)作業(yè)等待時(shí)間相同時(shí)，_ 的作業(yè)將得到優(yōu)先調(diào)度；當(dāng)各個(gè)作業(yè)要求運(yùn)行的時(shí)間相同時(shí)，_ 的作業(yè)得到優(yōu)先調(diào)度。26、某系統(tǒng)中共有10臺(tái)磁帶機(jī)被 m 個(gè)進(jìn)程競爭，每個(gè)進(jìn)程最多要求3臺(tái)磁帶機(jī)，那么當(dāng)m的取值為_時(shí)，系統(tǒng)不會(huì)發(fā)生死鎖。27、 設(shè)有8頁的邏輯空間，每頁有1024字節(jié)，它們被映射32塊的物理存儲(chǔ)區(qū)中，那么，邏輯地址的有效位是_位，物理地址至少是_位。28、 在一個(gè)分頁存儲(chǔ)管理系統(tǒng)中，頁長為4KB，頁號物理塊號031426某一作業(yè)的頁表如圖1所示，虛擬地址3000對應(yīng)的物理地址為_。

18、 圖1 作業(yè)頁表29、虛擬設(shè)備是通過_技術(shù)把獨(dú)占設(shè)備變成能為若干用戶_的設(shè)備。30、已知某文件采用串聯(lián)結(jié)構(gòu)，它由10個(gè)邏輯記錄組成，每個(gè)邏輯記錄剛好存放于一個(gè)磁盤塊上，都為1024字節(jié)，并依次存放在10、61、32、75、87、98、46、37、33和11號磁盤塊上。若要存取文件相對于文件頭偏移7654字節(jié)處的信息，則要訪問的磁盤塊塊號為_，塊內(nèi)的偏移量是_。三、簡答題31、什么是進(jìn)程？什么是線程？進(jìn)程與線程有何區(qū)別？32、什么是死鎖？產(chǎn)生死鎖的原因和必要條件是什么？33、說明作業(yè)調(diào)度，中級調(diào)度和進(jìn)程調(diào)度的區(qū)別，并分析下述問題應(yīng)由哪一級調(diào)度程序負(fù)責(zé)。 (1) 在可獲得處理機(jī)時(shí)，應(yīng)將它分給哪個(gè)就

19、緒進(jìn)程； (2) 在短期繁重負(fù)載下，應(yīng)將哪個(gè)進(jìn)程暫時(shí)掛起。四、綜合題34、在一個(gè)請求分頁系統(tǒng)中，假設(shè)系統(tǒng)分配給某進(jìn)程的物理塊數(shù)為3，開始時(shí)內(nèi)存為空，執(zhí)行如下訪問頁號序列： 1，2，3，4，1，2，5，1，2，3，4，5 試說明采用先進(jìn)先出(FIFO) 、最近最少使用（LRU）和最佳置換算法(OPT)進(jìn)行頁面置換時(shí)，缺頁次數(shù)各是多少？（要有詳細(xì)的計(jì)算過程，只給出結(jié)果者，本題不得分）35、（13分）如圖2所示，系統(tǒng)中有三個(gè)進(jìn)程GET、PRO和PUT，共用兩個(gè)緩沖區(qū)BUF1和BUF2。假設(shè)BUF1中最多可放11個(gè)信息，現(xiàn)已放入了兩個(gè)信息；BUF2最多可放5個(gè)信息。GET進(jìn)程負(fù)責(zé)不斷地將輸入信息送入B

20、UF1中，PRO進(jìn)程負(fù)責(zé)從BUF1中取出信息進(jìn)行處理，并將處理結(jié)果送到BUF2中，PUT進(jìn)程負(fù)責(zé)從BUF2中讀取結(jié)果并輸出。試寫出正確實(shí)現(xiàn)GET、PRO、PUT的同步與互斥的算法（要求：（1）用類C語言描述，條理清楚，注釋恰當(dāng)；（2）信號量原語統(tǒng)一使用wait和signal。）PUT PRO GETBUF2BUF1 圖2 進(jìn)程合作進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先級p1091P2143P3282P4310436（10分）設(shè)有4個(gè)進(jìn)程P1、P2、P3和P4，它們到達(dá)就緒隊(duì)列的時(shí)間、運(yùn)行時(shí)間及優(yōu)先級如右表所示。試回答下列問題：（1）若采用可剝奪的優(yōu)先級調(diào)度算法，給出各個(gè)進(jìn)程的調(diào)度次序以及平均周轉(zhuǎn)時(shí)間。（說明：數(shù)字越大大，優(yōu)先級越高）（2）若采用時(shí)間片（時(shí)間片單位為2）輪轉(zhuǎn)調(diào)度算法，試給出各個(gè)進(jìn)程的調(diào)度次序及平均周轉(zhuǎn)時(shí)間。37（8分）有5個(gè)記錄A、B、C、D和E，存放在磁盤的某磁道上。假定這個(gè)磁道劃分成5塊，每塊存放一個(gè)記錄，安排如下表所示。塊號12345記錄號ABCDE現(xiàn)在要順序處理這5個(gè)記錄，如果盤旋轉(zhuǎn)一周需20ms，處理程序每讀出一個(gè)記錄后要花6ms進(jìn)行處理，試問： （1）處理完這5個(gè)記錄所需的總時(shí)間是多少？ （2）為減少磁盤旋轉(zhuǎn)的周數(shù)，應(yīng)如何安排這5個(gè)記錄，并計(jì)算