|
#include <iostream>
#include <Windows.h>
#include <fstream>
#include <string>
#include <queue>
using namespace std;
int MemorySize = 0;
int OSSize = 0;
int Memory[1000] = { 0 };
struct Struct1{
int begin;
int length;
string state;//值为未分配或者空条目
};
queue<Struct1> WORK;//作业集合
queue<Struct1> EMPTY;//空区集合
//更新EMPTY队列，空区集合
void UpdateEMP(){
while (!EMPTY.empty()) {
EMPTY.pop();
}
for (int i = 0; i < MemorySize; i++) {
if (Memory[i] == 0) {
for (int j = i + 1; j < MemorySize; j++) {
if (Memory[j] == 1 || j == MemorySize - 1) {
Struct1 emp1;
emp1.begin = i;
if (j == MemorySize - 1) {
emp1.length = j - i + 1;
}
else {
emp1.length = j - i;
}
emp1.state = "未分配";
EMPTY.push(emp1);
i = j;
break;
}
}
}
}
cout << "现有的空区说明表为：" << endl;
int s = EMPTY.size();
cout << s << "块空区" << endl;
for (int i = 0; i < s; i++) {
Struct1 emp1;
emp1 = EMPTY.front();
EMPTY.push(emp1);
EMPTY.pop();
cout << " 起始：" << emp1.begin << " 长度：" << emp1.length << " 状态：" << emp1.state << endl;
}
}
//首次适应算法(FF)
void FF(int applyNum) {
if (EMPTY.empty()) {
cout << "没有足够的主存空间！！" << endl;
exit(0);
}
bool flag = false;
while (!EMPTY.empty()) {
Struct1 emp1 = EMPTY.front();
if (emp1.length > applyNum) {
for (int i = emp1.begin; i< applyNum + emp1.begin ;i++) {
Memory[i] = 1;
}
Struct1 work3;
work3.begin = emp1.begin;
work3.length = applyNum;
work3.state = "作业4";
WORK.push(work3);
UpdateEMP();
flag = true;
break;
}
EMPTY.pop();
}
if (!flag) {
cout << "没有足够的主存空间！！" << endl;
exit(0);
}
Sleep(2000);
//作业三撤离
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作业3") {
for (int i = work1.begin; i < work1.begin+ work1.length;i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作业三撤离！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
Sleep(2000);
//作业二撤离
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作业2") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作业二撤离！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
}
//循环首次适应算法（NF）
void NF(int applyNum) {
if (EMPTY.empty()) {
cout << "没有足够的主存空间！！" << endl;
exit(0);
}
bool flag = false;
while (!EMPTY.empty()) {
Struct1 emp1 = EMPTY.front();
if (emp1.length > applyNum) {
for (int i = emp1.begin; i < applyNum + emp1.begin; i++) {
Memory[i] = 1;
}
Struct1 work3;
work3.begin = emp1.begin;
work3.length = applyNum;
work3.state = "作业4";
WORK.push(work3);
UpdateEMP();
flag = true;
break;
}
EMPTY.pop();
}
if (!flag) {
cout << "没有足够的主存空间！！" << endl;
exit(0);
}
Sleep(2000);
//作业三撤离
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作业3") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作业三撤离！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
Sleep(2000);
//作业二撤离
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作业2") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作业二撤离！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
}
//最佳适应算法(BF)
void BF(int applyNum) {
if (EMPTY.empty()) {
cout << "没有足够的主存空间！！" << endl;
exit(0);
}
bool flag = false;
int col = 10000000;//记录每一个空区与请求大小的差值
string e = "";
int em = EMPTY.size()*2;
for (int i = 0; i < em; i++) {
Struct1 emp1 = EMPTY.front();
if (emp1.length > applyNum) {
if (col == (emp1.length - applyNum) && e==emp1.state) {
for (int i = emp1.begin; i < applyNum + emp1.begin; i++) {
Memory[i] = 1;
}
Struct1 work3;
work3.begin = emp1.begin;
work3.length = applyNum;
work3.state = "作业4";
WORK.push(work3);
UpdateEMP();
flag = true;
break;
}
if (col > (emp1.length - applyNum)) {
col = (emp1.length - applyNum);
e = emp1.state;
}
}
EMPTY.pop();
EMPTY.push(emp1);
}
if (!flag) {
cout << "没有足够的主存空间！！" << endl;
exit(0);
}
Sleep(2000);
//作业三撤离
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作业3") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作业三撤离！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
Sleep(2000);
//作业二撤离
for (int i = 0; i < WORK.size(); i++) {
Struct1 work1;
work1 = WORK.front();
if (work1.state == "作业2") {
for (int i = work1.begin; i < work1.begin + work1.length; i++) {
Memory[i] = 0;
}
WORK.pop();
cout << endl << "作业二撤离！" << endl;
UpdateEMP();
break;
}
else {
WORK.pop();
WORK.push(work1);
}
}
}
//主函数
int main() {
//打印提示信息
cout << "************************************************\n";
cout << " 操作系统实验内存分配算法\n";
cout << " 作者：CSDN Carmelo_7 主页： https://blog.csdn.net/Carmelo_7?spm=1000.2115.3001.5343 \n";
cout << "************************************************\n";
ifstream inFile;
inFile.open("MemoryAllocation.dat");
if (!inFile.is_open())
cout << "文件打开时候出错！！" << endl;
inFile >> MemorySize >> OSSize;
cout << "请输入主存的现有状态" << endl;
cout << "正在读取数据文件..." << endl;
Sleep(2000);
//打印空闲区说明表的初始状态
cout << "主存总大小：" << MemorySize << endl <<"操作系统占用空间：" << OSSize <<endl;
for (int i = 0;i<OSSize; i++) {
Memory[i] = 1;
}
int n = 0;
while (!inFile.eof()) {
n++;
Struct1 work1;
inFile >> work1.begin >> work1.length;
work1.state = "作业"+to_string(n);
WORK.push(work1);
}
int s = WORK.size();
for (int i = 0; i < s; i++) {
Struct1 work2;
work2 = WORK.front();
WORK.push(work2);
WORK.pop();
cout << work2.state << " 起始：" << work2.begin << " 长度：" << work2.length << endl;
for (int i = work2.begin; i < work2.length + work2.begin; i++) {
Memory[i] = 1;
}
}
/*for (int i : Memory) {
cout << i;
}*/
UpdateEMP();
cout << "请输入新的作业的申请主存数量：" << endl;
//打印作业4的申请量
int applyNum = 0;
cin >> applyNum;
cout << "作业" << n << "申请了"<< applyNum <<"主存空间" << endl;
cout << "===================================================================================" << endl;
cout << "1.首次适应算法(FF) :将所有空闲分区按照地址递增的次序链接，在申请内存分配时，从链首开始查找，将满足需求的第一个空闲分区分配给作业。" << endl;
cout << "2.循环首次适应算法（NF）：将所有空闲分区按照地址递增的次序链接，在申请内存分配时，总是从上次找到的空闲分区的下一个空闲分区开始查找，将满足需求的第一个空闲分区分配给作业" << endl;
cout << "3.最佳适应算法(BF) : 将所有空闲分区按照从小到大的顺序形成空闲分区链，在申请内存分配时，总是把满足需求的、最小的空闲分区分配给作业。" << endl;
cout << "===================================================================================" << endl;
cout << "请输入对应的序号选择算法：" << endl;
int choose = 0;
cin >> choose;
switch (choose) {
case 1:
FF(applyNum);
break;
case 2:
NF(applyNum);
break;
case 3:
BF(applyNum);
break;
default:
cout << "你输入的序号有误！！！" << endl;
exit(0);
break;
}
}
|
1
0
已为社区贡献33条内容
所有评论(0)