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

1、操作系統(tǒng)課程作業(yè)（2013年春）姓名：學(xué)號(hào)：專業(yè)：年級(jí)：學(xué)校：日期：作業(yè)一：作業(yè)管理1、 有三道程序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秒問：（1）三道程序順序執(zhí)行的總時(shí)間是多少？（2）充分發(fā)揮各設(shè)備的效能，并行執(zhí)行上述三道程序，最短需多少時(shí)間（不計(jì)系統(tǒng)開銷）？并給出相應(yīng)的示意圖。2、 假設(shè)一個(gè)單CPU系統(tǒng)，以單道方式處理一個(gè)作業(yè)流，作業(yè)流中有2道作業(yè)，共占用CPU計(jì)算時(shí)間、輸入卡片數(shù)和打印輸出行數(shù)如下：作業(yè)號(hào)占用CPU計(jì)算時(shí)間輸入卡片張

2、數(shù)打印輸出行數(shù)13分鐘100張2000行22分鐘200張600行其中，卡片輸入機(jī)速度為1000張/分鐘，打印機(jī)輸出速度為1000行/分鐘，試計(jì)算：（1） 不采用spooling技術(shù)，計(jì)算這兩道作業(yè)的總運(yùn)行時(shí)間（從第1道作業(yè)輸入開始到最后一個(gè)作業(yè)輸出完畢）。（2） 如采用spooling技術(shù)，計(jì)算這2道作業(yè)的總運(yùn)行時(shí)間（不計(jì)讀/寫盤時(shí)間），并給出相應(yīng)的示意圖。作業(yè)二：進(jìn)程管理1、 請(qǐng)寫出兩程序S1和S2可并發(fā)執(zhí)行的Bernstein條件。2、 有以下5條語句，請(qǐng)畫出這5條語句的前趨圖。S1：y=x+1R(x)W(y)S2：c=f-wR(f,w)W(c)S3：d=r-yR(r,y)W(d)S4：x

3、=a+bR(a,b)W(x)S5：r=c+yR(c,y)W(r)3、 設(shè)在教材第62頁3.6.4節(jié)中所描述的生產(chǎn)者消費(fèi)者問題中，其緩沖部分為m個(gè)長度相等的有界緩沖區(qū)組成，且每次傳輸數(shù)據(jù)長度等于有界緩沖區(qū)長度以及生產(chǎn)者和消費(fèi)者可對(duì)緩沖區(qū)同時(shí)操作。重新描述發(fā)送過程deposit(data)和接收過程remove(data)。4、 設(shè)有k個(gè)進(jìn)程共享一臨界區(qū)，對(duì)于下述情況，請(qǐng)說明信號(hào)量的初值、含義，并用P，V操作寫出有關(guān)互斥算法。（1） 一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)；（2） 一次允許m（m<k）個(gè)進(jìn)程進(jìn)入臨界區(qū)。作業(yè)三：進(jìn)程管理1、 假若一個(gè)街道交通如下圖所示，若有一長度大于兩個(gè)路口距離的車，可

4、以從東南西北四個(gè)方向開來，問（1）何時(shí)會(huì)發(fā)生死鎖？（2）請(qǐng)?zhí)岢鲆环N可預(yù)防死鎖發(fā)生的簡(jiǎn)單方法。2、 某超市市場(chǎng)科容納100人同時(shí)購物，入口處備有籃子，每個(gè)購物者可取1只籃子入內(nèi)購物，出口處結(jié)賬并歸還籃子（出、入口僅容1人通過）。請(qǐng)?jiān)囉肞，V操作及信號(hào)量寫出如下情況的購物同步算法：（1）1個(gè)出入口，且一次只允許1人通過；（2）1個(gè)入口，n個(gè)出口（n1且為整數(shù)）。3、設(shè)有無窮多個(gè)緩沖區(qū)和無窮多個(gè)信息，甲進(jìn)程把信息逐個(gè)寫入每個(gè)緩沖區(qū)，乙進(jìn)程則逐個(gè)地從緩沖區(qū)中取出信息。試問：（1）兩個(gè)進(jìn)程間的制約關(guān)系；（2）用P，V操作寫出兩個(gè)進(jìn)程的同步算法，并給出信號(hào)量的初值；（3）指出信號(hào)量的值的變化范圍及取值的含

