頁框演算法

⑴ 最佳頁面置換演算法的演算法描述

當產生缺頁中斷時，利用相應的淘汰頁面的演算法選擇需要淘汰的頁面。
頁面置換演算法在淘汰頁面時的演算法：
輸入：頁面號引用串P1,P2...Pn；
輸出：淘汰頁面Pt
實現：
1、如果頁框中的某個頁面P以後永不使用，則該頁面為淘汰頁面Pt。
2、如果每個P都會再次被訪問，那麼其中最長未來時間內不再被訪問的頁面為淘汰頁面Pt。

⑵ 操作系統頁式存儲管理的問題

存儲管理的基本原理內存管理方法 內存管理主要包括內存分配和回收、地址變換、內存擴充、內存共享和保護等功能。 下面主要介紹連續分配存儲管理、覆蓋與交換技術以及頁式與段式存儲管理等基本概念和原理。 1． 連續分配存儲管理方式 連續分配是操作系統頁式存儲管理的問題

⑶ 幾種頁面置換演算法的基本原理及實現方法

收藏推薦 在多道程序的正常運行過程中,屬於不同進程的頁面被分散存放在主存頁框中,當正在運行的進程所訪問的頁面不在內存時,系統會發生缺頁中斷,在缺頁中斷服務程序中會將所缺的頁面調入內存,如內存已無空閑頁框,缺頁中斷服務程序就會調用頁面置換演算法,頁面置換演算法的目的就是選出一個被淘汰的頁面.把內存和外存統一管理的真正目的是把那些被訪問概率非常高的頁存放在內存中.因此,置換演算法應該置換那些被訪問概率最低的頁,將它們移出內存.1最佳置換演算法基本原理:淘汰以後不再需要的或最遠的將來才會用到的頁面.這是1966年Belady提出的理想演算法,但無法實現,主要用於評價其他置換演算法.例:分配給某進程的內存頁面數是3頁,頁面地址流如下:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,其內存動態分配過程如下:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 17 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 20 0 0 0 0 0 4 4 4 0 0 0 0 0 0 01 1 1 3 3 3 3 3 3 3 3 1 1 1 12先進先出置換......(本文共計2頁) 如何獲取本文>>

