姓名：万大明
学号：201821121058
班级：计算1812

int display_mem_usage(){
    //显示当前内存的使用情况，包括空闲分区的情况和已经分配的情况
    FBT *fbt = free_block;
    AB *ab = allocated_block_head;
    // if(fbt == NULL) return -1;
    printf("e[0;31;1m------------------------------------------------------------------e[0m
");
    //显示空闲区
    printf("e[0;32;1m空闲的内存:e[0m
");
    printf("e[0;33;1m%20s %20se[0m
","     start_addr","       size");
    while(fbt!=NULL){
        if(fbt->size!=0)
            printf("%20d %20d
",fbt->start_addr,fbt->size);
        fbt = fbt->next;
    }

    //显示已分配区
    printf("
");
    printf("e[0;35;1m使用的内存:e[0m
");
    printf("e[0;33;1m%10s %20s %20s %10se[0m
","PID","ProcessName","start_addr","size");
    while(ab != NULL){
        printf("%10d %20s %20d %10d
",ab->pid,ab->process_name,ab->start_addr,ab->size);
        ab = ab->next;
    }
    printf("e[0;31;1m------------------------------------------------------------------e[0m
");
    return 0;
}

2. 记录空闲分区

/*描述每一个空闲块的数据结构*/
typedef struct free_block_type{
    int size;         //空闲块大小
    int start_addr;         //空闲区起始地址
    struct free_block_type *next;       //指向下一个空闲块
}FBT;

//初始化空闲分区链表
FBT *init_free_block(int mem_size){
    FBT *fb;

    fb = (FBT*)malloc(sizeof(FBT));
    if(fb==NULL){
        printf("No mem
");
        return NULL;
    }
    fb->size = mem_size;
    fb->start_addr = DEFAULT_MEM_START;
    fb->next = NULL;
    return fb;
}

    //显示已分配区
    printf("
");
    printf("e[0;35;1m使用的内存:e[0m
");
    printf("e[0;33;1m%10s %20s %20s %10se[0m
","PID","ProcessName","start_addr","size");
    while(ab != NULL){
        printf("%10d %20s %20d %10d
",ab->pid,ab->process_name,ab->start_addr,ab->size);
        ab = ab->next;
    }
    printf("e[0;31;1m------------------------------------------------------------------e[0m
");
    return 0;
}

3. 内存分配算法

使用什么样的内存分配算法，给出算法源代码，并解释。

内存分配：最佳分配、最差分配、首次适配、循环首次适配、快速适配、伙伴系统
虚拟内存分配：分页、分段、段页式（实现虚拟内存分配，加10分，按30分来打分）

//为进程分配内存 
int alloc_process(Prc prc){
    AB *ab;
    int ret;
    ab = (AB*)malloc(sizeof(AB));
    if(!ab) exit(-5);
    /*为ab赋值 */ 
    ab->next=NULL;
    pid++;//记录id 
    strcpy(ab->process_name,prc.process_name);
    ab->pid = pid; 
    ab->size=prc.size+rand()%ALLOC_SIZE;//随机分配内存 

    ret = allocate_mem(ab);        //从空闲分区分配内存，ret==1表示分配成功
    if((ret == 1) && (allocated_block_head == NULL)){
        /*如果此时allocated_block_head尚未赋值，则赋值*/
        allocated_block_head = ab;
        return 1;
    }else if(ret == 1){
        /*分配成功，将该分配块的描述插入已分配链表*/
        ab->next = allocated_block_head;
        allocated_block_head = ab;
        return 2;
    }else if(ret == -1){
        //分配不成功
        printf("e[0;31;1m 内存分配失败！ e[0m
");
        free(ab);
        return -1;
    }
    return 3;
}

void rearrange_FF(){
    /*首次适应算法，空闲区大小按起始地址升序排序*/
    //这里使用冒泡排序方法
    if(free_block == NULL || free_block->next == NULL)
        return;
    FBT *t1,*t2,*head;
    head = free_block;
    for(t1 = head->next;t1;t1 = t1->next){
        for(t2 = head;t2 != t1;t2=t2->next){
            if(t2->start_addr > t2->next->start_addr){
                int tmp = t2->start_addr;
                t2->start_addr = t2->next->start_addr;
                t2->next->start_addr = tmp;

                tmp = t2->size;
                t2->size = t2->next->size;
                t2->next->size = tmp;
            }
        }
    }
}

//按照最坏适应算法给新进程分配内存空间
int allocate_WF(struct allocated_block *ab)
{
    int ret;
    struct free_block_type *wf= free_block;
    if(wf== NULL)
        return -1;
    if(wf->size>= ab->size)
        allocate(NULL,wf,ab);
    else if(current_free_mem_size>= ab->size)
        ret= mem_retrench(ab);
    else
        ret= -2;
    rearrange_WF();
    return ret;
}

//按照最佳适应算法给新进程分配内存空间
int allocate_BF(struct allocated_block *ab)
{
    int ret;
    struct free_block_type *pre= NULL,*bf= free_block;
    if(bf== NULL)
        return -1;
    while(bf!= NULL)
    {
        if(bf->size>= ab->size)
        {
            ret= allocate(pre,bf,ab);
            break;
        }
        pre= bf;
        pre= pre->next;
    }
    if(bf== NULL&&current_free_mem_size> ab->size)
        ret= mem_retrench(ab);
    else
        ret= -2;
    rearrange_BF();
    return ret;
}

4. 内存释放算法

//释放链表节点
int dispose(AB *free_ab){
    /*释放ab数据结构节点*/
    AB *pre,*ab;
    if(free_ab == allocated_block_head){
        //如果要是释放第一个节点
        allocated_block_head = allocated_block_head->next;
        free(free_ab);
        return 1;
    }
    pre = allocated_block_head;
    ab = allocated_block_head->next;
    while(ab!=free_ab){
        pre = ab;
        ab = ab->next;
    }
    pre->next = ab->next;
    free(ab);
    return 2;
}

//更新分区表
int free_mem(AB *ab){
    /* 将ab所表示的已分配区归还，并进行可能的合并 */
    int algorithm = ma_algorithm;
    FBT *fbt,*pre,*work;
    fbt = (FBT*)malloc(sizeof(FBT));
    if(!fbt) return -1;
    fbt->size = ab->size;
    fbt->start_addr = ab->start_addr;

    //插至末尾
    work = free_block;
    if(work == NULL){
        free_block = fbt;
        fbt->next == NULL;
    }else{
        while(work ->next != NULL){
            work = work->next;
        }
        fbt->next = work->next;
        work->next = fbt;
    }
    //按地址重新排布
    rearrange_FF();

    //合并可能分区;即若两空闲分区相连则合并
    pre = free_block;
    while(pre->next){
        work = pre->next;
        if(pre->start_addr + pre->size == work->start_addr ){
            pre->size = pre->size + work->size;
            pre->next = work->next;
            free(work);
            continue;
        }else{
            pre = pre->next;
        }
    }

    //按照当前算法排序
    rearrange(ma_algorithm);
    return 1;
}

5. 运行结果

int main(int argc, char const *argv[]){
    int sel1,sel2; 
    int total=0; //记录分配内存的次数 
    free_block = init_free_block(mem_size);//初始化空闲区
    Prc prc[PROCESS_NUM];//存放要加载的进程
    init_program(prc,PROCESS_NUM);//对这几个程进程进行初始化 
    srand((unsigned)time(NULL));  
    for(int i=0;i<DATA_NUM;++i)
    {
        /*
           sel1=0表示为某进程分配内存空间 
           sel1=1表示为释放某进程占用的内存空间 
        */ 
        sel1=rand()%2;
        int count=0;
        //统计三个进程中有多少个进程已经分配内存 
        for(int j=0;j<PROCESS_NUM;++j){
            if(prc[j].pid!=-1)
                count++;
        }
        //如果全部分配进程或者进程分配到达5次，那么就不能继续分配内存改为释放内存 
        if((count==PROCESS_NUM && sel1==0)||total==5)
            sel1=1;
        //如果全部未分配进程，那么就不能继续释放内存 
        if(count==0 && sel1==1)
            sel1=0;
        if(sel1==0)//为进程分配内存 
        {
            //随机找到一个未分配内存的进程 
            do{
                sel2=rand()%PROCESS_NUM;
            }while(prc[sel2].pid!=-1);
            alloc_process(prc[sel2]);//分配内存空间 
            prc[sel2].pid=pid;//改变标记 
            total++;
            display_mem_usage();//显示 
        }
        else//释放进程占用的内存空间 
        {
            //随机找到一个可释放进程 
            do{
                sel2=rand()%PROCESS_NUM;
            }while(prc[sel2].pid==-1);
            kill_process(prc[sel2].pid);//释放内存空间 
            prc[sel2].pid=-1;//改变标记 
            display_mem_usage();//显示 
        }
    }
}