復(fù)習(xí)題_問答題部分New(2).

1、第二早1已知一個(gè)求值公式（3A+2B）/（A+5B2+C），若A、B、C已賦值，試畫出該公式 求值過程的前趨圖。解：令 S1： X1 = 3A;S2: X2 = 2B;S3: X3 = X1+X2;S4： X4 = 5B2;S5: X5 = A+X4+C;S6: X6 = X3/X5則求值過程的前趨圖為：SIS2 IS42、已知一個(gè)求值公式（B2+AB）/（5B+A），若A、B已賦值，試畫出該公式求值過 程的前趨圖。解：令 S1： X1 = B2 ；S2： X2 = AB ；S3: X3 = X1 + X2 ；S4： X4 = 5B ；S5: X5 = X4 + A ；S6: X6 = X3

2、/ X5。則求值過程的前趨圖為：（自己畫出）3、寫出實(shí)現(xiàn)兩個(gè)進(jìn)程單向同步問題的偽碼。（參考講義）3、寫出通過信號(hào)量實(shí)現(xiàn)生產(chǎn)進(jìn)程和消費(fèi)進(jìn)程（單緩沖區(qū)）雙向同步的偽碼。 （參考講義）解：定義信號(hào)量：var生產(chǎn)進(jìn)程偽碼：Process P:beg inwhile(true) dobeg in生產(chǎn)一個(gè)產(chǎn)品；P操作，等待可以生產(chǎn)的信號(hào)量 將產(chǎn)品放入緩沖區(qū)。其他操作sin gal(s2); /V操作，發(fā)送可以消費(fèi)的信號(hào)量 endend消費(fèi)進(jìn)程偽碼：Process C:beg inwhile(true) dobeg in/P操作，等待可以消費(fèi)的信號(hào)量 從緩沖區(qū)中取出產(chǎn)品進(jìn)行消費(fèi)。/其他操作sin gal(s

3、1); /V操作，發(fā)送可以生產(chǎn)的信號(hào)量endend4、寫出通過信號(hào)量實(shí)現(xiàn)進(jìn)程1和進(jìn)程2互斥訪問共享資源(臨界資源)的偽 碼。(參考講義)解：定義信號(hào)量：訪問資源進(jìn)程1偽碼：Process P1:beg in while(true) dobeg in/P操作，申請(qǐng)?jiān)L問資源權(quán)限的的信號(hào)量臨界區(qū)代碼；其他訪問資源操作/V操作，釋放訪問資源權(quán)限的信號(hào)量endend訪問資源進(jìn)程2偽碼：(同P1類似)Process P2:beg inwhile(true) dobeg inwait(s); /P操作，申請(qǐng)?jiān)L問資源權(quán)限的的信號(hào)量臨界區(qū)代碼；其他訪問資源操作sin gal(s); /V操作，釋放訪問資源權(quán)限的

4、信號(hào)量endend5、寫出具有緩沖池（n個(gè)緩沖區(qū)）的生產(chǎn)者-消費(fèi)者問題的偽碼。（參考講義、 教材）6、 寫出公共汽車司機(jī)和售票員同步問題的偽碼。（參考講義）解：信號(hào)量定義var s1,s2:semaphore:=0,0;s1為控制能否行車的信號(hào)量s2為控制能否開門的信號(hào)量司機(jī)進(jìn)程：Process Driver:beg inwhile（true） dobeg inwait（s1）;加油行車；到站停車；sin gal（s2）;endend售票員進(jìn)程：Process Con ductor:beg inwhile（true） do beg in關(guān)車門；singal（s1）;售票；wait（s2）;開車

5、門；end end7、讀者-寫者同步問題（參考講義和教材）第三章1、系統(tǒng)有5個(gè)進(jìn)程，其就緒時(shí)刻（指在該時(shí)刻已經(jīng)在就緒隊(duì)列中就緒）、服務(wù)時(shí)間 如下表所示。當(dāng)分別采用先來先服務(wù)（FCFS）和短進(jìn)程優(yōu)先（SPF）算法時(shí)，畫出調(diào)度 過程，并計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 （進(jìn)程就緒時(shí)刻服務(wù)時(shí)間P】02P225P343P466P581iMHUIH始拉汁時(shí)閘周料時(shí)同幫寂周轉(zhuǎn)時(shí)闔pi0*02j1P2rVp35iPS471062P46b10lbw50PSi16IT*期平均周轉(zhuǎn)時(shí)間=平均帶權(quán)周轉(zhuǎn)時(shí)間=就緒時(shí)劇瞰務(wù)時(shí)阿HR龍成時(shí)閘周轉(zhuǎn)時(shí)屈時(shí)何PI020221P225751Pi47106EM66HH11/6亦

