操作系统实验

,

实验三：存储器管理

一、实验目的

本次实验旨在通过使用操作系统内存分配信息的动态观察以及存储器管理算法的实现，加深对内存分配原理的理解（重点加深对请求式分页存储管理方式的理解）。同时通过相关算法的实现，熟悉页面置换算法及其性能。

二、实验内容

  1. 使用 taskmgr.exe 观察实验环境中的进程生命周期内系统内存分配变化情
    况；
  2. 编程实现请求分页管理方式时的地址变换过程；
  3. 编程实现 OPT 或者 FIFO 算法
  4. 编程实现 LRU 算法；

三、思考题

  1. OPT 算法是否具备实用性？
  2. OPT 算法与 LRU 算法的区别是什么？
  3. 虚拟存储器的主要特征有哪些？

一、地址转换过程实现

请求分页管理方式时，需要将逻辑地址转换为物理地址。通常涉及页面号和偏移量的计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>

using namespace std;

int addressTranslation(int logicalAddress, int pageSize, const vector<int>& pageTable) {
    int pageNumber = logicalAddress / pageSize;  // 页面号
    int offset = logicalAddress % pageSize;      // 偏移量

    if (pageNumber >= pageTable.size()) {
        cout << "错误：页号超出范围！" << endl;
        return -1;
    }

    int physicalAddress = pageTable[pageNumber] * pageSize + offset;
    return physicalAddress;
}

int main() {
    vector<int> pageTable = {2, 4, 1, 7};  // 模拟页表
    int pageSize = 1024;                   // 假设页面大小为1024字节
    
    int logicalAddress = 2048;  // 输入逻辑地址
    int physicalAddress = addressTranslation(logicalAddress, pageSize, pageTable);
    
    if (physicalAddress != -1) {
        cout << "逻辑地址 " << logicalAddress << " 对应的物理地址是：" << physicalAddress << endl;
    }

    return 0;
}

解释：

  1. 页表记录了每个页面在物理内存中的帧号。
  2. 通过 逻辑地址 / 页面大小 得到页面号，逻辑地址 % 页面大小 得到偏移量。
  3. 页表转换后返回物理地址。

结果：

1
逻辑地址 2048 对应的物理地址是：1024

二、FIFO 页面置换算法

FIFO（First-In-First-Out，先进先出）页面置换算法的逻辑是：

  1. 页面进入内存后，它们会按顺序存入一个队列，最早进入的页面最先被替换。
  2. 如果内存已满，当需要加载一个新的页面时，会将最早进入的页面（队列的第一个）移除，再将新的页面加入队列。
  3. 每当访问的页面不在内存中（缺页）时，会触发一次缺页中断，并增加缺页次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <queue>
#include <map>

using namespace std;

void FIFOPageReplacement(int pages[], int n, int capacity) {
    map<int, bool> s;  // 当前内存中的页（使用 map 实现）
    queue<int> indexes; // 实现FIFO队列
    int pageFaults = 0; // 记录缺页次数

    // 遍历pages数组中的每个页面
    for (int i = 0; i < n; i++) {
        // 使用 count 检查页面是否在内存中
        if (s.count(pages[i]) == 0) {
            // 如果内存已满
            if (s.size() == capacity) {
                int val = indexes.front();  
                indexes.pop();
                s.erase(val);  // 从map中删除最早进入的页面
            }

            // 加入新页面
            s[pages[i]] = true;  // map 插入新页面
            indexes.push(pages[i]);

            // 增加缺页次数
            pageFaults++;
        }

        cout << "访问页面 " << pages[i] << "，当前内存：";
        for (auto page : s) cout << page.first << " ";  // 打印页面
        cout << endl;
    }

    cout << "总缺页次数：" << pageFaults << endl;
}

int main() {
    int pages[] = {1, 3, 0, 3, 5, 6, 3};  // 页面序列
    int n = sizeof(pages) / sizeof(pages[0]);
    int capacity = 3;  // 内存容量为 3

    FIFOPageReplacement(pages, n, capacity);
    
    return 0;
}

部分代码解释：
count() 函数：

  • s.count(pages[i]) 返回值：
    • 如果页面 pages[i] 存在，返回 1。
    • 如果页面 pages[i] 不存在，返回 0。

结果：

