devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

操作系统原理与实验——实验十分离散存储管理方式的模拟和实现（分段式）_希冀段式存储管理模拟实验

作者：代码探险家 | 2024-06-25 07:54:38

赞

踩

希冀段式存储管理模拟实验

实验指南

运行环境：

Dev c++

算法思想：

本实验是模拟分段存储管理，系统需要建立两张分区表，分别是已分配和未分配分区表，首先根据装入作业的大小判断是否小于空闲分区的总容量，若满足，则对该作业继续进行分段，每输入一个分段大小就在空闲分区中找到第一个没有使用且足够大的分区，若找到将该分区标记为该作业名和对应的分段号，修改已分配和未分配分区表，并打印内存分配信息。对已分配分区的回收，首先输入要回收的作业名，找到该作业的每一段所在的分区，修改已分配分区表，未分配分区表（根据是否存在上下邻），打印回收成功后内存分配信息。

关键数据结构定义：

//内存结构体

typedef struct memory_node

{

    int size; //内存大小

    int address; //内存始址

} memoryNode;

memoryNode memory;

//分区结构体

typedef struct link_node

{

    int id;//分区号

    int size; //分区长度

    int address; //分区始址

    char flag[20]; //分区状态，空闲或者占用作业名

    struct link_node* next;

} node;

//段表

typedef struct segment_node

{

    int a[10][10];

    struct segment_node *next;

} segmentNode;

程序框架：

//函数名 :initMemory  参数:无

node* initMemory()

{

  //函数功能：初始化内存空间

}

//函数名:operation 参数:node* head

int operation(node *head)

{

//函数功能：打印操作菜单，选择需要进行的操作,输入1进行内存 分配,输入2进  行内存去配,输入0退出

}

//函数名:allocate 参数:node* head

void allocate(node *head)

{

//函数名：输入作业名和大小，默认采用最先分配

}

//函数名:firstAllocation 参数:node* head,int size,charc[10]

void firstAllocation(node* head,int size,char c[10])

{

 //函数功能：对作业进行分段，并采用最先分配，分段结束后打印 段表

}

        //函数名:reorder 参数:node* head

void reorder(node* head)

{

   //函数功能：对分区和未分区的存储区域进行编号 

}

//函数名:recycle 参数:node* head

void recyle(node* head) //回收算法

{

   //函数功能：对归还分区按情况进行处理，，有上邻有下邻，有上邻     无下邻，无上邻有下邻，无上邻无下邻

            

}

//函数名:print参数:node* head

void print(node* head)

{

   //函数功能：打印主存分配表

}

int main()

{

    node* head;

    head=initMemory();

    while(1)

    {

        int c;

        c=operation(head);

        if(c==1)

        {

            break;

        }

    }

    return 0;

}

测试用例：

/*

256

40

1

jobA

50

2

20

30

1

jobB

100

3

30

35

35

2

jobB

2

jobA

0

*/

