03. 非连续分配管理

非连续分配管理方式

非连续分配允许进程的内存空间在物理内存中不连续分布，有效解决了连续分配中的外碎片问题。

分页管理

基本原理

将进程的逻辑地址空间和物理内存空间都划分为固定大小的页（Page）和页框（Frame），通过页表建立逻辑页到物理页框的映射关系。

地址结构

逻辑地址 = 页号 + 页内偏移
物理地址 = 页框号 + 页内偏移

地址转换过程：

1. 从逻辑地址中提取页号
2. 通过页表查找对应的页框号
3. 将页框号与页内偏移组合成物理地址

页表结构

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

#define PAGE_SIZE 4096
#define MAX_PAGES 1024

PageTableEntry page_table[MAX_PAGES];
int page_table_size;

地址转换实现

int page_address_translation(int logical_addr) {
    int page_number = logical_addr / PAGE_SIZE;
    int page_offset = logical_addr % PAGE_SIZE;

    // 检查页号是否有效
    if (page_number >= page_table_size) {
        return -1;  // 页号越界
    }

    // 检查页是否在内存中
    if (!page_table[page_number].valid) {
        // 页不在内存中，需要调入
        if (page_fault_handler(page_number) != 0) {
            return -1;  // 调页失败
        }
    }

    // 更新引用位
    page_table[page_number].referenced = 1;

    // 计算物理地址
    int frame_number = page_table[page_number].frame_number;
    int physical_addr = frame_number * PAGE_SIZE + page_offset;

    return physical_addr;
}

页表优化

1. 多级页表

// 二级页表结构
typedef struct {
    int page_directory[1024];  // 页目录
    PageTableEntry page_tables[1024][1024];  // 页表
} TwoLevelPageTable;

int two_level_address_translation(int logical_addr, TwoLevelPageTable *pt) {
    int page_directory_index = (logical_addr >> 22) & 0x3FF;
    int page_table_index = (logical_addr >> 12) & 0x3FF;
    int page_offset = logical_addr & 0xFFF;

    // 检查页目录项
    if (!pt->page_directory[page_directory_index]) {
        return -1;  // 页表不存在
    }

    // 访问页表
    PageTableEntry *entry = &pt->page_tables[page_directory_index][page_table_index];

    if (!entry->valid) {
        return -1;  // 页不在内存中
    }

    return entry->frame_number * PAGE_SIZE + page_offset;
}

2. 倒置页表

typedef struct {
    int process_id;      // 进程ID
    int page_number;     // 页号
    int frame_number;    // 页框号
} InvertedPageTableEntry;

InvertedPageTableEntry inverted_table[MAX_FRAMES];
int frame_count;

int inverted_address_translation(int logical_addr, int process_id) {
    int page_number = logical_addr / PAGE_SIZE;
    int page_offset = logical_addr % PAGE_SIZE;

    // 在倒置页表中查找
    for (int i = 0; i < frame_count; i++) {
        if (inverted_table[i].process_id == process_id &&
            inverted_table[i].page_number == page_number) {
            return inverted_table[i].frame_number * PAGE_SIZE + page_offset;
        }
    }

    return -1;  // 页不在内存中
}

3. TLB（快表）

typedef struct {
    int page_number;     // 页号
    int frame_number;    // 页框号
    int valid;          // 有效位
    int process_id;     // 进程ID
} TLBEntry;

#define TLB_SIZE 64
TLBEntry tlb[TLB_SIZE];

int tlb_address_translation(int logical_addr, int process_id) {
    int page_number = logical_addr / PAGE_SIZE;
    int page_offset = logical_addr % PAGE_SIZE;

    // 在TLB中查找
    for (int i = 0; i < TLB_SIZE; i++) {
        if (tlb[i].valid && tlb[i].process_id == process_id &&
            tlb[i].page_number == page_number) {
            // TLB命中
            return tlb[i].frame_number * PAGE_SIZE + page_offset;
        }
    }

    // TLB未命中，访问页表
    int physical_addr = page_address_translation(logical_addr);
    if (physical_addr != -1) {
        // 更新TLB
        update_tlb(page_number, physical_addr / PAGE_SIZE, process_id);
    }

    return physical_addr;
}

分段管理

基本原理

