1、操作系統課程作業（2013年春）姓名：學號：專業：年級：學校：日期：作業一：作業管理1、 有三道程序A、B、C在一個系統中運行，該系統有輸入、輸出設備各1臺。三道程序A、B、C構成如下：A：輸入32秒，計算8秒，輸出5秒B：輸入21秒，計算14秒，輸出35秒C：輸入12秒，計算32秒，輸出15秒問：（1）三道程序順序執行的總時間是多少？（2）充分發揮各設備的效能，并行執行上述三道程序，最短需多少時間（不計系統開銷）？并給出相應的示意圖。2、 假設一個單CPU系統，以單道方式處理一個作業流，作業流中有2道作業，共占用CPU計算時間、輸入卡片數和打印輸出行數如下：作業號占用CPU計算時間輸入卡片張

2、數打印輸出行數13分鐘100張2000行22分鐘200張600行其中，卡片輸入機速度為1000張/分鐘，打印機輸出速度為1000行/分鐘，試計算：（1） 不采用spooling技術，計算這兩道作業的總運行時間（從第1道作業輸入開始到最后一個作業輸出完畢）。（2） 如采用spooling技術，計算這2道作業的總運行時間（不計讀/寫盤時間），并給出相應的示意圖。作業二：進程管理1、 請寫出兩程序S1和S2可并發執行的Bernstein條件。2、 有以下5條語句，請畫出這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、 設在教材第62頁3.6.4節中所描述的生產者消費者問題中，其緩沖部分為m個長度相等的有界緩沖區組成，且每次傳輸數據長度等于有界緩沖區長度以及生產者和消費者可對緩沖區同時操作。重新描述發送過程deposit(data)和接收過程remove(data)。4、 設有k個進程共享一臨界區，對于下述情況，請說明信號量的初值、含義，并用P，V操作寫出有關互斥算法。（1） 一次只允許一個進程進入臨界區；（2） 一次允許m（m<k）個進程進入臨界區。作業三：進程管理1、 假若一個街道交通如下圖所示，若有一長度大于兩個路口距離的車，可

4、以從東南西北四個方向開來，問（1）何時會發生死鎖？（2）請提出一種可預防死鎖發生的簡單方法。2、 某超市市場科容納100人同時購物，入口處備有籃子，每個購物者可取1只籃子入內購物，出口處結賬并歸還籃子（出、入口僅容1人通過）。請試用P，V操作及信號量寫出如下情況的購物同步算法：（1）1個出入口，且一次只允許1人通過；（2）1個入口，n個出口（n1且為整數）。3、設有無窮多個緩沖區和無窮多個信息，甲進程把信息逐個寫入每個緩沖區，乙進程則逐個地從緩沖區中取出信息。試問：（1）兩個進程間的制約關系；（2）用P，V操作寫出兩個進程的同步算法，并給出信號量的初值；（3）指出信號量的值的變化范圍及取值的含

5、義。作業四：作業、進程調度1、下面哪幾種調度算法適合于作業調度，哪些適合進程調度？（1）先來先服務（2）輪轉法（3）短作業優先（4）優先級高者優先（5）長作業優先2、作業調度算法選擇作業的原則可以是保證系統吞吐量大、對用戶公平合理或者充分發揮系統資源的利用率。通常情況下，采用簡單算法只能體現其中一種原則而其它原則得不到反映。為此，給出下列能反映多種原則的調度算法，并假定完全根據優先數從高到低順序挑選作業，作業優先數按下述公式計算：R(優先數)=(作業等待時間)2+1/(作業要求運行時間)請問這種算法反映了上述原則中的哪些原則？并簡述理由。3、假設有4道作業，它們的提交時刻及運行時間由下表給出：

