操作系统-循环首次适应算法

循环首次适应算法介绍

每次为进程分配空间的时候，从上一次刚分配过的空闲区的下一块开始寻找，比如，初始化的内存空闲区是用户输入的max大小，没有进行回收之前之前必定是只有最后一块是空闲的，但是经过回收之后，你设定的表（这里是设定了一张表，也可以用俩张，但是一张就可以解决的没必要俩张），从是空闲区的区号开始分配之后，标记此块,下次分配从标记的这一块开始向下寻找，符合就分配，然后标记分配的空闲区区号，与首次适应算法的区别就在这

代码

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1    //完成
#define ERROR 0 //出错
typedef int Status;
int flag;
/**
 *设置空闲块
 *有三个标识符
 *address起始地址
 *size空闲块大小
 *state空闲块状态
 */
typedef struct freearea
{
    int address;//空闲区地址
    int size;//作业空间大小
    int state;//空闲去状态
}ElemType;
/**
 *设置链表指针
 */
typedef struct DuLNode
{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode, *DuLinkList;
/**
 *block_first
 *链表首地址
 *block_last
 *链表尾地址
 */
DuLinkList block_first;
DuLinkList lastfind;
DuLinkList block_last;
void alloc(int);
void free(int);
Status NF(int);
void show();
void initblock();
/**
 *初始化内存
 *传入用户需设置的内存大小MAX_length
 */
void initblock(int MAX_length)
{
    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_last->data.address=0;
    block_last->data.size=MAX_length;
    block_last->data.state=Free;


}
/**
 *输入进程请求的空闲块大小
 *调用分配空闲块大小的算法NF（response）
 */
void alloc()
{
    int request;
    printf("请您输入进程所需分配的空间大小：");
    scanf("%d",&request);
    if(request<0||request==0)
    {
        printf("输入错误，内存大小不能小于等于0 请重新输入");


    }
    else
    {
        if(NF(request)==OK)
            {
                printf("分配成功！");


            }
        else
            {
                printf("内存不足分配失败！");


            }
    }


}
/**
 *循环首次适应算法
 *lastfind为上次分配空闲的位置，如果是首次分配就不存在lastfind
 *request为用户输入的进程请求空闲块的大小
 *寻找内存中空闲块大于等于请求的空闲块
 *即size>response&&state=Free
 *等于则直接修改该状态
 *大于则分配response大小后把剩余的存为空闲块
 *找到则标记为lastfind
 */
Status NF(int request)
{
    DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));
    temp->data.size=request;
    temp->data.state=Busy;
    if(lastfind)
    {
        while(lastfind)
        {
            if(lastfind->data.state==Free&&lastfind->data.size==request)
            {
                lastfind->data.state=Busy;
                lastfind=lastfind->next;
                return OK;
                break;
            }
            if(lastfind->data.state==Free&&lastfind->data.size>request)
            {
                temp->prior=lastfind->prior;
                temp->next=lastfind;
                temp->data.address=lastfind->data.address;
                lastfind->prior->next=temp;
                lastfind->prior=temp;
                lastfind->data.address=temp->data.address+temp->data.size;
                lastfind->data.size=lastfind->data.size-request;
                lastfind=lastfind->next;
                return OK;
                break;
            }
            lastfind=lastfind->next;
        }
    }
    else
    {
        DuLNode *p = block_first->next;
        while(p)
        {
            if(p->data.state==Free&&p->data.size==request)
            {
                p->data.state=Busy;
                lastfind=p->next;
                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=p->data.size-request;
                lastfind=p->next;
                return OK;
                break;
            }
            p=p->next;
        }
    }
}
/**
 *回收内存算法
 *若回收的区号的左右指针均为空闲块，则三块回收为一块
 *若只有左指针为空闲块，则俩块合并为一块
 *若只有右指针为空闲块，则俩块合并为一块
 *若左右均不是空闲块，则只改变该区号的状态为空闲
 */
void free(int flag)
{
    DuLNode *p = block_first;
    for(int i=0;i<=flag;i++)
    {
        if(p!=NULL)
        {
            p=p->next;
        }
    }
    p->data.state=Free;
    if(p->prior->data.state==Free&&p->next->data.state!=Free)
    {
        p->prior->data.size+=p->data.size;
        p->prior->next=p->next;
        p->next->prior=p->prior;
        p=p->prior;
    }
    if(p->prior->data.state!=Free&&p->next->data.state==Free)
    {
        p->next->data.size+=p->data.size;
        p->next->data.address=p->data.address;
        p->next->prior=p->prior;
        p->prior->next=p->next;
        p=p->next;
    }
    if(p->prior->data.state==Free&&p->next->data.state==Free)
    {
        p->next->data.size+=p->data.size+=p->prior->data.size;
        p->next->data.address=p->prior->data.address;
        p->next->prior=p->prior->prior;
        p->prior->prior->next=p->next;
        p=p->next;
    }


}
/**
 *显示内存分配函数
 *从链表的首指针开始
 *依次显示
 */
void show()
{
    int flag=0;
    printf("主存分配情况：\n");
    DuLNode *q=block_first->next;
    printf("分区号\t起始地址 分区大小\t状态\n\n");
    while(q)
    {
        printf("%d\t",flag);
        flag++;
        printf("%d\t",q->data.address);
        printf("%dKB\t",q->data.size);
        if(q->data.state==Free)
        {
            printf("      空闲\n\n");
        }
        else
        {
            printf("      已分配\n\n");
        }
        q=q->next;
    }
    printf("++++++++++++++++++++++++++++\n");
}
int main()
{
    int c=1;
    int MAX_length;
    printf("**********您现在操作的是循环首次适应分配算法*****************\n");
    printf("***请输入初始空闲片的大小：");
    scanf("%d",&MAX_length);
    initblock(MAX_length);
    int choice;
    while(c==1)
    {
        printf("\n1: 分配内存   2:回收内存  3:退出系统  4:显示内存分配情况\n");
        printf("*******请输入您将进行的操作：");
        scanf("%d",&choice);
        if(choice==1)
        {
            alloc();
            c=1;
        }
        else if(choice==2)
        {
            printf("请输入您想要回收的空闲块区号：");
            scanf("%d",&flag);
            free(flag);
            c=1;
        }
        else if(choice==3)
        {
            exit(1);
        }
        else if(choice==4)
        {
            show();
            c=1;
        }
        else
        {
            printf("操作不存在 请重新输入！");
            c=1;
        }
    }
    return 0;
}