一、实验目的

    为了合理地分配和使用这些存储空间，当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间和使用情况，找出足够的空闲区域给申请者。当作业撤离归还主存资源时，则存储管理要收回占用的主存空间。主存的分配和回收的实现是与主存储器的管理方式有关的，通过本实验帮助我们理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。

    用高级语言完成一个主存空间的分配和回收模拟程序，以加深对内存分配方式及其算法的理解。

二、 实验内容

2.1  模拟包括3部分：

1）实现特定的内存分配算法

2）实现内存回收模拟

3）每种内存分配策略对应的碎片数统计

2.2  固定分区存储管理

假设内存容量为120KB，并且分别划分成8,16,32,64KB大小的块各一块。

一个进程所需要的内存为0到100个KB。同时假设一个进程在运行过程中所需内存的大小不变。

模拟五个进程到达请求分配与运行完回收情况,输出主存分配表.

2.3  动态分区分配存储管理

采用连续分配方式之动态分区分配存储管理，使用首次适应算法、下次适应算法、最佳适应算法和最坏适应算法4种算法完成设计(任选两种算法)。

（1）在程序运行过程，由用户指定申请与释放。

（2）设计一个已占用分区表，以保存某时刻主存空间占用情况。

（3）设计一个空闲分区表，以保存某时刻主存空间剩余情况。

（4）用两个表的变化情况,反应各进程所需内存的申请与释放情况。

三、实验方法、步骤及结果测试