6、&jH)113進(jìn)程列達(dá)時(shí)刻運(yùn)行時(shí)間Pl05p:11Pj22P431巴43平均周轉(zhuǎn)時(shí)間=平均帶權(quán)周轉(zhuǎn)時(shí)間=解：進(jìn)程執(zhí)行過程如下：P1P2P3P4P5時(shí)間：平均周轉(zhuǎn)時(shí)間：(11+1+6+2+8)/5 = 5.6平均帶權(quán)周轉(zhuǎn)時(shí)間：(11/5+1/1+6/2+2/1+8 /52.173、系統(tǒng)中有5個(gè)進(jìn)程，每個(gè)進(jìn)程的運(yùn)行時(shí)間、優(yōu)先級(jí)和到達(dá)時(shí)刻如下表所示。若米用搶占式優(yōu)先級(jí)調(diào)度算法(優(yōu)先級(jí)越大越優(yōu)先執(zhí)行)進(jìn)程到達(dá)時(shí)刻運(yùn)行時(shí)間優(yōu)先級(jí)Pl154p2116222P433斗35進(jìn)程量大需求已分配P1105P242P3924、假定系統(tǒng)中有三個(gè)進(jìn)程 P1、P2和P3,共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求 10臺(tái)磁帶機(jī)，

7、P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在TO時(shí)刻，進(jìn)程P1、P2和P3 已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，如下表所示：(1) 該狀態(tài)是否是安全狀態(tài)？請(qǐng)說明理由。解：TO時(shí)刻，系統(tǒng)是處于安全狀態(tài)，因?yàn)榇藭r(shí)的空閑磁帶機(jī)資源為3,存在一個(gè)安全序列P2、P1、P3,即只要系統(tǒng)按此進(jìn)程序列分配磁帶機(jī)資源，就能夠使三 個(gè)進(jìn)程都順利完成。（為什么？）（2）若到達(dá)一新進(jìn)程P4，請(qǐng)求1臺(tái)磁帶機(jī)，其最大需求為4臺(tái)，是否可以分配？ 請(qǐng)說明理由。（參考P108）解：可以進(jìn)行資源分配。因?yàn)閷?臺(tái)磁帶機(jī)分配給P4后，尚有2臺(tái)空閑磁帶 機(jī)，存在一個(gè)安全序列P2、P4、P1、P3，即只有系統(tǒng)按此進(jìn)程序列分配磁帶機(jī) 資源，就能夠使

8、四個(gè)進(jìn)程都順利完成。（為什么？）5、設(shè)系統(tǒng)中有人資淞謚求址已汕配幻源敗董冉CAc卩592i23種類型的資源（A，B，C）和5個(gè)進(jìn)程P1、P2、P3、P4、P5, A資源的數(shù)量為17, B資源的數(shù)量為5, C資源的數(shù)量為20,在T0時(shí)刻系統(tǒng)狀態(tài)如下表所示。系 統(tǒng)米用銀行家算法實(shí)施死鎖避免策略。（參考P110）53b40Ti4UIII4U5Pl4A54Pi4I3114罰余番踴AHCj313（1）T0時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列;最大資源需求量己分配瓷源數(shù)量、哉M資源需求量A；cABCABcPl559hi1234sPj5364UJ 134 |4V114U500 6p442520422ri

9、tei424314Io |剰余瓷Alic源數(shù)233T0時(shí)刻是安全狀態(tài)。存在安全序列P4、P2、P3、P5、P1（為什么？能否找出其他安全序列？）若在T0時(shí)刻進(jìn)程P2請(qǐng)求資源（0, 3, 4）,是否能實(shí)施資源分配？為什么？解：若在TO時(shí)刻進(jìn)程P2請(qǐng)求資源(0, 3, 4),不能實(shí)施資源分配。因?yàn)檎?qǐng)求資源數(shù)(0, 3, 4)可用資源數(shù)(2, 3, 3)不成立，沒有足夠資源。在(1)的基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源(2, 0, 1)，Meed IS薄需求雖ABcABcBchS59器1工p.536402p*40114050典4254H5O14A1141QA0y7是否能實(shí)施資源解：可以實(shí)施分配，因?yàn)榉峙浜笥?/p>

