动态分区分配算法(First Fit，Next Fit，Best Fit，Worst Fit)-世界杯经典瞬间-梅西世界杯进球数_中国进过世界杯吗

动态分区分配算法(First Fit，Next Fit，Best Fit，Worst Fit)

一、动态分区分配算法的背景

为了能将用户程序装入内存，必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式，曾被广泛应用于上世纪60~ -80 年代的OS中，该分配万式为个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻。连续分配方式可分为四类:单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区分配算法四种方式，其中动态分区分配算法就是此实验的实验对象。

动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三方面的问题。

二、四种分配算法原理

1.首次适应算法（First Fit）

将空闲分区链以地址递增的顺序连接；在进行内存分配时，从链首开始顺序查找，直到找到一块分区的大小可以满足需求时，按照该作业的大小，从该分区中分配出内存，将剩下的空闲分区仍然链在空闲分区链中。

2.循环首次适应算法（Next Fit）

分配内存时不是从链首进行查找可以分配内存的空闲分区，而是从上一次分配内存的空闲分区的下一个分区开始查找，直到找到可以为该进程分配内存的空闲分区；

3.最佳适应算法（Best Fit）

将空闲分区链中的空闲分区按照空闲分区由小到大的顺序排序，从而形成空闲分区链。每次从链首进行查找合适的空闲分区为作业分配内存，这样每次找到的空闲分区是和作业大小最接近的，所谓“最佳”。

4.最坏适应算法（Worst Fit）

与最佳适应算法刚好相反，将空闲分区链的分区按照从大到小的顺序排序形成空闲分区链，每次查找时只要看第一个空闲分区是否满足即可。

三、四种算法过程记录

动态内存信息：

分区个数：5

各分区首址：0 50 190 340 530

各分区大小：130 70 140 80 20

1.首次适应算法（First Fit）

2.循环首次适应算法（Next Fit）

3.最佳适应算法（Best Fit）

4.最坏适应算法（Worst Fit）

四、算法的优劣比较

1.首次适应算法（First Fit）

优点：高址部分的大的空闲分区得到保留，为大作业的内存分配创造了条件；

缺点：

（1）每次都是优先利用低址部分的空闲分区，造成低址部分产生大量的外碎片。

（2）每次都是从低址部分查找，使得查找空闲分区的开销增大；

2.循环首次适应算法（Next Fit）

优点：

（1）使得空闲分区分布更加均匀；

（2）空闲分区的查找开销小；

缺点：高址部分的大空闲分区被分小，使得大作业进入无法分配内存；

3.最佳适应算法（Best Fit）

优点：第一次找到的空闲分区是大小最接近待分配内存作业大小的；

缺点:产生大量难以利用的外部碎片。

4.最坏适应算法（Worst Fit）

优点：效率高，分区查找方便；

缺点：当小作业把大空闲分区分小了，那么，大作业就找不到合适的空闲区。

五、代码实现

Partition.h

#pragma once

#include

using namespace std;

typedef struct//分区

{

static int PartitionNum;//分区数量

int m_PartitionId;//分区首地容量址

int m_PartitionSize;//分区

int m_BlockId;//空白分区首地址

}Partition;

typedef struct//进程控制块

{

static int PCBNum;//进程数量

string m_PidName;//进程名称

int m_PidSize;//进程大小

}PCB;

void ReadData();//读入数据

void Display1();

void Display_Partition();

void Display();//输出分区完后各个分区的状态

void Display_PCB();//显示进程的状态

void FirstFit();//首次适应算法

void NextFit();//循环首次适应算法

void BestFit();//最佳适应算法

void WorstFit();//最坏适应算法

Partition.cpp

#include" Partition.h"

int Partition::PartitionNum = 0;

int PCB::PCBNum = 0;

Partition* partition;

PCB* pcb;

int MIN;

void ReadData()//读入数据

