操作系统: 最佳适配算法和邻近适配算法的模拟实现(内存分配算法)

实现动态分区的分配算法。

(1) 最佳适配算法:选择内存空闲块中最适合进程大小的块分配。

(2) 邻近适配算法:从上一次分配的地址开始查找符合要求的块,所查找到的第一个满足要求的空闲块就分配给进程。

模拟添加进程的时候,假定内存是一块完整的空闲区,对于算法(1)来说,分配的时候遍历所有的空闲内存块,找出其中最适合的一块,注意此时内存分区的总块数可能已经发生了变化;

对于算法(2)来说,则需要从上次分配的内存块(使用变量记录即可)接着向下找到第一个满足条件的块即可,内存分区的总块可能也已经发生了变化。

模拟删除进程(释放内存)的时候,则需要注意如果当前内存块的上下有空闲块,则需要将其合并为一整个空闲块,也需要注意内存总块的数量变化。

最佳适配算法

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
struct node
{
	int num;
	int is_data;
};
int main()
{
	vector<node> cluster;
	vector<node> TTemp;
	map <int,int> mp;
	mp.clear();
	node temp;
	int R_num;
	int curnum;

	temp.is_data=0;
	temp.num=10;
	cluster.push_back(temp);

    cout<<"请使用add命令添加一个进程,delete命令删除一个进程!"<<endl;
    while(1)
    {
   	   string s;
   	   cin>>s;
   	   if(s=="add")
   	   {
      	cout<<"请输入进程号及其的大小"<<endl;
	   	cin>>R_num>>curnum;

		int flag=0;
		int curIndex;

		int cmp=11;
    	for(int i=0;i<cluster.size();i++)
		{
			if(cluster[i].is_data==0&&cluster[i].num>=curnum)
			{
				flag=1;
				if(cluster[i].num-curnum<cmp)
				{
					curIndex=i;
					cmp=cluster[i].num-curnum;
				}
			}
		}
		if(flag)
		{
			cluster[curIndex].is_data=1;
			mp[R_num]=curIndex;

			node op;
			TTemp.clear();
			int is_flag=0;
			if(cluster[curIndex].num>curnum)
			{
				op.is_data=0;
				op.num=cluster[curIndex].num-curnum;
				is_flag=1;
			}

		for(int i=0;i<cluster.size();i++)
		{
			if(i==curIndex)
			{
				cluster[curIndex].num=curnum;
				TTemp.push_back(cluster[curIndex]);
				mp[R_num]=i;

				if(is_flag)
				{
					TTemp.push_back(op);
				}
			}
			else
			TTemp.push_back(cluster[i]);
		}

		cluster.swap(TTemp);

		for(int i=0;i<cluster.size();i++)
		cout<<"大小 "<<cluster[i].num<<"  是否分配 "<<cluster[i].is_data<<endl;

	}
	else
	{
		cout<<"内存不足!"<<endl;
	}
 }

     else if(s=="delete")
     {
   	   	  	int deletenum;
			cout<<"请输入删除的进程:"<<endl;
			cin>>deletenum;

		int i=mp[deletenum];
		while(--i>=0 && cluster[i].is_data==0)
		{

		}
		int j=mp[deletenum];
		while(++j<cluster.size() && cluster[j].is_data==0)
		{

		}

		node kk;
		kk.num=0;
		for(int e=i+1;e<=j-1;e++)
		{
			kk.num+=cluster[e].num;
		}
		kk.is_data=0;

		TTemp.clear();
		for(int p=0;p<cluster.size();)
		{
			if(p==i+1)
			{
				p=j;
				TTemp.push_back(kk);
			}
			else{
				TTemp.push_back(cluster[p]);
	      		p++;
		}

	}
		cluster.swap(TTemp);

		for(int i=0;i<cluster.size();i++)
		cout<<"大小 "<<cluster[i].num<<"  是否分配 "<<cluster[i].is_data<<endl;

   	   }
   }
	return 0;
}

