前言

        大家好！今天给大家详解《计算机操作系统》第八章 —— 磁盘存储器的管理，这一章是操作系统外存管理的核心内容，不管是考研、面试还是实际开发，都是高频考点。本文会用通俗易懂的语言拆解每个知识点，搭配完整可运行的 C++98 代码（无任何语法糖，纯 C++98 标准）、 架构图 / 流程图，还有每个知识点的实战案例，方便大家动手实操。

8.1 外存的组织方式

        外存（磁盘为主）的组织方式决定了数据如何在磁盘上存储和读取，核心是把物理磁盘的扇区、磁道抽象成操作系统可管理的逻辑结构。

核心概念

        磁盘的物理结构：磁道（同心圆）→ 扇区（磁道分割的最小存储单元）→ 柱面（不同盘面的同号磁道）；常见外存组织方式：

1. 连续分配：文件占用连续的磁盘块，优点是读取快，缺点是易产生碎片、扩展困难；
2. 链接分配：文件块通过指针链接，分隐式链接（指针存在块末尾）和显式链接（FAT 表存指针），优点是无外部碎片，缺点是随机访问慢；
3. 索引分配：为文件建索引块（存所有数据块地址），优点是随机访问快，缺点是索引块占用额外空间。

架构图

综合案例：模拟连续分配与链接分配

        以下是完整的 C++98 代码，模拟两种分配方式的磁盘块管理，代码可直接编译运行（g++ -std=c++98 文件名.cpp）：

#include <iostream>
#include <vector>
#include <string>
// 禁用C++11及以上特性，严格遵循C++98
#if __cplusplus >= 201103L
#error "请使用C++98标准编译！"
#endif

using namespace std;

// 磁盘块大小（模拟，单位：字节）
const int BLOCK_SIZE = 512;
// 总磁盘块数
const int TOTAL_BLOCKS = 100;

// 磁盘块结构体（C++98不支持类内初始化，需在构造函数初始化）
struct DiskBlock {
    int block_id;       // 块编号
    bool is_used;       // 是否被占用
    int next_block;     // 链接分配的下一块编号（-1表示无）
    string data;        // 块内数据

    // C++98构造函数
    DiskBlock() : block_id(0), is_used(false), next_block(-1), data("") {}
    DiskBlock(int id) : block_id(id), is_used(false), next_block(-1), data("") {}
};

// 磁盘管理器类
class DiskManager {
private:
    vector<DiskBlock> disk;  // 模拟磁盘（C++98的vector支持）

public:
    // 初始化磁盘
    DiskManager() {
        // 初始化100个磁盘块
        for (int i = 0; i < TOTAL_BLOCKS; ++i) {
            disk.push_back(DiskBlock(i));
        }
    }

    // 8.1.1 连续分配：为文件分配连续的n个块
    // 返回起始块号，-1表示分配失败
    int continuous_allocate(int n) {
        int count = 0;
        int start = -1;
        // 遍历磁盘找连续空闲块
        for (int i = 0; i < TOTAL_BLOCKS; ++i) {
            if (!disk[i].is_used) {
                if (count == 0) {
                    start = i;  // 记录连续块起始位置
                }
                count++;
                // 找到足够的连续块
                if (count == n) {
                    // 标记为已使用
                    for (int j = start; j < start + n; ++j) {
                        disk[j].is_used = true;
                    }
                    return start;
                }
            } else {
                // 中断连续，重置计数
                count = 0;
                start = -1;
            }
        }
        return -1;  // 无足够连续块
    }

    // 8.1.2 链接分配：为文件分配一个空闲块，并链接到前一块
    // prev_block：前一块编号（-1表示新文件的第一个块）
    // 返回新分配的块号，-1表示分配失败
    int linked_allocate(int prev_block) {
        // 找第一个空闲块
        for (int i = 0; i < TOTAL_BLOCKS; ++i) {
            if (!disk[i].is_used) {
                disk[i].is_used = true;
                // 如果有前一块，更新前一块的next指针
                if (prev_block != -1 && prev_block >= 0 && prev_block < TOTAL_BLOCKS) {
                    disk[prev_block].next_block = i;
                }
                return i;
            }
        }
        return -1;
    }

