操作系统实验 —— 动态分区分配方式的模拟 - CS 基础 - 笔记

慕课指路：操作系统原理
超有意思一定要动手敲下试试的动态分区分配方式【滑稽】
代码思路来源学校的慕课给出的代码，自己敲了一遍进行了亿点点改动
不过核心思路没变，异常处理什么的没有

# 一、实验目的

了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

# 二、实验要求

(1) 用 C 语言实现采用首次适应算法的动态分区分配过程 alloc () 和回收过程 free ()。空闲分区通过空闲分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。
(2) 假设初始状态下，可用的内存空间为 640KB，并有下列的请求序列:

作业 1 申请 130KB
作业 2 释放 60KB
作业 3 申请 100KB
作业 2 释放 60KB
作业 4 申请 200KB
作业 3 释放 100KB
作业 1 释放 130KB
作业 5 申请 140KB
作业 6 申请 60KB
作业 7 申请 50KB
作业 6 释放 60KB。

请采用首次适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。

# 三、实验内容

# 1、数据结构

定义请求序列结构体，num 代表作业号，state 代表该作业申请还是释放空间，len 代表该做也申请或释放空间的大小。

	// 定义请求序列结构体
	struct Allocquery {
	int num;
	char state; //a 表示申请 (apply)，f 表示释放（free）
	int len; // 长度
	Allocquery(int n = 0, char s = 'f', int l = 0):num(n), state(s), len(l){}
	} alocq[MaxNum];

定义内存分配队列结构体，flag 为 0 时表示该内存块空闲，为其他数值则表示相应作业。如为 1 则表示存储的是作业 1。firstadd 表示该内存块的首地址，len 表示该内存块的大小。

	// 定义内存分配队列
	struct Freequery {
	int flag; //0 表示空闲，其他数值表示相应作业
	int firstadd; // 起始地址
	int len; // 占有长度
	Freequery(int f = 0, int fi = 0, int l = 0) : flag(f), firstadd(fi), len(l) {}
	} freeq[MaxNum];

# 2、初始化

从文件中读取，in.txt 内容为题意要求的作业请求队列，1 a 130 表示作业 1 申请 130KB 的空间

1 a 130
2 f 60
3 a 100
2 f 60
4 a 200
3 f 100
1 f 130
5 a 140
6 a 60
7 a 50
6 f 60

定义常量

	const string InputFileName = "in.txt";
	const string OutputFileName = "out.txt";
	const int MaxNum = 11;

首先初始化作业请求序列，利用 c++ 文件流，初始化每个作业请求。

	// 初始化作业请求序列
	void initAlocq() {
	ifstream infp(InputFileName, ios::in);
	int index = 0;
	while(!infp.eof() && index < MaxNum) {
	int num;
	stringstream ss;
	infp >> alocq[index].num >> alocq[index].state >> alocq[index].len;
	++index;
	}
	infp.close();
	}

然后初始化内存空间，注意 Freequery 的构造函数中默认参数中 len 一开始都为 0，也就是说 len 为 0 则这个内存块不存在，可以作为循环结束的依据，所以一开始将 freeq [0] 的长度置为整个内存空间的长度。

	void initFreeq() {
	freeq[0].flag = 0, freeq[0].firstadd = 0, freeq[0].len = 640;
	}

# 3、主程序

对每次作业请求执行操作，并显示执行结果在文件 out.txt 中。其中 Freetotal 表示内存空余块的数量，一开始当然为 1，first_alg 为首次适应算法，参数为请求块、当前空块个数、内存分配队列。

	void Run() {
	ofstream outfp(OutputFileName, ios::out);
	int Freetotal = 1;
	// 对每次作业请求执行操作，显示执行结果
	for(int i = 0; i < MaxNum; ++i ) {
	first_alg(alocq[i], Freetotal, freeq);
	outfp << "序列" << i+1 << ":作业" << alocq[i].num;
	if(alocq[i].state == 'a') outfp << "申请" << alocq[i].len << "K\n";
	else outfp << "释放" << alocq[i].len << "K\n";
	outfp << "Now total free blocks:" << Freetotal << endl;
	outfp << "IDNum\taddress\t\tlength"<< endl;
	for(int j = 0 ; freeq[j].len != 0; ++j) {
	outfp << " " << freeq[j].flag << "\t\t "
	<< freeq[j].firstadd << "\t\t "
	<< freeq[j].len << endl;
	}
	outfp << "--------------------------------------------------\n" << endl;

	}
	outfp.close();
	}
	int main() {
	initAlocq();
	initFreeq();
	Run();
	return 0;
	}

首次适应算法，参数为请求块、当前空块个数、内存分配队列

函数声明：

void first_alg(Allocquery nowaloc, int &ptotal, Freequery *pfreeq);