⑷ 基本分頁存儲管理

  閱讀前請先閱讀 內存管理基礎 。從本文開始就介紹不連續分配的幾種方式，本文主要介紹基本分頁存儲管理。

  假設進程A的大小為23MB，但是每個分區的大小隻有10MB，如果進程只能佔用一個分區，顯然是放不下的。
  解決思路：如果允許進程佔用多個分區，那麼可以把進程拆分成 10MB + 10MB + 3MB三個部分 ，再把這三個部分別放在三個分區中（這些分區不要求連續）.....

  將內存空間分為一個個大小相等的分區（如每個分區4KB，每個分區就是一個 「頁框」 ，或稱 「內存塊」 、 「物理塊」 。每個頁框有一個編號，即 「頁框號」 ，或 「內存塊號」 、 「物理塊號」 ，頁框號 從0開始 ）。將用戶進程的地址空間也分為與頁框大小相等的一個個區域，稱為 頁面 或 頁 。頁框的大小不能太大，否則可能會產生過大的內存碎片。
  操作系統 以頁框為單位為各個進程分配內存空間。 進程的每個頁面分別放入一個頁框中，即進程的 頁面和內存的頁框 有 一一對應 的關系。

  進程分頁後，進程的各個頁面可以放在不連續的頁框中，所以如何實現邏輯地址到物理的地址的轉換？
  如下圖，將下面的進程分頁，假設每頁大小為50B，那麼就分為4個頁面。

  手動計算方法：
   頁號 = 邏輯地址 / 頁面長度（取整數部分）。
   頁內偏移量 = 邏輯地址 % 頁面長度
   頁面在內存中的起始位置 ：操作系統需要用某種數據結構記錄進程各個頁面的起始位置。
  對於計算機，通常將 頁面的大小劃分為2的整數次冪 。假設用32個二進制位表示邏輯地址，頁面大小為取2 12 B = 4096B = 4KB。

  如邏輯地址2，用二進製表示00000000 00000000 0000 0000 00000010 ，前24位二進制對應的十進制值就是邏輯地址2對應的頁號，即0號頁，而後12二進制位對應的十進制值就是偏移量。如果0號頁在內存中的起始地址為X，那麼邏輯地址2對應的物理地址就是 X + 2.
  同理，邏輯地址4097，用二進製表示00000000 00000000 0001 0000 00000001 ，前24位二進制對應的十進制值就是邏輯地址4097對應的頁號，即1號頁，而後12二進制位對應的十進制值就是偏移量。如果0號頁在內存中的起始地址為Y，那麼邏輯地址4097對應的物理地址就是 Y + 1.
  結論： 如果每個頁面的大小為2 k B，用二進製表示邏輯地址，則末尾的K位表示頁內偏移量，其餘部分就是頁號。
  因此，如果讓 每個頁面的大小為2的整數次冪， 計算機就可以很方便的得出一個邏輯地址對應的頁號和頁內偏移量。
  如果一個頁面的大小為2KB，那分頁存儲管理的邏輯地址結構為：

  地址結構包括兩個部分：前一個部分表示頁號，後一個部分表示頁內偏移量W。

  在知道如何計算頁號和偏移量後，要計算實際的物理地址，還需要知道頁號在內存中的起始地址，如何知道每個頁面在內存中存放的位置——操作系統要為 每個進程建立一張頁表。

  按照之前的方法計算出邏輯地址所對應的頁號N，然後根據頁表區查詢實際的內存塊號M，由於每個內存塊號的大小都是相等的，所以實際地址 = M * 內存塊大小 + 偏移量。

  在實際上，頁表中是沒有頁號的，那怎麼找到實際對應的內存塊號呢？
  假設某系統物理內存大小為4GB，頁面大小為4KB，則每個頁表項至少應該佔用多少位元組？

  各頁表項會 按順序連續地 存放在內存中，如果該頁表在內存中存放的地址為X，則M號頁對應的頁表項存放的地址為：X + M * 3B
  因此，頁表的頁號可以是隱含的。只需要知道 頁表存放的起始地址 和 頁表項長度 ，即可找到各個頁號對應的頁表項存放的位置，找到位置後就可以讀取該位置的值，即實際內存塊號。
  舉個例子，如果按照邏輯地址計算出了偏移量為20，頁號為1，頁表中的頁號是隱藏的，那麼根據頁表在內存中的起始地址20（假設的值），以及頁表項長度3B，那麼頁號為1所對應的實際內存塊號的值所在的地址就是：20 + 3 * 1 = 23的位置，然後在該位置的值，該值就是實際內存塊號，如果是4的話，那麼實際地址就是： 4 * 頁面大小（4096B） + 20 = 16404。

  基本地址變換結構可以藉助進程的頁表將邏輯地址轉換為物理地址。
  通常在系統中設置一個 頁表寄存器（PTR Page-Table Register） ，存放 頁表在內存中起始地址F 和 頁表長度M 。
  進程在未執行時，頁表的起址和頁表長度放在 進程式控制制塊（PCB）中 ，當進程被調度時，操作系統內核會把它們放在頁表寄存器中。

  邏輯地址到物理地址變換的過程：

  比較頁表長度，頁表項長度和頁面大小三個概念：

  在分頁存儲管理（頁式管理）系統中，只要確定了每個頁面的大小，邏輯地址結構就確定了。因此， 頁式管理中地址是一維的。 即只要給出一個邏輯地址，系統就可以自動算出頁號、頁內偏移量兩個部分，並不需要顯示告系統這個邏輯地址中，頁內偏移量佔多少位。
  基本地址變換結構需要訪問兩次內存： 第一次訪問內存查找頁表；第二次訪問物理內存對應的內存單元。

  對於上圖，會很頻繁地訪問10號塊中的指令、23號塊。
   時間局部性 ：如果執行了程序中的某條指令，那麼不久後這條指令很有可能再次執行：如果某個數據被訪問過，不久之後該數據很有可能再次被訪問。（因此程序中存在大量循環）。
   空間局限性 ：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元也很有可能被訪問。（因為很多數據在內存中都是連續存放的。如上面的數組，每次循環一次都會訪問鄰近的下一個元素地址）。
  在基本地址變換機構中，每次訪問一個邏輯地址，都需要查詢內幕才能中的頁表。由於局部性原理，可能連續很多次查找到的都是一個頁表項。既然如此，就可以利用這個特性減少訪問頁表的次數——快表。

   快表 ，又稱 聯想寄存器（TLB） ，是一種 訪問速度比內存快很多 的高速緩沖存儲器，用來存儲當前訪問的若干頁表項，以加速地址變換的過程。與此對應，內存中的頁表常稱為 慢表。
  快表的地址包換過程：
  (1) CPU給出邏輯地址，由某個硬體算得頁號、頁內偏移量，將頁號與快表中的所有頁號進行比較。
  (2) 如果找到匹配的頁號，說明要訪問的頁表項在快表中有副本，則直接從中取出該頁對應的內存塊號，再根據內存塊號中與頁內偏移量算地物理地址。最後訪問該物理地址對應的內存單元。因此如果快表命中，則訪問某個邏輯地址只需 一次 訪問內存即可。
  (3) 如果沒有找到匹配的頁號，則就需要訪問頁表，需要兩次訪問內存，在第一次訪問內存查詢得到頁號後，需要將頁號添加到快表中，以便後面再次被訪問。如果快表已滿，則必須按照一定的演算法對舊的頁表項進行替換。
  由於查詢快表比查詢頁表的速度快很多，因此只要快表命中，就可以節省很多時間。因為局部性原理，一般來說快表的命中率可以達到90%以上。

