程式專題：設計一個虛擬記憶體管理程式

專題概述

這個專題要求撰寫一個程式，將大小為 2^16 = 65,536 位元組的虛擬位址空間中的邏輯位址轉換為實體位址。程式需要：

1. 讀取包含邏輯位址的檔案
2. 使用 TLB 和分頁表
3. 轉換每個邏輯位址為對應的實體位址
4. 輸出儲存在轉換後實體位址的位元組數值

目標是模擬邏輯位址到實體位址的轉換步驟。

細節

位址結構

• 讀取的檔案包含 32 位元整數表示的邏輯位址
• 只需關注最右邊的 16 位元
• 16 位元分為：
  1. 8 位元的分頁號碼
  2. 8 位元的偏移量

系統參數

• 分頁表有 2^8 個項次
• 分頁大小為 2^8 位元組
• TLB 有 16 個項次
• 欄大小為 2^8 位元組
• 256 個欄
• 實體記憶體大小為 65,536 位元組（256 欄 × 256 位元欄大小）

功能限制

• 只需處理讀取邏輯位址和轉換為實體位址
• 不需支援寫入邏輯位址空間

位址轉換過程

1. 從邏輯位址取出分頁號碼
2. 參考 TLB
   • TLB 命中：直接取出欄號碼
   • TLB 失誤：參考分頁表
     • 從分頁表獲得欄號碼
     • 或發生分頁錯誤

處理分頁錯誤

• 使用需求分頁方式
• 後備儲存體使用 BACKING_STORE.bin（65,536 位元組的二進位檔案）
• 分頁錯誤時，從 BACKING_STORE 讀取 256 位元組的分頁到實體記憶體
• 更新分頁表和 TLB

測試

• 使用提供的 addresses.txt 檔案（包含 0 到 65535 的邏輯位址）
• 輸出：
  1. 轉換前的邏輯位址
  2. 轉換後的實體位址
  3. 實體位址中儲存的位元組數值
• 使用 correct.txt 檢查輸出正確性

統計報告

程式執行完畢後，報告：

1. 分頁錯誤率
2. TLB 命中率

建議的實作步驟

1. 先寫一個簡單程式，從給定整數中提取分頁號碼和偏移量
2. 初期只實作分頁表，忽略 TLB
3. 分頁表正常工作後，整合 TLB（使用 FIFO 或 LRU 策略）

執行方式

./a.out address.txt

修改建議

• 使用較小的實體記憶體空間（如 128 分頁欄）
• 實作分頁替換策略（FIFO 或 LRU）

資源

所需檔案可在 https://github.com/greggagne/OSC9e/tree/master/ch9 找到。

程式碼

首先，請確保您有一個名為 BACKING_STORE.bin 的文件，大小為 65,536 bytes，放在與程式相同的目錄下。同時，您還需要一個 addresses.txt 文件，包含要轉換的邏輯地址。

以下是完整的 C++ 程式碼：

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
#include <algorithm>
#include <iomanip>

const int PAGE_TABLE_SIZE = 256;  // 2^8 頁表項
const int PAGE_SIZE = 256;        // 每頁 256 bytes
const int FRAME_COUNT = 256;      // 256 個框架
const int TLB_SIZE = 16;          // TLB 有 16 個項目
const int PHYSICAL_MEMORY_SIZE = 65536;  // 256 * 256 bytes

struct TLBEntry {
    uint8_t page_number;
    uint8_t frame_number;
};

struct PageTableEntry {
    bool valid;
    uint8_t frame_number;
};

class VirtualMemoryManager {
private:
    std::vector<PageTableEntry> page_table;
    std::vector<TLBEntry> tlb;
    std::vector<uint8_t> physical_memory;
    std::ifstream backing_store;
    int page_faults;
    int tlb_hits;
    int total_accesses;

    uint8_t find_free_frame() {
        static uint8_t next_frame = 0;
        uint8_t frame = next_frame;
        next_frame = (next_frame + 1) % FRAME_COUNT;
        return frame;
    }

    void update_tlb(uint8_t page_number, uint8_t frame_number) {
        static int tlb_index = 0;
        tlb[tlb_index] = {page_number, frame_number};
        tlb_index = (tlb_index + 1) % TLB_SIZE;
    }

    void handle_page_fault(uint8_t page_number) {
        page_faults++;
        
        uint8_t free_frame = find_free_frame();
        
        backing_store.seekg(page_number * PAGE_SIZE);
        backing_store.read(reinterpret_cast<char*>(&physical_memory[free_frame * PAGE_SIZE]), PAGE_SIZE);
        
        page_table[page_number] = {true, free_frame};
    }

public:
    VirtualMemoryManager() : 
        page_table(PAGE_TABLE_SIZE, {false, 0}),
        tlb(TLB_SIZE, {0, 0}),
        physical_memory(PHYSICAL_MEMORY_SIZE, 0),
        page_faults(0),
        tlb_hits(0),
        total_accesses(0) {
        backing_store.open("BACKING_STORE.bin", std::ios::binary);
        if (!backing_store) {
            std::cerr << "Error: Unable to open BACKING_STORE.bin" << std::endl;
            exit(1);
        }
    }

    uint32_t translate_address(uint32_t logical_address) {
        total_accesses++;
        uint16_t offset = logical_address & 0xFF;
        uint8_t page_number = (logical_address >> 8) & 0xFF;
        uint8_t frame_number;

        auto tlb_entry = std::find_if(tlb.begin(), tlb.end(),
            [page_number](const TLBEntry& entry) { return entry.page_number == page_number; });

        if (tlb_entry != tlb.end()) {
            tlb_hits++;
            frame_number = tlb_entry->frame_number;
        } else {
            if (!page_table[page_number].valid) {
                handle_page_fault(page_number);
            }
            frame_number = page_table[page_number].frame_number;
            update_tlb(page_number, frame_number);
        }

        uint32_t physical_address = (frame_number << 8) | offset;
        return physical_address;
    }

