操作系統(tǒng)期末復習

1、邏輯地址轉化物理地址過程,邏輯地址以十六進制數(shù)給出 根據(jù)頁大小劃分邏輯地址為頁號和頁內地址 以頁號查頁表，得到對應內存塊號 物理地址頁號拼接位移量 邏輯地址以十進制數(shù)給出 頁號虛地址/頁大小 位移量虛地址 mod 頁大小 以頁號查頁表，得到對應內存塊號 物理地址塊號頁大小位移量,例1,某虛擬存儲器的用戶編程空間共32個頁面，每頁為1KB，內存為16KB。假定某時刻一用戶頁表中已調入內存的頁面對應的物理塊號如下表：,則邏輯地址0A5C（H）所對應的物理地址為 ：_,例1,0A5CH0000,1010,0101,1100 B 頁號為2，對應塊號為4， 物理地址：0001，0010,0101,110

2、0 即：125CH,例2,設頁面大小為1K字節(jié)，作業(yè)的0、1、2頁分別存放在第2、3、8塊中。求邏輯地址2500對應的物理地址？ 則邏輯地址2500的頁號為2（2500/1024=2）頁內地址為452 （2500 %1024452）。 查頁表可知第2頁對應的物理塊號為8。 將塊號8與頁內地址452拼接（810244528644）得到物理地址為8644。,練習題,1.一分頁存儲管理系統(tǒng)中邏輯地址長度為16位，頁面大小為1KB字節(jié)，現(xiàn)有一邏輯地址為0A6FH ，且第0、1、2、3、頁依次存放在物理塊3、7、11、10中。邏輯地址0A6FH對應的物理地址是多少？ 邏輯地址0A6FH的二進制表示如下：

3、 頁號 頁內地址 0000，10 10，0110，1111 由此可知邏輯地址0A6FH的頁號為2，該頁存放在第11號物理塊中，用十六進制表示塊號為B， 所以物理地址為： 0010，1110，0110，1111 ，即2E6FH。,練習題,2.有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內存的第7、9、A、5塊，試將虛地址0AFEH，1ADDH轉換成內存地址。,虛地址0AFEH 0000 1010 1111 1110 P1 W010 1111 1110 PA00100 1010 1111 1110 4AFEH,虛地址1ADDH 0001 1010 1101 1101 P

4、3 W010 1101 1101 PA0010 1010 1101 1101 2ADDH,若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如右所示。已知頁面大小為1024字節(jié)，試將邏輯地址0A5CH，07EFH，3000，5012轉化為相應的物理地址。,對于邏輯地址0A5CH 0A5CH=0000 1010 0101 1100 頁號2，對應物理塊1 物理地址為0000 0110 0101 1100 即065CH 對于邏輯地址07EFH 0A5CH=0000 0111 1110 1111 頁號1，對應物理塊3 物理地址為0000 1111 1110 1111 即0FEFH 對于邏輯地址3000 Pint(

5、3000/1024)2 W3000 mod 1024952 查頁表第2頁在第1塊，所以物理地址為1976。 對于邏輯地址5012 Pint(5012/1024)4 W5012 mod 1024916 因頁號超過頁表長度，該邏輯地址非法。,習題解答,3 有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內存的第7、9、10、5塊，試將虛地址7145，3412轉換成內存地址。,虛地址 3412 P3412 2048 1 W 3412 mod 2048 1364 MR=9*2048+1364=19796 虛地址3412的內存地址 是：19796,虛地址 7145 P7145 2

6、048 3 W7145 mod 2048 1001 MR=5*2048+1001 =11241 虛地址7145的內存地址是：11241,4.5.2 分段系統(tǒng)的基本原理地址變換機構,地址變換過程： 進行地扯變換時，系統(tǒng)將邏輯地址中的段號S與段表長度進行比較，若段號超過了段表長度則產生越界中斷； 否則根據(jù)段表始址和段號計算出該段對應段表項的位置，從中讀出該段在內存的起始地址， 然后再檢查段內地址是否超過該段的段長，若超過則同樣發(fā)出越界中斷信號； 若未越界，則將該段的起始地址與段內位移相加，從而得到了要訪問的物理地址。,分段地址變換例,設作業(yè)分為3段，0、1、2段長度分別為1K、800、600，分別

7、存放在內存6K、4K、8K開始的內存區(qū)域。邏輯地址（2，100）的段號為2，段內位移為100。其物理地址是多少？ 查段表可知第2段在內存的起始地址8K。 將起始地址與段內位移相加，8K1008292，物理地址為8292。,例子： 給定段表如下，求下列對應的內存物理地址。 1、0,430 2、3,400 3、1,1 4、 2,500,在一個段式存儲管理系統(tǒng)中，其段表如左表所示，求右表邏輯地址對應的物理地址。,1.(1)由于第0段的內存始址為210，段長為500，故邏輯地址0,430是合法地址。邏輯地址0,430對應的物理地址為210430640 。 (2)由于第1段的內存始址為2350，段長為2

