競プロのジャッジシステムっぽいものをGo言語で自作してみた
この記事は、公立はこだて未来大学 Advent Calendar 2022 11日目の記事です。
だれ
この人です。学部1年です。
最近は、ダジャレを検出してみたり、ロボットを作ってみたりしています。
はじめに
本学のプログラミング基礎という授業では、提出課題のテストツールとして、ppchk というプログラム群が提供されています。あらかじめ用意している複数のテストケースで、与えられたプログラムの入出力をテストするものです。競技プログラミングのジャッジシステムのようなものですね。
せっかくなら、この ppchk そのものを自作してみたら、プログラミングの勉強になる上に面白いと思ったので、やっていこうと思います。
つかったもの
できた
ということで、できました。
こんな感じで動作します。
また、本家コマンドとほぼ同等のインターフェースをもったtiny版もついでに作りました。
適切にaliasを張れば、本家コマンドと同様に利用できます。
今回はこのソフトについてのお話をしていこうと思いますが、全部を説明すると、内容が超盛り沢山になってしまうので、いちばん重要な、外部ファイルの実行関連の部分を書いていこうと思います。
ファイルを安全に実行したい
このシステムは作成したプログラムをチェックするのに使われるので、様々なプログラムを実行することになります。処理にとてつもない時間がかかるプログラムや、無限ループに陥ってしまうプログラムが投入されるかもしれません。なんらか、実装がマズいプログラムが投入される可能性もあります。
実際に演習用サーバを破壊した人
そのようなプログラムを、適切に中断させる必要があります。例えば、競技プログラミングサイトの AtCoder では、一定時間以上経ってもプログラムが終了しない場合は誤答 (TLE) となります。これと同じようなものを実装すれば、ジャッジシステム側での対策が可能そうです。
実行時間を計測しよう
処理にとてつもない時間がかかるプログラムを落とすために、一定時間たったら処理を中断させるようにします。そのためには、実行時間を計測してあげればよさそうです。
cmd := exec.Command("./"+question)
start := time.Now()
if err := cmd.Start(); err != nil {
panic(err)
}
if err := cmd.Wait(); err != nil {
panic(err)
}
since := time.Since(start).Seconds()
if since > 2 {
fmt.Println("TLE")
}
このようにすれば、実行時間を計測することができます。しかし、これでは、実行時間はわかりますが、実行が終了するまで計測ができないので、2秒を超えたら途中で中断する、ということができません。
goroutine、登場
外部ファイルの実行と並列に、タイマーを動かすことができれば解決しそうです。Go言語だと、goroutine をつかって簡単に実装できます。
cmd := exec.Command("./"+question)
// TLE Timer
go func() {
time.Sleep(time.Second * 2)
fmt.Println("TLE")
}()
// ～前処理いろいろ～
// 実行を開始
if err := cmd.Start(); err != nil {
panic(err)
}
// ～中間処理いろいろ～
// 終了を待つ
if err := cmd.Wait(); err != nil {
panic(err)
}
// ～処理いろいろ～
TLE Timerの部分が並列に動いているので、ちゃんと2秒後に"TLE"とPrintされるはずです。このPrintの後にいい感じに終了処理をしてあげればうまくいきそうです。
いい感じに外部ファイル実行を中断する
いい感じに実行を終了していきます。(*exec.Cmd).Process.Kill()すれば、そのプロセスにSIGKILL(強制終了してね、というOSの指令)が飛んで、そのプロセスは強制的に終了します。
cmd := exec.Command("./"+question)
// TLE Timer
go func() {
time.Sleep(time.Second * 2)
fmt.Println("TLE")
+ cmd.Process.Kill()
}()
// ～前処理いろいろ～
// 実行を開始
if err := cmd.Start(); err != nil {
panic(err)
}
// ～中間処理いろいろ～
// 終了を待つ
if err := cmd.Wait(); err != nil {
panic(err)
}
// ～後処理いろいろ～
これで良さそうに見えます。
動作確認
ちゃんとプロセスがKillされているか、確認してみましょう。試しに、TLEするプログラムを入れてみます。
#include <stdio.h>
int main(void) {
sleep(3);
printf("Hello!\n");
return 0;
}
これをジャッジシステムに入れて、終了後に実行中プロセスを確認します。
$ ps j
PPID PID PGID SID TTY TPGID STAT UID TIME COMMAND
2380 2381 2381 2381 pts/6 2800 Ss 1000 0:00 /usr/bin/zsh -i
2381 2800 2800 2381 pts/6 2800 R+ 1000 0:00 ps j
./helloのプロセスは残っていません。いい感じに落ちていますね。
無限ループになってしまうプログラムも試してみましょう。
int main(void){
int cnt = 0;
while (1) {
cnt += 1;
}
printf("Hello!\n");
return 0;
}
while の部分の終了条件がマズいので、無限ループになってしまっています。
$ ps j
PPID PID PGID SID TTY TPGID STAT UID TIME COMMAND
27866 28531 28531 28531 pts/6 29333 Ss 1000 0:00 /usr/bin/zsh -i
28531 29333 29333 28531 pts/6 29333 R+ 1000 0:00 ps j
きちんとTLEで落ちて、./loopのプロセスは残っていません。
ではこのようなコードならどうでしょう。
#include <stdio.h>
int main(void) {
system("sleep 3");
printf("Hello!\n");
return 0;
}
今度はC言語から他のプログラムを呼ぶかたちのプログラムです。プロ基礎の授業ではおそらくこのようなコードは出てきませんが、どんなプログラムを入れても安全であって欲しいので一応試してみましょう。
$ ps j
PPID PID PGID SID TTY TPGID STAT UID TIME COMMAND
977 1618 1618 1618 pts/6 4493 Ss 1000 0:00 /usr/bin/zsh -i
955 4464 4361 1618 pts/6 4493 S 1000 0:00 sh -c sleep 3
4464 4465 4361 1618 pts/6 4493 S 1000 0:00 sleep 3
1618 4493 4493 1618 pts/6 4493 R+ 1000 0:00 ps j
あれ、なんか残ってしまっています。./hello2は終了していますが、./hello2が呼んだsleep 3が終了していません。実は、cmd.Process.Kill()では、自分で実行したプロセスだけを落とします。実行したプロセスが実行する別のコマンド、孫にあたるプロセスに対してはなにもしません。hello2.cで、終了時に適切にsleep 3も終了するように書いてあればきちんと落ちますが、それをしていない場合、実行が終了するまで孫プロセスが生き続けます。もしこれが無限ループに陥るものであった場合は大変です。
PGIDを使おう
実行するプログラム群をグループとしてまとめてKillするようにしましょう。まずは、グループ番号になるPGID(Process Group ID)を付与するように設定をします。そして、そのグループ全体に対して、SIGKILL(強制終了してね、というOSの指令)を飛ばします。
cmd := exec.Command("./"+question)
+cmd.SysProcAttr = &syscall.SysProcAttr{Setpgid: true}
// TLE Timer
go func() {
time.Sleep(time.Second * 2)
fmt.Println("TLE")
- cmd.Process.Kill()
+ syscall.Kill(-cmd.Process.Pid, syscall.SIGKILL)
}()
// ～前処理いろいろ～
// 実行を開始
if err := cmd.Start(); err != nil {
panic(err)
}
// ～中間処理いろいろ～
// 終了を待つ
if err := cmd.Wait(); err != nil {
panic(err)
}
// ～後処理いろいろ～
これで全部落ちるはずです。試してみましょう。
$ ps j
PPID PID PGID SID TTY TPGID STAT UID TIME COMMAND
977 1618 1618 1618 pts/6 5554 Ss 1000 0:00 /usr/bin/zsh -i
1618 5554 5554 1618 pts/6 5554 R+ 1000 0:00 ps j
ちゃんと落ちていますね。いい感じです。これで安全に実行できそうです。
Ctrl+C 対応も忘れずに
あまりにも時間がかかってしまうときや、間違えて実行してしまった際には、Ctrl+Cをすると思います。これもちゃんと試してみましょう。TLEが出る前にCtrl+Cをします。
$ ps j
PPID PID PGID SID TTY TPGID STAT UID TIME COMMAND
977 1618 1618 1618 pts/6 5683 Ss 1000 0:00 /usr/bin/zsh -i
5680 5681 5680 1618 pts/6 5683 S 1000 0:00 sh -c sleep 3
5681 5682 5680 1618 pts/6 5683 S 1000 0:00 sleep 3
1618 5683 5683 1618 pts/6 5683 R+ 1000 0:00 ps j
孫プロセスが生き残ってしまっていますね。Ctrl+Cを受け取ったら、ちゃんと終了処理中にSIGKILLを飛ばして終了させてあげましょう。
cmd := exec.Command("./" + question)
cmd.SysProcAttr = &syscall.SysProcAttr{Setpgid: true}
// TLE Timer
go func() {
time.Sleep(time.Second * 2)
fmt.Println("TLE")
// cmd.Process.Kill()
syscall.Kill(-cmd.Process.Pid, syscall.SIGKILL)
}()
+// syscall listener
+sig := make(chan os.Signal, 1)
+signal.Notify(sig, syscall.SIGTERM, syscall.SIGINT)
+go func() {
+ <-sig
+ syscall.Kill(-cmd.Process.Pid, syscall.SIGKILL)
+}()
// ～前処理いろいろ～
// 実行を開始
if err := cmd.Start(); err != nil {
panic(err)
}
// ～中間処理いろいろ～
// 終了を待つ
if err := cmd.Wait(); err != nil {
panic(err)
}
<-sigでは、sigというチャンネルに情報が入るまで処理がそこで止まります。
これで、Ctrl+C(SIGINT)や、SIGTERMを受け取ったとき、sigに情報が入ります。これらのシグナルを受けてプロセスの終了処理が走るようになりました。もう一度試してみます。動作中にCtrl+Cを送信して処理を中断させます。
$ ps j
PPID PID PGID SID TTY TPGID STAT UID TIME COMMAND
977 1618 1618 1618 pts/6 6431 Ss 1000 0:00 /usr/bin/zsh -i
1618 6431 6431 1618 pts/6 6431 R+ 1000 0:00 ps j
ちゃんと終了しています。これで完了です！
おわりに
安全に外部プログラムを動かすのは難しいですね。これらの安全に実行する仕組みに加え、いい感じの色・アニメーションつきUIなどを実装したので、ぜひ試してみてください。多分どのOSでも、(Go言語が対応していれば)ビルドして動かすことができるはずです。テストケースも中に含んだバイナリがビルドされるので、実行ファイルだけ配置すれば、セットアップが完了します。
現状、ファイル入出力を伴う問題のテストができないので、次はその機能を追加したいですね。
明日の記事は、
-
Part1: ツナチキンさんの『【令和最新版】弊学の大学生協パソコンが凄い【新入生必見】』
え！？来年の生協パソコンは凄いんですか！？めちゃくちゃ気になりますね。ボクは推奨機を買わずにThinkPadを買いましたが... -
Part2: 楓さんの『趣味Aか趣味Bかsurfaceについて書くと思います』
どんな趣味のお話なのか、気になりますね。 -
Part3: ゆんゆんさんの『みたらハマるガチャガチャの話！あとサークルも作った』
ガチャガチャ、楽しいですよね！
です。ということで、乞うご期待！
Discussion