关键代码

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<string.h>
  4. int g_size; 
  5. //内存结构体
  6. typedef struct memory_node
  7. {
  8.     int size; //内存大小
  9.     int address; //内存始址
  10. } memoryNode;
  11.  
  12. memoryNode memory;
  13.  
  14. //分区结构体
  15. typedef struct link_node
  16. {
  17.     int id;//分区号
  18.     int size; //分区长度
  19.     int address; //分区始址
  20.     char flag[20]; //分区状态，空闲或者占用作业名
  21.     struct link_node* next;
  22. } node;
  23.  
  24. //段表
  25. typedef struct segment_node
  26. {
  27.     int sum;
  28.     char jobname[20];
  29.     int a[10][10];
  30.     struct segment_node *next;
  31. } segmentNode;
  32.  
  33. node* initMemory();
  34. node* operation(node *head);
  35. node* allocate(node *head);
  36. node* firstAllocation(node* head,int size,char c[10]);
  37. node* reorder(node* head);
  38. node* recyle(node* head);
  39. void print(node* head);
  40.  
  41.     node *distribute = NULL;
  42.     segmentNode *duanbiao =NULL;
  43.  
  44. //函数名 :initMemory  参数:无
  45. node* initMemory()
  46. {
  47.   //函数功能：初始化内存空间
  48.     printf("请输入内存大小：");
  49.     scanf("%d",&memory.size);g_size = memory.size;
  50.     printf("请输入起始地址：");
  51.     scanf("%d",&memory.address);
  52.     node* p = (node *) malloc ( sizeof(node) * memory.size ); //分配可以放得下265个node的内存空间
  53.     p->next = NULL;
  54.     p->id = 1;
  55.     p->size = memory.size;
  56.     p->address = memory.address;
  57.     p->flag[0] = '\0';
  58.     return p;
  59. }
  60.  
  61. //函数名:operation 参数:node* head
  62. node* operation(node *head)
  63. {
  64. //函数功能：打印操作菜单，选择需要进行的操作,输入1进行内存分配,输入2进行内存去配,输入0退出
  65.     int choice; 
  66.     printf("*********可变分区管理**********\n");
  67.     printf("   *     1.内存分配      *\n");
  68.     printf("   *     2.内存去配      *\n");
  69.     printf("   *     0.退出          *\n");
  70.     printf("         请输入选项[ ]\b\b");
  71.     scanf("%d",&choice);
  72.     if(choice == 1)
  73.     {
  74.         printf("1.内存分配\n");
  75.         reorder(head); 
  76.         print(head);
  77.         head=allocate(head);
  78.     }
  79.     else if(choice == 2)
  80.     {
  81.         printf("2.内存去配\n");
  82.         reorder(head);
  83.         print(head);
  84.         head=recyle(head); 
  85.     }
  86.     else
  87.     {
  88.         return NULL;
  89.     }
  90.     return head;
  91. }
  92. //函数名:allocate 参数:node* head
  93. node* allocate(node *head)
  94. {
  95. //函数名：输入作业名和大小，默认采用最先分配
  96.     char name[20];
  97.     int jobsize;
  98.     printf("请输入作业名：");
  99.     scanf("%s",&name);
  100.     printf("请输入%s需要分配的主存大小：",name);
  101.     scanf("%d",&jobsize);
  102.     if(jobsize <= g_size)
  103.     head = firstAllocation(head,jobsize,name);
  104.     else
  105.     printf("分配失败！");
  106.     return head;
  107.      
  108. }
  109.  
  110. //函数名:firstAllocation 参数:node* head,int size,charc[10]
  111. node* firstAllocation(node* head,int size,char c[10])
  112. {
  113.  //函数功能：对作业进行分段，并采用最先分配，分段结束后打印 段表
  114.     int count = 0,blockNum,jobblocksize,state;
  115.     node *q,*pre;
  116.     
  117.     segmentNode* D = (segmentNode *) malloc ( sizeof(segmentNode) * 1 ); 
  118.     D->next = NULL;
  119.     strcpy(D->jobname,c);
  120.     if(duanbiao == NULL) 
  121.     duanbiao = D;
  122.     else
  123.     {
  124.         D->next = duanbiao;
  125.         duanbiao = D;
  126.     }
  127.     
  128.     q = head;
  129.     printf("请输入要分成几段：");
  130.     scanf("%d",&blockNum);D->sum = blockNum;
  131.     while(count != blockNum)
  132.     {   
  133.         printf("剩余%dKB的内存，请输入第%d段的大小：",size,count+1);
  134.         scanf("%d",&jobblocksize);
  135.         node* p = (node *) malloc ( sizeof(node) * 1 ); 
  136.         p->next = NULL;
  137.         p->size = jobblocksize;
  138.         strcpy(p->flag,c);
  139. //      p->flag[strlen(p->flag)+1] = p->flag[strlen(p->flag)];
  140. //      p->flag[strlen(p->flag)]= '0' + count;
  141.         
  142.         state = count;
  143.         while(1)
  144.         {
  145.             if(state/10 == 0)
  146.             {
  147.                 p->flag[strlen(p->flag)+1] = p->flag[strlen(p->flag)];
  148.                 p->flag[strlen(p->flag)]= '0' + state%10;
  149.                 break;
  150.             }
  151.             else
  152.             {
  153.                 p->flag[strlen(p->flag)+1] = p->flag[strlen(p->flag)];
  154.                 p->flag[strlen(p->flag)]= '0' + state/10;
  155.                 state=state%10;
  156.             }
  157.         }
  158.         
  159.         while(q!=NULL)
  160.         {
  161.             if(q->size >= p->size)
  162.             break;
  163.             pre = q;
  164.             q = q->next;
  165.         }
  166.         if(q!=NULL)
  167.         {
  168.             p->address = q->address;
  169.             if(q->size == p->size)
  170.             {
  171.                 if(q==head)
  172.                 head=NULL;
  173.                 else
  174.                 pre->next = q->next;
  175.             }
  176.             else
  177.             {
  178.                 q->size = q->size -p->size;
  179.                 q->address = q->address + p->size;
  180.             }
  181.             if(distribute == NULL)
  182.             {
  183.                 distribute = p;
  184.             }
  185.             else
  186.             {
  187.                 p->next = distribute;
  188.                 distribute = p;
  189.             }
  190.         }
  191.         else
  192.         {
  193.             printf("分配失败！");
  194.             return head;
  195.         }
  196.         D->a[count][0] = jobblocksize;
  197.         D->a[count][1] = p->address + p->size;
  198.         count++;
  199.         size = size - jobblocksize;
  200.         reorder(head);
  201.         print(head);
  202.     }
  203.     printf("分配成功！\n");
  204.     printf("************打印%s段表************\n",c);
  205.     printf("段号\t段长\t基址\n");
  206.     for(int i=0;i<blockNum;i++)
  207.     printf("%d\t%d\t%d\n",i,D->a[i][0],D->a[i][1]);
  208.     return head;
  209. }
  210.  
  211.     //函数名:reorder 参数:node* head
  212. node* reorder(node* head) 
  213. {
  214.    //函数功能：对分区和未分区的存储区域进行编号  
  215.    int count;
  216.    node *p;
  217.    count = 1;
  218.    p = distribute;
  219.    while(p!=NULL)
  220.    {
  221.         p->id = count;
  222.         count++;
  223.         p = p->next; 
  224.    }
  225.    
  226.    p = head;
  227.    while(p!=NULL)
  228.    {
  229.         p->id = count;
  230.         count++;
  231.         p = p->next; 
  232.    }
  233.    return head;
  234. }
  235.  
  236. //函数名:recycle 参数:node* head
  237. node* recyle(node *head) //回收算法
  238. {
  239.    //函数功能：对归还分区按情况进行处理，有上邻有下邻，有上邻无下邻，无上邻有下邻，无上邻无下邻
  240.     char name[20];
  241.     int state;
  242.     segmentNode *q,*preq;
  243.     node *qq,*preqq,*qqq,*preqqq;//distribute 
  244.     q = duanbiao;
  245.     printf("请输入您想回收的作业名：");
  246.     scanf("%s",&name);
  247.     while(q!=NULL&&strcmp(q->jobname,name)!=0)
  248.     {
  249.         preq = q;
  250.         q = q->next;
  251.     }
  252.     if(q==duanbiao)
  253.     {
  254.         duanbiao=q->next;
  255.     }
  256.     else
  257.     {
  258.         preq->next=q->next;
  259.     }
  260.     if(q==NULL)
  261.     printf("没有该作业！");
  262.     else
  263.     {
  264.         for(int i=0;i<q->sum;i++)
  265.         { 
  266.             qq = distribute;//已分配链表 
  267.             while(qq!=NULL)//在已分配表中找要回收的作业
  268.             {
  269.                 if(qq->address == q->a[i][1]-q->a[i][0])
  270.                 {
  271.                     if(qq==distribute)
  272.                     {
  273.                         distribute = qq->next;
  274.                     }
  275.                     else
  276.                     {
  277.                         preqq->next = qq->next;
  278.                     }
  279.                     break;
  280.                 }
  281.                 preqq = qq;
  282.                 qq = qq->next;
  283.             }
  284.             
  285.             preqqq = NULL;
  286.             qqq = head;//未分配链表 
  287.             while(qqq!=NULL)//将要回收的作业的空闲分区合并
  288.             {
  289.                 if(qq->address+qq->size<head->address)//头没有临界区
  290.                 {
  291.                     qq->next = head;
  292.                     head = qq;
  293.                     printf("回收%s的段%s成功！\n",name,qq->flag);
  294.                     qq->flag[0] = '\0'; 
  295.                     break;
  296.                 }
  297.                 else if(qq->address+qq->size == head->address)//头有下
  298.                 {
  299.                     head->address = qq->address;
  300.                     head->size = head->size + qq->size;
  301.                     printf("回收%s的段%s成功！\n",name,qq->flag);
  302.                     break;
  303.                 }
  304.                 else if(preqqq!=NULL&&qq->address == preqqq->address+preqqq->size&&qq->address+qq->size==qqq->address)//有上有下
  305.                 {
  306.                     preqqq->size = preqqq->size+qqq->size+qq->size;
  307.                     preqqq->next = qqq->next;
  308.                     printf("回收%s的段%s成功！\n",name,qq->flag);
  309.                     free(qq);
  310.                     break;
  311.                 }
  312.                 else if(preqqq!=NULL&&qq->address == preqqq->address+preqqq->size&&qq->address+qq->size<qqq->address)//有上没有下
  313.                 {
  314.                     preqqq->size =preqqq->size + qq->size;
  315.                     printf("回收%s的段%s成功！\n",name,qq->flag);
  316.                     free(qq);
  317.                     break;
  318.                 }
  319.                 else if(preqqq!=NULL&&qq->address > preqqq->address+preqqq->size&&qq->address+qq->size==qqq->address)//没有上有下
  320.                 {
  321.                     qqq->address = qq->address;
  322.                     qqq->size = qqq->size+qq->size;
  323.                     printf("回收%s的段%s成功！\n",name,qq->flag);
  324.                     free(qq);
  325.                     break;
  326.                 }
  327.                 else if(preqqq!=NULL&&qq->address > preqqq->address+preqqq->size&&qq->address+qq->size<qqq->address)//没有上没有下
  328.                 {
  329.                     qq->next = qqq;
  330.                     preqqq->next = qq;
  331.                     printf("回收%s的段%s成功！\n",name,qq->flag);
  332.                     qq->flag[0] = '\0';
  333.                     break;
  334.                 }
  335.                 else if(preqqq!=NULL&&qqq->next == NULL&&qqq->address+qqq->size==qq->address)//尾部（有上）
  336.                 {
  337.                     qqq->size = qqq->size+qq->size;
  338.                     printf("回收%s的段%s成功！\n",name,qq->flag);
  339.                     break;
  340.                 }
  341.                 else if(preqqq!=NULL&&qqq->next == NULL&&qqq->address+qqq->size<qq->address)// 尾部（没有上）
  342.                 {
  343.                     qqq->next = qq;
  344.                     qq->next =NULL;
  345.                     printf("回收%s的段%s成功！\n",name,qq->flag);
  346.                     qq->flag[0]='\0';
  347.                     break;
  348.                 }
  349.                 preqqq = qqq;
  350.                 qqq = qqq->next; 
  351.             }
  352.             
  353.         }
  354.         reorder(head);
  355.         print(head);
  356.         free(q);
  357.     }
  358.     return head;
  359. }
  360. //函数名:print参数:node* head
  361. void print(node* head)
  362. {
  363.    //函数功能：打印主存分配表
  364.     node *p;
  365.     printf("******************主存分配情况******************\n");
  366.     p = distribute;
  367.     printf("已分配：\n");
  368.     printf("分配号  大小（KB）      起始（KB）      状态\n");
  369.     while(p!=NULL&&p->flag[0]!='\0')
  370.     {
  371.         printf("%d\t%d\t\t%d\t\t%s\n",p->id,p->size,p->address,p->flag);
  372.         p = p->next;
  373.     }
  374.     printf("\n\n\n");
  375.     p = head;
  376.     printf("未分配：\n");
  377.     printf("分配号  大小（KB）      起始（KB）      状态\n");
  378.     while(p!=NULL&&p->flag[0] == '\0')
  379.     {
  380.         printf("%d\t%d\t\t%d\t\t空闲\n",p->id,p->size,p->address,p->flag);
  381.         p = p->next;
  382.     }
  383. }
  384.  
  385. int main()
  386. {
  387.     node* head;
  388.     head=initMemory();
  389.     while(1)
  390.     {
  391.         head=operation(head);
  392.         if(head==NULL)
  393.         {
  394.             break;
  395.         }
  396.     }
  397.     return 0;
  398. }

运行结果

实验总结

①对单链表还是不熟,没有头结点的单链表head没有next；

②对链表的遍历条件没有设计好，在该题中preqqq！=NULL才能进行遍历；

③对于指针，如果修改了指针则要返回该指针并赋值给它本身，或者在传递指针时，传的是指针的指针，否则对指针的处理是无效的。

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号