0x00 背景

传统的评测模式下,判题机按照固定的顺序执行:运行被测程序,获取运行结果,比对结果数据。由于是严格比较,结果数据和答案属于有任意一个字节(除常用格式字符外)不匹配,都将被判定为WA。

有些时候,这种方式太过于苛刻。在涉及到浮点数运算的题目,如计算圆的面积时,我们不得不面对计算结果的精度误差,这将导致原本正确的程序,被判定为WA,显然这不符合我们的逾期。

在特殊评测功能还没能设计开发出来之前,我们通常的解决办法是固定使用一种数据类型出题,比如要求选手使用double来存储浮点数,这样可以确保最终打印的小数精度和我们设定的答案一致。

我们知道,数据检查工具是判题机的一部分,那么是否能让判题机支持调用出题者编写的数据检查工具呢?

0x01 特殊评测

特殊评测中,判题机在数据检查阶段,将控制权交给出题者预定好的数据检查工具。出题者需要按照判题机的文档编写对应的程序,从运行参数列表里接收判题机传过来的输入数据、用户输出数据、答案数据和日志文件等参数,并进行读写、判定,必要时还可以记录日志。所有工作完成后,返回特定的退出代码。判题机接收到将以退出代码作为判题结果。

当然,作为判题机,也要监控这个检查工具的执行情况。如果长时间没有反馈,或者返回了错误的信息,需要及时进行错误标记,并通知出题者等。特殊评测的实现比较简单,这里不再赘述了,需要深入了解,请直接阅读判题机源码即可。

0x02 交互判题

交互式判题是一种新颖的特殊评测形式,它支持特判程序和选手的程序进行互动。

例如,我们可以出一题猜数字游戏:特判程序随机在[0, 1000]内生成一个数,要求被测程序在10次询问内,告知特判程序这个数是什么。每次询问,判题机会告诉你是“>”、“<”还是“=”。如果10次内没有猜到这个数,那么特判程序会直接返回WA,表示被测程序错误了。

上述问题相信大家都知道怎么解答吧。从技术的角度来看,在这个“猜数字”的过程中,特判程序和被测程序之间建立了一个“数据通道”(标准输入输出流),特判程序只要生成一个数,然后通过scanf获取被测程序发来的数,比对后返回结果。比对成功则返回AC,超过10次错误,直接返回WA。而判题机,只需要作为一个旁观者,无须参与实际的数据判定。但如果特判程序结束了,无论被测程序是否执行完毕,都应该直接结束掉。

// 特判程序

#include <stdio.h>
#define AC 0
#define WA 4

int main() {
    int ans = rand() % 1000;
    int ques = 0;
    int err = 0;
    while(~scanf("%d", &ques) && err < 10) {
        if (ques < ans ) {
            printf("<\n");
        } else if (ques > ans ) {
            printf(">\n");
        } else {
            printf("=\n");
            return AC;
        }
    }
    return WA;
}
// 选手程序

#include <stdio.h>
int main() {
    int left = 0, right = 1000, half = (left + right) / 2;
    char ans;
    printf("%d", half);
    fflush(stdout);
    while(~scanf("%c%*c", &ans)) {
        if (ans == '<') {
            right = half;
        } else if (ans == '>') {
            left = half;
        } else {
            return half;
        }
        half = (left + right) / 2;
        printf("%d", half);
        fflush(stdout);
    }
}

下面来讲这个比较有意思的功能是如何实现的。

0x03 数据重定向

要想实现交互判题功能,我们需要对特判程序和被测程序的输入输出流进行重定向。在Linux中,进程之间进行通讯(IPC)的方式常见的有两种:一种是使用pipe管道,另外一种是sockerpair。前者是半双工的,即只能一个发送一个接收;后者是全双工的,可以同时进行发送和接收工作。我们目前只讨论第一种,即pipe方式。

// int pipe(int pipefd[2]); 

int judger[2], program[2];
pipe(judger);   // 特判程序用于读取的管道
pipe(program);  // 被测程序用于读取的管道

pipe函数将会把参数中列表的值分别设置为对应的文件描述符,其中fd[0]为读取,fd[1]为写入。这个很关键,它决定了数据的流向,即fd[1] —> fd[0]。然后,我们就可以拿出之前的dup2函数,将对应的文件描述符指向对应的输入输出流:

// 被测程序
dup2(program[0], STDIN_FILENO);
dup2(judger[1], STDOUT_FILENO);
// 特判程序
dup2(fdjudge[0], STDIN_FILENO);
dup2(program[1], STDOUT_FILENO);

// 数据流向:
// 被测程序 --judger--> 特判程序
// 被测程序 <--program-- 特判程序

这样,我们就完成了交互评测中最核心的逻辑。当然,除了这些核心逻辑,判题机依然需要监控程序的运行状况。因为特判程序和被测程序都是不稳定的,并不知道谁会出错,也难免存在卡住的情况,都需要进行及时的处理。

0x04 更佳的实践

