logo
简体中文
导航

04. 虚拟内存管理

虚拟内存管理

虚拟内存管理是现代操作系统的核心技术，通过将外存空间扩展为主存空间，为进程提供比物理内存更大的地址空间。

虚拟内存基本概念

基本原理

虚拟内存允许进程使用比物理内存更大的地址空间，通过页面置换机制将不常用的页面换出到外存，需要时再换入内存。

虚拟内存的优势

1. 扩大地址空间

  • 进程可以使用比物理内存更大的地址空间
  • 支持大程序的运行
  • 提高内存利用率

2. 内存保护

  • 每个进程有独立的虚拟地址空间
  • 防止进程间相互干扰
  • 支持内存访问权限控制

3. 内存共享

  • 多个进程可以共享相同的页面
  • 节省物理内存
  • 支持共享库

4. 按需调页

  • 只将需要的页面调入内存
  • 减少内存占用
  • 提高系统并发度

虚拟内存的实现机制

虚拟地址空间 → 页表 → 物理内存 + 外存

核心组件：

  1. 页表：记录虚拟页到物理页框的映射
  2. 页面置换算法：决定哪些页面被换出
  3. 调页机制：处理页面缺失
  4. 工作集管理：跟踪进程的活跃页面

请求分页管理

基本概念

请求分页是指进程的页面在需要时才调入内存，而不是一次性全部调入。

页表项结构

typedef struct {
    int frame_number;    // 物理页框号
    int valid;          // 有效位：1-在内存，0-在外存
    int dirty;          // 修改位：1-已修改，0-未修改
    int referenced;      // 引用位：1-最近访问，0-未访问
    int protection;      // 保护位：读/写/执行权限
    int present;         // 存在位：1-在内存，0-在外存
    int accessed;        // 访问位：1-已访问，0-未访问
} PageTableEntry;

页面缺失处理

void page_fault_handler(int page_number) {
    // 1. 检查页面是否有效
    if (page_number >= page_table_size) {
        raise_segmentation_fault();
        return;
    }

    // 2. 检查页面保护
    if (!check_page_protection(page_number, current_access)) {
        raise_protection_fault();
        return;
    }

    // 3. 查找空闲页框
    int frame_number = find_free_frame();
    if (frame_number == -1) {
        // 没有空闲页框，需要页面置换
        frame_number = page_replacement();
    }

    // 4. 从外存调入页面
    if (load_page_from_disk(page_number, frame_number) != 0) {
        raise_io_error();
        return;
    }

    // 5. 更新页表
    page_table[page_number].frame_number = frame_number;
    page_table[page_number].valid = 1;
    page_table[page_number].present = 1;
    page_table[page_number].referenced = 1;

    // 6. 更新TLB
    update_tlb(page_number, frame_number);

    // 7. 重新执行指令
    restart_instruction();
}

页面置换策略

1. 全局置换

  • 从所有进程中选择被置换的页面
  • 考虑整个系统的内存使用情况
  • 可能导致进程饥饿

2. 局部置换

  • 只从当前进程中选择被置换的页面
  • 保证进程的内存分配
  • 可能导致内存利用率低

页面置换算法

1. 最佳置换算法（OPT）

基本原理：选择将来最长时间内不会被访问的页面进行置换。

实现示例：

int optimal_page_replacement() {
    int victim_page = -1;
    int max_future_time = -1;

    for (int i = 0; i < page_table_size; i++) {
        if (page_table[i].valid) {
            int future_time = get_next_access_time(i);
            if (future_time > max_future_time) {
                max_future_time = future_time;
                victim_page = i;
            }
        }
    }

    return victim_page;
}

int get_next_access_time(int page_number) {
    // 查找页面下次被访问的时间
    for (int i = current_time + 1; i < reference_string_length; i++) {
        if (reference_string[i] == page_number) {
            return i;
        }
    }
    return INT_MAX;  // 不再被访问
}

特点：

  • 理论最优算法
  • 需要预知未来的访问序列
  • 实际中无法实现

2. 先进先出算法（FIFO）

基本原理：选择最早进入内存的页面进行置换。

实现示例：

typedef struct {
    int page_number;
    int entry_time;
} FIFOEntry;

FIFOEntry fifo_queue[MAX_FRAMES];
int queue_head = 0;
int queue_tail = 0;

int fifo_page_replacement() {
    // 选择最早进入的页面
    int victim_page = fifo_queue[queue_head].page_number;

    // 更新队列
    queue_head = (queue_head + 1) % MAX_FRAMES;

    return victim_page;
}

void fifo_page_in(int page_number) {
    // 将新页面加入队列
    fifo_queue[queue_tail].page_number = page_number;
    fifo_queue[queue_tail].entry_time = current_time;
    queue_tail = (queue_tail + 1) % MAX_FRAMES;
}

特点：

  • 实现简单
  • 不考虑页面使用频率
  • 性能较差

3. 最近最少使用算法（LRU）

基本原理：选择最长时间未被访问的页面进行置换。

实现示例：

typedef struct {
    int page_number;
    int last_access_time;
} LRUEntry;

LRUEntry lru_table[MAX_PAGES];