8、0，故邏輯地址1,10是合法地址。邏輯地址1,10對應的物理地址為2350+10=2360 。 (3)由于第2段起始地址為100，段長為90，所給邏輯地址2,500非法。 (4)由于第3段的內存始址為1350，段長為590，故邏輯地址3,400是合法地址。邏輯地址3,400對應的物理地址。,5.6.1 磁盤的結構和性能,5.6.1 磁盤的結構和性能,二、磁盤的類型 硬盤和軟盤、單片盤和多片盤、固定磁頭和活動磁頭。 1.固定頭磁盤： 每個磁道上有一個磁頭，并行讀寫，速度快 2.移動頭磁盤： 每個盤面僅有一個磁頭，要讀寫數(shù)據(jù)需要移動磁頭尋道。結構簡單、I/O速度慢 。 溫

9、徹斯特磁盤簡稱溫盤，是一種可移動磁頭固定盤片的磁盤存儲器，它是目前應用最廣，最有代表性的硬磁盤存儲器。,5.6.1 磁盤的結構和性能,三、磁盤訪問時間： 1.尋道時間：TS=m*n+S m：常量，n：磁道數(shù)，s：磁盤啟動時間。 2.旋轉延時間Tr： 指定扇區(qū)旋轉到磁頭下所需時間。 設每秒r轉，則Tr1/2r（均值） 3.數(shù)據(jù)傳輸時間Ttb/rN b：讀寫字節(jié)數(shù) N：每道上的字節(jié)數(shù) 訪問時間：Ta=Ts+Tr+Tt 可見，由于特定磁盤，只有集中放數(shù)據(jù)，集中讀寫（讀寫字節(jié)多）才能更好提高傳輸效率。,5.6.2 磁盤的調度算法,磁盤是典型的共享設備。在用戶處理的信息量越來越大的情況下，對磁盤等共享設

10、備的訪問也越來越頻繁，因而訪問調度是否得當直接影響到系統(tǒng)的效率。 磁盤調度的目標：減少尋道時間 有如下五種磁盤調度算法： 一、FCFS（Fisrt Come First Second） 二、SSTF（最短尋道優(yōu)先） 三、掃描算法。 四、循環(huán)掃描CSCAN 五、NStepSCAN和FSCAN算法。,圖 5-23 FCFS調度算法,1. 先來先服務FCFS(First-Come, First Served),僅用于請求磁盤I/O的進程數(shù)目較少的場合。,圖 5-24 SSTF調度算法,2. 最短尋道時間優(yōu)先SSTF(Shortest Seek Time First),要求訪問的磁道與當前磁頭距離最近

11、，使每次的尋道時間最短,SSTF算法雖然能獲得較好的尋道性能，卻可能導致某個進程發(fā)生“饑餓”(Starvation)現(xiàn)象。 Scan算法該算法不僅考慮到欲訪問的磁道與當前磁道間的距離，更優(yōu)先考慮磁頭當前的移動方向。 其原理是訪問的下一個對象應是同方向的，且又距離最近的。一般自里向外訪問，直至再無更外的磁道需要訪問，才將磁臂換向自外向里，往返反復。這種算法又稱為“電梯算法”,3. 掃描(SCAN)算法,SCAN調度算法,Cscan算法規(guī)定磁頭單項移動，進行循環(huán)掃描。一個方向讀完，不是象SCAN那樣回頭，而是循環(huán)。 訪問時間：2TT+Smax T是從外向里或從里向外單向掃描完要訪問的磁道的尋道時間

12、。 而Smax是將磁頭從最外面被訪問的磁道直接移到最里面欲訪問的磁道的尋道時間。,4. 循環(huán)掃描(CSCAN)算法,CSCAN調度算法,若某磁盤共有200個柱面，其編號為0199，假設已完成96號柱面的訪問請求，還有若干個請求者在等待服務，它們依次要訪問的柱面號為：175，52，157，36，159、106，l08，72，分別用先來先服務調度算法、最短尋道時間調度算法、電梯調度算法和單向掃描調度算法（向序號增加的方向移動）來確定實際服務的次序，并計算上述兩種算法下移動臂需移動的距離。,(1)先來先服務調度算法： 實際服務的次序： 96175521573615910610872 移動臂需移動的距