按程序的逻辑结构将进程的地址空间划分为若干个段，每个段对应一个逻辑模块（如代码段、数据段、栈段等）。

地址结构

逻辑地址 = 段号 + 段内偏移
物理地址 = 段基址 + 段内偏移

段表结构

typedef struct {
    int base;           // 段基址
    int limit;          // 段长度
    int valid;          // 有效位
    int protection;     // 保护位
    int accessed;       // 访问位
    int modified;       // 修改位
} SegmentTableEntry;

#define MAX_SEGMENTS 16
SegmentTableEntry segment_table[MAX_SEGMENTS];
int segment_count;

地址转换实现

int segment_address_translation(int logical_addr, int segment_number) {
    // 检查段号是否有效
    if (segment_number >= segment_count) {
        return -1;  // 段号越界
    }

    SegmentTableEntry *entry = &segment_table[segment_number];

    // 检查段是否在内存中
    if (!entry->valid) {
        return -1;  // 段不在内存中
    }

    // 检查段内偏移是否越界
    int segment_offset = logical_addr;
    if (segment_offset >= entry->limit) {
        return -1;  // 段内偏移越界
    }

    // 更新访问位
    entry->accessed = 1;

    // 计算物理地址
    int physical_addr = entry->base + segment_offset;

    return physical_addr;
}

分段与分页的比较

段页式管理

基本原理

结合分段和分页的优点，先按逻辑结构分段，再将每个段划分为固定大小的页。

地址结构

逻辑地址 = 段号 + 段内偏移
段内偏移 = 页号 + 页内偏移
物理地址 = 页框号 + 页内偏移

地址转换过程

1. 段表查找：根据段号查找段表，获得段基址和段长度
2. 段内地址检查：检查段内偏移是否越界
3. 页表查找：根据段内页号查找页表，获得页框号
4. 物理地址计算：将页框号与页内偏移组合

段页式地址转换

typedef struct {
    int base;           // 段基址
    int limit;          // 段长度
    int valid;          // 有效位
    int page_table_base; // 页表基址
} SegmentTableEntry;

typedef struct {
    int frame_number;    // 页框号
    int valid;          // 有效位
    int protection;     // 保护位
} PageTableEntry;

int segment_page_address_translation(int logical_addr, int segment_number) {
    // 第一步：段表查找
    if (segment_number >= segment_count) {
        return -1;  // 段号越界
    }

    SegmentTableEntry *seg_entry = &segment_table[segment_number];
    if (!seg_entry->valid) {
        return -1;  // 段不在内存中
    }

    // 第二步：段内地址检查
    int segment_offset = logical_addr;
    if (segment_offset >= seg_entry->limit) {
        return -1;  // 段内偏移越界
    }

    // 第三步：页表查找
    int page_number = segment_offset / PAGE_SIZE;
    int page_offset = segment_offset % PAGE_SIZE;

    PageTableEntry *page_entry = &page_tables[seg_entry->page_table_base][page_number];
    if (!page_entry->valid) {
        return -1;  // 页不在内存中
    }

    // 第四步：计算物理地址
    int physical_addr = page_entry->frame_number * PAGE_SIZE + page_offset;

    return physical_addr;
}

内存共享

分页系统中的共享

// 共享页面的实现
typedef struct {
    int frame_number;    // 页框号
    int reference_count; // 引用计数
    int shared;          // 共享标志
} SharedPageInfo;

SharedPageInfo shared_pages[MAX_FRAMES];

int share_page(int process_id, int page_number, int frame_number) {
    // 检查页面是否已被共享
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (shared_pages[i].frame_number == frame_number) {
            shared_pages[i].reference_count++;
            return i;
        }
    }

    // 创建新的共享页面
    int index = find_free_shared_slot();
    shared_pages[index].frame_number = frame_number;
    shared_pages[index].reference_count = 1;
    shared_pages[index].shared = 1;

    return index;
}

void unshare_page(int process_id, int page_number) {
    // 减少引用计数
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (shared_pages[i].frame_number == get_frame_number(process_id, page_number)) {
            shared_pages[i].reference_count--;
            if (shared_pages[i].reference_count == 0) {
                // 释放页面
                free_frame(shared_pages[i].frame_number);
                shared_pages[i].shared = 0;
            }
            break;
        }
    }
}

分段系统中的共享

