第十六届全国青少年信息学奥赛题(模拟系统内存分配)

主题：第十六届全国青少年信息学奥赛题(模拟系统内存分配)

qinheng [专家分：280] 发布于 2005-10-28 19:41:00

[em28][em28][em28]
内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。经典的内存分配过程是这样进行的：

    内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。

    运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内（即T时刻开始，T+P时刻结束），这M个被占用的内存单元不能再被其他进程使用。

    假设在T时刻有一个进程申请M个单元，且运行时间为P，则：

    若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。

    如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为M的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

    现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

   输入

第一行是一个数N，表示总内存单元数（即地址范围从0到N-1）

从第二行开始每行描述一个进程的三个整数T、M、P（M<=N）。

数据已按T从小到大排序。

最后一行用三个0表示结束。

输入文件最多10000行，且所有数据都小于109。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

   输出

包括2行。

第一行是全部进程都运行完毕的时刻。

第二行是被放入过等待队列的进程总数。

样例输入

10

1 3 10

2 4 3

3 4 4

4 1 4

5 3 4

0 0 0

　

样例输出

12

2

样例示例时刻

T内存占用情况进程事件

   1

   2

   3

   4

   5

   6

   7

   8

   9

  10

  11

120123456789进程A申请空间（M=3,P=10）<成功>

  A

  AB进程B申请空间（M=4,P=3）<成功>

  AB进程C申请空间（M=4,P=4）<失败进入等待队列>

  ABD进程D申请空间（M=1,P=4）<成功>

   ACD进程B结束，释放空间

   进程C从等待队列取出，分配空间

   进程E申请空间（M=3,P=4）<失败进入等待队列>

   ACD

   ACD

   ACE进程D结束，释放空间

   进程E从等待队列取出，分配空间

   AE进程C结束，释放空间

   AE

   E进程A结束，释放空间

   进程E结束，释放空间
[b]请高手帮忙,解决一下这个问题,研究了好长时间都没有结果...[/b]

本帖地址： http://bbs.pfan.cn/post/116505.html

回复列表（共14个回复）

沙发

qinheng [专家分：280] 发布于 2005-10-29 21:54:00

大家不管会不会的请留下自己的想法行吗?急需大家的帮助啊!!!小弟在这里谢谢大家了!!~~

板凳

独行者 [专家分：1280] 发布于 2005-10-30 09:43:00

感觉有点复杂,我需要一点时间考虑以下,下次告诉你.

3 楼

qinheng [专家分：280] 发布于 2005-10-31 22:40:00

来的人都给分啊,希望大家一起来研究讨论

4 楼

天空飞雪 [专家分：960] 发布于 2005-11-01 19:29:00

这题好抽呀，需要好好研究。。。。。。。。

5 楼

独行者 [专家分：1280] 发布于 2005-11-02 16:19:00

我已编好代码，但是还未调试好。明天给你帖出来，最迟后天！

6 楼

qinheng [专家分：280] 发布于 2005-11-02 20:48:00

