c++ - 最差拟合算法
问题描述
我创建了一个代码,该代码使用大小为 256 的数组演示了 First Fit 算法,该代码显示了一个地图,显示了如何根据 First Fit 算法存储内存,该代码也允许用户删除内存位置,我想为我的代码创建相同的概念,但使用 Worst Fit Algorithm ,我阅读了很多文章并了解 Worst Fit Algorithm 的工作原理,但我想不出一种方法让我的代码使用 Worst Fit算法,在我的代码上使用 First Fit 比 Worst Fit 更容易,有人可以告诉我如何实现我的代码以使用 Worst Fit Algorithm ,将不胜感激。
这是代码:
include <iostream>
#include <cmath>
using namespace std;
int PutInMemory(int memory[], int size) {
if (size < 1) cout << "Error!" << endl;
int firstSize = 0;
int j;
for (int i = 0; i < 256; i++) {
if (memory[i] < 0 && abs(memory[i]) >= size) {
j = i;
firstSize += abs(memory[j]);
break;
}
}
if (firstSize < size) {
cout << "Out of Memory";
return 0;
}
if (j + size <= 256) {
memory[j] = size;
for (int i = j + 1; i < j + size; i++)
memory[i] = 0;
int i = j + size;
int count = 0;
while (memory[i] <= -1 && i < 256) {
count++;
i++;
}
if (count != 0) {
memory[i - 1] = -count;
memory[j + size] = -count;
}
return j;
}
else {
cout << "Out of memory";
}
}
void DelSeg(int memory[], int n) {
int count = memory[n];
int prev = 0;
int next = count - 1;
int i = n + 1;
int pos = n;
if (memory[n - 1] < -1 && n != 0) {
i += memory[n - 1];
prev = -memory[n - 1];
count -= memory[n - 1];
pos = i;
}
while (true) {
for (i; i < pos + count - 1; i++) {
memory[i] = -1;
}
if (memory[i + 1] < -1) {
count += -memory[i + 1] + 1;
next = -memory[i + 1];
}
else {
break;
}
}
memory[n - prev] = 0 - count;
memory[n + next] = 0 - count;
}
void checkMemory(int memory[]) {
int countFreeSeg = 0;
int countFullSeg = 0;
int countFullMem = 0;
int countFreeMem = 0;
for (int i = 0; i < 256; i++) {
if (memory[i] < 0) {
if (memory[i] < 0) cout << "Beginning of the adress:" << i << ", ";
int count = 0;
while (memory[i] < 0 && i < 256) {
count++;
i++;
}
countFreeSeg++;
cout << "Size = " << count << endl;
countFreeMem += count;
i--;
}
}
cout << "Number of free processes = " << countFreeSeg << endl << endl;
cout << "Number of free memory = " << countFreeMem << endl << endl;
for (int i = 0; i < 256; i++) {
if (memory[i] > 0) {
cout << "Beginning adress: " << i << ", size - " << memory[i] << endl;
countFullMem += memory[i];
i += memory[i] - 1;
countFullSeg++;
}
}
cout << "Number of occupied processes = " << countFullSeg << endl;
cout << "Number of occupied memory = " << countFullMem << endl;
}
void print(int memory[]) {
for (int i = 0; i < 256; i++) {
cout << memory[i] << " ";
}
}
int main()
{
int memory[256];
memory[0] = -256;
for (int i = 1; i < 256; i++) {
memory[i] = -1;
}
while (true) {
system("cls");
cout << "1.Allocate Memory \n2.Free memory segment\n3.Get information about the
memory\n4.Exit" << endl;
int choice;
cin >> choice;
int m = 0;
switch (choice)
{
case 1:
system("cls");
cout << "Enter the amount of memory to be entered:" << endl;
cin >> m;
cout << PutInMemory(memory, m) << endl;
break;
case 2:
system("cls");
cout << "Enter the starting address of the memory location:" << endl;
cin >> m;
DelSeg(memory, m);
break;
case 3:
checkMemory(memory);
print(memory);
break;
case 4:
system("cls");
exit(0);
break;
default:
cout << "Incorrect entry" << endl;
break;
}
system("pause");
}
}
解决方案
您的 FirstFit 代码通过查找第一个足够大的内存块来容纳您请求的分配来工作。一旦找到任何适合的块,您就会停下来。
int firstSize = 0;
int j;
for (int i = 0; i < 256; i++) {
if (memory[i] < 0 && abs(memory[i]) >= size) {
j = i;
firstSize += abs(memory[j]);
break;
}
}
if (firstSize < size) {
cout << "Out of Memory";
return 0;
}
对于 WorstFit,您只需要找到最大的可用连续内存块并分配它,如果它足够大的话。
int worstSize = 0;
int j;
for (int i = 0; i < 256; i++) {
if (memory[i] < 0 && abs(memory[i]) >= worstSize) {
j = i;
worstSize = abs(memory[j]);
}
}
if (worstSize < size) {
cout << "Out of Memory";
return 0;
}
推荐阅读
- angular - I want to remove identity server from "ABP" angular app
- css - font-feature-settings : 'tnum' , 'lnum' : Not Working
- xpath - XPath text() returns 2 Values how to combine them to one
- java - Spring WebClient odd behaviour
- excel - 如何选择具有条件格式范围的活动单元格和活动单元格列
- sql - 如何有效计算多条经/纬度之间的最短距离(Oracle SQL)?
- excel - VBA 外部数据源
- mongodb - 匹配聚合管道中的任何日期元素 $
- git - 用于私有 gitlab 存储库的 Ansible-Galaxy,只为所有角色引用一个角色的文件
- excel - Excel - 自动递增值的公式/宏