首次适应算法.txt

内存分派算法——首次适应算法及其实验报告设计

操作系统课程设计报告_首次适应算法
一、实验目的：
熟悉首次适应算法，理解分配内存资源及回收资源的方法,加深记意。
二、实验环境：
Win2000/winxp   VC++6.0
三、实验内容：
编程实现初次内存分配算法、新申请资源分配算法、删除进程算法，回收合并算法等。
四．实验函数
程序主要以链表实现，相关函数如下：
1．void Init(memoryspace &L,int size)
初始化空间段，大小可自定。
2．void choice(memoryspace &L)
选择对作业的操作类型，选0退出程序，先1新建作业，输出已经分配和空闲资源情况，选3删除某作业，选4回收资源。
3．void Add(memoryspace &L)
添加的作业。
4．void Display(const memoryspace L)
输出已经分配和空闲结点。
5．void deltask(const memoryspace L)
输出已经分配和空闲资源情况。
6．void setfree(memoryspace &L)
回收空闲空间，若存在连续的空闲结点则合并。
五．实验代码：

 程序代码
#include <iostream.h>
#include <stdlib.h>
typedef struct LNode
{    int size;        //内存大小
    int state;   //0表示空闲，1表示已经装入作业
    char task_name;  //装入的作业名称
    struct LNode *next;
}LNode,*memoryspace;
void Init(memoryspace &L,int size); //初始化空间段
void choice(memoryspace &L);  //选择操作类型
void Add(memoryspace &L); //添加作业
void Display(const memoryspace L); //显示作业
void deltask(const memoryspace L); //删除作业
void setfree(memoryspace &L); //回收空闲空间
void main()
{
    memoryspace L=new LNode; //memoryspace
    int N;
    cout<<"初始多大空间,请输入一个整数:"<<endl;
    cin>>N;
    Init(L,N);    //初始化大小为1000的内存空间
    choice(L);    //进入操作
}
void Init(memoryspace &L,int size) //初始化空间段
{
    memoryspace p = new LNode;
    p->size = size;
    p->state = 0;
    p->task_name = 'n';
    p->next = NULL;
    L->next = p;
}
void setfree(memoryspace &L) //找出连续的空闲资源,回收空闲空间
{
    memoryspace p=L->next,q=p->next;
    while(p && q)
    {
        if(p->state == 0 && q->state == 0) //如果空间连续,则回收
        {
            p->size +=q->size;
            p->next = p->next->next;
            delete q;
            q=p->next;
        }
        else
        {
            p = q;
            q = q->next;
        }
    }
    cout<<"回收成功"<<endl;
}
void deltask(const memoryspace L) //删除作业
{
    char task_name;
    int flag=0;
    Display(L);
    cout<<"请输入需要回收的作业名称:";
    cin>>task_name;

    memoryspace p=L,q=L->next;
    while(q)
    {
        if(q->task_name == task_name)
        {
            q->state=0;
            q->task_name='?';
            flag=1;
            break;
        }
        else
        {
            p = q;
            q = q->next;  //找到要删除作业的下一个结点
        }
    }
    if(flag == 0)
        cout<<"删除作业不成功"<<endl;
    else
        cout<<"删除作业成功"<<endl;
}

void Display(const memoryspace L) //显示作业
{
    int count=1;
    memoryspace p = L->next;
    cout<<"结点号 作业 状态 大小"<<endl;
    while(p)
    {
        cout<<"结点"<<count<<"    "<<p->task_name<<"   ";
        cout<<p->state<<"   "<<p->size<<endl;
        p = p->next;
        count++;
    }
}

void Add(memoryspace &L) //添加作业
{
    int new_size;
    char new_name;
    memoryspace q=L,p = L->next;
    cout<<"请输入新任务的名称:";
    cin>>new_name;
    cout<<"请输入新任务的大小:";
    cin>>new_size;
    
    while(p) //查找空闲资源进行分配
    {
        if (new_size<=0)
        {
            cout<<endl<<"申请的空间不能小于1"<<endl;
            break;
        }
        if(p->state==0 && p->size >= new_size) 
        {   
        //****************************************************//
            memoryspace q = new LNode;
            q->size = p->size - new_size; 
            q->state = 0;
            q->task_name='?';
            q->next=NULL;
        //****************************************************//
            p->size = new_size;
            p->state = 1;
            p->task_name=new_name;
            q->next = p->next;
            p->next = q;
            break;  //分配完成便退出
        }
        else
        {
            p = p->next;  //移动到足够分配的空结点
        }
        if(!p)
        {
            cout<<"作业"<<new_name<<"内存分配不成功"<<endl;
            break;
        }
    }
    p = L->next;
    while(p) //删除大小为0的结点,当分配空间完时会出现0结点
    {
        if(p->size == 0)
        {
            q->next = q->next->next;
            delete p;
            p = q->next;
        }
        else 
        {
            q = p;
            p = p->next;
        }
    }
}
void choice(memoryspace &L)  //选择操作类型
    { 
      int choice;
      do
      {
        cout<<"0.退出本程序"<<endl;
        cout<<"1.添加新的作业"<<endl;
        cout<<"2.显示当前作业"<<endl;        
        cout<<"3.删除一条作业"<<endl;
        cout<<"4.回收空闲空间"<<endl;
        cout<<endl<<"输入你的选择:";
        cin>>choice;
        switch(choice)
        {
        case 0:
            exit(1);break;
        case 1:
            Add(L); break;
        case 2:
            Display(L); break;        
        case 3:
            deltask(L); break;
        case 4:
            setfree(L); break;
        default:
            cout<<"请输入正确的选择!"<<endl;
            break;
        }
        cout<<endl;
      }while(choice!=0 ||choice!=1 || choice !=2 || choice!=3 || choice!=4);
    }
六．实验总结
在一般的操作系统中,进程量都不是很大,于是添加新作业及回收资源的时候都是遍历整个链表对每个结点进行操作,这样也使算法易于实现.通过本次实验,我对操作系统的内存分配方法有了进一步的理解.