从零开始的代码评测系统设计与实践(一) —— 进程和输入输出

Posted by LanceLRQ on Monday, July 27, 2020

不过是去便利店买了个泡面，居然穿越到了异世界。一次意外的去世，发现自己拥有了死亡后读档的技能…原来，世界线分支交错复杂，不同的世界线里发生着不同的故事…

0x00 进程

进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在早期面向进程设计的计算机结构中，进程是程序的基本执行实体；在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。

来自百度百科词条

进程就像是一个个世界线的分支，各自发生着不同的故事，但又是相互关联的。

我们运行的每一个程序，系统都会为它创建一个进程，然后分配内存和堆栈，装入程序的指令，并执行它们。如果我们要在自己的程序里调用其他的程序，就需要向系统申请创建子进程，重复执行上述的初始化操作。那么进程应该如何创建呢？

0x01 创建进程

在Linux的世界里，我们可以利用fork()函数或者vfork()函数来创建新的子进程。代码如下所示：

pid_t child = fork();
if (child == 0) {
    // 子进程
} else {
    // 父进程继续执行
}

有趣的事情来了，父子进程居然通过一个if条件区分了！因为子进程拥有和父进程的一样的数据空间、堆和栈等，并以副本的形式存在。代码从fork()开始，被一分为二，分别在不同的进程继续执行。其中，fork()的返回值child变量，在子进程中获取到的是0，而在父进程获取到的是子进程PID。

0x02 进程调度

为了更好的理解进程的工作原理，先来简单的了解一下系统调度进程的方式。

现代操作系统可以同时运行多个程序，但从操作系统的视角来看，CPU是个菜鸡，一次只能执行一个程序（如单核CPU）。那如果要同时运行程序怎么办？没错，换多核处理器！EPYC 7742了解一下？64核128线程…

你的钱包还好吗？

显然，简单的堆硬件是不合理的。操作系统需要解决的问题便是，如何让多个程序同时有序的执行，但又要让用户觉得他们是同时执行。于是操作系统引入了一个调度概念：

  • 就绪 ：程序等待系统唤醒 。(你在这待着别动，我去给你买橘子。)
  • 执行：程序正常执行。(动，自己动，使劲儿动！)
  • 阻塞：程序由于自身I/O需要，将控制权交出给I/O设备，等待返回。

就绪状态时，进程都是不会占用CPU的，处于休眠状态，等待操作系统唤醒。操作系统会对时间进行划分成一个个区间，称作时间片。当某个进程获得时间片后，操作系统就会唤醒它，进入执行状态；时间片用完了，系统就会令其休眠，进入就绪状态；如此往复，不同的进程均在某段时间获取了时间片并执行，于是均达到了运行的目的。由于这个过程非常的快，用户直观上几乎无法察觉它的存在，即所有的进程的“同时”运行的。

0x03 输入输出

当你在Terminal使用键盘输入文字的时候，你的输入将被送入程序的基本输入流(STDIN)缓冲区，再经由程序处理，并将结果输出到基本输出流(STDOUT)。操作系统默认为你的程序分配了三个标准的流：STDIN、STDOUT和STDERR，它们的文件描述符(File Descriptor)是0、1和2。

判题机内核要想接管程序的输入输出，就需要将这几个默认的流重定向。Linux系统为我们提供了dup2函数：

#include <unistd.h>

int dup2(int oldfd, int newfd);

通过参数名，很容易知道这个函数传入两个文件描述符，oldfd将会替换newfd。因此，判题机内核要做的工作就是打开一个测试数据的输入文件，和一个临时文件，并将它们分别重定向到子进程的STDIN和STDOUT中。

int fd_in = open("./testcase.in", O_RDONLY);
int fd_out = open("/tmp/user.out", O_RDWR);

dup2(fd_in, STDIN_FILENO);    // STDIN_FILENO  == 2
dup2(fd_out, STDOUT_FILENO);  // STDOUT_FILENO == 1

此时，程序的输入将从testcase.in文件读入，输出内容将可以在user.out文件获取。你还可以将STDERR_FILENO重定向到一个文件，以便接收程序在STDERR流输出的内容。注意，由于open方法是一个非常底层的文件操作，user.out文件在反复写入的时候，只会从头覆盖特定长度的内容，而不是清空整个文件后再写入。例如程序A输出了10个字节，程序B输出了4个字节，覆盖操作下，程序B运行结束后，user.out文件依然是10个字节，只是前4个字节被覆盖。因此，在每次执行判题前，需要先将user.out文件删除，确保输出结果是正常的。

0x04 等待进程退出

判题内核的一个关键目标就是，必须能够监控被测程序的开始和结束。

通过第一节我们了解到，父进程可以创建子进程并在子进程运行外部程序。但不知道你有没有注意到，如果我们要实现一个判题内核，在启动新的进程后，父进程就必须停下来，等待子进程结束后，才能继续工作，收集被测程序的运行信息等。这时候就要用到wait()系列的函数了。

wait函数有很多个兄弟姐妹，常用的如wait()、waitpid()、wait3()和wait4()等。它们共同的作用就是阻塞父进程，等待子进程的结束。

wait()函数会阻塞原程序并等待任意一个子进程退出，而waitpid()可以指定等待的子进程PID。不过，这两个我们都不用，因为他们都不能取到程序的运行信息。

pid_t wait4(pid_t pid, int *status, int options, struct rusage *rusage);

wait4解决了这个问题，它为我们带来了四个参数：

  • pid_t pid：等待的进程
  • int *status：接收进程退出的状态信息
  • int options：设置等待方式
    • WUNTRACED：除了返回终止子进程的信息外，还返回因信号而停止的子进程信息。
    • WCONTINUED：返回那些因收到SIGCONT信号而恢复执行的已停止子进程的状态信息。
    • WNOHANG：如果参数pid所指定的子进程并未发生状态变化，则立即返回不会阻塞。这种情况下waitpid返回0
  • struct rusage *rusage：获取运行的资源信息。

要获取进程的运行资源信息，我们可以rusage返回的数据来获取。要获取进程的退出状态，可以用WIFEXITED(status)和WIFSIGNALED(status)来判断，前者判定进程是正常退出的，可以使用WEXITSTATUS(status)获取退出代码[1]，后者判定进程是以信号方式终止[2]，可以通过WTERMSIG(status)获取退出时的信号。通过对这些数据的分析，我们可以得知进程是以什么方式退出的，从而作出正确的判定。这些会在后续的文章中进行介绍。

0x05 小结

本文从进程的概念着手，对判题机核心中最重要的功能的实现进行简述，为后续开发完整的判题机核心奠定理论基础。下一节，我会就判题机如何判断TLE、MLE和OLE等判定进行分析。

一些备注

[1] 在你学C语言的课上，老师肯定建议你main函数结尾加上return 0; 当你产生了很多的问号，老师会跟你说不用管这个0是什么意思，写就是了。这个main函数的返回值0就是退出代码，表示正常退出，如果是负数，则说明程序异常退出了。显然，你可以自定义这个退出代码。
[2] Linux系统中通过信号（signal）机制来传递消息，在软件层模拟了一个中断（软中断）。当进程收到信号的时候，默认是会终止运行。你可以在程序中编写相关函数来捕获信号，并选择终止程序或者忽略信号。

文章引用

https://www.dazhuanlan.com/2019/12/26/5e0426c13920a
https://man7.org/linux/man-pages/man2/dup2.2.html

CATALOG