首先判断是申请空间还是释放空间，若为申请空间，遍历所有内存块。当且仅当该内存块 pfreeq [i] 没有被分配，且大小大于等于申请的空间量，将该块分配给该作业，并将空块合并，详细的合并方法在注释里都有体现。若为释放空间，那就找到待释放的块将其释放，并将释放后空闲区合并。

	// 首次适应算法
	// 参数为请求块、当前空块个数、内存具体使用情况
	void first_alg(Allocquery nowaloc, int &ptotal, Freequery *pfreeq){
	Freequery temp;
	Freequery temp_f1, temp_f2;
	if(nowaloc.state == 'a') {
	// 申请空间
	for(int i = 0; i < MaxNum; ++i) {
	// 该内存块空闲且空间足以分给该作业
	if(pfreeq[i].flag == 0 && pfreeq[i].len >= nowaloc.len) {
	temp.flag = pfreeq[i].flag;
	temp.firstadd = pfreeq[i].firstadd+nowaloc.len; // 首地址下移
	temp.len = pfreeq[i].len-nowaloc.len; // 剩余空间长度
	// 找到的空块长度正好等于请求块，则立刻分配
	pfreeq[i].flag = nowaloc.num;
	pfreeq[i].len = nowaloc.len;
	if(pfreeq[i+1].len == 0) {
	// 找到的空块正好是全部剩余空间
	pfreeq[i+1] = temp;
	} else if (pfreeq[i+1].firstadd != temp.firstadd){
	// 前后被占用，空块在中间，且长度大于请求块
	temp_f1 = temp;
	temp_f2 = pfreeq[i+1];
	int j;
	for(j = i+1; pfreeq[j].len != 0; ++j) {
	pfreeq[j] = temp_f1;
	temp_f1 = temp_f2;
	temp_f2 = pfreeq[j+1];
	}
	pfreeq[j] = temp_f1;
	}
	break;
	}
	}
	} else {
	// 释放空间
	for(int i = 0; i < MaxNum; ++i) {
	if(pfreeq[i].flag == nowaloc.num) {
	// 找到待回收的块
	if(i > 0 && pfreeq[i-1].flag == 0 && pfreeq[i+1].flag == 0) {
	// 前后都为空块，且回收块的首地址不是 0
	pfreeq[i-1].len = pfreeq[i-1].len + nowaloc.len + pfreeq[i+1].len;
	for(int j = i; pfreeq[j].len != 0; ++j) {
	// 三块合并后队列变化
	pfreeq[j] = pfreeq[j+2];
	}
	} else if(i > 0 && pfreeq[i-1].flag == 0) {
	// 前为空块，后不为空块，且不是首块
	pfreeq[i-1].len = pfreeq[i-1].len + nowaloc.len;
	for(int j = i; pfreeq[j].len != 0; ++j) {
	// 两块合并后队列变化
	pfreeq[j] = pfreeq[j+1];
	}
	} else if(pfreeq[i+1].flag == 0) {
	// 后为空块
	pfreeq[i].flag = 0;
	pfreeq[i].len = nowaloc.len + pfreeq[i+1].len;
	for(int j = i+1; pfreeq[j].len != 0; ++j) {
	pfreeq[j] = pfreeq[j+1];
	}
	} else {
	// 前后都不空
	pfreeq[i].flag = 0;
	}
	}
	}
	}
	int fnum = 0; // 统计空闲块
	for(int i = 0; pfreeq[i].len != 0; ++i)
	if(pfreeq[i].flag == 0) ++fnum;
	ptotal = fnum;
	}

# 四、实验结果

在这里插入图片描述