6、作業號提交時刻/小時執行時間/小時110.002210.201310.400.5410.500.3計算在單道程序環境下，采用先來先服務調度算法、最短作業優先調度算法和最高響應比優先調度算法時的平均周轉時間和平均帶權周轉時間，并指出他們的調度順序。作業五：存儲管理1、假定某頁式虛擬系統中，頁面大小為100個單元，某作業占有實頁面數為M=3，它的訪問地址（走向）序列為75，175，66，267，32，102，333，166，22，255，256（數字為虛存的邏輯地址）。（1）請指出這些單元對應的頁面訪問順序序列；（2）按先來先服務（FIFO）頁面淘汰算法求出缺頁率f，并畫出圖表表示之；（3）按最近

7、最久未使用（LRU）頁面置換算法求出缺頁率f，并畫出圖表表示之。2、有系統其主存容量為1024K（字節），有6個作業同時到達，各作業要求主存量和運行時間如下表所示。假定系統初啟時，將主存1024K按作業的編號順序分給各道作業，并假定是多CPU下，分配到主存的作業都可以立即運行。請問：（1）1秒后，主存空白區按首次適應和最佳適應算法的鏈接方式鏈接，將如何鏈接？（2）2秒后，主存空白區按首次適應和最佳適應算法的鏈接方式鏈接，將如何鏈接？（3）在（2）后，此時有一個作業7要求進入主存，它需要主存量為30K，按上述兩種算法應把那一塊空白區分給它，并畫出分配后的鏈接情況。作業編號需主存量（K）運行時間（

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

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

10、C在一個系統中運行，該系統有輸入、輸出設備各1臺。三道程序A、B、C構成如下：A：輸入32秒，計算8秒，輸出5秒B：輸入21秒，計算14秒，輸出35秒C：輸入12秒，計算32秒，輸出15秒問：（1）三道程序順序執行的總時間是多少？（2）充分發揮各設備的效能，并行執行上述三道程序，最短需多少時間（不計系統開銷）？并給出相應的示意圖。4、 假設一個單CPU系統，以單道方式處理一個作業流，作業流中有2道作業，共占用CPU計算時間、輸入卡片數和打印輸出行數如下：作業號占用CPU計算時間輸入卡片張數打印輸出行數13分鐘100張2000行22分鐘200張600行其中，卡片輸入機速度為1000張/分鐘，打印

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

12、s，按BAC執行需112s，按BCA執行需90s，按CAB執行 114s，按CBA執行需99s。2、（1）不采用spooling技術，計算這兩道作業的總運行時間為：100/1000（輸入）+3（執行）+2000/1000（輸出）+200/1000+2+600/1000=7.9分鐘5.3時間（分）7.9輸入計算輸出輸入計算輸出程序2程序10.13.15.17.3（2）采用spooling技術，這2道作業的總運行時間為5.7分鐘。0.2時間（分）輸入計算輸出輸入計算輸出程序2程序10.13.15.15.7作業二：進程管理5、 請寫出兩程序S1和S2可并發執行的Bernstein條件。6、 有以下5

13、條語句，請畫出這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、 設在教材第62頁3.6.4節中所描述的生產者消費者問題中，其緩沖部分為m個長度相等的有界緩沖區組成，且每次傳輸數據長度等于有界緩沖區長度以及生產者和消費者可對緩沖區同時操作。重新描述發送過程deposit(data)和接收過程remove(data)。8、 設有k個進程共享一臨界區，對于下述情況，請說明信號量的初值、含義，并用P，V操作寫出有關互斥算法。（1） 一次只允許一個進程進

14、入臨界區；（2） 一次允許m（m<k）個進程進入臨界區。作業二解答過程：1、Bernstein條件（可并發執行的條件）：設R(Si)=a1,a2,am表示程序Si在執行期間所需要引用（讀）變量的集合-讀集 W(Si)= b1,b2,bn表示程序Si在執行期間要改變（寫）變量的集合-寫集 如果兩個程序S1和S2能同時滿足下述條件，它們便能并發執行，否則不能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、設第i塊緩沖區的公用信號量為bufi，初值為1；生

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

