目錄

請求分頁中的硬件支持

1. 請求頁表機制

2. 缺頁中斷機構

硬件支持的詳細工作流程

示例代碼

請求分頁中的內存分配

最小物理塊數的確定

分配方式

分配公平性

請求分頁存儲管理方式中的內存分配策略

具體示例

頁面調入策略

最近最久未使用（LRU, Least Recently Used）

最少使用（LFU, Least Frequently Used）

先進先出（FIFO, First In First Out）

結語

---

????????請求分頁存儲管理方式是一種 commonly used 的虛擬內存管理技術，它結合了分頁存儲管理和按需裝入的概念。在請求分頁中，進程的地址空間被劃分為多個頁，但只將部分頁裝入內存，其余頁留在磁盤上。當進程訪問未駐留內存的頁時，會觸發缺頁中斷，操作系統負責將該頁調入內存。

請求分頁中的硬件支持

????????為了實現請求分頁，系統必須提供一定的硬件支持。除了要求一定容量的內存和磁盤外，還需要以下硬件組件：

1. 請求頁表機制

????????請求分頁系統需要使用請求頁表，其基本作用是將虛擬地址映射到物理地址。為了滿足頁面換進換出，在請求頁表中增加了以下四個字段：

• 存在位（Present Bit）：指示該頁是否駐留在物理內存中。如果存在位為0，表示該頁不在內存中，需要觸發缺頁中斷。
• 訪問字段（Accessed Bit）：記錄該頁是否被訪問過，用于頁面置換算法（如LRU算法）來判斷哪些頁可以被換出。
• 修改位（Dirty Bit）：指示該頁是否被修改過。如果被修改過，在換出時需要將該頁寫回到磁盤。
• 頁框號（Frame Number）：記錄該頁在物理內存中的位置。

2. 缺頁中斷機構

缺頁中斷是當進程訪問未駐留內存的頁時觸發的中斷。缺頁中斷機構負責以下任務：

• 保護 CPU 環境：保存當前的CPU狀態和寄存器內容，以便在中斷處理完成后能夠恢復。
• 分析中斷原因：確定中斷是由于缺頁引起的，并識別缺頁的虛擬地址。
• 轉入缺頁中斷處理程序：調用操作系統中的缺頁中斷處理程序，負責將所需的頁面從磁盤加載到內存中。
• 恢復 CPU 環境：在中斷處理完成后，恢復之前保存的CPU狀態和寄存器內容，使進程繼續執行。

硬件支持的詳細工作流程

以下是請求分頁過程中硬件支持的詳細工作流程：

1. 地址轉換：

   • CPU 生成虛擬地址。
   • 請求頁表機制將虛擬地址拆分為頁號和頁內偏移量。
   • 檢查請求頁表中的存在位。
     • 如果存在位為1，頁面在內存中，直接使用頁框號和頁內偏移量生成物理地址。
     • 如果存在位為0，觸發缺頁中斷。

2. 缺頁中斷處理：

   • 缺頁中斷機構保存當前CPU環境。
   • 分析中斷原因，確定缺頁的虛擬地址。
   • 調用操作系統的缺頁中斷處理程序。
     • 從磁盤讀取缺頁對應的頁面。
     • 更新請求頁表中的頁框號和存在位。
     • 如果需要，更新訪問字段和修改位。
   • 恢復CPU環境。
   • 重新執行引起缺頁中斷的指令。

示例代碼

以下是一個簡化的示例代碼，展示了如何處理請求分頁中的缺頁中斷：

#include <stdio.h>
#include <stdlib.h>#define PAGE_SIZE 4096
#define NUM_PAGES 256
#define MEMORY_SIZE (PAGE_SIZE * NUM_PAGES)typedef struct {int present;   // 存在位int accessed;  // 訪問字段int dirty;     // 修改位int frame_number; // 頁框號
} PageTableEntry;PageTableEntry page_table[NUM_PAGES];
char memory[MEMORY_SIZE];void handle_page_fault(int page_number) {printf("Handling page fault for page number: %d\n", page_number);// 從磁盤加載頁面到內存中（模擬）int frame_number = page_number; // 簡化示例，假設頁框號等于頁號page_table[page_number].frame_number = frame_number;page_table[page_number].present = 1;// 模擬數據加載snprintf(memory + frame_number * PAGE_SIZE, PAGE_SIZE, "Data for page %d", page_number);
}void access_memory(int virtual_address) {int page_number = virtual_address / PAGE_SIZE;int offset = virtual_address % PAGE_SIZE;if (page_number >= NUM_PAGES) {printf("Invalid virtual address\n");return;}if (!page_table[page_number].present) {handle_page_fault(page_number);}int frame_number = page_table[page_number].frame_number;char *data = memory + frame_number * PAGE_SIZE + offset;printf("Accessed data: %s\n", data);
}int main() {// 初始化頁表for (int i = 0; i < NUM_PAGES; i++) {page_table[i].present = 0;page_table[i].accessed = 0;page_table[i].dirty = 0;page_table[i].frame_number = -1;}// 模擬內存訪問access_memory(0x1234); // 訪問虛擬地址 0x1234access_memory(0x5678); // 訪問虛擬地址 0x5678return 0;
}

