操作系统实验（一）——可变分区存储管理

湖南师范大学信息科学与工程学院计算机科学与技术非师范班操作系统实验报告

一、实验目的：

加深对可变分区存储管理的理解；
提高用C语言编制大型系统程序的能力，特别是掌握C语言编程的难点：指针和指针作为函数参数；
掌握用指针实现链表和在链表上的基本操作。

二、实验内容：

参照教材P137-P140的内容，编写一个C程序，用char *malloc（unsigned size）函数向系统申请一次内存空间（如size=1000，单位为字节），用循环首次适应算法、最佳适应算法和最坏适应算法，模拟可变分区存储管理，实现对内存区的分配和回收管理。

三、实验要求：

分配函数addr=（char *）lmalloc（unsigned size）和释放函数lfree（unsigned size，char *addr）的参数size和addr，要以键盘命令的形式输入，每次分配和释放后显示空闲分区表。
空闲分区表可采用结构数组的形式（最低要求）或双向链表的形式。

四、参考测试数据：

操作系统在低地址占用100KB的空间，用户区主存从100KB处开始占用512KB。初始时，用户区全部为空闲，分配时截取空闲分区的低地址部分作为已分配区。执行以下申请、释放操作序列后：请求300KB，请求100KB，释放300KB，请求150KB，请求90KB，释放100KB。

开始写代码！

空闲分区表采用双向链表的形式

struct SubAreaNode{
    int id;
    int addr;
    int size;
    char state;
    SubAreaList pre;
    SubAreaList next;
};

完整代码

#include 
#include 
#include 
#define MEMORY_SIZE 512
#define ALLOCATED 1
#define FREE 0
typedef struct SubAreaNode *SubAreaList;
struct SubAreaNode{
    int addr;
    int size;
    int pid;
    int state;
    SubAreaList pre;
    SubAreaList next;
};
SubAreaList head;
SubAreaList nowList;

SubAreaList getSubArea(){
    return (SubAreaList) malloc(sizeof(struct SubAreaNode));
}
//初始化分区链表
SubAreaList initSubArea(){
    SubAreaList p = getSubArea();//?
    p->addr = 100;//初始地址
    p->size = MEMORY_SIZE;
    p->pid = -1;
    p->state = FREE;
    p->pre = NULL;
    p->next = NULL;
    return p;
}
//分配
int alloc(int pid, int psize, SubAreaList p) {
    if (p == NULL)   //无合适空间可分配
        return 0;
    if (p->size == psize) {   //分区整块分配
        p->state = ALLOCATED;
        p->pid = pid;
    } else {                  //分割分区
        SubAreaList newSubArea = getSubArea();
        newSubArea->addr = p->addr + psize;
        newSubArea->size = p->size - psize;
        newSubArea->state = FREE;
        newSubArea->pid = -1;

        p->size = psize;
        p->state = ALLOCATED;
        p->pid = pid;

        newSubArea->next = p->next;
        p->next = newSubArea;
        newSubArea->pre = p;
    }
    return 1;
} 
//回收
int freeAlloc(int pid){
    SubAreaList p = head;
    while(p){
        if(p->pid == pid) break;
        p = p->next;
    }
    if(p==NULL)
        return 0;
    //不是首块分区且与前一空闲分区相连
    if(p!=head && p->pre->state==FREE && p->pre->addr+p->pre->size==p->addr){
        SubAreaList preNode = p->pre;
        SubAreaList nextNode = p->next;
        preNode->size += p->size;
        preNode->next = p->next;
        nextNode->pre = preNode;
    //与后一空闲分区相邻
        if(p->next->state==FREE && p->pre->addr+p->pre->size==p->next->addr){
            preNode->size += nextNode->size;
            preNode->next = nextNode->next;
            nextNode->next->pre = preNode;//?
            free(nextNode);
        }
        free(p);
    }else{
        //不是最后一个分区且与后一分区相邻
        if(p->next!=NULL && p->next->state==FREE && p->addr+p->size==p->next->addr){
            SubAreaList nextNode = p->next;
            p->size += nextNode->size;
            p->next = nextNode->next;
            nextNode->next->pre = p;
            p->pid = -1;
            p->state = FREE;
            free(nextNode);
        } else {
            p->pid = -1;
            p->state = FREE;
        }
    }
    return 1;
}
void displayAllocTable(){
    SubAreaList p = head;
    printf("n%5s %5s %5s %5sn","起始地址","终止地址","长度","分配状态","ID");

    while (p){
        printf("n%5d %5d %5d %5dn",p->addr,p->addr+p->size,p->size,p->state,p->pid);
        p = p->next;
    }
    printf("n");
}
 
