編譯原理綜合練習

1、綜合練習 選擇題 問答題 綜合題選擇題 操作系統(tǒng)是一種（ ）。 A.應用軟件 B. 系統(tǒng)軟件 C.通用軟件 D. 工具軟件 操作系統(tǒng)是一組（ ）。A.文件管理程序 B.中斷處理程序C.資源管理程序 D.設(shè)備管理程序答案：1、B；2 、 C 操作系統(tǒng)是計算機系統(tǒng)的核心軟件。按功能特征的不同，可把操作系統(tǒng)分為1、2、3、個人機系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)等基本類型。其中1的主要目標是提高系統(tǒng)的吞吐率和效率，而2是一旦有處理請求和要求處理的數(shù)據(jù)時，CPU就應該立即處理該數(shù)據(jù)并將結(jié)果及時送回，例如4等。供選擇的答案：123A、 單用戶系統(tǒng) B、多道批處理系統(tǒng) C、分時系統(tǒng) D、微機操作系統(tǒng) E、

2、實時系統(tǒng)4A、計算機激光照排系統(tǒng) B、辦公自動化系統(tǒng)C、計算機輔助設(shè)計系統(tǒng) D、航空訂票系統(tǒng)答案：B E C D 引入多道程序的目的在于（ ）。A. 充分利用CPU，減少CPU等待時間B. 提高實時響應速度C. 有利于代碼共享，減少主、輔存信息交換量D. 充分利用存儲器 答案：A 在分時系統(tǒng)中，時間片一定，（ ），響應時間越長。A.內(nèi)存越多 B.用戶數(shù)越多C.后備隊列越短 D.用戶數(shù)越少 答案：B 以下（ ）項功能不是操作系統(tǒng)具備的主要功能。A內(nèi)存管理 B中斷處理 C文檔編輯 DCPU調(diào)度 答案：C 用戶要在程序一級獲得系統(tǒng)幫助，必須通過（ ）。A.進程調(diào)度 B.作業(yè)調(diào)度 C.鍵盤命令 D.系

3、統(tǒng)調(diào)用 答案：D 進程和程序的本質(zhì)區(qū)別是（ ）。A.存儲在內(nèi)存和外存 B.順序和非順序執(zhí)行機器指令C.分時使用和獨占使用計算機資源 D.動態(tài)和靜態(tài)特征 答案：D 進程就是程序在并發(fā)環(huán)境中的執(zhí)行過程，它是系統(tǒng)進行資源分配和調(diào)度的一個基本單位。進程具有1、2、調(diào)度性、異步性和結(jié)構(gòu)性等基本特征。進程是一次執(zhí)行過程，具有生命期體現(xiàn)了進程的1特征。進程由程序段、3、4組成，其中4是進程在系統(tǒng)中存在的唯一標識。供選擇的答案：12 A、動態(tài)性 B、靜態(tài)性 C、共行性 D、并發(fā)性 E、可執(zhí)行性 F、易用性3 A、過程 B、數(shù)據(jù) C、進程標識符 D、函數(shù)4 A、FCB B、FIFO C、PCB D、JCB 答案

4、：A、D、B、C 進程執(zhí)行時的間斷性，決定了進程可能具有多種狀態(tài)。進程的基本狀態(tài)有三種，在分時系統(tǒng)中，當一個進程擁有的時間片到時，則該進程即由1進入2。如果出現(xiàn)因某種原因使得處理機空閑時，則需要從就緒隊列中選擇一進程，并將處理機分配給它，此時該進程進入3，這個過程是由4來完成。供選擇的答案：123 A、就緒狀態(tài) B、靜止狀態(tài)C、阻塞狀態(tài) D、運行狀態(tài)4 A、進程控制程序 B、資源分配程序C、進程調(diào)度程序 D、處理機分配程序 答案：D、A、D、C 為了描述進程的動態(tài)變化過程，采用了一個與進程相聯(lián)系的（ ），根據(jù)它而感知進程的存在。A.進程狀態(tài)字 B. 進程優(yōu)先數(shù)C.進程控制塊 D. 進程起始地址