5、義。作業(yè)四：作業(yè)、進(jìn)程調(diào)度1、下面哪幾種調(diào)度算法適合于作業(yè)調(diào)度，哪些適合進(jìn)程調(diào)度？（1）先來先服務(wù)（2）輪轉(zhuǎn)法（3）短作業(yè)優(yōu)先（4）優(yōu)先級(jí)高者優(yōu)先（5）長作業(yè)優(yōu)先2、作業(yè)調(diào)度算法選擇作業(yè)的原則可以是保證系統(tǒng)吞吐量大、對(duì)用戶公平合理或者充分發(fā)揮系統(tǒng)資源的利用率。通常情況下，采用簡(jiǎn)單算法只能體現(xiàn)其中一種原則而其它原則得不到反映。為此，給出下列能反映多種原則的調(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)問這種算法反映了上述原則中的哪些原則？并簡(jiǎn)述理由。3、假設(shè)有4道作業(yè)，它們的提交時(shí)刻及運(yùn)行時(shí)間由下表給出：

6、作業(yè)號(hào)提交時(shí)刻/小時(shí)執(zhí)行時(shí)間/小時(shí)110.002210.201310.400.5410.500.3計(jì)算在單道程序環(huán)境下，采用先來先服務(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、假定某頁式虛擬系統(tǒng)中，頁面大小為100個(gè)單元，某作業(yè)占有實(shí)頁面數(shù)為M=3，它的訪問地址（走向）序列為75，175，66，267，32，102，333，166，22，255，256（數(shù)字為虛存的邏輯地址）。（1）請(qǐng)指出這些單元對(duì)應(yīng)的頁面訪問順序序列；（2）按先來先服務(wù)（FIFO）頁面淘汰算法求出缺頁率f，并畫出圖表表示之；（3）按最近

7、最久未使用（LRU）頁面置換算法求出缺頁率f，并畫出圖表表示之。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)問：（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ū)分給它，并畫出分配后的鏈接情況。作業(yè)編號(hào)需主存量（K）運(yùn)行時(shí)間（

8、s）1200221201310034501580363202作業(yè)六：文件管理1、在UNIX系統(tǒng)中，為使文件的索引表較小又能允許組織大文件，采用直接索引與多次間接索引（多級(jí)索引）方式，給出一個(gè)文件的所有磁盤的塊號(hào)，如下圖。假設(shè)每個(gè)磁盤塊大小為1024字節(jié)，并且每個(gè)間接塊容納256個(gè)塊號(hào)，試問：（1）如某進(jìn)程要讀取某文件的字節(jié)偏移量為9000處的數(shù)據(jù)，應(yīng)如何找到它所在的磁盤塊及塊內(nèi)位移量？（2）如想要存取350000處，又將如何？直接04096直接1228直接245423直接3401直接4702直接511111直接610直接7101直接8367直接990間接428間接9156間接8242、磁道（0

9、-90道）的存取正在處理第55道的服務(wù)請(qǐng)求，對(duì)于磁盤訪問序列（磁道號(hào)）：22、77、35、90、40、83、66，試問對(duì)以下的磁盤I/O請(qǐng)求調(diào)度算法而言，滿足以上請(qǐng)求序列，磁頭將如何移動(dòng)，移動(dòng)距離為多少？若每移動(dòng)一個(gè)柱面需3ms，計(jì)算總共花費(fèi)的尋道時(shí)間。（1）先來先服務(wù)算法（FCFS）（2）最短查找時(shí)間優(yōu)先調(diào)度（SSTF）（3）掃描調(diào)度（SCAN）（電梯調(diào)度算法）（4）循環(huán)掃描（C-SCAN）算法3、如果磁道范圍0-99，剛結(jié)束第50道的服務(wù)請(qǐng)求，對(duì)于磁道序列70，25，40，85，90，55，分別按第2題（1）-（4）四種磁道掃描方法，磁頭將如何移動(dòng)？作業(yè)一：作業(yè)管理3、 有三道程序A、B、