通常情况下,编写特殊评测、交互评测检查器,对于出题者来说无疑是一项并不容易的工作,出题者需要全方位考虑到问题可能发生的各种情况、数据是否符合题目要求等,还得保证接收到一些奇怪的数据时尽量不崩溃。

在我个人的认知里,交互评测功能应该是出自于著名的ACM竞赛网站CodeForces,而该网站推出了一款很强大的评测辅助工具:Testlib。该工具最早是Pascal语言开发的,后用C++重写。它引入了Generator、Validator、Interactor和Checker四个概念,为了便于理解,我将它们分别描述为:输入数据生成器、输入数据校验器、交互评测检查器、普通特判检查器。

它们可以让出题人更加专注于出题,不会被繁琐的校验工作难倒。这里只是简单的描述一下这个工具,如果你需要开发一套完整的判题系统,我非常推荐你尝试支持这套工具的使用,提前代表出题者感谢你的支持。

支持这套工具并不难,你只需要支持出题者上传相关的程序代码,将代码和testlib.h一同编译并运行即可。对于判题机内核,只需要关心interactor和checker的运行和输出。对于OJ网站(出题),能调用shell执行Generator和Validator即可。具体实现了哪些功能,你可以打开cf的polygon网站了解一下。

0x05 畅想未来

判题这块核心的内容讲的差不多了。总的来说,原理并不复杂,往往开发实现的时候会遇到很多的坑,这是必经的过程,不必惊慌。

在人工智能技术不断突破发展的今天,我们完全可以利用这些技术打造一个更加智能的判题程序。这是我设计和开发WeJudge系统的时候,听过最多的建议。因为WeJudge本身面向的群体是学生、教师团体,而不是ACM的参赛者,学生最需要的是学习代码实现的思路、代码风格,注重过程,而不是仅仅局限在精确无误的数据上。严苛的评测机制本身会对这学生带来心理上的压力,也对教师造成的许多不便,毕竟很多时候出现的莫名其妙的问题,老师也难以向学生解答。

总之,在原有的基础上进行突破和超越,是每一位开发者所追求的共同目标。

非常欢迎有想法的你参与到开源判题机的建设上来。

参考和引用:

Testlib中文简介:https://oi-wiki.org/tools/testlib/
Testlib英文博客:https://codeforces.com/testlib
致谢项目:https://github.com/dojiong/Lo-runner
我开发的判题内核deer-executor:https://github.com/LanceLRQ/deer-executor

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术语说明

0x00 资源占用

一个完整的判题机核心,不可避免要支持程序的资源占用判定。我们常以两个维度来判定一个程序的优劣,时间维度和空间维度。在ACM-ICPC比赛里,通常每道题目都有一个期望的最差运行时间,和最大内存占用。如果你的程序算法效率足够高,便可以很快的运行完某个测试数据;如果你的算法效率不够优,也许还可以通过使用内存来优化,但难免会造成内存占用。

一旦程序超出了预期,如运行过慢、陷入了死循环或内存占用太多,判题机核心的工作就是结束掉它,并收集它的信息,再给出相关的出错提示。

从上一节我们可以了解到,wait4()函数可以返回一个rusage结构体,我们可以完成对它信息的收集工作。那么问题来了,如果程序陷入了死循环,判题机又是如何知道的呢?

0x01 限制资源使用

Linux内核为我们提供了一个资源限制函数:setrlimit

struct rlimit {
  rlim_t rlim_cur;  //soft limit
  rlim_t rlim_max;  //hard limit
};

int setrlimit(int resource, const struct rlimit *rlim);

并为resource参数定义了多个常量,判题机常用的如下:

  • RLIMIT_AS  进程的最大虚内存空间,字节为单位。
  • RLIMIT_CPU  最大允许的CPU使用时间,秒为单位。当进程达到软限制,内核将给其发送SIGXCPU信号,这一信号的默认行为是终止进程的执行。然而,可以捕捉信号,处理句柄可将控制返回给主程序。如果进程继续耗费CPU时间,核心会以每秒一次的频率给其发送SIGXCPU信号,直到达到硬限制,那时将给进程发送 SIGKILL信号终止其执行。
  • RLIMIT_DATA  进程数据段的最大值。
  • RLIMIT_FSIZE  进程可建立的文件的最大长度。如果进程试图超出这一限制时,核心会给其发送SIGXFSZ信号,默认情况下将终止进程的执行。
  • RLIMIT_STACK  最大的进程堆栈,以字节为单位。

第二个参数传入一个rlimit结构体,其中rlim_cur表示软限制,rlim_max表示硬限制。软限制可以由被限制的程序自行修改, 修改的值不可超过硬限制。

你可以想象成你的蚂蚁花呗额度,假如你有1000元的额度,你可以在0-1000元的范围内调整自由额度,但不能超过1000元,因为花呗给你分配了最高1000元的额度。

下面,将详细的说明如何使用这个参数

0x02 时间限制

需要限制程序的运行时间,可以使用RLIMIT_CPU常量定义程序可用的CPU时间长度。当程序运行的CPU时间超过限制时,系统将会向程序发送SIGXCPU信号。这时候我们就可以判定该程序超过了时间显示,判题机需要报TLE错误。

