배타적 접근

동시성 프로그래밍에서 중요한 문제 하나는 여러 스레드가 공유 자원에 배타적으로 접근하도록 보장하는 것이다. 이것은 상호 배제(Mutual Exclusion) 프로토콜이라고도 불린다. 동시에 실행되지 않도록 보호해야 하는 코드를 임계 구역(critical section, CS)이라고 한다. CS로의 접근을 조율하기 위해 애플리케이션의 스레드들은 서로 정보를 주고받는 공유 변수 집합을 사용한다. 이 공유 변수들은 애플리케이션 코드가 사용하는 다른 모든 변수와는 구별된다. 실제로 상호 배제 프로토콜은 두 개의 메서드 enterCS와 exitCS로 구현된다. 애플리케이션이 CS 안에서 어떤 코드를 실행해야 할 때 enterCS를 호출하고, CS를 실행한 뒤 exitCS를 호출한다.

상호 배제 프로토콜을 이론적으로 분석하려면 실행 중인 애플리케이션을 전체로서 고려해야 한다. 애플리케이션의 각 스레드는, CS와 무관한 어떤 작업(이를 비임계 구역(non-critical section, NCS)이라 한다)을 반복적으로 수행한 다음 enterCS를 호출하고 CS를 실행한 뒤 exitCS를 호출하며, 그 뒤 이 반복을 다시 시작하는 무한 루프로 표현된다. NCS와 CS 내부의 코드는 중요하지 않다. 그것은 프로토콜과 관련된 어떤 연산도 수행하지 않으며 프로토콜이 사용하는 공유 변수를 변경하지 않는 것으로 간주한다.

우리는 두 개의 스레드가 동시에 실행되는 시스템을 고려한다. 스레드들은 상호 배제 프로토콜을 구현하기 위해 공유되는 1비트 변수 집합을 사용한다. 각 변수는 0 또는 1의 값을 저장할 수 있으며, 하나의 명령으로 읽거나 쓸 수 있다. 공유 변수는 0으로 초기화된다. 각 스레드는 다음에 실행할 명령을 가리키는 지역 포인터(IP)를 가진다. 실행은 코드의 맨 위에서 시작한다. 실행의 각 단계에서 두 스레드 중 하나가 임의로 선택되어 명령 하나를 실행하고, 그 뒤 자신의 IP를 다음에 실행할 명령으로 바꾼다. 이 무한한 단계의 열을 히스토리(history)라고 한다. 히스토리는, 두 스레드가 모두 무한히 많은 단계를 실행하거나, 또는 한 스레드만 그렇게 하고 다른 스레드는 유한한 수의 단계를 밟은 뒤 IP가 NCS에 있는 상태로 멈추는 경우에 한하여 합법적(legal)이라고 한다.

아래 표에는 상호 배제 프로토콜을 구현하려 시도하는 여러 알고리즘이 의사코드로 담겨 있다. 이 의사코드에서 id는 첫 번째 스레드에 대해 0, 두 번째 스레드에 대해 1이다. 변수 want[0], want[1], turn은 상호 배제 프로토콜을 구현하기 위해 스레드 간에 공유된다. "+"로 표시된 줄은 enterCS를, "-"로 표시된 줄은 exitCS를 구현한다. NCS()와 CS() 줄은 각각 비임계 구역과 임계 구역 안에서 동작하는 어떤 코드의 자리표시자이며 이 문제와는 무관하다.

알고리즘 1	알고리즘 2	알고리즘 3
```
loop forever
NCS()

loop while
(turn == 1 - id) CS()

turn <- (1 - id) end loop | loop forever NCS()

want[id] <- 1
loop while
(want[1 - id] == 1) CS()

want[id] <- 0 end loop | loop forever NCS()

want[id] <- 1
turn <- (1 - id)
loop while
(want[1 - id] == 1 and
```
turn == 1 - id)
```
CS()

want[id] <- 0 end loop


주어진 알고리즘이 다음 세 가지 중요한 성질을 만족하는지 판별하는 것이 과제이다.

- 어떤 합법적 히스토리에서도 CS가 두 스레드에 의해 동시에 실행되지 않으면(즉, 두 스레드의 IP가 동시에 CS에 있는 단계가 존재하지 않으면) 그 알고리즘은 *상호 배제(mutual exclusion)*를 만족한다.
- 모든 합법적 히스토리가 무한히 많은 CS 실행을 가지면 그 알고리즘은 *교착 상태 없음(deadlock freedom)*을 만족한다.
- 어떤 합법적 히스토리에서도 무한히 많은 단계를 실행하는 스레드가 무한히 많은 CS 실행을 가지면 그 알고리즘은 *기아 상태 없음(starvation freedom)*을 만족한다.

상호 배제 성질 자체는 자명하게 만족시킬 수 있다. 아무 일도 하지 않고 영원히 반복하기만 하는 알고리즘도 그것을 만족한다. 위의 예시 알고리즘들은 모두 상호 배제를 만족하지만, 처음 두 개는 교착 상태 없음을 달성하지 못한다. (원래 Gary Peterson이 고안한) 알고리즘 3은 세 성질을 모두 만족한다.

입력의 첫 줄에는 두 정수 m1과 m2가 주어진다. 여기서 mi는 i번째 스레드의 코드 줄 수이다(2 ≤ mi ≤ 9). 그 뒤로 첫 번째 스레드의 코드 m1줄과 두 번째 스레드의 코드 m2줄이 이어진다.

각 스레드의 코드는 한 줄에 하나의 명령을 담는다. 명령은 1부터 mi까지의 정수 줄 번호로 시작하고(줄은 오름차순으로 번호가 매겨지며 가독성을 위해 포함된다), 그 뒤에 명령 니모닉, 그리고 명령 인자 목록이 이어지며 모두 공백으로 구분된다. 명령의 마지막 인자들은 다음에 실행할 명령의 줄 번호(NIP — 1부터 mi까지)를 나타낸다. 스레드 간에 공유되는 변수는 A, B, C 세 개이다. 명령 니모닉은 다음과 같다.

NCS — 비임계 구역 자리표시자. 인자는 NIP 하나이다.
CS — 임계 구역 자리표시자. 인자는 NIP 하나이다.
SET — 공유 변수에 값을 쓴다. 인자는 v, x, g 세 개이며, v는 쓸 변수(A, B, C 중 하나), x는 쓸 값(0 또는 1), g는 NIP이다.
TEST — 공유 변수의 값을 읽어 검사한다. 인자는 v, g0, g1 세 개이며, v는 읽을 변수(A, B, C 중 하나), g0은 변수의 값이 0일 때의 NIP, g1은 변수의 값이 1일 때의 NIP이다.

NCS와 CS는 각 스레드의 코드에 정확히 한 번씩 나타난다. 코드가 반드시 단순한 루프를 나타내는 것은 아니지만, 한 스레드에 의한 CS와 NCS의 실행이 번갈아 나타나는 것이 보장된다. 즉, 모든 합법적 히스토리에서 한 스레드의 두 CS 실행 사이에는 항상 같은 스레드의 NCS 실행이 있고, 반대로 한 스레드의 두 NCS 실행 사이에는 같은 스레드의 CS 실행이 있다.

배타적 접근

문제

입력

출력