操作系统之实验四主存空间的分配和回收

实验四主存空间的分配和回收

专业：商业软件工程班级：商软2班姓名：甘佳萍学号：201406114207

一. 目的和要求

1.1. 实验目的

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

1.2. 实验要求

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

（1）**设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行。

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

（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。

把空闲区说明表的变化情况以及各作业的申请、释放情况显示。

二. 实验内容

第一步：

完成程序数据结构的创建，初始化内存分配情况，创建空闲分区表和已分配分区表。

第二步：

完成为某作业分配内存空间。

用户输入作业名称；
判断作业名称是否已经存在，如果存在则要求用户重新输入；
用户输入作业所占空间大小；
判断是否能够在剩余的空闲区域中找到一块放置该作业，如果不行则要求用户重新输入；
显示菜单，由用户选择使用哪一种分配算法：

1) 首次适应算法

2) 循环首次适应算法

3) 最佳适应算法

4) 最坏适应算法

6.为该作业分配内存空间，分配处理流程图如下（size的值设定为1K）

7.屏幕显示分配后的内存分区情况。

第三步：

完成内存空间回收；

由用户输入作业的ID，决定所要终止的作业；
判断是否存在用户所输入的ID，如果存在则进行终止，否则提示作业不存在；
判断即将终止的作业前后是否有空闲区域，如果没有则作业所占的空间独立成为一个空闲块，在未分配区表中增加一项；

（思考：如何判断前后是否有空闲块？）

4.即将终止作业所占空间前后有空闲块的情况：（X代表即将被终止的作业，黑色代表内存中的空闲块）

所以，判断某个即将被终止的作业所占空间前面是否有空闲块的方法是：作业空间的起始地址A.begin是否等于某个空闲块的结束地址B.end，若相等，则前面有空闲块，则需要合并；若不相等则再判断后面是否有空闲块。

回答：如何判断？

5.进行四种情况的判断，然后分别做出相应的区块回收操作。

回答：如何处理回收？

6.显示回收后的内存使用情况。

根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。

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

1. 源程序名：压缩包文件（rar或zip）中源程序名OS.c

可执行程序名：OS.exe

2. 原理分析及流程图

主要总体设计问题。

(包括存储结构，主要算法，关键函数的实现等)

存储结构：

typedef struct free_table//定义一个空闲区说明表结构  
{     
int num; //分区序号    
long begin; //起始地址    
long size;   //分区大小    
int status;   //分区状态 
}ElemType;

typedef struct Node// 线性表的双向链表存储结构 
{    
    ElemType data;     
struct Node *prior; //前趋指针   
struct Node *next;  //后继指针 
}Node,*LinkList;    

LinkList first; //头结点 
LinkList end;  //尾结点  
int flag;//记录要删除的分区序号   

Status Initblock()//开创带头结点的内存空间链表 
{     
    first=(LinkList)malloc(sizeof(Node));   
    end=(LinkList)malloc(sizeof(Node));   
    first->prior=NULL;   
    first->next=end;   
    end->prior=first;
    end->next=NULL; 
     end->data.num=1;   
     end->data.begin=40;   
     end->data.size=600;   
     end->data.status=0;  
return SIZE; 
}

主要算法：

操作系统之实验四主存空间的分配和回收

关键函数：

Status allocation(int a)
Status Best_fit(int request) 
Status deal1(Node *p)
Status deal2(Node *p) 
Status First_fit(int request) 
Status Initblock()
Status recovery(int flag)
void show()
void sort()
Status Worst_fit(int request)

3. 主要程序段及其解释：

实现主要功能的程序段，重要的是程序的注释解释。

源程序:

#include<stdio.h>  
#include<conio.h>
#include<string.h>
#include<stdlib.h> 

#define SIZE 1
#define ERROR 0 //出错   
typedef int Status; 

typedef struct free_table//定义一个空闲区说明表结构  
{     
int num; //分区序号    
long begin; //起始地址    
long size;   //分区大小    
int status;   //分区状态 
}ElemType;

typedef struct Node// 线性表的双向链表存储结构 
{    
    ElemType data;     
struct Node *prior; //前趋指针   
struct Node *next;  //后继指针 
}Node,*LinkList;    

