程序执行的时空测量方法研究

黎远松

（四川理工学院计算机学院，四川自贡643000）

程序执行的时空测量方法研究

黎远松

（四川理工学院计算机学院，四川自贡643000）

程序执行时所花费的时间和内存空间是评价一个程序性能优劣的一个重要指标。理论上，可以借助于数学这个强有力的工具估算出程序的时间复杂度和空间复杂度，然后用这两个标准来度量程序的效率；实际上，在源代码在线评测系统这样的实际系统中无法使用。文章对程序执行时所花费的时间和内存空间的测量方法进行大量深入的研究，基于DOS平台，提出了计时法，利用clock和coreleft测量程序执行的时间和空间；基于Windows平台，利用Get Process Times和Get Process MemoryInfo测量程序执行的时间和空间，在四川理工ACM中得到应用，实践证明这些方法正确、有效。

程序；时间；空间；测量；方法

在源代码在线评测系统的研究过程中发现，测量进程执行时所花费的时间和所占用的内存空间是一个亟待解决的重要问题。利用API函数Get Tick Count（）获取进程的执行时间［1］，在多任务环境里是不准确的，负载的变化对实验结果影响明显。

Windows 2000引入了新的进程控制原语——作业对象。作业对象是可以作为单个实体管理的一个或多个进程的集合。用户可以设置整个执行时间和处理器时间的分配、以及控制作业对象的调度选项［2］，但编程实现略显复杂。

针对这些问题，本文进行大量深入的研究，提出了以下适用不同环境的测量方法。

1 基于DOS平台的测量

1.1 运行时间的测量

函数clock（）返回程序开始运行时经过的时间，利用它测定运行时间，方法如下∶

t1=clock（）；

被测程序

t2=clock（）；

t3=t2-t1；

在虚拟机（16M，单核2.33Ghz，DOS7.1，BC31）中测量以下程序的实验数据见表1。

for（a=100；a＜200；a++）｛

for（b=100；b＜200；b++）｛

for（c=100；c＜200；c++）｛

d=711-a-b-c；

if（a*b*c*d==711000000）

｝｝｝

从表1中的time数据可以看出，被测程序的运行时间稳定在17 s。

由于DOS是单任务操作系统，被测程序受环境的影响极小，因此，测试结果变化极小。

DOS平台的测量方法是最基本的方法，测量的结果也是最容易理解的。但在多任务环境里，准确性难于保证［3-4］。

1.2 内存空间的测量

函数coreleft返回以前未用的堆空间的大小。只用在没有分配或释放对象时这个值才代表真正可用的内存大小。获得准确的RAM大小需要遍历堆空间，利用它测定未用的RAM内存，方法如下∶

r1=coreleft（）；

被测程序∶

r2=coreleft（）；

r3=r2-r1；

实验结果见表2。

从表2中的数据可以看出，被测程序malloc（1024）在堆空间中分配了1 KB的RAM内存，未用的RAM内存空间减少1 KB，正确，但是这种方法只能测定以前未用的堆空间的大小，第三组静态分配的内存用coreleft测量不出来，因此，具有很大的局限性。

2 基于Windows平台的测量

2.1 获取进程时间信息

选手程序执行时间的多少，是一个重要的评测指标［2，5-6］，这里利用API函数Get Process Times（）获取进程的执行时间，方法为∶

用父进程本身创建一个新进程（Create Process），获得pi.handle，然后等程序运行完毕以后调用Get Process Times得到需要的时间（用户模式与kernel模式）。

通过传递给Create Porcess的PROCESS_INFORMATION参数，创建进程Wait For Single Object（pi.h Process，INFINITE），然后再调用Get Process Times。最后利用File Time To System Time函数转成SYSTEMTIME，核心代码如下∶

BOOL ret=Create Process（argv［1］，NULL，NULL，NULL，TRUE，0，NULL，NULL，&si，&pi）；

//argv［1］是选手程序的文件名

a=Wait For Single Object（pi.h Process，INFINITE）；

//等待选手程序执行INFINITE

Get Process Times（pi.h Process，&Creation Time，& Exit Time，&Kernel Time，&User Time）；

File Time To System Time（&Kernel Time，&kt）；

File Time To System Time（&User Time，&ut）；

//时间格式转换

