存储管理原理最先适应

原理最先适应"/>

存储管理原理最先适应

一、问题描述

设物理内存320KB，共有10个进程先后申请进入内存，进程详细情况见表1-1。

其中实现动态分区管理的具体要求如下：

1. 设计动态分区存储管理必须的表格，例如分区说明表、可用表或自由链；

2. 内存分配策略包括最先适应、最佳适应、最坏适应三种，程序可实现不同内存策略的切换；

3. 程序能够实现“当一个进程申请使用内存时，能够显示该进程在内存的占用情况及其可用表和分区说明表的变化情况；当一个进程执行完毕释放内存时，能够显示可用表和分区说明表的变化情况”;

                                              表1-1 进程相关信息

• 二、问题分析

• 涉及的知识点

1. 动态分区分配（又称为可变分区分配）：这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
2. 分区说明表：每个分区对应一个表项。表项中包含分区号、分区大小、分区起始地址、状态信息。
3. 空闲分区表：每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址。【注：因为分区说明表涵盖了空闲分区表，且各时段的分区数目不超过两个，为了更好的屏幕展示效果，本实验只打印出分区说明表】
4. 分区双向链表：每个分区起始部分和末尾部分分别设置前向指针和后向指针，各分区节点记录分区大小、起始地址、状态以及进程信息，同时给链表安排一个头结点。
5. 动态分区分配算法：

• 最先适应算法：算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。算法实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。
• 最佳适应算法：算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区。算法实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。
• 最坏适应算法：算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，故在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。算法实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。

6．内存分区的回收（分4种情况）：

• 当“回收区的后面有一个相邻的空闲分区”，则两个相邻的空闲分区合并为一个，并修改后面这个分区的分区大小和起始地址。
• 当“回收区的前面有一个相邻的空闲分区”，则两个相邻的空闲分区合并为一个，并修改前面这个分区的分区大小。
• 当“回收区的前、后各有一个相邻的空闲分区”，则三个相邻的空闲分区合并为一个，并修改前面这个分区的分区大小。
• 当“回收区的前、后都没有相邻的空闲分区”，则将该分区的状态改为“空闲”，并在空闲分区表中增加一个表项。

  •                                         问题的解决思路

因为问题给出了各个进程的达到时间，则按时间点的顺序，依次安排各进程进入内存（若到达时间相同，则规定进程编号小的进程优先占用内存）。设置三种不同的动态分区分配算法，，根据各算法实现方式进行对分区链表进行处理。当选择一种算法之后，在各个进程进入/离开内存的时间点上，打印出当前内存的使用情况，即分区说明表。

                                                        三、实验结果分析

1. 1. 结果展示：

                                                                           图3-1

图3-1为初始菜单选择算法执行页面，用户可通过键入1、2、3、0选择不同的功能。

                            图3-2最先、最佳适应算法（截取第10s的内存分配与回收） 

                                图3-3 最坏适应算法（截取第10s的内存分配与回收） 

在本次内存管理作业中，最佳适应度算法与最先适应度算法的表现结果完全一样，故不再重复截取图片。最后，附上各算法的初始执行状态和最终执行状态，很巧合的是，采用各个算法的内存最终进程执行完毕的时间均相同且初始状态也都相同，故都只截取一张图片表示。

                                图3-4内存初始状态（三种算法执行结果均为此图）

                                图3-5内存最终状态（三种算法执行结果均为此图） 

如图3-5所示，展示完第一种算法之后，用户仍可以键入对应数字来选择下一种算法执行，直至用户按0选择退出，如图3-6所示。

                                                                图3-6退出程序 

1. 1. 结果原因刨析

在此实验中，最佳适应度算法与最坏适应度算法有很大的不同。最佳适应算法：为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区。所以如图3-2、图3-3所示：当进程A释放完内存空间后，此时内存中有两块空闲的内存空间（分区1，大小30KB；分区3，大小247KB）。此时刚好D进程（6KB）来占用内存，最佳适应度算法会分配该进程D进1号分区，因为1号分区在当前所有空闲分区中分区长度最短，此时的空闲分区链如图3-7所示：它会最先找到分区空间大的空闲分区。而最坏适应度算法则会分配该进程D进入4号分区，因为4号分区在当前所有空闲分区中分区长度最长，此时的空闲分区链如图3-8所示：它会最先找到分区空间大的空闲分区。

                     图3-7 最佳适应算法的空闲分区链（截取第10sA进程释放内存）    

                        图3-8 最佳适应算法的空闲分区链（截取第10sA进程释放内存） 

总结如下：最佳适应度算法：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。

最差适应度算法：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。

对最先适应度算法进行如下总结：该算法会将空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区来进行进程分配。

1. 1. 性能分析

首先，从搜索速度上看，最先适应算法具有最佳性能。尽管最佳适应算法或最坏适应算法看上去能很快地找到一个最适合的或最大的空闲区，但后两种算法都要求首先把大小不同的空闲区按其大小进行排队，这实际上是对所有空闲区进行一次搜索。再者，从回收过程来看，最先适应算法也是最佳的。因为使用最先适应算法回收某一空闲区时，无论被释放区是否与空闲区相邻，都不用改变该区在可用表或自由链中的位置，只需修改其大小或起始地址。而最佳适应算法和最坏适应算法都必须重新调整该区的位置。
最先适应算法的另一个优点就是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。