16、s)<進入臨界區>V(s)信號量s的變化范圍為-(k-1) ,-1,0,1。其中，s=1表示有1個空閑且可用的臨界資源，且沒有進程進入類名為s的臨界區；s=0表示有1個進程在臨界區中（該臨界資源已被某進程占用），但無等待使用該臨界資源的進程；s=-n(1nk-1，n為整數)表示有1個進程在臨界區中，且有n個進程等待使用該臨界資源。（2）一次允許m（m<k）個進程進入臨界區：設s為互斥信號量，初值為m，表示有m個空閑且可用的共享臨界資源，即可允許m個進程同時進入該臨界區對任一進程Pi（1ik）：P(s)<進入臨界區>V(s)信號量s的變化范圍為-(k-m) ,-1,

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

18、/4、 某超市市場科容納100人同時購物，入口處備有籃子，每個購物者可取1只籃子入內購物，出口處結賬并歸還籃子（出、入口僅容1人通過）。請試用P，V操作及信號量寫出如下情況的購物同步算法：（1）1個出入口，且一次只允許1人通過；（2）1個入口，n個出口（n1且為整數）。3、設有無窮多個緩沖區和無窮多個信息，甲進程把信息逐個寫入每個緩沖區，乙進程則逐個地從緩沖區中取出信息。試問：（1）兩個進程間的制約關系；（2）用P，V操作寫出兩個進程的同步算法，并給出信號量的初值；（3）指出信號量的值的變化范圍及取值的含義。作業三解答過程：1、（1）何時會發生死鎖？北（2）請提出一種可預防死鎖發生的簡單方法北

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

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

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

22、00；入口互斥信號量為mutex1，初值為1；出口互斥信號量為mutex2，初值為n。購物進程Pi同步描述：P（S）P（mutex1）<進入超市并取1只籃子>V（mutex1） <選購商品>P（mutex2）<結賬并歸還籃子>V（mutex2）V（S）信號量S的變化范圍為-m ,-1,0,1 ,100（m為正整數）。其中，；信號量mutex1和mutex2的變化范圍均為-99 ,-1,0,1 。其中，3、（1）兩個進程間的制約關系：乙進程不能先于甲進程執行，而甲進程不受乙進程約束。（2）設置1個信號量S，S表示甲進程寫滿的緩沖區的個數，S初值為0，表示緩沖區

23、為空，則甲、乙兩進程的同步算法描述為甲進程：i=0i=i+1<寫入第i個緩沖區>V（S）乙進程：j=0j=j+1P（S）<讀出第j個緩沖區>（3）信號量S的變化范圍為-1,+中的整數，當S=-1時表示緩沖區從未被寫入信息或緩沖區信息被乙進程讀空，且乙進程要求進一步讀緩沖區中的信息，即乙進程超前甲進程欲讀取緩沖區的信息而受阻。作業四：作業、進程調度1、下面哪幾種調度算法適合于作業調度，哪些適合進程調度？（1）先來先服務（2）輪轉法（3）短作業優先（4）優先級高者優先（5）長作業優先2、作業調度算法選擇作業的原則可以是保證系統吞吐量大、對用戶公平合理或者充分發揮系統資源的利

24、用率。下表給出了3種簡單的作業調度算法： 調度算法吞吐量大公平合理發揮資源利用率先來先服務最短作業優先？（1）請指出每種算法主要是體現了上述哪種原則。（在對應的行列上打上記號）（2）如果在實際系統中只采用上述3種簡單算法的任一種，都只能體現其中一種原則而其它原則得不到反映。為此，給出下列能反映多種原則的調度算法，并假定完全根據優先數從高到低順序挑選作業，作業優先數按下述公式計算：R(優先數)=(作業等待時間)2+1/(作業要求運行時間)請問這種算法反映了上述原則中的哪些原則？并簡述理由。3、假設有4道作業，它們的提交時刻及運行時間由下表給出：作業號提交時刻/小時執行時間/小時110.00221