10、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秒問：（1）三道程序順序執(zhí)行的總時(shí)間是多少？（2）充分發(fā)揮各設(shè)備的效能，并行執(zhí)行上述三道程序，最短需多少時(shí)間（不計(jì)系統(tǒng)開銷）？并給出相應(yīng)的示意圖。4、 假設(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張/分鐘，打印

11、機(jī)輸出速度為1000行/分鐘，試計(jì)算：（3） 不采用spooling技術(shù)，計(jì)算這兩道作業(yè)的總運(yùn)行時(shí)間（從第1道作業(yè)輸入開始到最后一個(gè)作業(yè)輸出完畢）。（4） 如采用spooling技術(shù)，計(jì)算這2道作業(yè)的總運(yùn)行時(shí)間（不計(jì)讀/寫盤時(shí)間），并給出相應(yīng)的示意圖。作業(yè)一解答過程：1、（1）三道程序順序執(zhí)行的總時(shí)間是：32+8+5+21+14+35+12+32+15=174秒。（2）充分發(fā)揮各設(shè)備的效能，并行執(zhí)行上述三道程序，最短需90秒（按BCA順序執(zhí)行），示意圖如下：時(shí)間（秒）90輸入計(jì)算輸出輸入計(jì)算輸出輸入計(jì)算輸出程序C程序B2135程序A0706585注：按ABC執(zhí)行需117s，按ACB執(zhí)行需126

12、s，按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í)間（分）7.9輸入計(jì)算輸出輸入計(jì)算輸出程序2程序10.13.15.17.3（2）采用spooling技術(shù)，這2道作業(yè)的總運(yùn)行時(shí)間為5.7分鐘。0.2時(shí)間（分）輸入計(jì)算輸出輸入計(jì)算輸出程序2程序10.13.15.15.7作業(yè)二：進(jìn)程管理5、 請(qǐng)寫出兩程序S1和S2可并發(fā)執(zhí)行的Bernstein條件。6、 有以下5

13、條語句，請(qǐng)畫出這5條語句的前趨圖。S1：y=x+1R(x)W(y)S2：c=f-wR(f,w)W(c)S3：d=r-yR(r,y)W(d)S4：x=a+bR(a,b)W(x)S5：r=c+yR(c,y)W(r)7、 設(shè)在教材第62頁3.6.4節(jié)中所描述的生產(chǎn)者消費(fèi)者問題中，其緩沖部分為m個(gè)長度相等的有界緩沖區(qū)組成，且每次傳輸數(shù)據(jù)長度等于有界緩沖區(qū)長度以及生產(chǎn)者和消費(fèi)者可對(duì)緩沖區(qū)同時(shí)操作。重新描述發(fā)送過程deposit(data)和接收過程remove(data)。8、 設(shè)有k個(gè)進(jìn)程共享一臨界區(qū)，對(duì)于下述情況，請(qǐng)說明信號(hào)量的初值、含義，并用P，V操作寫出有關(guān)互斥算法。（1） 一次只允許一個(gè)進(jìn)程進(jìn)

14、入臨界區(qū)；（2） 一次允許m（m<k）個(gè)進(jìn)程進(jìn)入臨界區(qū)。作業(yè)二解答過程：1、Bernstein條件（可并發(fā)執(zhí)行的條件）：設(shè)R(Si)=a1,a2,am表示程序Si在執(zhí)行期間所需要引用（讀）變量的集合-讀集 W(Si)= b1,b2,bn表示程序Si在執(zhí)行期間要改變（寫）變量的集合-寫集 如果兩個(gè)程序S1和S2能同時(shí)滿足下述條件，它們便能并發(fā)執(zhí)行，否則不能R(S1)W(S2)= ，W(S1)R(S2)=，W(S1)W(S2)=（也可以寫成 R(S1)W(S2)W(S1)R(S2)W(S1)W(S2)= ）2、前趨圖：S4S2S1S5S33、設(shè)第i塊緩沖區(qū)的公用信號(hào)量為bufi，初值為1；生

15、產(chǎn)者進(jìn)程的私用信號(hào)量為produce，初值為m；消費(fèi)者進(jìn)程的私用信號(hào)量為consume，初值為0。發(fā)送過程deposit(data)和接收過程remove(data)描述如下：Deposit(data)：BeginP(produce)選擇一個(gè)空緩沖區(qū)iP(bufi)送數(shù)據(jù)入緩沖區(qū)iV(consume)V(bufi)EndRemove(data)：BeginP(consume)選擇一個(gè)滿緩沖區(qū)iP(bufi)取緩沖區(qū)i中的數(shù)據(jù)V(produce)V(bufi)End4、（1）一次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)：設(shè)s為互斥信號(hào)量，初值為1，表示有1個(gè)空閑且可用的共享臨界資源對(duì)任一進(jìn)程Pi（1ik）：P(

16、s)<進(jìn)入臨界區(qū)>V(s)信號(hào)量s的變化范圍為-(k-1) ,-1,0,1。其中，s=1表示有1個(gè)空閑且可用的臨界資源，且沒有進(jìn)程進(jìn)入類名為s的臨界區(qū)；s=0表示有1個(gè)進(jìn)程在臨界區(qū)中（該臨界資源已被某進(jìn)程占用），但無等待使用該臨界資源的進(jìn)程；s=-n(1nk-1，n為整數(shù))表示有1個(gè)進(jìn)程在臨界區(qū)中，且有n個(gè)進(jìn)程等待使用該臨界資源。（2）一次允許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（1ik）：P(s)<進(jìn)入臨界區(qū)>V(s)信號(hào)量s的變化范圍為-(k-m) ,-1,