反过来，最佳适应法找到的空闲区是最佳的，也就是说，用最佳适应法找到的空闲区或者是正好等于用户请求的大小或者是能满足用户要求的最小空闲区。不过，尽管最佳适应法能选出最适合用户要求的可用空闲区，但这样做在某些情况下并不一定能提高内存的利用率。例如，当用户请求小于最小空闲区不太多时，分配程序会将其分配后的剩余部分作为一个新的小空闲区留在可用表或自由链中。这种小空闲区有可能永远得不到再利用(除非与别的空闲区合并)，而且也会增加内存分配和回收时的查找负担。
最坏适应算法正是基于不留下碎片空闲区这一出发点的，它选择最大的空闲区来满足用户要求，以期分配后的剩余部分仍能进行再分配。

综上所述：这三种算法各有所长，针对不同的请求队列，效果和功能是不一样的。

源代码详见主页

#include<stdio.h>
#include<stdlib.h>
#include<stdlib.h>
#include <iostream>
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1    //完成
#define ERROR 0 //出错
#define MAX_length 320 //最大内存空间为320KB
#include<iostream>
using namespace std;//各列解释：进程号，所占内存，到达时间，执行时间 
int time[10][4]={{0,0,0,0}, {1,30,0,10},{2,28,5,15},{3,15,6,16},{4,6,10,5},{5,78,10,10},{6,108,16,3},{7,320,18,20},{8,60,22,17},{9,18,22,30}};typedef int Status;
int n = 0;
char process[11]={ ' ','A','B','C','D','E','F','G','H','I'};
typedef struct freearea//定义一个空闲区说明表结构
{int ID;   //分区号 ----hzy修改为进程号 long size;   //分区大小long address; //分区地址int state;   //状态
}ElemType;//---------- 线性表的双向链表存储结构 ------------
typedef struct DuLNode //double linked list
{ElemType data;struct DuLNode* prior; //前趋指针struct DuLNode* next; //后继指针
}DuLNode, * DuLinkList;DuLinkList block_first; //头结点
DuLinkList block_last; //尾结点Status alloc(int);//内存分配
Status free(int); //内存回收
Status First_fit(int, int);//首次适应算法
Status Best_fit(int, int); //最佳适应算法
void show();//查看分配
Status Initblock();//开创空间表Status Initblock()//开创带头结点的内存空间链表
{block_first = (DuLinkList)malloc(sizeof(DuLNode));block_last = (DuLinkList)malloc(sizeof(DuLNode));block_first->prior = NULL;block_first->next = block_last;block_last->prior = block_first;block_last->next = NULL;block_first->data.ID=999;block_first->data.state=999;block_last->data.address = 0;block_last->data.size = MAX_length;block_last->data.ID = 0;block_last->data.state = Free;return OK;
}//------------------ 首次适应算法 -----------------------
Status First_fit(int ID, int request)//传入作业名及申请量， 
{//为申请作业开辟新空间且初始化DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));temp->data.ID = ID;temp->data.size = request;temp->data.state = Busy;DuLNode* p = block_first->next;while (p){if (p->data.state == Free && p->data.size == request){//有大小恰好合适的空闲块p->data.state = Busy;p->data.ID = ID;return OK;break;}if (p->data.state == Free && p->data.size > request){//有空闲块能满足需求且有剩余"temp->prior = p->prior;temp->next = p;temp->data.address = p->data.address;p->prior->next = temp;p->prior = temp;p->data.address = temp->data.address + temp->data.size;p->data.size -= request;return OK;break;}p = p->next;}return ERROR;
}//-------------------- 最佳适应算法 ------------------------Status Best_fit(int ID, int request) //ID表示输入的进程，可理解为进程号 
{int ch; //记录最小剩余空间DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));temp->data.ID = ID;temp->data.size = request;temp->data.state = Busy;DuLNode* p = block_first->next;DuLNode* q = NULL; //记录最佳插入位置while (p) //初始化最小空间和最佳位置{if (p->data.state == Free &&(p->data.size > request || p->data.size == request)){q = p;ch = p->data.size - request;break;}p = p->next;}while (p){if (p->data.state == Free && p->data.size == request){//空闲块大小恰好合适p->data.ID = ID;p->data.state = Busy;return OK;break;}if (p->data.state == Free && p->data.size > request){//空闲块大于分配需求if (p->data.size - request < ch)//剩余空间比初值还小{ch = p->data.size - request;//更新剩余最小值q = p;//更新最佳位置指向}}p = p->next;}if (q == NULL) return ERROR;//没有找到空闲块else{//找到了最佳位置并实现分配temp->prior = q->prior;temp->next = q;temp->data.address = q->data.address;q->prior->next = temp;q->prior = temp;q->data.address += request;q->data.size = ch;return OK;}
}//-------------------- 最坏适应算法 ------------------------
Status worst_fit(int ID, int request){ //ID表示输入的进程，可理解为进程号 int ch; //记录最大剩余空间DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));temp->data.ID = ID;temp->data.size = request;temp->data.state = Busy;DuLNode* p = block_first->next;DuLNode* q = NULL; //记录最佳插入位置while (p) //初始化最大空间和最佳位置{if (p->data.state == Free &&(p->data.size > request || p->data.size == request)){q = p;ch = p->data.size - request;break;}p = p->next;}while (p)  //遍历找到最大空间和最佳位置{if (p->data.state == Free && p->data.size >= request){//空闲块大于分配需求if (p->data.size - request > ch)//剩余空间比初值还小{ch = p->data.size - request;//更新剩余最大值q = p;//更新最佳位置指向}}p = p->next;}if (q == NULL) return ERROR;//没有找到空闲块else{//找到了最佳位置并实现分配temp->prior = q->prior;temp->next = q;temp->data.address = q->data.address;q->prior->next = temp;q->prior = temp;q->data.address += request;q->data.size = ch;return OK;}
}//-----------------------   主 存 回 收   --------------------
Status free(int ID)
{DuLNode* p = block_first->next;while (p){if (p->data.ID == ID){p->data.state = Free;//cout << p->next->data.state << endl;//p->data.ID = Free;if((p->next!=NULL)&&(p->prior->data.state == Free)&&(p->next->data.state == Free))//前面、后面均为空闲块{p->prior->data.size=p->prior->data.size+p->data.size+p->next->data.size;if(p->next->next !=NULL){p->prior->next=p->next->next;p->next->next->prior=p->prior;}elsep->prior->next= NULL;free(p);free(p->next);}else if (p->prior->data.state == Free)//与前面的空闲块相连{p->prior->data.size += p->data.size;p->prior->next = p->next;p->next->prior = p->prior;free(p);}else if ((p->next!=NULL)&&(p->next->data.state == Free))//与后面的空闲块相连{//空闲块的后继指针并不为0p->next->data.size += p->data.size;p->next->prior = p->prior;p->prior->next = p->next;p->next->data.address = p->data.address;free(p);//p->next->next->prior = p;//p->next = p->next->next;}break;}p = p->next;}return OK;
}//----------------------- 分 配 内 存 -------------------------  需要改 
Status alloc(int ch,int ID) //ch表示选择的算法 
{int request;request=time[ID][1];if (request < 0 || request == 0){return ERROR;}if (ch == 2) //选择最佳适应算法{if (Best_fit(ID, request) == OK)return OK; elsereturn ERROR;}else if (ch==3) //选择最坏适应算法{if (worst_fit(ID, request) == OK)return OK; elsereturn ERROR;}else //默认首次适应算法{if (First_fit(ID, request) == OK)return OK; elsereturn ERROR;}
}//--------------- 显示主存分配情况 ------------------  
void show(int time)
{cout << "NOW TIME：";cout << time << endl;cout << "*******************-----------------*********************"<<endl;cout << "************       分 区 说 明 表        *************"<<endl;cout << "*******************-----------------*********************"<<endl;DuLNode* p = block_first->next;int i=1;cout << "分 区 号" << "\t" <<  "起始地址" << "\t"  << "分区大小（KB）" << "\t" << "状    态" << endl;cout << "---------------------------------------------------------" << endl;while (p){cout << i++ << "\t\t" << p->data.address << "\t\t" << p->data.size << "\t\t";if (p->data.state == Free) cout << "空 闲" << endl;else cout << "已分配" << endl;p = p->next;}cout << "---------------------------------------------------------" << endl;
}
//-----------------------菜单--------------------- 
void menu(){cout << "1.最先适应算法 2.最佳适应算法 3.最坏适应算法 0.退出"<<endl;
} 
//----------------------- 主 函 数---------------------------  需要改 
void choice()
{int ch, d = 0;//算法选择标记cout << "请选择分配算法："<<endl;cin >> ch;if (ch == 0 || ch == 1 || ch == 2|| ch == 3) d++;while (d == 0){cout << "请选择正确的数字0 ,1 ,2或3" << endl;cin >> ch;if (ch == 0 || ch == 1 || ch == 2|| ch == 3) d++;}if (ch == 0) exit(0);if (n == 0) Initblock(); //开创空间表int now_time =0;int now_ID=1;while(now_time<80){for(int i=1;i<=9;i++){if(time[i][2]+time[i][3]==now_time){ //进程离开内存，进行更新 free(time[i][0]);     //time【i】【0】为进程号cout << "进程" << process[i] << "释放内存" << "  " ; show(now_time);for(int k=now_ID;k<=9;k++){if(time[k][2]<now_time){time[k][2]=now_time;}}}} while((time[now_ID][2]==now_time)&&alloc(ch,now_ID)){cout << "进程" << process[now_ID] << "("<< time[now_ID][1]<< "KB)" <<  "占用内存" << "  " ; now_ID++;show(now_time);}now_time++;	if(time[now_ID][2]<now_time){time[now_ID][2]=now_time;}}}
int main(){while(1){menu();choice();}return 0;
}