从零开始的代码评测系统设计与实践(三) —— 运行结果处理

0x00 获取运行结果

上两篇文章,我介绍了判题机是如何管理进程,并如何限制进程的资源使用。目标程序运行完毕退出后,我们的判题机进程将从等待中唤醒,进行运行数据的收集工作。此时,判题机能够作出判断的状态分别有AC(暂时)、TLE、MLE、RE和OLE。

从进程篇我们可以了解到,WIFSIGNALED(status)可以判定进程是因为收到系统信号而终止的。此时,再使用WTERMSIG(status)获取到进程的信号,根据信号的不同来判定运行状态。

0x01 获取时间、内存使用情况

首先,我们来了解rusage结构体的定义:

struct rusage {
    struct timeval ru_utime; /* user time used   用户态使用的时间 */
    struct timeval ru_stime; /* system time used 内核态使用的时间 */
    long   ru_maxrss;        /* maximum resident set size 最大驻留集大小 */
    long   ru_ixrss;         /* integral shared memory size 全部共享内存大小 */
    long   ru_idrss;         /* integral unshared data size 全部非共享内存大小*/
    long   ru_isrss;         /* integral unshared stack size */
    long   ru_minflt;        /* page reclaims 页回收 */
    long   ru_majflt;        /* page faults  页失效 */
    long   ru_nswap;         /* swaps 交换区 */
    long   ru_inblock;       /* block input operations */
    long   ru_oublock;       /* block output operations */
    long   ru_msgsnd;        /* messages sent */
    long   ru_msgrcv;        /* messages received */
    long   ru_nsignals;      /* signals received */
    long   ru_nvcsw;         /* voluntary context switches */
    long   ru_nivcsw;        /* involuntary context switches */
};

其中,计算时间和内存占用的算法如下所示:

time_used = ru.ru_utime.tv_sec * 1000
            + ru.ru_utime.tv_usec / 1000
            + ru.ru_stime.tv_sec * 1000
            + ru.ru_stime.tv_usec / 1000;    
  
memory_used = ru.ru_minflt * (sysconf(_SC_PAGESIZE) / 1024);
// memory_used = ru.ru_maxrss;

运行时间为内核态+用户态的时间之和,内存的话可以有两种方式判断:判断页回收的数量ru_minflt或者直接获取最大驻留值ru_maxrss。你可以通过sysconf(_SC_PAGESIZE)获取到系统内存每个页的大小,单位是字节。

0x02 各种状态的判定

当信号SIGALRMSIGVTALRMSIGXCPUSIGPROF信号被触发时,我们可以得知进程因为超时或者触发时钟而被终止,因此可以判定为TLE。如果你不放心,还可以在判定为正常退出后,再次判断time_used是否大于Time Limit。

当信号SIGSEGV被触发时,我们可以得知这是由于内存错误引发的。但并不能直接认为就是MLE。当你进行一些错误的操作,如除0操作、数组越界等,也会触发这个信号,此时应该被判定为RE。如果memory_used大于 Memory Limit,我们才有理由相信它是超过了内存资源的限制。

当信号SIGKILL被触发时,可能是MLE,也可能是TLE(你可以通过time_used判断)。而信号SIGXFSZ被触发时,则直接判定为OLE。

理论上判定的优先级为:TLE > MLE, OLE > RE

上述错误都没有发生的情况下,我们便可以认为,程序按照预期顺利执行并结束了,接下来就需要对它的输出进行分析,判断输出结果是否正确。

0x03 输出结果分析

在进程篇里,我们将用户输出的答案存放在了/tmp/user.out文件中。在被测程序运行结束后,如果没有触发上述的错误信息,则判题机将启动对用户输出数据的检查工作。

数据检查主要思路就是同时读取用户输出user.out和答案输出answer.out,逐一比较每个字符是否一致。

等等!我们注意到,在OJ中有一种错误叫格式错误(PE)。这种错误比较特别:除字符“空格”、\r、\n和\t的数量或位置不同以外,其他的内容均与答案匹配。

我们先定义两个游标left和right分别表示用户输出和答案输出,然后执行循环逐字比较。当某个游标遇到上述“格式字符”时,先使用一个子循环推动游标后移,直到遇到不可忽略的字符为止。两个游标在每次比较前都要做完这个操作,然后再进行,直到任意游标越界(超出了数组长度),主循环结束。如果逐字比较过程中任意一个字符不匹配,则直接返回WA。

当上述循环结束后,如果left == right,则说明答案内容完全一致,返回AC;否则,返回格式错误PE。

然而你以为到这就结束了吗?实际使用的时候,我们遇到了一个新的问题。来看看这组数据:

用户:2\r\n4\n\r6\r\t8
答案:2\r\n4\r\n6\r\n8

很不幸的是,上述检查会忽略“格式字符”的顺序,并根据left==right判定其为AC。这不是我们想要的结果。当时为了解决这个问题,一时脑子发热的我,居然想用CRC去校验文本,简直就是大炮打苍蝇。解决办法很简单,当第一次检查通过以后,我们再执行一次严格检查,对每个字符进行比较,即可得知是AC还是PE。

检查数据相关代码请访问我的开源项目:
https://github.com/LanceLRQ/deer-executor/blob/master/checker.go (Go语言)

0x04 小结

到这里,我们基本上了解了一个判题机内核最基础的工作原理。这是万里之行中迈出的第一步,也是非常重要的一步。下一篇,我会对特殊评测(Special Judge)的工作原理进行一些讲解。

TLE:Time Limit Exceed 超出时间限制
MLE:Memory Limit Exceed 超出内存限制
OLE:Output Limit Exceed 输出超出限制
RE: Runtime Error 运行时错误
WA:Wrong Answer 答案错误
PE:Presentation Error 格式错误
AC:Accepted 答案通过

OJ术语说明