請求分頁中的內存分配

????????請求分頁是一種內存管理技術，它結合了分頁和按需調頁的優勢，提高了內存利用率和系統的靈活性。在請求分頁中，內存分配涉及幾個關鍵問題：

1. 最小物理塊數的確定：確保每個進程能夠正常運行所需的最小物理塊數。
2. 分配方式：選擇固定分配還是可變分配。
3. 分配公平性：決定如何公平地分配物理塊，采用平均分配或按比例分配。

最小物理塊數的確定

為了保證進程能正常運行，需要為每個進程分配至少一定數量的物理塊。確定最小物理塊數時，需要考慮以下因素：

• 進程的工作集大小：進程運行過程中實際所需的最小頁面數。
• 系統的上下文切換開銷：頻繁的缺頁中斷將增加系統開銷，可能影響進程的響應時間。

最小物理塊數的選擇通常是操作系統預設的一個閾值，具體值根據系統資源和應用需求確定。

分配方式

進程的物理塊可以采用固定分配或可變分配兩種方式：

1. 固定分配（Fixed Allocation）

   • 定義：為每個進程分配固定數量的物理塊，數量在進程創建時確定，不隨運行過程中變化。
   • 優點：實現簡單，易于管理。
   • 缺點：可能無法應對進程的動態需求，導致部分進程缺頁中斷頻繁而其他進程空閑。

2. 可變分配（Variable Allocation）

   • 定義：根據進程運行情況動態調整所分配的物理塊數量，靈活應對內存需求。
   • 優點：靈活性高，能夠更好地適應進程的實際需要。
   • 缺點：實現復雜，管理難度高。

分配公平性

為了確保資源利用的公平性，在分配物理塊時可選擇以下策略：

1. 平均分配算法（Equal Allocation Algorithm）

   • 實現：將物理塊平均分配給每個進程。
   • 優點：公平、簡單，每個進程獲得相同數量的物理塊。
   • 缺點：忽略了進程實際的工作集大小，可能導致不必要的缺頁中斷。

2. 按比例分配算法（Proportional Allocation Algorithm）

   • 實現：根據進程的大小或優先級按比例分配物理塊。
   • 優點：考慮了進程實際的內存需求，提高了內存利用效率。
   • 缺點：需要更多信息和計算，管理復雜。

請求分頁存儲管理方式中的內存分配策略

1. 固定分配局部置換（Fixed Allocation, Local Replacement）

   • 描述：為每個進程分配一組固定數量的物理塊，運行期間不再改變。
   • 缺頁處理：當進程發生缺頁中斷時，只能從分配給該進程的物理塊中選擇一個頁換出，再裝入所需頁。
   • 優點：簡單易行，進程間互不干擾，保證了隔離性。
   • 缺點：可能導致頻繁的缺頁中斷，內存利用率較低。

2. 可變分配全局置換（Variable Allocation, Global Replacement）

   • 描述：為每個進程初始分配一定數量的物理塊，運行期間可根據需要動態調整。
   • 缺頁處理：當進程發生缺頁中斷時，可以從系統的空閑物理塊中分配，也可以選擇全局范圍內任一物理塊上的頁換出，再裝入新頁。
   • 優點：靈活應對內存需求，提高了內存利用率。
   • 缺點：管理和實現復雜，可能導致缺頁率增加，影響系統性能。

具體示例

固定分配局部置換示例：

function handlePageFault(process) {if (process.allocatedFrames < process.maxFrames) {frame = allocateFrame();loadPage(process.page, frame);} else {victimPage = selectVictimPage(process);evictPage(victimPage);frame = victimPage.frame;loadPage(process.page, frame);}
}function selectVictimPage(process) {// Implement LRU, FIFO or any other page replacement algorithm inside the process's limit
}

可變分配全局置換示例：

function handlePageFaultGlobal(process) {if (freeFrameAvailable()) {frame = allocateFrame();loadPage(process.page, frame);} else {victimPage = selectGlobalVictimPage();evictPage(victimPage);frame = victimPage.frame;loadPage(process.page, frame);}
}function selectGlobalVictimPage() {// Implement LRU, FIFO or any other page replacement algorithm across all processes
}function freeFrameAvailable() {// Check the central free frame listreturn freeFrameList.size > 0;
}

