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

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

0x00 进程

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

来自百度百科词条

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

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

0x01 创建进程

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

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

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

与fork()不同的是,vfork()创建的子进程会和父进程共享数据段,另外,vfork()会保证在_exit()和exec()类函数执行前,子进程先运行。

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