17、0,1,m。其中，s= m表示有m個(gè)空閑且可用的臨界資源，且沒有進(jìn)程進(jìn)入類名為s的臨界區(qū)；s=j(1jm，j為整數(shù))表示有m-j個(gè)進(jìn)程正在該臨界區(qū)中，且仍有j個(gè)空閑且可用的臨界資源，但無等待使用該臨界資源的進(jìn)程；s=0表示有m個(gè)進(jìn)程在臨界區(qū)中，目前無空閑且可用的臨界資源，但無等待使用該臨界資源的進(jìn)程；s=-n(1nk-m，n為整數(shù))表示有m個(gè)進(jìn)程在臨界區(qū)中，目前無空閑且可用的臨界資源，且有n個(gè)進(jìn)程等待使用該臨界資源。作業(yè)三：進(jìn)程管理3、 假若一個(gè)街道交通如下圖所示，若有一長度大于兩個(gè)路口距離的車，可以從東南西北四個(gè)方向開來，問（1）何時(shí)會(huì)發(fā)生死鎖？（2）請(qǐng)?zhí)岢鲆环N可預(yù)防死鎖發(fā)生的簡(jiǎn)單方法。北.

18、/4、 某超市市場(chǎng)科容納100人同時(shí)購物，入口處備有籃子，每個(gè)購物者可取1只籃子入內(nèi)購物，出口處結(jié)賬并歸還籃子（出、入口僅容1人通過）。請(qǐng)?jiān)囉肞，V操作及信號(hào)量寫出如下情況的購物同步算法：（1）1個(gè)出入口，且一次只允許1人通過；（2）1個(gè)入口，n個(gè)出口（n1且為整數(shù)）。3、設(shè)有無窮多個(gè)緩沖區(qū)和無窮多個(gè)信息，甲進(jìn)程把信息逐個(gè)寫入每個(gè)緩沖區(qū)，乙進(jìn)程則逐個(gè)地從緩沖區(qū)中取出信息。試問：（1）兩個(gè)進(jìn)程間的制約關(guān)系；（2）用P，V操作寫出兩個(gè)進(jìn)程的同步算法，并給出信號(hào)量的初值；（3）指出信號(hào)量的值的變化范圍及取值的含義。作業(yè)三解答過程：1、（1）何時(shí)會(huì)發(fā)生死鎖？北（2）請(qǐng)?zhí)岢鲆环N可預(yù)防死鎖發(fā)生的簡(jiǎn)單方法北

19、方向方向方向方向路口S1路口S2路口S3路口S4設(shè)4個(gè)路口為4個(gè)資源，其信號(hào)量分別設(shè)為S1，S2，S3和S4，初值均為1，代表資源空閑可用，下面用P，V操作預(yù)防死鎖問題：方向進(jìn)程：P（S1，S2）<通過S1、S2路口>V（S1，S2）方向進(jìn)程：P（S2，S4）<通過S2、S4路口>V（S2，S4）方向進(jìn)程：P（S3，S4）<通過S3、S4路口>V（S3，S4）方向進(jìn)程：P（S1，S3）<通過S1、S3路口>V（S1，S3）信號(hào)量S1，S2，S3和S4 的變化范圍均為-,-1,0,1。其中，S1S4=1表示有1個(gè)空閑且可用的臨界資源，且沒有進(jìn)程進(jìn)入

20、類名為S1S4的臨界區(qū)；S1S4=0表示有1個(gè)進(jìn)程在臨界區(qū)中，目前無空閑且可用的臨界資源，但無等待使用該臨界資源的進(jìn)程；S1S4=-m（m為正整數(shù)）表示有1個(gè)進(jìn)程正在該臨界區(qū)中，目前無空閑且可用的臨界資源，且有m個(gè)進(jìn)程等待使用該臨界資源。 2、（1）1個(gè)出入口，且一次只允許1人通過：設(shè)超市容量信號(hào)量為S，初值為100；購物進(jìn)程為Pi，購物信號(hào)量為mutex，初值為1。購物進(jìn)程Pi同步描述：P（S）P（mutex）<進(jìn)入超市并取1只籃子>V（mutex） <選購商品>P（mutex）<結(jié)賬并歸還籃子>V（mutex）V（S）信號(hào)量S的變化范圍為-m,-1,0,

