高端網(wǎng)站建設(shè)設(shè)搜索引擎的網(wǎng)站
目錄
一、相關(guān)問(wèn)題
1. 什么是虛擬內(nèi)存？為什么需要虛擬內(nèi)存？
（1）內(nèi)存擴(kuò)展
（2）內(nèi)存隔離
（3）物理內(nèi)存管理
（4）頁(yè)面交換
（5）內(nèi)存映射文件
2.?局部性原理
（1）時(shí)間局部性
（2）空間局部性
3.?什么是內(nèi)存分段和分頁(yè)？作用是什么？
（1）內(nèi)存分段
（2）內(nèi)存簡(jiǎn)單分頁(yè)
（3）多級(jí)頁(yè)表
那么 為什么不分級(jí)的 頁(yè)表就 做不到這樣 節(jié)約內(nèi)存 呢？
（4）段頁(yè)式內(nèi)存管理
（5）分頁(yè)分段的作用？
① 邏輯隔離
② 內(nèi)存保護(hù)
③ 虛擬內(nèi)存
④ 內(nèi)存共享
⑤ 內(nèi)存管理
（6）分段與分頁(yè)的區(qū)別？
① 分段
② 分頁(yè)（Paging）
（7）分段與分頁(yè)優(yōu)缺點(diǎn)？
4.?解釋一下內(nèi)存頁(yè)面置換算法？
補(bǔ)充：快表
（1）最佳頁(yè)面置換算法
（2）先進(jìn)先出置換算法
（3）最近最久未使用的置換算法
（4）時(shí)鐘頁(yè)面置換算法
一、相關(guān)問(wèn)題
1. 什么是虛擬內(nèi)存？為什么需要虛擬內(nèi)存？
????????虛擬內(nèi)存 在 每一個(gè) 進(jìn)程 創(chuàng)建加載的 過(guò)程中，會(huì) 分配一個(gè) 連續(xù) 虛擬地址空間，它 不是 真實(shí) 存在的，而是 通過(guò)映射 與 實(shí)際地址空間 對(duì)應(yīng)，這樣 就可以 使 每個(gè)進(jìn)程 看起來(lái) 都有 自己獨(dú)立的 連續(xù)地址空間，并 允許 程序訪問(wèn) 比物理內(nèi)存 RAM 更大的 地址空間，每個(gè)程序 都可以 認(rèn)為它 擁有 足夠的 內(nèi)存來(lái) 運(yùn)行。
????????需要 虛擬內(nèi)存的 原因：
（1）內(nèi)存擴(kuò)展
????????虛擬內(nèi)存 使得 每個(gè)程序 都可以 使用 比實(shí)際可用 內(nèi)存 更多的 內(nèi)存，從而 允許運(yùn)行 更大的程序 或 處理更多的 數(shù)據(jù)。
（2）內(nèi)存隔離
????????虛擬內(nèi)存還 提供了 進(jìn)程之間的 內(nèi)存隔離。每個(gè)進(jìn)程 都有自己的 虛擬地址 空間，因此 一個(gè)進(jìn)程 無(wú)法 直接訪問(wèn) 另一個(gè) 進(jìn)程的 內(nèi)存。
（3）物理內(nèi)存管理
????????虛擬內(nèi)存 允許 操作系統(tǒng) 動(dòng)態(tài)地 將數(shù)據(jù) 和 程序的部分 加載到 物理內(nèi)存中，以 滿足當(dāng)前 正在運(yùn)行的 進(jìn)程的 需求。當(dāng) 物理內(nèi)存不足時(shí)，操作系統(tǒng) 可以將 不常用的 數(shù)據(jù)或程序 暫時(shí)移到 硬盤上，從而 釋放內(nèi)存，以便 其他進(jìn)程 使用。
（4）頁(yè)面交換
????????當(dāng) 物理內(nèi)存 不足時(shí)，操作系統(tǒng) 可以 將一部分 數(shù)據(jù)從 物理內(nèi)存 寫入到 硬盤的 虛擬內(nèi)存中，這個(gè)過(guò)程被稱為 頁(yè)面交換。當(dāng)需要時(shí)，數(shù)據(jù) 可以 再次 從虛擬內(nèi)存中 加載到 物理內(nèi)存 中。這樣 可以保證 系統(tǒng)可以 繼續(xù)運(yùn)行，盡管 物理內(nèi)存 有限。
（5）內(nèi)存映射文件
????????虛擬內(nèi)存 還可以 用于 將文件映射到 內(nèi)存中，這使得 文件的 讀取和寫入 可以 像訪問(wèn) 內(nèi)存一樣 高效。
2.?局部性原理
????????在一段時(shí)間內(nèi)，程序傾向于 多次訪問(wèn) 相同的 數(shù)據(jù) 或 接近的 數(shù)據(jù)，而不是 隨機(jī)地 訪問(wèn) 內(nèi)存中的 各個(gè)位置。局部性原理 通常分為 兩種類型：時(shí)間局部性 和 空間局部性。
（1）時(shí)間局部性
????????如果 一個(gè)數(shù)據(jù) 被訪問(wèn)，那么在 不久的 將來(lái)它 很可能會(huì) 再次 被訪問(wèn)。這意味著 程序 在短時(shí)間內(nèi)傾向于 反復(fù)使用 相同的 數(shù)據(jù)項(xiàng)。
????????例如在 循環(huán)中 反復(fù)訪問(wèn) 數(shù)組的 元素。通過(guò) 利用 時(shí)間局部性，程序可以 將頻繁 使用的 數(shù)據(jù)存 儲(chǔ)在 緩存中，從而 減少訪問(wèn) 主內(nèi)存的 次數(shù)，提高程序的 執(zhí)行速度。
（2）空間局部性
????????如果一個(gè) 數(shù)據(jù)被 訪問(wèn)，那么 它附近的 數(shù)據(jù)也 很可能會(huì) 被訪問(wèn)，這意味著 程序在 訪問(wèn)一個(gè) 數(shù)據(jù)時(shí)，通常會(huì) 在接近 該數(shù)據(jù)的 附近訪問(wèn) 其他數(shù)據(jù)。
????????例如遍歷數(shù)組時(shí)，往往會(huì) 訪問(wèn) 相鄰的 元素。
????????文件系統(tǒng)在 磁盤上 存儲(chǔ)數(shù)據(jù)時(shí)，通常會(huì) 將相關(guān)的 數(shù)據(jù)塊 放在相鄰的 磁盤扇區(qū)上，以便在 訪問(wèn)一個(gè)數(shù)據(jù)塊 時(shí)能夠 快速地 訪問(wèn)相鄰的 數(shù)據(jù)塊。
3.?什么是內(nèi)存分段和分頁(yè)？作用是什么？
（1）內(nèi)存分段
????????內(nèi)存分段是 將一個(gè) 程序的 內(nèi)存空間 分為不同的 邏輯段 segments，每個(gè) 段 代表程序的 一個(gè)功能模塊 或 數(shù)據(jù)類型，如 代碼段、數(shù)據(jù)段、堆棧段 等。每個(gè)段 都有其 自己的大小 和 權(quán)限。
????????分段機(jī)制下的 虛擬地址 由兩部分組成，段選擇因子 和 段內(nèi)偏移量（二維結(jié)構(gòu)）。
- 段選擇子就 保存在 段寄存器 里面。段選擇子 里面 最重要的是 段號(hào)，用作 段表的 索引。段表 里面保存的是 這個(gè)段的 基地址、段的界限 和 特權(quán)等級(jí) 等。
- 虛擬地址 中的 段內(nèi)偏移量 應(yīng)該 位于 0 和 段界限 之間，如果 段內(nèi) 偏移量是 合法的，就將 段基地址 加上 段內(nèi)偏移量 得到 物理內(nèi)存地址。
????????知道了 虛擬地址 是 通過(guò) 段表 與 物理地址 進(jìn)行 映射的，分段機(jī)制 會(huì)把 程序的 虛擬地址分成 4 個(gè)段，每個(gè)段 在段表中 有一個(gè)項(xiàng)，在 這一項(xiàng) 找到 段的 基地址，再加上 偏移量，于是就能 找到 物理內(nèi)存 中的 地址，如下圖：
????????如果要 訪問(wèn) 段 3 中 偏移量 500 的虛擬地址，我們 可以 計(jì)算出 物理地址為，段 3 基地址 7000＋偏移量 500 = 7500。
（2）內(nèi)存簡(jiǎn)單分頁(yè)
????????分段的好處 就是能 產(chǎn)生 連續(xù)的 內(nèi)存空間，但是會(huì) 出現(xiàn)「外部?jī)?nèi)存碎片 和 內(nèi)存交換的空間 太大」的問(wèn)題。要 解決 這些問(wèn)題，那么就要 想出 能少出現(xiàn)一些 內(nèi)存碎片 的辦法。另外，當(dāng) 需要 進(jìn)行內(nèi)存交換的 時(shí)候，讓 需要 交換寫入 或者 從磁盤裝載的 數(shù)據(jù) 更少一點(diǎn)，這樣就 可以 解決問(wèn)題了。這個(gè)辦法，也就是 內(nèi)存分頁(yè)（Paging）。
????????分頁(yè)是 把 整個(gè) 虛擬和物理 內(nèi)存空間 切成一段段 固定尺寸的 大小。這樣 一個(gè) 連續(xù)并且 尺寸固定的 內(nèi)存空間，我們叫 頁(yè)（Page）。在 Linux 下，每一頁(yè)的大小為 4KB。虛擬地址與物理地址 之間通過(guò) 頁(yè)表 來(lái)映射，如下圖：
????????頁(yè)表 是 存儲(chǔ)在 內(nèi)存里的，內(nèi)存管理單元（MMU）就做 將 虛擬內(nèi)存地址 轉(zhuǎn)換成 物理地址 的工作。而當(dāng) 進(jìn)程訪問(wèn) 的 虛擬地址 在 頁(yè)表 中查不到時(shí)，系統(tǒng)會(huì) 產(chǎn)生一個(gè) 缺頁(yè)異常，進(jìn)入系統(tǒng)內(nèi)核空間 分配 物理內(nèi)存、更新 進(jìn)程 頁(yè)表，最后再 返回 用戶空間，恢復(fù)進(jìn)程的 運(yùn)行。
????????內(nèi)存分頁(yè) 由于 內(nèi)存空間 都是 預(yù)先劃分 好的，也就 不會(huì)像 內(nèi)存分段 一樣，在 段與段 之間 會(huì)產(chǎn)生間隙 非常小的 內(nèi)存，這正是 分段 會(huì)產(chǎn)生 外部?jī)?nèi)存碎片 的原因。
????????采用了 分頁(yè)，頁(yè)與頁(yè) 之間 是緊密排列的，所以不會(huì)有外部碎片。但是，因?yàn)?內(nèi)存分頁(yè)機(jī)制 分配內(nèi)存的 最小單位是 一頁(yè)，即使 程序 不足 一頁(yè)大小，我們 最少 只能 分配一個(gè)頁(yè)，所以 頁(yè)內(nèi) 會(huì)出現(xiàn) 內(nèi)存浪費(fèi)，所以 針對(duì) 內(nèi)存分頁(yè) 機(jī)制 會(huì)有 內(nèi)部?jī)?nèi)存碎片 的現(xiàn)象。
????????如果 內(nèi)存空間 不夠，操作系統(tǒng) 會(huì)把 其他 正在運(yùn)行的 進(jìn)程 中的「最近 沒(méi)被使用」的內(nèi)存 頁(yè)面 給釋放掉，也就是 暫時(shí) 寫在 硬盤上，稱為 換出（Swap Out）。一旦 需要的 時(shí)候，再 加載進(jìn)來(lái)，稱為 換入（Swap In）。所以，一次性 寫入磁盤 的 也只有 少數(shù)的 一個(gè)頁(yè) 或者 幾個(gè)頁(yè)，不會(huì) 花太多時(shí)間，內(nèi)存交換的效率就 相對(duì)比較高。
????????更進(jìn)一步地，分頁(yè)的方式 使得 我們 在加載程序的 時(shí)候，不再需要 一次性 都把 程序 加載到 物理內(nèi)存中。我們 完全可以 在進(jìn)行虛擬內(nèi)存 和 物理內(nèi)存的 頁(yè)之間的 映射之后，并不 真的 把頁(yè) 加載到 物理內(nèi)存 里，而是 只有在 程序運(yùn)行中，需要 用到對(duì)應(yīng) 虛擬內(nèi)存頁(yè) 里面的 指令 和 數(shù)據(jù)時(shí)，再加載到 物理內(nèi)存 里面去。
????????在 分頁(yè) 機(jī)制下，虛擬地址 分為 兩部分，頁(yè)號(hào)和頁(yè)內(nèi)偏移。頁(yè)號(hào) 作為 頁(yè)表的索引，頁(yè)表 包含 物理頁(yè)，每頁(yè) 所在物理內(nèi)存的 基地址，這個(gè) 基地址 與 頁(yè)內(nèi)偏移的 組合 就形成了 物理內(nèi)存地址，見(jiàn)下圖。
總的來(lái)說(shuō)，對(duì)于一個(gè)內(nèi)存地址轉(zhuǎn)換，其實(shí) 就是三個(gè)步驟：
- 把 虛擬內(nèi)存地址，切分成 頁(yè)號(hào)和偏移量；
- 根據(jù) 頁(yè)號(hào)，從 頁(yè)表 里面，查詢 對(duì)應(yīng)的 物理頁(yè)號(hào)；
- 直接拿 物理頁(yè)號(hào)，加上 前面的 偏移量，就得到了 物理 內(nèi)存地址。
????????下面 舉個(gè)例子（單個(gè)進(jìn)程），虛擬內(nèi)存中的 頁(yè) 通過(guò) 頁(yè)表 映射 為了 物理內(nèi)存中的 頁(yè)，如下圖：
缺陷
????????有空間上的缺陷。因?yàn)椴僮飨到y(tǒng)是可以同時(shí)運(yùn)行非常多的進(jìn)程的，這就意味著頁(yè)表會(huì)非常的龐大。
????????在 32 位 的環(huán)境下，虛擬地址空間 共有 4GB，假設(shè)一個(gè)頁(yè)的大小是 4KB（2^12），那么就需要大約 100萬(wàn)（2^20）個(gè)頁(yè)，每個(gè)「頁(yè)表項(xiàng)」需要 4 個(gè)字節(jié)大小來(lái) 存儲(chǔ)，那么整個(gè) 4GB 空間的 映射 就 需要有 4MB 的 內(nèi)存來(lái) 存儲(chǔ)頁(yè)表。
????????每個(gè)進(jìn)程 都是有 自己的 虛擬 地址空間的，也就說(shuō) 都有自己的 頁(yè)表。那么，100 個(gè) 進(jìn)程的話，就需要 400MB 的 內(nèi)存來(lái) 存儲(chǔ)頁(yè)表，這是 非常大的 內(nèi)存了，更別說(shuō) 64 位 的環(huán)境了。
（3）多級(jí)頁(yè)表
????????要解決 上面的 問(wèn)題，就 需要 采用一種 叫作 多級(jí)頁(yè)表（Multi-Level Page Table）的解決方案。上述 對(duì)于 單頁(yè)表 的實(shí)現(xiàn)方式，在 32 位 和 頁(yè)大小 4KB 的環(huán)境下，一個(gè)進(jìn)程的 頁(yè)表 需要 裝下 100 多萬(wàn)個(gè)「頁(yè)表項(xiàng)」，每個(gè) 頁(yè)表項(xiàng) 占用 4 字節(jié) 大小，相當(dāng)于 每個(gè) 頁(yè)表 需占用 4MB 大小的空間。
????????我們把 這個(gè) 100 多萬(wàn)個(gè)「頁(yè)表項(xiàng)」的 單級(jí)頁(yè)表 再分頁(yè)，將 頁(yè)表（一級(jí)頁(yè)表）分為 1024 個(gè)頁(yè)表（二級(jí)頁(yè)表），每個(gè)表（二級(jí)頁(yè)表）中包含 1024 個(gè)「頁(yè)表項(xiàng)」，形成 二級(jí)分頁(yè)。如下圖所示：
????????每個(gè)進(jìn)程 都有 4GB 的 虛擬地址空間，而 顯然 對(duì)于 大多數(shù) 程序 來(lái)說(shuō)，其 使用到的 空間 遠(yuǎn)未 達(dá)到 4GB，因此?會(huì) 存在 部分 對(duì)應(yīng)的 頁(yè)表項(xiàng) 都是空的，根本 沒(méi)有分配，對(duì)于 已分配的 頁(yè)表項(xiàng)，如果 存在 最近一定時(shí)間 未訪問(wèn)的 頁(yè)表，在 物理內(nèi)存 緊張的 情況下，操作系統(tǒng)會(huì) 將頁(yè)面 換出到 硬盤，也就是說(shuō) 不會(huì)占用 物理內(nèi)存。
????????如果 使用了 二級(jí)分頁(yè)，一級(jí)頁(yè)表 就可以 覆蓋 整個(gè) 4GB 虛擬 地址空間，但如果 某個(gè) 一級(jí)頁(yè)表的頁(yè)表項(xiàng) 沒(méi)有被 用到，也就 不需要 創(chuàng)建這個(gè) 頁(yè)表項(xiàng) 對(duì)應(yīng)的 二級(jí)頁(yè)表 了，即 可以在 需要時(shí) 才創(chuàng)建 二級(jí)頁(yè)表。
????????做個(gè)簡(jiǎn)單的計(jì)算，假設(shè) 只有 20% 的 一級(jí)頁(yè)表項(xiàng) 被用到了，那么 頁(yè)表 占用的 內(nèi)存空間 就只有 4KB（一級(jí)頁(yè)表）+20%*4MB（二級(jí)頁(yè)表）= 0.804MB，這對(duì)比 單級(jí)頁(yè)表 的 4MB 是一個(gè) 巨大的節(jié)約。
那么 為什么不分級(jí)的 頁(yè)表就 做不到這樣 節(jié)約內(nèi)存 呢？
????????從 頁(yè)表的性質(zhì) 來(lái)看，保存在 內(nèi)存中的 頁(yè)表 承擔(dān)的 職責(zé)是 將 虛擬地址 翻譯成 物理地址。假如 虛擬地址 在 頁(yè)表中 找不到 對(duì)應(yīng)的 頁(yè)表項(xiàng)，計(jì)算機(jī)系統(tǒng) 就不能 工作了。所以 頁(yè)表一定 要 覆蓋全部 虛擬地址空間，不分級(jí)的頁(yè)表 就 需要有 100 多萬(wàn)個(gè) 頁(yè)表項(xiàng) 來(lái)映射，而 二級(jí)分頁(yè) 則 只需要 1024 個(gè) 頁(yè)表項(xiàng)（此時(shí) 一級(jí)頁(yè)表 覆蓋到了 全部 虛擬地址空間，二級(jí)頁(yè)表在 需要時(shí) 創(chuàng)建）。
????????我們把 二級(jí)分頁(yè) 再推廣到 多級(jí)頁(yè)表，就會(huì) 發(fā)現(xiàn) 頁(yè)表 占用的 內(nèi)存空間 更少了，這一切都要 歸功于 對(duì) 局部性原理的 充分應(yīng)用。
對(duì)于 64 位 的系統(tǒng)，兩級(jí)分頁(yè)肯定不夠了，就變成了四級(jí)目錄，分別是：
- 全局頁(yè)目錄項(xiàng) PGD（Page Global Directory）；
- 上層頁(yè)目錄項(xiàng) PUD（Page Upper Directory）；
- 中間頁(yè)目錄項(xiàng) PMD（Page Middle Directory）；
- 頁(yè)表項(xiàng) PTE（Page Table Entry）；
（4）段頁(yè)式內(nèi)存管理
????????內(nèi)存分段 和 內(nèi)存分頁(yè) 并不是 對(duì)立的，它們是 可以 組合起來(lái) 在同一個(gè) 系統(tǒng)中 使用的，組合起來(lái)后通常稱為 段頁(yè)式 內(nèi)存管理。
段頁(yè)式內(nèi)存管理 實(shí)現(xiàn)的 方式：
- 先 將程序 劃分為 多個(gè) 有邏輯意義的 段，也就是 前面提到的 分段機(jī)制；
- 接著 再把 每個(gè)段 劃分為 多個(gè)頁(yè)，也就是 對(duì)分段 劃分出來(lái)的 連續(xù)空間，再劃分 固定大小的 頁(yè)；
????????這樣，地址結(jié)構(gòu) 就由 段號(hào)、段內(nèi)頁(yè)號(hào) 和 頁(yè)內(nèi)位移 三部分 組成。
????????用于 段頁(yè)式 地址變換 的數(shù)據(jù)結(jié)構(gòu)是 每一個(gè)程序 一張段表，每個(gè)段 又建立 一張頁(yè)表，段表中的地址 是頁(yè)表的 起始地址，而 頁(yè)表中的 地址則為 某頁(yè)的 物理頁(yè)號(hào)，如圖所示：
段頁(yè)式 地址變換 中要得到 物理地址 須經(jīng)過(guò) 三次內(nèi)存訪問(wèn)：
- 第一次 訪問(wèn)段表，得到 頁(yè)表起始地址；
- 第二次 訪問(wèn)頁(yè)表，得到 物理頁(yè)號(hào)；
- 第三次 將物理頁(yè)號(hào) 與 頁(yè)內(nèi)位移 組合，得到 物理地址。
????????可用 軟、硬件 相結(jié)合的方法 實(shí)現(xiàn) 段頁(yè)式 地址變換，這樣雖然 增加了 硬件成本 和 系統(tǒng)開(kāi)銷，但提高了 內(nèi)存的 利用率。
（5）分頁(yè)分段的作用？
① 邏輯隔離
????????內(nèi)存 分段和分頁(yè) 都實(shí)現(xiàn)了 程序的 邏輯隔離，使不同的 功能模塊 或 數(shù)據(jù)類型 能夠被 單獨(dú)管理和保護(hù)，提高了 程序的 可靠性和安全性。
② 內(nèi)存保護(hù)
????????通過(guò) 將不同的 段或頁(yè)面 設(shè)置為 只讀、可讀寫、不可執(zhí)行等 權(quán)限，操作系統(tǒng)可以 確保 程序 不會(huì)越界訪問(wèn) 或 修改 其他段的 內(nèi)容，從而 提高了 系統(tǒng)的 穩(wěn)定性。
③ 虛擬內(nèi)存
????????分段和分頁(yè) 都 有助于 實(shí)現(xiàn) 虛擬內(nèi)存 的概念，允許 應(yīng)用程序 認(rèn)為它們 在使用的是 一個(gè) 比實(shí)際物理內(nèi)存 更大的 內(nèi)存空間。
④ 內(nèi)存共享
????????通過(guò) 分頁(yè)，操作系統(tǒng) 可以實(shí)現(xiàn) 內(nèi)存頁(yè)面的 共享，從而 節(jié)省 內(nèi)存空間，多個(gè)進(jìn)程 可以 共享 相同的代碼 或 數(shù)據(jù)頁(yè)面。
⑤ 內(nèi)存管理
????????分頁(yè) 更加靈活，允許 操作系統(tǒng) 將 不同進(jìn)程的 頁(yè)面 分散 存放在 物理內(nèi)存 中，從而 提高 內(nèi)存利用率。分段 則 更適用于 管理不同的 邏輯模塊。
（6）分段與分頁(yè)的區(qū)別？
① 分段
- 基本單位：地址空間 被劃分為 不同的 邏輯段，每個(gè)段 具有 獨(dú)立的含義，如 代碼段、數(shù)據(jù)段等。
- 段的長(zhǎng)度：每個(gè)段的 長(zhǎng)度可以 動(dòng)態(tài)變化，不同段 的長(zhǎng)度 可以不同。
- 內(nèi)部碎片：由于 每個(gè)段的 長(zhǎng)度 可以 動(dòng)態(tài)變化，可能會(huì) 導(dǎo)致 內(nèi)部碎片，即 段內(nèi)部的 未使用空間。
- 外部碎片：可能會(huì) 導(dǎo)致 外部碎片，即 段之間的 未使用空間。
- 邏輯地址：邏輯地址 由 兩部分組成，一個(gè)是 段號(hào)，另一個(gè)是 段內(nèi)偏移。
② 分頁(yè)（Paging）
- 基本單位：地址空間 被劃分為 固定大小的 頁(yè)面，物理內(nèi)存 也被 劃分為 相同大小的 頁(yè)面框。
- 頁(yè)面的長(zhǎng)度：頁(yè)面的長(zhǎng)度 是固定的，由 操作系統(tǒng) 定義。
- 內(nèi)部碎片：由于 頁(yè)面長(zhǎng)度 固定，可能會(huì) 導(dǎo)致 內(nèi)部碎片，即 頁(yè)面內(nèi)部的 未使用空間。
- 外部碎片：由于 頁(yè)面長(zhǎng)度 固定，不同 頁(yè)面 之間的 未使用 空間 無(wú)法利用，可能 導(dǎo)致 外部碎片。
- 邏輯地址：邏輯地址 由 兩部分組成，一個(gè)是 頁(yè)號(hào)，另一個(gè)是 頁(yè)內(nèi)偏移。
綜述：
- 分頁(yè) 對(duì)用戶 不可見(jiàn)，分段 對(duì)用戶 可見(jiàn)。
- 分頁(yè)的 地址空間是 一維的，分段的 地址空間是 二維的。
- 分頁(yè)（單級(jí)頁(yè)表）、分段 訪問(wèn)一個(gè) 邏輯地址都 需要 兩次訪存，分段存儲(chǔ) 中可以 引入 快表機(jī)制。
- 分段 更容易 實(shí)現(xiàn) 信息的 共享和保護(hù)（純代碼 或 可重入代碼 可以共享）。
（7）分段與分頁(yè)優(yōu)缺點(diǎn)？
????????分頁(yè)管理：內(nèi)存 空間利用率高，不會(huì) 產(chǎn)生 外部碎片，只會(huì)有 少量的 頁(yè)內(nèi)碎片。但是 不方便 按照 邏輯模塊 實(shí)現(xiàn)信息的 共享和保護(hù)。
????????分段管理：很方便 按照 邏輯模塊 實(shí)現(xiàn) 信息的 共享和保護(hù)。但是如果 段長(zhǎng) 過(guò)大，為其 分配 很大的 連續(xù)空間會(huì) 很不方便，段式管理會(huì) 產(chǎn)生 外部碎片。
補(bǔ)充：
????????分頁(yè)管理將內(nèi)存劃分為固定大小的頁(yè)，這些頁(yè)并不直接反映程序的邏輯結(jié)構(gòu)。因此，很難根據(jù)程序的邏輯模塊來(lái)劃分頁(yè)，也很難直接通過(guò)頁(yè)來(lái)實(shí)現(xiàn)信息的共享和保護(hù)。
????????分段管理將程序的地址空間劃分為若干段，如代碼段、數(shù)據(jù)段、堆棧段等。這些段與程序的功能模塊緊密相關(guān)，反映了程序的邏輯結(jié)構(gòu)。由于段是按照程序的功能模塊劃分的，因此很容易確定哪些段需要共享，哪些段需要保護(hù)。
4.?解釋一下內(nèi)存頁(yè)面置換算法？
????????先說(shuō)一下 缺頁(yè)異常（缺頁(yè)中斷）。
????????當(dāng) CPU 訪問(wèn)的 頁(yè)面 不在 物理內(nèi)存 時(shí)，便會(huì) 產(chǎn)生一個(gè) 缺頁(yè)中斷，請(qǐng)求 操作系統(tǒng) 將所 缺頁(yè) 調(diào)入到 物理內(nèi)存。那它 與一般 中斷的 主要區(qū)別 在于：
- 缺頁(yè)中斷 在指令執(zhí)行「期間」產(chǎn)生 和 處理 中斷信號(hào)，而 一般中斷在 一條指令 執(zhí)行「完成」后 檢查和處理 中斷信號(hào)。
- 缺頁(yè)中斷 返回到 該指令的 開(kāi)始 重新執(zhí)行「該指令」，而 一般 中斷 返回 回到 該指令的「下一個(gè)指令」執(zhí)行。
????????缺頁(yè)中斷的處理流程如下圖：
- 在 CPU 里訪問(wèn) 一條 Load M 指令，然后 CPU 會(huì)去找 M 所對(duì)應(yīng)的 頁(yè)表項(xiàng)。
- 如果 該頁(yè)表項(xiàng) 的狀態(tài)位是「有效的」，那 CPU 就可以 直接去 訪問(wèn) 物理內(nèi)存 了，如果 狀態(tài)位 是「無(wú)效的」，則 CPU 則會(huì) 發(fā)送缺頁(yè) 中斷請(qǐng)求。
- 操作系統(tǒng) 收到了 缺頁(yè)中斷，則會(huì) 執(zhí)行 缺頁(yè)中斷 處理函數(shù)，先會(huì) 查找 該頁(yè)面在 磁盤中的 頁(yè)面的位置。
- 找到 磁盤中 對(duì)應(yīng)的 頁(yè)面后，需要把 該頁(yè)面 換入到 物理內(nèi)存 中，但是在 換入前，需要在 物理內(nèi)存中 找空閑頁(yè)，如果 找到 空閑頁(yè)，就把 頁(yè)面 換入到 物理內(nèi)存 中。
- 頁(yè)面 從 磁盤 換入到 物理內(nèi)存 完成后，則把 頁(yè)表項(xiàng)中的 狀態(tài)位 修改為「有效的」。
- 最后，CPU 重新執(zhí)行 導(dǎo)致 缺頁(yè)異常 的指令。
????????第 4 步 如果 找不到空閑頁(yè)的話，就說(shuō)明 此時(shí) 內(nèi)存 已滿了，這時(shí)候，就需要「頁(yè)面置換算法」選擇一個(gè) 物理頁(yè)，如果 該物理頁(yè)有 被 修改過(guò)（臟頁(yè)），則 把它 換出到 磁盤，然后 把該 被置換 出去的 頁(yè)表項(xiàng)的 狀態(tài) 改成「無(wú)效的」，最后 把 正在訪問(wèn)的 頁(yè)面 裝入到 這個(gè)物理頁(yè) 中。頁(yè)表項(xiàng)通常有如下圖的字段：
- 狀態(tài)位：用于 表示 該頁(yè) 是否 有效，也就是說(shuō) 是否 在物理內(nèi)存中，供 程序訪問(wèn)時(shí) 參考。
- 訪問(wèn)字段：用于 記錄該頁(yè) 在一段時(shí)間 被訪問(wèn)的 次數(shù)，供 頁(yè)面置換算法 選擇出 頁(yè)面時(shí) 參考。
- 修改位：表示 該頁(yè)在 調(diào)入內(nèi)存后 是否有被 修改過(guò)，由于 內(nèi)存中的 每一頁(yè) 都在 磁盤上 保留 一份副本，因此，如果 沒(méi)有修改，在 置換該頁(yè)時(shí) 就不需要 將該頁(yè) 寫回到 磁盤上，以 減少 系統(tǒng)的 開(kāi)銷；如果 已經(jīng) 被修改，則將 該頁(yè) 重寫到 磁盤上，以 保證磁盤中 所保留的 始終是 最新的副本。
- 硬盤地址：用于 指出 該頁(yè)在 硬盤上的 地址，通常是 物理塊號(hào)，供 調(diào)入 該頁(yè)時(shí) 使用。
????????所以，頁(yè)面置換算法的 功能是，當(dāng) 出現(xiàn) 缺頁(yè)異常，需 調(diào)入 新頁(yè)面 而內(nèi)存 已滿時(shí)，選擇 被置換的 物理頁(yè)面，也就是說(shuō) 選擇一個(gè) 物理頁(yè)面 換出到 磁盤，然后把 需要訪問(wèn) 的頁(yè)面 換入到 物理頁(yè)。
補(bǔ)充：快表
????????快表是 一種 特殊的 高速緩沖存儲(chǔ)器（Cache），內(nèi)容是 頁(yè)表 中的 一部分 或 全部?jī)?nèi)容。在操作系統(tǒng)中 引入 快表是 為了 加快 地址映射速度。在 虛擬頁(yè)式 存儲(chǔ)管理 中設(shè)置了 快表，作為 當(dāng)前 進(jìn)程頁(yè)表的 Cache。通?？毂硖幱?MIMU 中。
- 按照 邏輯地址 中的 頁(yè)號(hào) 查快表。
- 若該頁(yè)?已存在 快表 中，則由 快表中 記錄的 映射信息 和 頁(yè)內(nèi)偏移量 形成 物理地址。
- 若該頁(yè)?不在快表中，則 再查 主存頁(yè)表，與 頁(yè)表中 記錄的 映射信息 和 頁(yè)內(nèi)偏移量 形成物理地址，同時(shí) 將該 頁(yè)表項(xiàng) 登記到 快表中。
- 當(dāng) 快表 填滿后，又要 登記 新頁(yè)時(shí)，則需要 按照一定 替換策略 淘汰一個(gè) 舊的 登記項(xiàng)。
（1）最佳頁(yè)面置換算法
????????最佳頁(yè)面置換算法 基本思路是，置換在「未來(lái)」最長(zhǎng)時(shí)間 不訪問(wèn)的 頁(yè)面。所以，該算法 實(shí)現(xiàn) 需要 計(jì)算 內(nèi)存中 每個(gè) 邏輯頁(yè)面的「下一次」訪問(wèn)時(shí)間，然后比較，選擇 未來(lái) 最長(zhǎng)時(shí)間 不訪問(wèn)的 頁(yè)面。
????????舉個(gè)例子，假設(shè) 一開(kāi)始 有 3 個(gè) 空閑的 物理頁(yè)，然后 有請(qǐng)求的 頁(yè)面序列，那 它的 置換過(guò)程 如下圖：
????????在 這個(gè) 請(qǐng)求的 頁(yè)面序列 中，缺頁(yè) 共 發(fā)生了 7 次（空閑頁(yè) 換入 3 次＋最優(yōu)頁(yè)面置換 4 次），頁(yè)面置換 共發(fā)生了 4 次。這很理想，但是 實(shí)際系統(tǒng)中 無(wú)法實(shí)現(xiàn)，因?yàn)?程序 訪問(wèn)頁(yè)面 時(shí)是 動(dòng)態(tài)的，我們是 無(wú)法 預(yù)知 每個(gè) 頁(yè)面在「下一次」訪問(wèn)前的 等待時(shí)間。
????????所以，最佳頁(yè)面置換算法 作用是 為了衡量 你的算法的 效率，你的 算法 效率 越接近 該算法的 效率，那么 說(shuō)明你的 算法是 高效的。
（2）先進(jìn)先出置換算法
????????無(wú)法 預(yù)知頁(yè)面在 下一次訪問(wèn) 前 所需的 等待時(shí)間，那可以 選擇在 內(nèi)存駐留 時(shí)間 很長(zhǎng)的頁(yè)面 進(jìn)行中 置換，這個(gè)就是「先進(jìn)先出置換」算法的 思想。
????????以前面的 請(qǐng)求的 頁(yè)面序列作為例子，假設(shè)使用先進(jìn)先出置換算法，則過(guò)程如下圖：
????????在這個(gè) 請(qǐng)求的 頁(yè)面序列中，缺頁(yè)共發(fā)生了 10 次，頁(yè)面置換 共發(fā)生了 7 次，跟 最佳頁(yè)面 置換算法 比較起來(lái)，性能 明顯差了 很多。
（3）最近最久未使用的置換算法
????????最近最久未使用（LRU）的置換算法的 基本思路 是，發(fā)生缺頁(yè)時(shí)，選擇 最長(zhǎng)時(shí)間 沒(méi)有 被 訪問(wèn)的頁(yè)面 進(jìn)行置換，也就是說(shuō)，該算法 假設(shè) 已經(jīng) 很久 沒(méi)有 使用的 頁(yè)面 很有可能 在未來(lái) 較長(zhǎng)的 一段時(shí)間內(nèi) 仍然不會(huì) 被使用。
????????這種算法 近似 最優(yōu)置換算法，最優(yōu)置換算法是 通過(guò)「未來(lái)」的 使用情況 來(lái) 推測(cè) 要淘汰的 頁(yè)面，而 LRU 則是 通過(guò)「歷史」的 使用情況 來(lái)推測(cè) 要淘汰的 頁(yè)面。
????????以前面的 請(qǐng)求的 頁(yè)面序列作為例子，假設(shè) 使用 最近最久未使用的 置換算法，則過(guò)程如下圖：
????????在這個(gè) 請(qǐng)求的 頁(yè)面序列 中，缺頁(yè) 共 發(fā)生了 9 次，頁(yè)面置換 共 發(fā)生了 6 次，跟 先進(jìn)先出 置換算法比較 起來(lái)，性能 提高了一些。雖然 LRU 在理論上是 可以實(shí)現(xiàn)的，但 代價(jià)很高。
????????為了 完全 實(shí)現(xiàn) LRU，需要 在內(nèi)存中 維護(hù)一個(gè) 所有 頁(yè)面的 鏈表，最近 最多使用 的 頁(yè)面在 表頭，最近最少 使用的 頁(yè)面在 表尾。困難的是，在 每次訪問(wèn) 內(nèi)存時(shí) 都 必須要 更新「整個(gè)鏈表」。在 鏈表中 找到一個(gè) 頁(yè)面，刪除它，然后把 它移動(dòng)到 表頭是 一個(gè) 非常 費(fèi)時(shí)的 操作。所以，LRU? 雖然看上去 不錯(cuò)，但是 由于開(kāi)銷 比較大，實(shí)際 應(yīng)用中 比較少 使用。
（4）時(shí)鐘頁(yè)面置換算法
????????那 有沒(méi)有一種 即能 優(yōu)化置換的 次數(shù)，也能 方便實(shí)現(xiàn)的 算法呢？
????????時(shí)鐘頁(yè)面置換算法 就可以 兩者兼得，它跟 LRU 近似，又是對(duì) FIFO 的 一種改進(jìn)。
????????該算法的 思路是，把 所有的 頁(yè)面都 保存在 一個(gè)類似 鐘面的「環(huán)形鏈表」中，一個(gè) 表針 指向 最老的 頁(yè)面。當(dāng) 發(fā)生缺頁(yè) 中斷時(shí)，算法 首先 檢查 表針 指向的頁(yè) 面：
- 如果 它的 訪問(wèn)位 是 0，表示該頁(yè)面最久未被訪問(wèn)，可以選擇進(jìn)行置換，然后?淘汰 該頁(yè)面，并 把新的 頁(yè)面 插入 這個(gè)位置，然后 把表針 前移 一個(gè)位置。
- 如果 訪問(wèn)位 是 1，表示該頁(yè)面最近被訪問(wèn)過(guò)，它仍然處于活躍狀態(tài)，然后?清除 訪問(wèn)位，并把 表針 前移一個(gè) 位置，重復(fù) 這個(gè) 過(guò)程 直到 找到了 一個(gè)訪問(wèn)位 為 0 的 頁(yè)面 為止。
????????時(shí)鐘頁(yè)面置換算法的 工作流程圖如下：
