Online Judge 채점 서버의 제출 코드 실행 시간 측정하기

본 게시글은 개인 프로젝트[AlgoMarket]를 개발하며 작성한 기록입니다.

GitHub - ymkim97/algo-market: 개인 프로젝트 - 알고리즘 온라인 저지 서비스

들어가며

현재 AlgoMarket의 채점 서버는 Python으로 구축되어 있습니다.
글을 작성하는 시점을 기준으로 채점할 수 있는 언어는 Java와 Python이 있습니다.
외부 코드를 받고 그대로 돌리는 것은 위험하기에 샌드박스로 Docker를 사용하여 컴파일하고, 각 테스트 데이터(Local에 저장되어 있으며, 부재 시 S3에서 Get)를 Iterate 하면서 정답 output과 일치하는지 확인합니다.
이때 모든 케이스를 맞추면 "ACCEPTED" 라는 status와 사용자 코드의 최대 실행 시간(ms) 및 최대 메모리(mb) 사용량을 반환하는 것이 목표였습니다.
어떻게 코드의 실행 시간 자체를 측정하여 문제의 제한 시간 이내인지 정확히 판별하고, 사용자에게 보여줄지 알아보겠습니다.

 

채점 프로세스 방식

먼저 Python에서 어떻게 채점되는지 일부 코드를 보도록 하겠습니다.

# judge.py
...

for i, (input_data, expected_data) in enumerate(zip(input_test_data, output_test_data)):
        process = None
        try:
            process = subprocess.Popen(
                docker_cmd,
                stdin=subprocess.PIPE,
                stdout=subprocess.PIPE,
                stderr=subprocess.PIPE,
                text=True,
                encoding='utf-8'
            )

            stdout, stderr = process.communicate(input=input_data, timeout=time_limit)
            
...

 

