비동기 예외

ACM(Asynchronous Calculating Machine)은 여러 스레드를 동시에 실행하는 기계다. 이 기계에서 프로그램을 시뮬레이션해 각 스레드가 언제 끝나는지 구하라. 결과를 보면 경쟁 상태나 교착 상태 같은 스레드 동작이 드러난다.

기계에는 정해진 개수의 처리 장치와 전역 스케줄러 하나가 있다. 스케줄러는 모든 스레드를 관리하고, 스레드를 처리 장치에 배정하며, 세마포어를 관리한다. 모든 스레드는 RUNNING, READY, WAITING 중 한 상태에 있다. 스케줄러는 스레드 큐를 하나 두고 READY 상태인 스레드를 들어온 순서대로 담는다.

프로그램과 스레드

프로그램은 코드 블록의 목록이다. 코드 블록은 한 줄에 하나씩 적힌 연산의 목록이고, 마지막 줄은 항상 end다. 스레드는 코드 블록 하나의 연산만 위에서 아래로 실행하며, end에 닿거나 다른 스레드가 종료 신호를 보낼 때까지 이어 간다. 스레드 번호는 생성 순서대로 붙어서 n번째로 생성된 스레드의 번호는 n이다. 시뮬레이션은 1번 스레드에서 시작하고, 이 스레드는 입력의 첫 코드 블록을 1번 처리 장치에서 실행한다.

연산

대괄호로 묶은 낱말은 인자다. [clock], [amount], [loop count]는 0 이상 1000 이하의 정수다. [thread-var], [semaphore name], 코드 블록 이름은 알파벳으로만 이루어진 길이 200 이하의 문자열이고 대소문자를 구분한다.

compute [clock]: [clock] 클록만큼 계산한다. T클록만 쓰고 중단되면 다시 실행될 때 남은 [clock] - T 클록을 쓴다.
[thread-var] <- forkR [code block]: [code block]을 실행하는 네이티브 스레드를 만들고 그 번호를 [thread-var]에 저장한다. 네이티브 스레드는 어떤 스레드와도 동시에 실행될 수 있다.
[thread-var] <- forkI [code block]: [code block]을 실행하는 가상 스레드를 만들고 그 번호를 [thread-var]에 저장한다. 가상 스레드는 부모 스레드와 자원을 공유하므로, 노는 처리 장치가 있어도 둘은 절대 동시에 실행되지 않는다. 이 제약은 forkI의 부모 자식 관계로 직접 또는 간접으로 이어진 모든 스레드 쌍에 적용된다. 그렇게 이어진 스레드는 한 그룹을 이루고, 한 그룹에서 RUNNING 상태인 스레드는 언제나 최대 하나다. forkR로 만든 스레드는 자기 혼자 있는 새 그룹을 열고, 1번 스레드도 혼자 있는 그룹에 속한다.
yield: RUNNING 상태에서 물러나 스레드 큐의 맨 뒤로 간다.
killThread [thread-var]: [thread-var]에 저장된 번호의 스레드에 종료 신호를 보낸다.
lock [semaphore name] [amount]: 세마포어에 [amount]만큼 요청한다.
unlock [semaphore name] [amount]: 세마포어에 [amount]를 더한다. 값은 초깃값보다 커질 수 있고, 이 연산으로 스레드가 막히는 일은 없다.
loop [loop count]: 이 줄과 짝이 되는 next 사이의 연산을 [loop count]번 실행한다. 한 코드 블록 안에서 반복문을 중첩할 수 있다. 횟수가 0이면 짝이 되는 next 바로 다음으로 건너뛴다.
next: 같은 코드 블록에 있는 짝 loop의 본문이 끝나는 자리다.
end: 스레드를 끝낸다. 코드 블록의 마지막 줄에만 나온다.

이미 값이 들어 있는 스레드 변수에 새 번호를 저장하면 이전 번호는 덮어써져 사라진다. 스레드 변수는 값을 저장한 스레드의 것이라서, 같은 코드 블록을 실행하는 두 스레드는 서로 다른 값을 따로 유지한다.

세마포어

세마포어마다 요청이 들어온 순서대로 늘어선 대기 큐를 따로 둔다. lock [semaphore name] [amount]는 그 대기 큐가 비어 있고 값이 [amount] 이상일 때만 곧바로 성공해서 값에서 [amount]를 뺀다. 이때 스레드는 RUNNING 상태 그대로 다음 연산으로 넘어간다. 그렇지 않으면 스레드는 WAITING 상태가 되어 그 대기 큐의 맨 뒤에 선다. 지금 값이 요청량을 채우더라도 마찬가지다.

