操作系统：内存置换、分配与回收（LRU、最先适应算法、位示图算法）_最先适应算法流程图

一、实验题目：

实验三 实现最近最久未使用（LRU）置换算法。
实验六 主存储器空间的分配和回收。

二、实验目的：

一、实验三 实现最近最久未使用（LRU）置换算法：
1、LINUX 中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分调入内存便可运行，还支持请求调页的存储管理方式。
2、本实验要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
二、实验六 主存储器空间的分配和回收
通过本实验帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。

三、实验内容及操作步骤：

（一）实验三 实现最近最久未使用（LRU）置换算法：

1、最近最久未使用（LRU）置换算法原理
当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。
例如: 分配给该进程的页块数为 3，一个 20 位长的页面访问序列为：
1 2 5 6 0 3 6 5 3 6 5 6 0 4 2 7 0 4 3 5
则缺页次数和缺页率按下图给出:

2、算法举例
假定分配给该进程的页块数为 3，页面访问序列长度为 20。
本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用 LRU 算法，将当前一段时间内最久未使用过的页替换出去。模拟程序的算法如下图：

3、具体实现步骤：
（1）程序中使用的数据结构及符号说明：
算法的实现主要是依靠一些数组来完成，同时用一些变量进行辅助。算法中使用到的变量和数组的名称及其含义如下表所示：

（2）算法具体描述：
首先通过键盘输入读取内存块的最大数量和想要测试的页面访问序列的长度，因为是序列的形式输入，所以为了避免歧义，规定所有的页面编号只在 0~9 范围内。接着初始化内存块的内容均为未使用，我们用-1 来表示尚未分配，同时将所有的页设置成不在内存中。
接着就开始序列的依次读取，每次读取一个序列的位，然后调用核心的 LRU 算法，判断是否发生缺页，同时对内存中的块内容进行修改，并统计缺页次数，操作完成以后输出是否缺页的计算结果，并输出操作完成以后当前内存的内容。读取完序列的所有内容，并统计完成缺页的次数，就可以计算缺页率，最后将缺页率和缺页次数输出即可。
接下来对核心的 LRU 算法进行描述。首先这个算法当中比较重要的一部分就是这个保存内存内容的数组，为了方便每次的缺页替换，将这个数组设置成优先队列的形式，按照内存内容最后访问的时间先后进行排序，越靠前的内容最近被访问过，所以发生缺页的时候，如果需要替换，只要将排在最后的内容换出即可。
每次读取了序列的一位，表示需要访问的页号，就在内存当中寻找是否有这个页存在，由于采用了标记数组，所以直接查询即可知道是否在内存中。
如果需要的页在内存中，那么就不发生缺页，同时为了维持优先队列，由于刚刚访问了这个页，就需要在内存中找到这个页的位置，并逐个交换到队列的队首，表示最近一次访问过他，交换的时候不能改变其他的顺序，所以需要逐个交换到第一个。
如果不在内存中，那么就发生了缺页，就要将缺页的次数更新。这时候就要将这个页装入内存，分两种情况，如果内存已经满了，那么就把最后一个元素换成想要读取的页，然后把它逐个换到第一个位置上；如果内存没有满，那就先把他放到第一个空位上，更新内存中页的数量，然后把它交换到第一个位置上。放入内存并换到队首就完成了大部分的操作，然后标记这个页在内存中即可。最后输出内存中现在的内容即可继续读取下一个序列内容。
4、算法实现的源代码：

//LRU 算法
#include <iostream>
using namespace std;
//进程的页块数，缓冲区的大小
int n;
//页面访问序列的长度
int len;
//当前内存中存在的页数量
int cnt = 0;
//缺页的次数统计
int misstime = 0;
//缺页率
double misscent = 0.0;
//内存中对应的进程页内容
int memory[1001];
//进程需要的页是否在内存中的标记
bool flag[10];