    // 释放连续分配的块
    void continuous_free(int start, int n) {
        if (start < 0 || start + n > TOTAL_BLOCKS) {
            cout << "释放失败：起始块或块数非法！" << endl;
            return;
        }
        for (int i = start; i < start + n; ++i) {
            disk[i].is_used = false;
            disk[i].next_block = -1;  // 重置链接
            disk[i].data.clear();
        }
    }

    // 释放链接分配的块（从起始块开始）
    void linked_free(int start) {
        if (start < 0 || start >= TOTAL_BLOCKS || !disk[start].is_used) {
            cout << "释放失败：起始块非法或未使用！" << endl;
            return;
        }
        int current = start;
        // 遍历链表释放所有块
        while (current != -1) {
            int next = disk[current].next_block;
            disk[current].is_used = false;
            disk[current].next_block = -1;
            disk[current].data.clear();
            current = next;
        }
    }

    // 打印磁盘块使用状态（前20块，方便查看）
    void print_disk_status() {
        cout << "\n磁盘块使用状态（前20块）：" << endl;
        for (int i = 0; i < 20; ++i) {
            cout << "块" << i << "：" << (disk[i].is_used ? "已占用" : "空闲") 
                 << " | 下一块：" << disk[i].next_block << endl;
        }
    }
};

// 测试函数
void test_allocation() {
    DiskManager dm;
    cout << "===== 测试连续分配 =====" << endl;
    // 分配5个连续块
    int start = dm.continuous_allocate(5);
    if (start != -1) {
        cout << "成功分配连续块，起始块号：" << start << endl;
    } else {
        cout << "连续分配失败！" << endl;
    }
    dm.print_disk_status();

    cout << "\n===== 测试链接分配 =====" << endl;
    // 分配第一个块
    int block1 = dm.linked_allocate(-1);
    // 分配第二个块，链接到第一个块
    int block2 = dm.linked_allocate(block1);
    cout << "链接分配的块1：" << block1 << "，块2：" << block2 << endl;
    dm.print_disk_status();

    cout << "\n===== 测试释放 =====" << endl;
    dm.continuous_free(start, 5);
    dm.linked_free(block1);
    dm.print_disk_status();
}

int main() {
    // 测试外存组织方式的分配与释放
    test_allocation();
    return 0;
}

代码说明

1. 严格遵循 C++98 标准：禁用 C++11 及以上特性（如类内初始化、auto 关键字等），使用 C++98 支持的 vector、构造函数初始化列表；
2. 核心功能：模拟磁盘块的连续分配（找连续空闲块）、链接分配（通过 next 指针串联块），以及对应的释放逻辑；
3. 测试函数：覆盖分配、释放、状态打印，运行后可直观看到磁盘块的使用变化。

8.2 文件存储空间的管理

        文件存储空间管理的核心是高效跟踪磁盘空闲块，避免浪费、快速分配 / 释放，常见方法有：位示图法、空闲表法、空闲链表法、成组链接法。

核心概念

1. 位示图法：用二进制位表示磁盘块状态（0 = 空闲，1 = 占用），优点是占用空间小、查找快，适合大容量磁盘；
2. 空闲表法：用表格记录空闲块的起始地址和块数（类似内存的空闲分区表），适合连续分配；
3. 空闲链表法：把所有空闲块用链表串联，分块链表（按块链接）和簇链表（按簇链接）；
4. 成组链接法：结合空闲表和链表的优点，UNIX 系统采用，把空闲块分组链接，减少链表遍历开销。

流程图

综合案例：位示图法实现磁盘空间管理（C++98 代码）

#include <iostream>
#include <vector>
#include <cstring>
// 严格C++98
#if __cplusplus >= 201103L
#error "请使用C++98标准编译！"
#endif

using namespace std;

// 位示图管理器（C++98实现）
class BitmapManager {
private:
    vector<char> bitmap;  // 位示图：每个char存8个块的状态（1字节=8位）
    int total_blocks;     // 总磁盘块数