13、離為： (175-96)+(175-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642 移動臂需移動642柱面的距離。 (2)最短尋找時間優(yōu)先調度算法： 實際服務的次序：96106108725236157159175 移動臂需移動的距離為： (106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159-l57)+(175-159)=223 移動臂需移動223個柱面的距離。,(1)電梯調度算法： 實際服務的次序：96106108157159175725236 (106

14、-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-72)+(72-52)+(52-36)=218 移動臂需移動218個柱面的距離。 (2)單向掃描調度算法： 實際服務的次序：96106108157159175365272 (106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-36)+(52-36)+(72-52)=254 除了移動臂由里向外返回所用的時間外，還需移動254個柱面的距離。,4.8.1 最佳置換算法和先進先出算法,二、FIFO 淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的

15、頁面予以淘汰。 出發(fā)點：最早調入主存中的頁面不再使用的可能性越大，應該最先淘汰。算法簡單對具有按線性順序訪問的程序比較合適，而對其它情況效率不高,4.8.1 最佳置換算法和先進先出算法,進程P執(zhí)行時的頁面走向為：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在內存中分配3個頁面，則缺頁情況如下：12次訪問中有缺頁9次；,如果在內存中分配4個頁面，則缺頁情況如下：12次訪問中有缺頁10次；,Belady現(xiàn)象的原因：FIFO算法的置換特征與進程訪問內存的動態(tài)特征是矛盾的，即被置換的頁面并不是進程不會訪問的。,習題,1某進程執(zhí)行時的頁面走向為1 2 3 4 1 2 5

16、1 2 3 4 5，分別畫出其分配物理塊為3的最佳置換算法的置換圖。 2某進程執(zhí)行時的頁面走向為1 2 3 4 1 2 5 1 2 3 4 5，分別畫出其分配物理塊為3和4的FIFO算法的置換圖。 3在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：3 4 2 1 4 3 1 4 3 1 4 5，采用LRU置換算法求出訪問過程中發(fā)生的缺頁中斷的次數(shù)及缺頁率。設分給作業(yè)的存儲塊數(shù)為3.,4在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：2 3 2 1 5 2 4 5 3 2 5 2，設分給作業(yè)的存儲塊數(shù)為3。若用最佳置換算法，先進先出，LRU置換算法求出訪問過程中發(fā)生的缺頁次數(shù)及缺頁率。,習題

17、,1某進程執(zhí)行時的頁面走向為1 2 3 4 1 2 5 1 2 3 4 5，分別畫出其分配物理塊為3的最佳置換算法的置換圖。,習題,2某進程執(zhí)行時的頁面走向為1 2 3 4 1 2 5 1 2 3 4 5，分別畫出其分配物理塊為3和4的FIFO算法的置換圖。,習題,3在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：3 4 2 1 4 3 1 4 3 1 4 5，采用LRU置換算法求出訪問過程中發(fā)生的缺頁中斷的次數(shù)及缺頁率。設分給作業(yè)的存儲塊數(shù)為3.,4在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：2 3 2 1 5 2 4 5 3 2 5 2，設分給作業(yè)的存儲塊數(shù)為3。若用最佳置換算法，

18、先進先出，LRU置換算法求出訪問過程中發(fā)生的缺頁次數(shù)及缺頁率。,請求分頁存儲管理方式中，假定系統(tǒng)為某進程分配了4個頁框，頁面的引用順序為：6、1、2、0、3、0、4、2、3、0、3、2、6、0，采用FIFO置換算法產生多少次頁面置換？缺頁率是多少？,(2)頁面置換次數(shù)為3次 (3)缺頁率為：7/14=50%,請求分頁存儲管理方式中，假設分配給某進程的頁框數(shù)為3，若程序的頁面引用順序為：0、2、3、4、1、2、5、0、2、3、2、5，采用最佳置換算法產生多少次頁面置換？缺頁率是多少？,(2)頁面置換次數(shù)為4次 (3)缺頁率為：7/12=58%,二、銀行家算法 避免死鎖算法中最有代表性的算法是Di

19、jkstra E.W 于1968年提出的銀行家算法： 該算法需要檢查申請者對資源的最大需求量，如果系統(tǒng)現(xiàn)存的各類資源可以滿足申請者的請求，就滿足申請者的請求。 這樣申請者就可很快完成其計算，然后釋放它占用的資源，從而保證了系統(tǒng)中的所有進程都能完成，所以可避免死鎖的發(fā)生。,3.6.2 避免死鎖,3.6.3利用銀行家算法避免死鎖,1數(shù)據(jù)結構 可利用資源向量available 其初值是系統(tǒng)中該類資源的最大可用數(shù)目，其值將隨著該類資源的分配與回收而動態(tài)改變。 availablej=k: 系統(tǒng)現(xiàn)有Rj類資源k個； 最大需求矩陣Max 是一個nm的矩陣，定義了系統(tǒng)中的n個進程中的每一個進程對m類資源的最大

20、需求量。 maxi,j=k: 進程i需要Rj的最大數(shù)k個；,3.6.3利用銀行家算法避免死鎖,分配矩陣Allocation 是一個nm的矩陣，定義了系統(tǒng)中每一類資源的數(shù)量。allocationi,j=k: 進程i已得到Rj類資源k個； 需求矩陣Need 是一個nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)。 needi,j=k:進程i還需Rj類資源k個，方能完成任務。 有：needi,j= maxi,jallocationi,j requesti進程i請求資源數(shù),3.6.3利用銀行家算法避免死鎖,2銀行家算法,當進程Pi 向系統(tǒng)提出申請類資源請求時，系統(tǒng)按下列步驟檢查： 若RequestijN

