操作系統(tǒng)作業(yè)題與答案

...wd......wd......wd...《操作系統(tǒng)》課程作業(yè)〔2013年春〕姓名：學(xué)號(hào)：專(zhuān)業(yè)：年級(jí)：學(xué)校：日期：作業(yè)一：作業(yè)管理有三道程序A、B、C在一個(gè)系統(tǒng)中運(yùn)行，該系統(tǒng)有輸入、輸出設(shè)備各1臺(tái)。三道程序A、B、C構(gòu)成如下：A：輸入32秒，計(jì)算8秒，輸出5秒B：輸入21秒，計(jì)算14秒，輸出35秒C：輸入12秒，計(jì)算32秒，輸出15秒問(wèn)： 〔1〕三道程序順序執(zhí)行的總時(shí)間是多少〔2〕充分發(fā)揮各設(shè)備的效能，并行執(zhí)行上述三道程序，最短需多少時(shí)間〔不計(jì)系統(tǒng)開(kāi)銷(xiāo)〕并給出相應(yīng)的示意圖。假設(shè)一個(gè)單CPU系統(tǒng)，以單道方式處理一個(gè)作業(yè)流，作業(yè)流中有2道作業(yè)，共占用CPU計(jì)算時(shí)間、輸入卡片數(shù)和打印輸出行數(shù)如下：作業(yè)號(hào)占用CPU計(jì)算時(shí)間輸入卡片張數(shù)打印輸出行數(shù)13分鐘100張2000行22分鐘200張600行其中，卡片輸入機(jī)速度為1000張/分鐘，打印機(jī)輸出速度為1000行/分鐘，試計(jì)算：不采用spooling技術(shù)，計(jì)算這兩道作業(yè)的總運(yùn)行時(shí)間〔從第1道作業(yè)輸入開(kāi)場(chǎng)到最后一個(gè)作業(yè)輸出完畢〕。如采用spooling技術(shù)，計(jì)算這2道作業(yè)的總運(yùn)行時(shí)間〔不計(jì)讀/寫(xiě)盤(pán)時(shí)間〕，并給出相應(yīng)的示意圖。作業(yè)二：進(jìn)程管理請(qǐng)寫(xiě)出兩程序S1和S2可并發(fā)執(zhí)行的Bernstein條件。有以下5條語(yǔ)句，請(qǐng)畫(huà)出這5條語(yǔ)句的前趨圖。S1：y=x+1 R(x) W(y)S2：c=f-w R(f,w) W(c)S3：d=r-y R(r,y) W(d)S4：x=a+b R(a,b) W(x)S5：r=c+y R(c,y) W(r)設(shè)在教材第62頁(yè)3.6.4節(jié)中所描述的生產(chǎn)者消費(fèi)者問(wèn)題中，其緩沖局部為m個(gè)長(zhǎng)度相等的有界緩沖區(qū)組成，且每次傳輸數(shù)據(jù)長(zhǎng)度等于有界緩沖區(qū)長(zhǎng)度以及生產(chǎn)者和消費(fèi)者可對(duì)緩沖區(qū)同時(shí)操作。重新描述發(fā)送過(guò)程deposit(data)和接收過(guò)程remove(data)。設(shè)有k個(gè)進(jìn)程共享一臨界區(qū)，對(duì)于下述情況，請(qǐng)說(shuō)明信號(hào)量的初值、含義，并用P，V操作寫(xiě)出有關(guān)互斥算法。一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)；一次允許m〔m<k〕個(gè)進(jìn)程進(jìn)入臨界區(qū)。作業(yè)三：進(jìn)程管理假假設(shè)一個(gè)街道交通如以以以下圖所示，假設(shè)有一長(zhǎng)度大于兩個(gè)路口距離的車(chē)，可以從東南西北四個(gè)方向開(kāi)來(lái)，問(wèn)〔1〕何時(shí)會(huì)發(fā)生死鎖〔2〕請(qǐng)?zhí)岢鲆环N可預(yù)防死鎖發(fā)生的簡(jiǎn)單方法。某超市市場(chǎng)科容納100人同時(shí)購(gòu)物，入口處備有籃子，每個(gè)購(gòu)物者可取1只籃子入內(nèi)購(gòu)物，出口處結(jié)賬并歸還籃子〔出、入口僅容1人通過(guò)〕。請(qǐng)?jiān)囉肞，V操作及信號(hào)量寫(xiě)出如下情況的購(gòu)物同步算法：〔1〕1個(gè)出入口，且一次只允許1人通過(guò)；〔2〕1個(gè)入口，n個(gè)出口〔n≥1且為整數(shù)〕。3、設(shè)有無(wú)窮多個(gè)緩沖區(qū)和無(wú)窮多個(gè)信息，甲進(jìn)程把信息逐個(gè)寫(xiě)入每個(gè)緩沖區(qū)，乙進(jìn)程則逐個(gè)地從緩沖區(qū)中取出信息。試問(wèn)： 〔1〕兩個(gè)進(jìn)程間的制約關(guān)系； 〔2〕用P，V操作寫(xiě)出兩個(gè)進(jìn)程的同步算法，并給出信號(hào)量的初值； 〔3〕指出信號(hào)量的值的變化范圍及取值的含義。作業(yè)四：作業(yè)、進(jìn)程調(diào)度1、下面哪幾種調(diào)度算法適合于作業(yè)調(diào)度，哪些適合進(jìn)程調(diào)度〔1〕先來(lái)先服務(wù)〔2〕輪轉(zhuǎn)法〔3〕短作業(yè)優(yōu)先〔4〕優(yōu)先級(jí)高者優(yōu)先〔5〕長(zhǎng)作業(yè)優(yōu)先2、作業(yè)調(diào)度算法選擇作業(yè)的原則可以是保證系統(tǒng)吞吐量大、對(duì)用戶(hù)公平合理或者充分發(fā)揮系統(tǒng)資源的利用率。通常情況下，采用簡(jiǎn)單算法只能表達(dá)其中一種原則而其它原則得不到反映。為此，給出以下能反映多種原則的調(diào)度算法，并假定完全根據(jù)優(yōu)先數(shù)從高到低順序挑選作業(yè)，作業(yè)優(yōu)先數(shù)按下述公式計(jì)算：R(優(yōu)先數(shù))=(作業(yè)等待時(shí)間)2+1/(作業(yè)要求運(yùn)行時(shí)間)請(qǐng)問(wèn)這種算法反映了上述原則中的哪些原則并簡(jiǎn)述理由。3、假設(shè)有4道作業(yè)，它們的提交時(shí)刻及運(yùn)行時(shí)間由下表給出：作業(yè)號(hào)提交時(shí)刻/小時(shí)執(zhí)行時(shí)間/小時(shí)110.002210.201310.400.5410.500.3計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法、最短作業(yè)優(yōu)先調(diào)度算法和最高響應(yīng)比優(yōu)先調(diào)度算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，并指出他們的調(diào)度順序。作業(yè)五：存儲(chǔ)管理1、假定某頁(yè)式虛擬系統(tǒng)中，頁(yè)面大小為100個(gè)單元，某作業(yè)占有實(shí)頁(yè)面數(shù)為M=3，它的訪問(wèn)地址〔走向〕序列為75，175，66，267，32，102，333，166，22，255，256〔數(shù)字為虛存的邏輯地址〕?！?〕請(qǐng)指出這些單元對(duì)應(yīng)的頁(yè)面訪問(wèn)順序序列；〔2〕按先來(lái)先服務(wù)〔FIFO〕頁(yè)面淘汰算法求出缺頁(yè)率f，并畫(huà)出圖表表示之；〔3〕按最近最久未使用〔LRU〕頁(yè)面置換算法求出缺頁(yè)率f，并畫(huà)出圖表表示之。2、有系統(tǒng)其主存容量為1024K〔字節(jié)〕，有6個(gè)作業(yè)同時(shí)到達(dá)，各作業(yè)要求主存量和運(yùn)行時(shí)間如下表所示。假定系統(tǒng)初啟時(shí)，將主存1024K按作業(yè)的編號(hào)順序分給各道作業(yè)，并假定是多CPU下，分配到主存的作業(yè)都可以立即運(yùn)行。請(qǐng)問(wèn)： 〔1〕1秒后，主存空白區(qū)按首次適應(yīng)和最正確適應(yīng)算法的鏈接方式鏈接，將若何鏈接〔2〕2秒后，主存空白區(qū)按首次適應(yīng)和最正確適應(yīng)算法的鏈接方式鏈接，將若何鏈接 〔3〕在〔2〕后，此時(shí)有一個(gè)作業(yè)7要求進(jìn)入主存，它需要主存量為30K，按上述兩種算法應(yīng)把那一塊空白區(qū)分給它，并畫(huà)出分配后的鏈接情況。作業(yè)編號(hào)需主存量〔K〕運(yùn)行時(shí)間〔s〕1200221201310034501580363202作業(yè)六：文件管理1、在UNIX系統(tǒng)中，為使文件的索引表較小又能允許組織大文件，采用直接索引與屢次間接索引〔多級(jí)索引〕方式，給出一個(gè)文件的所有磁盤(pán)的塊號(hào)，如以以以下圖。假設(shè)每個(gè)磁盤(pán)塊大小為1024字節(jié)，并且每個(gè)間接塊容納256個(gè)塊號(hào)，試問(wèn)：〔1〕如某進(jìn)程要讀取某文件的字節(jié)偏移量為9000處的數(shù)據(jù)，應(yīng)若何找到它所在的磁盤(pán)塊及塊內(nèi)位移量〔2〕如想要存取350000處，又將若何直接04096直接1228直接245423直接3401直接4702直接511111直接610直接7101直接8367直接990間接428間接9156間接8242、磁道〔0-90道〕的存取正在處理第55道的服務(wù)請(qǐng)求，對(duì)于磁盤(pán)訪問(wèn)序列〔磁道號(hào)〕：22、77、35、90、40、83、66，試問(wèn)對(duì)以下的磁盤(pán)I/O請(qǐng)求調(diào)度算法而言，滿(mǎn)足以上請(qǐng)求序列，磁頭將若何移動(dòng)，移動(dòng)距離為多少假設(shè)每移動(dòng)一個(gè)柱面需3ms，計(jì)算總共花費(fèi)的尋道時(shí)間。 〔1〕先來(lái)先服務(wù)算法〔FCFS〕 〔2〕最短查找時(shí)間優(yōu)先調(diào)度〔SSTF〕 〔3〕掃描調(diào)度〔SCAN〕〔電梯調(diào)度算法〕 〔4〕循環(huán)掃描〔C-SCAN〕算法3、如果磁道范圍0-99，剛完畢第50道的服務(wù)請(qǐng)求，對(duì)于磁道序列70，25，40，85，90，55，分別按第2題〔1〕-〔4〕四種磁道掃描方法，磁頭將若何移動(dòng)作業(yè)一：作業(yè)管理有三道程序A、B、C在一個(gè)系統(tǒng)中運(yùn)行，該系統(tǒng)有輸入、輸出設(shè)備各1臺(tái)。三道程序A、B、C構(gòu)成如下：A：輸入32秒，計(jì)算8秒，輸出5秒B：輸入21秒，計(jì)算14秒，輸出35秒C：輸入12秒，計(jì)算32秒，輸出15秒問(wèn)： 〔1〕三道程序順序執(zhí)行的總時(shí)間是多少〔2〕充分發(fā)揮各設(shè)備的效能，并行執(zhí)行上述三道程序，最短需多少時(shí)間〔不計(jì)系統(tǒng)開(kāi)銷(xiāo)〕并給出相應(yīng)的示意圖。假設(shè)一個(gè)單CPU系統(tǒng)，以單道方式處理一個(gè)作業(yè)流，作業(yè)流中有2道作業(yè)，共占用CPU計(jì)算時(shí)間、輸入卡片數(shù)和打印輸出行數(shù)如下：作業(yè)號(hào)占用CPU計(jì)算時(shí)間輸入卡片張數(shù)打印輸出行數(shù)13分鐘100張2000行22分鐘200張600行其中，卡片輸入機(jī)速度為1000張/分鐘，打印機(jī)輸出速度為1000行/分鐘，試計(jì)算：不采用spooling技術(shù)，計(jì)算這兩道作業(yè)的總運(yùn)行時(shí)間〔從第1道作業(yè)輸入開(kāi)場(chǎng)到最后一個(gè)作業(yè)輸出完畢〕。如采用spooling技術(shù)，計(jì)算這2道作業(yè)的總運(yùn)行時(shí)間〔不計(jì)讀/寫(xiě)盤(pán)時(shí)間〕，并給出相應(yīng)的示意圖。作業(yè)一解答過(guò)程：1、〔1〕三道程序順序執(zhí)行的總時(shí)間是：32+8+5+21+14+35+12+32+15=174秒?！?〕充分發(fā)揮各設(shè)備的效能，并行執(zhí)行上述三道程序，最短需90秒〔按BCA順序執(zhí)行〕，示意圖如下：時(shí)間〔秒〕時(shí)間〔秒〕90輸入計(jì)算輸出輸入計(jì)算輸出輸入計(jì)算輸出程序C程序B2135程序A0706585注：按ABC執(zhí)行需117s，按ACB執(zhí)行需126s，按BAC執(zhí)行需112s，按BCA執(zhí)行需90s，按CAB執(zhí)行114s，按CBA執(zhí)行需99s。2、〔1〕不采用spooling技術(shù)，計(jì)算這兩道作業(yè)的總運(yùn)行時(shí)間為： 100/1000〔輸入〕+3〔執(zhí)行〕+2000/1000〔輸出〕+200/1000+2+600/1000=7.9分鐘5.3時(shí)間〔5.3時(shí)間〔分〕7.9輸入計(jì)算輸出輸入計(jì)算輸出程序2程序10.13.15.17.3〔2〕采用spooling技術(shù)，這2道作業(yè)的總運(yùn)行時(shí)間為5.7分鐘。0.2時(shí)間〔0.2時(shí)間〔分〕輸入計(jì)算輸出輸入計(jì)算輸出程序2程序10.13.15.15.7作業(yè)二：進(jìn)程管理請(qǐng)寫(xiě)出兩程序S1和S2可并發(fā)執(zhí)行的Bernstein條件。有以下5條語(yǔ)句，請(qǐng)畫(huà)出這5條語(yǔ)句的前趨圖。S1：y=x+1 R(x) W(y)S2：c=f-w R(f,w) W(c)S3：d=r-y R(r,y) W(d)S4：x=a+b R(a,b) W(x)S5：r=c+y R(c,y) W(r)設(shè)在教材第62頁(yè)3.6.4節(jié)中所描述的生產(chǎn)者消費(fèi)者問(wèn)題中，其緩沖局部為m個(gè)長(zhǎng)度相等的有界緩沖區(qū)組成，且每次傳輸數(shù)據(jù)長(zhǎng)度等于有界緩沖區(qū)長(zhǎng)度以及生產(chǎn)者和消費(fèi)者可對(duì)緩沖區(qū)同時(shí)操作。重新描述發(fā)送過(guò)程deposit(data)和接收過(guò)程remove(data)。設(shè)有k個(gè)進(jìn)程共享一臨界區(qū)，對(duì)于下述情況，請(qǐng)說(shuō)明信號(hào)量的初值、含義，并用P，V操作寫(xiě)出有關(guān)互斥算法。一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)；一次允許m〔m<k〕個(gè)進(jìn)程進(jìn)入臨界區(qū)。作業(yè)二解答過(guò)程：1、Bernstein條件〔可并發(fā)執(zhí)行的條件〕：設(shè)R(Si)={a1,a2,…,am}表示程序Si在執(zhí)行期間所需要引用〔讀〕變量的集合---讀集W(Si)={b1,b2,…,bn}表示程序Si在執(zhí)行期間要改變〔寫(xiě)〕變量的集合---寫(xiě)集如果兩個(gè)程序S1和S2能同時(shí)滿(mǎn)足下述條件，它們便能并發(fā)執(zhí)行，否則不能R(S1)∩W(S2)={∮}，W(S1)∩R(S2)={∮}，W(S1)∩W(S2)={∮}〔也可以寫(xiě)成R(S1)∩W(S2)∪W(S1)∩R(S2)∪W(S1)∩W(S2)={∮}〕2、前趨圖：S4S4S2S1S5S33、設(shè)第i塊緩沖區(qū)的公用信號(hào)量為buf[i]，初值為1；生產(chǎn)者進(jìn)程的私用信號(hào)量為produce，初值為m；消費(fèi)者進(jìn)程的私用信號(hào)量為consume，初值為0。發(fā)送過(guò)程deposit(data)和接收過(guò)程remove(data)描述如下：Deposit(data)：Begin P(produce) 選擇一個(gè)空緩沖區(qū)i P(buf[i]) 送數(shù)據(jù)入緩沖區(qū)i V(consume) V(buf[i])EndRemove(data)：Begin P(consume) 選擇一個(gè)滿(mǎn)緩沖區(qū)i P(buf[i]) 取緩沖區(qū)i中的數(shù)據(jù) V(produce) V(buf[i]) End4、〔1〕一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)： 設(shè)s為互斥信號(hào)量，初值為1，表示有1個(gè)空閑且可用的共享臨界資源 對(duì)任一進(jìn)程Pi〔1≤i≤k〕： P(s) <進(jìn)入臨界區(qū)> V(s) 信號(hào)量s的變化范圍為[-(k-1),…,-1,0,1]。其中，s=1表示有1個(gè)空閑且可用的臨界資源，且沒(méi)有進(jìn)程進(jìn)入類(lèi)名為s的臨界區(qū)；s=0表示有1個(gè)進(jìn)程在臨界區(qū)中〔該臨界資源已被某進(jìn)程占用〕，但無(wú)等待使用該臨界資源的進(jìn)程；s=-n(1≤n≤k-1，n為整數(shù))表示有1個(gè)進(jìn)程在臨界區(qū)中，且有n個(gè)進(jìn)程等待使用該臨界資源?！?〕一次允許m〔m<k〕個(gè)進(jìn)程進(jìn)入臨界區(qū)： 設(shè)s為互斥信號(hào)量，初值為m，表示有m個(gè)空閑且可用的共享臨界資源，即可允許m個(gè)進(jìn)程同時(shí)進(jìn)入該臨界區(qū) 對(duì)任一進(jìn)程Pi〔1≤i≤k〕： P(s) <進(jìn)入臨界區(qū)> V(s) 信號(hào)量s的變化范圍為[-(k-m),…,-1,0,1,…,m]。其中，s=m表示有m個(gè)空閑且可用的臨界資源，且沒(méi)有進(jìn)程進(jìn)入類(lèi)名為s的臨界區(qū)；s=j(1≤j＜m，j為整數(shù))表示有m-j個(gè)進(jìn)程正在該臨界區(qū)中，且仍有j個(gè)空閑且可用的臨界資源，但無(wú)等待使用該臨界資源的進(jìn)程；s=0表示有m個(gè)進(jìn)程在臨界區(qū)中，目前無(wú)空閑且可用的臨界資源，但無(wú)等待使用該臨界資源的進(jìn)程；s=-n(1≤n≤k-m，n為整數(shù))表示有m個(gè)進(jìn)程在臨界區(qū)中，目前無(wú)空閑且可用的臨界資源，且有n個(gè)進(jìn)程等待使用該臨界資源。作業(yè)三：進(jìn)程管理假假設(shè)一個(gè)街道交通如以以以下圖所示，假設(shè)有一長(zhǎng)度大于兩個(gè)路口距離的車(chē)，可以從東南西北四個(gè)方向開(kāi)來(lái)，問(wèn)〔1〕何時(shí)會(huì)發(fā)生死鎖〔2〕請(qǐng)?zhí)岢鲆环N可預(yù)防死鎖發(fā)生的簡(jiǎn)單方法。北./北某超市市場(chǎng)科容納100人同時(shí)購(gòu)物，入口處備有籃子，每個(gè)購(gòu)物者可取1只籃子入內(nèi)購(gòu)物，出口處結(jié)賬并歸還籃子〔出、入口僅容1人通過(guò)〕。請(qǐng)?jiān)囉肞，V操作及信號(hào)量寫(xiě)出如下情況的購(gòu)物同步算法：〔1〕1個(gè)出入口，且一次只允許1人通過(guò)；〔2〕1個(gè)入口，n個(gè)出口〔n≥1且為整數(shù)〕。3、設(shè)有無(wú)窮多個(gè)緩沖區(qū)和無(wú)窮多個(gè)信息，甲進(jìn)程把信息逐個(gè)寫(xiě)入每個(gè)緩沖區(qū)，乙進(jìn)程則逐個(gè)地從緩沖區(qū)中取出信息。試問(wèn)： 〔1〕兩個(gè)進(jìn)程間的制約關(guān)系； 〔2〕用P，V操作寫(xiě)出兩個(gè)進(jìn)程的同步算法，并給出信號(hào)量的初值； 〔3〕指出信號(hào)量的值的變化范圍及取值的含義。作業(yè)三解答過(guò)程：1、〔1〕何時(shí)會(huì)發(fā)生死鎖北北〔2〕請(qǐng)?zhí)岢鲆环N可預(yù)防死鎖發(fā)生的簡(jiǎn)單方法北北方向①方向②方向③方向④路口S1路口S2路口S3路口S4 設(shè)4個(gè)路口為4個(gè)資源，其信號(hào)量分別設(shè)為S1，S2，S3和S4，初值均為1，代表資源空閑可用，下面用P，V操作預(yù)防死鎖問(wèn)題：方向①進(jìn)程：P〔S1，S2〕<通過(guò)S1、S2路口>V〔S1，S2〕方向②進(jìn)程：P〔S2，S4〕<通過(guò)S2、S4路口>V〔S2，S4〕方向③進(jìn)程：P〔S3，S4〕<通過(guò)S3、S4路口>V〔S3，S4〕方向④進(jìn)程：P〔S1，S3〕<通過(guò)S1、S3路口>V〔S1，S3〕信號(hào)量S1，S2，S3和S4的變化范圍均為[-∞,…,-1,0,1]。其中，S1~S4=1表示有1個(gè)空閑且可用的臨界資源，且沒(méi)有進(jìn)程進(jìn)入類(lèi)名為S1~S4的臨界區(qū)；S1~S4=0表示有1個(gè)進(jìn)程在臨界區(qū)中，目前無(wú)空閑且可用的臨界資源，但無(wú)等待使用該臨界資源的進(jìn)程；S1~S4=-m〔m為正整數(shù)〕表示有1個(gè)進(jìn)程正在該臨界區(qū)中，目前無(wú)空閑且可用的臨界資源，且有m個(gè)進(jìn)程等待使用該臨界資源。2、〔1〕1個(gè)出入口，且一次只允許1人通過(guò)：設(shè)超市容量信號(hào)量為S，初值為100；購(gòu)物進(jìn)程為Pi，購(gòu)物信號(hào)量為mutex，初值為1。購(gòu)物進(jìn)程Pi同步描述：P〔S〕P〔mutex〕<進(jìn)入超市并取1只籃子>V〔mutex〕<選購(gòu)商品>P〔mutex〕<結(jié)賬并歸還籃子>V〔mutex〕V〔S〕信號(hào)量S的變化范圍為[-m,…,-1,0,1,…,100](m為正整數(shù))。其中，S=100表示有100個(gè)空閑且可用的臨界資源，且沒(méi)有進(jìn)程進(jìn)入類(lèi)名為S的臨界區(qū)；s=j(1≤j＜100，j為整數(shù))表示有100-j個(gè)進(jìn)程正在該臨界區(qū)中，且仍有j個(gè)空閑且可用的臨界資源，但無(wú)等待使用該臨界資源的進(jìn)程；s=0表示有100個(gè)進(jìn)程在臨界區(qū)中，目前無(wú)空閑且可用的臨界資源，但無(wú)等待使用該臨界資源的進(jìn)程；s=-m(m為正整數(shù))表示有100個(gè)進(jìn)程在臨界區(qū)中，目前無(wú)空閑且可用的臨界資源，且有m個(gè)進(jìn)程等待使用該臨界資源；信號(hào)量mutex的變化范圍為[-99,…,-1,0,1]。其中，……〔2〕1個(gè)入口，n個(gè)出口〔n≥1且為整數(shù)〕 設(shè)購(gòu)物進(jìn)程為Pi,；超市容量信號(hào)量為S，初值為100；入口互斥信號(hào)量為mutex1，初值為1；出口互斥信號(hào)量為mutex2，初值為n。購(gòu)物進(jìn)程Pi同步描述：P〔S〕P〔mutex1〕<進(jìn)入超市并取1只籃子>V〔mutex1〕<選購(gòu)商品>P〔mutex2〕<結(jié)賬并歸還籃子>V〔mutex2〕V〔S〕 信號(hào)量S的變化范圍為[-m,…,-1,0,1,…,100]〔m為正整數(shù)〕。其中，……；信號(hào)量mutex1和mutex2的變化范圍均為[-99,…,-1,0,1]。其中，……3、〔1〕兩個(gè)進(jìn)程間的制約關(guān)系：乙進(jìn)程不能先于甲進(jìn)程執(zhí)行，而甲進(jìn)程不受乙進(jìn)程約束?！?〕設(shè)置1個(gè)信號(hào)量S，S表示甲進(jìn)程寫(xiě)滿(mǎn)的緩沖區(qū)的個(gè)數(shù)，S初值為0，表示緩沖區(qū)為空，則甲、乙兩進(jìn)程的同步算法描述為甲進(jìn)程：i=0i=i+1<寫(xiě)入第i個(gè)緩沖區(qū)>V〔S〕乙進(jìn)程：j=0j=j+1P〔S〕<讀出第j個(gè)緩沖區(qū)> 〔3〕信號(hào)量S的變化范圍為[-1,+∞]中的整數(shù)，當(dāng)S=-1時(shí)表示緩沖區(qū)從未被寫(xiě)入信息或緩沖區(qū)信息被乙進(jìn)程讀空，且乙進(jìn)程要求進(jìn)一步讀緩沖區(qū)中的信息，即乙進(jìn)程超前甲進(jìn)程欲讀取緩沖區(qū)的信息而受阻。作業(yè)四：作業(yè)、進(jìn)程調(diào)度1、下面哪幾種調(diào)度算法適合于作業(yè)調(diào)度，哪些適合進(jìn)程調(diào)度〔1〕先來(lái)先服務(wù)〔2〕輪轉(zhuǎn)法〔3〕短作業(yè)優(yōu)先〔4〕優(yōu)先級(jí)高者優(yōu)先〔5〕長(zhǎng)作業(yè)優(yōu)先2、作業(yè)調(diào)度算法選擇作業(yè)的原則可以是保證系統(tǒng)吞吐量大、對(duì)用戶(hù)公平合理或者充分發(fā)揮系統(tǒng)資源的利用率。下表給出了3種簡(jiǎn)單的作業(yè)調(diào)度算法：調(diào)度算法吞吐量大公平合理發(fā)揮資源利用率先來(lái)先服務(wù)最短作業(yè)優(yōu)先〔1〕請(qǐng)指出每種算法主要是表達(dá)了上述哪種原則。〔在對(duì)應(yīng)的行列上打上記號(hào)√〕〔2〕如果在實(shí)際系統(tǒng)中只采用上述3種簡(jiǎn)單算法的任一種，都只能表達(dá)其中一種原則而其它原則得不到反映。為此，給出以下能反映多種原則的調(diào)度算法，并假定完全根據(jù)優(yōu)先數(shù)從高到低順序挑選作業(yè)，作業(yè)優(yōu)先數(shù)按下述公式計(jì)算：R(優(yōu)先數(shù))=(作業(yè)等待時(shí)間)2+1/(作業(yè)要求運(yùn)行時(shí)間)請(qǐng)問(wèn)這種算法反映了上述原則中的哪些原則并簡(jiǎn)述理由。3、假設(shè)有4道作業(yè)，它們的提交時(shí)刻及運(yùn)行時(shí)間由下表給出：作業(yè)號(hào)提交時(shí)刻/小時(shí)執(zhí)行時(shí)間/小時(shí)110.002210.201310.400.5410.500.3計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)調(diào)度算法、最短作業(yè)優(yōu)先調(diào)度算法和最高響應(yīng)比優(yōu)先調(diào)度算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，并指出他們的調(diào)度順序。作業(yè)四解答過(guò)程：1、適用于作業(yè)調(diào)度用的算法：〔1〕〔3〕〔4〕〔5〕，適用于進(jìn)程調(diào)度用的算法：〔1〕〔2〕〔4〕。2、〔1〕調(diào)度算法吞吐量大公平合理發(fā)揮資源利用率先來(lái)先服務(wù)√最短作業(yè)優(yōu)先√√〔2〕該算法表達(dá)了先來(lái)先服務(wù)原則和最短作業(yè)優(yōu)先原則。理由如下：表達(dá)先來(lái)先服務(wù)原則：假假設(shè)兩作業(yè)運(yùn)行時(shí)間一樣，但到達(dá)時(shí)間不同，早到達(dá)的作業(yè)等待時(shí)間長(zhǎng)，根據(jù)公式計(jì)算，它的優(yōu)先數(shù)大，則優(yōu)先調(diào)度。表達(dá)最短作業(yè)優(yōu)先原則：假假設(shè)兩道作業(yè)同時(shí)到達(dá)，但運(yùn)行時(shí)間不等，根據(jù)公式計(jì)算，運(yùn)行時(shí)間短的作業(yè)其優(yōu)先數(shù)高，因而優(yōu)先調(diào)度。3、〔1〕先來(lái)先服務(wù)〔FCFS〕調(diào)度：調(diào)度順序?yàn)?→2→3→4。作業(yè)號(hào)到達(dá)時(shí)間完畢時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.0012.0021.00210.2013.002.82.80310.4013.503.16.20410.5013.803.311.00 平均周轉(zhuǎn)時(shí)間T=(2+2.8+3.1+3.3)/4=2.8小時(shí) 平均帶權(quán)周轉(zhuǎn)時(shí)間W=(1+2.8+6.2+11)/4=5.25小時(shí)〔2〕最短作業(yè)優(yōu)先〔SJF〕調(diào)度：調(diào)度順序?yàn)?→4→3→2。作業(yè)號(hào)到達(dá)時(shí)間完畢時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.0012.0021410.5012.301.806310.4012.802.404.8210.2013.803.603.6 平均周轉(zhuǎn)時(shí)間T=(2+1.8+2.4+3.6)/4=2.45小時(shí) 平均帶權(quán)周轉(zhuǎn)時(shí)間W=(1+6+4.8+3.6)/4=3.85小時(shí)〔3〕最高響應(yīng)比優(yōu)先〔HRN〕調(diào)度：調(diào)度順序?yàn)?→4→3→2。響應(yīng)比=(作業(yè)執(zhí)行時(shí)間+作業(yè)等待時(shí)間)/作業(yè)執(zhí)行時(shí)間 從下表可見(jiàn)，在作業(yè)1完成時(shí)刻〔12.00〕，作業(yè)2、3、4的響應(yīng)比最高的為4；在作業(yè)4完成時(shí)刻〔12.30〕，作業(yè)2、3的響應(yīng)比最高的為3。作業(yè)號(hào)等待時(shí)間執(zhí)行時(shí)間響應(yīng)比21.8012.831.600.54.241.500.3622.113.131.90.54.8作業(yè)號(hào)到達(dá)時(shí)間完畢時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.0012.0021410.5012.301.806310.4012.802.404.8210.2013.803.603.6平均周轉(zhuǎn)時(shí)間T=(2+1.8+2.4+3.6)/4=2.45小時(shí) 平均帶權(quán)周轉(zhuǎn)時(shí)間W=(1+6+4.8+3.6)/4=3.85小時(shí)作業(yè)五：存儲(chǔ)管理1、假定某頁(yè)式虛擬系統(tǒng)中，頁(yè)面大小為100個(gè)單元，某作業(yè)占有實(shí)頁(yè)面數(shù)為M=3，它的訪問(wèn)地址〔走向〕序列為75，175，66，267，32，102，333，166，22，255，256〔數(shù)字為虛存的邏輯地址〕?！?〕請(qǐng)指出這些單元對(duì)應(yīng)的頁(yè)面訪問(wèn)順序序列；〔2〕按先來(lái)先服務(wù)〔FIFO〕頁(yè)面淘汰算法求出缺頁(yè)率f，并畫(huà)出圖表表示之；〔3〕按最近最久未使用〔LRU〕頁(yè)面置換算法求出缺頁(yè)率f，并畫(huà)出圖表表示之。2、有系統(tǒng)其主存容量為1024K〔字節(jié)〕，有6個(gè)作業(yè)同時(shí)到達(dá)，各作業(yè)要求主存量和運(yùn)行時(shí)間如下表所示。假定系統(tǒng)初啟時(shí)，將主存1024K按作業(yè)的編號(hào)順序分給各道作業(yè)，并假定是多CPU下，分配到主存的作業(yè)都可以立即運(yùn)行。請(qǐng)問(wèn)： 〔1〕1秒后，主存空白區(qū)按首次適應(yīng)和最正確適應(yīng)算法的鏈接方式鏈接，將若何鏈接 〔2〕2秒后，主存空白區(qū)按首次適應(yīng)和最正確適應(yīng)算法的鏈接方式鏈接，將若何鏈接 〔3〕在〔2〕后，此時(shí)有一個(gè)作業(yè)7要求進(jìn)入主存，它需要主存量為30K，按上述兩種算法應(yīng)把那一塊空白區(qū)分給它，并畫(huà)出分配后的鏈接情況。作業(yè)編號(hào)需主存量〔K〕運(yùn)行時(shí)間〔s〕1200221201310034501580363202作業(yè)五解答過(guò)程：1、〔1〕訪問(wèn)序列為0，1，0，2，0，1，3，1，0，2，2?！?〕FIFO：頁(yè)面0102013102210112223300020011122333300011222缺頁(yè)××√×√√×√×√√缺頁(yè)率f=5/11=45.45%?！?〕LRU：頁(yè)面0102013102210102013102220102013100311200311缺頁(yè)××√×√√×√√×√ 缺頁(yè)率f=5/11=45.45%。2、〔1〕1秒后，主存空白區(qū)按首次適應(yīng)和最正確適應(yīng)算法的鏈接方式： 首次適應(yīng)算法：120→50→154 最正確適應(yīng)算法：50→120→154〔2〕2秒后，主存空白區(qū)的鏈接方式： 首次適應(yīng)算法：320→50→474 最正確適應(yīng)算法：50→320→474〔3〕2秒后，作業(yè)7要求進(jìn)入主存： 首次適應(yīng)算法：290→50→474最正確適應(yīng)算法：20→320→4742001201005080320154〔空閑〕作業(yè)六：文件管理1、在UNIX系統(tǒng)中，為使文件的索引表較小又能允許組織大文件，采用直接索引與屢次間接索引〔多級(jí)索引〕方式，給出一個(gè)文件的所有磁盤(pán)的塊號(hào)，如以以以下圖。假設(shè)每個(gè)磁盤(pán)塊大小為1024字節(jié)，并且每個(gè)間接塊容納256個(gè)塊號(hào)，試問(wèn)：〔1〕如某進(jìn)程要讀取某文件的字節(jié)偏移量為9000處的數(shù)據(jù)，應(yīng)若何找到它所在的磁盤(pán)塊及塊內(nèi)位移量〔2〕如想要存取350000處，又將若何直接0367808367808數(shù)據(jù)塊直接1228直接245423直接3401直接4702直接511111直接610直接7101直接83333數(shù)據(jù)塊81633133333333數(shù)據(jù)塊8163313333一次間址759156331二次間址0直接990間接428間接9156間接8242、磁道〔0-90道〕的存取正在處理第55道的服務(wù)請(qǐng)求，對(duì)于磁盤(pán)訪問(wèn)序列〔磁道號(hào)〕：22、77、35、90、40、83、66，試問(wèn)對(duì)以下的磁盤(pán)I/O請(qǐng)求調(diào)度算法而言，滿(mǎn)足以上請(qǐng)求序列，磁頭將若何移動(dòng)，移動(dòng)距離為多少假設(shè)每移動(dòng)一個(gè)柱面需3ms，計(jì)算總共花費(fèi)的尋道時(shí)間。 〔1〕先來(lái)先服務(wù)算法〔FCFS〕 〔2〕最短查找時(shí)間優(yōu)先調(diào)度〔SSTF〕 〔3〕掃描調(diào)度〔SCAN〕〔電梯調(diào)度算法〕 〔4〕循環(huán)掃描〔C-SCAN〕算法3、如果磁道范圍0-99，剛完畢第50道的服務(wù)請(qǐng)求，對(duì)于磁道序列70，25，40，85，90，55，分別按第2題〔1〕-〔4〕四種磁道掃描方法，磁頭將若何移動(dòng)作業(yè)六解答過(guò)程：1、〔1〕根據(jù)9000/1024=8.8，故該字節(jié)在文件索引8〔從0開(kāi)場(chǎng)計(jì)〕直接塊中，于是可從表目項(xiàng)中讀出內(nèi)容為367，即該字節(jié)在