unlock으로 세마포어 값이 커지거나 취소된 요청이 대기 큐에서 빠지면, 스케줄러는 그 대기 큐의 맨 앞을 살핀다. 맨 앞 요청을 현재 값으로 채울 수 있는 동안 스케줄러는 요청량만큼 값을 빼고, 그 스레드를 READY로 바꿔 스레드 큐 맨 뒤에 넣는다. 값으로 채울 수 없는 첫 요청에서 멈추므로, 같은 세마포어를 먼저 요청한 스레드를 나중에 요청한 스레드가 앞지르는 일은 없다. 같은 시점에 풀린 스레드는 요청한 순서대로 스레드 큐에 들어간다.

종료 신호

killThread [thread-var]는 대상 스레드에 즉시 작용하고, 이 연산으로 세마포어 값은 바뀌지 않는다. 변수에는 같은 코드 블록의 앞선 forkR이나 forkI가 저장한 번호가 들어 있다.

대상이 WAITING이면 lock 요청을 취소해 그 세마포어의 대기 큐에서 빼고, 대상은 READY가 되어 스레드 큐 맨 뒤로 간다. 그 뒤 그 세마포어의 대기 큐를 unlock 다음과 똑같이 살핀다.
대상이 RUNNING이면 현재 시간 단계에서 끝나고 처리 장치를 비운다.
대상이 READY면 스레드 큐에 그대로 남아 있다가, 처리 장치에 배정되어 실행 차례가 오는 순간 끝난다.
대상이 이미 끝났으면 아무 일도 일어나지 않는다.

종료 신호를 받은 스레드는 연산을 더 실행하지 않는다.

시뮬레이터

시간 단계는 0부터 센다. 시뮬레이터는 0, 1, ..., S 단계를 이 순서로 실행하고, S는 그 테스트 케이스의 시간 단계 수다. 한 단계는 다음과 같이 진행한다.

단계 번호가 타임 슬라이스의 배수면, 처리 장치가 번호가 작은 것부터 차례로 RUNNING 스레드를 READY로 바꿔 스레드 큐 맨 뒤에 넣는다. 그다음 스케줄러가 스레드를 배정한다.
스레드 배정: 노는 처리 장치가 있는 동안 스케줄러는 스레드 큐를 앞에서부터 훑어, 그룹에 RUNNING 스레드가 없는 첫 스레드를 큐에서 빼고 노는 처리 장치 중 번호가 가장 작은 곳에 올린다. 모든 처리 장치가 차거나 올릴 수 있는 스레드가 없으면 멈춘다. 배정은 1번 단계에서만 하지 않고, 처리 장치가 비거나 스레드가 스레드 큐에 들어올 때마다 한다.
실행: 처리 장치를 번호가 작은 것부터 차례로 본다. 지금 보는 처리 장치의 스레드에 남은 계산 시간이 있으면 그 장치는 이 단계에서 아무 일도 하지 않는다. 그렇지 않으면 그 스레드가 연산을 잇달아 실행하고, 횟수가 양수인 compute, yield, 막히는 lock, end만 실행을 멈춘다. 나머지 연산은 시간을 쓰지 않는다. 스레드가 처리 장치에서 내려가면 스케줄러가 다시 배정하고, 지금 보는 처리 장치에 올라온 스레드는 이 단계에서 이어서 실행한다. 한 스레드는 한 시간 단계에 최대 한 번만 실행하므로, yield했거나 대기에서 풀린 스레드는 같은 단계에서 다시 실행하지 않는다. 이미 지나온 처리 장치는 같은 단계에서 다시 보지 않는다.
그 단계의 연산이 끝나면, RUNNING 상태이면서 남은 계산 시간이 양수인 모든 스레드의 계산 시간을 1씩 줄인다.

스레드가 끝난 시각은 end를 실행한 시간 단계, 또는 종료 신호로 끝난 시간 단계다. 살아 있는 스레드 수는 생성됐고 아직 끝나지 않은 스레드의 수다. 스레드를 새로 만들어 이 수가 기계의 수용량을 넘으면 시뮬레이션은 그 자리에서 멈춘다. 한 테스트 케이스에서 모든 스레드가 실행하는 연산 줄의 총수는 100,000을 넘지 않는다.

비동기 예외

문제

프로그램과 스레드

연산

세마포어

종료 신호

시뮬레이터

입력

출력