編譯原理綜合練習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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