1
2
3
4
5
6
7
8
访问页面 1，当前内存：1
访问页面 3，当前内存：1 3
访问页面 0，当前内存：0 1 3
访问页面 3，当前内存：0 1 3
访问页面 5，当前内存：0 3 5
访问页面 6，当前内存：0 5 6
访问页面 3，当前内存：3 5 6
总缺页次数：6

三、OPT页面置换算法

  1. 原理：OPT算法的核心思想是，当内存已满且需要替换页面时，选择一个未来最晚被访问的页面进行替换，因为该页面将在最长时间内不会被访问，因此将其替换会减少未来的缺页次数。
  • 判断是否需要置换：
    • 当一个页面请求到达时，检查该页面是否已经在内存中。
    • 如果页面已经在内存中，继续下一请求；否则产生一次缺页中断。
  • 选择置换页面：
    • 对每个在内存中的页面，预测其未来的访问情况。
    • 找出内存中未来最晚再被访问的页面（即在当前请求后最久才会再次被访问的页面）。
    • 将该页面替换成当前请求的页面。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>

using namespace std;

void OPTPageReplacement(int pages[], int n, int capacity) {
    vector<int> s;  // 当前内存中的页
    int pageFaults = 0;  // 记录缺页次数

    for (int i = 0; i < n; i++) {
        // 检查页面是否已经在内存中
        auto it = find(s.begin(), s.end(), pages[i]);
        if (it == s.end()) {
            // 页面不在内存中，缺页发生
            if (s.size() == capacity) {
                // 内存已满，找到未来最晚访问的页面并替换
                int farthest = -1, indexToReplace = -1;
                for (int j = 0; j < s.size(); j++) {
                    int nextUse = n;  // 假设页面不会再被访问
                    for (int k = i + 1; k < n; k++) {
                        if (s[j] == pages[k]) {
                            nextUse = k;
                            break;
                        }
                    }
                    if (nextUse > farthest) {
                        farthest = nextUse;
                        indexToReplace = j;
                    }
                }
                s[indexToReplace] = pages[i];
            }
            else {
                s.push_back(pages[i]);
            }
            pageFaults++;
        }

        cout << "访问页面 " << pages[i] << "，当前内存：";
        for (int page : s) cout << page << " ";
        cout << endl;
    }

    cout << "总缺页次数：" << pageFaults << endl;
}

int main() {
    int pages[] = { 1, 3, 0, 3, 5, 6, 3 };  // 页面序列
    int n = sizeof(pages) / sizeof(pages[0]);
    int capacity = 3;  // 内存容量为 3

    OPTPageReplacement(pages, n, capacity);

    return 0;
}

核心代码部分：如何找到未来最晚访问的页面并替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if (s.size() == capacity) {
    // 内存已满，找到未来最晚访问的页面并替换
    int farthest = -1, indexToReplace = -1;
    for (int j = 0; j < s.size(); j++) {
        int nextUse = n;  // 假设页面不会再被访问
        for (int k = i + 1; k < n; k++) {
            if (s[j] == pages[k]) {
                nextUse = k;
                break;
            }
        }
        if (nextUse > farthest) {
            farthest = nextUse;
            indexToReplace = j;
        }
    }
    s[indexToReplace] = pages[i];
}

解释：

  1. 首先检查内存是否已满，只有在内存已满的情况下才会进行替换。

  2. 然后，通过遍历内存中的每个页面，找出它们在未来的访问序列中最后一次被访问的时间。

  3. 比较所有页面的最后访问时间，选择最晚被访问的页面进行替换。

  4. 最后，替换掉最晚访问的页面，并把当前页面加载到内存中。

详细：

  • farthest 用来记录未来最晚被访问的页面的访问时间索引。初始值设为 -1，因为我们假设没有页面被访问（较大的访问时间）。
  • indexToReplace 用来记录最晚被访问页面的索引。我们用它来确定替换哪个页面。
  • for循环遍历当前内存中的所有页面
  • nextUse 记录页面 s[j] 在未来的下次访问时间。初始化为 n（表示页面从未访问），假设页面之后不会再被访问。
  • for (int k = i + 1; k < n; k++) 这是一个内部循环，用来检查页面 s[j] 在未来的页面访问序列中的位置。
  • if (s[j] == pages[k]) { nextUse = k; break; } 如果当前内存中的页面 s[j] 与未来的页面 pages[k] 相同，表示页面 s[j] 在时间 k 被访问。我们将 nextUse 更新为 k，表示页面 s[j] 下次被访问的时间。
  • if (nextUse > farthest) { farthest = nextUse; indexToReplace = j; }这个 if 判断找到了未来最晚被访问的页面。