//首次适应算法
SubAreaList ff(int psize){
    SubAreaList p = head;
    while(p){
        if(p->size>=psize && p->state==FREE) return p;
        p = p->next;
    }
    return NULL;
}
int ffAlloc(int pid,int psize){
    return alloc(pid,psize, ff(psize));
}
//循环首次适应
SubAreaList nfFindFreeSubArea(int psize) {
    SubAreaList tmp = nowList;
    while (nowList) {
        if (nowList->state == FREE && nowList->size >= psize)  return nowList;
        nowList = nowList->next == NULL ? head : nowList->next;//如果到了队尾 返回队首
        if (nowList == tmp) return NULL;//判断是否循环了一圈
    }
}
int nfAlloc(int pid, int psize) {
    int ret = alloc(pid, psize, nfFindFreeSubArea(psize));
    nowList = nowList->next == NULL ? head : nowList->next;
    return ret;
}
//最佳适应算法
SubAreaList bfFindFreeSubArea(int psize) {
    SubAreaList p = head, minP = NULL;
    int minSize = MEMORY_SIZE + 1;
    while (p) {
        if (p->state == FREE && p->size >= psize) {
            if (p->size < minSize) {
                minSize = p->size;
                minP = p;
            }
        }
        p = p->next;
    }
    return minP;
}
int bfAlloc(int pid, int psize) {
    return alloc(pid, psize, bfFindFreeSubArea(psize));
}
//最坏适应算法
SubAreaList wfFindFreeSubArea(int psize) {
    SubAreaList p = head, maxP = NULL;
    int maxSize = -1;

    while (p) {
        if (p->state == FREE && p->size >= psize) {
            if (p->size > maxSize) {
                maxSize = p->size;
                maxP = p;
            }
        }
        p = p->next;
    }

    return maxP;
}
int wfAlloc(int pid, int psize) {
    return alloc(pid, psize, wfFindFreeSubArea(psize));
}

 
void FF(){
    printf("分配输入： A 作业号 大小n");
    printf("回收输入： F 作业号n");
    printf("退出输入： Qnn");

    char T[5];
    scanf("%s",T);
    while (T[0]!='Q'){
        if(T[0]=='A'){
            int id,size;
            printf("> ");
            scanf("%d%d",&id,&size);
            printf("%d %d",id,size);
            int ret = ffAlloc(id,size);
            if(ret){
                printf("作业号%d 分配%d KBn",id,size);
                displayAllocTable();
            } else{
                printf("n 内存不足，分配失败nn");
            }
        } else if(T[0]=='F'){
            int id;
            scanf("%d",&id);
            int ret = freeAlloc(id);
            if(ret){
                printf("作业号 %d  已回收n", id);
                displayAllocTable();
            }else {
                printf("未找到相关作业，回收失败nn");
            }
        }else
            exit(0);
        scanf("%s",T);
    }
}
 
void NF(){
    printf("分配输入： A 作业号 大小n");
    printf("回收输入： F 作业号n");
    printf("退出输入： Qnn");

    char T[5];
    scanf("%s",T);
    while (T[0]!='Q'){
        if(T[0]=='A'){
            int id,size;
            printf("> ");
            scanf("%d%d",&id,&size);
            printf("n%d %d",id,size);
            //关键步骤
            int ret = nfAlloc(id,size);
            if(ret){
                printf("作业号%d 分配%d KBn",id,size);
                displayAllocTable();
            } else{
                printf("n 内存不足，分配失败nn");
            }
        } else if(T[0]=='F'){
            int id;
            scanf("%d",&id);
            int ret = freeAlloc(id);
            if(ret){
                printf("作业号 %d  已回收n", id);
                displayAllocTable();
            }else {
                printf("未找到相关作业，回收失败nn");
            }
        }else
            exit(0);
        scanf("%s",T);
    }
}
void BF(){
    printf("分配输入： A 作业号 大小n");
    printf("回收输入： F 作业号n");
    printf("退出输入： Qnn");

    char T[5];
    scanf("%s",T);
    while (T[0]!='Q'){
        if(T[0]=='A'){
            int id,size;
            printf("> ");
            scanf("%d%d",&id,&size);
            printf("%d %d",id,size);
            //关键步骤
            int ret = bfAlloc(id,size);
            if(ret){
                printf("作业号%d 分配%d KBn",id,size);
                displayAllocTable();
            } else{
                printf("n 内存不足，分配失败nn");
            }
        } else if(T[0]=='F'){
            int id;
            scanf("%d",&id);
            int ret = freeAlloc(id);
            if(ret){
                printf("作业号 %d  已回收n", id);
                displayAllocTable();
            }else {
                printf("未找到相关作业，回收失败nn");
            }
        }else
            exit(0);
        scanf("%s",T);
    }
}
void WF(){
    printf("分配输入： A 作业号 大小n");
    printf("回收输入： F 作业号n");
    printf("退出输入： Qnn");

    char T[5];
    scanf("%s",T);
    while (T[0]!='Q'){
        if(T[0]=='A'){
            int id,size;
            printf("> ");
            scanf("%d%d",&id,&size);
            printf("%d %d",id,size);
            //关键步骤
            int ret = wfAlloc(id,size);
            if(ret){
                printf("作业号%d 分配%d KBn",id,size);
                displayAllocTable();
            } else{
                printf("n 内存不足，分配失败nn");
            }
        } else if(T[0]=='F'){
            int id;
            scanf("%d",&id);
            int ret = freeAlloc(id);
            if(ret){
                printf("作业号 %d  已回收n", id);
                displayAllocTable();
            }else {
                printf("未找到相关作业，回收失败nn");
            }
        }else
            exit(0);
        scanf("%s",T);
    }
}
 
 
int main(){
    head = initSubArea();
    nowList = head;

    printf("n-----------------------------------nn");
    printf("            内存动态分区分配方式的模拟           nn");
    printf(" 1) 首次适应算法n");
    printf(" 2) 循环首次适应算法n");
    printf(" 3) 最佳适应算法n");
    printf(" 4) 最坏适应算法n");
    printf(" q) 退出n");
    printf("n-------------------------------nn");
    char op[20];
    printf("> ");
    scanf("%s",op);

    if (!strcmp(op, "1"))
        FF();
    else if (!strcmp(op, "2"))
        NF();
    else if (!strcmp(op, "3"))
        BF();
    else if (!strcmp(op, "4"))
        WF();

    return 0;
}

参考链接：基于c语言的分区算法https://www.write-bug.com/article/1383.html

操作系统实验（一）——可变分区存储管理

C/C++/C#相关栏目本月热门文章