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

2020年8月4日系列从零开始的代码评测系统设计与实践

WeJudgeOnline JudgeOJACM-ICPC

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 各种状态的判定

当信号 SIGALRM、SIGVTALRM、SIGXCPU 或 SIGPROF 信号被触发时，我们可以得知进程因为超时或者触发时钟而被终止，因此可以判定为 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 术语说明