⑸ 內存管理

在一段時間內，程序的執行僅限於某個部分，相應地，它所訪問的存儲空間也局限於某個區域。

局部性原理的 分類 ：

將編譯後的目標模塊裝配成一個可執行程序。

可執行程序以 二進制可執行文件 的形式存儲在磁碟上。

鏈接程序的 任務 ：

程序的鏈接，可劃分為：

重定位 ：將邏輯地址（相對地址）轉換為物理地址（絕對地址）的過程。

物理地址 = 邏輯地址 + 程序在內存中的起始地址

程序的裝入，可劃分為：

任何時刻主存儲器 最多隻有一個作業 。

每個分區 大小固定不變 ：分區大小相等、分區大小不等。

每個分區可以且 僅可以裝入一個作業 。

使用 下限寄存器 和 上限寄存器 來保存當前作業的起始位置和結束位置。

使用 固定分區說明表 區分各分區的狀態。

分區 大小不是預先固定的 ，而是按作業（進程）的實際需求來劃分的。

分區 個數也不是預先固定的 ，而是由裝入的作業數決定的。

使用 空閑分區表 說明空閑分區的位置。

使用 空閑分區鏈 說明空閑分區的位置。

首次適應演算法的 過程 ：

外部碎片：空閑內存 沒有在 分配的 進程 中。

內部碎片：空閑內存 在 分配的 進程 中。

從 上次找到的 空閑分區的 下一個 空閑分區開始查找。

優點：空閑區分布均勻、查找開銷較小。

缺點：缺乏大空閑區。

最佳適應演算法的 過程 ：

優點：提高內存利用率。

注意點：每次在進行空閑區的修改前，需要先進行 分區大小遞增 的排序。

頁 ：將一個 進程 的 邏輯地址空間 分成若干個 大小相等 的 片 。

頁框 ：將 物理內存空間 分成與頁大小相同的若干個 存儲塊 。

分頁存儲 ：將進程的若干 頁 分別裝入多個 可以不相鄰 的 頁框 中。

頁內碎片 ：進程 最後一頁 一般裝不滿一個頁框，形成 頁內碎片 。

頁表 ：記錄描述頁的各種數據，實現從 頁號 到 頁框號 的映射。

注意： 頁內偏移量 的單位是 位元組 。

分頁地址變換指是： 邏輯地址 通過 地址變換機構 變換為 物理地址 。

分頁地址變換的 過程 ：

操作系統在修改或裝入頁表寄存器的值時，使用的是 特權級 指令。

頁大小：512B ~ 4KB，目前的計算機系統中，大多選擇 4KB 大小的頁。

頁大小的 選擇因素 ：

快表也稱為「轉換後援緩沖」，是為了提高CPU訪問速度而採用的專用緩存，用來存放 最近被訪問過的頁表項 。

英文縮寫：TLB。

組成： 鍵和值 。

在TLB中找到某一個頁號對應的頁表項的百分比稱為 TLB命中率 。

當 能 在TLB中找到所需要的頁表項時：

有效訪問時間 = 一次訪問TLB 的時間 + 一次訪問內存 的時間（訪問內存讀寫數據或指令）

當 不能 在TLB中找到所需要的頁表項時：

有效訪問時間 = 一次訪問TLB 的時間 + 兩次訪問內存 的時間（一次訪問內存頁表，一次訪問內存讀寫數據或指令）

將頁表再分頁，形成兩級或多級頁表，將頁表離散地存放在物理內存中。