struct rlimit rl;
rl.rlim_cur = 1;
rl.rlim_max = rl.rlim_cur + 1;
setrlimit(RLIMIT_CPU, rl);

在实际使用的过程中,这种限制存在一些问题。当用户代码里使用sleep()的时候,因为进程处于休眠状态,并不占用CPU资源,因此并不能触发时间限制。后面的内容将会就此情况进行讨论。

另外要注意的是,当目标程序TLE的时候,通过rusage获取到的CPU时间并不是绝对精确的,可能会偏移正负数个毫秒,这是正常的。

0x03 内存限制

需要限制内存的占用,需要限制RLIMIT_AS、RLIMIT_DATA和RLIMIT_STACK。

其中,RLIMIT_AS为虚拟内存占用,可以设置为 RLIMIT_DATA + RLIMIT_STACK 的总和。这个限制不是必须的。

而RLIMIT_DATA一般是题目限定的内存值,单位是KB。

如C语言在定义全局变量的时候,事实上是定义在栈上的。RLIMIT_STACK可以限制栈的大小,你可以将它设置为一个固定值,或者按题目限定为准。

#include <stdio.h>
int a[1000];      // 栈
int main() {
    int b[1000];  // 堆
} 

当内存超过系统限制后,你将会捕捉到SIGSEGV信号。因为RE也可能触发SIGSEGV信号,需要通过rusage判断内存是否超出设定值。

0x04 文件访问限制

除了常见的TLE、MLE,还有一个不常见的状态叫做OLE。通常情况下,为了减轻服务器存储压力,我们会限制程序输出的数据的大小;某些情况下,一些未知的死循环可能造成一瞬间产生数百MB至数GB不等的文件,这些数据是无意义的。

使用RLIMIT_FSIZE,可以限制文件大小,参数的单位是Bytes。当限制被触发时,将收到系统发出的SIGXFSZ信号,后程序将被结束。

另外,OLE的判定条件不仅仅是SIGXFSZ。如果程序输出了两倍以上(含)于参考答案的数据,也会被认为是OLE。

0x05 实际使用中遇到的问题

也许细心的你发现了一个问题,RLIMIT_CPU只能精确到秒。如果一个题目的时间限制为1500ms,就无法实现了。

我在开发deer-executor判题机核心时,在解决sleep()问题上采用系统的定时器函数setitimer(ITIMER_REAL)来触发一个闹钟信号SIGALRM,强制结束掉进程。由于这个定时器使用的是真实的系统时间,因此可以准确的在我想要的时间内结束掉程序。(但我依然觉得这并不是一个最优的办法,如果你有更好的办法,欢迎和我分享讨论!)。撰写本文时,我重新翻阅了相关的文档,发现setitimer函数提供了三个参数可以使用:

  • ITIMER_REAL:计时器的值实时递减,发送的信号是SIGALRM
  • TIMER_VIRTUAL:进程执行(用户态)时递减计时器的值,发送的信号是SIGVTALRM
  • ITIMER_PROF:进程(用户态)和系统(内核态)执行时都递减计时器的值,发送的信号是SIGPROF

也就是说,我们可以用setitimer(ITIMER_PROF)来更加精确的触发时钟中断(通常情况下内核态会进行一些I/O操作,也会被认为是解题时间,因此不用TIMER_VIRTUAL参数),问题迎刃而解。setitimer函数的定义为:

struct itimerval {
    struct timeval it_interval;  // 触发间隔
    struct timeval it_value;     // 第一次触发时间 
};
struct timeval {
    long tv_sec;    // 单位:秒
    long tv_usec;   // 单位:微秒 (1μs == 1,000ms == 1,000,000s)
};
int setitimer(int which, const struct itimerval *value, struct itimerval *ovalue);

事实上,我们可以采取双重限制的办法:

假设当前题目的时间限制为tl = 1500 (ms),将setrlimit(RLIMIT_CPU)的时间设置为:

rlim_cur = rlim_max = ceil(tl / 1000)

setitimer(ITIMER_PROF)的时间设置为:

tv_sec = floor(tl / 1000);
tv_usec = (tl % 1000) * 1000;

即可实现更为精确的定时功能。

另外,上文提到如果用户在程序中执行sleep()函数,则无论是RLIMIT_CPU还是ITIMER_PROF,在sleep结束前都是不会被触发的。为了对抗这种行为,简单的办法是再增加定时器ITIMER_REAL,这个计时器是按真实的时间触发的,可以直接在超时后的结束掉程序。在多线程并行评测的情况下,这个时间可以被初略的设置为:

ceil(并发数 / CPU 核数) * TimeLimit

当然可以根据实际情况调整。但我始终认为这不是一个最优的办法,如果并行执行多个任务,则不能准确的计算出最佳的时间宽度。如果你有更好的办法,如阻止用户调用sleep等,欢迎和我一起讨论分享。

引用

https://linux.die.net/man/3/setrlimit
https://linux.die.net/man/3/getrlimit
https://linux.die.net/man/3/setitimer
https://www.cnblogs.com/niocai/archive/2012/04/01/2428128.html