int lru_page_replacement() {
    int victim_page = -1;
    int oldest_time = INT_MAX;

    for (int i = 0; i < page_table_size; i++) {
        if (page_table[i].valid && lru_table[i].last_access_time < oldest_time) {
            oldest_time = lru_table[i].last_access_time;
            victim_page = i;
        }
    }

    return victim_page;
}

void lru_page_access(int page_number) {
    // 更新页面的最后访问时间
    lru_table[page_number].last_access_time = current_time;
}

特点：

  • 性能较好
  • 需要记录每个页面的访问时间
  • 硬件支持复杂

4. 时钟算法（CLOCK）

基本原理：使用循环队列模拟时钟，选择引用位为 0 的页面进行置换。

实现示例：

typedef struct {
    int page_number;
    int reference_bit;
} ClockEntry;

ClockEntry clock_queue[MAX_FRAMES];
int clock_hand = 0;

int clock_page_replacement() {
    while (1) {
        if (clock_queue[clock_hand].reference_bit == 0) {
            // 找到被置换的页面
            int victim_page = clock_queue[clock_hand].page_number;
            clock_hand = (clock_hand + 1) % MAX_FRAMES;
            return victim_page;
        } else {
            // 给页面第二次机会
            clock_queue[clock_hand].reference_bit = 0;
            clock_hand = (clock_hand + 1) % MAX_FRAMES;
        }
    }
}

void clock_page_access(int page_number) {
    // 设置页面的引用位
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (clock_queue[i].page_number == page_number) {
            clock_queue[i].reference_bit = 1;
            break;
        }
    }
}

特点：

  • 实现相对简单
  • 性能接近 LRU
  • 硬件支持较少

5. 改进的时钟算法

基本原理：同时考虑引用位和修改位，优先置换未被引用且未修改的页面。

实现示例：

typedef struct {
    int page_number;
    int reference_bit;
    int dirty_bit;
} EnhancedClockEntry;

EnhancedClockEntry enhanced_clock_queue[MAX_FRAMES];
int enhanced_clock_hand = 0;

int enhanced_clock_page_replacement() {
    int first_unreferenced = -1;
    int first_unreferenced_clean = -1;

    // 第一轮：查找未被引用且未修改的页面
    for (int i = 0; i < MAX_FRAMES; i++) {
        int index = (enhanced_clock_hand + i) % MAX_FRAMES;
        if (enhanced_clock_queue[index].reference_bit == 0) {
            if (first_unreferenced == -1) {
                first_unreferenced = index;
            }
            if (enhanced_clock_queue[index].dirty_bit == 0) {
                first_unreferenced_clean = index;
                break;
            }
        }
    }

    // 第二轮：如果没找到干净的页面，查找任何未被引用的页面
    if (first_unreferenced_clean != -1) {
        enhanced_clock_hand = (first_unreferenced_clean + 1) % MAX_FRAMES;
        return enhanced_clock_queue[first_unreferenced_clean].page_number;
    } else if (first_unreferenced != -1) {
        enhanced_clock_hand = (first_unreferenced + 1) % MAX_FRAMES;
        return enhanced_clock_queue[first_unreferenced].page_number;
    }

    // 第三轮：所有页面都被引用，重置引用位
    for (int i = 0; i < MAX_FRAMES; i++) {
        enhanced_clock_queue[i].reference_bit = 0;
    }

    return enhanced_clock_page_replacement();
}

页面分配策略

1. 固定分配

基本原理：为每个进程分配固定数量的页面。

实现示例：

typedef struct {
    int process_id;
    int allocated_frames;
    int max_frames;
} ProcessFrameAllocation;

ProcessFrameAllocation frame_allocation[MAX_PROCESSES];

int allocate_frames_fixed(int process_id, int requested_frames) {
    if (frame_allocation[process_id].allocated_frames + requested_frames >
        frame_allocation[process_id].max_frames) {
        return -1;  // 超过分配限制
    }

    // 分配页面
    int allocated = 0;
    for (int i = 0; i < requested_frames && allocated < requested_frames; i++) {
        int frame = find_free_frame();
        if (frame != -1) {
            allocate_frame_to_process(frame, process_id);
            allocated++;
        }
    }

    frame_allocation[process_id].allocated_frames += allocated;
    return allocated;
}

2. 可变分配

基本原理：根据进程的需要动态调整分配的页面数量。

实现示例：

typedef struct {
    int process_id;
    int allocated_frames;
    int working_set_size;
    float page_fault_rate;
} VariableAllocation;

VariableAllocation variable_allocation[MAX_PROCESSES];

int adjust_frame_allocation(int process_id) {
    float current_fault_rate = variable_allocation[process_id].page_fault_rate;
    int current_frames = variable_allocation[process_id].allocated_frames;

    if (current_fault_rate > HIGH_FAULT_RATE) {
        // 页面缺失率高，增加分配
        return increase_frame_allocation(process_id);
    } else if (current_fault_rate < LOW_FAULT_RATE) {
        // 页面缺失率低，减少分配
        return decrease_frame_allocation(process_id);
    }

    return current_frames;
}

工作集模型

基本概念

