从零开始的代码评测系统设计与实践(二) —— 资源占用与限制

Posted by LanceLRQ on Monday, August 3, 2020

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

CATALOG