21、1 ,100 (m為正整數(shù))。其中，S=100表示有100個(gè)空閑且可用的臨界資源，且沒有進(jìn)程進(jìn)入類名為S的臨界區(qū)；s=j(1j100，j為整數(shù))表示有100-j個(gè)進(jìn)程正在該臨界區(qū)中，且仍有j個(gè)空閑且可用的臨界資源，但無等待使用該臨界資源的進(jìn)程；s=0表示有100個(gè)進(jìn)程在臨界區(qū)中，目前無空閑且可用的臨界資源，但無等待使用該臨界資源的進(jìn)程；s=-m (m為正整數(shù))表示有100個(gè)進(jìn)程在臨界區(qū)中，目前無空閑且可用的臨界資源，且有m個(gè)進(jìn)程等待使用該臨界資源；信號(hào)量mutex的變化范圍為-99 ,-1,0,1 。其中，（2）1個(gè)入口，n個(gè)出口（n1且為整數(shù)）設(shè)購物進(jìn)程為Pi,；超市容量信號(hào)量為S，初值為1

22、00；入口互斥信號(hào)量為mutex1，初值為1；出口互斥信號(hào)量為mutex2，初值為n。購物進(jìn)程Pi同步描述：P（S）P（mutex1）<進(jìn)入超市并取1只籃子>V（mutex1） <選購商品>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)程約束。（2）設(shè)置1個(gè)信號(hào)量S，S表示甲進(jìn)程寫滿的緩沖區(qū)的個(gè)數(shù)，S初值為0，表示緩沖區(qū)

23、為空，則甲、乙兩進(jìn)程的同步算法描述為甲進(jìn)程：i=0i=i+1<寫入第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ū)從未被寫入信息或緩沖區(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）先來先服務(wù)（2）輪轉(zhuǎn)法（3）短作業(yè)優(yōu)先（4）優(yōu)先級(jí)高者優(yōu)先（5）長作業(yè)優(yōu)先2、作業(yè)調(diào)度算法選擇作業(yè)的原則可以是保證系統(tǒng)吞吐量大、對(duì)用戶公平合理或者充分發(fā)揮系統(tǒng)資源的利

24、用率。下表給出了3種簡(jiǎn)單的作業(yè)調(diào)度算法： 調(diào)度算法吞吐量大公平合理發(fā)揮資源利用率先來先服務(wù)最短作業(yè)優(yōu)先？（1）請(qǐng)指出每種算法主要是體現(xiàn)了上述哪種原則。（在對(duì)應(yīng)的行列上打上記號(hào)）（2）如果在實(shí)際系統(tǒng)中只采用上述3種簡(jiǎn)單算法的任一種，都只能體現(xiàn)其中一種原則而其它原則得不到反映。為此，給出下列能反映多種原則的調(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)問這種算法反映了上述原則中的哪些原則？并簡(jiǎn)述理由。3、假設(shè)有4道作業(yè)，它們的提交時(shí)刻及運(yùn)行時(shí)間由下表給出：作業(yè)號(hào)提交時(shí)刻/小時(shí)執(zhí)行時(shí)間/小時(shí)110.00221

25、0.201310.400.5410.500.3計(jì)算在單道程序環(huán)境下，采用先來先服務(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è)四解答過程：1、適用于作業(yè)調(diào)度用的算法：（1）（3）（4）（5），適用于進(jìn)程調(diào)度用的算法：（1）（2）（4）。2、（1）調(diào)度算法吞吐量大公平合理發(fā)揮資源利用率先來先服務(wù)最短作業(yè)優(yōu)先（2）該算法體現(xiàn)了先來先服務(wù)原則和最短作業(yè)優(yōu)先原則。理由如下：體現(xiàn)先來先服務(wù)原則：假若兩作業(yè)運(yùn)行時(shí)間相同，但到達(dá)時(shí)間不同，早到達(dá)的作業(yè)等待時(shí)間長，根據(jù)公式計(jì)算，它的優(yōu)先數(shù)大，則優(yōu)先調(diào)度。體現(xiàn)最短作業(yè)優(yōu)先原則：假若兩道作業(yè)同

26、時(shí)到達(dá)，但運(yùn)行時(shí)間不等，根據(jù)公式計(jì)算，運(yùn)行時(shí)間短的作業(yè)其優(yōu)先數(shù)高，因而優(yōu)先調(diào)度。3、（1）先來先服務(wù)（FCFS）調(diào)度：調(diào)度順序?yàn)?234。作業(yè)號(hào)到達(dá)時(shí)間結(jié)束時(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)?432。作業(yè)號(hào)到達(dá)時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.0012.0021410.5012.301.8