LinkList first; //头结点 
LinkList end;  //尾结点  
int flag;//记录要删除的分区序号   

Status Initblock()//开创带头结点的内存空间链表 
{     
    first=(LinkList)malloc(sizeof(Node));   
    end=(LinkList)malloc(sizeof(Node));   
    first->prior=NULL;   
    first->next=end;   
    end->prior=first;
    end->next=NULL; 
     end->data.num=1;   
     end->data.begin=40;   
     end->data.size=600;   
     end->data.status=0;  
return SIZE; 
}

//菜单
void menu()
{
    printf("\n                 |*************内存分配和回收***********|\n");
    printf("                 |======================================|\n");
    printf("                 |              0.退出                  |\n");
    printf("                 |              1.首次适应算法          |\n");
    printf("                 |              2.最佳适应算法          |\n");
    printf("                 |              3.最坏适应算法          |\n");
    printf("                 |======================================|\n");
}

void sort()//分区序号重新排序 
{    
    Node *p=first->next,*q;   
    q=p->next;    
for(;p!=NULL;p=p->next)   
    {     
for(q=p->next;q;q=q->next)    
        {       
if(p->data.num>=q->data.num)       
            {          
                q->data.num+=1;        
            }    
        }     
    } 
 } 

//显示主存分配情况 
void show()  
{  
int flag=0;//用来记录分区序号    
    Node *p=first;     
    p->data.num=0;     
    p->data.begin=0;     
    p->data.size=40;     
    p->data.status=1;     
    sort();      
    printf("\n\t\t》主存空间分配情况《\n");      
    printf("**********************************************************\n\n");     
    printf("分区序号\t起始地址\t分区大小\t分区状态\n\n");     
while(p)     
    {        
        printf("%d\t\t%d\t\t%d",p->data.num,p->data.begin,p->data.size);         
if(p->data.status==0) printf("\t\t空闲\n\n");         
else printf("\t\t已分配\n\n"); 
          p=p->next;      
    }      
    printf("**********************************************************\n\n"); 
}

//首次适应算法  
Status First_fit(int request) 
{   
//为申请作业开辟新空间且初始化    
    Node *p=first->next;    
    LinkList temp=(LinkList)malloc(sizeof(Node));    
    temp->data.size=request;   
    temp->data.status=1;   
    p->data.num=1;   
while(p)   
    {     
if((p->data.status==0)&&(p->data.size==request))     
        {
//有大小恰好合适的空闲块       
            p->data.status=1;       
return SIZE;        
break;  
             }     
else if((p->data.status==0) && (p->data.size>request))     
        {
//有空闲块能满足需求且有剩余        
            temp->prior=p->prior;        
            temp->next=p;         
            temp->data.begin=p->data.begin;        
            temp->data.num=p->data.num;        
            p->prior->next=temp;         
            p->prior=temp;         
            p->data.begin=temp->data.begin+temp->data.size;        
            p->data.size-=request;        
            p->data.num+=1;        
return SIZE;        
break;     
        }     
        p=p->next;  
    }
return ERROR; 
}   

//最佳适应算法  
Status Best_fit(int request) 
{    
int ch; //记录最小剩余空间    
    Node *p=first;     
    Node *q=NULL; //记录最佳插入位置     
    LinkList temp=(LinkList)malloc(sizeof(Node)); 
     temp->data.size=request;    
     temp->data.status=1;     
     p->data.num=1;     
while(p) //初始化最小空间和最佳位置    
     {      
if((p->data.status==0) && (p->data.size>=request) )      
         {          
if(q==NULL)             
             {              
                 q=p;               
                 ch=p->data.size-request;             
         }          
else if(q->data.size > p->data.size)          
             {           
                 q=p;            
                 ch=p->data.size-request;          
             }      
         } 
          p=p->next;   
     }    
if(q==NULL) return ERROR;//没有找到空闲块   
else if(q->data.size==request)   
     {         
         q->data.status=1;         
return SIZE;     
     }  
else   
     {       
         temp->prior=q->prior;      
         temp->next=q;       
         temp->data.begin=q->data.begin;      
         temp->data.num=q->data.num;      
         q->prior->next=temp;      
         q->prior=temp;        
         q->data.begin+=request;      
         q->data.size=ch;      
         q->data.num+=1; 
return SIZE;   
     }   
return SIZE; 
}   

