a071. NOI1999 Day2.3.内存分配
標籤 :
通過比率 : 22人/26人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 01:50

內容
内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。
经典的内存分配过程是这样进行的:
1. 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从0开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
2. 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻T,需要内存单元数M及运行时间P。在运行时间P内(即T时刻开始,T+P时刻结束),这M个被占用的内存单元不能再被其他进程使用。
3、假设在T时刻有一个进程申请M个单元,且运行时间为P,则:
1. 若T时刻内存中存在长度为M的空闲地址片,则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片,则系统将首地址最小的那个空闲地址片分配给该进程。
2. 如果T时刻不存在长度为M的空闲地址片,则该进程被放入一个等待队列。对于处于等待队列队头的进程,只要在任一时刻,存在长度为M的空闲地址片,系统马上将该进程取出队列,并为它分配内存单元。注意,在进行内存分配处理过程中,处于等待队列队头的进程的处理优先级最高,队列中的其它进程不能先于队头进程被处理。
现在给出一系列描述进程的数据,请编写一程序模拟系统分配内存的过程。
輸入說明
第一行是一个数N,表示总内存单元数(即地址范围从0到N-1)。从第二行开始每行描述一个进程的三个整数T、M、P(M <= N)。最后一行用三个0表示结束。
数据已按T从小到大排序。
输入文件最多10000行,且所有数据都小于10^9。
输入文件中同一行相邻两项之间用一个或多个空格隔开。
輸出說明
包括2行。
第一行是全部进程都运行完毕的时刻。
第二行是被放入过等待队列的进程总数。
範例輸入 #1
10
1 3 10
2 4 3
3 4 4
4 1 4
5 3 4
0 0 0
範例輸出 #1
12
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
提示 :

T

内存占用情况

进程事件

0

1

2

3

4

5

6

7

8

9

进程A申请空间(M=3, P=10)<成功>

1

A

 

 

 

 

 

 

 

2

A

B

 

 

 

进程B申请空间(M=4, P=3)<成功>

3

A

B

 

 

 

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

4

A

B

D

 

 

进程D申请空间(M=1, P=4)<成功>

5

A

C

D

 

 

进程B结束,释放空间

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

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

6

A

C

D

 

 

 

7

A

C

D

 

 

 

8

A

C

E

进程D结束,释放空间

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

9

A

 

 

 

 

E

进程C结束,释放空间

10

A

 

 

 

 

E

 

11

 

 

 

 

 

 

 

E

进程A结束,释放空间

12

 

 

 

 

 

 

 

 

 

 

进程E结束,释放空间

標籤:
出處:
NOI1999Day2第三题 [管理者: liouzhou_101 (王启圣) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」