1 #include
     
          2 #include
      
           3 #define Free 0 //空闲状态    4 #define Busy 1 //已用状态    5 #define OK 1    //完成    6 #define ERROR 0 //出错    7 #define MAX_length 32767 //最大内存空间为32767KB    8 typedef int Status;    9 int n=0;    10 typedef struct freearea//定义一个空闲区说明表结构   11 {   12     int ID;   //分区号   13     long size;   //分区大小   14     long address; //分区地址   15     int state;   //状态   16 }ElemType;   17    18 //---------- 线性表的双向链表存储结构 ------------   19 typedef struct DuLNode //double linked list   20 {   21     ElemType data;    22     struct DuLNode *prior; //前趋指针   23     struct DuLNode *next; //后继指针   24 }DuLNode,*DuLinkList;   25    26 DuLinkList block_first; //头结点   27 DuLinkList block_last; //尾结点   28    29 Status alloc(int);//内存分配   30 Status free(int); //内存回收   31 Status First_fit(int,int);//首次适应算法   32 Status Best_fit(int,int); //最佳适应算法   33 void show();//查看分配   34 Status Initblock();//开创空间表   35    36 Status Initblock()//开创带头结点的内存空间链表   37 {   38     block_first=(DuLinkList)malloc(sizeof(DuLNode));   39     block_last=(DuLinkList)malloc(sizeof(DuLNode));   40     block_first->prior=NULL;   41     block_first->next=block_last;   42     block_last->prior=block_first;   43     block_last->next=NULL;   44     block_last->data.address=0;   45     block_last->data.size=MAX_length;   46     block_last->data.ID=0;   47     block_last->data.state=Free;   48     return OK;   49 }   50    51 //----------------------- 分 配 主 存 -------------------------   52 Status alloc(int ch)   53 {   54     int ID,request;   55     cout<<"请输入作业(分区号)：";    56     cin>>ID;   57     cout<<"请输入需要分配的主存大小(单位:KB)：";    58     cin>>request;   59     if(request<0 ||request==0)    60     {   61         cout<<"分配大小不合适，请重试!"<
       
        data.ID=ID;    84     temp->data.size=request;   85     temp->data.state=Busy;         86     DuLNode *p=block_first->next;   87     while(p)   88     {   89         if(p->data.state==Free && p->data.size==request)   90         {
   //有大小恰好合适的空闲块   91             p->data.state=Busy;   92             p->data.ID=ID;   93             return OK;   94             break;   95         }   96         if(p->data.state==Free && p->data.size>request)   97         {
   //有空闲块能满足需求且有剩余"   98             temp->prior=p->prior;   99             temp->next=p;        100             temp->data.address=p->data.address;  101             p->prior->next=temp;   102             p->prior=temp;  103             p->data.address=temp->data.address+temp->data.size;  104             p->data.size-=request;  105             return OK;  106             break;  107         }  108         p=p->next;  109     }  110     return ERROR;  111 }   112 //-------------------- 最佳适应算法 ------------------------ 113 Status Best_fit(int ID,int request)   114 {   115     int ch; //记录最小剩余空间  116     DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));   117     temp->data.ID=ID;   118     temp->data.size=request;  119     temp->data.state=Busy;  120     DuLNode *p=block_first->next;  121     DuLNode *q=NULL; //记录最佳插入位置  122     while(p) //初始化最小空间和最佳位置  123     {   124         if(p->data.state==Free &&  (p->data.size>request || p->data.size==request) )  125         {  126             q=p;  127             ch=p->data.size-request;  128             break;  129         }  130         p=p->next;    131     }   132     while(p)  133     {    134          if(p->data.state==Free && p->data.size==request)  135         {
   //空闲块大小恰好合适  136             p->data.ID=ID;  137             p->data.state=Busy;  138             return OK;  139             break;  140         }   141         if(p->data.state==Free && p->data.size>request)  142         {
   //空闲块大于分配需求  143             if(p->data.size-request
        
         data.size-request;//更新剩余最小值  146                  q=p;//更新最佳位置指向  147             }  148         }   149         p=p->next;   150     }    151     if(q==NULL) return ERROR;//没有找到空闲块   152     else 153     {
   //找到了最佳位置并实现分配 154         temp->prior=q->prior;   155         temp->next=q;   156         temp->data.address=q->data.address;  157         q->prior->next=temp;  158         q->prior=temp;  159         q->data.address+=request;  160         q->data.size=ch;  161         return OK; 162     }  163 }  164 //-----------------------   主 存 回 收   --------------------  165 Status free(int ID)  166 {   167     DuLNode *p=block_first;   168     while(p)   169     {   170         if(p->data.ID==ID)  171         {  172             p->data.state=Free;  173             p->data.ID=Free;  174             if(p->prior->data.state==Free)//与前面的空闲块相连  175             {  176                 p->prior->data.size+=p->data.size; 177                 p->prior->next=p->next;  178                 p->next->prior=p->prior;  179             }  180             if(p->next->data.state==Free)//与后面的空闲块相连  181             {  182                 p->data.size+=p->next->data.size;  183                 p->next->next->prior=p;  184                 p->next=p->next->next;      185             }  186             break;   187         }  188         p=p->next;  189     }    190     return OK;  191 }   192 //--------------- 显示主存分配情况 ------------------  193 void show()    194 {    195     cout<<"***********-----------------************\n";   196     cout<<"****       主 存 分 配 情 况        ****\n";   197     cout<<"***********-----------------************\n";    198     DuLNode *p=block_first->next;   199     while(p)    200     {  201         cout<<"分 区 号：";  202         if(p->data.ID==Free) cout<<"Free"<
         
          data.ID<
          
           data.address<
           
            data.size<<" KB"<
            
             data.state==Free) cout<<"空 闲"<
             
              next; 211 } 212 } 213 //----------------------- 主 函 数--------------------------- 214 void main() 215 { 216 int ch,d=0;//算法选择标记 217 cout<<"1.首次适应算法 2.最佳适应算法 0.退出\n"; 218 cout<<"请选择分配算法："; 219 cin>>ch; 220 if(ch==0||ch==1||ch==2) d++; 221 while(d==0) 222 { 223 cout<<"请选择正确的数字0 ,1 或2"<
              
               >ch; 225 if(ch==0||ch==1||ch==2) d++; 226 } 227 if(ch==0) exit(0); 228 if(n==0) Initblock(); //开创空间表 229 int choice; //操作选择标记 230 while(1) 231 { 232 cout<<"********************************************\n"; 233 cout<<"** 1: 分配内存 2: 回收内存 **\n"; 234 cout<<"** 3: 查看分配 0: 返 回 **\n"; 235 cout<<"********************************************\n"; 236 cout<<"请输入您的操作 ："; 237 cin>>choice; 238 if(choice==1) 239 { 240 alloc(ch); // 分配内存 241 n++; 242 } 243 else if(choice==2) // 内存回收 244 { 245 int ID; 246 cout<<"请输入您要释放的分区号："; 247 cin>>ID; 248 free(ID); 249 n++; 250 } 251 else if(choice==3) 252 { 253 show();//显示主存 254 n++; 255 } 256 else if(choice==0) 257 { 258 main(); //退出 259 n++; 260 } 261 else //输入操作有误 262 { 263 cout<<"输入有误，请重试!\n"<
              
             
            
           
          
         
        
       
      
     

结果：

四、结果分析与总结：

       刚接到题目的时候需要重新去翻阅一下以前的书籍，有时也会遇到许多无法达到理想的结果，后来我去请教了几位同学，慢慢的解决了许多问题，尽管还不是很收悉，可是我相信随着学习的深入，我可以慢慢的掌握更多的知识，问题的解决，经验的积累，会学的越来越好的。