邏輯地址以十六進制數(shù)給出邏輯地址以十六進制數(shù)給出根據(jù)頁大小劃分邏輯地址為頁號和根據(jù)頁大小劃分邏輯地址為頁號和頁內地址頁內地址以頁號查頁表以頁號查頁表，，得到對應內存塊號得到對應內存塊號物理地址＝頁號物理地址＝頁號拼接拼接位移量位移量邏輯地址以十進制數(shù)給出邏輯地址以十進制數(shù)給出頁號＝虛地址頁號＝虛地址//頁大小頁大小位移量＝虛地址位移量＝虛地址頁大小頁大小以頁號查頁表以頁號查頁表，，得到對應內存塊號得到對應內存塊號物理地址＝塊號物理地址＝塊號頁大小＋位移量頁大小＋位移量某虛擬存儲器的用戶編程空間共某虛擬存儲器的用戶編程空間共3232個頁面?zhèn)€頁面，，每頁為每頁為，，內存為內存為。。假定某時刻一用戶假定某時刻一用戶頁表中已調入內存的頁面對應的物理塊號如頁表中已調入內存的頁面對應的物理塊號如下表：下表：頁號物理塊號頁號為2，對應塊號為4，物理地址：0001，0010,0101,1100即：125CH頁號物理塊設頁面大小為設頁面大小為11KK字節(jié)字節(jié)，，作業(yè)的作業(yè)的00、、11、、22頁頁分別存放在第分別存放在第22、、33、、88塊中塊中。。求邏輯地址求邏輯地址對應的物理地址對應的物理地址？？則邏輯地址則邏輯地址的頁號為的頁號為22（（//==22））頁內地址為頁內地址為（（%＝＝））。
。查頁表可知第查頁表可知第22頁對應的物理塊號為頁對應的物理塊號為88。。將塊號88與頁內地址與頁內地址拼接拼接（（＋＋＝＝））得到物理地址為得到物理地址為。。練習題11..一分頁存儲管理系統(tǒng)中邏輯地址長度為一分頁存儲管理系統(tǒng)中邏輯地址長度為1616位位，，頁面頁面大小為大小為字節(jié)字節(jié)，，現(xiàn)有一邏輯地址為現(xiàn)有一邏輯地址為且第00、、11、、22、、33、、頁依次存放在物理塊頁依次存放在物理塊33、、77、、1111、、1010中中。。邏邏輯地址輯地址對應的物理地址是多少對應的物理地址是多少？邏輯地址邏輯地址的二進制表示如下：的二進制表示如下：頁號頁號頁內地址頁內地址，，，，，，––由此可知邏輯地址由此可知邏輯地址的頁號為的頁號為22，，該頁存放在第該頁存放在第1111號物理塊中，，用十六進制表示塊號為用十六進制表示塊號為BB，，––所以物理地址為：所以物理地址為：，，，，，，，，即即練習題22..有一系統(tǒng)采用頁式存儲管有一系統(tǒng)采用頁式存儲管理理，，有一作業(yè)大小是有一作業(yè)大小是，，頁大小為頁大小為，，依次裝入內依次裝入內存的第77、、99、、AA、、55塊塊，，試將虛地址虛地址，，轉換成轉換成內存地址內存地址。
。虛地址＝PA＝＝4AFEH虛地址＝PA＝11101＝2ADDH若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如右所示。已知頁面大小為1024字節(jié)，試將邏輯地址0A5CH，07EFH，3000，5012轉化為相應的物理地0A5CH=11100頁號2，對應物理塊1物理地址為11100即=01111頁號1，對應物理塊3物理地址為01111即＝＝952W＝＝916習題解答33有一系統(tǒng)采用頁式存儲管理有一系統(tǒng)采用頁式存儲管理，，有一作業(yè)大小有一作業(yè)大小是是，，頁大小為頁大小為，，依次裝入內存的第依次裝入內存的第77、、99、、1010、、55塊塊，，試將虛地址試將虛地址，，轉換成轉換成內存地址內存地址。
。虛地址3412P＝3412％2048W＝＝=9*2048+1364=19796虛地址3412的內存地址是：19796虛地址虛地址＝＝72048＝＝33WW＝＝48＝＝=MR=55**++==虛地址虛地址的內存地址是：的內存地址是：04.5.2分段系統(tǒng)的基本原理－地址變換機構地址變換過程：地址變換過程：進行地扯變換時進行地扯變換時，，系統(tǒng)將邏輯地址中的段號系統(tǒng)將邏輯地址中的段號SS與段表長度進行與段表長度進行比較比較，，若段號超過了段表長度若段號超過了段表長度則產生則產生越界中斷越界中斷；；否則根據(jù)段表始址和段號計算出該段對應否則根據(jù)段表始址和段號計算出該段對應段表項的位置項的位置，，從中讀出從中讀出該段在內存的起始地址該段在內存的起始地址，，然后再檢查段內地址是否超過該段的段長然后再檢查段內地址是否超過該段的段長，，若若超過則同樣發(fā)出超過則同樣發(fā)出越界中斷越界中斷信號信號；；若未越界若未越界，，則將該段的起始地址與段內位移則將該段的起始地址與段內位移相相加加，，從而得到了要訪問的物理地址從而得到了要訪問的物理地址。
。11100段表寄存器邏輯地址越界中斷0段長基址8292物理地址分段系統(tǒng)地址變換機構12分段地址變換例設作業(yè)分為設作業(yè)分為33段段，，00、、11、、22段長度分別為段長度分別為11KK、、、、，，分別存放在內存分別存放在內存66KK、、44KK、、88KK開開始的內存區(qū)域始的內存區(qū)域。。邏輯地址邏輯地址（（22，，））的段號為號為22，，段內位移為段內位移為。。其物理地址是多其物理地址是多少少？？查段表可知第查段表可知第22段在內存的起始地址段在內存的起始地址88KK。。 將起始地址與段內位移相加將起始地址與段內位移相加，，88KK＋＋100 100＝＝ 8292 8292，，物理地址為 物理地址為8292 8292。。 13 例子： 例子： 給定段表如下，求下列對應的內存物理地址。 給定段表如下，求下列對應的內存物理地址。 11、 、[0,430] [3,400]3、、[1,1] [2,500][2,500] 段長段長 00 219 219 600 600 11 2300 2300 14 14 22 90 90 100 100 33 1327 1327 580 580 14 在一個段式存儲管理系統(tǒng)中，其段表如左表所示，求右表邏輯地址對應的物理地址。
15 1.(1)由于第0段的內存始址為210，段長為500，故邏輯地址[0,430]是合法地址。邏輯地址[0,430]對應的物理地址為 210＋430＝640 (2)由于第1段的內存始址為2350，段長為20，故邏輯地址[1,10]是合法地址。邏輯地址[1,10]對應的物理地址為 2350+10=2360 (3)由于第2段起始地址為100，段長為90，所給邏輯地址[2,500]非法。 (4)由于第3段的內存始址為1350，段長為590，故邏輯地址[3,400]是合法地址。邏輯地址[3,400]對應的物理地址為 1350＋400＝1750 165.6.1 磁盤的結構和性能 17 5.6.1 磁盤的結構和性能 二、磁盤的類型 二、磁盤的類型 硬盤和軟盤、單片盤和多片盤、固定磁頭和活動磁頭。 硬盤和軟盤、單片盤和多片盤、固定磁頭和活動磁頭。 1.固定頭磁盤：固定頭磁盤： 每個磁道上有一個磁頭，并行讀寫，速度快每個磁道上有一個磁頭，并行讀寫，速度快 2.移動頭磁盤：移動頭磁盤： 每個盤面僅有一個磁頭，要讀寫數(shù)據(jù)需要移動磁每個盤面僅有一個磁頭，要讀寫數(shù)據(jù)需要移動磁 頭頭——尋道。結構簡單、 尋道。
結構簡單、I/O I/O速度慢 速度慢 溫徹斯特磁盤簡稱溫盤，是一種可移動磁頭固定溫徹斯特磁盤簡稱溫盤，是一種可移動磁頭固定 盤片的磁盤存儲器，它是目前應用最廣，最有代 盤片的磁盤存儲器，它是目前應用最廣，最有代 表性的硬磁盤存儲器。 表性的硬磁盤存儲器。 18 5.6.1 磁盤的結構和性能 三、磁盤訪問時間： 三、磁盤訪問時間： 1.尋道時間尋道時間：：TS=m*n+S TS=m*n+S mm：常量， ：常量，nn：磁道數(shù)， ：磁道數(shù)，ss：磁盤啟動時間。 ：磁盤啟動時間。 2.旋轉延時間旋轉延時間Tr Tr：： 指定扇區(qū)旋轉到磁頭下所需時間。 指定扇區(qū)旋轉到磁頭下所需時間。 設每秒 設每秒rr轉，則 轉，則Tr Tr＝＝1/2r 1/2r（均值） （均值） 3.數(shù)據(jù)傳輸時間數(shù)據(jù)傳輸時間Tt Tt＝＝b/rN b/rN bb：讀寫字節(jié)數(shù) ：讀寫字節(jié)數(shù) NN：每道上的字節(jié)數(shù) ：每道上的字節(jié)數(shù) 訪問時間： 訪問時間：Ta=Ts+Tr+Tt Ta=Ts+Tr+Tt 可見，由于特定磁盤，只有集中放數(shù)據(jù)，集中讀寫 可見，由于特定磁盤，只有集中放數(shù)據(jù)，集中讀寫 （讀寫字節(jié)多）才能更好提高傳輸效率。
（讀寫字節(jié)多）才能更好提高傳輸效率。 19 5.6.2 磁盤的調度算法 磁盤是典型的共享設備。在用戶處理的信息量越來越磁盤是典型的共享設備。在用戶處理的信息量越來越 大的情況下，對磁盤等共享設備的訪問也越來越頻繁， 大的情況下，對磁盤等共享設備的訪問也越來越頻繁， 因而訪問調度是否得當直接影響到系統(tǒng)的效率。 因而訪問調度是否得當直接影響到系統(tǒng)的效率。 磁盤調度的目標：減少尋道時間磁盤調度的目標：減少尋道時間 有如下五種磁盤調度算法： 有如下五種磁盤調度算法： 一、（（Fisrt Come First Fisrt Come First ）） 二、（最短尋道優(yōu)先） （最短尋道優(yōu)先） 三、掃描算法。 三、掃描算法。 四、循環(huán)掃描 四、循環(huán)掃描CSCAN CSCAN 五、NN————SCAN SCAN和和FSCAN FSCAN算法。 算法。 20 先來先服務FCFS(First-Come,First ) 僅用于請求磁盤 程數(shù)目較少的場合。 21 圖5-24 SSTF調度算法 最短尋道時間優(yōu)先SSTF( Time First) nn 要求訪問的磁道與當 要求訪問的磁道與當 前磁頭距離最近，使 前磁頭距離最近，使 每次的尋道時間最短 每次的尋道時間最短 22 SSTF算法雖然能獲得較好的尋道性能 算法雖然能獲得較好的尋道性能，，卻可能 卻可能 導致某個進程發(fā)生 導致某個進程發(fā)生““饑餓 饑餓””() ()現(xiàn)象 現(xiàn)象。
。 Scan算法該算法不僅考慮到欲訪問的磁道與當 算法該算法不僅考慮到欲訪問的磁道與當 前磁道間的距離，更優(yōu)先考慮磁頭當前的移動方 前磁道間的距離，更優(yōu)先考慮磁頭當前的移動方 vv其原理是訪問的下一個對象應是同方向的，且其原理是訪問的下一個對象應是同方向的，且 又距離最近的。一般自里向外訪問，直至再無更 又距離最近的。一般自里向外訪問，直至再無更 外的磁道需要訪問，才將磁臂換向自外向里，往 外的磁道需要訪問，才將磁臂換向自外向里，往 返反復。這種算法又稱為 返反復。這種算法又稱為““電梯算法 電梯算法”” 掃描(SCAN)算法SCAN調度算法 100道開始，增加方向 被訪問下一個磁道 移動距離 150 50 160 10 184 24 90 94 58 32 55 3916 38 1820 平均尋道長度：27.8 24 Cscan Cscan算法規(guī)定磁頭單項移動，進行循環(huán)掃描。一 算法規(guī)定磁頭單項移動，進行循環(huán)掃描。一 個方向讀完，不是象 個方向讀完，不是象SCAN SCAN那樣回頭，而是循環(huán)。 那樣回頭，而是循環(huán)。 nn訪問時間： 訪問時間：2T 2TT+Smax T+Smax nnTT是從外向里或從里向外單向 是從外向里或從里向外單向掃描完要訪問的磁道的 掃描完要訪問的磁道的 尋道時間 尋道時間。
。 nn而而Smax Smax是將磁頭從最外面被訪問的磁道 是將磁頭從最外面被訪問的磁道直接移到 直接移到最最 里面欲訪問的磁道的尋道時間。 里面欲訪問的磁道的尋道時間。 循環(huán)掃描(CSCAN)算法CSCAN調度算法 100道開始，增加方向 被訪問的下一個磁道 移動距離 150 50 160 10 184 24 18 166 38 20 39 5516 58 9032 平均尋道長度：27.5 26 若某磁盤共有200個柱面，其編號為0～199，假設已完成96號柱面的訪問請求，還有若干個請求 者在等待服務，它們依次要訪問的柱面號為： 175，52，157，36，159、106，l08邏輯地址轉換為物理地址，72，分別 用先來先服務調度算法、最短尋道時間調度算法、 電梯調度算法和單向掃描調度算法（向序號增加 的方向移動）來確定實際服務的次序，并計算上 述兩種算法下移動臂需移動的距離。 27 (1)先來先服務調度算法： (175-96)+(175-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642 移動臂需移動642柱面的距離。 (106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159-l57)+(175-159)=223 移動臂需移動223個柱面的距離。
28 實際服務的次序：(106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-72)+(72- 52)+(52-36)=218 移動臂需移動218個柱面的距離。 (106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-36)+(52-36)+(72-52)=254 除了移動臂由里向外返回所用的時間外，還需移動 254個柱面的距離。 29 4.8.1 最佳置換算法和先進先出算法 二、 ––淘汰 淘汰最先進入內存的頁面 最先進入內存的頁面，即選擇在內存中駐留時間 ，即選擇在內存中駐留時間 最久的頁面予以淘汰。 最久的頁面予以淘汰。 ––出發(fā)點：最早調入主存中的頁面不再使用的可能性越 出發(fā)點：最早調入主存中的頁面不再使用的可能性越 大，應該最先淘汰。算法簡單對具有按線性順序訪問 大，應該最先淘汰。算法簡單對具有按線性順序訪問 的程序比較合適，而對其它情況效率不高 的程序比較合適，而對其它情況效率不高 引用率 304.8.1 最佳置換算法和先進先出算法 進程 進程PP執(zhí)行時的頁面走向為： 執(zhí)行時的頁面走向為：1, 如果在內存中分配如果在內存中分配33個頁面，則缺頁情況如下： 個頁面，則缺頁情況如下： 12 12次訪問中有缺頁 次訪問中有缺頁99次； 31如果在內存中分配4個頁面，則缺頁情況如下： 12次訪問中有缺頁10次； FIFO 現(xiàn)象的原因：FIFO算法的置換特征與進程訪問內存的動態(tài)特征是矛盾的，即被置換的頁 面并不是進程不會訪問的。
32 習題 11．某進程執(zhí)行時的頁面走向為 ．某進程執(zhí)行時的頁面走向為1 5，分別畫出其分配物理塊為，分別畫出其分配物理塊為33的最佳置換算 的最佳置換算 法的置換圖。 法的置換圖。 22．某進程執(zhí)行時的頁面走向為 ．某進程執(zhí)行時的頁面走向為1 5，分別畫出其分配物理塊為，分別畫出其分配物理塊為33和 和44的的FIFO FIFO算算 法的置換圖。 法的置換圖。 33．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問 ．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問 如下頁面： 如下頁面：3 5，采用，采用LRU LRU 置換算法求出訪問過程中發(fā)生的缺頁中斷的次數(shù) 置換算法求出訪問過程中發(fā)生的缺頁中斷的次數(shù) 及缺頁率。設分給作業(yè)的存儲塊數(shù)為 及缺頁率。設分給作業(yè)的存儲塊數(shù)為3. 3344．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問 ．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問 如下頁面： 如下頁面：2 2，設分給，設分給 作業(yè)的存儲塊數(shù)為 作業(yè)的存儲塊數(shù)為33。若用最佳置換算法，先進 。若用最佳置換算法，先進 先出， 先出，LRU LRU置換算法求出訪問過程中發(fā)生的缺頁 置換算法求出訪問過程中發(fā)生的缺頁 次數(shù)及缺頁率。
次數(shù)及缺頁率。 34 習題 11．某進程執(zhí)行時的頁面走向為 ．某進程執(zhí)行時的頁面走向為1 5，分別畫出其分配物理塊為，分別畫出其分配物理塊為33的最佳置 的最佳置 換算法的置換圖。 換算法的置換圖。 頁面蹤跡 缺頁率f＝7/1235 習題 22．某進程執(zhí)行時的頁面走向為 ．某進程執(zhí)行時的頁面走向為1 5，分別畫出其分配物理塊為，分別畫出其分配物理塊為33和 和44的的FIFO FIFO算法 算法 的置換圖。 的置換圖。 頁面蹤跡 缺頁率f＝9/1236 習題 33．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如 ．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如 下頁面： 下頁面：3 5邏輯地址轉換為物理地址，采用，采用LRU LRU置置 換算法求出訪問過程中發(fā)生的缺頁中斷的次數(shù)及 換算法求出訪問過程中發(fā)生的缺頁中斷的次數(shù)及 缺頁率。設分給作業(yè)的存儲塊數(shù)為 缺頁率。設分給作業(yè)的存儲塊數(shù)為3. 缺頁中斷次數(shù)6，缺頁率f＝6/12 37 44．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如 ．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如 下頁面： 下頁面：2 2，設分給作業(yè)，設分給作業(yè) 的存儲塊數(shù)為 的存儲塊數(shù)為33。若用最佳置換算法，先進先出， 。
若用最佳置換算法，先進先出， LRU LRU置換算法求出訪問過程中發(fā)生的缺頁次數(shù)及缺 置換算法求出訪問過程中發(fā)生的缺頁次數(shù)及缺 最佳置換訪問蹤跡 FIFO算法 頁面蹤跡 LRU算法 39 請求分頁存儲管理方式中，假定系統(tǒng)為某進程分配了4個頁框，頁面的引用順序為：6、1、2、0、 換算法產生多少次頁面置換？缺頁率是多少？(2)頁面置換次數(shù)為3次 (3)缺頁率為：7/14=50% 40 請求分頁存儲管理方式中，假設分配給某進程的頁框數(shù)為3，若程序的頁面引用順序為：0、2、3、 4、1、2、5、0、2、3、2、5，采用最佳置換算 法產生多少次頁面置換？缺頁率是多少？ (2)頁面置換次數(shù)為4次 (3)缺頁率為：7/12=58% 41 二、銀行家算法 避免死鎖算法中最有代表性的算法是 E.W 于1968年提出的銀行家算法： 該算法需要檢查申請者對資源的最大需求量，如 果系統(tǒng)現(xiàn)存的各類資源可以滿足申請者的請求， 就滿足申請者的請求。 這樣申請者就可很快完成其計算，然后釋放它占 用的資源，從而保證了系統(tǒng)中的所有進程都能完 成，所以可避免死鎖的發(fā)生。 3.6.2 避免死鎖 42 3.6.3利用銀行家算法避免死 1．數(shù)據(jù)結構–可利用資源向量 其初值是系統(tǒng)中該類資源的最大可用數(shù)目，其值將 隨著該類資源的分配與回收而動態(tài)改變。
[j]=k: 系統(tǒng)現(xiàn)有Rj類資源k個； –最大需求矩陣Max 是一個nm的矩陣，定義了系統(tǒng)中的n個進程中的 每一個進程對m類資源的最大需求量。 max[i,j]=k: 進程i需要Rj的最大數(shù)k個； 43 3.6.3利用銀行家算法避免死 –分配矩陣是一個nm的矩陣，定義了系統(tǒng)中每一類資源 的數(shù)量。[i,j]=k: 進程i已得到Rj 類資源k個； –需求矩陣Need 是一個nm的矩陣，用以表示每一個進程尚需 的各類資源數(shù)。 need[i,j]=k:進程i還需Rj類 資源k個，方能完成任務。 –有：need[i,j]= max[i,j]－[i,j] – 進程i請求資源數(shù)44 3.6.3利用銀行家算法避免死 2．銀行家算法[i,j]出錯處理。 否則,轉向下一步。 avail=avail-=+reqi needi=needi-reqi [i]=.F. needi