devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

操作系统实验：首次适应算法、最佳适应算法、最坏适应算法_首次适应算法c语言

作者：我家小花儿 | 2024-05-26 03:11:45

赞

踩

首次适应算法c语言

1、首次适应算法

概念：首次适应算法从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。

实验要求：已知作业名、作业大小、作业提交时间、内存容量、碎片大小，要求使用分区大小不等的内存分区方法和首次适应分配算法给每次到来的作业分配内存。输出内存分区情况和分配情况。

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. #define FREE 0
  5. #define  BUSY 1
  6. #define  MAX_length 300
  7. const double debri = 20; //设置碎片大小
  8. // FREE代表空闲  BUSY代表已分配 
  9.  
  10. typedef struct free_area //首先定义空闲区分表结构
  11. {
  12. int flag;
  13. int size;
  14. int number;
  15. int begin_address;
  16.  }Elemtype;
  17.  
  18. typedef struct Free_Node
  19. {
  20. 	Elemtype date;
  21. 	struct Free_Node *prior;
  22. 	struct Free_Node *next;
  23. }Free_Node,*pNod;
  24.  
  25. pNod headNode;
  26. pNod initNode;
  27. int m_allocation();//作业分配
  28. int free(int number);//作业回收
  29. bool ff(int number,int size);//首次适应算法
  30. void show();//查看分配
  31. void init();//初始化
  32.  
  33. int main()
  34. {
  35. 	int tag=0;
  36. 	int number;
  37. 	init();
  38. 	while(tag!=4)
  39. 	{
  40. 		cout<<"请选择操作： 1-申请作业，2-作业回收，3-显示作业状况，4-退出"<<endl;
  41. 		cin>>tag;
  42. 		switch(tag)
  43. 			{
  44. 		    case 1:
  45. 				m_allocation();
  46. 				    break;
  47. 			case 2:
  48. 				cout<<"请输入需要回收的number号："<<endl;
  49. 				cin>>number;
  50. 				free(number);
  51. 					break;
  52. 			case 3:
  53. 				show();
  54. 				break;
  55. 			default:
  56. 				return 0;
  57. 		    }
  58. 	}
  59. 	return 0;
  60. }
  61.  
  62. void init()
  63. {
  64. 	headNode=new Free_Node;
  65. 	initNode = new Free_Node;
  66. 	headNode->prior=NULL;
  67. 	headNode->next=initNode;
  68. 	initNode->prior=headNode;
  69. 	initNode->next=NULL;
  70. 	initNode->date.begin_address=0;
  71. 	initNode->date.flag=FREE;
  72. 	initNode->date.number= 0;
  73. 	initNode->date.size=MAX_length;
  74. }
  75.  
  76. //实现作业分配
  77. int m_allocation()
  78. {
  79. 	int number,size1;
  80. 	cout<<"请输入作业号：";
  81. 	cin>>number;
  82. 	cout<<"请输入所需作业大小：";
  83. 	cin>>size1;
  84.  
  85. 	if(ff(number,size1))
  86. 	{		
  87. 		cout<<"分配成功！"<<endl;
  88. 	}
  89. 	else cout<<"分配失败！"<<endl;
  90. 	return 1;
  91. }
  92.  
  93. bool ff(int number,int size)//首次适应算法
  94. {
  95. 	 pNod temp= new Free_Node;
  96. 	 Free_Node *p=headNode->next;  //从首节点开始
  97. 	 temp->date.number=number;
  98. 	 temp->date.size=size;
  99. 	 temp->date.flag=BUSY;
  100. 	while(p)
  101. 	{
  102. 		if (p->date.flag==FREE &&  p->date.size == size )//请求大小刚好满足
  103. 		{
  104. 			p->date.flag=BUSY;
  105. 			p->date.number=number;
  106. 			return true;
  107. 		}
  108. 		if (p->date.flag==FREE && p->date.size>size)//说明还有其他的空闲区间
  109. 		{
  110. 			temp->next=p;
  111. 			temp->prior=p->prior;
  112. 			temp->date.begin_address=p->date.begin_address;
  113. 			p->prior->next=temp;
  114. 			p->prior=temp;
  115. 			p->date.begin_address=temp->date.begin_address+temp->date.size;//空闲分区开始地址+此次分配的空间
  116. 			p->date.size-=size;      //分配空闲作业
  117. 		    return true;
  118. 		}
  119. 		p=p->next;
  120. 	}
  121. 	return false;
  122. }
  123.  
  124. int free(int number)//主存回收
  125. {
  126. 	Free_Node *p=headNode->next;
  127. 	while(p)
  128. 	{
  129. 		if (p->date.number==number)//找到要回收的number区域
  130. 		{
  131. 			p->date.flag=FREE;
  132. 			p->date.number=FREE;
  133. 			//判断P与前后区域关系
  134.  
  135. 			//1、回收分区r上临一个空闲分区，此时应该合并为一个连续的空闲区，其始址为r上相邻的分区的首地址，而大小为两者大小之和
  136. 			if (p->prior->date.flag==FREE&&p->next->date.flag!=FREE)   
  137. 			{
  138. 				p->prior->date.size+=p->date.size;
  139. 				p->prior->next=p->next;  //将要回收分区的前后两个分区链接起来
  140. 				p->next->prior=p->prior;
  141. 			}
  142. 			//2、回收分区r与下相邻空闲分区，合并后仍然为空闲区，该空闲区的始址为回收分区r的地址。大小为两者之和
  143. 			else if (p->prior->date.flag!=FREE&&p->next->date.flag==FREE)
  144. 			{
  145. 				p->date.size+=p->next->date.size;   //合并前后两个分区
  146. 				if(p->next->next)      //下一个分区不是最后一个分区
  147. 				{
  148. 					p->next->next->prior=p;
  149. 				    p->next = p->next->next;
  150. 				}
  151. 				else 
  152. 					p->next=p->next->next;
  153. 			}
  154. 			//3、回收部分r与上下空闲区相邻，此时将这三个区域合并，始址为r上相邻区域的地址，大小为三个分区大小之和
  155. 			else if(p->prior->date.flag==FREE&&p->next->date.flag==FREE)
  156. 			{
  157. 				p->prior->date.size+=p->date.size+p->next->date.size;
  158. 				if(p->next->next) //如果最后一个节点不是最后一个节点
  159. 				{
  160. 				p->next->next->prior=p->prior;
  161. 				p->prior->next=p->next->next;
  162. 				}
  163. 				else p->prior->next=p->next->next;
  164. 			}
  165. 			//4、当回收部分r上下区域都为非空闲区域，此时建立一个新的空闲分区，并且加入到空闲区队列中去
  166. 			else if(p->prior->date.flag!=FREE && p->next->date.flag!=FREE)
  167. 			{
  168. 				//只用把结点的number和flag改成free就行了
  169. 			}
  170. 			break;
  171. 		}
  172. 		p=p->next;
  173. 	}
  174. 	cout<<"回收成功！"<<endl;
  175. 	return 1;
  176. }
  177.  
  178. void show()
  179. {
  180. 	cout<< endl;
  181. 	cout<<"作业分配情况"<<endl;
  182. 	int i = 1;
  183. 	Free_Node *p=headNode->next;
  184. 	cout<<"分区号"  << "  作业号" << "\t起始地址"  << "    作业大小"  << "   分区状态" << endl;
  185. 	while(p)
  186. 	{
  187. 		cout << i++ << "\t " << p->date.number << '\t' << p->date.begin_address << "\t\t" << p->date.size << '\t';
  188. 		if (p->date.flag==FREE)
  189. 			cout<<"空闲"<<endl;
  190. 		else
  191. 			 cout<<"已分配"<<endl;
  192. 		p=p->next;
  193. 	}
  194. }