工作集是指进程在最近一段时间内访问的页面集合，反映了进程的局部性特征。

工作集计算

typedef struct {
    int page_number;
    int last_access_time;
} WorkingSetEntry;

WorkingSetEntry working_set[MAX_PAGES];
int working_set_size = 0;

int calculate_working_set(int process_id, int window_size) {
    int current_time = get_current_time();
    int ws_size = 0;

    for (int i = 0; i < page_table_size; i++) {
        if (page_table[i].valid &&
            current_time - working_set[i].last_access_time <= window_size) {
            ws_size++;
        }
    }

    return ws_size;
}

void update_working_set(int page_number) {
    working_set[page_number].last_access_time = get_current_time();
    working_set[page_number].page_number = page_number;
}

工作集置换算法

int working_set_page_replacement(int window_size) {
    int current_time = get_current_time();
    int victim_page = -1;
    int oldest_time = INT_MAX;

    for (int i = 0; i < page_table_size; i++) {
        if (page_table[i].valid) {
            int time_since_access = current_time - working_set[i].last_access_time;
            if (time_since_access > window_size &&
                working_set[i].last_access_time < oldest_time) {
                oldest_time = working_set[i].last_access_time;
                victim_page = i;
            }
        }
    }

    return victim_page;
}

抖动问题

抖动现象

抖动是指系统频繁进行页面置换，导致 CPU 利用率急剧下降的现象。

抖动原因

  1. 页面分配不足：进程分配的页面数量少于工作集大小
  2. 页面置换算法不当：选择的置换算法不适合当前访问模式
  3. 内存竞争激烈：多个进程同时竞争有限的内存资源

抖动检测

typedef struct {
    int process_id;
    int page_fault_count;
    int cpu_utilization;
    float fault_rate;
} ThrashingMonitor;

ThrashingMonitor thrashing_monitor[MAX_PROCESSES];

int detect_thrashing() {
    int thrashing_processes = 0;

    for (int i = 0; i < process_count; i++) {
        if (thrashing_monitor[i].fault_rate > THRESHOLD_FAULT_RATE &&
            thrashing_monitor[i].cpu_utilization < THRESHOLD_CPU_UTIL) {
            thrashing_processes++;
        }
    }

    return thrashing_processes > 0;
}

抖动预防

void prevent_thrashing() {
    if (detect_thrashing()) {
        // 1. 增加页面分配
        increase_frame_allocation_for_all();

        // 2. 调整页面置换算法
        adjust_replacement_algorithm();

        // 3. 限制进程数量
        limit_process_count();

        // 4. 使用工作集模型
        use_working_set_model();
    }
}

性能优化

1. 预调页

void prepaging(int process_id) {
    // 根据历史访问模式预测需要的页面
    int predicted_pages[MAX_PAGES];
    int predicted_count = predict_pages(process_id, predicted_pages);

    for (int i = 0; i < predicted_count; i++) {
        if (!page_table[predicted_pages[i]].valid) {
            load_page_from_disk(predicted_pages[i], find_free_frame());
        }
    }
}

2. 页面缓冲

typedef struct {
    int page_number;
    int frame_number;
    int dirty;
} PageBuffer;

PageBuffer page_buffer[MAX_BUFFER_SIZE];
int buffer_head = 0;
int buffer_tail = 0;

void buffer_page(int page_number, int frame_number) {
    page_buffer[buffer_tail].page_number = page_number;
    page_buffer[buffer_tail].frame_number = frame_number;
    page_buffer[buffer_tail].dirty = 0;
    buffer_tail = (buffer_tail + 1) % MAX_BUFFER_SIZE;
}

3. 写时复制

int copy_on_write(int page_number) {
    if (page_table[page_number].reference_count > 1) {
        // 创建页面副本
        int new_frame = allocate_new_frame();
        copy_page_content(page_table[page_number].frame_number, new_frame);

        // 更新页表
        page_table[page_number].frame_number = new_frame;
        page_table[page_number].reference_count = 1;

        return new_frame;
    }

    return page_table[page_number].frame_number;
}

实际应用

Linux 虚拟内存管理

// Linux内核中的虚拟内存管理
struct vm_area_struct {
    unsigned long vm_start;      // 起始地址
    unsigned long vm_end;        // 结束地址
    unsigned long vm_flags;      // 标志位
    struct file *vm_file;        // 映射文件
    unsigned long vm_pgoff;      // 文件偏移
    struct vm_operations_struct *vm_ops; // 操作函数
};

Windows 虚拟内存管理

// Windows虚拟内存API
LPVOID VirtualAlloc(
    LPVOID lpAddress,
    SIZE_T dwSize,
    DWORD flAllocationType,
    DWORD flProtect
);

BOOL VirtualFree(
    LPVOID lpAddress,
    SIZE_T dwSize,
    DWORD dwFreeType
);

总结

虚拟内存管理是现代操作系统的核心技术，通过页面置换、工作集管理和性能优化等技术，为进程提供了比物理内存更大的地址空间。选择合适的页面置换算法和分配策略对于提高系统性能至关重要。现代操作系统通常结合多种技术，以实现高效的内存管理。