5、 答案：C 下列進程狀態(tài)的轉(zhuǎn)換中，哪一個是不正確的（ ）。A. 就緒-運行 B. 運行-就緒C. 就緒-阻塞 D. 阻塞-就緒 答案：C 下列各項步驟中，哪一個不是創(chuàng)建進程所必須的步驟（ ）。A. 建立一個進程控制塊PCBB. 由CPU調(diào)度程序為進程調(diào)度CPUC. 為進程分配內(nèi)存等必要的資源D. 將PCB鏈入進程就緒隊列 答案：B 在單處理機系統(tǒng)中，處于運行狀態(tài)的進程（ ）。A.只有一個 B. 可以有多個C.不能被掛起 D. 必須在執(zhí)行完后才能被撤下 答案：A 進程和程序的區(qū)別是（） a.程序有狀態(tài)，而它沒有 b. 它有狀態(tài)，而程序沒有 c.程序可占用資源，而它不可 d.它可占用資源，而程序不

6、可 答案：B 操作系統(tǒng)中有一組常稱為特殊系統(tǒng)調(diào)用的程序，它不能被系統(tǒng)中斷，在操作系統(tǒng)中稱為（ ）。A.初始化程序 B. 原語 C.子程序 D. 控制模塊 B 兩個進程合作完成一個任務，在并發(fā)執(zhí)行中，一個進程要等待其合作伙伴發(fā)來信息，或者建立某個條件后再向前執(zhí)行，這種關(guān)系是進程間的（ ）關(guān)系。A.同步 B. 互斥 C.競爭 A 在一段時間內(nèi)，只允許一個進程訪問的資源稱為（ ）。A. 共享資源 B. 臨界區(qū) C. 臨界資源 D. 共享區(qū) C 在操作系統(tǒng)中，對信號量S的P原語操作定義中，使進程進入相應阻塞隊列等待的條件是（ ）。A. S0 B. S=0 C. S= 1 N = 5綜合題 設(shè)某系統(tǒng)有輸

7、入進程和輸出進程共用一個單緩沖T（該緩沖區(qū)的大小為每次只能存放一個數(shù)據(jù)），輸入進程負責不斷地計算數(shù)據(jù)并送入單緩沖T；輸出進程負責從單緩沖T中取出數(shù)據(jù)去打印。試用信號等的P、V操作實現(xiàn)輸入進程和輸出進程的同步，要求寫出程序描述。 P:While(true) 計算出一個數(shù)據(jù)；計算出一個數(shù)據(jù)； P(S1); 把數(shù)據(jù)放入緩沖；把數(shù)據(jù)放入緩沖； V(S2);Q:While(true) P(S2); 從緩沖里取數(shù)據(jù)；從緩沖里取數(shù)據(jù)； V(S1); 打印數(shù)據(jù)；打印數(shù)據(jù)；;設(shè)置兩個信號量，設(shè)置兩個信號量，S1初值為初值為1，S2初值為初值為0 設(shè)系統(tǒng)中只有一臺打印機，有三個用戶的程序在執(zhí)行過程中都要使用打印機

8、輸出計算結(jié)果。設(shè)每個用戶程序?qū)粋€進程。問：這三個進程間有什么樣的制約關(guān)系？試用P、V操作寫出這些進程使用打印機的算法。 設(shè)一臺計算機，有兩條I/O通道，分別接一臺卡片輸入機和一臺打印機?？ㄆ瑱C把一疊卡片逐一輸入到緩沖區(qū)B1中，加工處理后再搬到緩沖區(qū)B2中，并在打印機上印出，問：1）系統(tǒng)要設(shè)幾個進程來完成這個任務？各自的工作是什么？2）這些進程間有什么樣的相互制約關(guān)系3）用P,V操作寫出這些進程的同步算法這是一個典型的生產(chǎn)者，消費者問題1）系統(tǒng)要設(shè)三個進程完成任務，第一個進程P1,從卡片輸入機中讀入數(shù)據(jù)，并且把數(shù)據(jù)放入緩沖區(qū)B1中。第二個進程從B1緩沖區(qū)中取數(shù)據(jù)，加工處理后放入緩沖區(qū)B2中。

