🧪

競プロのジャッジシステムっぽいものをGo言語で自作してみた

2022/12/11に公開約7,600字

この記事は、公立はこだて未来大学 Advent Calendar 2022 11日目の記事です。

https://adventar.org/calendars/7402

だれ

この人です。学部1年です。
https://twitter.com/jugesuke

最近は、ダジャレを検出してみたり、ロボットを作ってみたりしています。
https://github.com/jugesuke/dajareGo

はじめに

本学のプログラミング基礎という授業では、提出課題のテストツールとして、ppchk というプログラム群が提供されています。あらかじめ用意している複数のテストケースで、与えられたプログラムの入出力をテストするものです。競技プログラミングのジャッジシステムのようなものですね。

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10136347940

せっかくなら、この ppchk そのものを自作してみたら、プログラミングの勉強になる上に面白いと思ったので、やっていこうと思います。

つかったもの

  • Go言語
    • きみもやろう
  • cobra
    • CLIツールを簡単に作ることができます
  • gcc
    • C言語で書かれたプログラムをコンパイルするのに使いました

できた

ということで、できました。

https://github.com/jugesuke/local-judge-tools

こんな感じで動作します。

また、本家コマンドとほぼ同等のインターフェースをもった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するプログラムを入れてみます。

hello.c
#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のプロセスは残っていません。いい感じに落ちていますね。

無限ループになってしまうプログラムも試してみましょう。

loop.c
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のプロセスは残っていません。

ではこのようなコードならどうでしょう。

hello2.c
#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言語が対応していれば)ビルドして動かすことができるはずです。テストケースも中に含んだバイナリがビルドされるので、実行ファイルだけ配置すれば、セットアップが完了します。

https://github.com/jugesuke/local-judge-tools

現状、ファイル入出力を伴う問題のテストができないので、次はその機能を追加したいですね。

明日の記事は、

  • Part1: ツナチキンさんの『【令和最新版】弊学の大学生協パソコンが凄い【新入生必見】』
    え!?来年の生協パソコンは凄いんですか!?めちゃくちゃ気になりますね。 ボクは推奨機を買わずにThinkPadを買いましたが...

  • Part2: 楓さんの『趣味Aか趣味Bかsurfaceについて書くと思います』
    どんな趣味のお話なのか、気になりますね。

  • Part3: ゆんゆんさんの『みたらハマるガチャガチャの話!あとサークルも作った』
    ガチャガチャ、楽しいですよね!

です。ということで、乞うご期待!

Discussion

ログインするとコメントできます