    void simulate(const std::string& filename) {
        std::ifstream address_file(filename);
        if (!address_file) {
            std::cerr << "Error: Unable to open " << filename << std::endl;
            return;
        }

        uint32_t logical_address;
        
        while (address_file >> logical_address) {
            uint32_t physical_address = translate_address(logical_address);
            uint8_t value = physical_memory[physical_address];
            
            std::cout << "Logical: " << std::setw(5) << logical_address 
                      << " Physical: " << std::setw(5) << physical_address 
                      << " Value: " << std::setw(4) << static_cast<int>(value) << std::endl;
        }
        
        print_statistics();
    }

    void print_statistics() {
        std::cout << "\nStatistics:" << std::endl;
        std::cout << "Page Faults: " << page_faults << std::endl;
        std::cout << "Page Fault Rate: " << std::fixed << std::setprecision(4) 
                  << static_cast<double>(page_faults) / total_accesses << std::endl;
        std::cout << "TLB Hits: " << tlb_hits << std::endl;
        std::cout << "TLB Hit Rate: " << std::fixed << std::setprecision(4) 
                  << static_cast<double>(tlb_hits) / total_accesses << std::endl;
    }
};

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <address_file>" << std::endl;
        return 1;
    }

    VirtualMemoryManager vmm;
    vmm.simulate(argv[1]);

    return 0;
}

要編譯和運行這個程式，請按照以下步驟：

1. 將上述代碼保存為 virtual_memory_manager.cpp。

2. 確保您有 BACKING_STORE.bin 和 addresses.txt 文件在同一目錄下。

3. 使用 g++ 編譯程式：

   g++ -std=c++11 -o virtual_memory_manager virtual_memory_manager.cpp
   

4. 運行程式：

   ./virtual_memory_manager addresses.txt
   

程式將讀取 addresses.txt 中的邏輯地址，轉換為物理地址，並顯示結果。最後，它會輸出統計信息，包括頁錯誤率和 TLB 命中率。

請注意，由於邏輯地址是隨機生成的，您可能會看到相對較低的 TLB 命中率，這是正常的。頁錯誤率會隨著程式的運行而降低，因為更多的頁面會被載入到物理記憶體中。

程式碼說明

1. 結構和常量定義：

   const int PAGE_TABLE_SIZE = 256;  // 2^8 頁表項
   const int PAGE_SIZE = 256;        // 每頁 256 bytes
   const int FRAME_COUNT = 256;      // 256 個框架
   const int TLB_SIZE = 16;          // TLB 有 16 個項目
   const int PHYSICAL_MEMORY_SIZE = 65536;  // 256 * 256 bytes
   
   struct TLBEntry {
       uint8_t page_number;
       uint8_t frame_number;
   };
   
   struct PageTableEntry {
       bool valid;
       uint8_t frame_number;
   };
   

   這裡定義了系統的基本參數和數據結構。TLB 和頁表的條目結構也在這裡定義。

2. VirtualMemoryManager 類：
   這個類封裝了整個虛擬記憶體管理系統的功能。

3. 主要成員變數：

   std::vector<PageTableEntry> page_table;
   std::vector<TLBEntry> tlb;
   std::vector<uint8_t> physical_memory;
   std::ifstream backing_store;
   int page_faults;
   int tlb_hits;
   int total_accesses;
   

   這些變數分別代表頁表、TLB、物理記憶體、後備存儲、頁錯誤計數、TLB命中計數和總訪問次數。

4. find_free_frame() 方法：
   使用簡單的循環策略找到下一個可用的框架。

5. update_tlb() 方法：
   使用 FIFO 策略更新 TLB。

6. handle_page_fault() 方法：
   處理頁錯誤，從後備存儲讀取頁面到物理記憶體，並更新頁表。

7. translate_address() 方法：
   這是核心方法，負責將邏輯地址轉換為物理地址。它首先檢查 TLB，如果未命中則檢查頁表，必要時處理頁錯誤。

8. simulate() 方法：
   讀取輸入文件中的邏輯地址，調用 translate_address() 進行轉換，並輸出結果。

9. print_statistics() 方法：
   輸出統計信息，包括頁錯誤率和 TLB 命中率。

10. main() 函數：
    創建 VirtualMemoryManager 實例並調用 simulate() 方法。

關於執行結果：

• 程式處理了 1000 個邏輯地址（因為 total_accesses 是 1000）。
• 發生了 244 次頁錯誤，頁錯誤率為 24.4%。這意味著有 24.4% 的訪問需要從後備存儲讀取頁面。
• TLB 命中了 54 次，命中率為 5.4%。這個相對較低的命中率是因為地址是隨機生成的，沒有很好的局部性。

輸出中的每一行代表一個邏輯地址的轉換：

• Logical 是輸入的邏輯地址
• Physical 是轉換後的物理地址
• Value 是在該物理地址找到的值（byte）

完賽心得

寫在最後的最後：
沒想到就這樣完成 30 天了。最大的改變應該是結束忙碌的一天後，要記得坐回書桌前打開作業系統課本。
感謝小黃借我書，感謝小夥伴們鼓勵，感謝我活在一個有 AI 可以問的 2024 年。
希望接下來能繼續善用 AI ，不要成為搬運工人 🤪