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

-PAGE9-裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)東北大學(xué)秦皇島分校裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)課程名稱：操作系統(tǒng)試卷：(A)考試形式：閉卷授課專業(yè)：信息與計(jì)算科學(xué)考試日期：2004年12月22日試卷：共3頁題號(hào)一二三四五總分得分閱卷人選擇題：（每題1分，共10分）1、（B）的主要特點(diǎn)是提供即時(shí)響應(yīng)和高可靠性。生產(chǎn)過程的控制、武器系統(tǒng)、航空訂票系統(tǒng)、銀行業(yè)務(wù)就是這樣的系統(tǒng)。A.分時(shí)系統(tǒng) B.實(shí)時(shí)系統(tǒng)C.批處理系統(tǒng)D.分布式系統(tǒng)2、下列進(jìn)程狀態(tài)的轉(zhuǎn)換中，哪一個(gè)是不正確的(C)。A.就緒一運(yùn)行B.運(yùn)行一就緒C.就緒一阻塞D.阻塞一就緒3、利用信號(hào)量實(shí)現(xiàn)進(jìn)程的（B），應(yīng)為臨界區(qū)設(shè)置一個(gè)信號(hào)量mutex，其初值為1，表示該資源尚未使用，臨界區(qū)應(yīng)置于P（mutex）和V（mutex）原語之間。A.同步 B.互斥C.競爭 D.合作4、作業(yè)調(diào)度的關(guān)鍵在于(B)。A.選擇恰當(dāng)?shù)倪M(jìn)程管理程序B.選擇恰當(dāng)?shù)淖鳂I(yè)調(diào)度算法C.用戶作業(yè)準(zhǔn)備充分D.有一個(gè)較好的操作環(huán)境5、下列存儲(chǔ)管理方案中，不采用動(dòng)態(tài)重定位的是（C）。A.頁式管理 B.可變分區(qū)C.固定分區(qū)D.段式管理6、關(guān)于虛擬存儲(chǔ)器，以下說法正確的是（D）。A.可提高計(jì)算機(jī)運(yùn)算速度的設(shè)備B.容量擴(kuò)大了的主存實(shí)際空間C.通過SPOOLING技術(shù)實(shí)現(xiàn)的D.可以容納和超過主存容量的多個(gè)作業(yè)同時(shí)運(yùn)行的一個(gè)地址空間7、下面幾個(gè)設(shè)備中，（C）是共享設(shè)備。A.打印機(jī)B.磁盤C.讀卡機(jī)D.掃描儀8、文件系統(tǒng)采用多級(jí)目錄結(jié)構(gòu)的目的,不包括是（B）A.縮短訪問文件的尋找時(shí)間B.節(jié)省存儲(chǔ)空間C.解決文件的命名沖突D.易于實(shí)現(xiàn)文件共享9、磁盤驅(qū)動(dòng)調(diào)度算法中（B）算法可能會(huì)隨時(shí)改變移動(dòng)臂的運(yùn)動(dòng)方向。A.電梯調(diào)度B.先來先服務(wù)C.掃描D.循環(huán)掃描10、正在運(yùn)行的進(jìn)程在信號(hào)量S上作P操作之后，當(dāng)S<0的時(shí)候，進(jìn)程進(jìn)入信號(hào)量的（A）。A.等待隊(duì)列B.提交隊(duì)列C.后備隊(duì)列D.就緒隊(duì)列二、填空題：（每空1分，共15分）1、不論是分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)還是批處理系統(tǒng)都具有四個(gè)基本特征并發(fā)、共享、虛擬、異步。2、特權(quán)指令只能在__系統(tǒng)_態(tài)下執(zhí)行，若在用戶態(tài)下執(zhí)行則被認(rèn)為是非法指令。3、__PCB______是進(jìn)程存在的唯一標(biāo)志。4、設(shè)基址寄存器內(nèi)容為1000，在采用動(dòng)態(tài)重定位的系統(tǒng)中，當(dāng)執(zhí)行指令“LOADA,2000”時(shí)，操作數(shù)的實(shí)際地址是__3000_________。5、按照調(diào)度的層次我們把調(diào)度分為高級(jí)、低級(jí)、中級(jí)。6、根據(jù)文件的邏輯結(jié)構(gòu)，文件可以分為有結(jié)構(gòu)文件和__無結(jié)構(gòu)文件_兩類。7、目前常用的外存分配方法有：連續(xù)分配、_鏈接______分配、索引分配。三、名詞解釋（每題3分，共12分）1、操作系統(tǒng)：操作系統(tǒng)是一組控制和管理計(jì)算機(jī)硬件和軟件資源（1分）、合理地對各類作業(yè)進(jìn)行調(diào)度（1分）、以及方便用戶的程序的集合（1分）。2、臨界區(qū)：每個(gè)進(jìn)程中訪問臨界資源的（2分）那段代碼（1分）稱為臨界區(qū)3、對換：所謂對換，是指把內(nèi)存中暫不能運(yùn)行的進(jìn)程，或暫不用的程序和數(shù)據(jù)（1分），換出到外存上，以騰出足夠的內(nèi)存空間（1分），把已具備運(yùn)行條件的進(jìn)程，或進(jìn)程所需的程序和數(shù)據(jù)，換入內(nèi)存（1分）4、設(shè)備獨(dú)立性：應(yīng)用程序獨(dú)立于具體的物理設(shè)備（3分）。四、簡單題（每題6分，共24分）1、比較程序、進(jìn)程的區(qū)別。進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的，程序是有序代碼的集合（1分）；進(jìn)程是程序的執(zhí)行（1分）；進(jìn)程是暫時(shí)的，程序的永久的，進(jìn)程是一個(gè)狀態(tài)變化的過程，程序可長久保存（1分）；進(jìn)程與程序的組成不同，進(jìn)程的組成包括程序、數(shù)據(jù)和進(jìn)程控制塊（即進(jìn)程狀態(tài)信息）（1分）；通過多次執(zhí)行，一個(gè)程序可對應(yīng)多個(gè)進(jìn)程（1分）；通過調(diào)用關(guān)系，一個(gè)進(jìn)程可包括多個(gè)程序（1分）。裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)所謂死瑣，是指多個(gè)進(jìn)程因競爭資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)（3分）。死鎖預(yù)防的措施有：（1）屏棄“請求和保持”條件，（2）屏棄“不剝奪”條件，（1分），（3）摒棄“環(huán)路等待”條件（1分）。3、簡述分頁與分段的主要區(qū)別（1）頁是信息的物理單位，已削減內(nèi)存零頭，提高內(nèi)存利用率為目的，而不是用戶的需求。（1分）段是信息的邏輯單位，具有相對完整的意義，是為了滿足用戶的需求。（1分）（2）頁的大小固定，由系統(tǒng)確定。（1分）段的大小不固定，決定于用戶編寫的程序。（1分）（3）分頁的作業(yè)地址是一維的。（1分）分段的作業(yè)地址是二維的。（1分）4、什么是局部性原理？什么是抖動(dòng)？你有什么辦法減少系統(tǒng)的抖動(dòng)現(xiàn)象？局部性原理是指在幾乎所有程序的執(zhí)行過程中，在一段時(shí)間內(nèi)，CPU總是集中地訪問程序中的某一個(gè)部分而不是對程序的所有部分具有平均的訪問概率。（2分）抖動(dòng)是指當(dāng)給進(jìn)程分配的內(nèi)存小于所要求的工作區(qū)時(shí)，由于內(nèi)存外存之間交換頻繁，訪問外存的時(shí)間和輸入輸出處理時(shí)間大大增加,反而造成CPU因等待數(shù)據(jù)而空轉(zhuǎn),使得整個(gè)系統(tǒng)性能大大下降。（2分）在物理系統(tǒng)中，為了防止抖動(dòng)的產(chǎn)生，在進(jìn)行淘汰或置換時(shí)，一般總是把缺頁進(jìn)程鎖住，不讓其換出，從而防止抖動(dòng)的產(chǎn)生。（1分）防止抖動(dòng)產(chǎn)生的另一個(gè)辦法是設(shè)置較大的內(nèi)存工作區(qū)。（1分）五、應(yīng)用與計(jì)算（共39分）1、現(xiàn)有一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，Produce進(jìn)程把它生產(chǎn)的消息放入一個(gè)緩沖區(qū)，Consumer進(jìn)程可從一個(gè)緩沖區(qū)中取得一個(gè)消息消費(fèi)。用信號(hào)量實(shí)現(xiàn)生產(chǎn)者和消費(fèi)者之間的同步與互斥。請將下面的生產(chǎn)者和消費(fèi)者算法補(bǔ)充完整。生產(chǎn)者和消費(fèi)者對緩沖池互斥訪問的信號(hào)量為SM，緩沖池的初值SB=n，緩沖池中消息個(gè)數(shù)初值為SP=0。（本題9分）初值設(shè)置SM=1；SB=n；sp=0P生產(chǎn)者：While(1){...ProduceranitemWait(SB)Wait(SM)緩沖操作Singal(SMSingal(SB)…}C消費(fèi)者：While(1){...Wait(SB)Wait(SM緩沖操作Singal(SMSingal(SB)Consumetheitem…}2、銀行家算法中，若出現(xiàn)下述的資源分配情況：ProcessAllocationNeedAvailableP00,1,07,4,33,3,2P12,0,01,2,4P23,0,26,5,0P32,1,10,1,1P40,0,24,3,1試問：（1）當(dāng)前系統(tǒng)狀態(tài)是否安全？如果安全寫出安全序列。（7分）（2）若進(jìn)程P1提出請求Request(1,0,2)后，系統(tǒng)能否將資源分配給它？（3分）（1）存在如下進(jìn)程序列，可使進(jìn)程順利執(zhí)行完畢：進(jìn)程可用資源數(shù)P3：執(zhí)行完5，4，3P4：執(zhí)行完5，4，5P1：執(zhí)行完7，4，5P0：執(zhí)行完7，5，5P2：執(zhí)行完10，5，7當(dāng)前系統(tǒng)是安全的，安全序列是：P3,P4,P1,P0,P2.（8分）(2)如果將資源分配給進(jìn)程P1,這時(shí)所有待執(zhí)行的進(jìn)程中就沒有滿足所需資源數(shù)<=系統(tǒng)可提供資源數(shù)條件的，所以系統(tǒng)不可以將資源分配P1（2分）3、假設(shè)一磁道有200個(gè)柱面，編號(hào)為0—199，在完成了磁道125處的請求后，當(dāng)前正在磁道143處為一請求服務(wù)，若請求隊(duì)列的先后順序?yàn)?6，147，91，177，94，150，102，175，130。試分別采用FCFS（先來先服務(wù)）、SSTF（最短尋道時(shí)間優(yōu)先）算法完成上述請求，寫出磁道移動(dòng)的順序，并計(jì)算磁頭移動(dòng)的總距離。裝訂線裝訂線內(nèi)不要答題裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)（1）采用FCFS算法調(diào)度，磁頭移動(dòng)順序?yàn)椋?43-86-147-91-177-94-150-102-175-130磁頭移動(dòng)總量為：565（柱面）。（4分）（2）采用SSTF算法調(diào)度，磁頭移動(dòng)順序?yàn)椋?43-147-150-130-102-94-91-86-175-177磁頭移動(dòng)總量為：162（柱面）。（4分）4、我們打開計(jì)算機(jī)中的某個(gè)word文檔，然后通過打印機(jī)打印文檔中的內(nèi)容，在這個(gè)過程中，操作系統(tǒng)為我們做了什么？試從操作系統(tǒng)功能的角度加以分析。（本題12分）進(jìn)程管理：執(zhí)行時(shí)完成調(diào)度（2分）存儲(chǔ)管理：為調(diào)度的進(jìn)程分配內(nèi)存，以及從硬盤中讀取文件。（2分）文件管理：所調(diào)度文件的查詢與讀?。?分）設(shè)備管理：打印機(jī)的驅(qū)動(dòng)，以及打印工作的執(zhí)行。（2分）用戶接口：執(zhí)行程序時(shí)的界面，以及程序進(jìn)程本身所含的系統(tǒng)調(diào)度。（2分）整個(gè)過程是五個(gè)功能合作完成。（2分）裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)東北大學(xué)秦皇島分校裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)課程名稱：計(jì)算機(jī)操作系統(tǒng)試卷：(A)考試形式：閉卷授課專業(yè)：計(jì)算機(jī)考試日期：年月日試卷：共3頁題號(hào)一二三四總分得分閱卷人單項(xiàng)選擇題：（每題2分，共30分）1、操作體統(tǒng)是對(C)進(jìn)行管理的軟件。A.軟件B.硬件C.計(jì)算機(jī)資源D.應(yīng)用程序2、操作系統(tǒng)的基本類型主要有(B)A.批處理系統(tǒng)、分時(shí)系統(tǒng)及多任務(wù)系統(tǒng)B.實(shí)時(shí)操作系統(tǒng)、分時(shí)操作系統(tǒng)及批處理操作系統(tǒng)C.單用戶系統(tǒng)、多用戶系統(tǒng)及批處理系統(tǒng)D.實(shí)時(shí)系統(tǒng)、分時(shí)系統(tǒng)和多用戶系統(tǒng)3、在進(jìn)程管理中，當(dāng)(C)時(shí)，進(jìn)程從阻塞狀態(tài)變?yōu)榫途w狀態(tài)。A.進(jìn)程被進(jìn)程調(diào)度程序選中B.等待某一事件C.等待的事件發(fā)生D.時(shí)間片用完4.若P、V操作的信號(hào)量S初值為2，當(dāng)前值為-1，則表示有(B)等待進(jìn)程。A.0個(gè)B.1個(gè)C.2個(gè)D.3個(gè)5、操作系統(tǒng)通過(B)對進(jìn)程進(jìn)行管理。A.JCBB.PCBC.DCTD.CHCT6、多道程序環(huán)境下，操作系統(tǒng)分配資源以(D)為基本單位。A.程序B.指令C.進(jìn)程D.作業(yè)7、發(fā)生死鎖的必要條件有四個(gè)，要防止死鎖的發(fā)生，可以破壞這四個(gè)必要條件，但破壞(A)條件是不太實(shí)際的。A.互斥B.不可剝奪C.部分分配D.環(huán)路等待8、在分時(shí)操作體統(tǒng)中，進(jìn)程調(diào)度經(jīng)常采用(C)算法。A.先來現(xiàn)服務(wù)B.最高優(yōu)先權(quán)C.事件片輪轉(zhuǎn)D.隨機(jī)9、系統(tǒng)“抖動(dòng)”現(xiàn)象的發(fā)生是由(A)引起的。A.置換算法選擇不當(dāng)B.交換的信息量過大C.內(nèi)存容量不足D.請求頁式管理方案10、首次適應(yīng)算法的空閑區(qū)是(A)A.按地址遞增順序連在一起B(yǎng).始端指針表指向最大空閑區(qū)C.按大小遞增順序連在一起D.尋找從最大空間區(qū)開始11、CPU輸出數(shù)據(jù)的速度遠(yuǎn)遠(yuǎn)高于打印機(jī)的打印速度，為了解決這一矛盾，可采用()A.并行技術(shù)B.通道技術(shù)C.緩沖技術(shù)D.虛擬技術(shù)12、從用戶的角度看，引入文件系統(tǒng)的主要目的是()A.實(shí)現(xiàn)虛擬存儲(chǔ)B.保存系統(tǒng)文件C.保存用戶和系統(tǒng)文檔D.實(shí)現(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.進(jìn)程B.系統(tǒng)調(diào)用C.庫函數(shù)D.系統(tǒng)調(diào)用和庫函數(shù)填空題：（每空1分，共15分）1、操作系統(tǒng)的基本功能包括處理機(jī)管理、存儲(chǔ)器管理、設(shè)備管理、文件管理。除此之外還為用戶使用操作系統(tǒng)提供了用戶接口。2、臨界資源的概念是，而臨界區(qū)是指。3、作業(yè)調(diào)度又被稱為，用于決定把外存上地哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建、分配必要的資源。4、在頁式存儲(chǔ)器管理中，邏輯地址由和兩部分組成。5、根據(jù)文件的邏輯結(jié)構(gòu)，文件可以分為_____________和____________兩類。6、目前常用的外存分配方法有：連續(xù)分配、_______分配、______分配。7、一個(gè)進(jìn)程只有在獲得通道、和所需設(shè)備三者之后，才具備進(jìn)行I/O操作的物質(zhì)條件。三、簡答題（每題5分，共20分）1、程序和進(jìn)程的主要區(qū)別是什么？裝訂線裝訂線內(nèi)不要答題裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)3、段式存儲(chǔ)器管理和頁式存儲(chǔ)器管理的區(qū)別是什么？4、二級(jí)目錄和多級(jí)目錄的好處是什么？四、應(yīng)用題（共35分）1、現(xiàn)有一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，Produce進(jìn)程把它生產(chǎn)的消息放入一個(gè)緩沖區(qū)，Consumer進(jìn)程可從一個(gè)緩沖區(qū)中取得一個(gè)消息消費(fèi)。用信號(hào)量實(shí)現(xiàn)生產(chǎn)者和消費(fèi)者之間的同步與互斥。請將下面的生產(chǎn)者和消費(fèi)者算法補(bǔ)充完整。生產(chǎn)者和消費(fèi)者對緩沖池互斥訪問的信號(hào)量為SM，緩沖池的初值SB=n，緩沖池中消息個(gè)數(shù)初值為SP=0。把下面的算法填寫完整。（本題8分）初值設(shè)置SM=；SB=n；sp=0P生產(chǎn)者：While(1){...ProduceranitemWait()緩沖操作Singal()…}C消費(fèi)者：While(1){...Wait()緩沖操作Singal()Consumetheitem…}2、銀行家算法中，若出現(xiàn)下述的資源分配情況：ProcessAllocationNeedAvailableP00,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試問：（1）當(dāng)前系統(tǒng)狀態(tài)是否安全？如果安全寫出安全序列。（5分）（2）若進(jìn)程P1提出請求Request(1,2,2,2)后，系統(tǒng)能否將資源分配給它？（2分）裝訂線裝訂線內(nèi)不要答題裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)4、假設(shè)一磁道有200個(gè)柱面，編號(hào)為0—199，在完成了磁道125處的請求后，當(dāng)前正在磁道143處為一請求服務(wù)，若請求隊(duì)列的先后順序?yàn)?6，147，91，177，94，150，102，175，130。若采用SSTF（最短尋道時(shí)間優(yōu)先）算法完成上述請求，寫出磁道移動(dòng)的順序，并計(jì)算磁頭移動(dòng)的總距離。（本題5分）5、我們打開計(jì)算機(jī)中的某個(gè)word文檔，然后通過打印機(jī)打印文檔中的內(nèi)容，在這個(gè)過程中，操作系統(tǒng)為我們做了什么？試從操作系統(tǒng)五大功能的角度加以分析。（本題10分）裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)東北大學(xué)秦皇島分校裝訂線裝訂線內(nèi)不要答題學(xué)號(hào)姓名班級(jí)課程名稱：編譯原理試卷：(B)答案考試形式：閉卷授課專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)考試日期：年月日試卷：共2頁題號(hào)一二三四總分得分閱卷人填空題（每空2分，共30分）1、編譯程序的整個(gè)過程可以從邏輯上劃分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等幾個(gè)階段，另外還有兩個(gè)重要的工作是表格管理和出錯(cuò)處理。2、規(guī)范規(guī)約中的可歸約串是句柄，算符優(yōu)先分析中的可歸約串是最左素短語。3、語法分析方法主要可分為自頂向下和自底向上兩大類。4、LR（0）文法的項(xiàng)目集中不會(huì)出現(xiàn)移進(jìn)-歸約沖突和歸約-歸約沖突。5、數(shù)據(jù)空間的動(dòng)態(tài)存儲(chǔ)分配方式可分為棧式和堆式兩種。6、編譯程序是指能將源語言程序翻譯成目標(biāo)語言程序的程序。7、確定有窮自動(dòng)機(jī)DFA是NFA的一個(gè)特例。8、表達(dá)式(a+b)*c的逆波蘭表示為ab+c*。選擇題（每題2分，共20分）1、LR語法分析棧中存放的狀態(tài)是識(shí)別B的DFA狀態(tài)。A、前綴B、可歸前綴C、項(xiàng)目D、句柄2、D不可能是目標(biāo)代碼。 A、匯編指令代碼B、可重定位指令代碼C、絕對機(jī)器指令代碼D、中間代碼3、一個(gè)控制流程圖就是具有C的有向圖A、唯一入口結(jié)點(diǎn)B、唯一出口結(jié)點(diǎn)C、唯一首結(jié)點(diǎn)D、唯一尾結(jié)點(diǎn)4、設(shè)有文法G[S]：S→b|bB B→bS ，則該文法所描述的語言是C。A、L（G）={bi|i≥0}B、L（G）=