t=（ut.w Second+kt.w Second）*1000+ut.w Milliseconds+kt.w Milliseconds；//秒转换成毫秒

测试环境∶虚拟机，512 M，单核2.33 Ghz，Windows Server 2000，VC++6.0。实验结果见表3、表4。

从表4中的数据可以看出，利用函数GetProcess-Times（）来获取进程的执行时间，在多任务环境里是准确的，负载的变化对实验结果影响不明显。

2.2 获取进程内存信息

选手程序执行时占用内存的多少，是另一个重要的评测指标［7-9］，获取进程执行时所占用的内存信息比获取进程执行时所花费的时间要困难得多。本文用父进程本身创建一个新进程（Create Process），获得pi.handle，然后等程序运行完毕以后调用Get Process Memory-Info得到当前进程所使用的内存Working Set Size，单位是字节，核心代码如下∶

Get Process MemoryInfo（pi.h Process，&pmc，sizeof（pmc））；

//获取某一个进程的内存信息。

cout≪″|″≪t≪″|″≪pmc.Working Set Size/1024≪″|″；//把Byte转换KB

被测程序∶int x［1024］；int y［1024］；int z［1024］；

由表5可以看出，Get Process MemoryInfo能正确地测量出程序所使用的内存情况，分配单位为4KB。

需要强调的是，Get Process Times（）和Get Process MemoryInfo（）函数一定要位于Wait For Single Object（）函数之后，只有这样才能获取正确的信息。

3 结束语

基本DOS平台的测量方法简单、有效，在算法的事后分析时得到应用；基于Windows平台的测量方法已应用在理工ACM系统中，运行良好。对于运行时间和空间的评测和限制等，有待进一步研究和解决。

［1］王腾'药单霖.Online Judge系统的设计开发［J］.计算机应用与软件'2006(12）:78-83.

［2］(美）Jeffrey Richter.WINDOWS核心编程［M］.北京:机械工业出版社'2008.

［3］张浩斌.基于开放式云平台的开源在线评测系统设计与实现［J］.计算机科学'2012'39(11A）:339-346.

［4］李臣龙'鲍广喜.基于WAMP的在线评测系统设计与实现［J］.电脑编程技巧与维护'2013'15:64-75.

［5］孟繁军'刘东升'张丽萍'等.程序设计基础教学策略的实践研究［J］.内蒙古师范大学学报:教育科学版' 2013(3）:126-129.

［6］M ickey Williams.Windows 2000编程技术内幕［M］.北京:机械工业出版社'1999.

［7］唐子蛟'项菲'符长友.电子投票系统结果计算的误差源分析［J］.四川理工学院学报:自然科学版'2013' 26(4）:52-55.

［8］王晓'刘凤仙'李琦.GIS与三维可视化在校园地下管网线管理中的应用［J］.四川理工学院学报:自然科学版'2013'26(3）:46-50.

［9］M ihail B.The U-Kenmotsu Hypersurfaces Axiom and Six-Dimensional Hermitian Submanifolds of cayley algebra［J］.Journal of Sichuan University of Science& Engineering(Natural Science Edition）'2013'Vol.26No.3: 1-6.

Research on Approaches to Measure Program Execution Time and Space

LIYuansong
（School of Computer Science，Sichuan University of Science&Engineering，Zigong 643000，China）

Time and space needed for process are two essentialmeasures of our algorithm.In theory，we calculate the time complexity and space complexity of the algorithm with the aid ofmathematics firstly，and thenmeasure the efficiency of the algorithm with these two standards.In fact，the time complexity and space complexity of the algorithm cannot be used in the actual system such as online judge system.Approaches to measure process execution time and space were deeply researched for this problem and timing based on DOSwas proposed，which measures program execution timing and memory with clock and coreleft.Base on windows with get process times and get processmemory Info，it had been applied in the SUSE ACM correctly and effectively.

program；time；measure；approach

TP393.6

A

1673-1549（2014）01-0053-03

10.11863/j.suse.2014.01.14

2013-10-09

四川省教育厅科研项目（13ZAO125）；软件工程专业综合改革项目（ZG-1202）

黎远松（1970-），男，重庆开县人，副教授，硕士，主要从事源代码在线评测系统方面的研究，（E-mail）lys700620@yeah.net