?

頁面調入策略

????????頁面調入策略（Page Replacement Policies）是在發生缺頁中斷時，操作系統決定將哪個頁調入內存，確保系統運行的最優性能。通過合理選擇需要調入的頁，可以減少缺頁中斷次數，提高內存利用率和系統效率。以下是幾種常用的頁面調入策略：

最近最久未使用（LRU, Least Recently Used）

LRU算法選擇最近最久未使用的頁進行調入。該算法假設最近未被使用的頁在將來被訪問的可能性最小。

• 實現：為每個頁設置一個訪問字段，記錄該頁自上次被訪問以來的時間。每次訪問頁面時，更新該訪問字段。
• 過程：
  1. 發生缺頁中斷時，查找所有在內存中的頁面，選擇訪問字段值最大的頁面（即最近最久未使用的頁面）。
  2. 替換選中的頁面，將缺頁頁面調入內存。

示例偽代碼：

function lruPageReplacement(pageTable) {oldestPage = pageTable[0];for each page in pageTable {if page.accessTime > oldestPage.accessTime {oldestPage = page;}}return oldestPage;
}function handlePageFault_LRU(pageTable, newPage) {victimPage = lruPageReplacement(pageTable);evictPage(victimPage);loadPage(newPage, victimPage.frame);pageTable.updateAccessTime(newPage);
}

?

最少使用（LFU, Least Frequently Used）

LFU算法選擇在最近時期使用最少的頁進行調入。它假設使用頻率最低的頁在將來被訪問的可能性也較低。

• 實現：為每個頁設置一個計數器，記錄該頁被訪問的次數。每次訪問頁面時，增加該計數器的值。
• 過程：
  1. 發生缺頁中斷時，查找所有在內存中的頁面，選擇計數器值最小的頁面（即最近使用最少的頁面）。
  2. 替換選中的頁面，將缺頁頁面調入內存。

示例偽代碼：

?

function lfuPageReplacement(pageTable) {leastUsedPage = pageTable[0];for each page in pageTable {if page.accessCount < leastUsedPage.accessCount {leastUsedPage = page;}}return leastUsedPage;
}function handlePageFault_LFU(pageTable, newPage) {victimPage = lfuPageReplacement(pageTable);evictPage(victimPage);loadPage(newPage, victimPage.frame);pageTable.updateAccessCount(newPage);
}

?

先進先出（FIFO, First In First Out）

FIFO算法選擇最早進入內存的頁進行調入。該算法利用隊列的數據結構來管理頁面按進入內存的先后順序。

• 實現：為頁面設置一個隊列，根據調入的先后順序排列。
• 過程：
  1. 發生缺頁中斷時，選擇隊列中的第一個頁（即最早進入內存的頁面）。
  2. 替換選中的頁面，將缺頁頁面調入內存，將新的頁面添加到隊列末尾。

示例偽代碼：

function fifoPageReplacement(pageQueue) {victimPage = pageQueue.head();pageQueue.dequeue();return victimPage;
}function handlePageFault_FIFO(pageQueue, newPage) {victimPage = fifoPageReplacement(pageQueue);evictPage(victimPage);loadPage(newPage, victimPage.frame);pageQueue.enqueue(newPage);
}

?

各頁面調入策略的優缺點：

• LRU

  • 優點：較符合實際應用的訪問模式，能有效減少缺頁中斷的發生。
  • 缺點：實現復雜，需要維護訪問時間記錄，開銷較大。

• LFU

  • 優點：關注頁面的訪問頻率，對于某些特定使用場景效果較好。
  • 缺點：實現復雜，需要維護訪問計數器；如果某些頁面使用突然頻繁，可能導致性能不佳。

• FIFO

  • 優點：實現簡單，使用隊列管理頁面的調入順序。
  • 缺點：可能不符合實際應用的訪問模式，容易發生Belady異常（FIFO Anomaly），即增加頁框反而增加缺頁率。

?

結語

????????請求分頁存儲管理方式是 commonly used 的虛擬內存管理技術，它通過在磁盤和內存之間移動頁，實現了按需裝入和虛擬內存。請求分頁中的硬件支持包括請求頁表機制和缺頁中斷機構，內存分配策略包括固定分配和可變分配，頁面調入策略 commonly used LRU、LFU 和 FIFO 算法。了解請求分頁存儲管理方式，有助于我們理解虛擬內存的管理技術，并提高系統的性能和穩定性。