9、第三個進程將緩沖區(qū)的內(nèi)容輸入到打印機中打印出來2）這三個進程之間是同步和互斥的關(guān)系 3）三個進程之間必須協(xié)調(diào)工作，需設(shè)置四個信號量，S1,S2,S3,S4并令S1的初值為1,S2、S3的初值為0，S4的初值為1,則程序為：進程 p1 進程p2 進程p3While(1) While(1) while(1)P(S1) P(S2) P(S3)從卡片機中讀入數(shù)據(jù) 將緩沖區(qū)B1內(nèi)容取出 V(S1) 加工數(shù)據(jù) P(S4) V(S2) 在打印機中輸出 拷貝道Buffer B2中 V(S4) V(S3) 假定系統(tǒng)有三個并發(fā)進程read， move和print共享緩沖器B1和B2.進程read負責從輸入設(shè)備上讀

10、信息，每讀出一個記錄后把它存放到緩沖器B1中。進程move從緩沖器B1中取出一記錄，加工后存入緩沖器B2.進程print將B2中的記錄取出打印輸出。緩沖器B1和B2每次只能存放一個記錄。要求三個進程協(xié)調(diào)完成任務，使打印出來的與讀入的記錄的個數(shù)，次序完全一樣。 設(shè)有一個可以裝A、B兩種物品的倉庫，其容量無限大，但要求倉庫中A、B兩種物品的數(shù)量滿足下述不等式: -MA物品數(shù)量B物品數(shù)量N 其中M和N為正整數(shù)。 試用信號量和PV操作描述A、B兩種物品的入庫過程。 semaphore a=n;semaphore b=m; A物品入庫：process A()while(1) P(a); A物品入庫; V

11、(b); B物品入庫：process B() while(1) P(b); B物品入庫; V(a); 理發(fā)師問題 理發(fā)店中有k張理發(fā)椅和n張等待理發(fā)的顧客坐的座椅，如圖所示。若沒有顧客，理發(fā)師就坐在理發(fā)椅上打盹；當顧客來時，就喚醒打盹的理發(fā)師進行理發(fā)；若理發(fā)師全在工作，又來新顧客，則就坐在空座椅上等待理發(fā)，沒有空座椅就離去。座椅座椅座椅座椅座椅理發(fā)椅n張入口理發(fā)椅理發(fā)椅k張出口 設(shè)立三個信號量 custs：記錄等待理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)，初值為0； barbs：正在等待為顧客理發(fā)的理發(fā)師數(shù)，初值為k； mutex：保證互斥使用變量waiting的互斥信號量，初值為1。 設(shè)置變量：