在進程切換時，要運行的進程的頁目錄表歧視地址被寫入 頁表寄存器 。

在二級分頁系統中，為頁表再建立一個頁目錄表的目的是為了能在地址映射時得到頁表在物理內存中的地址，在頁目錄表的表項中存放了每一個 頁表 在物理內存中所在的 頁框號 。

虛擬存儲器 ：是指具有 請求調入功能 和 置換功能 ，能 從邏輯上對內存容量進行擴充 的一種存儲系統。

請求調入 ：就是說，先將進程一部分裝入內存，其餘的部分什麼時候需要，什麼時候請求系統裝入。

置換 ：如果請求調入時，沒有足夠的內存，則由操作系統選擇一部分內存中的進程內容移到外存，以騰出空間把當前需要裝入的內存調入。

為了實現請求分頁，需要：

保證進程正常運行的所需要的最小頁框數。

最小頁框數與進程的大小沒有關系，它與計算機的 硬體結構 有關，取決於 指令的格式、功能和定址方式 。

內存不夠時，從進程本身選擇淘汰頁，還是從系統中所有進程中選擇？：

採用什麼樣的演算法為不同進程分配頁框？：

常用的兩種 置換策略 ： 局部置換 和 全局置換 。

從分配給進程的頁框數量上看，常使用的兩種 分配策略 ： 固定分配 和 可變分配 。

用新調入的頁替換 最長時間沒有訪問 的頁面。

找到 未來最晚被訪問 的那個頁換出。

，P為缺頁率。

有效訪問時間與缺頁率成 正比 ，缺頁率越高，有效訪問時間越長，訪問效率越低。

工作集 ：某段時間間隔里，進程實際要訪問的頁的集合。

引入工作集的 目的 ：降低缺頁率，提高訪問內存效率。

抖動 ：運行進程的大部分時間都用於頁的換入換出，幾乎不能完成任何有效果工作的狀態。

抖動的 產生原因 ：

抖動的 預防方法 ：

在分段存儲管理的系統中，程序使用 二維 的邏輯地址，一個數用來表示 段 ，另一個數用來表示 段內偏移量 。

引入分段的 目的 ：

引入分段的 優點 ：

進程的地址空間被劃分成 若干個段 。

每個段定義了一組邏輯信息，每個段的大小由相應的邏輯信息組的長度確定， 段的大小不一樣 ，每個段的邏輯地址從0開始，採用一段 連續的地址空間 。

系統為每個段分配一個 連續的物理內存區域 ，各個 不同的段可以離散 地放入物理內存不同的區域。

系統為 每個進程建立一張段表 ，段表的每一個表項記錄的信息包括： 段號、段長和該段的基址 ，段表存放在內存中。

分段的 邏輯地址結構 ：

段表是由操作系統維護的用於支持分段存儲管理 地址映射 的數據結構。

每個進程有一個段表，段表由段表項構成。每個段表項包括： 段號、段長（段的大小）和該段的基址（段的起始地址） 。

若已知邏輯單元的地址為 S:D （段號:段內偏移量），求相應物理地址的步驟如下：

相同點 ：分頁和分段都屬於 離散 分配方式，都要通過數據結構與硬體的配合來實現 邏輯地址到物理地址 的映射。

不同點 ：

將用戶進程的邏輯空間 先劃分為若干個段 ， 每個段再劃分成若干個頁 。

進程以頁為單位在物理內存中 離散 存放，每個段中被離散存放的頁具有 邏輯相關性 。

為了實現地址映射，操作系統為 每個進程建立一個段表 ，再為 每個段建立一個頁表 。

進程段表的段表項組成：

滿足以下條件的兩個塊稱為 夥伴 ：

⑹ 實際中操作系統能為一個進程分配多少個頁框

根據LRU演算法，需要替換上次使用距現在最遠的頁面。
首先2,3,2這三頁進入內存（進程只分配到3個頁面，切順序為由內到外，第二個2進入時不缺頁，所以共缺頁2次），1進入時，內存不滿且內存中沒有1這個頁面即第1個進入內存，所以順序是2,3,1（缺頁1次）；下一個進入的是5，替換3（缺頁1次），得到2，1，5；下一個進入的是2，內存中有2號頁面，進行下一個頁面；下一個進入4,4替換1，得到2,5,4（缺頁1次）；下一個進入5，內存中有5號頁面，進行下一個頁面；下一個進入3，3替換2，得到3,5,4（缺頁1次）；下一次進入2,2替換4，得到3,5,2（缺頁1次）；後面2號和5號內存中均存在，則不需要替換。所以一共發生了7次缺頁.