    // 计算位示图的索引和位偏移
    void get_bit_pos(int block_id, int& index, int& offset) {
        index = block_id / 8;    // 对应char的索引
        offset = block_id % 8;   // 对应char内的位偏移
    }

public:
    // 初始化位示图：total_blocks个磁盘块，初始全空闲（0）
    BitmapManager(int total) : total_blocks(total) {
        // 计算需要的char数：向上取整
        int bitmap_size = (total_blocks + 7) / 8;
        bitmap.resize(bitmap_size, 0);  // 初始化为0（所有位为0）
    }

    // 检查块是否空闲
    bool is_free(int block_id) {
        if (block_id < 0 || block_id >= total_blocks) return false;
        int index, offset;
        get_bit_pos(block_id, index, offset);
        // 按位与判断：对应位为0则空闲
        return (bitmap[index] & (1 << offset)) == 0;
    }

    // 分配单个块：返回块号，-1失败
    int allocate_block() {
        for (int i = 0; i < total_blocks; ++i) {
            if (is_free(i)) {
                int index, offset;
                get_bit_pos(i, index, offset);
                bitmap[index] |= (1 << offset);  // 标记为占用（置1）
                return i;
            }
        }
        return -1;
    }

    // 分配n个连续块：返回起始块号，-1失败
    int allocate_continuous(int n) {
        int count = 0;
        int start = -1;
        for (int i = 0; i < total_blocks; ++i) {
            if (is_free(i)) {
                if (count == 0) start = i;
                count++;
                if (count == n) {
                    // 标记所有块为占用
                    for (int j = start; j < start + n; ++j) {
                        int index, offset;
                        get_bit_pos(j, index, offset);
                        bitmap[index] |= (1 << offset);
                    }
                    return start;
                }
            } else {
                count = 0;
                start = -1;
            }
        }
        return -1;
    }

    // 释放块
    void free_block(int block_id) {
        if (block_id < 0 || block_id >= total_blocks) {
            cout << "块号非法！" << endl;
            return;
        }
        int index, offset;
        get_bit_pos(block_id, index, offset);
        bitmap[index] &= ~(1 << offset);  // 置0
    }

    // 打印位示图（前10字节，方便查看）
    void print_bitmap() {
        cout << "\n位示图状态（前10字节，二进制）：" << endl;
        int print_size = min(10, (int)bitmap.size());
        for (int i = 0; i < print_size; ++i) {
            cout << "字节" << i << "：";
            // 逐位打印（从高位到低位）
            for (int j = 7; j >= 0; --j) {
                cout << ((bitmap[i] >> j) & 1);
            }
            cout << endl;
        }
    }
};

// 测试位示图
void test_bitmap() {
    BitmapManager bm(100);  // 100个磁盘块，位示图占13字节（100/8=12.5）
    cout << "===== 测试位示图分配 =====" << endl;
    // 分配单个块
    int block = bm.allocate_block();
    cout << "分配单个块：" << block << endl;
    // 分配5个连续块
    int start = bm.allocate_continuous(5);
    cout << "分配5个连续块，起始块：" << start << endl;

    bm.print_bitmap();

    cout << "\n===== 测试释放 =====" << endl;
    bm.free_block(block);
    bm.print_bitmap();
}

int main() {
    test_bitmap();
    return 0;
}

代码说明

1. 位示图核心：用 char 数组存储位状态（1 个 char=8 位，对应 8 个磁盘块），通过位运算快速标记 / 查询块状态；
2. 关键函数：get_bit_pos计算块号对应的位位置，allocate_continuous实现连续块分配，free_block释放块；
3. 兼容性：所有语法均为 C++98 支持，无 C++11 特性。

8.3 提高磁盘 I/O 速度的途径

        磁盘 I/O 是系统性能瓶颈，核心优化思路是减少寻道时间、旋转延迟、传输时间，常见途径如下：

核心方法