10、安全序列：(為什么？能否找出其他安全序列？),即分配后的狀態(tài)是安全的。6、假定系統(tǒng)中有三個(gè)進(jìn)程 P1、P2和P3,共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求 10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3 已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示：(參考 教材P108)進(jìn)程最大需求已分配可用r pi 11()53P24P391(1) T0時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列；在T0時(shí)刻P3申請(qǐng)一臺(tái)磁帶機(jī)，請(qǐng)問能否實(shí)施資源分配，為什么? 解：參考教材7、理解FCFS和SJF作業(yè)調(diào)度算法思想。業(yè)闊艮、進(jìn)IV耕ACE均列達(dá)時(shí)阿0134435迄4F

11、CFS(a)41214IN隔轉(zhuǎn)時(shí)河46In11E419帯權(quán)網(wǎng)轉(zhuǎn)時(shí)Ml125,53.52.8SJF尢誡時(shí)問49洛6134H163V;ET均01234時(shí)M /廣、IM符時(shí)側(cè)43s24U n1210iII174jr= |112y8IJ11.633? 24125UlKR id - JL知k柏;帀i i17i61&10139.1S3-152M9、通過上課所講示例理解 EDF （最早截止時(shí)間優(yōu)先）算法和 LLF（最低松弛度優(yōu) 先）算法思想。第四章1某系統(tǒng)采用動(dòng)態(tài)分區(qū)分配方式管理內(nèi)存，內(nèi)存空間為640KB，高端40KB用來存放操作系統(tǒng)。在內(nèi)存分配時(shí)，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。對(duì)下列的請(qǐng) 求序列：作業(yè)1申

12、請(qǐng)130KB，作業(yè)2申請(qǐng)60KB，作業(yè)3申請(qǐng)100KB，作業(yè)2釋 放60KB，作業(yè)4申請(qǐng)200KB，作業(yè)3釋放100KB，作業(yè)1釋放130KB，作業(yè)5 申請(qǐng)140KB，作業(yè)6申請(qǐng)60KB，作業(yè)7申請(qǐng)50KB，作業(yè)6釋放60KB，請(qǐng)分別 畫圖表示出使用首次適應(yīng)算法和最佳適應(yīng)算法進(jìn)行內(nèi)存分配和回收后，內(nèi)存的實(shí) 際使用情況。（參考教材和講義）解：參考教材、講義和下題方法2.某操作系統(tǒng)采用分區(qū)存儲(chǔ)管理技術(shù)。操作系統(tǒng)在低地址占用了100KB的空間,用戶區(qū)主存從100KB處開始占用512KB。初始時(shí)，用戶區(qū)全部為空閑，分配時(shí) 截取空閑分區(qū)的低地址部分作為已分配區(qū)。在執(zhí)行以下申請(qǐng)、釋放操作序列后：請(qǐng)求300