2、最佳适应算法

概念：最佳适应算法是指从全部空闲区中找出能满足作业要求且大小最小的空闲分区的一种计算方法，这种方法能使碎片尽量小。

  1. #include <iostream>
  2. #include <stdlib.h>
  3. using namespace std;
  4.  
  5. #define FREE 0
  6. #define  BUSY 1
  7. #define  MAX_length 300
  8.  
  9. typedef struct freeArea
  10. {
  11. 	int flag;
  12. 	int size;
  13. 	int ID;
  14. 	int address;
  15. }Elemtype;
  16.  
  17. typedef struct Free_Node
  18. {
  19. 	Elemtype date;
  20. 	struct Free_Node *front;
  21. 	struct Free_Node *next;
  22. }Free_Node,*FNodeList;
  23.  
  24. FNodeList block_first;
  25. FNodeList block_last;
  26. int alloc(int tag);//内存分配
  27. int free(int ID);//内存回收
  28. int best_fit(int ID,int size);//最佳适应算法
  29. void show();//查看分配
  30. void init();//初始化
  31. void menu();
  32.  
  33. //初始化 
  34. void init()
  35. {
  36. 	block_first=new Free_Node;
  37. 	block_last = new Free_Node;
  38. 	block_first->front=NULL;
  39. 	block_first->next=block_last;
  40. 	block_last->front=block_first;
  41. 	block_last->next=NULL;
  42. 	block_last->date.address=0;
  43. 	block_last->date.flag=FREE;
  44. 	block_last->date.ID=FREE;
  45. 	block_last->date.size=MAX_length;
  46. }
  47.  
  48. //实现内存分配
  49. int alloc(int tag)
  50. {
  51. 	int ID,size1;
  52. 	cout<<"请输入作业号：";
  53. 	cin>>ID;
  54. 	cout<<"请输入所需内存大小：";
  55. 	cin>>size1;
  56. 	if (ID<=0 || size1<=0)
  57. 	{
  58. 		cout<<"ERROR,请输入正确的ID和请求大小"<<endl;
  59. 		return 0;
  60. 	}
  61. 	
  62. 	if (tag==1)//采用最佳适应算法
  63. 	{
  64. 		if (best_fit(ID,size1))
  65. 		{
  66. 			cout<<"分配成功！"<<endl;
  67. 		}
  68. 		else cout<<"分配失败！"<<endl;
  69. 		return 1;
  70. 	}
  71. 	
  72. }
  73.  
  74. int best_fit(int ID,int size)//最佳适应算法
  75. {
  76. 	int surplus;//记录可用内存与需求内存的差值
  77. 	FNodeList temp=(FNodeList)malloc(sizeof(Free_Node));
  78. 	Free_Node *p=block_first->next;
  79. 	temp->date.ID=ID;
  80. 	temp->date.size=size;
  81. 	temp->date.flag=BUSY;
  82. 	Free_Node *q=NULL;//记录最佳位置
  83. 	while(p)//遍历链表，找到第一个可用的空闲区间将他给q
  84. 	{
  85. 		if (p->date.flag==FREE&&p->date.size>=size)
  86. 		{
  87. 			q=p;
  88. 			surplus=p->date.size-size;
  89. 			break;
  90. 		}
  91. 		p=p->next;
  92. 	}
  93. 	while(p)//继续遍历，找到更加合适的位置
  94. 	{
  95. 		if (p->date.flag==FREE&&p->date.size==size)
  96. 		{
  97. 			p->date.flag=BUSY;
  98. 			p->date.ID=ID;
  99. 			return 1;
  100. 			break;
  101. 		}
  102. 		if (p->date.flag==FREE&&p->date.size>size)
  103. 		{
  104. 			if (surplus>p->date.size-size)
  105. 			{
  106. 				surplus=p->date.size-size;
  107. 				q=p;
  108. 			}
  109.  
  110. 		}
  111. 		p=p->next;
  112. 	}
  113. 	if (q==NULL)//如果没有找到位置
  114. 	{
  115. 		return 0;
  116. 	}
  117. 	else//找到了最佳位置
  118. 	{
  119. 		temp->next=q;
  120. 		temp->front=q->front;
  121. 		temp->date.address=q->date.address;
  122. 		q->front->next=temp;
  123. 		q->front=temp;
  124. 		q->date.size=surplus;
  125. 		q->date.address+=size;
  126. 		return 1;
  127. 	}
  128. }
  129.  
  130. int free(int ID)//主存回收
  131. {
  132. 	Free_Node *p=block_first->next;
  133. 	while(p)
  134. 	{
  135. 		if (p->date.ID==ID)//找到要回收的ID区域
  136. 		{
  137. 			p->date.flag=FREE;
  138. 			p->date.ID=FREE;
  139. 			//判断P与前后区域关系
  140. 			if (p->front->date.flag==FREE&&p->next->date.flag!=FREE)
  141. 			{
  142. 				p->front->date.size+=p->date.size;
  143. 				p->front->next=p->next;
  144. 				p->next->front=p->front;
  145. 			}
  146. 			if (p->front->date.flag!=FREE&&p->next->date.flag==FREE)
  147. 			{
  148. 				p->date.size+=p->next->date.size;
  149. 				if(p->next->next)
  150. 				{
  151. 					p->next->next->front=p;
  152. 				p->next = p->next->next;
  153. 				}
  154. 				else p->next=p->next->next;
  155. 			}
  156. 			if(p->front->date.flag==FREE&&p->next->date.flag==FREE)
  157. 			{
  158. 				p->front->date.size+=p->date.size+p->next->date.size;
  159. 				if(p->next->next)
  160. 				{
  161. 				p->next->next->front=p->front;
  162. 				p->front->next=p->next->next;
  163. 				}
  164. 				else p->front->next=p->next->next;
  165. 			}
  166. 			if(p->front->date.flag!=FREE&&p->next->date.flag!=FREE)
  167. 			{//
  168. 				
  169. 			}
  170. 			break;
  171. 		}
  172. 		p=p->next;
  173. 	}
  174. 	cout<<"回收成功！"<<endl;
  175. 	return 1;
  176. }
  177.  
  178.  
  179.  
  180. void show()
  181. {
  182. 	cout<< endl;
  183. 	cout<<"作业分配情况"<<endl;
  184. 	int i = 1;
  185. 	Free_Node *p=block_first->next;
  186. 	cout<<"分区号"  << "  作业号" << "\t起始地址"  << "    作业大小"  << "   分区状态" << endl;
  187. 	
  188. 	while(p)
  189. 	{
  190. 		cout << i++ << "\t " << p->date.ID << '\t' << p->date.address << "\t\t" << p->date.size << '\t';
  191. 		if (p->date.flag==FREE)
  192. 			cout<<"空闲"<<endl;
  193. 		else
  194. 			cout<<"已分配"<<endl;
  195. 		p=p->next;
  196. 	}
  197. 	
  198. }
  199.  
  200. void menu()//菜单
  201. {
  202. 	int tag=0;
  203. 	int ID;
  204. 	init();
  205. 	cout<<"分区模拟："<<endl;
  206. 	while(tag!=4)
  207. 	{
  208. 		cout<<"请输入要进行的操作："<<endl;
  209. 		cout<<"1-申请作业，2-作业回收，3-显示作业状况，4-退出"<<endl;
  210. 			cin>>tag;
  211. 		switch(tag)
  212. 			{
  213. 			case 1:
  214. 				alloc(tag);
  215. 				break;
  216. 			case 2:
  217. 				cout<<"请输入需要回收的ID号："<<endl;
  218. 				cin>>ID;
  219. 				free(ID);
  220. 				break;
  221. 			case 3:
  222. 				show();
  223. 				break;
  224. 		    }
  225. 	}
  226.  
  227. }
  228. int main()
  229. {
  230. 	menu();
  231. }