结果：

1
2
3
4
5
6
7
8
访问页面 1，当前内存：1
访问页面 3，当前内存：1 3
访问页面 0，当前内存：1 3 0
访问页面 3，当前内存：1 3 0
访问页面 5，当前内存：5 3 0
访问页面 6，当前内存：6 3 0
访问页面 3，当前内存：6 3 0
总缺页次数：5

四、LRU 页面置换算法

LRU 页面置换算法用于内存管理中，在页面调度时会优先替换最近最少使用的页面。算法的基本逻辑是：

  1. 当页面访问请求到来时：
    • 如果页面在内存中，则直接访问并更新该页面的最近使用时间。
    • 如果页面不在内存中（缺页），则执行以下操作：
      • 若内存未满，将页面直接加载到内存。
      • 若内存已满，找出最近最少使用的页面并将其替换。
  2. 页面访问时间记录：LRU 需要跟踪每个页面的最后一次访问时间，用于找出需要替换的页面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <unordered_map>
#include <climits>  // for INT_MAX

using namespace std;

void LRUPageReplacement(int pages[], int n, int capacity) {
    unordered_map<int, int> indexes;  // 记录页面上次访问时间
    unordered_map<int, bool> s;       // 当前内存中的页
    int pageFaults = 0;               // 缺页次数

// i 代表页面的访问顺序（时间），也就是当前访问的时刻或步骤索引
    for (int i = 0; i < n; i++) {
        // 如果当前页不在内存中
        if (s.count(pages[i]) == 0) {
            // 如果内存已满
            if (s.size() == capacity) {
                int lru = INT_MAX, val;
                // 找到最久未使用的页面
                for (auto it : s) {
                    if (indexes[it.first] < lru) {
                        lru = indexes[it.first];
                        val = it.first;
                    }
                }

                // 替换最久未使用的页面
                s.erase(val);
                indexes.erase(val);
            }

            // 加入新页面
            s[pages[i]] = true;

            // 增加缺页次数
            pageFaults++;
        }

        // 更新当前页面的访问时间
        indexes[pages[i]] = i;

        cout << "访问页面 " << pages[i] << "，当前内存：";
        for (auto page : s) cout << page.first << " ";
        cout << endl;
    }

    cout << "总缺页次数：" << pageFaults << endl;
}

int main() {
    int pages[] = {1, 3, 0, 3, 5, 6, 3};  // 页面序列
    int n = sizeof(pages) / sizeof(pages[0]);
    int capacity = 3;  // 内存容量为 3

    LRUPageReplacement(pages, n, capacity);

    return 0;
}

部分解释：

  • unordered_map<int, int> indexes: 用于记录页面的上次访问时间。unordered_map 允许将页面号映射到它的访问时间索引，即页面号作为键，访问时间作为值。
  • unordered_map<int, bool> s: 用于表示当前内存中的页面集合。页面号作为键，bool 值表示该页面是否在内存中。unordered_map 提供 O(1) 时间复杂度的查找，因此适合高效检查页面是否在内存中。
  • indexes[it.first] 表示 indexes 中以 it.first（页面号）作为键来查找对应的最近访问时间。

结果：

1
2
3
4
5
6
7
8
访问页面 1，当前内存：1
访问页面 3，当前内存：1 3
访问页面 0，当前内存：1 3 0
访问页面 3，当前内存：1 3 0
访问页面 5，当前内存：3 0 5
访问页面 6，当前内存：3 5 6
访问页面 3，当前内存：3 5 6
总缺页次数：5

思考题

  1. OPT 算法是否具备实用性？

    • OPT（Optimal）算法理论上是最优的，因为它总是淘汰未来最晚被访问的页面。然而在实际系统中无法预知未来，因此 OPT 算法不具备实用性。

  2. OPT 算法与 LRU 算法的区别是什么？

    • OPT 算法根据未来的页面访问情况进行页面替换，而LRU 算法根据过去的页面访问记录来进行替换。OPT 是理想状态，而 LRU 是可实现的近似方案。

  3. 虚拟存储器的主要特征有哪些？

    • 虚拟存储器的特征包括：程序可以不完全装入内存即可运行；通过页表实现虚拟地址和物理地址的映射；通过页面置换技术提高内存利用率。