//按照最后使用时间先后输出当前内存中的页编号
void memcont() {
    cout << "当前进程的内存内容为(最后使用者优先):" << endl;
    for(int i = 1; i <= n; i++)
        cout << memory[i] << " ";
    cout << endl;
    cout << endl;
}

//LRU 算法的具体实现过程
void LRU(int num) {
//判断当前页是不是在内存中
//直接利用标志位就可以检测
    cout<<endl<<"读取 "<<num<<" ";
    if(flag[num] == true) {
//当前页在内存中则直接读取即可
        cout << "结果：未缺页" << endl;
        int pos = 1;
//找到需要的页的位置
        while(memory[pos] != num)
            pos++;
//由于刚刚读取，更新他的最后读取时间
        for(int i = pos; i > 1; i--)
            swap(memory[i], memory[i-1]);
    } else if(flag[num] == false) {
//当前页不在内存中
        cout << "结果：缺页" << endl;
//统计缺页次数
        misstime++;
//内存没有满则直接装入，同时调整位置
        if(cnt < n) {
            cnt++;
            flag[num] = true;
            memory[cnt] = num;
            for(int i = cnt; i > 1; i--)
                swap(memory[i], memory[i-1]);
        }
//内存已满则直接把内存中排在最后的页替换，并刷新位置
        else if(cnt == n) {
            flag[num] = true;
            flag[memory[cnt]] = false;
            memory[cnt] = num;
            for(int i = cnt; i > 1; i--)
                swap(memory[i], memory[i-1]);
        }
    }
    memcont();
}