1. 磁盘调度算法：减少寻道时间（核心），如 FCFS、SSTF、SCAN、C-SCAN、LOOK；
2. 提前读（预读）：操作系统预判用户可能读取的块，提前读入内存缓冲区；
3. 延迟写：数据先写入缓冲区，待合适时机（如缓冲区满、系统空闲）再刷到磁盘；
4. 磁盘高速缓存：内存中开辟一块区域缓存磁盘数据，减少物理 I/O；
5. 优化物理布局：文件数据按磁盘物理顺序存储，减少旋转延迟。

思维导图

综合案例：磁盘调度算法实现（C++98 代码）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
// 严格C++98
#if __cplusplus >= 201103L
#error "请使用C++98标准编译！"
#endif

using namespace std;

// 磁盘调度算法类
class DiskScheduling {
private:
    int current_pos;  // 当前磁头位置

public:
    DiskScheduling(int pos) : current_pos(pos) {}

    // 8.3.1 FCFS：先来先服务
    int fcfs(vector<int>& requests) {
        int total_seek = 0;
        cout << "\nFCFS调度过程：" << endl;
        cout << "初始磁头位置：" << current_pos << endl;
        for (size_t i = 0; i < requests.size(); ++i) {
            int seek = abs(requests[i] - current_pos);
            total_seek += seek;
            cout << "从" << current_pos << "到" << requests[i] << "，寻道距离：" << seek << endl;
            current_pos = requests[i];
        }
        return total_seek;
    }

    // 8.3.2 SSTF：最短寻道时间优先
    int sstf(vector<int> requests) {
        int total_seek = 0;
        vector<bool> processed(requests.size(), false);  // 标记是否处理过
        cout << "\nSSTF调度过程：" << endl;
        cout << "初始磁头位置：" << current_pos << endl;

        int processed_count = 0;
        while (processed_count < (int)requests.size()) {
            int min_seek = -1;
            int target = -1;
            int target_idx = -1;
            // 找当前磁头最近的未处理请求
            for (size_t i = 0; i < requests.size(); ++i) {
                if (!processed[i]) {
                    int seek = abs(requests[i] - current_pos);
                    if (min_seek == -1 || seek < min_seek) {
                        min_seek = seek;
                        target = requests[i];
                        target_idx = i;
                    }
                }
            }
            // 处理该请求
            total_seek += min_seek;
            cout << "从" << current_pos << "到" << target << "，寻道距离：" << min_seek << endl;
            current_pos = target;
            processed[target_idx] = true;
            processed_count++;
        }
        return total_seek;
    }

    // 8.3.3 SCAN：电梯算法（向一个方向走到头，再反向）
    int scan(vector<int> requests, int max_cylinder, bool direction_up) {
        int total_seek = 0;
        vector<int> left, right;
        // 分离磁头左侧和右侧的请求
        for (size_t i = 0; i < requests.size(); ++i) {
            if (requests[i] < current_pos) {
                left.push_back(requests[i]);
            } else {
                right.push_back(requests[i]);
            }
        }
        // 排序
        sort(left.begin(), left.end());
        sort(right.begin(), right.end());

        cout << "\nSCAN调度过程（" << (direction_up ? "向上" : "向下") << "）：" << endl;
        cout << "初始磁头位置：" << current_pos << endl;

        // 向上走
        if (direction_up) {
            // 处理右侧请求
            for (size_t i = 0; i < right.size(); ++i) {
                int seek = abs(right[i] - current_pos);
                total_seek += seek;
                cout << "从" << current_pos << "到" << right[i] << "，寻道距离：" << seek << endl;
                current_pos = right[i];
            }
            // 走到最外侧柱面
            if (!left.empty()) {
                int seek = abs(max_cylinder - current_pos);
                total_seek += seek;
                cout << "从" << current_pos << "到" << max_cylinder << "，寻道距离：" << seek << endl;
                current_pos = max_cylinder;
                // 反向处理左侧请求
                for (int i = left.size() - 1; i >= 0; --i) {
                    int seek = abs(left[i] - current_pos);
                    total_seek += seek;
                    cout << "从" << current_pos << "到" << left[i] << "，寻道距离：" << seek << endl;
                    current_pos = left[i];
                }
            }
        } else {
            // 向下走：处理左侧请求
            for (int i = left.size() - 1; i >= 0; --i) {
                int seek = abs(left[i] - current_pos);
                total_seek += seek;
                cout << "从" << current_pos << "到" << left[i] << "，寻道距离：" << seek << endl;
                current_pos = left[i];
            }
            // 走到最内侧柱面
            if (!right.empty()) {
                int seek = abs(current_pos - 0);
                total_seek += seek;
                cout << "从" << current_pos << "到0，寻道距离：" << seek << endl;
                current_pos = 0;
                // 反向处理右侧请求
                for (size_t i = 0; i < right.size(); ++i) {
                    int seek = abs(right[i] - current_pos);
                    total_seek += seek;
                    cout << "从" << current_pos << "到" << right[i] << "，寻道距离：" << seek << endl;
                    current_pos = right[i];
                }
            }
        }
        return total_seek;
    }
};