{

ifstream readData;

readData.open("data.txt");

readData >> Partition::PartitionNum;//读入分区数量

partition = new Partition[Partition::PartitionNum];//开空间

for (int i = 0; i < Partition::PartitionNum; i++)//读入分区起始地址

{

readData >> partition[i].m_PartitionId;

partition[i].m_BlockId = partition[i].m_PartitionId;

}

for (int i = 0; i < Partition::PartitionNum; i++)//读入分区大小

{

readData >> partition[i].m_PartitionSize;

}

//readData >> PCB::PCBNum;//读入进程数量

//pcb = new PCB[PCB::PCBNum];

//for (int i = 0; i < PCB::PCBNum; i++)//读入进程名称

//{

// readData >> pcb[i].m_PidName;

//}

//for (int i = 0; i < PCB::PCBNum; i++)//读入进程大小

//{

// readData >> pcb[i].m_PidSize;

//}

//readData.close();

}

void FirstFit()//首次适应算法

{

bool flag = false;

int i, j;

string choose;

ReadData();

//cout << "输入MIN:";

//cin >> MIN;

//Display_PCB();

{

Display_Partition();

pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));

cout << "输入进程名称：";

cin >> pcb[PCB::PCBNum - 1].m_PidName;

cout << "输入进程大小:";

cin >> pcb[PCB::PCBNum - 1].m_PidSize;

i = PCB::PCBNum - 1;

for (j = 0; j < Partition::PartitionNum; j++)

{

if (pcb[i].m_PidSize <= partition[j].m_PartitionSize)

{

partition[j].m_PartitionSize -= pcb[i].m_PidSize;

partition[j].m_BlockId += partition[j].m_PartitionSize;

if (partition[j].m_PartitionSize <= MIN)

{

partition[j].m_PartitionSize = 0;

}

flag = true;

break;

}

if (flag)

{

flag = false;

cout << "进程" << pcb[i].m_PidName << "分配到分区" << partition[j].m_PartitionId << endl;

}

else

{

cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;

}

Display1();

cout << "继续分配按Y" << endl;

cin >> choose;

} while (choose == "Y");

}

void NextFit()//循环首次适应算法

{

int pos = 0;

bool flag = false;

int i, j;

string choose;

ReadData();

//Display_PCB();

/*cout << "输入MIN:";

cin >> MIN;*/

{

Display_Partition();

pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum+1));

cout << "输入进程名称：";

cin >> pcb[PCB::PCBNum - 1].m_PidName;

cout << "输入进程大小:";

cin >> pcb[PCB::PCBNum - 1].m_PidSize;

i = PCB::PCBNum - 1;

for (j = pos;; j++)

{

if (pos >= PCB::PCBNum)

{

pos = 0;

}

if (pcb[i].m_PidSize <= partition[j].m_PartitionSize)

{

partition[j].m_PartitionSize -= pcb[i].m_PidSize;

partition[j].m_BlockId += partition[j].m_PartitionSize;

if (partition[j].m_PartitionSize <= MIN)

{

partition[j].m_PartitionSize = 0;

}

flag = true;

pos = j + 1;

if (pos == PCB::PCBNum)

{

pos = 0;

}

break;

}

if (flag)

{

flag = false;

cout << "进程" << pcb[i].m_PidName << "分配到分区" << partition[j].m_PartitionId << endl;

}

else

{

cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;

}

Display1();

cout << "继续分配按Y" << endl;

cin >> choose;

} while (choose == "Y");

}

void BestFit()//最佳适应算法

{

int pos = 0;

bool flag = false;

int i, j;

multimap m;

multimap::iterator ip;

string choose;

ReadData();

//Display_PCB();

/*cout << "输入MIN:";

cin >> MIN;*/

{

Display_Partition();

pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));

cout << "输入进程名称：";

cin >> pcb[PCB::PCBNum - 1].m_PidName;

cout << "输入进程大小:";

cin >> pcb[PCB::PCBNum - 1].m_PidSize;

i = PCB::PCBNum - 1;

m.clear();

for (j = 0; j < Partition::PartitionNum; j++)//按从小带大排序

{

m.insert(make_pair(partition[j].m_PartitionSize, partition + j));

}

for (ip = m.begin(); ip != m.end();)

{

if (pcb[i].m_PidSize <= ip->first)

{

ip->second->m_PartitionSize -= pcb[i].m_PidSize;

ip->second->m_BlockId += ip->second->m_PartitionSize;

/*if (ip->second->m_PartitionSize <= MIN)

{

ip->second->m_PartitionSize = 0;

}*/

flag = true;

break;

}

else

{

ip++;

}

if (flag)

{

flag = false;

cout << "进程" << pcb[i].m_PidName << "分配到分区" << ip->second->m_PartitionId << endl;

}

else

{

cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;

}

Display();

cout << "继续分配按Y" << endl;

cin >> choose;

} while (choose == "Y");

}

