東北大學(xué)秦皇島分校編譯原理操作系統(tǒng)試卷

1、課程名稱:題號-一一-二二-三四五總分得分閱卷人授課專業(yè)： 信息與計算科學(xué) 考試日期：20XX年12月22日 試卷：共二_頁、選擇題：（每題1分，共10分）裝 訂 線 內(nèi) 不A.同步B.互斥C.競爭D.合作B.選擇恰當?shù)淖鳂I(yè)調(diào)度算法D.有一個較好的操作環(huán)境東北大學(xué)秦皇島分校操作系統(tǒng) 試卷：（A ）考試形式： 閉卷1、 （B）的主要特點是提供即時響應(yīng)和高可靠性。生產(chǎn)過程的控制、武器系統(tǒng)、 航空訂票系統(tǒng)、銀行業(yè)務(wù)就是這樣的系統(tǒng)。A.分時系統(tǒng) B.實時系統(tǒng) C.批處理系統(tǒng) D.分布式系統(tǒng)2、下列進程狀態(tài)的轉(zhuǎn)換中，哪一個是不正確的 （C） oA.就緒一運行 B.運行一就緒 C.就緒一阻塞 D.阻塞一就

2、緒3、利用信號量實現(xiàn)進程的（B），應(yīng)為臨界區(qū)設(shè)置一個信號量 mutex，其初值 為1，表示該資源尚未使用，臨界區(qū)應(yīng)置于 P （mutex）和V （mutex）原語 之間。4、作業(yè)調(diào)度的關(guān)鍵在于（B） oA.選擇恰當?shù)倪M程管理程序C.用戶作業(yè)準備充分 5、下列存儲管理方案中，不采用動態(tài)重定位的是（C）oA.頁式管理B.可變分區(qū)C.固定分區(qū)D.段式管理 6、關(guān)于虛擬存儲器，以下說法正確的是（D）oA.可提高計算機運算速度的設(shè)備 B.容量擴大了的主存實際空間C.通過SPOOLING技術(shù)實現(xiàn)的D.可以容納和超過主存容量的多個作業(yè)同時運行的一個地址空間7、下面幾個設(shè)備中，（C）是共享設(shè)備。A.打印機B.

3、磁盤C.讀卡機 D.掃描儀8文件系統(tǒng)采用多級目錄結(jié)構(gòu)的目的，不包括是（B）A.縮短訪問文件的尋找時間B.節(jié)省存儲空間C.解決文件的命名沖突D.易于實現(xiàn)文件共享9、磁盤驅(qū)動調(diào)度算法中（B）算法可能會隨時改變移動臂的運動方向A. 電梯調(diào)度B.先來先服務(wù)C.掃描D.循環(huán)掃描10、正在運行的進程在信號量 S上作P操作之后，當S<0的時候，進程進入信號量的（A）oA.等待隊列B.提交隊列C.后備隊列D.就緒隊列二、填空題：（每空1分，共15分）1、 不論是分時系統(tǒng)、實時系統(tǒng)還是批處理系統(tǒng)都具有四個基本特征并發(fā) 、共享 、 虛擬 、 異步 o2、特權(quán)指令只能在系統(tǒng)態(tài)下執(zhí)行，若在用戶態(tài)下執(zhí)行則被認為是

4、非法指令。3、 _PCB.是進程存在的唯一標志。4、設(shè)基址寄存器內(nèi)容為1000,在采用動態(tài)重定位的系統(tǒng)中，當執(zhí)行指令“LOAD A,2000 ”時，操作數(shù)的實際地址是3000o5、 按照調(diào)度的層次我們把調(diào)度分為高級、 低級、 中級 o6、 根據(jù)文件的邏輯結(jié)構(gòu)，文件可以分為 有結(jié)構(gòu)文件 和 無結(jié)構(gòu)文件_兩類。7、 目前常用的外存分配方法有：連續(xù)分配、鏈接 分配、 索引 分配。三、名詞解釋（每題3分，共12分）1、操作系統(tǒng)：操作系統(tǒng)是一組控制和管理計算機硬件和軟件資源（1分）、合理地對各類作業(yè)進行調(diào)度（1分）、以及方便用戶的程序的集合（1分）。2、臨界區(qū):每個進程中訪問臨界資源的（2分）那段代碼（