邻近适配算法

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
struct node
{
	int num;
	int is_data;
};
int main()
{
	vector<node> cluster;
	vector<node> TTemp;
	map <int,int> mp;
	mp.clear();
	node temp;
	int R_num;
	int curnum;
	int last_ID=0;
	temp.is_data=0;
	temp.num=10;
	cluster.push_back(temp);

    cout<<"请使用add命令添加一个进程,delete命令删除一个进程!"<<endl;

    while(1)
    {
   	   string s;
   	   cin>>s;
   	   if(s=="add")
   	   {
      	cout<<"请输入进程号及其的大小"<<endl;
	   	cin>>R_num>>curnum;

		int flag=0;
		int curIndex;

    	//for(int i=beg_pos;i<cluster.size();i++)
    	int i=last_ID+1;
    	while(1)
		{
			if(i==cluster.size())
			i=0;
			if(cluster[i].is_data==0&&cluster[i].num>=curnum)
			{
				flag=1;
			    curIndex=i;
			    break;
			}
			i++;
		}
		if(flag)
		{
			cluster[curIndex].is_data=1;
			mp[R_num]=curIndex;

			node op;
			TTemp.clear();
			int is_flag=0;
			if(cluster[curIndex].num>curnum)
			{
				op.is_data=0;
				op.num=cluster[curIndex].num-curnum;
				is_flag=1;
			}

		for(int i=0;i<cluster.size();i++)
		{
			if(i==curIndex)
			{
				cluster[curIndex].num=curnum;
				TTemp.push_back(cluster[curIndex]);
				mp[R_num]=i;
                last_ID=i;
				if(is_flag)
				{
					TTemp.push_back(op);
				}
			}
			else
			TTemp.push_back(cluster[i]);
		}

		cluster.swap(TTemp);

		for(int i=0;i<cluster.size();i++)
		cout<<"大小 "<<cluster[i].num<<"  是否分配 "<<cluster[i].is_data<<endl;

	}
	else
	{
		cout<<"内存不足!"<<endl;
	}
 }

     else if(s=="delete")
     {
   	   	  	int deletenum;
			cout<<"请输入删除的进程:"<<endl;
			cin>>deletenum;

		int i=mp[deletenum];
		while(--i>=0 && cluster[i].is_data==0)
		{

		}
		int j=mp[deletenum];
		while(++j<cluster.size() && cluster[j].is_data==0)
		{

		}

		node kk;
		kk.num=0;
		for(int e=i+1;e<=j-1;e++)
		{
			kk.num+=cluster[e].num;
		}
		kk.is_data=0;

		TTemp.clear();
		for(int p=0;p<cluster.size();)
		{
			if(p==last_ID)
			last_ID=TTemp.size();
			if(p==i+1)
			{
				p=j;
				TTemp.push_back(kk);
			}
			else{
				TTemp.push_back(cluster[p]);
	      		p++;
		}

	}
		cluster.swap(TTemp);

		for(int i=0;i<cluster.size();i++)
		cout<<"大小 "<<cluster[i].num<<"  是否分配 "<<cluster[i].is_data<<endl;

   	   }
   }
	return 0;
}

时间: 12-26

操作系统: 最佳适配算法和邻近适配算法的模拟实现(内存分配算法)的相关文章

MINI3内存分配算法

1 最差适应算法 2 #ifdef USING_WORST_FIT 3 { 4 //先找到第一个满足要求的空洞, 5 //再以第一个为标准寻找最适合的空洞. 6 //当最适合的空洞完全吻合 7 //就直接划给它,当空洞较大时就切割. 8 9 //首先注册目标指针.目标前一个指针.头指针 10 //记录目标大小和目前最适合大小 11 register struct hole *hp; 12 register struct hole *prevAim_ptr; 13 register struct

内存分配算法 之 首次适应-最佳适应