int main() {
    cout << "请输入内存中块的数量:";
    cin >> n;
    cout << "请输入页面访问序列的长度:";
    cin >> len;
    cout<<endl<<"===================================================================="<<endl;
    //重置内存页和标志位
    for(int i = 1; i <= n; i++)
        memory[i] = -1;
    for(int i = 0; i < 10; i++)
        flag[i] = false;
    cout << "请输入当前进程需要访问的页面编号(0～9):";
    for(int i = 1; i <= len; i++) {
        int num;
        cin >> num;
        LRU(num);
    }
//所有序列输入结束，查找过程结束，输出结论以及统计信息
    misscent = misstime * 1.0 / len;
    cout << "====================================================================" << endl;
    cout << "缺页的次数为: " << misstime << endl;
    cout << "缺页率为:" << misscent << endl;
    return 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

5、程序测试结果：
在程序完成后进行测试，我们随机测试内存读取序列如下所示：
1 3 2 1 2 3
测试的结果如下图所示，根据检验，程序运行结果正确：

（二）实验六 主存储器空间的分配和回收：

1、可变分区管理最先适应算法。

1、算法描述：
（1）可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：

为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：

（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。
（3）采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
最先适应分配算法如下图：

（4）当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示(1)中列举的情况下，如果作业 2 撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。
归还主存时的回收算法如下图：

2、程序具体分析：
（1）程序中使用的数据结构及符号说明
算法的实现使用到了一个结构体 List，用来记录某个区域的具体属性，是空闲列表和资源列表的组成部分，以下是结构体 List 中一些元素的名称以及含义：

算法的实现主要是依靠一些数组来完成，同时用一些变量进行辅助。算法中使用到的变量和数组的名称及其含义如下表所示：

（2）算法的具体步骤

本题设计的算法是一个选择菜单式的系统，一共有六个功能可以选择，每个选择是实现不同的内容，算法不一样，所以接下里分为六个功能来进行算法描述。算法为了实现的方便，要始终保持空闲块列表中的空闲块按照开始地址的大小从小到大进行排序。
退出功能：这个功能比较简单，就是结束测试，直接结束进程，返回主函数即可，所以就直接 return 0 即可。
新建作业列表功能：这个功能是为了初始化而设计的，是为了测试的方便，本身是不符合这个算法的思想的（所有的作业进入无法选择资源起始的地址），但是为了简化测试过程，所以预留接口，可以手动对空闲列表和资源占用列表进行输入设置，为了不混淆原本的结构，所以这个功能使用的时候首先初始化内存区域，包括内存的大小都要重新输入。首先输入内存的最大空间进行初始化，然后输入资源占用列表的数量，依次输入这些作业的开始地址等信息，接着输入空闲列表的空闲块数量，然后依次输入这些块的开始地址、长度等信息。输入的时候默认所有的块不重叠，而且无法合并（不收尾相接）。最后对空闲列表进行排序，排序关键字是空闲块开始地址的大小。
作业进入分配资源：首先读取资源的所属进程编号以及长度，然后判断这个作业是否已经在内存，如果在则不重复添加，直接输出错误信息。然后根据长度遍历空闲块列表，从低地址开始找到以第一个空闲长度大于需求长度的块，如果有则将这个作业存入这个空闲块，更新空闲列表的状态，如果这个空闲块被占用以后没有空间了，就在空闲块列表中删除这个空闲块。占用的时候记录资源占用的开始地址，然后在作业列表中加入这个作业，初始化这个作业的资源占用信息。如果遍历空闲块列表没有找到空闲块的长度大于申请量，那么说明没有足够空间存储这个作业，申请资源失败，输出提示信息。最后对空闲块列表进行排序，维持顺序符合规则。
作业结束释放资源：首先兑取需要释放的资源的编号，然后在作业列表中搜索这个作业，如果没有找到则释放资源失败。接着在空闲块列表的最后加入这个作业的空间，然后对空闲块列表进行排序。接下来对连续的空闲块进行合并，遍历整个空闲块列表，找到一个空闲块，满足他的结束地址和下一个空闲块的开始地址一样，说明是连续的，那么把这个空闲块的结束地址和长度延长，表示把下一个空闲块合并了，然后把下一个空闲块从列表中移除来完成合并，最后需要将索引减一，下一次仍然检测这个空闲块和下一个的关系，否则容易少合并。这样遍历完成一遍就合并结束了，最后将这个作业从作业列表中删除即可。
显示空闲块列表：将所有空闲块的信息按照要求输出即可。
显示作业列表：将所有作业的资源占用信息按照要求输出即可。

3、算法实现源代码：

#include <iostream>
using namespace std;
//构建结构体存储空闲区和资源列表的条目
typedef struct List {
    int start;
    int len;
    int end;
    int num;
} List;
//创建内存资源空闲列表
List freelist[1001];
//空闲列表中的条目数量
int freenum = 0;
//创建内存资源占用列表
List allolist[1001];
//占用列表中的条目数量
int allonum = 0;
//内存空间的容量
int maxspace = 0;

//展示当前空闲表的所有条目
void ShowFreeList() {
    cout << "当前的空闲表为:" << endl;
    cout << "起始地址\t 长度" << endl;
    for(int i = 1; i <= freenum; i++)
        cout <<" "<< freelist[i].start << "\t\t  " << freelist[i].len << endl;
}

//展示作业列表的所有条目
void ShowAlloList() {
    cout << "当前的占用列表为:" << endl;
    cout << "起始地址\t 长度\t\t 作业编号" << endl;
    for(int i = 1; i <= allonum; i++)
        cout <<" "<< allolist[i].start << "\t\t   " << allolist[i].len << "\t\t   " <<allolist[i].num << endl;
}

//搜索作业是否已经在占用列表中
int alloSearch(List list[], int num) {
//从作业列表中寻找和目的作业编号相同的作业条目
//找到相同的就返回条目的位置
    for(int i = 1; i <= allonum; i++)
        if(list[i].num == num)
            return i;
//找不到就返回 0，表示无相同的
    return 0;
}

//空闲表排序
void SortFree() {
//将空闲列表按照开始的地址从小到大进行排序//如果初始化的时候没有重叠部分，之后也就不会有重叠的部分
    for(int i = 1; i <= freenum; i++)
        for(int j = i+1; j <=freenum; j++)
            if(freelist[i].start > freelist[j].start)
                swap(freelist[i], freelist[j]);
}

//创建
void CreateSpace() {
//初始化空闲列表
    cout << "请输入内存空间大小:";
    cin >> maxspace;
//构建作业表
    cout << "请输入初始状态内存中作业数量:";
    cin >> allonum;
//输入作业表中的所有内容
    for(int i = 1; i <= allonum; i++) {
        cout << "请依次输入第" << i << "个作业的起始地址、长度、作业编号" << endl;
        cin >> allolist[i].start >> allolist[i].len >> allolist[i].num;
        allolist[i].end = allolist[i].start + allolist[i].len;
    }
//构建空闲表
    cout << "请输入开始时内存中的空闲块的数量:";
    cin >> freenum;
//输入空闲列表中的所有内容
    for(int i = 1; i <= freenum; i++) {
        cout  <<  "请依次输入第"  <<  i  <<  "个空闲块的起始地址、长度"  <<endl;
        cin >> freelist[i].start >> freelist[i].len;
        freelist[i].end = freelist[i].start + freelist[i].len;
    }
    SortFree();
    cout<<"********初始化内存空间成功！********"<<endl;
}

//分配资源
void allocate() {
    cout << "开始为作业分配资源：" << endl;
    int num, len;
    cout << "请输入作业编号:";
    cin >> num;
    cout << "请输入作业长度:";
    cin >> len;
//在当前作业列表中查询，不重复添加编号相同的作业
    if(alloSearch(allolist, num) != 0) {
        cout << "该进程已经在内存中，无需重复加入" << endl;
        return;
    }
//标记是否有空位，如果有用来记录空位开始的地址
    int flag = -1;
//空闲表查找空间并加入
    for(int i = 1; i <= freenum; i++) {
        if(freelist[i].len >= len) {
            flag = freelist[i].start;
            freelist[i].len -= len;
            freelist[i].start += len; //如果这个空闲块以及没有空间了则删除这个空闲块
            if(freelist[i].start == freelist[i].end) {
                for(int j = i; j < freenum; j++)
                    freelist[i] = freelist[i+1];
                freenum--;
            }
            break;
        }
    }
//加入已分配列表
//开始地址为空闲位置的首地址
    if(flag != -1) {
        allolist[++allonum].start = flag;
        allolist[allonum].len = len;
        allolist[allonum].end = flag + len;
        allolist[allonum].num = num;
        cout<<"********资源分配成功！********"<<endl;
    } else
        cout<<"********可用空间不足，资源分配失败！********"<<endl;
//对空闲列表进行排序
//保证顺序始终是按照开始地址从小到大
    SortFree();
}

//释放资源
void release() {
    cout << "开始为作业释放资源" << endl;
    int num;
    cout << "请输入作业编号:";
    cin >> num;
//首先找到这个作业在作业列表当中的位置
    int pos = alloSearch(allolist, num);
//没有找到相应作业则不用释放
    if(pos == 0) {
        cout << "释放失败！内存空间中没有该作业" << endl;
        return;
    }
//归还当前作业资源，更新空闲表
    freelist[++freenum].start = allolist[pos].start;
    freelist[freenum].len = allolist[pos].len;
    freelist[freenum].end = allolist[pos].end;
    SortFree();
//合并连续的空闲表区域，找作业表中相邻的两个条目，合并收尾相接的两个条目
    for(int i = 1; i < freenum; i++) {
        if(freelist[i].end == freelist[i+1].start) {
            freelist[i].len += freelist[i+1].len;
            freelist[i].end = freelist[i+1].end;
//删除后面的条目，只留下前面的
            for(int j = i+1; j <freenum; j++)
                freelist[j] = freelist[j+1];
//空闲表条目数量减少
            freenum--;
//回到前一个作业重新判断
            i--;
        }
    }
//从占用资源列表中删除这个作业的资源
    for(int i = pos; i < allonum; i++)
        allolist[i] = allolist[i+1];
    allonum--;
        cout<<"********资源释放成功！********"<<endl;
}

//功能选择清单
void choicelist() {
    cout << "====================================================================" << endl;
    cout << "可变分区管理菜单:" << endl;
    cout << "0.结束操作，退出系统" << endl;
    cout << "1.创建新的内存空间" << endl;
    cout << "2.装载作业,分配资源" << endl;
    cout << "3.撤销作业,释放资源" << endl;
    cout << "4.显示空闲区说明表" << endl;
    cout << "5.显示当前作业清单" << endl;
    cout << "====================================================================" << endl;
}

int main() {
    int choice;
    choicelist();
    cout << "请输入你要执行的操作的编号: " ;
//根据选择的不同的功能来执行相应的操作
    while(cin >> choice) {
        cout<<"执行 "<<choice<<" 号操作："<<endl;
        switch (choice) {
//退出系统
            case 0:
                cout << "运行结束，系统退出" << endl;
                return 0;
                break;
//创建新的内存空间
            case 1:
                CreateSpace();
                break;
//申请并分配内存
            case 2:
                allocate();
                break;
//释放内存
            case 3:
                release();
                break;
//展示当前的空闲表
            case 4:
                ShowFreeList();
                break;
//展示当前的作业列表条目
            case 5:
                ShowAlloList();
                break;
//功能选择不正确，重新选择
            default:
                cout << "选择不正确，请重新选择" << endl;
        }
        choicelist();
           cout << "请输入你要执行的操作的编号: " ;
    }
    return 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221

4、算法测试结果：
程序完成对程序进行测试，测试的结果如下图所示，根据检验，程序运行结果正确：
1）初始化系统资源和空闲情况：

2）查看初始化相关情况：

3）新的主存页进入系统：

4）主存页撤离：

2、分页式管理位示图算法。

1、算法描述：
1）分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用 0/1 表示对应块为空闲/已占用。
2）假设某系统的主存被分成大小相等的 64 块，则位示图可用 8 个字节来构成，另用一单元记录当前空闲块数。
如果已有第 0，1，4，5，6，9，11，13，24，31，共 10 个主存块被占用了，那么位示图情况如下图：

3）当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。
按找到的计算出对应的块号，其计算公式为：块号=j*8+i。 其中，j 表示找到的是第 nj行，i 表示对应的是第 i位。根据分配给作业的块号，为作业建立一张页表，页表格式：

4）当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：
字节号 j=[块号/8] （[ ]表示取整）
位数 i={块号/8} （{ }表示取余）
5）设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为 5 页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第 4，5，6 和 31 块，运行你所设计的回收程序，收回作业归还的主存块。
要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。

2、程序中使用的数据结构及符号说明：
算法的实现主要是依靠一些数组来完成，同时用一些变量进行辅助。算法中使用到的变量和数组的名称及其含义如下表所示：

3、算法的具体步骤:
本题设计的算法是一个选择菜单式的系统，一共有六个功能可以选择，每个选择是实现不同的内容，算法不一样，所以接下里分为六个功能来进行算法描述。在进行功能选择之前，要先对内存块以及一些变量进行初始化，方便后续操作进行。为了方便记录，将每个进程的页表的第一位记录为这个进程的块的数量。
退出功能：这个功能比较简单，就是结束测试，直接结束进程，返回主函数即可，所以就直接 return 0 即可。
初始化内存空间：将内存所有的块变为未使用，然后将作业的数量改为 0，表示所有作业都退出了系统，然后将剩余的块的数量重置，这样整个内存和页表都被置位了。
设置功能：这个功能是为了方便测试以符合实验要求而设计的，是为了测试的方便，本身是不符合这个算法的思想的（所有的作业进入无法选择资源起始的地址），但是为了简化测试过程，所以预留接口，可以手动对某些块的状态进行修改，将他修改为已经被占用。首先读取需要设置的块的数量，然后读取这些块的编号，将他转化成位示图中的坐标，从而修改块的状态。
主存资源分配：首先读取当前作业需要的主存块的数量，然后判断剩余的资源是不是足够装入这个作业，如果不够则申请资源失败。然后用页表的第一位记录这个作业需要的块的数量。接着，在内存中从头开始寻找空闲块，然后记录这个空闲块的编号并且存入页表，形成映射关系，直到整个作业都装入内存为止，更新剩余空闲块的数量，输出成功信息。
主存资源释放：首先读取需要释放的资源的编号，然后判断编号是否在页中，也就是简单的判断输入的编号是否大于总作业数量，如果不合法则无法释放。接着，根据页表存储的映射关系，在内存中释放这个进程占用的内存块，然后在作业表当中删除这个作业，采用逐个覆盖的方式即可，最后将作业数量减一并输出成功提示信息即可。
输出内存信息：根据要求输出信息即可，包块内存块的剩余数量、位示图，以及内存中信息的页表，即进程页和主存块的映射关系。

4、算法具体步骤：

//分页式管理位示图算法
#include <iostream>
using namespace std;
//内存中各个块的占用情况，位示图
int memory[8][8];
//内存中剩余没有被占用的块的数量
//刚开始的时候有 64 个块
int leftblocks = 64;
//当前内存中作业数量
int jobcnt = 0;
//每个进程的页表，第一位存放块的数量
int pagetable[11][66];
//内存重置初始化，全都重置为 0
void init() {
    for(int i = 0; i < 8; i++)
        for(int j = 0; j < 8; j++)
            memory[i][j] = 0;
    leftblocks = 64;
    jobcnt = 0;
    cout<<"********成功清空当前内存空间！********"<<endl;
}

//设置内存中的一些块为已占用
//设置被占用的块
void alloSet() {
    //初始被占用内存块的数量
    int n;
    cout << "请输入初始被占用的内存块数量:";
    cin >> n;
    leftblocks -= n;
    cout << "请依次输入这些块的编号(0~63)" << endl; //将这些块的标记改成已经使用
    for(int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        memory[temp/8][temp%8] = 1;
    }
        cout<<"********成功设置被占用内存块！********"<<endl;
}

//添加作业，主存分配
void alloJob() {
    int num;
    cout << "请输入需要进入内存的作业大小:";
    cin >> num;
//检测剩余内存块是否可以存入当前作业的内容
    if(num > leftblocks) {
        cout << "作业需求大于内存剩余空间，申请失败" << endl;
        return;
    }
//记录这个作业需要的块的数量
    pagetable[++jobcnt][0] = num;
    int pos = 0;
    for(int i = 1; i <= num; i++) {
//找到第一个为空的内存块
        while(memory[pos/8][pos%8] == 1)
            pos=(pos+1)%64;
        memory[pos/8][pos%8] = 1;
        pagetable[jobcnt][i] = pos;
        leftblocks--;
    }
        cout<<"********资源分配成功！********"<<endl;
}

//删除作业，主存释放
void releaseJob() {
    int num;
    cout << "请输入需要退出内存的作业编号:";
    cin >> num;
//判断进程编号的输入是否合法
    if(num > jobcnt) {
        cout << "不存在这个作业，删除失败" << endl;
        return;
    }
//在位示图中释放当前进程占用的所有块
    for(int i = 1; i <= pagetable[num][0]; i++) {
        int temp = pagetable[num][i];
        memory[temp/8][temp%8] = 0;
        leftblocks++;
    }
//在作业表当中删除这个作业
    for(int i = num; i < jobcnt; i++)
        for(int j = 0; j <= pagetable[i][0]; j++)
            pagetable[i][j] = pagetable[i+1][j];
    jobcnt--;
        cout<<"********资源释放成功！********"<<endl;
}

//输出位示图和空闲块数剩余等信息
void info() {
    cout << "内存中剩余块的数量为: " << leftblocks << endl;
    cout << "当前的位示图如下所示:" << endl;
    cout << "       \\位数 \t 0 1 2 3 4 5 6 7" << endl;
    cout << "      字节数\\ \t ---------------" << endl;
    for(int i = 0; i < 8; i++) {
        cout << "   " << i << "\t ";
        for(int j = 0; j < 8; j++)
            cout << memory[i][j] << " ";
        cout << endl;
    }
    if(jobcnt == 0) {
        cout << "当前内存中没有作业" << endl;
        return;
    }
    cout << "当前内存中有 " << jobcnt << " 个作业" << endl;
    cout << "内存中所有进程对应的存储信息如下所示:" << endl;
    for(int i = 1; i <= jobcnt; i++) {
        cout << "\t 作业 " << i << " 占用资源: ";
        for(int j = 1; j <= pagetable[i][0]; j++)
            cout << pagetable[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}

//功能选择清单
void choicelist() {
    cout << "====================================================================" << endl;
    cout << "分页式管理位示图菜单:" << endl;
    cout << "0.结束操作，退出系统" << endl;
    cout << "1.初始化内存空间" << endl;
    cout << "2.设置被占用的内存空间" << endl;
    cout << "3.装载作业，分配资源" << endl;
    cout << "4.撤销作业，释放资源" << endl;
    cout << "5.输出当前内存信息" << endl;
    cout << "====================================================================" << endl;
}

int main() {
    int choice;
    choicelist();
    cout << "请输入你要执行的操作的编号: " ;
//重复进行功能选择，维系整个过程
    while(cin >> choice) {
        cout<<"执行 "<<choice<<" 号操作："<<endl;
        switch (choice) {
//退出系统
            case 0:
                cout << "运行结束，系统退出" << endl;
                return 0;
                break;
//初始化内存空间(全部置零)
            case 1:
                init();
                break;
//设置被占用的内存空间(设置被占用的块)
            case 2:
                alloSet();
                break;
//装入作业(分配主存资源)
            case 3:
                alloJob();
                break;
//作业结束(归还主存资源)
            case 4:
                releaseJob();
                break;
//输出当前的内存信息
            case 5:
                info();
                break;
//功能选择不正确，重新选择
            default:
                cout << "选择不正确，请重新选择" << endl;
        }
        choicelist();
           cout << "请输入你要执行的操作的编号: " ;
    }
    return 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

5、程序测试结果：
程序完成对程序进行测试，测试的结果如下图所示，根据检验程序运行结果正确：
1）初始化系统资源和空闲情况：

2）装入作业：

3）退出作业：

三、 思考题：

结合实际情况，参考书本，仔细考虑各种主存分配算法的优缺点。把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时把作业的信息按页分散存放在主存的空闲块中，这样很可能导致每个作业按页装入主存中时，某一页还存在一定的空闲空间，思考如何才能有效的利用这些空闲区域。
解答：
如果是采用可变分区管理最先适应算法的话，所有的文件都是连续存储的，这样读取的时候非常快，只要找到了就都是连续的读取，效率很高，同时，由于是连续存储的，所以存储文件的时候回很快，只要寻找空闲块的长度比申请长度大即可，类似的，释放资源的时候也会效率很高，比较节省资源。但是，这样进行操作必然会导致内存被划分成很多块，空闲区是零散的，所以一旦细碎的文件多了，会分散占用空闲块，导致大文件无法存储，使得空间利用率降低。
如果是使用分页式管理位示图算法，文件存储的时候是按照块来分割的，内存的空间也是按照块来分割的，所以就一定是能够充分利用内存空间的，不会造成浪费。但是同时，这种算法实现起来复杂度较高，虽然寻找空闲块比较简单，但是文件的读取和存储都是分块进行的，而且位置之间没有顺序性，所以读取和存储的寻址和处理的时间代价很大，算法复杂度较高。另外，这种算法是需要页表来进行维系的，页表也需要存储，会造成空间的浪费，如果内存分块块比较小，数量很多，会导致页表非常大，极限情况下，内存会被页表完全占领，造成极大的浪费，效率受到影响。