이때 사용되는 subprocess라는 모듈은 새로운 프로세스를 생성하고, 그들의 입력/출력/에러 파이프에 연결하고, 반환 코드를 얻을 수 있도록 합니다. (https://docs.python.org/ko/3.13/library/subprocess.html)

서버의 Docker에 명령을 보내기 위해서 사용되었습니다.

sub.process.Popen() 함수를 통해 subprocess().run() 함수보다 더 많은 제어와 유연성을 이용하여 자식 프로세스의 표준 입출력 스트림을 파이프로 연결하였습니다.

PIPE를 지정하지 않으면 자식 프로세스의 표준 입출력 스트림이 부모 프로세스가 쓰는 스트림을 그대로 상속합니다. 즉, 자식 프로세스가 쓰는 곳/읽는 곳이 부모의 콘솔과 같아집니다.

이미 존재하는 파일(테스트 데이터)를 읽고 입력해주는 것이기 때문에 필수 설정입니다.

• 출력(stdout/stderr): 자식이 출력하는 내용이 바로 부모의 콘솔(예: PyCharm 실행 콘솔)에 보이고, 파이썬 코드에서 문자열로 캡처되지 않음
• 입력(stdin): 자식이 표준 입력을 읽으면 콘솔에서 키보드 입력을 기다립니다. communicate(input=...)는 stdin=PIPE일 때만 동작

이름을 보시면 어느정도 짐작이 가실겁니다. stdin은 입력, stdout은 출력, stderr는 에러 또는 진단 관련 출력입니다.

 

자식 프로세스를 생성 후 process.communicate()를 이용하여 입력 테스트 데이터를 전달하고 출력을 기다립니다.

이때 argument로 timeout을 넣어주는 것을 확인할 수 있는데, time_limit은 문제의 시간 제한입니다.

해당 프로세스가 설정된 timeout을 초과할 경우 TimeoutExpired 예외가 발생합니다.

그리고 여기서 문제가 있다는 것을 느낄 수 있습니다!

 

proccess.communicate(..., timeout=time_limit)의 문제점

제가 위에서 말한 "해당 프로세스가 설정된 timeout을 초과할 경우" 를 잘 생각해 보면 무언가가 이상하다는 것을 알 수 있습니다.

알고리즘 문제 제출 코드의 실행 시간 자체에 대해서 시간 초과를 확인해야 하는데, 여기서 말하는 프로세스는 컨테이너의 생성 + 컨테이너 실행 + 컨테이너 정지 및 삭제를 말합니다.

 

예를 들어 알고리즘 문제에서 제시하는 제한 시간은 1초라고 하겠습니다.

제출 코드 실행 자체는 0.1초 정도밖에 되지 않지만, 컨테이너가 생성되고 이후에 정지 및 삭제되는 시간이 1초라면 총 1.1초로 RUNTIME_ERROR가 뜨고 사용자는 혼란에 빠질 수밖에 없죠.

실제로 Postman을 통해 테스트해 보았을 때도 바로 확인이 가능했습니다.

그러므로 이것만으로는 정확히 측정할 수 없겠다는 것을 확인하여 다른 방법을 찾아보았습니다.

 

전체 프로세스 실행(Docker 포함)과 실제 테스트 케이스 실행 시간 차이

 

하나의 컨테이너로 각 테스트 데이터 순회하며 측정

위의 코드는 테스트 데이터마다 독립적인 컨테이너에서 실행됩니다.
그렇다면 그냥 하나의 컨테이너로 코드를 반복해서 실행하고, 각 응답이 돌아오는 시간을 서버의 코드에서 측정하는 것을 생각해 봤습니다.
즉 docker exec…. 을 사용하는 것이죠.
어떻게 보면 계속 내렸다가 올렸다가 하는 것보다 성능적으로 이점이 있어 보였지만, 실제로 해보니 채점 시간도 3초 정도 더 느려지는 현상을 겪었습니다.
아쉽지만 제출 코드는 서버 코드처럼 항상 실행되어 있을 수 있는 것이 아니기 때문에 오히려 docker exec에서 오버헤드가 생기고 컨테이너 초기화에서 추가 시간이 발생한 것으로 보였습니다.
또한 각 테스트 케이스 간 완전한 격리가 되지 않을 수도 있다는 위험성도 존재하게 됩니다.

그럼에도 해당 방법을 쓴다 해도 코드 실행 시간만 측정할 수 없다는 것을 알게 되었습니다.

 

Shell에 내장된 time 기능: User + Sys

컨테이너에는 shell이 대부분 있을 것이고 shell에서 제공하는 time 명령을 사용할 수 있다는 것을 알게 되었습니다.

Shell 수준에서 명령을 사용하면 컨테이너의 생성 및 삭제 시간은 측정하지 않게 됩니다.

["bash", "-c", f"time java -Xmx{memory_limit}m -Dfile.encoding=UTF-8 -cp . Main"]
["bash", "-c", f"time python -I -B -S {script_name}"]

각각 Java, Python의 실행 명령어입니다. 해당 명령어는 docker command로 들어갑니다.

이때 time 이라는 명령어가 보이는데, "java..." 또는 "python..."이 실행되고 끝난 후 총 실행 시간을 측정합니다.

그럼 다음과 같은 출력이 발생합니다.

['real\t0m0.373s', 'user\t0m0.342s', 'sys\t0m0.030s']

• Real: 영어로 wall clock time이라고 합니다.
  현재 글을 읽고 계시는 분의 앞에 아날로그 벽 시계가 있다고 가정한 후, 해당 콜이 시작해서 끝날때까지 벽 시계로 시간을 측정한다고 상상해봅시다. 
  컴퓨터에서 실행되는 프로세스는 CPU를 독점적으로 사용하는 것이 아니라, 운영체제의 스케줄러에 의해 다른 프로세스들과 CPU 시간을 번갈아가며 사용합니다.
  프로세스 자신이 실행된 시간뿐 아니라 다른 프로세스가 CPU를 사용한 시간, 그리고 해당 프로세스가 I/O 완료를 기다리며 차단(blocked) 상태에 있었던 시간까지 모두 포함됩니다.
  
  
• User: 해당 프로세스가 사용자 모드 코드(커널 영역 밖)를 실행하는 데 소요된 CPU 시간을 의미합니다. 이는 오직 해당 프로세스가 실제로 CPU를 사용하여 명령을 실행한 시간만을 포함합니다. 다른 프로세스가 CPU를 사용한 시간이나, 해당 프로세스가 차단(blocked) 상태에서 기다린 시간은 이 수치에 포함되지 않습니다.
  
  
• Sys: 프로세스가 커널 내부에서 보낸 CPU 시간(system time)을 의미합니다. 이는 라이브러리 코드처럼 여전히 사용자 영역에서 실행되는 코드가 아니라, 시스템 호출을 통해 커널 모드에서 실제로 CPU를 사용한 시간을 가리킵니다. user 시간과 마찬가지로, 프로세스가 실제로 CPU를 사용한 시간만 포함되며, 다른 프로세스가 사용한 시간은 포함되지 않습니다.

Real time을 기준으로 삼게 된다면 다른 프로세스의 시간까지 포함되기 때문에 올바르지 못한 시간이 측정됩니다.

결론적으로 알고리즘의 시간 복잡도(Time Complexity)와 가장 직접적인 관련이 있는 User time 으로 측정하면 됩니다!

하지만 정확히는 User + Sys 가 실제 실행 시간입니다.
Sys time 은 사용자 모드가 아닌 커널 모드에 대한 시간 측정이기 때문에 입출력에 관한 시간이 측정됩니다.

 

현재 AlgoMarket은 유저가 입출력에 관한 코드도 작성하기 때문에 User + Sys 로 측정하기로 했습니다.

측정된 시간은 위에서 봤던 stderr로 출력됩니다.

stdout과는 별도의 출력이기 때문에 테스트 데이트 입출력에 방해 주지 않고 사용할 수 있습니다.

 

stdout, stderr = process.communicate(input=input_data, timeout=time_limit + 2)

execution_time = _parse_execution_time(stderr)

 

배운점

이번 기회를 통해 Shell에 내장된 time 명령어를 통한 실행 측정 방법과 각 결과가 정확히 어떤 것을 나타내는지 알 수 있었습니다.

또한 계속해서 풀어왔던 알고리즘 문제가 어떻게 측정되었을까에 대한 고민을 해결할 수 있어 시원했습니다.

 

자세히 보니, 현재 국내에서 가장 많이 사용되는 백준(https://www.acmicpc.net/)에서 Java의 Scanner와 BufferedReader의 사용에 따라 시간 초과가 발생하고 안하는 현상이 왜 존재하는지 이제 이해할 수 있었습니다! (또는 Python에서 input()와 sys.stdin.readline())

백준 역시 유저가 입출력에 관한 코드도 작성하기에 User + Sys로 측정하지 않을까 예상됩니다.

 

프로그래머스(https://programmers.co.kr/)처럼 입출력을 받지 않았다면 User time만 사용하여 측정했을 것 같습니다.