21、eedi,j,出錯處理。 否則，轉向下一步。 若RequestijAvailablei,j出錯處理。 否則,轉向下一步。,N,N,N,Y,Y,3.6.3利用銀行家算法避免死鎖, 系統(tǒng)試著把資源分給進程Pi，并修改下列數(shù)值。 Availj=Availj-Reqi j ; Alloi,jAlloi,j+ Reqij; Needi,j= Needi,jReqij ; 執(zhí)行安全性算法,檢查這次資源分配后，系統(tǒng)是否處于安全狀態(tài). 如果安全，則正式將資源分配給Pi，否則恢復原來的資源分配狀態(tài)，然進程Pi等待。,安全性算法,設置兩個工作向量 設置一個臨時向量work：表示系統(tǒng)可提供給進程繼續(xù)運行的資源的集合

22、。安全性算法剛開始執(zhí)行時，work:Available。 設置一個數(shù)組finishi：表示進程i能否順序完成。當finishiTrue，表示進程Pi可以獲得其所需的全部資源，而順利執(zhí)行完成。,安全性算法,從進程集合中找到一個能滿足下述條件的進程： A Finishi= false; B Needi,j workj； 若找到，執(zhí)行3步驟，否則執(zhí)行4步驟 進程Pi獲得資源，可順利執(zhí)行直至完成，然后釋放它的全部資源。執(zhí)行： Workj=workj+Allocationi,j; Finishi=True; Goto 2 如果所有進程的Finishi=true,則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)。,

23、4實例,T0時刻的資源分配表,5 3 2,7 4 3,7 4 5,7 5 5,10 5 7,WORK,4實例,T0時刻的安全序列,4實例,5 3 2,7 4 3,7 4 5,7 5 5,10 5 7,P1申請資源(1,0,2)時安全性檢查(安全),WORK,4實例,P1申請資源(1,0,2)時安全性檢查(安全),4實例,若此時P4請求資源，Request4（3，3，0），系統(tǒng)按照銀行家算法進行檢查： Request4（3，3，0） Available（2，3，0） 故P4需要等待 若此時P0請求資源，Request0（0，2，0），系統(tǒng)按照銀行家算法進行檢查： Request0（0，2，0）

24、Need4（7，4，3）， Request0（0，2，0） Available（2，3，0） 故系統(tǒng)暫定能為P0分配資源，修改有關數(shù)據(jù)。,4實例,為P0分配（0，2，0）后的情況（不安全）,3.3調度算法是一個資源分配問題,1.FCFS 非剝奪式的調度算法。 以等待時間為主要的調度指標 總是選擇就緒隊列的隊首作業(yè)運行 是一種最簡單的調度算法，既可用于作業(yè)調度，也可用于進程調度 優(yōu)點:實現(xiàn)簡單，容易實現(xiàn) 缺點:沒考慮進程的優(yōu)先級,3.3.1先來先服務和短作業(yè)（進程）優(yōu)先調度算法,例:FCFS算法,3.3調度算法是一個資源分配問題,剝奪或非剝奪式的調度算法。 以要求服務時間為主要的調度指標 總是選擇執(zhí)行時間最短的作業(yè)運行；進程運行時間不易確定，通常采用近似估算方法。,2.短作業(yè)進程優(yōu)先調度算法：SJ(P)F,3.3調度算法是一個資源分配問題,優(yōu)點：有效地降低作業(yè)的平均等待時間，縮短平均周轉時間和平均帶權周轉時間（從而提高了系統(tǒng)吞吐量） 缺點： 不利于長作業(yè)，會出現(xiàn)餓死現(xiàn)象。 未考慮緊迫程度，不能保證緊迫性作業(yè)(進程)會被及時處理。 該算法不一定能真正做到短作業(yè)優(yōu)先調度。作業(yè)(進程)的長短只是根據(jù)用戶所估計的近似值。,2.短作業(yè)進程優(yōu)先調度算法：SJ(P)F,FCFS與SJF調度算法,1.FCFS算法 FCFS以等待時間為調度指標，優(yōu)先考慮等待時間最長的作業(yè)