25、0.201310.400.5410.500.3計算在單道程序環境下，采用先來先服務調度算法、最短作業優先調度算法和最高響應比優先調度算法時的平均周轉時間和平均帶權周轉時間，并指出他們的調度順序。作業四解答過程：1、適用于作業調度用的算法：（1）（3）（4）（5），適用于進程調度用的算法：（1）（2）（4）。2、（1）調度算法吞吐量大公平合理發揮資源利用率先來先服務最短作業優先（2）該算法體現了先來先服務原則和最短作業優先原則。理由如下：體現先來先服務原則：假若兩作業運行時間相同，但到達時間不同，早到達的作業等待時間長，根據公式計算，它的優先數大，則優先調度。體現最短作業優先原則：假若兩道作業同

26、時到達，但運行時間不等，根據公式計算，運行時間短的作業其優先數高，因而優先調度。3、（1）先來先服務（FCFS）調度：調度順序為1234。作業號到達時間結束時間周轉時間帶權周轉時間110.0012.0021.00210.2013.002.82.80310.4013.503.16.20410.5013.803.311.00平均周轉時間T=(2+2.8+3.1+3.3)/4=2.8小時平均帶權周轉時間W=(1+2.8+6.2+11)/4=5.25小時（2）最短作業優先（SJF）調度：調度順序為1432。作業號到達時間結束時間周轉時間帶權周轉時間110.0012.0021410.5012.301.8

27、06310.4012.802.404.8210.2013.803.603.6平均周轉時間T=(2+1.8+2.4+3.6)/4=2.45小時平均帶權周轉時間W=(1+6+4.8+3.6)/4=3.85小時 （3）最高響應比優先（HRN）調度：調度順序為1432。響應比=(作業執行時間+作業等待時間)/作業執行時間從下表可見，在作業1完成時刻（12.00），作業2、3、4的響應比最高的為4；在作業4完成時刻（12.30），作業2、3的響應比最高的為3。作業號等待時間執行時間響應比21.8012.831.600.54.241.500.3622.113.131.90.54.8作業號到達時間結束時間周

28、轉時間帶權周轉時間110.0012.0021410.5012.301.806310.4012.802.404.8210.2013.803.603.6平均周轉時間T=(2+1.8+2.4+3.6)/4=2.45小時平均帶權周轉時間W=(1+6+4.8+3.6)/4=3.85小時作業五：存儲管理1、假定某頁式虛擬系統中，頁面大小為100個單元，某作業占有實頁面數為M=3，它的訪問地址（走向）序列為75，175，66，267，32，102，333，166，22，255，256（數字為虛存的邏輯地址）。（1）請指出這些單元對應的頁面訪問順序序列；（2）按先來先服務（FIFO）頁面淘汰算法求出缺頁率f，

29、并畫出圖表表示之；（3）按最近最久未使用（LRU）頁面置換算法求出缺頁率f，并畫出圖表表示之。2、有系統其主存容量為1024K（字節），有6個作業同時到達，各作業要求主存量和運行時間如下表所示。假定系統初啟時，將主存1024K按作業的編號順序分給各道作業，并假定是多CPU下，分配到主存的作業都可以立即運行。請問：（1）1秒后，主存空白區按首次適應和最佳適應算法的鏈接方式鏈接，將如何鏈接？（2）2秒后，主存空白區按首次適應和最佳適應算法的鏈接方式鏈接，將如何鏈接？（3）在（2）后，此時有一個作業7要求進入主存，它需要主存量為30K，按上述兩種算法應把那一塊空白區分給它，并畫出分配后的鏈接情況。作

30、業編號需主存量（K）運行時間（s）1200221201310034501580363202作業五解答過程：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、白區按首次適應和最佳適應算法的鏈接方式：首次適應算法：12050154最佳適應算法：50120154（2）2秒后，主存空白區的鏈接方式：首次適應算法：32050474最佳適應算法：50320474（3）2秒后，作業7要求進入主存：首次適應算法：29050474最佳適應算法：203204742001201005080320154（空閑）作業六：文件管理1、在UNIX系統中，為使文件的索引表較小又能允許組織大文件，采用直接索引與多次間接索引（多級索引）方式，給出一個文件的所有磁盤的塊號，如下圖。假設每個磁盤塊大小為1024字節，并且每個間接塊容納256個塊號，試問：（1）如某進程要讀取某文件的字節

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