# 五、完整代码

	#include <iostream>
	#include <string>
	#include <sstream>
	#include <fstream>
	using namespace std;
	const string InputFileName = "in.txt";
	const string OutputFileName = "out.txt";
	const int MaxNum = 11;
	// 定义请求序列结构体
	struct Allocquery {
	int num;
	char state; //a 表示申请 (apply)，f 表示释放（free）
	int len; // 长度
	Allocquery(int n = 0, char s = 'f', int l = 0):num(n), state(s), len(l){}
	} alocq[MaxNum];
	// 定义内存分配队列
	struct Freequery {
	int flag; //0 表示空闲，其他数值表示相应作业
	int firstadd; // 起始地址
	int len; // 占有长度
	Freequery(int f = 0, int fi = 0, int l = 0) : flag(f), firstadd(fi), len(l) {}
	} freeq[MaxNum];

	// 首次适应算法
	// 参数为请求块、当前空块个数、内存分配队列
	void first_alg(Allocquery nowaloc, int &ptotal, Freequery *pfreeq);

	// 初始化作业请求序列
	void initAlocq() {
	ifstream infp(InputFileName, ios::in);
	int index = 0;
	while(!infp.eof() && index < MaxNum) {
	int num;
	stringstream ss;
	infp >> alocq[index].num >> alocq[index].state >> alocq[index].len;
	//cout << alocq[index].num << ' ' << alocq[index].state << ' ' << alocq[index].len << endl;
	++index;
	}
	infp.close();
	}
	// 初始化内存空间
	void initFreeq() {
	freeq[0].flag = 0, freeq[0].firstadd = 0, freeq[0].len = 640;
	}
	void Run() {
	ofstream outfp(OutputFileName, ios::out);
	int Freetotal = 1;
	// 对每次作业请求执行操作，显示执行结果
	for(int i = 0; i < MaxNum; ++i ) {
	first_alg(alocq[i], Freetotal, freeq);
	outfp << "序列" << i+1 << ":作业" << alocq[i].num;
	if(alocq[i].state == 'a') outfp << "申请" << alocq[i].len << "K\n";
	else outfp << "释放" << alocq[i].len << "K\n";
	outfp << "Now total free blocks:" << Freetotal << endl;
	outfp << "IDNum\taddress\t\tlength"<< endl;
	for(int j = 0 ; freeq[j].len != 0; ++j) {
	outfp << " " << freeq[j].flag << "\t\t "
	<< freeq[j].firstadd << "\t\t "
	<< freeq[j].len << endl;
	}
	outfp << "--------------------------------------------------\n" << endl;

	}
	outfp.close();
	}
	int main() {
	initAlocq();
	initFreeq();
	Run();
	return 0;
	}
	// 首次适应算法
	// 参数为请求块、当前空块个数、内存具体使用情况
	void first_alg(Allocquery nowaloc, int &ptotal, Freequery *pfreeq){
	Freequery temp;
	Freequery temp_f1, temp_f2;
	if(nowaloc.state == 'a') {
	// 申请空间
	for(int i = 0; i < MaxNum; ++i) {
	// 该内存块空闲且空间足以分给该作业
	if(pfreeq[i].flag == 0 && pfreeq[i].len >= nowaloc.len) {
	temp.flag = pfreeq[i].flag;
	temp.firstadd = pfreeq[i].firstadd+nowaloc.len; // 首地址下移
	temp.len = pfreeq[i].len-nowaloc.len; // 剩余空间长度
	// 找到的空块长度正好等于请求块，则立刻分配
	pfreeq[i].flag = nowaloc.num;
	pfreeq[i].len = nowaloc.len;
	if(pfreeq[i+1].len == 0) {
	// 找到的空块正好是全部剩余空间
	pfreeq[i+1] = temp;
	} else if (pfreeq[i+1].firstadd != temp.firstadd){
	// 前后被占用，空块在中间，且长度大于请求块
	temp_f1 = temp;
	temp_f2 = pfreeq[i+1];
	int j;
	for(j = i+1; pfreeq[j].len != 0; ++j) {
	pfreeq[j] = temp_f1;
	temp_f1 = temp_f2;
	temp_f2 = pfreeq[j+1];
	}
	pfreeq[j] = temp_f1;
	}
	break;
	}
	}
	} else {
	// 释放空间
	for(int i = 0; i < MaxNum; ++i) {
	if(pfreeq[i].flag == nowaloc.num) {
	// 找到待回收的块
	if(i > 0 && pfreeq[i-1].flag == 0 && pfreeq[i+1].flag == 0) {
	// 前后都为空块，且回收块的首地址不是 0
	pfreeq[i-1].len = pfreeq[i-1].len + nowaloc.len + pfreeq[i+1].len;
	for(int j = i; pfreeq[j].len != 0; ++j) {
	// 三块合并后队列变化
	pfreeq[j] = pfreeq[j+2];
	}
	} else if(i > 0 && pfreeq[i-1].flag == 0) {
	// 前为空块，后不为空块，且不是首块
	pfreeq[i-1].len = pfreeq[i-1].len + nowaloc.len;
	for(int j = i; pfreeq[j].len != 0; ++j) {
	// 两块合并后队列变化
	pfreeq[j] = pfreeq[j+1];
	}
	} else if(pfreeq[i+1].flag == 0) {
	// 后为空块
	pfreeq[i].flag = 0;
	pfreeq[i].len = nowaloc.len + pfreeq[i+1].len;
	for(int j = i+1; pfreeq[j].len != 0; ++j) {
	pfreeq[j] = pfreeq[j+1];
	}
	} else {
	// 前后都不空
	pfreeq[i].flag = 0;
	}
	}
	}
	}
	int fnum = 0; // 统计空闲块
	for(int i = 0; pfreeq[i].len != 0; ++i)
	if(pfreeq[i].flag == 0) ++fnum;
	ptotal = fnum;
	}

操作系统