// 测试磁盘调度算法
void test_scheduling() {
    // 磁道请求序列
    vector<int> requests;
    requests.push_back(98);
    requests.push_back(183);
    requests.push_back(37);
    requests.push_back(122);
    requests.push_back(14);
    requests.push_back(124);
    requests.push_back(65);
    requests.push_back(67);

    // 初始磁头位置：53，最大柱面数：199
    DiskScheduling ds(53);

    // FCFS
    int fcfs_seek = ds.fcfs(requests);
    cout << "FCFS总寻道距离：" << fcfs_seek << endl;

    // 重置磁头位置
    DiskScheduling ds2(53);
    // SSTF
    int sstf_seek = ds2.sstf(requests);
    cout << "SSTF总寻道距离：" << sstf_seek << endl;

    // 重置磁头位置
    DiskScheduling ds3(53);
    // SCAN（向上）
    int scan_seek = ds3.scan(requests, 199, true);
    cout << "SCAN总寻道距离：" << scan_seek << endl;
}

int main() {
    test_scheduling();
    return 0;
}

代码说明

1. 核心算法：实现 FCFS（简单遍历）、SSTF（找最近请求）、SCAN（电梯算法），计算总寻道距离；
2. 关键逻辑：SSTF 通过遍历找最短寻道请求，SCAN 按方向处理请求后反向；
3. 测试用例：采用经典的磁道请求序列（53→98→183→37→122→14→124→65→67），可直观对比不同算法的寻道效率。

8.4 提高磁盘可靠性的技术

        磁盘是易损硬件，核心目标是防止数据丢失、提升容错能力，常见技术如下：

核心技术

1. 磁盘镜像（RAID 1）：将数据同时写入两个磁盘（主盘 + 镜像盘），一个损坏另一个可用，缺点是磁盘利用率 50%；
2. 磁盘条带化（RAID 0）：将数据分块存储到多个磁盘，并行 I/O 提升速度，但无容错（一块损坏则数据全丢）；
3. RAID 5：结合条带化和奇偶校验，至少 3 块磁盘，奇偶校验信息分布在不同磁盘，容错且利用率高（n-1/n）；
4. 热备份（热插拔）：磁盘故障时，备用磁盘自动替换故障盘，无需停机；
5. 数据备份与恢复：定期备份数据到离线介质（如磁带、云存储）。

综合案例：模拟 RAID 5 奇偶校验计算（C++98 代码）

#include <iostream>
#include <vector>
#include <string>
// 严格C++98
#if __cplusplus >= 201103L
#error "请使用C++98标准编译！"
#endif

using namespace std;

// RAID 5奇偶校验管理器
class RAID5Manager {
private:
    int disk_count;  // 磁盘数量（至少3）
    // 修复：C++98中嵌套模板的>>必须拆分为> >
    vector<vector<unsigned char> > disk_data;

