병렬 컴퓨터 시뮬레이터

단일 프로세서 시스템에서 여러 프로그램이 '동시에' 실행되는 것처럼 보이지만, 실제로는 하나의 CPU가 프로그램들을 번갈아 가며 각 프로그램의 명령을 몇 개씩 실행한 뒤 다음 프로그램으로 넘어간다. 이러한 시스템에서 최대 열 개의 프로그램이 동시에 실행되는 과정을 시뮬레이션하고, 그 결과로 출력되는 내용을 구하여라.

현재 실행 중인 프로그램을 실행 중(running) 상태라 하고, 실행을 기다리는 모든 프로그램을 준비(ready) 상태라 한다. 하나의 프로그램은 최대 200개의 문장으로 이루어지며, 한 줄에 한 문장씩 쓰이고 마지막은 end 문장으로 끝난다. 사용할 수 있는 문장은 다음과 같다.

<변수>는 하나의 소문자 알파벳이고, <상수>는 1000 미만의 부호 없는 십진 정수이다. 시스템에는 변수가 26개뿐이며 모든 프로그램이 이를 공유한다. 따라서 한 프로그램에서의 대입이 다른 프로그램이 출력할 값에 영향을 준다. 모든 변수의 초깃값은 0이다.

각 문장은 정수 단위의 실행 시간을 갖는다. 실행 중인 프로그램은 퀀텀(quantum) 이라 부르는 일정 시간 동안 명령을 계속 실행한다. 퀀텀이 만료되면 준비 상태의 다른 프로그램이 선택되어 실행된다. 퀀텀이 만료되는 순간 실행 중이던 명령은 끝까지 완료된다.

프로그램들은 선입선출(FIFO) 방식의 준비 큐(ready queue) 에서 대기한다. 준비 큐의 초기 순서는 입력에 주어진 프로그램 순서와 같다. 다만 이 순서는 lock과 unlock의 실행으로 바뀔 수 있다.

lock과 unlock은 프로그램이 다루는 변수에 대한 상호 배타적 접근을 얻기 위해 사용한다. 이 둘은 항상 하나 이상의 문장을 감싸는 쌍으로 나타나며, lock이 항상 대응하는 unlock보다 먼저 오고 쌍은 절대 중첩되지 않는다. 어떤 프로그램이 lock을 성공적으로 실행하면, 그 프로그램이 대응하는 unlock을 실행하기 전까지 다른 어떤 프로그램도 lock을 성공적으로 실행할 수 없다. 실행 중인 프로그램이 이미 lock이 걸려 있는 상태에서 lock을 실행하려 하면, 그 프로그램은 블록 큐(blocked queue) 의 맨 뒤로 들어가고 남은 퀀텀을 모두 잃는다. unlock이 실행되면 블록 큐의 맨 앞에 있는 프로그램(있다면)이 준비 큐의 맨 앞으로 옮겨지며, 그 프로그램이 실행할 첫 문장은 앞서 실패했던 lock이 된다. 상호 배제 규약을 지키는 것은 전적으로 프로그램들의 책임이다. lock/unlock 쌍이 없는 프로그램은 다른 프로그램들이 올바르게 잠금을 사용하더라도 원하는 어떤 변수든 마음대로 바꿀 수 있다.

첫째 줄에는 공백으로 구분된 일곱 개의 정수가 주어진다. 순서대로, 이어지는 프로그램의 개수, 위에 나열된 다섯 가지 문장 종류 각각의 실행 시간(대입, print, lock, unlock, end 순), 그리고 한 퀀텀을 이루는 시간 단위의 수이다.

나머지 입력은 위 규칙에 맞게 올바르게 작성된 프로그램들이다. 모든 문장은 줄의 첫 번째 칸에서 시작하며, 문장 안에 나타나는 공백은 무시한다. 각 프로그램은 입력에서의 위치에 따라 식별 번호를 갖는다(첫 번째 프로그램은 1, 두 번째는 2, …).

시뮬레이션이 진행되는 동안 실행되는 print 문장이 만들어내는 출력을, 실행되는 순서대로 출력한다. print 문장이 실행될 때마다 프로그램의 식별 번호, 콜론, 공백, 그리고 해당 변수의 값을 출력한다. 서로 다른 print 문장의 출력은 각각 다른 줄에 나타난다.