復習題_問答題部分New(2).

1、第二早1已知一個求值公式（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、已知一個求值公式（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、寫出實現(xiàn)兩個進程單向同步問題的偽碼。（參考講義）3、寫出通過信號量實現(xiàn)生產(chǎn)進程和消費進程（單緩沖區(qū)）雙向同步的偽碼。 （參考講義）解：定義信號量：var生產(chǎn)進程偽碼：Process P:beg inwhile(true) dobeg in生產(chǎn)一個產(chǎn)品；P操作，等待可以生產(chǎn)的信號量 將產(chǎn)品放入緩沖區(qū)。其他操作sin gal(s2); /V操作，發(fā)送可以消費的信號量 endend消費進程偽碼：Process C:beg inwhile(true) dobeg in/P操作，等待可以消費的信號量 從緩沖區(qū)中取出產(chǎn)品進行消費。/其他操作sin gal(s

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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