    // 异或校验计算（RAID 5核心：奇偶校验位=所有数据位异或）
    unsigned char xor_check(const vector<unsigned char>& data) {
        unsigned char check = 0;
        for (size_t i = 0; i < data.size(); ++i) {
            check ^= data[i];
        }
        return check;
    }

public:
    // 初始化：disk_count块磁盘，每个磁盘有block_count个块
    RAID5Manager(int disks, int block_count) : disk_count(disks) {
        if (disks < 3) {
            cout << "RAID 5至少需要3块磁盘！自动设置为3块。" << endl;
            disk_count = 3;
        }
        // 初始化磁盘数据
        disk_data.resize(disk_count);
        for (int i = 0; i < disk_count; ++i) {
            disk_data[i].resize(block_count, 0);
        }
    }

    // 写入数据块，并计算奇偶校验
    // data：要写入的数据块（数量=disk_count-1）
    // block_idx：写入的块索引
    void write_block(const vector<unsigned char>& data, int block_idx) {
        if (block_idx < 0 || block_idx >= (int)disk_data[0].size()) {
            cout << "块索引非法！" << endl;
            return;
        }
        if ((int)data.size() != disk_count - 1) {
            cout << "数据块数量必须为" << disk_count - 1 << "！" << endl;
            return;
        }

        // 确定校验块的位置（轮询分布：block_idx % disk_count）
        int check_disk = block_idx % disk_count;
        cout << "\n写入块" << block_idx << "，校验块位置：磁盘" << check_disk << endl;

        // 写入数据块
        int data_idx = 0;
        for (int i = 0; i < disk_count; ++i) {
            if (i == check_disk) {
                continue;  // 校验盘先不写
            }
            disk_data[i][block_idx] = data[data_idx++];
        }

        // 收集数据块计算校验值
        vector<unsigned char> temp_data;
        for (int i = 0; i < disk_count; ++i) {
            if (i != check_disk) {
                temp_data.push_back(disk_data[i][block_idx]);
            }
        }
        unsigned char check_val = xor_check(temp_data);
        // 写入校验值
        disk_data[check_disk][block_idx] = check_val;

        cout << "数据写入完成，校验值：" << (int)check_val << endl;
    }

    // 模拟磁盘故障，恢复数据
    // failed_disk：故障磁盘编号
    // block_idx：要恢复的块索引
    void recover_disk(int failed_disk, int block_idx) {
        if (failed_disk < 0 || failed_disk >= disk_count) {
            cout << "故障磁盘编号非法！" << endl;
            return;
        }
        if (block_idx < 0 || block_idx >= (int)disk_data[0].size()) {
            cout << "块索引非法！" << endl;
            return;
        }

        cout << "\n恢复故障磁盘" << failed_disk << "的块" << block_idx << endl;

        // 收集其他磁盘的块数据（包括校验块）
        vector<unsigned char> temp_data;
        for (int i = 0; i < disk_count; ++i) {
            if (i != failed_disk) {
                temp_data.push_back(disk_data[i][block_idx]);
            }
        }

        // 异或计算恢复故障块数据
        unsigned char recovered_data = xor_check(temp_data);
        disk_data[failed_disk][block_idx] = recovered_data;

        cout << "恢复完成，故障块数据：" << (int)recovered_data << endl;
    }

    // 打印磁盘数据
    void print_disk_data() {
        cout << "\nRAID 5磁盘数据：" << endl;
        for (int i = 0; i < disk_count; ++i) {
            cout << "磁盘" << i << "：";
            for (size_t j = 0; j < disk_data[i].size(); ++j) {
                cout << (int)disk_data[i][j] << " ";
            }
            cout << endl;
        }
    }
};

// 测试RAID 5
void test_raid5() {
    // 初始化：4块磁盘，每个磁盘5个块
    RAID5Manager raid5(4, 5);

    // 写入第一组数据（3个数据块）
    vector<unsigned char> data1;
    data1.push_back(0x12);  // 18
    data1.push_back(0x34);  // 52
    data1.push_back(0x56);  // 86
    raid5.write_block(data1, 0);

    // 写入第二组数据
    vector<unsigned char> data2;
    data2.push_back(0x78);  // 120
    data2.push_back(0x9A);  // 154
    data2.push_back(0xBC);  // 188
    raid5.write_block(data2, 1);

    raid5.print_disk_data();

    // 模拟磁盘1故障，恢复块0
    raid5.recover_disk(1, 0);
    raid5.print_disk_data();
}

