从零开始实现一个 OJ 评测姬。
为什么叫评测姬?因为她有耐心、细心,但有时候会闹别扭卡评测,所以我认为她应该是姬。
什么是评测姬
简单来说,评测姬就是在线运行用户提交代码并返回运行结果的一个软件。一般用在 OJ(Online Judge 在线评测系统)中。如果你在 OJ 上交过题的话,那你就已经使用过评测姬了。
常用的 OJ:
- SDUTOJ:https://acm.sdut.edu.cn/
- POJ:http://poj.org/
- LOJ:https://loj.ac/
- 洛谷:https://www.luogu.org/
- CF:http://codeforces.com/
此处强推最近比赛插件 recent_contests,可以方便的查看最近的比赛与时间。
为什么需要评测姬
在 OJ 的环境下,需要获得程序的时间与内存占用,从而在相同输入数据的情况下对比判断用户设计的程序的时间复杂度与空间复杂度;同时还需要保证在用户提交了错误的代码(如死循环等)的情况下能正确的结束用户程序并返回结果;此外还有安全性等的要求,如果使用很多语言自带的 fork
是做不到的,这些都需要评测姬来做。
我们的评测姬需要实现的功能
首先是最基础的评测功能,即用户提交代码,评测姬可以编译执行这段代码,给定程序输入并获取程序输出,并根据程序的输出来判断用户提交的代码的正确性,返回给用户。
然后是获取用户程序占用的资源,并以此为基准判断用户代码的时间复杂度与空间复杂度是否可以被接受。
出于对安全性的考虑,需要限制用户程序能够使用的资源,否则用户提交一段死循环代码就会导致评测姬卡住。还要限制用户程序能够对评测姬进行的操作,否则用户提交 system('rm -rf /')
就完蛋了。
最后,由于评测姬与 OJ 的 WEB 端较为独立,每次评测都需要双方交互,因此评测姬最好有比较清晰的接口,易于调用。
使用什么实现
因为 Windows 平台编程我完全没接触过,因此这个评测姬将是 Linux 平台的。实现一个评测姬需要很多的系统调用,使用 C 语言可以最轻松的使用这些系统调用;同时 C 语言的普及率也是比较高的,因此在这个系列里我将使用 Linux(Ubuntu 16.04) 与 C 语言实现。
系列里所有的代码我将放到 GitHub 仓库 ZeroJudger 里,预计系列完结时我们已经开发完成一个完整可用的评测姬。
也可以参考其他语言(Go)实现的评测核心:JudgeLight-Go。
总结
在本章中,我们大概了解了一下评测姬的用处,下一章我将介绍评测姬的具体评测流程与结果判断的原理。