// 共享段的实现
typedef struct {
    int segment_number;  // 段号
    int base;           // 段基址
    int limit;          // 段长度
    int reference_count; // 引用计数
    int shared;         // 共享标志
} SharedSegmentInfo;

SharedSegmentInfo shared_segments[MAX_SEGMENTS];

int share_segment(int process_id, int segment_number) {
    // 查找是否已有相同的共享段
    for (int i = 0; i < MAX_SEGMENTS; i++) {
        if (shared_segments[i].shared &&
            shared_segments[i].limit == get_segment_limit(process_id, segment_number)) {
            shared_segments[i].reference_count++;
            return i;
        }
    }

    // 创建新的共享段
    int index = find_free_shared_slot();
    shared_segments[index].segment_number = segment_number;
    shared_segments[index].base = get_segment_base(process_id, segment_number);
    shared_segments[index].limit = get_segment_limit(process_id, segment_number);
    shared_segments[index].reference_count = 1;
    shared_segments[index].shared = 1;

    return index;
}

内存保护

分页保护

// 页面级保护
typedef struct {
    int frame_number;    // 页框号
    int read;           // 读权限
    int write;          // 写权限
    int execute;        // 执行权限
    int user;           // 用户权限
} PageProtection;

int check_page_protection(int logical_addr, int access_type, int user_mode) {
    int page_number = logical_addr / PAGE_SIZE;
    PageProtection *prot = &page_protection[page_number];

    switch (access_type) {
        case READ_ACCESS:
            if (!prot->read) return -1;
            break;
        case WRITE_ACCESS:
            if (!prot->write) return -1;
            break;
        case EXECUTE_ACCESS:
            if (!prot->execute) return -1;
            break;
    }

    // 检查用户权限
    if (user_mode && !prot->user) {
        return -1;
    }

    return 0;
}

分段保护

// 段级保护
typedef struct {
    int base;           // 段基址
    int limit;          // 段长度
    int read;           // 读权限
    int write;          // 写权限
    int execute;        // 执行权限
    int user;           // 用户权限
} SegmentProtection;

int check_segment_protection(int logical_addr, int segment_number,
                           int access_type, int user_mode) {
    SegmentProtection *prot = &segment_protection[segment_number];

    // 检查段内偏移
    int offset = logical_addr;
    if (offset >= prot->limit) {
        return -1;  // 段内偏移越界
    }

    // 检查访问权限
    switch (access_type) {
        case READ_ACCESS:
            if (!prot->read) return -1;
            break;
        case WRITE_ACCESS:
            if (!prot->write) return -1;
            break;
        case EXECUTE_ACCESS:
            if (!prot->execute) return -1;
            break;
    }

    // 检查用户权限
    if (user_mode && !prot->user) {
        return -1;
    }

    return 0;
}

实际应用

Linux 内存管理

Linux 使用段页式管理，但主要依赖分页：

// Linux内核中的内存管理
struct mm_struct {
    struct vm_area_struct *mmap;        // 内存区域链表
    struct rb_root mm_rb;               // 红黑树
    unsigned long start_code, end_code; // 代码段
    unsigned long start_data, end_data; // 数据段
    unsigned long start_brk, brk;       // 堆
    unsigned long start_stack;          // 栈
    unsigned long arg_start, arg_end;   // 参数
    unsigned long env_start, env_end;   // 环境变量
};

Windows 内存管理

Windows 使用分页内存管理：

// Windows内存管理API
HANDLE CreateFileMapping(
    HANDLE hFile,
    LPSECURITY_ATTRIBUTES lpAttributes,
    DWORD flProtect,
    DWORD dwMaximumSizeHigh,
    DWORD dwMaximumSizeLow,
    LPCTSTR lpName
);

LPVOID MapViewOfFile(
    HANDLE hFileMappingObject,
    DWORD dwDesiredAccess,
    DWORD dwFileOffsetHigh,
    DWORD dwFileOffsetLow,
    SIZE_T dwNumberOfBytesToMap
);

总结

非连续分配管理方式通过分页、分段和段页式管理，有效解决了连续分配中的碎片问题，提高了内存利用率。现代操作系统主要采用段页式管理，结合了分段和分页的优点，既支持程序的逻辑结构，又提供了灵活的内存管理机制。