操作系统作业

木来 木来

实验二 内存分配与回收模拟算法

一.实验目的

 理解连续分配方式的动态分区算法

二.实验内容与基本要求

1、编写程序,模拟实现以下功能:

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

由用户指定申请和释放操作,结果以空闲分区表、已分配区表展示。

程序设计语言任选。请同学们认真完成并书写实验报告。

提交内容:将程序源代码及实验报告打包成压缩包,命名为:学号-姓名

实验报告格式参考模板

提交时间:12.17之前


作业源码:

#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()
{
    printf("诚意印象作业\n");
    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");
}




 

 

0 条评论