程序在向操作系统申请内存空间的时候,操作系统会扫描空闲块链表并从中取出一块足够大的分配,与之对应的算法有 首次适应 和 最佳适应,顾名思义,首次适应就是把首次遇到的足够大的空闲块分配给应用程序,最佳适应就是扫描完空闲块链表把大小与申请空间最匹配的空闲块分配给应用程序. mem.h        程序用到的头文件 main.c       主函数 fit.c        具体的实现函数 这里使用make来编译使用,若是读者还没接触过make的, 请移步参考我写的这篇文章:http://netca

我所理解的内存分配算法(一)

内存分配从本质上来说是一种空间管理算法,给你一块连续的空间,提供存储服务,那么你的空间管理跟分配要采用什么样的算法才会比较高效? Bump-the-Pointer Bump-the-Pointer是最简单的算法.HotSpot的MM白皮书是这么描述btp的, That is, the end of the previously allocated object is always kept track of. When a new allocation request needs to be s

垃圾收集与内存分配算法

3.1判断对象是否已死引用-计数算法 给对象添加一个引用计数器,每当有一个地方引用它时,计数器值就加1:当引用失效时,计数器值就减1:任何时候计数器为0的对象就是不可能再被使用的. 3.2判断对象是否已死引用-可达性分析算法 在主流的程序语言中,都是通过可达性分析来判断对象是否存活的.这个算法的基本思路就是通过一系列称为“GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链,当一个对象至GC Roots没有任何引用链相连时,则证明此对象不可用. 在java语言中

合约广告中的流量分配算法

简介 合约广告是一种基于合约的广告模式,在线广告中的一种主流方式是担保式投放(Guaranteed Delivery,GD).GD是一种量优于质的广告投放方式,需要保证广告主能够获得在合约中约定的受众用户的流量.GD中,媒体的流量按照属性划分,媒体要给不同的广告主按照合同分配约定好的流量.Ad Server的准则是希望在每一次展现满足多个合约时,选择合适的广告主,以使得每个广告主效果最好,同时能够更有效的分配流量.如下图所示,supply为媒体方,提供流量,媒体的流量可以按照性别.年龄.地域划分

RT-thread内核之小内存管理算法

 一.动态内存管理 动态内存管理是一个真实的堆(Heap)内存管理模块,可以在当前资源满足的情况下,根据用户的需求分配任意大小的内存块.而当用户不需要再使用这些内存块时,又可以释放回堆中供其他应用分配使用.RT-Thread系统为了满足不同的需求,提供了两套不同的动态内存管理算法,分别是小内存管理算法和SLAB内存管理算法.小堆内存管理模块主要针对系统资源比较少,一般用于小于2M内存空间的系统:而SLAB内存管理模块则主要是在系统资源比较丰富时,提供了一种近似多内存池管理算法的快速算法. 两种内

MFC界面开发(QQ透明皮肤:多层算法,一键适配各种背景 )

http://blog.csdn.net/kent19900125/article/category/1368203/3 QQ透明皮肤:多层算法,一键适配各种背景 . http://blog.csdn.net/liu__ke/article/details/8889171

操作系统中的内存管理算法

操作系统的内存管理算法主要分为最近最久未使用算法(LRU),最近最少使用算法(LFU),先进先出算法,最优置换算法.这些算法都比较容易实现,在上课时做了一个课程实验,写了相关的程序: #include <iostream> #include <queue> #include <stack> #include <cstdio> #include <cstring> #include <cstdlib> #include <ctim

C#语言中的动态数组(ArrayList)模拟常用页面置换算法(FIFO、LRU、Optimal)

目录 00 简介 01 算法概述 02 公用方法 03 先进先出置换算法(FIFO) 04 最近最久未使用(LRU)算法 05 最佳置换算法(OPT) 00 简介 页面置换算法主要是记录内存的忙闲状态,为进程分配和释放内存.当主存的空间太小而无法装入所有的进程时,就需要在内存和硬盘之间进行调度操作. 多数操作系统只采用某种特定的页面置换算法进行置换,无法预先探测当前运行进程的页面访问模式,因此不能根据不同的页面访问模式,选用不同的页面置换算法.当然,如果能对不同的访问模式选取相应的页面置换算法,