实验四：文件管理

一、实验目的

本次实验旨在通过实践了解文件管理原理与方法，重点加深对外存分配方式和文件空闲存储空间的理解。

二、实验内容

  1. 了解使用计算机系统的文件系统的格式；

  2. 编程实现连续分配、链接分配、索引分配等三种外存分配方式；

  3. 编程实现空闲表法、位示图法连续分配、成组链接法等三种文件存储空间

管理方式

三、实验组织运行要求

根据本实验的特点、要求和具体条件，宜采用“以学生自主训练为主的开放模式组织教学”。相关材料可以以书面资料（或电子版本）的形式分发给学生。学生自主练习、提问；教师针对性的辅导。本次实验内容很多，阈于课时限制，编程可能无法全部完成。对实验内容中 2）、3）（外存分配方式、文件存储空间管理方式）要求的 6 个编程要求，可以分成：
a) 连续分配与链接分配、
b) 索引分配、
c) 空闲表法与位示图法连续分配、
d) 成组链接法等四组
要求在实验课时内至少完成一组的编程。

四、思考题

  1. 实验使用的计算机系用中，术语文件夹与文件管理中的概念一致？

  2. 连续分配、链接分配、索引分配等三种外存分配方式的特点以及彼此之间的差异是什么？

  3. 空闲表法、位示图法连续分配、成组链接法三种文件存储空间管理方式的特点以及彼此之间的差异有哪些？

a) 连续分配与链接分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 磁盘块数量定义为常量
const int DISK_SIZE = 100;

// 模拟磁盘：数组表示磁盘，每个元素代表一个磁盘块
// -1 表示空闲块，非负值表示被文件占用（存储文件ID或链表指针）
int disk[DISK_SIZE];

// 初始化磁盘块，将所有块标记为空闲
void initializeDisk() {
    for (int i = 0; i < DISK_SIZE; ++i) {
        disk[i] = -1; // 初始化时所有磁盘块未分配，设置为 -1
    }
}

// 显示当前磁盘状态
void displayDisk() {
    cout << "Disk Status: [ ";
    for (int i = 0; i < DISK_SIZE; ++i) {
        cout << disk[i] << " "; // 打印每个磁盘块的状态
    }
    cout << "]" << endl;
}

// 连续分配实现
bool contiguousAllocation(int fileID, int fileSize) {
    int start = -1; // 起始位置初始化为 -1，表示未找到起始空闲块
    int count = 0;  // 记录当前连续空闲块的数量

    // 遍历磁盘寻找足够大的连续空闲区域
    for (int i = 0; i < DISK_SIZE; ++i) {
        if (disk[i] == -1) { // 如果当前块是空闲的
            if (start == -1) start = i; // 如果这是第一块空闲块，记录起始位置
            count++; // 计数连续空闲块
            if (count == fileSize) break; // 如果找到足够大小的区域，停止搜索
        }
        else {
            // 遇到非空闲块，重置起始位置和计数器
            start = -1;
            count = 0;
        }
    }

    // 如果找到足够的空闲块，进行分配
    if (count == fileSize) {
        for (int i = start; i < start + fileSize; ++i) {
            disk[i] = fileID; // 将这些块分配给文件
        }
        cout << "File " << fileID << " 使用连续分配进行分配从 " << start << " 到 " << start + fileSize - 1 << endl;
        return true; // 分配成功
    }
    else {
        // 如果没有足够的连续空闲块，分配失败
        cout << "文件的连续分配失败 " << fileID << endl;
        return false;
    }
}