int main() {
    test_raid5();
    return 0;
}

代码说明

1. RAID 5 核心：通过异或校验实现容错，校验块轮询分布在不同磁盘，避免单块校验盘瓶颈；
2. 关键函数：xor_check计算异或校验值，write_block写入数据并生成校验块，recover_disk模拟故障恢复；
3. 恢复逻辑：利用异或的可逆性（A^B^C=P → A=B^C^P），通过剩余磁盘数据恢复故障盘数据。

8.5 数据一致性控制

        多进程 / 线程读写磁盘数据时，易出现数据不一致（如写一半断电），核心目标是保证数据的原子性、一致性、持久性。

核心技术

1. 事务（Transaction）：将一组操作封装为原子单元，要么全执行，要么全不执行；
2. 日志（Journaling）：先写操作日志到磁盘，再执行实际操作，故障时通过日志恢复；
3. 检查点（Checkpoint）：定期将内存中的修改刷到磁盘，减少故障恢复时间；
4. 写前日志（WAL, Write-Ahead Logging）：修改数据前先写日志，确保日志落盘后再改数据。

流程图

综合案例：模拟 WAL 写前日志（C++98 代码）

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
// 严格C++98
#if __cplusplus >= 201103L
#error "请使用C++98标准编译！"
#endif

using namespace std;

// 日志操作类型
enum LogType {
    INSERT,  // 插入
    UPDATE,  // 更新
    DELETE   // 删除
};

// 日志条目
struct LogEntry {
    LogType type;       // 操作类型
    int record_id;      // 记录ID
    string old_data;    // 旧数据（更新/删除时用）
    string new_data;    // 新数据（插入/更新时用）
    bool is_committed;  // 是否已提交

    // C++98构造函数
    LogEntry() : type(INSERT), record_id(0), is_committed(false) {}
    LogEntry(LogType t, int id, const string& old_d, const string& new_d) 
        : type(t), record_id(id), old_data(old_d), new_data(new_d), is_committed(false) {}
};

// WAL管理器
class WALManager {
private:
    vector<LogEntry> log;          // 内存日志
    vector<string> data_store;     // 模拟数据存储
    string log_file_path;          // 日志文件路径

    // 将日志写入文件（模拟落盘）
    void write_log_to_disk() {
        ofstream log_file(log_file_path.c_str(), ios::app);  // C++98需转const char*
        if (!log_file.is_open()) {
            cout << "日志文件打开失败！" << endl;
            return;
        }
        // 写入未提交的日志
        for (size_t i = 0; i < log.size(); ++i) {
            if (!log[i].is_committed) {
                log_file << log[i].type << " " << log[i].record_id << " "
                         << log[i].old_data << " " << log[i].new_data << endl;
                log[i].is_committed = true;  // 标记为已提交
            }
        }
        log_file.close();
    }

public:
    // 初始化
    WALManager(const string& log_path) : log_file_path(log_path) {
        // 初始化数据存储（10个空记录）
        data_store.resize(10, "");
    }

    // 插入数据（WAL流程）
    bool insert(int record_id, const string& data) {
        if (record_id < 0 || record_id >= (int)data_store.size()) {
            cout << "记录ID非法！" << endl;
            return false;
        }
        // 1. 创建日志条目
        LogEntry entry(INSERT, record_id, "", data);
        log.push_back(entry);

        // 2. 写日志到磁盘
        write_log_to_disk();

        // 3. 修改内存数据
        data_store[record_id] = data;
        cout << "插入记录" << record_id << "成功，数据：" << data << endl;
        return true;
    }

