교착 상태 판정

동시성 환경에서 교착 상태는 둘 이상의 스레드가 서로 상대가 자원을 놓기를 기다리며 아무도 더 진행하지 못하는 상황이다. 여러 스레드가 같은 명령어 열을 동시에 실행할 때 교착 상태가 생길 수 있는지 판정해야 한다.

명령어 열은 문자 u와 숫자 0부터 9까지로 이루어지고, 문자 하나가 명령어 하나다. 스레드 10개가 같은 명령어 열 하나를 실행한다. 각 스레드는 열의 처음부터 주어진 순서대로 실행하며, 명령어를 모두 실행하면 끝난다.

L0부터 L9까지 락 10개를 모든 스레드가 공유한다. 숫자 $k$는 락 L$k$를 획득하는 명령어다. 어떤 스레드가 L$k$를 획득하면 u 명령어로 풀기 전까지 그 스레드가 계속 쥐고 있다. 락을 쥐고 있는 동안에는 이미 그 락을 획득한 스레드까지 포함해 어떤 스레드도 같은 락 L$k$를 새로 획득하지 못한다.

정확히는 모든 스레드가 끝날 때까지 다음을 반복한다.

1. 아직 끝나지 않은 스레드 하나를 임의로 고른다.
2. 고른 스레드가 아직 실행하지 않은 다음 명령어를 실행하려 한다.
   • 다음 명령어가 숫자 $k$이고 L$k$를 쥔 스레드가 없으면, 명령어 $k$를 실행하고 L$k$를 획득한다.
   • 다음 명령어가 숫자 $k$인데 이미 어떤 스레드가 L$k$를 쥐고 있으면, 명령어 $k$는 실행되지 않는다.
   • 다음 명령어가 u이면 그 명령어를 실행하고, 그 스레드가 쥔 락을 모두 푼다.

여러 단계를 실행하다 보면 끝나지 않은 스레드의 다음 명령어가 모두 이미 쥐여 있는 락을 획득하는 명령어인 상황에 빠지기도 한다. 이런 상황이 한 번 생기면 어떤 스레드를 골라도 명령어가 더는 실행되지 않는다. 이 상황을 교착 상태라고 한다.

실행 순서를 어떻게 잡아도 교착 상태에 이르지 않는 명령어 열이 있다. 이런 명령어 열을 안전하다고 한다. 그렇지 않은 경우, 즉 교착 상태로 이어지는 실행 순서가 하나라도 있으면 그 명령어 열은 안전하지 않다. 주어진 명령어 열이 안전한지 판정하는 프로그램을 작성하라.

입력은 데이터 집합 최대 50개로 이루어지고, 각 데이터 집합의 형식은 다음과 같다.

n
s

$n$은 명령어 열의 길이이고 $s$는 그 열을 나타내는 문자열이다. $n$은 10,000 이하의 양의 정수다. $s$의 각 문자는 숫자 0부터 9 중 하나이거나 u이고, $s$는 항상 u로 끝난다.

입력의 끝은 0 하나만 있는 줄로 나타낸다.

데이터 집합마다 명령어 열이 안전하면 SAFE를, 안전하지 않으면 UNSAFE를 한 줄에 출력한다.

명령어 열 01u10u는 교착 상태가 될 수 있다. 한 스레드가 앞의 네 명령어 01u1을 실행하면 그 스레드는 락 L1 하나만 쥐고 있다. 이때 다른 스레드가 첫 명령어 0을 실행하면 그 스레드가 L0을 획득한다. 그러면 첫 번째 스레드는 두 번째 스레드가 쥔 L0을 획득하려 하고, 두 번째 스레드는 첫 번째 스레드가 쥔 L1을 획득하려 한다. 교착 상태다.

→ →

그림 1. 01u10u가 안전하지 않은 이유.

반면 201u210u는 안전하다. 한 스레드가 201u21까지, 다른 스레드가 20까지 실행하면 교착 상태처럼 보이지만, 두 스레드가 L2를 동시에 쥘 수 없으므로 이런 상황은 생기지 않는다.