13、KB;請(qǐng)求100KB;釋放300KB;請(qǐng)求150KB;請(qǐng)求50KB;請(qǐng)求 90KB，進(jìn)行以下回答：（1）分別采用首次適應(yīng)算法和最佳適應(yīng)算法時(shí)，主存的實(shí)際使用情況如何？分別 畫出主存分布圖，并指出空閑分區(qū)的首地址和大??；（2）若隨后又要請(qǐng)求80KB，針對(duì)上述兩種情況產(chǎn)生什么后果？說明了什么問題？ （參考教材和講義）（1）采用首次適應(yīng)算法時(shí)，主存分布圖如下圖ISCIKB(已井 HO90KB(已分配EKB；詢|KJGKBre 分的lUKBf空閑)空閑區(qū)1:首地址390KB，大小10KB ;空閑區(qū)2:首地址500KB，大小112KB;(2) 采用最佳適應(yīng)算法時(shí)，主存分布圖如下圖空閑區(qū)1:首地址340K

14、B，大小60KB ；空閑區(qū)2:首地址550KB，大小62KB ；(3) 若隨后又要請(qǐng)求分配80KB，首次適應(yīng)算法可順利分配，而最佳適應(yīng)算法不 能。說明首次適應(yīng)算法可在高址端保留大分區(qū)。3、某分頁系統(tǒng)的邏輯地址為16位，其中高6位為頁號(hào)，低10位為頁內(nèi)偏移量，則在這樣的地址結(jié)構(gòu)中：(1) 一頁有多少個(gè)字節(jié)？(2) 邏輯地址可有多少頁？(3) 一個(gè)進(jìn)程最大的邏輯地址空間是多少 KB ?(參考P130)解：210 = 1024因此一頁有1024字節(jié)26 = 64因此邏輯地址可有64頁216 = 64KB因此一個(gè)進(jìn)程最大的邏輯地址空間是64KB4、 某系統(tǒng)采用頁式存儲(chǔ)管理策略，擁有邏輯空間32頁，每頁

15、為2KB，擁有物理 空間1MB。(1) 寫出邏輯地址的格式。解：11位頁內(nèi)地址，5位頁號(hào)(2) 若不考慮訪冋權(quán)限等，進(jìn)程的頁表最多有多少項(xiàng)？每項(xiàng)至少有多少位？解：因?yàn)橛?2個(gè)邏輯頁面，所以頁表有32項(xiàng)。因?yàn)橛?M/2K= 2的9次方物理 塊，所以每個(gè)頁表項(xiàng)至少有 9位(3) 如果物理空間減少一半，頁表結(jié)構(gòu)應(yīng)相應(yīng)作怎樣的改變？解：32項(xiàng)，每項(xiàng)至少需要8位5、 對(duì)于如下表所示的段表，請(qǐng)將邏輯地址(0,137), (1,4000), (2,3600),段號(hào)內(nèi)存始址段艮050K10KB160K3KB270K5KB3120K8KB4150K4KB解：(0,137)對(duì)應(yīng)的物理地址為：50K+137 = 5

16、0*1024+137 = 51337;(1,4000)的段內(nèi)偏移地址越界，是一個(gè)不合法邏輯地址；(2,3600)對(duì)應(yīng)的物理地址為：70K+3600 = 75280(5,230)的段號(hào)越界，是一個(gè)不合法邏輯地址。6、在一個(gè)請(qǐng)求分頁系統(tǒng)中，假如一個(gè)作業(yè)的頁面走向?yàn)?, 3, 2，1, 4, 3, 5,4，3, 2, l, 5, 目前它還沒有任何頁裝入內(nèi)存，當(dāng)分配給該作業(yè)的物理塊數(shù)目M分別為3和4時(shí)，請(qǐng)分別計(jì)算采用OPT、LRU和FIFO頁面淘汰算法時(shí)訪問過 程中所發(fā)生的缺頁次數(shù)和缺頁率，并比較所得的結(jié)果。解：請(qǐng)參照講義畫出調(diào)頁過程，7、系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，頁面訪問順序?yàn)椋?, 0, 1,

17、 2, 0, 3, 0,4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1,試問采用 OPT、FIFO、LRU 置換算 法時(shí)會(huì)產(chǎn)生多少次缺頁中斷？（假定初始時(shí)所有頁面均未裝入內(nèi)存；請(qǐng)畫出置換過 程）解：參照講義8在某個(gè)分頁管理系統(tǒng)中，某一個(gè)進(jìn)程有 4個(gè)頁面，被分別裝入到主存的第 3、 4、6、8塊中，假定頁面和塊大小均為1024字節(jié)，當(dāng)進(jìn)程在CPU上運(yùn)行時(shí)，執(zhí) 行到一條傳送指令：MOV 2100, 3100請(qǐng)計(jì)算出MOV指令中兩個(gè)操作數(shù)（邏輯地址）的物理地址。解：2100 / 1024 = 2第 2頁放在第6塊中2100 % 1024 = 526X1024 + 52 =

18、 6196因此第一個(gè)操作數(shù)的物理地址為 6196。3100 / 1024 = 3第3頁放在第8塊中3100 % 1024 =288X1024 + 28 = 8220因此第二個(gè)操作數(shù)的物理地址為 8220。9、已知某分頁系統(tǒng)，主存容量為 64KB，頁面大小為1KB。對(duì)于一個(gè)4頁大的作 業(yè)，其0、1、2、3頁分別被分配到主存的2、4、6、7塊中。將十進(jìn)制的邏輯地 址1023、2500、3500、4500轉(zhuǎn)換成物理地址。（參考講義）解：邏輯地址1023的頁號(hào)和頁內(nèi)偏移地址分別為：1023/1024 = 0, 1023%1024 = 1023所以其的物理地址為：2*1024+1023 = 3041邏輯