//最差适应算法  
Status Worst_fit(int request) 
{      
int ch; //记录最大剩余空间     
    Node *p=first->next;      
    Node *q=NULL; //记录最佳插入位置      
    LinkList temp=(LinkList)malloc(sizeof(Node));      
    temp->data.size=request;     
    temp->data.status=1;     
    p->data.num=1;      
while(p) //初始化最大空间和最佳位置      
    {          
if(p->data.status==0 && (p->data.size>=request) )          
        {             
if(q==NULL)            
            {                  
                q=p; 
                ch=p->data.size-request;             
            }             
else if(q->data.size < p->data.size)            
            {             
                q=p;              
                ch=p->data.size-request;            
            }          
        }          
        p=p->next;      
    }      
if(q==NULL) return ERROR;//没有找到空闲块     
else if(q->data.size==request)      
    {         
        q->data.size=1;        
return SIZE;      
    }     
else      
    {
        temp->prior=q->prior;       
        temp->next=q;        
        temp->data.begin=q->data.begin;       
        temp->data.num=q->data.num;       
        q->prior->next=temp;       
        q->prior=temp;         
        q->data.begin+=request;       
        q->data.size=ch;       
        q->data.num+=1;       
return SIZE; 
        }      
return SIZE; 
}   

//分配主存  
Status allocation(int a) 
{    
int request;//申请内存大小    
    printf("请输入申请分配的主存大小(单位:KB):");    
    scanf("%d",&request);   
if(request<0 ||request==0)      
    {        
        printf("分配大小不合适，请重试！");       
return ERROR;     
    }    
switch(a)   
    {      
case 1: //默认首次适应算法 
if(First_fit(request)==SIZE) printf("\t****分配成功！****");             
else printf("\t****内存不足，分配失败！****");             
return SIZE;    
break;      
case 2: //选择最佳适应算法              
if(Best_fit(request)==SIZE) printf("\t****分配成功！****");             
else printf("\t****内存不足，分配失败！****");             
return SIZE;             
break;  
case 3: //选择最差适应算法              
if(Worst_fit(request)==SIZE) printf("\t****分配成功！****");             
else printf("\t****内存不足，分配失败！****");             
return SIZE;    
break;   
    } 
}

Status deal1(Node *p)//处理回收空间 
{     
    Node *q=first;     
for(;q!=NULL;q=q->next)    
    {       
if(q==p)      
        {      
if(q->prior->data.status==0&&q->next->data.status!=0)     
            {
                q->prior->data.size+=q->data.size;         
                q->prior->next=q->next;         
                q->next->prior=q->prior;         
                q=q->prior;         
                q->data.status=0;          
                q->data.num=flag-1;       
            }        
if(q->prior->data.status!=0&&q->next->data.status==0)       
            {         
                q->data.size+=q->next->data.size;     
                q->next=q->next->next;         
                q->next->next->prior=q;        
                q->data.status=0;         
                q->data.num=flag;      
            }        
if(q->prior->data.status==0&&q->next->data.status==0)      
            {    
                q->prior->data.size+=q->data.size;         
                q->prior->next=q->next;         
                q->next->prior=q->prior; 
                q=q->prior;         
                q->data.status=0;          
                q->data.num=flag-1;      
            }         
if(q->prior->data.status!=0&&q->next->data.status!=0)       
            {    
                q->data.status=0;      
            }      
        }    
    }     
return SIZE; 
}   

Status deal2(Node *p)//处理回收空间 
{     
    Node *q=first;
for(;q!=NULL;q=q->next)    
    {       
if(q==p)      
        {      
if(q->prior->data.status==0&&q->next->data.status!=0)     
            {    
                q->prior->data.size+=q->data.size;         
                q->prior->next=q->next; 
                 q->next->prior=q->prior;         
                 q=p->prior;         
                 q->data.status=0;          
                 q->data.num=flag-1;       
}        
if(q->prior->data.status!=0&&q->next->data.status==0)       
            {         
                q->data.status=0;     
}        
if(q->prior->data.status==0&&q->next->data.status==0)      
            {    
                q->prior->data.size+=q->data.size;         
                q->prior->next=q->next;         
                q->next->prior=q->prior;         
                q=q->prior;         
                q->data.status=0;          
                q->data.num=flag-1;      
            }
if(q->prior->data.status!=0&&q->next->data.status!=0)       
             {    
                 q->data.status=0;      
             }      
        }    
    }     
return SIZE; 
}   