⑺ 分頁存儲管理的實現原理

採用分頁存儲器允許把一個作業存放到若干不相鄰的分區中，既可免去移動信息的工作，又可盡量減少主存的碎片。分頁式存儲管理的基本原理如下：

1、 頁框：物理地址分成大小相等的許多區，每個區稱為一塊；
2、址分成大小相等的區，區的大小與塊的大小相等，每個稱一個頁面。
3、 邏輯地址形式：與此對應，分頁存儲器的邏輯地址由兩部分組成，頁號和單元號。邏輯地址格式為 頁號 單元號（頁內地址） 採用分頁式存儲管理時，邏輯地址是連續的。所以，用戶在編製程序時仍只須使用順序的地址，而不必考慮如何去分頁。

4、頁表和地址轉換：如何保證程序正確執行呢？
採用的辦法是動態重定位技術，讓程序的指令執行時作地址變換，由於程序段以頁為單位，所以，我們給每個頁設立一個重定位寄存器，這些重定位寄存器的集合便稱頁表。頁表是操作系統為每個用戶作業建立的，用來記錄程序頁面和主存對應頁框的對照表，頁表中的每一欄指明了程序中的一個頁面和分得的頁框的對應關系。絕對地址=塊號*塊長+單元號 以上從拓撲結構角度分析了對稱式與非對稱式虛擬存儲方案的異同,實際從虛擬化存儲的實現原理來講也有兩種方式;即數據塊虛擬與虛擬文件系統. 數據塊虛擬存儲方案著重解決數據傳輸過程中的沖突和延時問題.在多交換機組成的大型Fabric結構的SAN中,由於多台主機通過多個交換機埠訪問存儲設備,延時和數據塊沖突問題非常嚴重.數據塊虛擬存儲方案利用虛擬的多埠並行技術,為多台客戶機提供了極高的帶寬,最大限度上減少了延時與沖突的發生,在實際應用中,數據塊虛擬存儲方案以對稱式拓撲結構為表現形式. 虛擬文件系統存儲方案著重解決大規模網路中文件共享的安全機制問題.通過對不同的站點指定不同的訪問許可權,保證網路文件的安全.在實際應用中,虛擬文件系統存儲方案以非對稱式拓撲結構為表現形式. 虛擬存儲技術,實際上是虛擬存儲技術的一個方面,特指以CPU時間和外存空間換取昂貴內存空間的操作系統中的資源轉換技術 基本思想:程序,數據,堆棧的大小可以超過內存的大小,操作系統把程序當前使用的部分保留在內存,而把其他部分保存在磁碟上,並在需要時在內存和磁碟之間動態交換,虛擬存儲器支持多道程序設計技術 目的:提高內存利用率 管理方式
A 請求式分頁存儲管理 在進程開始運行之前,不是裝入全部頁面,而是裝入一個或零個頁面,之後根據進程運行的需要,動態裝入其他頁面;當內存空間已滿,而又需要裝入新的頁面時,則根據某種演算法淘汰某個頁面,以便裝入新的頁面

B 請求式分段存儲管理 為了能實現虛擬存儲,段式邏輯地址空間中的程序段在運行時並不全部裝入內存,而是如同請求式分頁存儲管理,首先調入一個或若干個程序段運行,在運行過程中調用到哪段時,就根據該段長度在內存分配一個連續的分區給它使用.若內存中沒有足夠大的空閑分區,則考慮進行段的緊湊或將某段或某些段淘汰出去,這種存儲管理技術稱為請求式分段存儲管理

⑻ 頁面置換演算法淘汰某一頁後的頁框號怎麼處理

我也是剛刷題看到的，想了一下，有些見解，有誤還望指正。
1.操作系統調出頁面0到外存
2.頁面1調入內存(我想這里把頁面1的內容放到了101H這個地址)
因此頁號1對應的頁框號是101h

⑼ 如果將FIFO頁面置換演算法用到4個頁框和8個頁面上，若初始時頁框為空，訪問字元串為0172327103，請問會發生

FIFO的頁框：
x0172333300
xx017222233
xxx01777722
xxxx0111177
LRU的頁框：
x0172327103
xx017232710
xxx01773271
xxxx0111327
FIFO發生6次缺頁，LRU為7次