最差拟合算法 [英] Worst fit algorithm

问题描述

我创建了一个代码，它使用大小为 256 的数组来演示 First Fit Algorithm，该代码显示了一个地图，显示了如何根据 First Fit Algorithm 存储内存，该代码允许用户删除内存位置也是如此，我想创建与我的代码相同的概念，但使用最差拟合算法，我已经阅读了很多文章并了解了最差拟合算法的工作原理，但我想不出一种方法使我的代码使用Worst Fit Algorithm ，在我的代码中使用 First Fit 比 Worst Fit 更容易，有人可以告诉我如何实现我的代码以使用 Worst Fit Algorithm ，将不胜感激.

I've created a code which demonstrates the First Fit Algorithm using an array of size 256 , the code displays a map showing how the memory is being stored according to the First Fit Algorithm, the code allows the user to delete a memory location too , I would like to create the same concept of my code but using the Worst Fit Algorithm , I've read many articles and understood how the Worst Fit Algorithm works but I can't think of a way so that my code works using the Worst Fit Algorithm , it's easier to use the First Fit than the Worst Fit on my code, could someone show me how to implement my code to use the Worst Fit Algorithm , would be appreciated a lot.

代码如下:

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 代码的工作原理是找到足够大的第一个内存块来容纳您请求的分配.找到适合的块后立即停止.

Your code for FirstFit works by finding the first block of memory large enough to hold your requested allocation. You stop as soon as you find any block that will fit.

  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，您只需找到最大的可用连续内存块并分配它(如果它足够大).

For WorstFit, you simply need to find the largest available contiguous block of memory and allocate that, if it's large enough.

  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;
  }

这篇关于最差拟合算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！