HongyiOJ -- 本科阶段的一次勇敢尝试
追求是什么?我想应该是可以勇敢地去做自己想做的事情吧~
Hongyi OJ,一款由弘毅学生自主研发的在线判题 / 做题平台
目前已经支持4种基本高级编程语言啦(C、C++、Java、Python3)
附上OJ地址: http://119.29.24.77 代码仓库: 前端:github.com/jiayu1011/H… 后端:github.com/jiayu1011/H…
技术栈
前端:
框架、组件库:
React
+Ant Design
语言:
TypeScript
后端:
框架:
Django
语言:
Python
评测机:
基于
Docker
封装
功能速览
核心功能:判题
在题库中浏览题目列表后,选择想要练习的题目进行代码提交
目前的评测结果有8种状态:
- Queuing:在队列中,代码等待评测
- Accepted(AC):代码成功通过所有测试数据,此题通过
- Presentation Error(PE):输出格式错误
- Wrong Answer(WA):输出结果错误
- Compile Error(CE):代码编译时出错
- Runtime Error(RE):代码运行时出错,程序异常终止
- Time Limit Exceeded(TLE):代码运行超时
- Memory Limit Exceeded(MLE):代码运行占用内存超限
在评测结果页面点击结果,可以查看出错的原因
可以对评测列表进行筛选,只查看某个用户或者某个题目的提交情况
上传题目
我们鼓励上传更多有价值、高质量的题目,以帮助我们更好地丰富我们的题库;
任何权限的用户都可以上传题目;
题目被上传后,后续会有题库管理员统一对上传的题目进行审核;
表单中,题目名称,题目难度,题目描述,时间限制,空间限制为必填项;
题号会由系统自动分配;
注:题目上传者需要提供标准测试输入输出数据,多组数据间用"\n##\n"隔开,标准输入和输出组需要一一对应位置和顺序
后台管理
管理员可以在任意时刻对题库中的题目进行审核,修改审核状态,或者编辑/删除题目
题目状态分为:审核中、已通过、未通过三种
管理员也可以对所有帐户进行权限更改和删除
未来迭代功能
我们希望把Hongyi OJ做成一个开源的,可以随处部署的低耦合式OJ平台,并且希望能够丰富它的版块功能
我们会后续推出比赛和社区板块,让用户可以更好地在平台中徜徉,交流、分享彼此的观点和解法,建设一个更加开放和轻松的OJ社区平台
准备工作
在之前的学习经历中,我其实对前端方面的技术接触的更多。就目前企业中更常用的前后端分离的体系来说,作为自强Studio的前端组成员,对于后端的概念还更多地停留在各种API接口的无情提供者。因为之前写过的项目中并没有涉及特别复杂的模块,所以便想趁着大软的机会好好锻炼一下自己。在某天打开洛谷的时候,我心中已经有了答案--我想独立地做出一个OJ平台。虽然现在的感觉和洛谷还相去甚远,但起码已经有了OJ的雏形。至于后续可能存在的高并发性能问题,我还在一步步学习中。
选题背景调研
对于研发岗的求职者或者信息竞赛选手来说,我想对于各种OJ平台,如leetcode, codeforces, POJ, HDUOJ, 洛谷
应该不会感到陌生。他们各有各的特色。我们对一些具有代表性的OJ平台进行了平台基础功能,题目,竞赛,论坛四个方面的调研。
力扣 | 洛谷 | 杭电、北大oj |
---|---|---|
力扣是上面的网站之中做的最好的网站,其优势在于这个网站不单单局限在做题上,网站充分利用了用户的需求,也就是求职;采用引用公司招人真题的方式来吸引用户。相比于单纯的刷题来说,力扣独特的企业题库更加有吸引力。网站带有的模拟笔试和面试的功能,给用户身临其境的求职体验。同时,在做题之外,用户还能直接在力扣进行专业知识的学习,从而保持用户在力扣的在线时间,进一步增加了影响力。此外,网站针对用户的做题统计会给出详细的正确率和做题分析,让用户可以有效地针对自己的知识空白进行补充。 | 洛谷是一个单纯的知识网站,学生能在网站上进行刷题以及和竞赛相关的训练。相比于力扣,洛谷的基本知识的题量比较接近,而重心则是放在了大学生竞赛上,和竞赛相关的真题、模拟等比较多。总的来说,适合有意向学习算法和准备参加竞赛的学生进行一般性的训练。不过洛谷主要是中文界面,和acm的全英文要求不太相符。 | 作为学校建立的oj,网站更加的简洁,功能也更加单一。网站的主要目的就是锻炼学生的编程能力,并为学生提供校际、校内算法比赛的平台。 |
一些细节分析(by陈嘉诺)
- 从论坛大佬的口中我了解到,很多人认为不用ide,而是用肉眼检查算法,这样对自己的编程能力有很大的提升。同时,网站里面的题也只是一个初级训练场,是通向竞赛和更高层次训练的基础。
- 不同的网站它的评测方式会有所不同,有的是在Windows下评测, 有的是在Linux系统下评测。有时候会出现细微的词缀错误。
- 如果平台的目标用户不仅是本校的学生,那么需要制定足够的规则来约束用户的言行,可以学习洛谷和力扣的站务贴
- 需要对题库做出一个解题规范,避免因为字符、常数、变量字母的格式问题出现不必要的错误,影响网站的运行效率。
- 在涉及与作业、竞赛有关的项目时,也许需要检测不同用户间可能存在的抄袭现象。
一些先于技术细节的Q&A
评测机是什么?我们做的是什么样的评测机?
顾名思义,评测机就是将用户提交的代码进行编译并运行,并实时监测程序运行状态,最终对程序输出结果进行结果分析的一个自动化系统。
考虑到技术难度,我们实现的是针对ACM模式的评测机。
ACM模式是什么?
目前的OJ平台对于评测代码这一块主要分成两大类:Core Function(核心函数)模式和ACM模式。
- Core Function(核心函数)模式
在用户进入提交代码页面的时候,类名和待实现的方法名及相应格式的输入形参已经写好,用户仅需要实现该方法并返回结果,相当于实现一个具有核心功能的函数。
例题:反转单链表
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。输入示例: head = [1,2,3,4,5]
输出: [5,4,3,2,1]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
上题中表明需要在Solution
函数中返回一个ListNode
类型的值,顺着这个题目的思路想办法构造一个符合题目要求的ListNode
即可。
leetcode基本都采用的是Core Function模式来供用户们练习。
- ACM模式
题目的标准输入均为字符串,需要自己写出完整的,能够处理标准输入输出的程序。对于需要的数据,需要自己一一将对应的数据转化成自己需要的数据类型,如整形、数组等。
在处理标准输入输出时,需要用到编程语言中的IO语句,如Python
对应的读取标准输入的函数为input()
,可以使用str = input()
来获取到所有标准输入,并且使用print()
函数进行标准输出,如print('hello')
会在标准输出中输出hello
这个字符串; Java中则可以使用Scanner
和System.out.println()
来进行标准输入和输出的控制...
例题:反转链表
第一行一个整数
n
,表示单链表的长度。 第二行n
个整数val
表示单链表的各个节点。 第三行一个整数m
,表示双链表的长度。 第四行m
个整数val
表示双链表的各个节点。输入示例: 3 1 2 3 4 1 2 3 4 输出: 3 2 1 4 3 2 1
总结比较
- Core Function模式对新手更加友好,无需花费精力在处理输入输出的格式上面;ACM相对难度较高,需要掌握一种编程语言基本的IO方法,并且要注意输入输出与题目要求的对应关系,否则会出现Presentation Error
- Core Function模式中用户提交的所有代码在评测机中无法独立完成编译和运行,需要评测机对提交代码的外部再套一层处理层;而ACM模式提交的代码可以在评测机中独立完成编译和运行,无需再进行多余的处理
技术细节
关于前后端的基本业务逻辑我就不在此赘述了,难度并不高;
数据库设计
考虑到后续加入的社区和比赛板块,我提前构建好了数据库结构。
在Django
中构建数据库的模型时(models.py
中),由于Evaluation(评测任务)
类中的relatedProblemId
属性直接与Problem(题目)
类中的problemId
直接挂钩,因为problemId
是Problem
类的主键,即problemId
这个属性是Evaluation
类的外键,通俗地说就是一个评测任务会对应到一个题目上面(提交代码是针对某个题目进行提交的),如果这个题目不存在了(被删除了或者其他的情况),那么这个评测任务也会变得毫无意义,应该随之被删除,即外键约束应该为DESCADE
,同理适用于author
属性。
数据库时区设置
在获取代码提交时间时,需要在Django项目中的settings.py
中设置时区,否则在将数据写入数据库时,会默认转换成英国格林尼治时间,并不是我们想要的时间
# Time Zone setting
TIME_ZONE = 'Asia/Shanghai'
USE_TZ = False
后端&评测机设计
工程结构如下
其中后端宿主机Host与Docker容器使用以下linux命令进行通信:
容器向主机拷贝
docker cp [OPTIONS] CONTAINER:SRC_PATH DEST_PATH
主机向容器拷贝
docker cp [OPTIONS] SRC_PATH CONTAINER:DEST_PATH
示例:
docker cp E10001:/Temp/E10001_result.txt ./
评测功能流程
在解释评测机内部是怎么工作之前,先给出我们设定的结果分析机制。
结果分析机制(7种结果类型是如何分析得出的)
- 编译,如果编译时出现错误则判定为
Compile Error
,并且返回错误日志 - 执行可执行文件,若出错则判定为
Runtime Error
,并且返回错误日志 - 运行时监测Docker容器内该待评测进程的内存占用峰值和程序运行CPU占用时间,记录在运行日志中返回(后续用于判断是否存在运行超时或者内存超限)
- 若没有出错,则将待评测进程输出结果和标准输出逐字符比对,若完全一致,则判定为
Accepted
;若不完全一致,则用python
中的split()
函数对结果文本进行分割(split()
默认会将所有空字符作为分隔符),得到结果列表,再逐项比对列表中元素内容,全部一致则判定为Presentation Error
;若不一致则判定为Wrong Answer
评测机流程
在介绍监视器前,有必要介绍一下Python与系统交互常用的一些工具。我用到的是psutil
和subprocess
。
psutil
在
Linux
下,有许多系统命令可以让我们时刻监控系统运行的状态,如ps
,top
,free
等等。 相比于使用上述系统命令来获取系统信息,在Python
中的一个好办法是使用psutil
这个第三方模块。顾名思义,psutil = process and system utilities,它不仅可以通过一两行代码实现系统监控,还可以跨平台使用,支持Linux/UNIX/OSX/Windows
等,是系统管理员和运维小伙伴不可或缺的必备模块。、常用方法:
# 使用进程号实例化一个psutil.Process对象 pst = psutil.Process(12345) """ 获取进程的CPU占用时间,包括user和system两部分 """ runningTime = pst.cpu_times() """ 获取进程的内存占用情况,包括rss和vms两部分 rss对应top命令的RES(实存),vms对应top命令的VIRT(虚存) """ runningMem = pst.memory_info()
subprocess
subprocess
模块可以生成新的进程,连接到它们的input/output/error
管道,同时获取它们的返回码。Popen() 方法
Popen
是subprocess
的核心,子进程的创建和管理都靠它处理。 构造函数:compileProcess = subprocess.Popen( [ 'g++', codeFilePath, '-w', '-o', compileOutput ], stderr=CEFile ) compileProcess.wait() # Wait until compile finished
常用参数:
args
:shell命令,可以是字符串或者序列类型(如:list,元组)bufsize
:缓冲区大小。当创建标准流的管道对象时使用,默认-1。 0:不使用缓冲区 1:表示行缓冲,仅当universal_newlines=True时可用,也就是文本模式 正数:表示缓冲区大小 负数:表示使用系统默认的缓冲区大小。\stdin, stdout, stderr
:分别表示程序的标准输入、输出、错误句柄preexec_fn
:只在 Unix 平台下有效,用于指定一个可执行对象(callable object),它将在子进程运行之前被调用shell
:如果该参数为 True,将通过操作系统的 shell 执行指定的命令。cwd
:用于设置子进程的当前目录。env
:用于指定子进程的环境变量。如果 env = None,子进程的环境变量将从父进程中继承。
程序运行时是以进程的形式,因此讨论是在进程层面。我们需要考虑进程运行时的状态,对不同指标进行取舍,以更好地监控进程的行为。
进程执行时间
真实时间:进程从开始执行到最后结束的时间,包括阻塞 + 就绪 + 运行的时间。称为 wall clock time/墙上时钟时间/elpapsed time,是我们跑程序实际等待的时间;
系统cpu时间(system time):用户进程获得CPU资源后,在内核态的执行时间,如write,read等系统调用;
用户cpu时间(user time):用户进程获得CPU资源后,在用户态执行的时间,主要是我们自己编写的代码;
其中可大致认为:
真实时间 = 阻塞时间 + 就绪时间 + CPU运行时间
CPU运行时间 = 用户CPU时间(user time) + 系统CPU时间(system time)
根据对洛谷等平台的测试,我们发现用户CPU时间更接近在上述平台中测试的结果,故在监视器中我们取
用户CPU时间(user time)
作为监测指标。
进程内存占用
关于top
命令中的VIRT
(虚存)和RES
(实存),具体描述如下:
VIRT | RES |
---|---|
1、进程“需要的”虚拟内存大小,包括进程使用的库、代码、数据,以及malloc、new分配的堆空间和分配的栈空间等; | 1、进程当前使用的内存大小,包括使用中的malloc、new分配的堆空间和分配的栈空间,但不包括swap out量; |
2、假如进程新申请10MB的内存,但实际只使用了1MB,那么它会增长10MB,而不是实际的1MB使用量。 | 2、包含其他进程的共享; |
3、VIRT = SWAP + RES | 3、如果申请10MB的内存,实际使用1MB,它只增长1MB,与VIRT相反; |
4、关于库占用内存的情况,它只统计加载的库文件所占内存大小。 | |
5、RES = CODE + DATA |
根据对洛谷等平台的测试,我们发现实存更接近在上述平台中测试的结果,故在监视器中我们取
实存
作为监测指标。
监视器流程
结果分析流程
一些难题
在评测机运行的过程中,我们在C和C++两个较为底层的语言中遇到了难题,问题出在:
当C或者C++程序在遇到运行时错误时,对于某些错误如:
段错误
- 访问不存在的或受系统保护的地址
- 堆栈溢出(如无限递归)
- 使用指针却没有给指针分配内存空间
- ....
浮点数错误
- 算术运算中有涉及到除0的操作
这些运行时出现的错误不会被重定向到错误输出中,也就是说,只从重定向后的错误日志中我们无法发现这类错误,但这类错误会导致程序异常终止。
原因在于,C
和C++
都是较为底层的语言,赋予了使用者操作内存的一种能力。C
和C++
中对于此类错误并没有相关封装好的程序终止方法,而是使用Linux系统中的信号的通信方式来对程序进行中断。如发生段错误后操作系统会抛出SIGSEGV
信号,之后调用默认的信号处理函数,产生core文件,然后中断程序。
解决方法
既然没有办法在错误输出重定向后的错误日志发现此类错误,我和阿汤同学在聊天的时候他提到了一个概念:进程退出码。 我查阅资料后发现,一个进程如果是由系统所发送的信号而终止,相比于正常退出,会有不同的进程退出码,而且每种中断信号对应的退出码都不一样!!
具体的对应关系如下表:
对于上表,进一步总结如下:
-
能使进程被终止执行并产生core dump的信号,它的退出状态码是信号编号+128,比如SIGQUIT信号,它的编号为3,进程收到该信号后会core dump,退出状态码为
3+128=131
; -
只是使进程被终止,而不会产生core dump的信号,它的退出状态码就是信号本身的编号。
- 对于段错误(Segmentation Fault),系统发送的信号是
SIGSEGV
。即进程退出码为139
- 对于算术异常(Float Point Error),系统发送的信号是
SIGFPE
。即进程退出码为136
- ...
在subprocess
的Popen
类中,可以使用process.returncode
属性或者process.poll()
的返回值来获取某个进程的返回码(也就是进程退出码exitcode
),如:
execProcess = subprocess.Popen(
[
'java',
javaMainClass
],
stdin=inputFile,
stdout=outputFile,
stderr=REFile
)
# 获取该进程的退出码
exitcode = execProcess.poll()
!!!但有一点要说明的是,在subprocess
库中,对于returncode属性
说明如下:
returncode
属性表示了该子进程的退出状态码。通常来说,一个为 0 的退出码表示进程运行正常。一个负值
-N
表示子进程被信号N
中断(仅POSIX
)。
意思就是说,如果该子进程被系统使用信号中断了,那么返回的值将会是一个负数。这个负数取相反数之后等于此中断信号的信号编号(即图表中最左那一栏的属性)。
也就是说,我们可以建立一个信号编号与报错信息的对应字典,在获取到中断信号的信号编号后,对应地拿到这种中断信号的报错信息!
构建如下:
processTerminatedExitCode2SignalDict = {
7: 'Bus Error',
8: 'Float Point Error',
11: 'Segmentation Fault',
}
上述字典当然还可以继续完善,但考虑到可能出现的错误类型,我们先把最常见的几种类型写了进去,决定等后续遇到问题再对信号库进行丰富和更新。至此,信号中断无报错问题被完美解决~
为什么在评测机外面要套一层Docker?
原本使用Docker
的初衷是想实现随处部署的这样一个技术,但有一天突然想到:如果用户提交的代码具有很强的攻击性怎么办?
为了保护宿主机不受破坏,增加服务器的安全性,Docker
可以限制容器的内存占用,并且就算受到了攻击,也只会是Docker
进程死掉,而不会破坏服务器中的其他系统级进程。所以给评测机套上了一层Docker
。
如果有多个用户同时提交代码,如何处理高并发情况呢?
高并发的问题我一开始就有考虑过,也是想借着这个机会来逼自己学一下多进程和多线程。 对于后端框架Django来说,每收到一个接口调用请求,Django都会新开一个线程去执行该任务,所以在Server进程中是一个多线程的情况。
趁着这个机会,复习一下多进程和多线程的区别~
维度 | 多进程 | 多线程 | 总结 |
---|---|---|---|
数据共享、同步 | 数据是分开的,共享复杂,需要用IPC;同步简单 | 多线程共享进程数据,共享简单;同步复杂 | 各有优势 |
内存、CPU | 占用内存多,切换复杂,CPU利用率低 | 占用内存少,切换简单,CPU利用率高 | 线程占优 |
创建销毁、切换 | 创建销毁进程开销大、切换复杂,速度慢 | 创建销毁线程开销小、切换简单,速度快 | 线程占优 |
编程调试 | 编程简单,调试简单 | 编程复杂,调试复杂 | 进程占优 |
可靠性 | 进程间不会相互影响(因为有独立的地址空间) | 一个线程挂掉将导致整个进程挂掉 | 进程占优 |
在可靠性这一方面,Django
中的多线程可能会出现某一线程死掉,进而导致所有线程直接崩溃,其他人的评测任务也受到了影响的情况。这个是后续需要考虑的一个点。
目前对于多个评测任务,服务器启动评测机的顺序也是让操作系统自行调度的,并没有明确的多进程调度算法来控制评测任务的先后执行。在评测任务达到一定数量之后,可能会出现后来的评测任务先出结果。这一块由于目前任务数并不多,所以不能够看出来很显著的问题。
总结
总的来说,这一整个流程下来,包括搭评测机,包括配置容器的运行环境(目前支持的4种编程语言),一系列亲手完成都是很有成就感的存在,其中也是收获多多,对操作系统,进程和线程又有了进一步的理解和学习,动手能力也是得到了进一步的提高。感谢组员们的帮助!
HongyiOJ小组成员: 组长:辛嘉宇 组员:陈炜鹏,文韬,曾文瑄,汪涛(准备考研ing),展钰奇(此人已下落不明)
转载自:https://juejin.cn/post/7036581231340814367