12、 為隨時記錄等待理發(fā)的顧客數(shù)，設(shè)置變量waiting，它的初值為0。注意，它是一個變量，不是信號量，不過它的值總是和信號量customers相同。 n ：來到理發(fā)店等待理發(fā)的顧客數(shù)的上限值。barber() while(TRUE) *P(custs); P(mutex); waiting=waiting-1; V(mutex); cut_hair(); *V(barbs); customer() P(mutex); if(waiting 當前狀態(tài)安全當前狀態(tài)安全 設(shè)有三個批作業(yè)JOB1、JOB2、JOB3，其到達時間、處理時間及完成時間如下：作業(yè) 作業(yè)到達時間（時） 開始處理時間（時） 處理完

13、成時間（時）JOB1 15 18 22JOB2 18 21 23 JOB3 17 19 21試計算：（1）各個作業(yè)的周轉(zhuǎn)時間；（2）所有作業(yè)的平均周轉(zhuǎn)時間； 1. (1) 754 (2) 5.33假定在單CPU條件下有下列要執(zhí)行的作業(yè)： 作業(yè)到來的時間是按作業(yè)編號順序進行的（即后面作業(yè)依次比前一個作業(yè)遲到一個時間單位）。（1）用一個執(zhí)行時間圖描述在采用非搶占式優(yōu)先級算法時執(zhí)行這些作業(yè)的情況。（2）對于上述算法，各個作業(yè)的周轉(zhuǎn)時間是多少？平均周轉(zhuǎn)時間是多少？（3）對于上述算法，各個作業(yè)的帶權(quán)周轉(zhuǎn)時間是多少？平均帶權(quán)周轉(zhuǎn)時間是多少？ 非優(yōu)先級搶占 平均周轉(zhuǎn)時間=12.33 平均帶權(quán)周轉(zhuǎn)時間=2.8

14、9假定要在一臺處理機上執(zhí)行下列作業(yè)，如表：作業(yè)進入時刻運行時間開始時刻完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18.001.5028.500.5039.000.1049.200.20平均周轉(zhuǎn)時間T=平均帶權(quán)周轉(zhuǎn)時間W= 給出使用FCFS、RR（時間片為1）、SJF、最高響應比優(yōu)先及非搶占式優(yōu)先調(diào)度算法（優(yōu)先級數(shù)字越小，優(yōu)先級越高）時的作業(yè)執(zhí)行順序以及使用每種方法的平均周轉(zhuǎn)時間與平均帶權(quán)周轉(zhuǎn)時間。Round Robin 設(shè)系統(tǒng)中先后有5個進程P1，P2，P3，P4和P5到達就緒狀態(tài)。它們的到達時刻和執(zhí)行時間如下圖所示。 請給出輪轉(zhuǎn)調(diào)度算法下時間片q值分別為2、4、6時的調(diào)度順序圖。 解： (1) 時間片=2

15、 在時刻0，調(diào)度算法選擇P1 P1執(zhí)行完一個時間片，到了時刻2，此時 就緒隊列ready_queue=P2(3) , 其中的P2(3)表示P2還需要3個時間單位才能執(zhí)行完P(guān)102 解： (1) 時間片=2 在時刻2，P1的時間片執(zhí)行完畢，被加入就緒隊列 進程P2被調(diào)度算法選中執(zhí)行 此時 ready_queue=P1(3)P102P2從時刻P2開始執(zhí)行 解： (1) 時間片=2 到時刻3，進程P3到達，但是此時P2的時間片還沒有用完，所以P3被加入就緒隊列 此時 ready_queue=P1(3)，P3(2)P102 解： (1) 時間片=2 到時刻4，進程P2的時間片用完，剩余時間t2=3-2

16、=1，因此P2要被加到就緒隊列等待下次執(zhí)行 進程P1被調(diào)度算法選中 此時 ready_queue=P3(2)，P2(1)P102P24 以后的各個時間點類推可得 最終，時間片q=2時的調(diào)度情況如下圖P102P24P16P38P29P411P112P514P416P517P1的周轉(zhuǎn)時間=12， 等待時間=7 時間片為4時的調(diào)度順序圖P104P27P39P110P414P517 時間片為6時的調(diào)度順序圖P105P28P310P414P517時間片越大，越接近于FCFS調(diào)度算法 對于如下的頁面訪問序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5當內(nèi)存塊數(shù)量分別為3和4時，試問：使用FIFO、LRU、OPT置換算法產(chǎn)生的缺頁中斷是多少？（所有內(nèi)存開始時都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷） 123412512345 設(shè)正在處理器上執(zhí)行的一個進程的頁表見表所示，表中的虛頁號和物理塊號是十進制數(shù)，起始頁號（塊號）均為0，所有的地址均是存儲器字節(jié)地址，頁的大小為2048B。 （1）詳述在設(shè)有快表的分頁存儲管理系統(tǒng)中，一個虛地址轉(zhuǎn)換成物理內(nèi)存地址的過程。 （2）下列虛地址對應于什么物理地址：6598B 某虛擬存儲器的用戶編程空間共32個頁