杭州交通信息网超好听的耶稣歌曲排行:如何解决"模拟内存分配问题"
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/06 05:37:12
内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。经典的内存分配过程是这样进行的：
内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从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结束，释放空间
请高手帮忙,解决一下这个问题,研究了好长时间都没有结果...
TJU1201
program tju1201;
const
maxprogs=10001;
var
heap:array[0..maxprogs]of record fin:longint;pchain:word;end;
chain:array[0..maxprogs]of record left,right:longint;pheap,pre,next:word;end;
wait:array[1..maxprogs]of record mem,time:longint;end;
h,n,a,b,c,f,r,now,p:longint;
function where(mem:longint):word;
begin
where:=0;
while (chain[where].next>0) and
(chain[chain[where].next].left-chain[where].right<mem) do
where:=chain[where].next;
end;
procedure ins(where,fintime,mem:longint);
var
p,q:word;
begin
inc(n);
with chain[n] do begin
left:=chain[where].right;right:=left+mem;
pre:=where;next:=chain[where].next;
end;
chain[where].next:=n;chain[chain[n].next].pre:=n;
inc(h);p:=h;q:=p shr 1;
while (p>1) and (fintime<heap[q].fin) do begin
heap[p]:=heap[q];
chain[heap[p].pchain].pheap:=p;
p:=q;q:=p shr 1;
end;
with heap[p] do begin fin:=fintime;pchain:=n;end;
chain[n].pheap:=p;
end;
function pop:longint;
var
p,l,r:word;
begin
pop:=heap[1].fin;
p:=heap[1].pchain;chain[chain[p].pre].next:=chain[p].next;chain[chain[p].next].pre:=chain[p].pre;
p:=1;l:=2;r:=3;
repeat
if (r<h) and (heap[h].fin>heap[r].fin) and (heap[r].fin<heap[l].fin) then begin
heap[p]:=heap[r];
chain[heap[p].pchain].pheap:=p;
p:=r;
end
else if (l<h) and (heap[h].fin>heap[l].fin) then begin
heap[p]:=heap[l];
chain[heap[p].pchain].pheap:=p;
p:=l;
end
else
break;
l:=p*2;r:=l+1;
until false;
heap[p]:=heap[h];chain[heap[p].pchain].pheap:=p;
dec(h);
end;
begin
repeat
h:=1;
with heap[1] do begin fin:=maxlongint;pchain:=1;end;
n:=1;
with chain[0] do begin right:=0;next:=1;end;
with chain[1] do begin read(left);pheap:=1;pre:=0;next:=0;end;
f:=1;r:=0;
repeat
read(a,b,c);
if b=0 then a:=maxlongint-1;
while heap[1].fin<=a do begin
repeat now:=pop;until heap[1].fin>now;
while f<=r do begin
p:=where(wait[f].mem);
if chain[p].next=0 then break;
ins(p,now+wait[f].time,wait[f].mem);
inc(f);
end;
end;
if b=0 then break;
p:=where(b);
if chain[p].next>0 then
ins(p,a+c,b)
else begin
inc(r);wait[r].mem:=b;wait[r].time:=c;
end;
until false;
writeln(now);writeln(r);
until seekeof;
end.