27、06310.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)?432。響應(yīng)比=(作業(yè)執(zhí)行時(shí)間+作業(yè)等待時(shí)間)/作業(yè)執(zhí)行時(shí)間從下表可見，在作業(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í)間結(jié)束時(shí)間周

28、轉(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、假定某頁式虛擬系統(tǒng)中，頁面大小為100個(gè)單元，某作業(yè)占有實(shí)頁面數(shù)為M=3，它的訪問地址（走向）序列為75，175，66，267，32，102，333，166，22，255，256（數(shù)字為虛存的邏輯地址）。（1）請(qǐng)指出這些單元對(duì)應(yīng)的頁面訪問順序序列；（2）按先來先服務(wù)（FIFO）頁面淘汰算法求出缺頁率f，

29、并畫出圖表表示之；（3）按最近最久未使用（LRU）頁面置換算法求出缺頁率f，并畫出圖表表示之。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)問：（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ū)分給它，并畫出分配后的鏈接情況。作

30、業(yè)編號(hào)需主存量（K）運(yùn)行時(shí)間（s）1200221201310034501580363202作業(yè)五解答過程：1、（1）訪問序列為0，1，0，2，0，1，3，1，0，2，2。（2）FIFO：頁面0102013102210112223300020011122333300011222缺頁×××××缺頁率f=5/11=45.45%。（3）LRU：頁面0102013102210102013102220102013100311200311缺頁×××××缺頁率f=5/11=45.45%。2、（1）1秒后，主存空

31、白區(qū)按首次適應(yīng)和最佳適應(yīng)算法的鏈接方式：首次適應(yīng)算法：12050154最佳適應(yīng)算法：50120154（2）2秒后，主存空白區(qū)的鏈接方式：首次適應(yīng)算法：32050474最佳適應(yīng)算法：50320474（3）2秒后，作業(yè)7要求進(jìn)入主存：首次適應(yīng)算法：29050474最佳適應(yīng)算法：203204742001201005080320154（空閑）作業(yè)六：文件管理1、在UNIX系統(tǒng)中，為使文件的索引表較小又能允許組織大文件，采用直接索引與多次間接索引（多級(jí)索引）方式，給出一個(gè)文件的所有磁盤的塊號(hào)，如下圖。假設(shè)每個(gè)磁盤塊大小為1024字節(jié)，并且每個(gè)間接塊容納256個(gè)塊號(hào)，試問：（1）如某進(jìn)程要讀取某文件的字節(jié)

32、偏移量為9000處的數(shù)據(jù)，應(yīng)如何找到它所在的磁盤塊及塊內(nèi)位移量？（2）如想要存取350000處，又將如何？直接0367808數(shù)據(jù)塊4096直接1228直接245423直接3401直接4702直接511111直接610直接7101直接83333數(shù)據(jù)塊8163313333一次間址759156331二次間址0367直接990間接428間接9156間接8242、磁道（0-90道）的存取正在處理第55道的服務(wù)請(qǐng)求，對(duì)于磁盤訪問序列（磁道號(hào)）：22、77、35、90、40、83、66，試問對(duì)以下的磁盤I/O請(qǐng)求調(diào)度算法而言，滿足以上請(qǐng)求序列，磁頭將如何移動(dòng)，移動(dòng)距離為多少？若每移動(dòng)一個(gè)柱面需3ms，計(jì)算總共花費(fèi)的尋道時(shí)間。（1）先來先服務(wù)算法（FCFS）（2）最短查找時(shí)間優(yōu)先調(diào)度（SSTF）（3）掃描調(diào)度（SCAN）（電梯調(diào)度算法）（4）循環(huán)掃描（C-SCAN）算法3、如果磁道范圍0-99，剛結(jié)束第50道的服務(wù)請(qǐng)求，對(duì)于磁道序列70，25，40，85，90，55，分別按第2題（1）-（4）四種磁道掃描方法，磁頭將如何移動(dòng)？作業(yè)六解答過程：1、（1）根據(jù)9000/1024=8.8，故該字節(jié)在文件索引8（從0開始計(jì)）直接塊中，于是可從表目項(xiàng)中讀出內(nèi)容為367，即