5楼的,最好有算法,其实代码并不是最难的,难写还是算法,可能的话,把你的算法也写下来好吗?等待你的回音`~~~

7 楼

独行者 [专家分：1280] 发布于 2005-11-04 10:05:00

我的思路是：
   1.把输入得数居存起来。可以利用结构体，每个结构体中存三个数即T.M.P.
   2.利用一个数组来模拟内存，并按照时间进行分配。（如一个进程T=1,M=2,P=3,那么就在第一时刻把内存中的两个空闲单元赋值为T+P(4)).
      （1）.要实现此功能必须利用时间进行循环，在每一时刻都对整个内存进行一遍扫描，如果内存单元中的数据等于时刻time,就把该单元中的值变为0。
      （2）.在每次扫描是都要把内存中的空闲单元的起止地址记录下来。（可以利用一个每个单元中含2个int型数据的结构体数组）
      （3）.在每一时刻进行了以上两步后，检测等待队列，如果有等待的进程则先对其分配内存，然后再分配该时刻申请的进程。
      （4）.如果内存中没有足够大的空间则将其防入等待队列。
代码如下：
（因时间关系未完成调试，我会尽快完成）
    main()
{
   int n,i,j,k,p=0,m,q,time,t=1,x=0;/*p,t为状态变量*/
   int NC[100]={0};      /*模拟内存*/
   struct sj             /*存储输入数据的结构体*/
   {  int T;
      int M;
      int P; };
   typedef struct sj s;  /*记录空闲内存地址的结构体*/
   struct jl
   {  int d;
      int c;  };
   typedef struct jl l;
   s a[1000],c,da[100],*front=&da[0],*rear;
   l b[1000];
   front--;rear=front;
   c.T=1;
   scanf("%d",&n);       /*输入数据*/
   for(i=0;i<n;i++)
     b[i].d=b[i].c=0;
   i=0;
   while(c.T!=0)
   {
      scanf("%d%d%d",&a[i].T,&a[i].M,&a[i].P);
      c.T=a[i].T;c.M=a[i].M;c.P=a[i].P;
      i++;
     }
   k=i;                    /*记录数据总量*/
   for(time=1;t!=0;time++)   /*按时间进行循环*/
   {
      t=0;
      for(i=0,j=0;i<n;i++)   /*扫描内存*/
      {
           if(NC[i]>=time)    /*如果内存使用完毕，将其清空*/
        NC[i]=0;
           if(i=0&&NC[i]==0)   /*记录空闲地址*/
             NC[i].d=i;
           else
         if(NC[i-1]!=0&&NC[i]==0)
           b[j].d=i;

       if(i==n-1&&NC[i]==0)
          b[j].c=i;
           else
             if(NC[i]!=0&&NC[i-1]==0)
          { b[j].c=i-b[j].c; j++; }
      }
       while(front!=rear||p==1)   /*检测队列*/
     {
        front++;
        for(i=0,p=1;i<j||p==0;i++)
          if(b[i].c>=(*front).M)
          {
         for(q=b[i].d;q<b[i].c+b[i].d;q++)
           NC[q]=(*front).P+time;
         p=0;
           }
        if(p==1) front--;
       }
    if(time<=k)
    {
      if(a[time-1].T==time)
       for(i=0,p=1;i<j||p==0;i++)
        if(b[i].c>=a[time-1].M)
        {
           for(q=b[i].d;q<a[time-1].M+b[i].d;q++)
         NC[q]=a[time-1].P+time;
           p=0;
         }
       else
       {
        if(rear<=&da[99] )
        {  rear++;
           (*rear).T=a[time-1].T; (*rear).M=a[time-1].M; (*rear).P=a[time-1].P;
           x++;
         }
        else
          printf("Can not put in!");
        }
       }
          for(i=0;i<n;i++)
        t+=NC[i];

    printf("%d\n%d\n",time,x);
}

8 楼

独行者 [专家分：1280] 发布于 2005-11-04 13:40:00

我刚刚修改了一下，但也不敢保证结果完全正确
  main()
{
   int n,i,j,k,p=0,m,q,time,t=1,x=0;/*p,t为状态变量*/
   int NC[100]={0};      /*模拟内存*/
   struct sj             /*存储输入数据的结构体*/
   {  int T;
      int M;
      int P; };
   typedef struct sj s;  /*记录空闲内存地址的结构体*/
   struct jl
   {  int d;
      int c;  };
   typedef struct jl l;
   s a[1000],c,da[100],*front=&da[0],*rear;
   l b[1000];
   front--;rear=front;
   c.T=1;
   scanf("%d",&n);       /*输入数据*/
   for(i=0;i<n;i++)
     b[i].d=b[i].c=0;
   i=0;
   while(c.T!=0)
   {
      scanf("%d%d%d",&a[i].T,&a[i].M,&a[i].P);
      c.T=a[i].T;c.M=a[i].M;c.P=a[i].P;
      i++;
     }
   k=i;                    /*记录数据总量*/
   for(time=1;t!=0;time++)   /*按时间进行循环*/
   {
      t=0;
      for(i=0,j=0;i<n;i++)   /*扫描内存*/
      {
           if(NC[i]<=time)    /*如果内存使用完毕，将其清空*/
        NC[i]=0;
           if(i=0&&NC[i]==0)   /*记录空闲地址*/
             b[j].d=i;
           else
         if(NC[i-1]!=0&&NC[i]==0)
           b[j].d=i;

       if(i==n-1&&NC[i]==0)
          b[j].c=i;
           else
             if(NC[i]!=0&&NC[i-1]==0)
          { b[j].c=i-b[j].c; j++; }
      }
       while(front!=rear||p==1)   /*检测队列*/
     {
        front++;
        for(i=0,p=1;p==1;i++)
          if(b[i].c>=(*front).M)
          {
         for(q=b[i].d;q<b[i].c+b[i].d;q++)
           NC[q]=(*front).P+time;
         p=0;
           }
        if(p==1) front--;
       }
    if(time<=k)
    {
      if(a[time-1].T==time)
       for(i=0,p=1;p==1;i++)
        if(b[i].c>=a[time-1].M)
        {
           for(q=b[i].d;q<a[time-1].M+b[i].d;q++)
         NC[q]=a[time-1].P+time;
           p=0;
         }
       else
       {
        if(rear<=&da[99] )
        {  rear++;
           (*rear).T=a[time-1].T; (*rear).M=a[time-1].M; (*rear).P=a[time-1].P;
           x++;
         }
        else
          printf("Can not put in!");
        }
       }
          for(i=0;i<n;i++)
        t+=NC[i];

    printf("%d\n%d\n",time,x);
}
我这是在网吧回的贴，u盘刚好坏了，所以只能凭记忆重新修改了一遍，都是些循环条件和判断条件的错误。鉴于本人水平有限，所以程序有些繁杂。如有更好的算法请不吝赐教！

9 楼

qinheng [专家分：280] 发布于 2005-11-04 20:12:00

我按照你说的修改了程序里的错误,编译通过了,可是输入数据没有结果啊???

10 楼

独行者 [专家分：1280] 发布于 2005-11-05 13:35:00

不会吧？再我这里有结果啊，虽然结果不一定正确。
你用这个再试一次：
main()
{
   int n,i,j,k,p=0,m,q,time,t=1,x=0;
   int NC[100]={0};
   struct sj
   {  int T;
      int M;
      int P; };
   typedef struct sj s;
   struct jl
   {  int d;
      int c;  };
   typedef struct jl l;
   s a[1000],c,da[100],*front=&da[0],*rear;
   l b[1000];
   front--;rear=front;
   c.T=1;
   scanf("%d",&n);
   for(i=0;i<n;i++)
     b[i].d=b[i].c=0;
   i=0;
   while(c.T!=0)
   {
      scanf("%d%d%d",&a[i].T,&a[i].M,&a[i].P);
      c.T=a[i].T;c.M=a[i].M;c.P=a[i].P;
      i++;
     }
   k=i;
   for(time=1;t!=0;time++)
   {
      t=0;
      for(i=0,j=0;i<n;i++)
      {
       if(NC[i]<=time)
        NC[i]=0;
       if(i==0&&NC[i]==0)
         b[j].d=i;
           else
         if(NC[i-1]!=0&&NC[i]==0)
           b[j].d=i;

       if(i==n-1&&NC[i]==0)
          b[j].c=i;
           else
             if(NC[i]!=0&&NC[i-1]==0)
          { b[j].c=i; j++; }
        printf("%d*(%d,%d)\n",j,b[j].d,b[j].c);
      }
       while(front!=rear||p==1)
     {
        front++;
        for(i=0,p=1;p==1;i++)
          if(b[i].c>=(*front).M)
          {
         for(q=b[i].d;q<b[i].c+b[i].d;q++)
           NC[q]=(*front).P+time;
         p=0;
           }
        if(p==1) front--;
       }
    if(time<=k)
    {
      if(a[time-1].T==time)
       for(i=0,p=1;p==1;i++){ printf("c=%d##M=%d",b[i].c,a[time-1].M);
        if(b[i].c>=a[time-1].M)
        {
           for(q=b[i].d;q<a[time-1].M+b[i].d;q++)
        { NC[q]=a[time-1].P+time;   printf("!");}
           p=0;
         }
       else

        if(rear<=&da[99] )
        {  rear++;
           (*rear).T=a[time-1].T; (*rear).M=a[time-1].M; (*rear).P=a[time-1].P;
           x++;  printf("(%d*%d*%d)\n",(*rear).T,(*rear).M,(*rear).P);
         }
        else
          printf("Can not put in!");
        }
       }
          for(i=0;i<n;i++)
       {   t+=NC[i]; printf("***%d***",NC[i]);}
       }
       /*clrscr(); */
    printf("%d\n%d\n",time,x);
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第十六届全国青少年信息学奥赛题(模拟系统内存分配)

回复列表（共14个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第十六届全国青少年信息学奥赛题(模拟系统内存分配)

回复列表 （共14个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共14个回复）