3、最坏适应算法

概念：空闲分区链必须按照容量递减的次序进行排序；若不满足容量递减的次序，则重新进行排序。每次选符合条件的最大的空闲区进行分配。

  1. #include <iostream>
  2. #include <stdlib.h>
  3. using namespace std;
  4.  
  5. #define FREE 0
  6. #define  BUSY 1
  7. #define  MAX_length 300
  8.  
  9. typedef struct freeArea
  10. {
  11. 	int flag;
  12. 	int size;
  13. 	int ID;
  14. 	int address;
  15. }Elemtype;
  16.  
  17. typedef struct Free_Node
  18. {
  19. 	Elemtype date;
  20. 	struct Free_Node *front;
  21. 	struct Free_Node *next;
  22. }Free_Node,*FNodeList;
  23.  
  24. FNodeList block_first;
  25. FNodeList block_last;
  26. int alloc(int tag);//内存分配
  27. int free(int ID);//内存回收
  28. int worst_fit(int ID,int size);//最坏适应算法 
  29. void show();//查看分配
  30. void init();//初始化
  31. void menu();
  32.  
  33. //初始化 
  34. void init()
  35. {
  36. 	block_first=new Free_Node;
  37. 	block_last = new Free_Node;
  38. 	block_first->front=NULL;
  39. 	block_first->next=block_last;
  40. 	block_last->front=block_first;
  41. 	block_last->next=NULL;
  42. 	block_last->date.address=0;
  43. 	block_last->date.flag=FREE;
  44. 	block_last->date.ID=FREE;
  45. 	block_last->date.size=MAX_length;
  46. }
  47.  
  48. //实现内存分配
  49. int alloc(int tag)
  50. {
  51. 	int ID,size1;
  52. 	cout<<"请输入作业号：";
  53. 	cin>>ID;
  54. 	cout<<"请输入所需内存大小：";
  55. 	cin>>size1;
  56. 	if (ID<=0 || size1<=0)
  57. 	{
  58. 		cout<<"ERROR,请输入正确的ID和请求大小"<<endl;
  59. 		return 0;
  60. 	}
  61. 	
  62. 	if (tag==1)//采用最坏适应算法
  63. 	{
  64. 		if (worst_fit(ID,size1))
  65. 		{
  66. 			cout<<"分配成功！"<<endl;
  67. 		}
  68. 		else cout<<"分配失败！"<<endl;
  69. 		return 1;
  70. 	}
  71. 	
  72. }
  73.  
  74. //最坏适应算法
  75. int worst_fit(int ID, int size) {
  76.     int max_surplus = -1;  // 记录最大的差值
  77.     Free_Node *worst_fit_node = NULL;  // 记录最坏适应位置
  78.     Free_Node *p = block_first->next;
  79.  
  80.     // 寻找第一个可用空闲区间，并将其作为最坏适应位置
  81.     while (p) {
  82.         if (p->date.flag == FREE && p->date.size >= size) {
  83.             worst_fit_node = p;
  84.             max_surplus = p->date.size - size;
  85.             break;
  86.         }
  87.         p = p->next;
  88.     }
  89.  
  90.     // 继续遍历链表，寻找更坏适应的位置
  91.     while (p) {
  92.         if (p->date.flag == FREE) {
  93.             int surplus = p->date.size - size;
  94.             if (surplus > max_surplus) {  // 更新最坏适应位置
  95.                 worst_fit_node = p;
  96.                 max_surplus = surplus;
  97.             }
  98.         }
  99.         p = p->next;
  100.     }
  101.  
  102.     if (worst_fit_node == NULL) {
  103.         return 0;  // 如果没有找到合适的位置
  104.     } else {
  105.         // 分配内存并更新链表
  106.         FNodeList temp = (FNodeList) malloc(sizeof(Free_Node));
  107.         temp->date.ID = ID;
  108.         temp->date.size = size;
  109.         temp->date.flag = BUSY;
  110.  
  111.         temp->next = worst_fit_node;
  112.         temp->front = worst_fit_node->front;
  113.         temp->date.address = worst_fit_node->date.address;
  114.  
  115.         worst_fit_node->front->next = temp;
  116.         worst_fit_node->front = temp;
  117.  
  118.         worst_fit_node->date.size = max_surplus;
  119.         worst_fit_node->date.address += size;
  120.  
  121.         return 1;
  122.     }
  123. }
  124.  
  125. int free(int ID)//主存回收
  126. {
  127. 	Free_Node *p=block_first->next;
  128. 	while(p)
  129. 	{
  130. 		if (p->date.ID==ID)//找到要回收的ID区域
  131. 		{
  132. 			p->date.flag=FREE;
  133. 			p->date.ID=FREE;
  134. 			//判断P与前后区域关系
  135. 			if (p->front->date.flag==FREE&&p->next->date.flag!=FREE)
  136. 			{
  137. 				p->front->date.size+=p->date.size;
  138. 				p->front->next=p->next;
  139. 				p->next->front=p->front;
  140. 			}
  141. 			if (p->front->date.flag!=FREE&&p->next->date.flag==FREE)
  142. 			{
  143. 				p->date.size+=p->next->date.size;
  144. 				if(p->next->next)
  145. 				{
  146. 					p->next->next->front=p;
  147. 				p->next = p->next->next;
  148. 				}
  149. 				else p->next=p->next->next;
  150. 			}
  151. 			if(p->front->date.flag==FREE&&p->next->date.flag==FREE)
  152. 			{
  153. 				p->front->date.size+=p->date.size+p->next->date.size;
  154. 				if(p->next->next)
  155. 				{
  156. 				p->next->next->front=p->front;
  157. 				p->front->next=p->next->next;
  158. 				}
  159. 				else p->front->next=p->next->next;
  160. 			}
  161. 			if(p->front->date.flag!=FREE&&p->next->date.flag!=FREE)
  162. 			{//
  163. 				
  164. 			}
  165. 			break;
  166. 		}
  167. 		p=p->next;
  168. 	}
  169. 	cout<<"回收成功！"<<endl;
  170. 	return 1;
  171. }
  172.  
  173.  
  174. void show()
  175. {
  176. 	cout<< endl;
  177. 	cout<<"作业分配情况"<<endl;
  178. 	int i = 1;
  179. 	Free_Node *p=block_first->next;
  180. 	cout<<"分区号"  << "  作业号" << "\t起始地址"  << "    作业大小"  << "   分区状态" << endl;
  181. 	
  182. 	while(p)
  183. 	{
  184. 		cout << i++ << "\t " << p->date.ID << '\t' << p->date.address << "\t\t" << p->date.size << '\t';
  185. 		if (p->date.flag==FREE)
  186. 			cout<<"空闲"<<endl;
  187. 		else
  188. 			cout<<"已分配"<<endl;
  189. 		p=p->next;
  190. 	}
  191. 	
  192. }
  193.  
  194. void menu()//菜单
  195. {
  196. 	int tag=0;
  197. 	int ID;
  198. 	init();
  199. 	cout<<"分区模拟："<<endl;
  200. 	while(tag!=4)
  201. 	{
  202. 		cout<<"请输入要进行的操作："<<endl;
  203. 		cout<<"1-申请作业，2-作业回收，3-显示作业状况，4-退出"<<endl;
  204. 			cin>>tag;
  205. 		switch(tag)
  206. 			{
  207. 			case 1:
  208. 				alloc(tag);
  209. 				break;
  210. 			case 2:
  211. 				cout<<"请输入需要回收的ID号："<<endl;
  212. 				cin>>ID;
  213. 				free(ID);
  214. 				break;
  215. 			case 3:
  216. 				show();
  217. 				break;
  218. 		    }
  219. 	}
  220.  
  221. }
  222.  
  223. int main()
  224. {
  225. 	menu();
  226. }
本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号