void WorstFit()//最坏适应算法

{

int pos = 0;

bool flag = false;

int i, j;

multimap> m;

multimap::iterator ip = m.begin();

string choose;

ReadData();

//Display_PCB();

/*cout << "输入MIN:";

cin >> MIN;*/

{

Display_Partition();

pcb = (PCB*)realloc(pcb, sizeof(PCB)*(PCB::PCBNum + 1));

cout << "输入进程名称：";

cin >> pcb[PCB::PCBNum - 1].m_PidName;

cout << "输入进程大小:";

cin >> pcb[PCB::PCBNum - 1].m_PidSize;

i = PCB::PCBNum - 1;

m.clear();

for (j = 0; j < Partition::PartitionNum; j++)//按从大到小排序

{

m.insert(make_pair(partition[j].m_PartitionSize, partition + j));

}

for (ip = m.begin(); ip != m.end();)

{

if (pcb[i].m_PidSize <= ip->first)

{

ip->second->m_PartitionSize -= pcb[i].m_PidSize;

ip->second->m_BlockId += ip->second->m_PartitionSize;

/*if (ip->second->m_PartitionSize <= MIN)

{

ip->second->m_PartitionSize = 0;

}*/

flag = true;

break;

}

else

{

ip++;

}

if (flag)

{

flag = false;

cout << "进程" << pcb[i].m_PidName << "分配到分区" << ip->second->m_PartitionId << endl;

}

else

{

cout << "进程" << pcb[i].m_PidName << "分配失败！" << endl;

}

Display();

cout << "继续分配按Y" << endl;

cin >> choose;

} while (choose == "Y");

}

void Display()

{

int i;

set s;

for (i = 0; i < Partition::PartitionNum; i++)

{

s.insert(partition[i].m_PartitionSize);

}

cout << "空白分区链:";

for (auto& e : s)

{

cout << e << "->";

}

cout << "NULL";

cout << endl;

}

void Display1()

{

int i;

map m;

for (i = 0; i < Partition::PartitionNum; i++)

{

m.insert(make_pair(partition[i].m_PartitionId, partition + i));

}

cout << "空白分区链:";

for (auto& e : m)

{

if (e.second->m_PartitionSize != 0)

{

cout << e.second->m_PartitionSize << "->";

}

cout << "NULL";

cout << endl;

}

void Display_Partition()

{

cout << endl << "分区起始地址 ";

for (int i = 0; i < Partition::PartitionNum; i++)

{

printf("%-d ", partition[i].m_PartitionId);

}

cout << endl << "分区大小: ";

for (int i = 0; i < Partition::PartitionNum; i++)

{

printf("%-d ", partition[i].m_PartitionSize);

}

cout << endl << endl;

}

void Display_PCB()

{

cout << endl << "进程id: ";

for (int i = 0; i < PCB::PCBNum; i++)

{

printf("%3s ", pcb[i].m_PidName.c_str());

}

cout << endl << "进程大小:";

for (int i = 0; i < PCB::PCBNum; i++)

{

printf("%3d ", pcb[i].m_PidSize);

}

cout << endl << endl;

}

Main.cpp

#include"Partition.h"

int main()

{

int choose;

while (1)

{

cout << "请选择实现的算法：" << endl;

cout << "***** 1 - 首次适应算法 *****" << endl;

cout << "***** 2 - 循环首次适应算法 *****" << endl;

cout << "***** 3 - 最佳适应算法 *****" << endl;

cout << "***** 4 - 最坏适应算法 *****" << endl;

cout << "***** 0 - 结束 *****" << endl;

cout << "输入你的选择： ";

cin >> choose;

switch (choose)

{

case 0:exit(0); break;

case 1:FirstFit(); break;

case 2:NextFit(); break;

case 3:BestFit(); break;

case 4:WorstFit(); break;

default:cout << "请输入正确的序号：" << endl;

}

system("pause");

return 0;

}

叫停！近一年超50家银行取消无卡存取业务
GOOD LUCK GLADIUS男装是什么牌子，这个牌子好吗？