实验1：内存页面置换算法的设计

一、实验内容

• 实现最近最久未使用(LRU)置换算法

二、实验目的

• LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分调入内存便可运行，还支持请求调页的存储管理方
  式。
• 本实验要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

三、实验题目

• 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。

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

• 模拟程序的算法如下图：

  

思考题

• 比较LRU和其他置换算法各自的优缺点，能够实现其他置换算法模拟设计，分析内存页面数的变化对各种置换算法命中率的影响

四、实验设计与过程

LRU算法实现并不难，但需考虑如何高效实现，本实验中我采用了哈希表和双向链表的结合来高效实现其中的插入、删除、查找，均可在O(1)时间内完成插入、删除、查找，利用空间换时间的思想，实现LRU算法。

数据结构和符号说明

struct Node{int key;int value;Node(int x, int y) : key(x), value(y) {}};int capacity;//内存页面容量int missing = 0;//是否缺页list<Node> cacheList;//双向链表unordered_map<int, list<Node>::iterator> 		cacheMap; //哈希表

函数说明

首先在哈希表中查找

• 若没找到，说明当前页不在页面内存中，需要进行页面替换

  • 然后再看是否有空闲页，即判断双向链表容量是否已满，若满则要删除链表尾部元素，即最久未访问的页面，然后将新页面加到双向链表头部，同时更新哈希表

• 若找到，则将该页放到链表头部，表示刚刚访问过，同时更新哈希表。

