0
0

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

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

一、实验目的：

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

二、实验内容：

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

三、实验要求：

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

四、参考测试数据：

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

开始写代码！

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

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

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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 %5s\n","起始地址","终止地址","长度","分配状态","ID");

    while (p){
        printf("\n%5d %5d %5d %5d\n",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("退出输入： Q\n\n");

    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 KB\n",id,size);
                displayAllocTable();
            } else{
                printf("\n 内存不足，分配失败\n\n");
            }
        } else if(T[0]=='F'){
            int id;
            scanf("%d",&id);
            int ret = freeAlloc(id);
            if(ret){
                printf("作业号 %d  已回收\n", id);
                displayAllocTable();
            }else {
                printf("未找到相关作业，回收失败\n\n");
            }
        }else
            exit(0);
        scanf("%s",T);
    }
}
 
void NF(){
    printf("分配输入： A 作业号 大小\n");
    printf("回收输入： F 作业号\n");
    printf("退出输入： Q\n\n");

    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 KB\n",id,size);
                displayAllocTable();
            } else{
                printf("\n 内存不足，分配失败\n\n");
            }
        } else if(T[0]=='F'){
            int id;
            scanf("%d",&id);
            int ret = freeAlloc(id);
            if(ret){
                printf("作业号 %d  已回收\n", id);
                displayAllocTable();
            }else {
                printf("未找到相关作业，回收失败\n\n");
            }
        }else
            exit(0);
        scanf("%s",T);
    }
}
void BF(){
    printf("分配输入： A 作业号 大小\n");
    printf("回收输入： F 作业号\n");
    printf("退出输入： Q\n\n");

    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 KB\n",id,size);
                displayAllocTable();
            } else{
                printf("\n 内存不足，分配失败\n\n");
            }
        } else if(T[0]=='F'){
            int id;
            scanf("%d",&id);
            int ret = freeAlloc(id);
            if(ret){
                printf("作业号 %d  已回收\n", id);
                displayAllocTable();
            }else {
                printf("未找到相关作业，回收失败\n\n");
            }
        }else
            exit(0);
        scanf("%s",T);
    }
}
void WF(){
    printf("分配输入： A 作业号 大小\n");
    printf("回收输入： F 作业号\n");
    printf("退出输入： Q\n\n");

    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 KB\n",id,size);
                displayAllocTable();
            } else{
                printf("\n 内存不足，分配失败\n\n");
            }
        } else if(T[0]=='F'){
            int id;
            scanf("%d",&id);
            int ret = freeAlloc(id);
            if(ret){
                printf("作业号 %d  已回收\n", id);
                displayAllocTable();
            }else {
                printf("未找到相关作业，回收失败\n\n");
            }
        }else
            exit(0);
        scanf("%s",T);
    }
}
 
 
int main(){
    head = initSubArea();
    nowList = head;

    printf("\n-----------------------------------\n\n");
    printf("            内存动态分区分配方式的模拟           \n\n");
    printf(" 1) 首次适应算法\n");
    printf(" 2) 循环首次适应算法\n");
    printf(" 3) 最佳适应算法\n");
    printf(" 4) 最坏适应算法\n");
    printf(" q) 退出\n");
    printf("\n-------------------------------\n\n");
    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

标签： 大数据
本文转载自: https://blog.csdn.net/weixin_58570383/article/details/125843329
版权归原作者 零零打代码不秃头 所有， 如有侵权，请联系我们删除。
登录后发布评论

“操作系统实验（一）——可变分区存储管理”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

探索libstorj：高效安全的分布式文件传输库

Go中更安全的枚举

差分隐私与联邦学习安全原理与代码实战案例讲解

开源 XDR/SIEM 安全平台，附下载链接

linux 常用知识汇总（非常全面！）

Docker 配置国内镜像源

2024docker可用镜像源配置

文章导航