文章 56
评论 98
浏览 271517
ACM刷题之-内存分配(POJ-1193 )

ACM刷题之-内存分配(POJ-1193 )

摘要: 内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。 经典的内存分配过程是这样进行的: 1. 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从 0 开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址 i 开始的 s 个连续的内存单元称为首地址为 i 长度为 s 的地址片。 2. 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻 T,需要内存单元数 M 及运行时间 P。在运行时间 P 内(即 T 时刻开始,T+P 时刻结束),这 M 个被占用的内存单元不能再被其他进程使用。 3、假设在 T 时刻有一个进程申请 M 个单元,且运行时间为 P,则: 1. 若 T 时刻。..

算法分析:

  1. 维护一个进程的链表,每个节点存有进程开始时间 t,进程运行时间 p, 在内存中的首地址 s,占用内存大小 m,和下一节点指针。

  2. 维护一个队列,表示还没有空间运行的进程。

  3. 维护一个释放内存的最早时间 nexttime,每读入一个新进程的时候,若进程开始时间不小于 nexttime,表示有进程在这之前已结束(可能不止一个),将其从链表删除,并循环检测队首进程是否有空间运行,如果有,就将其先加入(注意开始时间要设为止刻的 nexttime,而不是读入的值了,最后将新读入的进程加入链表,或加入队列。

对应的代码:

while (a[pos].t>=nexttime)  free_and_pop();   
if (!alloc(pos,a[pos].t)) { Q[tail++]=pos; }   
else nexttime=_cpp_min(nexttime,a[pos].t+a[pos].p);   
//删除结束的进程,加入队列进程,更新nexttime   
void free_and_pop()   
{   
       int pre=root,temp=inf;   
       for (int i=root;i;)   
       {   
              if (a[i].t+a[i].p==nexttime)   
              {   
                     if (i==root)    
                     {   
                            root=a[root].next;   
                            i=root;   
                     }   
                     else    
                     {   
                            i=a[pre].next=a[i].next;   
                     }   
              }   
              else    
              {   
                     if (a[i].t+a[i].p<temp) temp=a[i].t+a[i].p;   
                     pre=i;   
                     i=a[i].next;   
              }   
       }   
       while (head<tail)    
              if (!alloc(Q[head],nexttime)) break;    
              else { temp=_cpp_min(temp,a[Q[head]].t+a[Q[head]].p);++head;}   
              
              nexttime=temp;   
              
}

如此往复。。。读入结束后,再对残余的队列和链表处理完,算出结果,完毕。

程序源码(C++):

#include <iostream>   
#include <algorithm>   
#include <cmath>   
#include <vector>   
using namespace std;   
const int inf = 1<<28;   
int n,m;   
struct node   
{   
       int m,t,p,s,next;   
}a[10000];   
 
int Q[10000],head,tail,c,root,nexttime;   
 
//分配内存(插入链表)   
bool alloc(int pos,int t)   
{   
       if (!root || a[root].s-0>=a[pos].m)   
       {   
              a[pos].next=root;   
              root=pos;   
              a[pos].t=t;   
              a[pos].s=0;   
              return true ;   
       }   
       int i;   
       for (i=root;a[i].next!=0;i=a[i].next)   
       {   
              if (a[i].s+a[i].m-1+a[pos].m < a[a[i].next].s)   
              {   
            a[pos].next=a[i].next;   
            a[i].next=pos;   
            a[pos].s=a[i].s+a[i].m;   
            a[pos].t=t;   
            return true;   
              }   
       }   
       if (i && n-(a[i].s+a[i].m) >= a[pos].m)   
       {   
              a[i].next=pos;   
              a[pos].next=0;   
              a[pos].s=a[i].s+a[i].m;   
              a[pos].t=t;   
              return true;   
       }   
       return false;   
}   
//删除结束的进程,加入队列进程,更新nexttime   
void free_and_pop()   
{   
       int pre=root,temp=inf;   
       for (int i=root;i;)   
       {   
              if (a[i].t+a[i].p==nexttime)   
              {   
                     if (i==root)    
                     {   
                            root=a[root].next;   
                            i=root;   
                     }   
                     else    
                     {   
                            i=a[pre].next=a[i].next;   
                     }   
              }   
              else    
              {   
                     if (a[i].t+a[i].p<temp) temp=a[i].t+a[i].p;   
                     pre=i;   
                     i=a[i].next;   
              }   
       }   
       while (head<tail)    
              if (!alloc(Q[head],nexttime)) break;    
              else { temp=min(temp,a[Q[head]].t+a[Q[head]].p);++head;}   
              
              nexttime=temp;   
              
}   
//插入新读入的进程   
void insert(int pos)   
{   
       while (a[pos].t>=nexttime)  free_and_pop();   
       if (!alloc(pos,a[pos].t)) { Q[tail++]=pos; }   
       else nexttime=min(nexttime,a[pos].t+a[pos].p);   
}   
//处理最后的队列中的进程   
int SolveRemain()   
{   
    while (head<tail)   
    {   
        free_and_pop();   
    }   
    int lasttime=nexttime;   
    for (int i=root;i;i=a[i].next)   
    {   
        lasttime=max(lasttime,a[i].t+a[i].p);   
    }   
    return lasttime;   
}   
 
int main()   
{   
       cin>>n;
    head=tail=c=root=0;   
    nexttime=inf;   
    for (int i=1;;i++)   
    {   
              cin>>a[i].t>>a[i].m>>a[i].p;
        if (a[i].t==0 && a[i].m==0 && a[i].p==0) break;   
        insert(i);   
    }   
    cout<<SolveRemain()<<endl<<tail<<endl;   
    system("pause");   
    return 0;   
}


微信公众号

潘建锋

关于版权和转载

本文由 潘建锋 创作,采用 署名 4.0 国际 (CC BY 4.0) 国际许可协议进行授权。
本站文章除注明转载/出处外,均为本站原创或翻译,转载时请务必署名,否则,本人将保留一切追究责任的权利。
署名 4.0 国际 (CC BY 4.0)

转载规范

标题:ACM刷题之-内存分配(POJ-1193 )
作者:潘建锋
原文:https://taohuawu.club/POJ-1193

关于留言和评论

如果您对本文《ACM刷题之-内存分配(POJ-1193 )》的内容有任何疑问、补充或纠错,欢迎在下面的评论系统中留言,与作者一起交流进步,谢谢!(~ ̄▽ ̄)~

鲜衣怒马提银枪,一日看尽长安花,此间少年。