void set(int key, int val){if (cacheMap.find(key) == cacheMap.end()){missing = 1; //表示缺页//淘汰最后一个，然后将其加到第一个位置if (cacheList.size() == capacity){cacheMap.erase(cacheList.back().key);cacheList.pop_back();}cacheList.push_front(Node(key, val));cacheMap[key] = cacheList.begin();}else{missing = 0; //表示未缺页//更新节点的值，并将其加到第一个位置,map和list均要更新cacheMap[key]->value = val;cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);cacheMap[key] = cacheList.begin();}}

完整源代码

#include <bits/stdc++.h>
#include <iostream>
#include <list>
#include <unordered_map>using namespace std;
int pagelist[20];
void buildpage() //内存页初始化函数
{for (int i = 0; i < 20; i++){// cin >> pagelist[i];pagelist[i] = rand() % 6;}
}
class LRUCache
{
public:LRUCache(int c) : capacity(c) {} //页面数量初始化int get(int key)                 //查找{if (cacheMap.find(key) == cacheMap.end())return -1;//将key移到第一个，并更新cacheMapcacheMap[key] = cacheList.begin();cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);return cacheMap[key]->value;}void set(int key, int val){if (cacheMap.find(key) == cacheMap.end()){missing = 1; //表示缺页//淘汰最后一个，然后将其加到第一个位置if (cacheList.size() == capacity){cacheMap.erase(cacheList.back().key);cacheList.pop_back();}cacheList.push_front(Node(key, val));cacheMap[key] = cacheList.begin();}else{missing = 0; //表示未缺页//更新节点的值，并将其加到第一个位置,map和list均要更新cacheMap[key]->value = val;cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);cacheMap[key] = cacheList.begin();}}int show(){int t = 0;for (auto i = cacheList.rbegin(); i != cacheList.rend(); i++){printf("%2d", i->key);t++;}while (t++ < 3){printf("%2c", ' ');}return missing;}private:struct Node{int key;int value;Node(int x, int y) : key(x), value(y) {}};int capacity;//内存页面容量int missing = 0;//是否缺页list<Node> cacheList;                              //双向链表unordered_map<int, list<Node>::iterator> cacheMap; //哈希表
};
int main()
{srand((int)time(0));LRUCache lru(3); //背包容量初始化buildpage();     //页面初始化double m = 0;printf("|--------------------------------|\n");printf("|---------------LRU--------------|\n");printf("|--------------------------------|\n");printf("| 页面序列 | 当前页块 | 是否缺页 |\n");for (int i = 0; i < 20; i++){lru.set(pagelist[i], pagelist[i]);printf("|    %d     |  ", pagelist[i]);if (lru.show())printf("  |   缺页   |\n"), m++;elseprintf("  |          |\n");}printf("|--------------------------------|\n");printf("缺页次数为：%.0f\n缺页率为: %.2f%%", m, m / 20 * 100);
}

程序初值和运行结果

初值

1 2 5 6 0 3 6 5 3 6 5 6 0 4 2 7 0 4 3 5

测试样例结果：

页面序列随机生成结果：

思考题

页面置换算法各自的优缺点

• LRU（最近最久未使用）：

  • 优点：由于考虑程序访问的时间局部性，一般能有较好的性能；实际应用多
  • 缺点：实现需要较多的硬件支持，会增加硬件成本

• FIFO（先进先出）：

  • 优点：先进先出算法实现简单，是最直观的一个算法
  • 缺点：先进先出的性能最差，因为与通常页面的使用规则不符合，所以实际应用少

• OPT（最佳置换）：

  • 缺点：最佳置换算法是一种理想化算法，具有较好的性能，但是实际上无法实现（无法预知一个进程中的若干页面哪一个最长时间不被访问）；

  • 优点：最佳置换算法可以保证获得最低的缺页率

五、实验总结

LRU算法本身比较简单，关键在于时间复杂度的控制，使其能够高效实现，哈希表可以在O(1)时间内查找，双向链表可以在O(1)时间内插入和删除，所以两者结合可以高效的实现LRU，本次实验过程是我重新回顾了list和map的用法，结合这两者，成功完成了实验。

实验2：主存储器空间的分配和回收

一、实验内容

• 主存储器空间的分配和回收

二、实验目的

• 通过本实验帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收

三、实验题目

本实验模拟在两种存储管理方式下的主存分配和回收。

第一题：

在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。

[提示]：

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

   

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

   

2. 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

3. 采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图。

   

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

   

5. 请按最先适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。

第二题：

在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。

[提示]：

1. 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。

2. 假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存块被占用了，那么位示图情况如下

   

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

   

4. 当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：字节号 j=[块号/8] （[ ]表示取整）位数 i={块号/8} （{ }表示取余）

5. 设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行你所设计的回收程序，收回作业归还的主存块。要求能显示和打印分配或回收前后的位示图和当前空闲
   块数，对完成一次分配后还要显示或打印为作业建立的页表

思考题：

结合实际情况，参考书本，仔细考虑各种主存分配算法的优缺点。把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时把作业的信息按页分散存放在主存的空闲块中，这样很可能导致每个作业按页装入主存中时，某一页还存在一定的空闲空间，思考如何才能有效的利用这些空闲区域。

四、实验设计与过程

第一题：最先适应

数据结构和符号说明

struct table
{string name; //主存分配信息int address; //主存起始地址int length;  //主存分配长度int state;   //主存状态信息，1为已分配，0为未分配
};
vector<table> alloc_table;   //主存表

函数说明

一共三个主要函数

• 未分配主存的合并函数
• 主存回收函数
• 主存分配函数

根据流程图，函数思路均很清晰。

void merge() //未分配主存的合并函数
{for (int i = 0; i < alloc_table.size() - 1; i++){if (alloc_table[i].address + alloc_table[i].length == alloc_table[i + 1].address && alloc_table[i].state == 0 && alloc_table[i + 1].state == 0){ //相邻则合并，并删掉后者alloc_table[i].length += alloc_table[i + 1].length;alloc_table.erase(alloc_table.begin() + i + 1);break;}}
}
int recovery(string name) //主存回收函数
{for (int i = 0; i < alloc_table.size(); i++){if (alloc_table[i].name == name){alloc_table[i].name = "未分配";alloc_table[i].state = 0;return alloc_table[i].length;}}
}
void allocation(string name, int length) //主存分配函数
{for (int i = 0; i < alloc_table.size(); i++){if (alloc_table[i].length > length && alloc_table[i].state == 0) //剩余空间比需求大{table t;t.name = name;t.address = alloc_table[i].address;t.length = length;t.state = 1;alloc_table.push_back(t);alloc_table[i].address += length;alloc_table[i].length -= length;break;}else if (alloc_table[i].length == length && alloc_table[i].state == 0) //剩余空间和需求一样{alloc_table[i].name = name;alloc_table[i].state = 1;break;}}
}

完整源代码

#include <bits/stdc++.h>
using namespace std;
struct table
{string name; //主存分配信息int address; //主存起始地址int length;  //主存分配长度int state;   //主存状态信息，1为已分配，0位未分配
};
vector<table> alloc_table;   //主存表
bool cmp(table &a, table &b) //排序比较函数
{return a.address < b.address;
}
void merge() //未分配主存的合并函数
{for (int i = 0; i < alloc_table.size() - 1; i++){if (alloc_table[i].address + alloc_table[i].length == alloc_table[i + 1].address && alloc_table[i].state == 0 && alloc_table[i + 1].state == 0){ //相邻则合并，并删掉后者alloc_table[i].length += alloc_table[i + 1].length;alloc_table.erase(alloc_table.begin() + i + 1);break;}}
}
int recovery(string name) //主存回收函数
{for (int i = 0; i < alloc_table.size(); i++){if (alloc_table[i].name == name){alloc_table[i].name = "未分配";alloc_table[i].state = 0;return alloc_table[i].length;}}
}
void allocation(string name, int length) //主存分配函数
{for (int i = 0; i < alloc_table.size(); i++){if (alloc_table[i].length > length && alloc_table[i].state == 0) //剩余空间比需求大{table t;t.name = name;t.address = alloc_table[i].address;t.length = length;t.state = 1;alloc_table.push_back(t);alloc_table[i].address += length;alloc_table[i].length -= length;break;}else if (alloc_table[i].length == length && alloc_table[i].state == 0) //剩余空间和需求一样{alloc_table[i].name = name;alloc_table[i].state = 1;break;}}
}
void init() //状态初始化
{table a;a.name = "操作系统";a.address = 0;a.length = 5;a.state = 1;alloc_table.push_back(a);a.name = "1";a.address = 5;a.length = 5;a.state = 1;alloc_table.push_back(a);a.name = "3";a.address = 10;a.length = 4;a.state = 1;alloc_table.push_back(a);a.name = "2";a.address = 26;a.length = 6;a.state = 1;alloc_table.push_back(a);a.name = "未分配";a.address = 14;a.length = 12;a.state = 0;alloc_table.push_back(a);a.name = "未分配";a.address = 32;a.length = 96;a.state = 0;alloc_table.push_back(a);
}
void print() //信息打印
{printf("\n|----------------空闲分区表------------------|\n");printf("|  起 址  |  长 度  |  状 态  |     名称     |\n");for (int i = 0; i < alloc_table.size(); i++){if (alloc_table[i].state == 0){printf("|   %3d   |   %3d   |   %3d   |  %9s   |\n", alloc_table[i].address, alloc_table[i].length, alloc_table[i].state, alloc_table[i].name.c_str());}}printf("|--------------------------------------------|\n");printf("\n|----------------主存分配表------------------|\n");printf("|  起 址  |  长 度  |  状 态  |     名称     |\n");for (int i = 0; i < alloc_table.size(); i++){if (alloc_table[i].state == 1){printf("|   %3d   |   %3d   |   %3d   |  %9s   |\n", alloc_table[i].address, alloc_table[i].length, alloc_table[i].state, alloc_table[i].name.c_str());}}printf("|--------------------------------------------|\n");
}
int main()
{printf("\n~~~~~~~~~~~~~~~~~~初始状态~~~~~~~~~~~~~~~~~~~~\n");init();sort(alloc_table.begin(), alloc_table.end(), cmp); //排序merge();                                           //合并print();                                           //打印信息printf("\n~~~~~~~~~~~~~~~~~~加入工作4~~~~~~~~~~~~~~~~~~~\n");printf("\n------------------申请内存4-------------------\n");allocation("4", 6); //分配sort(alloc_table.begin(), alloc_table.end(), cmp);merge();print();printf("\n~~~~~~~~~~~~~~~~~~回收工作3~~~~~~~~~~~~~~~~~~~\n");int a = recovery("3"); //回收printf("\n------------------释放内存%d-------------------\n", a);sort(alloc_table.begin(), alloc_table.end(), cmp);merge();print();printf("\n~~~~~~~~~~~~~~~~~~回收工作2~~~~~~~~~~~~~~~~~~~\n");a = recovery("2");printf("\n------------------释放内存%d-------------------\n", a);sort(alloc_table.begin(), alloc_table.end(), cmp);merge();print();return 0;
}

程序初值和运行结果

初始状态：

加入工作4：

回收工作3：

回收工作2：

第二题：位示图

数据结构和符号说明

int table[8][8];//位示图
int free_num = 64;//当前位示图空闲块
struct work
{string name;//作业名称int mem_num;//作业页表数量int page_table[64];//页表
};
vector<work> w;//作业数量

函数说明

一共两个主要函数

• 作业分配函数allocation()
• 作业回收函数recovery()

函数思路如下，均相当好理解

void allocation()//作业分配函数
{work a;int t = 0;while (1)//输入作业名并判断是否已经存在{printf("请输入要分配的作业名:");cin >> a.name;int kk = 0;for (int i = 0; i < w.size(); i++){if (a.name == w[i].name)kk = 1;}if (kk == 1)printf("当前作业已存在，请重新输入\n");elsebreak;}printf("请输入作业内存申请量:");scanf("%d", &a.mem_num);if (free_num >= a.mem_num)//如果内存空间大于作业内存申请数量{for (int i = 0; i < 8; i++){for (int j = 0; j < 8; j++){if (!table[i][j])//修改未分配的位示图{table[i][j] = 1;free_num--;a.page_table[t++] = i * 8 + j;if (t == a.mem_num)break;}}if (t == a.mem_num)break;}w.push_back(a);//加入作业列表printf("\n作业内存分配成功\n");print();}elseprintf("\n内存空闲块不足\n");
}
void recovery()
{string name;printf("请输入要释放的作业名:");cin >> name;for (int i = 0; i < w.size(); i++){if (w[i].name == name){printf("\n当前作业归还的块号：");for (int k = 0; k < w[i].mem_num; k++)//逐个释放内存块{printf("%d  ", w[i].page_table[k]);table[w[i].page_table[k] / 8][w[i].page_table[k] % 8] = 0;free_num++;}w.erase(w.begin() + i);printf("\n作业回收成功\n");print();return;}}printf("\n未找到当前作业\n");
}

完整源代码

#include <bits/stdc++.h>
using namespace std;
int table[8][8];//位示图
int free_num = 64;//当前位示图空闲块
struct work
{string name;//作业名称int mem_num;//作业页表数量int page_table[64];//页表
};
vector<work> w;//作业数量
void menu()
{printf("1.分配作业\n");printf("2.回收作业\n");printf("3.退出\n");
}
void init()//位示图初始化函数
{memset(table, 0, sizeof(table));table[0][0] = 1;table[0][1] = 1;table[0][4] = 1;table[0][5] = 1;table[0][6] = 1;table[1][1] = 1;table[1][3] = 1;table[1][5] = 1;table[3][0] = 1;table[3][7] = 1;free_num -= 10;work a;a.name = "w1";//作业1a.mem_num = 4;a.page_table[0] = 4;a.page_table[1] = 5;a.page_table[2] = 6;a.page_table[3] = 31;w.push_back(a);a.name = "w2";//作业2a.mem_num = 6;a.page_table[0] = 0;a.page_table[1] = 1;a.page_table[2] = 9;a.page_table[3] = 11;a.page_table[4] = 13;a.page_table[5] = 24;w.push_back(a);printf("初始化完成\n");
}
void print()//信息打印函数
{printf("当前位示图和作业页表:\n");printf("\n|--------------位示图---------------|\n");printf("|-----------------------------------|\n");printf("|  位数  |");for (int i = 0; i < 8; i++){printf("%3d", i);}printf("  |\n| 字节数 |%24c  |\n", ' ');printf("|        ___________________________|\n");for (int i = 0; i < 8; i++){printf("| %6d |", i);for (int j = 0; j < 8; j++){printf("%3d", table[i][j]);}printf("  |\n");}printf("|-----------------------------------|\n");printf("\n当前空闲块数：%d\n", free_num);printf("\n|-----作业页表----|\n");for (int i = 0; i < w.size(); i++){printf("|-----------------|\n");printf("|      作业%s     |\n", w[i].name.c_str());printf("|  页号  |  块号  |\n");for (int j = 0; j < w[i].mem_num; j++){printf("|  %4d  |  %4d  |\n", j, w[i].page_table[j]);}}printf("|-----------------|\n\n");
}
void allocation()//作业分配函数
{work a;int t = 0;while (1)//输入作业名并判断是否已经存在{printf("请输入要分配的作业名:");cin >> a.name;int kk = 0;for (int i = 0; i < w.size(); i++){if (a.name == w[i].name)kk = 1;}if (kk == 1)printf("当前作业已存在，请重新输入\n");elsebreak;}printf("请输入作业内存申请量:");scanf("%d", &a.mem_num);if (free_num >= a.mem_num)//如果内存空间大于作业内存申请数量{for (int i = 0; i < 8; i++){for (int j = 0; j < 8; j++){if (!table[i][j])//修改未分配的位示图{table[i][j] = 1;free_num--;a.page_table[t++] = i * 8 + j;if (t == a.mem_num)break;}}if (t == a.mem_num)break;}w.push_back(a);//加入作业列表printf("\n作业内存分配成功\n");print();}elseprintf("\n内存空闲块不足\n");
}
void recovery()
{string name;printf("请输入要释放的作业名:");cin >> name;for (int i = 0; i < w.size(); i++){if (w[i].name == name){printf("\n当前作业归还的块号：");for (int k = 0; k < w[i].mem_num; k++)//逐个释放内存块{printf("%d  ", w[i].page_table[k]);table[w[i].page_table[k] / 8][w[i].page_table[k] % 8] = 0;free_num++;}w.erase(w.begin() + i);printf("\n作业回收成功\n");print();return;}}printf("\n未找到当前作业\n");
}int main()
{int q;init();print();while (1){menu();printf("请输入选择:");scanf("%d", &q);switch (q){case 1:allocation();break;case 2:recovery();break;case 3:exit(0);break;}}return 0;
}

程序初值和运行结果

初始状态：

加入工作3，申请量为5：

回收工作1：

全部回收：

思考题

各种主存分配算法的优缺点

• 首次适应算法：

  • 优点： 该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲 区。显然为以后到达的大作业分配大的内存空间创造了条件

  • 缺点：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销

• 最佳适应算法：

  • 优点：每次分配给文件的都是最合适该文件大小的分区。

  • 缺点：内存中留下许多难以利用的小的空闲区。

• 最差适应算法：

  • 优点：给文件分配分区后剩下的空闲区不至于太小，产生碎片的几率最小，对中小型文件分配分区操作有利。
  • 缺点：使存储器中缺乏大的空闲区，对大型文件的分区分配不利。

如何利用空闲分区

采用可变内存管理，合并小的空闲区。

五、实验总结

本次实验要我对不同的存储管理方式下应怎样实现主存空间的分配和回收有了更深的理解，对页面置换算法、主存分配回收算法、最先适应算法和位示图方法有了一定的了解，实验算法思路总体上较为简单，只要理解了具体的内存的分配和释放规则就比较容易写出算法。