// 链接分配实现
bool linkedAllocation(int fileID, int fileSize) {
    vector<int> allocatedBlocks; // 用于存储分配的块号
    for (int i = 0; i < DISK_SIZE && allocatedBlocks.size() < fileSize; ++i) {
        if (disk[i] == -1) { // 如果当前块是空闲的
            allocatedBlocks.push_back(i); // 将其加入分配的块号列表
        }
    }

    // 如果找到足够的块，进行链接分配
    if (allocatedBlocks.size() == fileSize) {
        for (size_t i = 0; i < allocatedBlocks.size(); ++i) {
            // 将块标记为分配，指向下一个块
            disk[allocatedBlocks[i]] = (i < allocatedBlocks.size() - 1) ? allocatedBlocks[i + 1] : 0; // 0 表示文件结束
        }
        // 打印分配结果
        cout << "File " << fileID << " 使用链式分配方式分配。块为: ";
        for (int block : allocatedBlocks) {
            cout << block << " "; // 打印分配的块号
        }
        cout << endl;
        return true; // 分配成功
    }
    else {
        // 如果块不足，分配失败
        cout << "文件链接分配失败 " << fileID << endl;
        return false;
    }
}

int main() {
    initializeDisk(); // 初始化磁盘状态
    displayDisk();    // 显示初始磁盘状态

    // 测试连续分配
    contiguousAllocation(1, 10); // 为文件ID为1的文件分配10个连续块
    displayDisk(); // 显示磁盘状态

    // 测试链接分配
    linkedAllocation(2, 5); // 为文件ID为2的文件分配5个链接块
    displayDisk(); // 显示磁盘状态

    // 再次测试分配
    contiguousAllocation(3, 15); // 测试另一个连续分配
    linkedAllocation(4, 7);      // 测试另一个链接分配
    displayDisk(); // 显示磁盘状态

    return 0; // 程序结束
}

b) 索引分配

