【操作系统】实验四 主存空间的分配和回收

木来 木来

实验四主存空间的分配和回收

一、目的和要求

1. 实验目的

用高级语言完成一个主存空间的分配和回收程序,以加深对动态分区分配方式及其算法的理解。

2.实验要求

采用连续分配方式之动态分区分配存储管理,使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计(任选两种算法)。

(1)设计一个作业申请队列以及作业完成后的释放顺序,实现主存的分配和回收。采用分区说明表进行。

(2)或在程序运行过程,由用户指定申请与释放。

(3)设计一个空闲区说明表,以保存某时刻主存空间占用情况。把空闲区说明表的变化情况以及各作业的申请、释放情况显示。

二、实验内容

编写并调试一个模拟的内存分配与回收程序,使用首次适应算法、循环首次适应算法对内存空间的分配与回收。

三、实验方法、步骤及结果测试

1.    源程序名:a.cpp

可执行程序名:a.exe

2.    原理分析

(1)编写该程序首先要给定一个一定空间大小的内存,即申请空闲区空间最大值,并且要定义空间的各分区的作业标号、分区起始地址、分区长度,单位为字节、分区表的状态位、前向指针、后向指针、已分配分区表、空闲分区等。

(2)通过定义空间分区后,还要定义空间分区链表并对其进行初始化,对空闲分区和已分配分区进行链表访问,对于空闲分区可以分配给新进来的进程使用,对于已分配的分区,则等进程执行结束后在回收空间,恢复空闲区。通过链表的访问实现整个空间分区的分配与回收。

3.      主要程序段及其解释:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <conio.h>
#define nil -1
#define NULL 0
#define maxisize 600    //用户的空闲区空间最大值
#define minisize 4     
#define getspace(type) (type*)malloc(sizeof(type)) //分配空间
struct table{
    char job;                 //作业标号
    float address;            //分区起始地址
    float length;             //分区长度,单位为字节
    int flag;                 //分区表的标志
    struct table *FRlink;     //前向指针
    struct table *RElink;    //后向指针
}*free_table = NULL, *place;   //已分配分区表,空闲分区表
typedef struct table FRtable;
//空间分区链表初始化
FRtable *init(FRtable *tb)
{
    tb->FRlink = NULL;
    tb->job = nil;
    tb->address = 1064;
    tb->length = 1664;
    tb->flag = 0;
    tb->RElink = NULL;
    return tb;
}
//主存分配函数,为作业job分配大小为xk的分区空间
void allocate(char job, float xk, int choice)
{
    FRtable *tb=NULL, *link;
    int k = 0;
    float temp = 600;
    if (free_table->FRlink == NULL&&free_table->RElink == NULL)
    {//给首个作业分配空间,改写分区链表
        free_table->job = job;
        free_table->length = xk;
        free_table->flag = 1;
        if (xk<maxisize)
        {
            tb = getspace(FRtable);
            free_table->RElink = tb;
            tb->FRlink = free_table;
            tb->job = nil;
            tb->address = 1064 + xk;
            tb->length = maxisize - xk;
            tb->flag = 0;
        }
        if (choice == 2)
        {//链接成循环链表
            free_table->FRlink = tb;
            tb->RElink = free_table;
            place = tb;
        }
        else
        {
            free_table->FRlink = NULL;
            if (xk<maxisize) tb->RElink = NULL;
        }
        k = 1;
    }
    else
    {
        if (2 == choice) tb = place;//采用CFF时将ta定位到上次找到的合适空间分区的下个空间分区
        else tb = free_table;
        while (tb != NULL)
        {
            if (3 == choice)
            {
                while (tb != NULL)
                {
                    if (tb->length >= xk&&tb->flag == 0)
                    if (tb->length<temp)
                    {
                        place = tb; temp = tb->length;
                    }   //选择最适合空间
                    tb = tb->RElink;
                }
                tb = place;
            }
            if (tb->length >= xk&&tb->flag == 0)
            if (tb->length - xk <= minisize)
            {//当搜索到的空间大小<=xk+minisize时,将空间全部分配给作业
                tb->job = job;
                tb->flag = 1;
                place = tb->RElink;
                k = 1;
                break;
            }
            else
            {//当搜索到的空间大小>xk+minisize时,将空间划分,再分配给作业
                link = getspace(FRtable);
                link->length = tb->length - xk;
                tb->job = job;
                tb->length = xk;
                tb->flag = 1;
                link->RElink = tb->RElink;
                if (NULL != tb->RElink) tb->RElink->FRlink = link;
                tb->RElink = link;
                link->FRlink = tb;
                link->job = nil;
                link->address = tb->address + xk;
                link->flag = 0;
                place = link;
                k = 1;
                break;
            }
            tb = tb->RElink;
        }
    }
    if (0 == k)
    {//未寻找到合适的空间分区,返回
        printf(">>空间申请失败! \n");
        return;
    }
}