5、1分）稱為臨界區(qū)3、對換：所謂對換，是指把內(nèi)存中暫不能運行的進程，或暫不用的程序和數(shù)據(jù)（1分），換出到外存上，以騰出足夠的內(nèi)存空間（1分），把已具備運行條件的進程，或 進程所需的程序和數(shù)據(jù)，換入內(nèi)存（1分）4、設(shè)備獨立性：應(yīng)用程序獨立于具體的物理設(shè)備（3分）。四、簡單題（每題6分，共24分）1、比較程序、進程的區(qū)別。進程是動態(tài)的，程序是靜態(tài)的，程序是有序代碼的集合（1分）；進程是程序的執(zhí) 行（1分）；進程是暫時的，程序的永久的，進程是一個狀態(tài)變化的過程，程序可 長久保存（1分）；進程與程序的組成不同，進程的組成包括程序、數(shù)據(jù)和進程控 制塊（即進程狀態(tài)信息）（1分）；通過多次執(zhí)行，一個程序可對應(yīng)

6、多個進程（1 分）；通過調(diào)用關(guān)系，一個進程可包括多個程序（1分）。P生產(chǎn)者：While(1).Producer an item Wait( SB ) Wait(SM) 緩沖操作Sin gal(SMSi ngal( SB)2、什么是死鎖？死鎖預(yù)防的措施有哪些？所謂死瑣，是指多個進程因競爭資源而造成的一種僵局，若無外力作用， 這些進程都將永遠不能再向前推進（3分）。死鎖預(yù)防的措施有：（1）屏棄 請求和保持”條件，（2）屏棄 不剝奪”條件，（1 分）， （ 3）摒棄環(huán)路等待”條件（1 分）。3、簡述分頁與分段的主要區(qū)別（1）頁是信息的物理單位，已削減內(nèi)存零頭，提高內(nèi)存利用率為目的，而 不是用戶的需求

7、。（1分）段是信息的邏輯單位，具有相對完整的意義，是 為了滿足用戶的需求。（1分）（2）頁的大小固定，由系統(tǒng)確定。（1分）段的大小不固定，決定于用戶編寫的程序。（1分）（3）分頁的作業(yè)地址是一維的。（1分）分段的作業(yè)地址是二維的。（1分）4、什么是局部性原理？什么是抖動？你有什么辦法減少系統(tǒng)的抖動現(xiàn)象？局部性原理是指在幾乎所有程序的執(zhí)行過程中，在一段時間內(nèi)，CPU總是集中地訪問程序中的某一個部分而不是對程序的所有部分具有平均的訪 問概率。（2分）抖動是指當給進程分配的內(nèi)存小于所要求的工作區(qū)時，由于內(nèi)存外存之間交換頻繁，訪問外存的時間和輸入輸出處理時間大大增加，反而造成CPU因等待數(shù)據(jù)而空轉(zhuǎn)，使

8、得整個系統(tǒng)性能大大下降。（2分）在物理系統(tǒng)中，為了防止抖動的產(chǎn)生，在進行淘汰或置換時，一般總是把 缺頁進程鎖住，不讓其換出，從而防止抖動的產(chǎn)生。（1分）防止抖動產(chǎn)生的另一個辦法是設(shè)置較大的內(nèi)存工作區(qū)。（1分）五、應(yīng)用與計算（共39分）1、現(xiàn)有一個具有n個緩沖區(qū)的緩沖池，Produce進程把它生產(chǎn)的消息放入一 個緩沖區(qū)，Consumer進程可從一個緩沖區(qū)中取得一個消息消費。用信號量實 現(xiàn)生產(chǎn)者和消費者之間的同步與互斥。請將下面的生產(chǎn)者和消費者算法補充 完整。生產(chǎn)者和消費者對緩沖池互斥訪問的信號量為SM，緩沖池的初值SB=n,緩沖池中消息個數(shù)初值為SP=0。（本題9分）初值設(shè)置SM= ； SB=n

9、； sp=0C消費者：While(1) .Wait(SB )Wait(SM 緩沖操作Sin gal(SMSin gal(SB )Con sume the item 2、銀行家算法中，若出現(xiàn)下述的資源分配情況：ProcessAllocati onNeedAvailableP00 , 1 , 07,4,33,3,2P12,0,01 , 2,4P23,0,26,5,0P32 , 1 , 10 , 1 , 1P40,0,24,3 , 1試問：（1）當前系統(tǒng)狀態(tài)是否安全？如果安全寫出安全序列。（7分）（2）若進程P1提出請求Request （ 1 , 0,2 ）后，系統(tǒng)能否將資源分配給它? （3分）（1

10、）存在如下進程序列，可使進程順利執(zhí)行完畢： 進程可用資源數(shù)P3：執(zhí)行完5，4，3執(zhí)行完5，4，5R:執(zhí)行完7，4，5Po：執(zhí)行完7，5，5執(zhí)行完10，5，7當前系統(tǒng)是安全的，安全序列是：P3 , P 4 , P 1 , P 0 , P 2 .（8 分）（2）如果將資源分配給進程P1 ,這時所有待執(zhí)行的進程中就沒有滿足所需資源數(shù)<=系統(tǒng)可提供資源數(shù)條件的，所以系統(tǒng)不可以將資源分配P1（2分）3、假設(shè)一磁道有200個柱面，編號為0 199 ,在完成了磁道125處的請 求后，當前正在磁道143處為一請求服務(wù)，若請求隊列的先后順序為86, 147, 91，177，94, 150，102，175，

11、130。試分別采用 FCFS （先來先服務(wù)）、SSTF（最短尋道時間優(yōu)先）算法完成上述請求，寫出磁道移動的順序，并計算磁頭移動的總距離。（本題8分）（1）采用FCFS算法調(diào)度，磁頭移動順序為：143-86-147-91-177-94-150-102-175-130磁頭移動總量為：565 （柱面）。（4分）（2）采用SSTF算法調(diào)度，磁頭移動順序為：143-147-150-130-102-94-91-86-175-177磁頭移動總量為：162 （柱面）。（4分）4、我們打開計算機中的某個 word文檔，然后通過打印機打印文檔中的內(nèi)容, 在這個過程中，操作系統(tǒng)為我們做了什么？試從操作系統(tǒng)功能的角度

12、加以分 析。（本題12分） 進程管理：執(zhí)行時完成調(diào)度（2分）存儲管理：為調(diào)度的進程分配內(nèi)存，以及從硬盤中讀取文件。（2分）文件管理：所調(diào)度文件的查詢與讀取（2分）設(shè)備管理：打印機的驅(qū)動，以及打印工作的執(zhí)行。（2分）用戶接口 ：執(zhí)行程序時的界面，以及程序進程本身所含的系統(tǒng)調(diào)度。（2分）整個過程是五個功能合作完成。（2分）東北大學(xué)秦皇島分校題號-一一-二二-三四總分得分閱卷人授課專業(yè)：計算機考試日期： 年 月曰 試卷：共丄頁裝 訂 線 內(nèi) 不課程名稱：計算機操作系統(tǒng)試卷：JA） 考試形式： 閉卷一、單項選擇題：（每題2分，共30分）1、操作體統(tǒng)是對（）進行管理的軟件。A.軟件 B.硬件 C.計算機

13、資源 D.應(yīng)用程序2、操作系統(tǒng)的基本類型主要有（）A. 批處理系統(tǒng)、分時系統(tǒng)及多任務(wù)系統(tǒng)B. 實時操作系統(tǒng)、分時操作系統(tǒng)及批處理操作系統(tǒng)C. 單用戶系統(tǒng)、多用戶系統(tǒng)及批處理系統(tǒng)D. 實時系統(tǒng)、分時系統(tǒng)和多用戶系統(tǒng)3、在進程管理中，當（）時，進程從阻塞狀態(tài)變?yōu)榫途w狀態(tài)。A.進程被進程調(diào)度程序選中B.等待某一事件C.等待的事件發(fā)生D.時間片用完4、若P、V操作的信號量S初值為2,當前值為-1,則表示有（）等待進程。A. 0個 B. 1個 C. 2個 D. 3個5、操作系統(tǒng)通過（）對進程進行管理。A. JCB B. PCB C. DCT D. CHCT6、多道程序環(huán)境下，操作系統(tǒng)分配資源以（）為基本

14、單位。A.程序 B.指令 C.進程 D.作業(yè)7、發(fā)生死鎖的必要條件有四個，要防止死鎖的發(fā)生，可以破壞這四個必要條 件，但破壞（）條件是不太實際的。A.互斥 B.不可剝奪 C.部分分配D.環(huán)路等待&在分時操作體統(tǒng)中，進程調(diào)度經(jīng)常采用（）算法。A.先來現(xiàn)服務(wù)B.最高優(yōu)先權(quán)C.事件片輪轉(zhuǎn)D.隨機9、系統(tǒng)“抖動”現(xiàn)象的發(fā)生是由（）引起的。A.置換算法選擇不當B.交換的信息量過大C.內(nèi)存容量不足D.請求頁式管理方案10、首次適應(yīng)算法的空閑區(qū)是（）A.按地址遞增順序連在一起B(yǎng).始端指針表指向最大空閑區(qū)C.按大小遞增順序連在一起D.尋找從最大空間區(qū)開始11、 CPU輸出數(shù)據(jù)的速度遠遠高于打印機的打印

15、速度，為了解決這一矛盾，可采用（）A.并行技術(shù)B.通道技術(shù)C.緩沖技術(shù)D.虛擬技術(shù)12、 從用戶的角度看，引入文件系統(tǒng)的主要目的是（）A.實現(xiàn)虛擬存儲B.保存系統(tǒng)文件C.保存用戶和系統(tǒng)文檔D.實現(xiàn)對文件的安名存取13、 在下列文件的物理結(jié)構(gòu)中，（）不利于文件長度增長。A.順序結(jié)構(gòu)B.連接結(jié)構(gòu) C.索引結(jié)構(gòu) D. Hash結(jié)構(gòu)14、磁盤上的文件以（）單位讀寫。A.塊 B.記錄 C.柱面 D.磁道15、操作系統(tǒng)提供給程序員的接口是（）A.進程 B.系統(tǒng)調(diào)用 C.庫函數(shù) D.系統(tǒng)調(diào)用和庫函數(shù)二、填空題：（每空1分，共15分）1、 操作系統(tǒng)的基本功能包括 管理、管理、管理、管理。除此之外還為用戶使用操

16、作系統(tǒng)提供了用戶接口。2、 臨界資源的概念是，而臨界區(qū)是指3、 作業(yè)調(diào)度又被稱為，用于決定把外存上地哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建、分配必要的資源。4、 在頁式存儲器管理中，邏輯地址由和兩部分組成。5、 根據(jù)文件的邏輯結(jié)構(gòu)，文件可以分為 和兩類。6、 目前常用的外存分配方法有：連續(xù)分配、 配、 配。7、 一個進程只有在獲得通道、和所需設(shè)備三者之后，才具備進行 I/O操作的 物質(zhì)條件。三、簡答題（每題5分，共20分）1、程序和進程的主要區(qū)別是什么？2、什么是虛擬存儲器？虛擬存儲器有哪些基本特征?3、段式存儲器管理和頁式存儲器管理的區(qū)別是什么?4、二級目錄和多級目錄的好處是什么?四、應(yīng)用題（共35

17、分）1、現(xiàn)有一個具有n個緩沖區(qū)的緩沖池，Produce進程把它生產(chǎn)的消息放入一 個緩沖區(qū)，Consumer進程可從一個緩沖區(qū)中取得一個消息消費。用信號量實 現(xiàn)生產(chǎn)者和消費者之間的同步與互斥。請將下面的生產(chǎn)者和消費者算法補充 完整。生產(chǎn)者和消費者對緩沖池互斥訪問的信號量為SM，緩沖池的初值SB=n,緩沖池中消息個數(shù)初值為 SP=0。把下面的算法填寫完整。（本題8 分）初值設(shè)置SM=； SB=n； sp=OP生產(chǎn)者：While(1) .Producer an itemWait()C消費者：While(1).Wait( ) 緩沖操作緩沖操作Si ngalC)Singal()Con sume the

18、itemProcessAllocati onNeedAvailableP00,0,3, 20 , 0 , 1, 21 , 6,2, 2P11 , 0,0, 01 , 7,5, 0P21 , 3,5, 42,3,5, 6P30,3,3, 20,6,5, 2P40 , 0 ,1, 40,6,5, 6 2、銀行家算法中，若出現(xiàn)下述的資源分配情況：試問：（1）當前系統(tǒng)狀態(tài)是否安全？如果安全寫出安全序列。（5分）（2）若進程P1提出請求Request （ 1 , 2,2, 2 ）后，系統(tǒng)能否將資源分配給 它？ （ 2分）5、我們打開計算機中的某個 word文檔，然后通過打印機打印文檔中的內(nèi)容，在這個 過

19、程中，操作系統(tǒng)為我們做了什么？試從操作系統(tǒng)五大功能的角度加以分析。（本題10分）3、已知頁面走向為1、2、1、3、1、2、4、2、1、3、4,且開始執(zhí)行時主存 中沒有頁面。若只給作業(yè)分配2個物理塊，采用FIFO頁面淘汰法時缺頁率為 多少？要求寫（畫）出頁面置換過程。（本題5分）4、假設(shè)一磁道有200個柱面，編號為0 199，在完成了磁道125處的請 求后，當前正在磁道143處為一請求服務(wù)，若請求隊列的先后順序為86, 147,91，177，94，150，102，175，130。若采用 SSTF （最短尋道時間優(yōu)先）算 法完成上述請求，寫出磁道移動的順序，并計算磁頭移動的總距離。（本題5分）題號

20、-一一-二二四總分得分閱卷人裝 訂 線 內(nèi) 不東北大學(xué)秦皇島分校課程名稱：編譯原理試卷： 但）答案考試形式： 閉卷授課專業(yè)： 計算機科學(xué)與技術(shù) 考試日期:年 月曰 試卷：共_2_頁一、填空題（每空2分，共30分）1、 編譯程序的整個過程可以從邏輯上劃分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標代碼生成等幾個階段，另外還有兩個重要的工作是 表格管理和出錯處理。2、 規(guī)范規(guī)約中的可歸約串是句柄，算符優(yōu)先分析中的可歸約串是最左素短語3、 語法分析方法主要可分為自頂向下 和 自底向上兩大類。4、 LR （0）文法的項目集中不會出現(xiàn)移講-歸約 沖突和 歸約-歸約 沖突。5、 數(shù)據(jù)空間的

21、動態(tài)存儲分配方式可分為 棧式 和 堆式 兩種。6、 編譯程序是指能將源語言 程序翻譯成目標語言 程序的程序。7、確定有窮自動機 DFA是 NFA 的一個特例。&表達式 （a+b）*c的逆波蘭表示為 ab+c* 。二、選擇題（每題2分，共20分）1、 LR語法分析棧中存放的狀態(tài)是識別 B的DFA狀態(tài)。A、前綴B、可歸前綴C、項目D、句柄2、 D不可能是目標代碼。A、匯編指令代碼B、可重定位指令代碼3、 一個控制流程圖就是具有C的有向圖A、唯一入口結(jié)點B、唯一出口結(jié)點C、唯一首結(jié)點D、唯一尾結(jié)點4、 設(shè)有文法 GS : St b|bBB宀bS，則該文法所描述的語言是C 。A、L （G） =bi|i> 0B、L （G） =b2i|i> 0C、L （G） =b2i+1|i > 0D、L （G） =b 2i+1 |i > 15、 把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由B 完成的。A、編譯器B、匯編器C、解釋器D、預(yù)處理器6、 在目標代碼生成階段，符號表用于D 。A、目標代碼生成B、語義檢查C、語法檢查D、預(yù)處理器地址分配7、規(guī)范歸約是指B。A、最左推導(dǎo)的逆過程B、最右推導(dǎo)的逆過程C、規(guī)范推導(dǎo)D、最左歸約逆過程8、使用 A 可以定義一個程序的意義。A、語義規(guī)則B、詞法規(guī)則C、語法規(guī)則D、左結(jié)合規(guī)則9、 經(jīng)過編譯所得到的目