    // 更新数据（WAL流程）
    bool update(int record_id, const string& new_data) {
        if (record_id < 0 || record_id >= (int)data_store.size()) {
            cout << "记录ID非法！" << endl;
            return false;
        }
        // 1. 保存旧数据
        string old_data = data_store[record_id];
        // 2. 创建日志条目
        LogEntry entry(UPDATE, record_id, old_data, new_data);
        log.push_back(entry);

        // 3. 写日志到磁盘
        write_log_to_disk();

        // 4. 修改内存数据
        data_store[record_id] = new_data;
        cout << "更新记录" << record_id << "成功，新数据：" << new_data << endl;
        return true;
    }

    // 故障恢复：从日志恢复数据
    void recover() {
        cout << "\n===== 开始故障恢复 =====" << endl;
        ifstream log_file(log_file_path.c_str());  // C++98需转const char*
        if (!log_file.is_open()) {
            cout << "日志文件不存在，无需恢复！" << endl;
            return;
        }

        // 读取日志并恢复
        int type, record_id;
        string old_data, new_data;
        while (log_file >> type >> record_id >> old_data >> new_data) {
            LogType log_type = (LogType)type;
            switch (log_type) {
                case INSERT:
                    data_store[record_id] = new_data;
                    cout << "恢复插入：记录" << record_id << "，数据：" << new_data << endl;
                    break;
                case UPDATE:
                    data_store[record_id] = new_data;
                    cout << "恢复更新：记录" << record_id << "，新数据：" << new_data << endl;
                    break;
                case DELETE:
                    data_store[record_id] = "";
                    cout << "恢复删除：记录" << record_id << endl;
                    break;
                default:
                    cout << "无效日志类型！" << endl;
                    break;
            }
        }
        log_file.close();
        cout << "恢复完成！" << endl;
    }

    // 打印数据存储
    void print_data() {
        cout << "\n当前数据存储：" << endl;
        for (size_t i = 0; i < data_store.size(); ++i) {
            cout << "记录" << i << "：" << data_store[i] << endl;
        }
    }
};

// 测试WAL
void test_wal() {
    // 日志文件路径（当前目录）
    WALManager wal("wal_log.txt");

    // 插入数据
    wal.insert(1, "user1:张三");
    wal.insert(2, "user2:李四");

    // 更新数据
    wal.update(1, "user1:张三丰");

    wal.print_data();

    // 模拟故障，恢复数据
    wal.recover();
    wal.print_data();
}

int main() {
    test_wal();
    return 0;
}

代码说明

1. WAL 核心流程：先写日志→日志落盘→修改内存数据→异步刷盘，保证故障时可通过日志恢复；
2. 关键函数：write_log_to_disk模拟日志落盘，recover从日志文件恢复数据；
3. 兼容性：C++98 的文件操作需用const char*（c_str()），无 C++11 的 string 直接传参。

习题

1. 编程题：基于 8.2 的位示图代码，实现空闲链表法的磁盘空间管理；
2. 简答题：对比 SCAN 和 C-SCAN 算法的优缺点，为什么 C-SCAN 更适合 SSD？
3. 实操题：修改 8.4 的 RAID 5 代码，模拟两块磁盘故障的场景（说明为什么 RAID 5 不支持两块盘故障）；
4. 分析题：为什么写前日志（WAL）能保证数据一致性？结合代码说明核心流程。

总结

1. 外存组织方式核心是连续、链接、索引分配，各有优劣，代码可模拟块的分配与释放；
2. 磁盘 I/O 优化的核心是减少寻道时间（调度算法）、利用缓存 / 预读，可靠性依赖 RAID 等容错技术；
3. 数据一致性控制的关键是原子性（事务）、持久性（日志），WAL 是最常用的实现方式；
4. 所有代码均严格遵循 C++98 标准，可直接编译运行，覆盖每个知识点的核心应用场景。

运行说明

1. 编译命令：g++ -std=c++98 文件名.cpp -o 可执行文件名；
2. 运行：./可执行文件名（Linux/Mac）或可执行文件名.exe（Windows）；
3. 注意：WAL 案例会生成日志文件，运行前确保当前目录有写权限。

        希望本文能帮助大家吃透磁盘存储器管理的核心知识点，代码可直接动手实操，有问题欢迎评论区交流！