索引分配是一种文件分配方式，在这种方式中，文件的每个块都有一个指针，指向该块在磁盘上的物理地址。一个索引块记录了文件所有数据块的地址。每个文件都有一个单独的索引块，它存储了文件所有数据块的指针。如果文件较大，索引块可能会分为多个层级（多级索引）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Disk {
public:
    vector<int> disk;         // 磁盘块
    unordered_map<int, vector<int>> indexTable;  // 存储每个文件的索引块（文件ID -> 数据块地址）

    Disk(int size) {
        disk.resize(size, -1);  // 初始化磁盘块（-1表示空闲）
    }

    // 索引分配方法
    bool allocate(int fileID, int blocksNeeded) {
        vector<int> allocatedBlocks; // 记录已分配的块
        int allocated = 0;  // 已分配块数

        for (int i = 0; i < disk.size(); i++) {
            if (disk[i] == -1 && allocated < blocksNeeded) { // 如果磁盘块空闲
                disk[i] = fileID;  // 分配磁盘块给文件
                allocatedBlocks.push_back(i); // 记录已分配的块
                allocated++;
            }
        }

        if (allocated == blocksNeeded) {
            indexTable[fileID] = allocatedBlocks; // 将分配的块存入索引表
            cout << "文件 " << fileID << " 分配成功。" << endl;
            return true;
        }
        else {
            cout << "文件 " << fileID << " 分配失败，磁盘空间不足。" << endl;
            return false;
        }
    }

    void displayDisk() {
        cout << "磁盘块分配情况: ";
        for (int i = 0; i < disk.size(); i++) {
            cout << disk[i] << " ";
        }
        cout << endl;
    }

    void displayIndexTable() {
        cout << "文件索引表: " << endl;
        for (auto& entry : indexTable) {
            cout << "文件ID: " << entry.first << " -> 块号: ";
            for (int block : entry.second) {
                cout << block << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Disk disk(10);  // 创建一个包含10个块的磁盘

    // 为文件1分配4个块
    disk.allocate(1, 4);
    disk.displayDisk();   // 输出磁盘块分配情况
    disk.displayIndexTable(); // 输出文件的索引表

    // 为文件2分配3个块
    disk.allocate(2, 3);
    disk.displayDisk();
    disk.displayIndexTable();

    return 0;
}

c) 空闲表法与位示图法连续分配

空闲链表：
在空闲表法中，我们使用一个表来表示磁盘块的分配状态。每个磁盘块的状态可以是“已分配”或“空闲”。如果某个块被分配了，它将在空闲表中被标记为已分配，否则标记为空闲。

位视图法：
在位示图法中，我们使用一个位图来表示磁盘块的分配状态。每个磁盘块对应一个位，如果该块被分配，则对应的位为1，如果是空闲的，则对应的位为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <vector>

using namespace std;

// 磁盘块和位图
const int DISK_SIZE = 100;
int disk[DISK_SIZE];
int bitMap[DISK_SIZE]; // 位示图，1表示已占用，0表示空闲

// 空闲表
vector<pair<int, int>> freeTable; // 每对表示 <起始块, 块数>

// 初始化磁盘
void initializeDisk() {
    for (int i = 0; i < DISK_SIZE; ++i) {
        disk[i] = -1;
        bitMap[i] = 0; // 所有块空闲
    }
    freeTable.push_back({ 0, DISK_SIZE }); // 整个磁盘起始空闲
}


// 显示空闲表
void displayFreeTable() {
    cout << "空闲表: " << endl;
    for (auto& entry : freeTable) {
        cout << "起始块: " << entry.first << ", 长度: " << entry.second << endl;
    }
}

// 空闲表分配
bool freeTableAllocation(int fileID, int fileSize) {
    for (auto it = freeTable.begin(); it != freeTable.end(); ++it) {
        if (it->second >= fileSize) { // 找到足够大的空闲段
            int start = it->first;
            for (int i = start; i < start + fileSize; ++i) {
                disk[i] = fileID; // 分配给文件
            }
            // 更新空闲表
            it->first += fileSize;
            it->second -= fileSize;
            if (it->second == 0) freeTable.erase(it); // 如果段被用完，删除
            cout << "文件 " << fileID << " 使用空闲表分配成功，起始块: " << start << endl;
            return true;
        }
    }
    cout << "空闲表分配失败：磁盘空间不足！" << endl;
    return false;
}

// 显示位示图
void displayBitMap() {
    cout << "位示图: [ ";
    for (int i = 0; i < DISK_SIZE; ++i) {
        cout << bitMap[i] << " ";
    }
    cout << "]" << endl;
}

// 位示图分配
bool bitMapAllocation(int fileID, int fileSize) {
    int count = 0, start = -1;
    for (int i = 0; i < DISK_SIZE; ++i) {
        if (bitMap[i] == 0) { // 找到空闲块
            if (start == -1) start = i;
            count++;
            if (count == fileSize) break;
        }
        else {
            start = -1;
            count = 0;
        }
    }
    if (count == fileSize) {
        for (int i = start; i < start + fileSize; ++i) {
            disk[i] = fileID;
            bitMap[i] = 1; // 更新位图
        }
        cout << "文件 " << fileID << " 使用位示图分配成功，起始块: " << start << endl;
        return true;
    }
    else {
        cout << "位示图分配失败：磁盘空间不足！" << endl;
        return false;
    }
}

int main() {
    // 初始化磁盘和位示图
    initializeDisk();

    // 显示初始化状态
    cout << "初始化状态:" << endl;
    displayBitMap();
    displayFreeTable();

    // 分配文件 1，大小为 20
    cout << "\n分配文件 1 (大小 20):" << endl;
    freeTableAllocation(1, 20);
    displayFreeTable();

    // 分配文件 2，大小为 15
    cout << "\n分配文件 2 (大小 15):" << endl;
    freeTableAllocation(2, 15);
    displayFreeTable();

    // 使用位示图分配文件 3，大小为 30
    cout << "\n分配文件 3 (大小 30) 使用位示图:" << endl;
    bitMapAllocation(3, 30);
    displayBitMap();

    // 使用位示图分配文件 4，大小为 40（可能失败）
    cout << "\n分配文件 4 (大小 40) 使用位示图:" << endl;
    bitMapAllocation(4, 40);
    displayBitMap();

    // 再次分配文件 5，大小为 10，尝试空闲表分配
    cout << "\n分配文件 5 (大小 10):" << endl;
    freeTableAllocation(5, 10);
    displayFreeTable();

    // 显示最终状态
    cout << "\n最终磁盘状态:" << endl;
    cout << "位示图:" << endl;
    displayBitMap();
    cout << "空闲表:" << endl;
    displayFreeTable();

    return 0;
}



d) 成组链接法

成组链接法是一种文件分配方式，它将文件分割成大小相等的块，并将文件的块按顺序进行分配，每个块除了指向下一个块的指针外，还记录一个块的组号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>

using namespace std;

class Disk {
public:
    vector<int> disk;      // 存储磁盘块
    vector<int> groupTable; // 存储每个块所属的组

    Disk(int size) {
        disk.resize(size, -1);  // 初始化磁盘块（-1表示空闲）
        groupTable.resize(size, -1);  // 初始化每个块的组号
    }

    bool allocate(int fileID, int blocksNeeded, int groupID) {
        int allocated = 0;  // 记录已分配的块数
        for (int i = 0; i < disk.size(); i++) {
            if (disk[i] == -1 && allocated < blocksNeeded) { // 块为空闲
                disk[i] = fileID;        // 将块分配给文件
                groupTable[i] = groupID; // 设置该块的组号
                allocated++;
            }
        }

        if (allocated == blocksNeeded) {
            cout << "文件 " << fileID << " 成功分配。" << endl;
            return true;
        } else {
            cout << "文件 " << fileID << " 分配失败，磁盘空间不足。" << endl;
            return false;
        }
    }

    void displayDisk() {
        cout << "磁盘块分配情况: ";
        for (int i = 0; i < disk.size(); i++) {
            cout << disk[i] << " ";
        }
        cout << endl;

        cout << "块的组号: ";
        for (int i = 0; i < groupTable.size(); i++) {
            cout << groupTable[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Disk disk(10);  // 创建一个包含10个块的磁盘
    disk.allocate(1, 3, 1); // 为文件1分配3个块，组号为1
    disk.displayDisk();
    disk.allocate(2, 5, 2); // 为文件2分配5个块，组号为2
    disk.displayDisk();

    return 0;
}

思考题

  1. 实验使用的计算机系用中，术语文件夹与文件管理中的概念一致？
    在实验计算机系统中，“文件夹”和“文件”的概念通常保持一致性，和实际操作系统中的定义类似：
  • 文件：表示存储在外存中的数据集合，由文件名和属性描述。每个文件都有逻辑结构和物理存储位置。
  • 文件夹：用于组织文件和其他文件夹，是一种逻辑结构，方便用户查找和管理文件。
  1. 连续分配、链接分配、索引分配等三种外存分配方式的特点以及彼此之间的差异是什么？
特性 连续分配 链接分配 索引分配
存储方式 文件存储在连续的物理块中 文件存储在链表结构中，块通过指针连接 一个索引块存储文件所有数据块的指针
优点 - 访问速度快（因为数据连续） - 无需连续块，空间利用率高 - 支持直接访问，文件可分布在任何位置
- 适合顺序和随机访问 - 动态分配灵活 - 动态分配灵活
缺点 - 需要找到足够大的连续空间 - 只适合顺序访问 - 索引块可能占用较多空间
- 文件扩展可能需要移动或重分配 - 额外的指针存储开销 - 索引结构增加了复杂性
访问方式 支持顺序和随机访问 仅支持顺序访问 支持随机和顺序访问
适用场景 小文件、对性能要求较高的场景 空间碎片多、动态扩展需求大的场景 大文件、需要频繁随机访问的场景
  • 差异总结：
    • 连续分配强调物理上连续，适合高效读写，但扩展性差。
    • 链接分配灵活，但只适合顺序访问。
    • 索引分配综合了两者的优点，支持随机访问，但索引块占用额外空间。
  1. 空闲表法、位示图法连续分配、成组链接法三种文件存储空间管理方式的特点以及彼此之间的差异有哪些？
特性 空闲表法 位示图法 成组链接法
实现方式 用表记录所有空闲块及其大小 使用位图记录每个块的状态（0=空闲，1=占用） 每组空闲块以链表连接，链表中记录若干空闲块
优点 - 适合大块连续空间分配 - 查找简单，适合小文件 - 查找大块空闲空间快，灵活性高
- 查找空闲空间较快 - 管理简单，空间开销小 - 空间利用率高，扩展性强
缺点 - 需要维护一张表，空间开销较大 - 顺序查找可能较慢 - 链表结构增加了复杂性
- 查找复杂度高于位示图 - 不适合大块连续分配 - 链表中可能有碎片
空间管理 记录空闲块的起始地址和大小 每个位表示一个块的状态 每组链接多个空闲块
适用场景 适合连续存储和大文件 适合分散的空间管理和小文件 适合需要动态管理和混合大小文件的场景
  • 差异总结：
    • 空闲表法适合管理连续大块空间，但需要维护额外的表。
    • 位示图法简单高效，适合小块分散分配，但查找连续大块时性能较差。
    • 成组链接法综合了两者优点，通过分组提高了查找效率，适合动态场景，但实现复杂。