잠금 관리자

데이터베이스 관리 시스템(DBMS)의 잠금 관리자(Lock Manager) 를 구현한다.

잠금(lock)은 여러 트랜잭션이 같은 데이터 항목에 동시에 접근하는 것을 제어한다. 이 DBMS는 단순하여 공유(Shared, S) 와 배타(Exclusive, X) 두 가지 잠금 모드만 사용한다. 각 잠금 요청은 잠금 모드(S 또는 X), 트랜잭션 번호, 데이터 항목 번호로 이루어진다. 같은 데이터 항목에 대해서도 서로 충돌하지 않는 한 여러 개의 잠금을 동시에 허가할 수 있다.

같은 데이터 항목에 대한 두 잠금은 다음 조건을 모두 만족할 때 충돌한다.

• 서로 다른 트랜잭션에 속하고,
• 둘 중 적어도 하나가 배타(X) 모드이다.

아주 단순한 잠금 관리자를 작성한다. 어떤 잠금 요청은 해당 데이터 항목에 대해 이미 허가된 잠금들과 충돌하지 않을 때에만 허가된다. 한 번 허가된 잠금은 절대 해제되거나 변경되지 않는다. 어떤 요청이 이전에 허가된 잠금과 충돌하여 거부되면, 그 요청을 보낸 트랜잭션은 차단(blocked) 되고, 그 트랜잭션이 이후에 보내는 모든 요청은 무시된다.

입력은 여러 개의 잠금 요청으로 이루어지며, 각 요청은 한 줄에 하나씩 주어진다. 각 요청의 형식은 다음과 같다.

MODE TRID ITEM

• MODE는 요청하는 잠금 모드를 나타내는 대문자 한 글자로, S 또는 X이다.
• TRID는 트랜잭션 번호, ITEM은 데이터 항목 번호이다. 둘 다 $0$보다 큰 정수이며, 각각 최대 $9$자리 십진수이다.

요청은 최소 $1$개, 최대 $10000$개이다. 마지막 요청 다음 줄에는 문자 # 하나만 있는 줄이 온다.

입력의 모든 요청을 순서대로 처리한다. 각 요청마다 그 요청에 대한 응답을 한 줄에 하나씩 출력한다. 가능한 응답은 다음과 같다.

• GRANTED — 이 요청이 이미 허가된 어떤 잠금과도 충돌하지 않아 허가된다.
• DENIED — 이 요청이 이미 허가된 어떤 잠금과 충돌하여 거부되며, 이로 인해 요청한 트랜잭션이 차단된다.
• IGNORED — 요청한 트랜잭션이 이 요청 이전의 어떤 요청에서 이미 차단되었다.

응답은 위와 정확히 같은 형태의 대문자로 출력한다. 마지막 응답 뒤에는 임의 개수의 빈 줄이 올 수 있다.