//主存回收函数,回收作业job所占用的分区空间
void reclaim(char job, int choice)
{
    int bool1 = 0, bool2 = 0;
    FRtable *tb, *link;
    tb = free_table;
    if (2 == choice) link = tb;
    else link = NULL;
    do
    {
        if (job == tb->job && 1 == tb->flag) break;
        tb = tb->RElink;
        if (tb == link)
        {
            printf("\n>>抱歉,不存在作业%c! \n", job);
            return;
        }
    } while (tb != link);
    bool1 = (NULL == tb->FRlink || tb->FRlink == tb->RElink) ? 1 : tb->FRlink->flag;
    bool2 = (NULL == tb->RElink || tb->FRlink == tb->RElink) ? 1 : tb->RElink->flag;
    if (bool1&&bool2)
    {
        tb->job = nil;
        tb->flag = 0;
    }
    else if ((NULL == tb->FRlink || 1 == tb->FRlink->flag) && 0 == tb->RElink->flag)
    {
        link = tb->RElink;
        tb->job = nil;
        tb->length += link->length;
        tb->flag = 0;
        tb->RElink = link->RElink;
        if (NULL != link->RElink) link->RElink->FRlink = tb;
        free(link);
    }
    else if (0 == tb->FRlink->flag && 1 == tb->RElink->flag)
    {
        link = tb->FRlink;
        link->length += tb->length;
        link->RElink = tb->RElink;
        tb->RElink->FRlink = link;
        if (free_table == tb) free_table = link;
        free(tb);
    }
    else if (0 == tb->FRlink->flag && 0 == tb->RElink->flag)
    {
        link = tb->FRlink;
        link->length = link->length + tb->length + tb->RElink->length;
        link->RElink = tb->RElink->RElink;
        if (NULL != tb->RElink->RElink) tb->RElink->RElink->FRlink = link;
        if (free_table == tb) free_table = link;
        free(tb);
        free(tb->RElink);
    }
}
//显示空间分区链表
void display(FRtable *tb, int choice)
{
    //    clrscr();
    FRtable *temp;
    if (2 == choice) temp = tb;
    else temp = NULL;
    printf("\n\t标号\t起始地址\t分区大小(KB)\t    标志\n");
    printf("\n\t sys\t 1024.00\t 40.00\t\t     1\n");
    do
    {
        printf("\n\t %c\t %.2f\t %.2f\t\t     %d\n", tb->job, tb->address, tb->length, tb->flag);
        tb = tb->RElink;
    } while (temp != tb);
}
//主函数
int main()
{
    int i, a, choice;
    float xk;
    char job;
    FRtable *ta = getspace(FRtable);
    free_table = init(ta);
    do{
        printf("\n 分区分配算法:\n\t0 - 退出(Exit)\n\t1 - 首次适应算法(FF)\n\t2 - 循环首次适应算法(CFF)\n \n");
        printf(">>请选择相应的算法:");
        scanf("%d", &choice);
        if (0 == choice) exit(0);
    } while (0>choice && 2<choice);
    while (1)
    {
        printf("\n    菜单:\n\t0 - 退出(Exit)\n\t1 - 申请空间(Allocation)\n\t2 - 回收空间(Reclaim) \n");
        printf(">>请选择你的操作:");
        scanf("%d", &a);
        switch (a)
        {
            //a=0,程序结束
        case 0:exit(0);
            //a=1,分配主存空间
        case 1:printf(">>请输入作业标号和所需要申请的空间:");
            scanf("%*c%c%f", &job, &xk);
            allocate(job, xk, choice);
            display(free_table, choice);
            break;
            //a=2,回收主存空间
        case 2:printf(">>请输入你想回收的作业的相应标号:");
            scanf("%*c%c", &job);
            reclaim(job, choice);
            display(free_table, choice);
            break;
        default:printf(">>ERROR:No thie choose! \n");
        }
    }

    system("pause");
}




4.运行结果

040946111336464.jpg

如上图所示,当输入需要申请的空间和标号后,空闲分区会分配相应的空间大小,当输入回收的标号时,内存会回收相应大小的空间。根据实验结果显示,实验已达到预期效果。

实验总结

(1)本次实验是有关内存空间分配的算法的实现,实验内容相对之前的进程调度稍微简洁些,但是基本实现的数据结构的链表算法是一样的,还是需要通过申请空间,定义分区大小,然后通过链表对各空闲分区进行相应的内存分配。

(2)虽然对实验步骤比较清晰,对首次适应算法、循环首次适应算法的知识理解得比较好,但是在对如何通过这些算法去实现这个内存分配的实验,还是遇到很多困难,比如链表初始化与访问的算法基础掌握得不好,还有一些基本的C语言的语法结构掌握不熟练,而且对算法与与程序之间的思维不清晰,导致在写程序中出现较多问题,然后通过查找课本,上网搜寻资料,询问同学进行帮助解答,最后得到基本的实验程序。

0 条评论