第一关
任务:
熟悉并掌握基本分页存储管理的思想及其实现方法,熟悉并掌握基本分页存储管理的分配和回收方式。
模拟实现基本分页存储管理方式下内存空间的分配和回收。
实验内容:
内存空间的初始化——输入初始内存空间各个物理块情况。(用二维矩阵的方式按物理块号,逐行给出每个物理块的状态,1——表示已分配,0——表示未分配,并能够将行标、列标转换为对应的物理块号,以查看或修改每一个块的状态,初始时部分物理块已分配)
基本分页的分配过程:输入作业号和作业的大小(这里的大小是逻辑页面数),实现分配过程:空间充足,分配,修改状态矩阵的相应位置的值(值由0转变为1),并用专门的数据记录下该作业占用的物理块的块号,以备删除作业时回收空间。
作业空间的回收:作业号,实现分区回收(通过相应的数据结构找到该作业占有的物理块号,将块号转变成对应的行标、列标,将对应位置的值由1转变成0就完成了回收)。
分区的显示:查看当前内存的情况(显示记录内存情况的矩阵的值)。
上答案:
我稍微改了下头文件
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int Row = 10;//行
const int Column = 20;//列
int Remain = Row * Column;//剩余物理块数
int Blocks[Row][Column];//物理块
/******begin 自己定义页表数据结构 ****/
typedef pair<int, int>PII;
typedef struct He {
int id;
vector<PII>text;
}He;
vector<He>m;
/******end 自己定义页表数据结构 ****/
/**函数声明**/
void in_it();
int m_malloc(int, int);
bool m_free(int);
void show();
int main()
{
in_it();//输入初始化物理内存块,为1表示已分配,为0表示未分配,如下示例
int n = 2;
int id, si;//作业id和需求内存页数
/*
0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1
0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0
0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1
1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0
0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0
1 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0
1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1
1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0
1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 1 0 1
*/
printf("初始内存使用情况\n");
show();//显示初始内存的分配情况,如上面的数据显示
while (n--) {//两次分配
cin >> id >> si;//输入作业ID和需求的内存大小,如 2 10表示2号作业需10页
switch (m_malloc(id, si))//内存分配
{
case 1:
printf("!!!ID重复,无法为作业%d再次分配内存\n", id);
break;
case 2:
printf("!!!内存不够分配给作业%d\n", id);
break;
case 3:
printf("作业%d成功分配%d块内存\n", id, si);
break;
default:
printf("!!!数据非法\n");
}
}
cin >> id;
if (m_free(id))//输入作业ID并释放其占用的物理内存,如3,表示释放3号作业的物理内存
{
printf("作业%d所占内存释放成功\n", id);
}
else
printf("!!!没有这个作业%d\n", id);
printf("当前内存使用情况\n");
show();
}
void in_it()
{
/******begin 定义函数,接受输入,初始化内存块使用情况Blocks,以及剩余块数Remain ****/
for(int i=0;i<10;i++)
for (int j = 0; j < 20; j++)
{
cin >> Blocks[i][j];
if (Blocks[i][j])
Remain--;
}
/******end 定义函数,接受输入,初始化内存块使用情况Blocks,以及剩余块数Remain ****/
}
/*
参数:id---作业ID
si---需求的内存页数
返回值:
1 -- ID重复
2 -- 内存不够分配
3 -- 分配成功,并更新Blocks数据
*/
int m_malloc(int id, int si)
{
/******begin 定义函数,为id号作业分配si块内存 ****/
int l = m.size();
int falg = 0;
for (int i = 0; i < l; i++)
if (m[i].id == id)
falg = 1;
if (falg == 1)return 1;
if (Remain < si)
return 2;
He a;
a.id = id;
Remain -= si;
for(int i=0;i<10&&si!=0;i++)
for (int j = 0; j < 20&&si!=0; j++)
{
if (!Blocks[i][j])
{
si--;
Blocks[i][j] = 1;
a.text.push_back({ i,j });
}
}
m.push_back(a);
return 3;
/******end 定义函数,为id号作业分配si块内存 ****/
}
/*
参数:id -- 欲释放作业id的所占物理内存
返回值:
true -- 释放成功,并更新内存块BLocks数据和剩余块数Remain
false -- 没有这个作业id,即没有给id号作业成功分配过内存
*/
bool m_free(int id)
{
/*** begin 定义函数,释放id号作业所占内存 *******/
int l = m.size();
int p;
int flag = 0;
for (p = 0; p < l; p++)
{
if (m[p].id == id)
{
flag = 1;
break;
}
}
if (flag == 0)
return false;
l = m[p].text.size();
Remain += l;
for (int i = 0; i < l; i++)
{
int x = m[p].text[i].first;
int y = m[p].text[i].second;
Blocks[x][y] = 0;
}
m.erase(m.begin() + p );
return true;
/*** end 定义函数,释放id号作业所占内存 *******/
}
/*
显示当前内存分配情况
*/
void show()
{
for (int i = 0; i < Row; i++)
for (int j = 0; j < Column; j++)
printf("%d%c", Blocks[i][j], j == Column - 1 ? '\n' : ' ');
}
说明:
一会儿补上
先说题目的输入
0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1
0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0
0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1
1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0
0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0
1 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0
1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1
1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0
1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 1 1 0 1
2 60
3 100
3
这个矩阵应该就是存储单元矩阵了吧
先是输入,看它们的状态
后面输入作业序号id和作业大小si
输入了以后就在存储单元矩阵里面找空的存储单元来当空间分配
数据结构
上代码说明:
const int Row = 10;//行
const int Column = 20;//列
int Remain = Row * Column;//剩余物理块数
int Blocks[Row][Column];//物理块
/******begin 自己定义页表数据结构 ****/
typedef pair<int, int>PII;
typedef struct He {
int id;
vector<PII>text;
}He;
vector<He>m;
/******end 自己定义页表数据结构 ****/
这个是数据结构部分
题目要求的数据结构要满足几个条件:
1,有索引,即可以按id找到
2,有记录,即可以记录使用的存储单元在存储单元矩阵中的位置
3,能动态操作,也即为可以删除,可以插入
所以在这里我选择使用vector容器
vector使用说明
pair使用说明
原本想用链表的,但是啊确实链表不好用,还得是vector
初始化
代码说明:
void in_it()
{
/******begin 定义函数,接受输入,初始化内存块使用情况Blocks,以及剩余块数Remain ****/
for(int i=0;i<10;i++)
for (int j = 0; j < 20; j++)
{
cin >> Blocks[i][j];
if (Blocks[i][j])
Remain--;
}
/******end 定义函数,接受输入,初始化内存块使用情况Blocks,以及剩余块数Remain ****/
}
这些就是把矩阵的状态输入进去
分配内存
上代码:
/*
参数:id---作业ID
si---需求的内存页数
返回值:
1 -- ID重复
2 -- 内存不够分配
3 -- 分配成功,并更新Blocks数据
*/
int m_malloc(int id, int si)
{
/******begin 定义函数,为id号作业分配si块内存 ****/
int l = m.size();
int falg = 0;
for (int i = 0; i < l; i++)
if (m[i].id == id)
falg = 1;//在m里面找id为id的,找到了就证明重复了
if (falg == 1)return 1;
if (Remain < si)
return 2;
He a;
a.id = id;
Remain -= si;
for(int i=0;i<10&&si!=0;i++)
for (int j = 0; j < 20&&si!=0; j++)
{
if (!Blocks[i][j])
{
si--;
Blocks[i][j] = 1;
a.text.push_back({ i,j });//记录使用的存储单元
}
}
m.push_back(a);
return 3;
/******end 定义函数,为id号作业分配si块内存 ****/
}
内存回收
上代码:
bool m_free(int id)
{
/*** begin 定义函数,释放id号作业所占内存 *******/
int l = m.size();
int p;
int flag = 0;
for (p = 0; p < l; p++)
{
if (m[p].id == id)
{
flag = 1;
break;
}
}
if (flag == 0)
return false;//没找到
l = m[p].text.size();
Remain += l;
for (int i = 0; i < l; i++)
{
int x = m[p].text[i].first;
int y = m[p].text[i].second;
Blocks[x][y] = 0;
}
m.erase(m.begin() + p );//删除
return true;
/*** end 定义函数,释放id号作业所占内存 *******/
}