19、地址2500的頁號(hào)和頁內(nèi)偏移地址分別為：2500/1024 = 2, 2500%1024 = 452所以其的物理地址為：6*1024+452 = 6596邏輯地址45004*1024-1,所以不是一個(gè)合法地址。第五章1、試說明spooling系統(tǒng)的組成和工作原理。（參考講義和教材）2、磁盤請(qǐng)求以15、32、25、5、60、10、48磁道的序列到達(dá)磁盤驅(qū)動(dòng)器。尋道 時(shí)移動(dòng)一個(gè)磁道需要8ms,當(dāng)分別采用FCFS算法、最短尋道時(shí)間優(yōu)先算法、SCAN算法、CSCAN算法時(shí)，磁道的訪問順序是怎樣的？平均尋道時(shí)間是多 少？假設(shè)磁頭的起始位置位于磁道 18,朝大磁道號(hào)方向移動(dòng)。（參考講義）從18號(hào)磁道開始磁

20、道訪問順序移動(dòng)距離(磁道數(shù))1533217257520605510504838平均尋道時(shí)間為：(3+17+7+20+55+50+38)/7*8二?從18號(hào)磁逍開始磁道訪問順序移動(dòng)距離(磁道數(shù))15310555251032748126012平均尋道時(shí)間為：(3+5+5+10+7+12+12)/7*8二?:從18號(hào)磁道開始磁道訪問順序移動(dòng)距離（磁道數(shù)）25732748126012154510555從18號(hào)磁道開始施道訪問順序移動(dòng)距離（磁道數(shù)）257327平均尋道時(shí)間為：（7+7+12+12+45+5+）/7*8= ?48126012555105155平均尋道時(shí)間為：（7+7+12+12+55+5+

21、）/7*8= ?3、磁盤請(qǐng)求以20、44、40、4、80、12、76磁道的序列到達(dá)磁盤驅(qū)動(dòng)器。尋道 時(shí)移動(dòng)一個(gè)磁道需要3ms,當(dāng)采用SCAN算法時(shí)，磁道的訪問順序是怎樣的？平 均尋道時(shí)間是多少？假設(shè)磁頭的起始位置位于磁道 40,磁頭向小磁道方向移動(dòng)。（參考講義）4、磁盤請(qǐng)求以20、44、40、4、80、12、76磁道的序列到達(dá)磁盤驅(qū)動(dòng)器。尋道 時(shí)移動(dòng)一個(gè)磁道需要3ms，當(dāng)采用CSCAN算法時(shí)，磁道的訪問順序是怎樣的？ 平均尋道時(shí)間是多少？假設(shè)磁臂的起始位置位于磁道 40,磁頭向大磁道方向移 動(dòng)。（參考講義）5、假設(shè)磁盤訪問序列:98, 183, 37, 122, 14, 124, 65, 67讀寫頭起始位置：53（1）安排磁頭服務(wù)序列（2）計(jì)算磁頭移動(dòng)總距離（道數(shù)）（參考講義） 第六章1、 存放在某個(gè)磁盤上的文件系統(tǒng)采用混合索引分配方式，其FCB中共有13個(gè)地址項(xiàng)，第09個(gè)地址項(xiàng)為直接地址，第10個(gè)地址項(xiàng)為一次間接地址，第11個(gè)地 址項(xiàng)為二次間接地址，第12個(gè)地址項(xiàng)為三次間接地址。如果每個(gè)盤塊的大小為 512字節(jié)，若盤塊號(hào)需要用3個(gè)字節(jié)來描述，而每個(gè)盤塊最多存放170個(gè)盤塊地址，則該文件系統(tǒng)允許文件的最大長度是多少？（參考教材和下題）2、有某操作系統(tǒng)對(duì)外存分配采用混合索引分配方式，在索引節(jié)點(diǎn)中包含文件的 物理結(jié)構(gòu)數(shù)組iaddr13，其中前10項(xiàng)