//主存回收  
Status recovery(int flag) 
{     
    Node *p=first;    
for(;p!=NULL;p=p->next)     
    {      
if(p->data.num==flag)     
        {     
if(p->prior==first)
                {      
if(p->next!=end)//当前P指向的下一个不是最后一个时       
                {        
if(p->next->data.status==0)      //与后面的空闲块相连         
                    {                  
                        p->data.size+=p->next->data.size;                 
                        p->next->next->prior=p;                 
                        p->next=p->next->next; 
                         p->data.status=0;                 
                         p->data.num=flag;         
                    }        
else p->data.status=0;       
                }      
if(p->next==end)//当前P指向的下一个是最后一个时       
                {               
                    p->data.status=0;         
                }    
            }
//结束if(p->prior==block_first)的情况    
else if(p->prior!=first)    
            {      
if(p->next!=end)      
                {        
                    deal1(p);       
                }      
else
                    {       
                    deal2(p);      
            }    
            }//结束if(p->prior!=block_first)的情况   
        }//结束if(p->data.num==flag)的情况   
}    
    printf("\t****回收成功****");    
return SIZE;    
}  

void main() 
{      
int i;  //操作选择标记     
int a;//算法选择标记      

while(1)
    {
     menu();
      printf("请选择输入所使用的内存分配算法 (0~3):");  
            scanf("%d",&a);   
while(a<0||a>3)     
     {        
         printf("\n输入错误，请重新选择输入所使用的内存分配算法 (0~3):");       
         scanf("%d",&a);      
     }
switch(a)  
          {    
case 1:printf("\n\t****使用首次适应算法：****\n");
break;       
case 2:printf("\n\t****使用最佳适应算法：****\n");
break;       
case 3:printf("\n\t****使用最坏适应算法：****\n");
break;  
case 0:printf("\n\t****退出内存分配与回收****\n");
return;  
          } 
          Initblock(); //开创空间表     
while(1)      
          {           
              show();          
              printf("\t1: 分配内存\t2: 回收内存\t0: 退出当前内存分配算法\n");         
              printf("请输入您的操作：");         
              scanf("%d",&i);         
if(i==1)            
                  allocation(a); // 分配内存         
else if(i==2)  // 内存回收         
              {              
                  printf("请输入您要释放的分区号：");             
                  scanf("%d",&flag);             
                  recovery(flag); 
                  }          
else if(i==0)    
              {    
                  printf("\n退出当前内存分配算法，返回主菜单\n");    
break; //退出   
              }          
else //输入操作有误         
              {              
                  printf("输入有误，请重新输入！");            
continue;         
              }     
          } 
     }
}

4. 运行结果及分析

一般必须配运行结果截图，结果是否符合预期及其分析。

（截图需根据实际，截取有代表性的测试例子）

运行结果：

操作系统之实验四主存空间的分配和回收

四、实验总结

总之，编写主存空间的分配和回收的过程有（如解决实际问题）。从解决实际问题的角度，我们可以这样来看：首先要了解这个问题的基本要求，即输入、输出、完成从输入到输出的要求是什么；其次，从问题的要害入手，从前到后的解决问题的每个方面，即从输入开始入手，着重考虑如何从输入导出输出。在这个过程中，可确定所需的变量、数组、函数，然后确定处理的过程－－算法。可得出最后的结论，进而完成程序的编写。经过这次实验，我对主存空间的分配和回收有了深一步的了解，同时也初步了解了内存空间的工作原理。总的来说这个实验不是很难，还有这个实验很有趣。

秒客网

操作系统之实验四主存空间的分配和回收

一. 目的和要求

二. 实验内容

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

四、实验总结

相关文章

操作系统之实验四主存空间的分配和回收

一. 目的和要求

二. 实验内容

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

四、 实验总结

相关文章

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

四、实验总结