Process synchronization

1. race condition

- 여러 주체(스레드, 프로세스, CPU 등)가 접근할 수 있는 공유자원을 서로 다른 주체가 동시에 조작하는 경우(공유변수의 값을 한쪽에서는 증가시키고 다른 쪽에서는 감소시키는 경우 등)가 있을 수 있다. 이러한 상황이 나타나면 프로그램이 사용자가 의도한 것과 전혀 다른 결과를 낼 수 있다. 예를 들어 프로세스 A가 한 변수의 값을 가져가 이를 증가시키는 연산을 하고 결과값을 저장하러 왔는데, 그 사이에 프로세스 B가 그 변수의 값을 감소시키는 연산을 하고 그 결과값을 먼저 저장해놓은 경우가 있을 수 있다. 이 경우 프로세스 A가 더 나중에 그 주소의 변수값을 변경했으므로, 프로세스 B가 그 변수의 값을 감소시킨 사실은 메모리 기록에서 사라지게 된다. 이처럼 공유자원을 놓고 여러 주체가 경쟁하는 상황을 race condition이라 하며, 이러한 상황에서는 각 주체 사이 synchronize가 중요한 문제가 된다.

- 한 주체가 공유자원을 선점했을 때 다른 주체가 그 자원을 요청하더라도 선점한 주체가 그 공유자원을 모두 사용할 때까지 다른 주체의 그 공유자원의 사용을 제한함으로써 race condition을 해결할 수 있다.

2. 커널 관련 race condition 해결

(1) 커널의 CPU 점유 중 interrupt가 발생한 경우

- 커널의 CPU 점유 중 interrupt가 발생하면 커널은 연산을 중단하고 interrupt 처리 루틴을 수행해야 하는데, interrupt 발생 전 커널이 값을 변경하고자 한 변수가 있어 그 값을 읽어온 상태일 때 interrupt가 발생했고 프로세스의 interrupt 처리 루틴 수행 과정에서 먼저 그 값을 변경하는 경우가 있을 수 있다. 이 경우 나중에 커널이 다시 그 값을 변경하면 프로세스가 변경한 값 정보는 사라진다(lost update).

- 이 경우, interrupt가 발생했다 하더라도 이를 무시하고 일단 하던 연산을 계속 수행하게 한 후 그 연산이 끝나면 그제야 interrupt 처리 루틴을 수행하게 하는 식으로 race condition을 해결할 수 있다.

• race condition 상황은 일반적으로 CPU 자체에 대한 접근권을 제한하는 경우는 생각하지 않고 공유자원에 대한 접근을 제한하는 방식으로써 해결하는 경향이 있는데, 이 방법은 특별히 single-processor 환경에서 CPU를 점유 중이던 커널에 CPU 점유권 반납 요구가 있을 때 그 반납을 거부하고 CPU 점유권을 내주지 않는 방식으로서 race condition을 해결한다.

• 프로세스 A가 system call을 해서 커널을 호출해 커널이 어떤 변수의 값을 변경하는 상황에서 timer interrupt가 발생한 경우에, 그 다음 프로세스인 프로세스 B 또한 커널을 호출해 그 변수의 값을 변경하는 경우 또한 이와 유사한 상황으로 볼 수 있다. 이 경우 역시 interrupt를 무시하고 프로세스 A에 관한 처리를 계속 하게 한 후 그것이 끝난 다음 프로세스 B로 context switch 하는 식으로 race condition을 해결할 수 있다.

(2) multiprocessor 환경에서 공유 메모리 상의 커널 영역의 변수를 사용하는 경우

- 커널이 shared memory에 접근할 때마다 그 데이터에 lock을 걸어, 한 CPU가 어떤 데이터에 접근해 그 데이터에 lock을 걸면 다른 CPU는 그 데이터의 값을 변경할 수 없게 한다.

3. critical section으로의 진입 통제를 통한 race condition의 해결

- 한 프로세스가 자신의 코드 중 공유자원에 접근을 하는 부분(critical section)으로 진입을 해야 하는 상황이 됐을 때 그 진입을 통제함으로써 race condition을 해결하는 코드를 구현할 수 있다. 이를 구현하는 방법은 여러 가지가 있으나, 공통적으로 갖추어야 할 조건은 다음과 같다.

(1) 한 프로세스가 critical section 부분을 수행 중이라면 다른 모든 프로세스들은 각자 자신의 critical section에 들어가면 안된다(mutual exclusion).

(2) 모든 프로세스가 critical section을 수행하고 있지 않다면, critical section에 들어가고자 하는 프로세스는 critical section으로 들어갈 수 있어야 한다(progress).

(3) 어떤 프로세스가 critical section 부분을 수행하겠다고 요청을 했다면 그 프로세스는 (다른 프로세스들만 critical section을 수행하여 그 프로세스는 critical section을 수행하지 못하는) starvation에 빠지지 않고 결국 그 critical section을 수행할 수 있어야 한다(bounded waiting).

4. critical section으로의 진입 통제를 통해 race condition을 해결하는 알고리즘들

1) ‘현재 critical section 진입 권한을 갖는 프로세스의 ID’를 변수로 저장하기

- ‘현재 critical section 진입 권한을 갖는 프로세스 ID’를 저장하는 변수를 두고, (1)진입 권한이 있는 프로세스만 critical section에의 진입을 허용하고 그 외의 프로세스는 critical section 앞에서 무한 대기 (2)프로세스는 critical section 수행 후 즉시 그 진입권을 다른 프로세스에 양도하게 하는 알고리즘을 쓸 수 있다.

- 이 알고리즘은 mutual exclusion은 충족하나 progress 조건을 충족하지 않는다. 또, critical section 진입권을 양도받은 프로세스는 critical section을 수행하는 경우가 그리 많지 않은데 양도한 프로세스는 critical section을 수행해야 하는 코드가 많다면 이처럼 ‘critical section 수행 즉시 진입권 양도’ 방식은 전체적으로 비효율적일 수 있다.

2) ‘각 프로세스가 현재 critical section으로 진입을 필요로 하는지’를 저장하는 플래그 배열을 사용하기

(1) 각 프로세스가 현재 critical section으로 진입을 필요로 하는지 여부를 저장하는 플래그 테이블을 만든다.

(2) critical section으로 진입을 필요로 하는 상황이 되면, 그 프로세스의 플래그 값을 true로 변경한다.

(3) 다른 프로세스들의 플래그 값이 어느 하나라도 true인 동안은 critical section 앞에서 무한 대기하고, 다른 모든 플래그 값이 false가 되었을 때 critical section에 진입한다.

(4) critical section을 수행한 후에는 그 프로세스의 플래그 값을 false로 변경한다.

- 이 알고리즘도 mutual exclusion은 충족하나 progress 조건을 충족하지 않는다.

3) 플래그 배열과 critical section 진입권 갖는 프로세스 ID를 저장하는 변수 동시에 사용하기(Peterson’s algorithm)

(1) 각 프로세스가 현재 critical section으로 진입을 필요로 하는지 여부를 저장하는 플래그 테이블을 만든다.

(2) critical section으로 진입을 필요로 하는 상황이 되면 그 프로세스의 플래그 값을 true로 변경하고, critical section 진입권을 다른 프로세스에게 넘긴다.

(3) 현재 critical section 진입권을 갖는 프로세스의 플래그 값이 true인 동안은 현재 프로세스가 critical section 진입이 필요하더라도 critical section 앞에서 무한 대기하고, 다른 프로세스가 플래그 값이 false거나 true더라도 critical section 진입권이 현재 프로세스에게 있다면 critical section에 진입한다.

(4) critical section을 수행한 후에는 그 프로세스의 플래그 값을 false로 변경한다.

- critical section 진입권을 자꾸 양도하다 보면 결국 플래그 값이 true인 프로세스에게 진입권이 양도되는 순간이 반드시 오므로, 이 알고리즘은 progress 조건을 충족한다.

- 이 알고리즘의 경우 대기하는 코드를 while문을 사용해 구현하면 대기하는 시간 동안 외부 변화 여부와 무관하게 쉬지 않고 조건문 충족 여부를 연산하는 ‘busy waiting’ 문제가 있다. (이처럼 critical section으로의 진입에 lock이 걸린 상황에서 busy waiting을 하는 경우 이 lock을 spinlock이라 한다.)

• 이 경우, 대기 상태에 들어간 프로세스들을 blocked 상태로 설정하고 blocked 상태인 프로세스들을 큐에 넣어 대기하게 하여 문제를 해결할 수 있다. (그런데 blocked 상태에서 wakeup 상태로 전환하는 데는 overhead가 커질 수 있으므로, critical section이 짧은 경우라면 그냥 busy waiting이 더 효율적일 수도 있다.)

- 경우에 따라 mutual exclusion 조건을 충족 못할 수 있다. critical section 진입 전 단계의 코드를 (a)플래그값을 true로 변경하고 (b)critical section 진입권을 양도하는 식으로 일일이 구현하면 둘 중 어느 한 작업만 겨우 막 수행했는데 거기서 갑자기 interrupt가 발생해 불완전한 상태에서 다른 프로세스가 critical section으로 들어오는 문제가 발생할 수 있다.

• 이 경우 일련의 과정을 atomic하게 구현하는 코드와 이를 지원하는 하드웨어를 사용하면 간단하게 해결할 수 있다.

5. mutex, semaphore, monitor

1) mutex

- 프로세스가 critical section에 진입하고자 할 때 그 프로세스가 critical section으로의 진입권을 가지고 있는지를 확인해 진입권이 있으면 진입을 허용하고 없으면 막는다는 개념을 mutex라 하며, 이 진입권을 mutex lock이라 한다. (즉, mutex lock을 가진 프로세스만이 critical section으로 진입할 수 있다.)

- mutex lock은 한 순간에 한 프로세스만이 가질 수 있으며, 동시에 둘 이상의 프로세스가 가질 수 없다.

2) semaphore

- 프로세스가 critical section에 진입하고자 할 때 가용자원의 수를 봐서 가용자원이 존재할 때에만 critical section으로 진입을 하고 가용자원이 없다면 critical section으로 진입하지 않고 대기한다는 개념 또는 그 가용자원의 수를 semaphore라 한다.

- 프로세스가 critical section으로 진입할 때 semaphore를 하나 줄이는 연산을 수행하며, critical section을 빠져나올 때 다시 semaphore를 하나 늘리는 연산을 수행한다. (오직 critical section을 빠져나온 다음에만 semaphore를 늘리는 연산을 수행해야 한다.)

- semaphore의 최대 개수를 1로 설정하면 mutex lock과 비슷한 방식으로 코드를 구현할 수 있으나, mutex lock과 달리 semaphore는 어느 한 프로세스가 소유하는 개념이 아니기 때문에 엄밀히 말해 둘은 다르다.

3) monitor

- semaphore를 이용한 구현은 (1)코딩이 어렵고, (2)정확히 작동하는지 확인이 어렵고 (3)코딩할 때 실수하기 쉬운 데 반해 실수했을 때 치명적인 문제가 나타날 수 있다는 단점이 있다. 이는 lock/unlock을 변수를 직접 조작하는 방식으로 구현하기 때문으로, monitor라는 개념을 이용해 구현하면 이러한 단점을 극복할 수 있다. monitor는 다음 두 가지 특징이 있다.

• 프로세스의 코드에서 공유변수를 직접 조작하지 않고 공유변수의 조작은 클래스로 구현한 객체의 내부에서만 구현하고 프로세스의 코드에서는 그 객체의 메서드를 호출하는 식으로만 구현한다.

• 처리할 수 있는 작업부터 하나씩 처리하며, 당장 처리할 수 없는 작업은 대기열에 넣어 대기시킨다. (이의 구현을 위해 객체 내부에서 대기열을 담는 condition 변수를 사용하며, 대기열에 담긴 작업들은 그 condition 변수의 대기 메서드 또는 순서 넘김 메서드를 호출하는 식으로 통제한다.)

6. process synchronization 고전 3문제

1) bounded-buffer 문제

버퍼의 크기가 유한하고 동시에 이 버퍼에 데이터를 추가하는 프로세스(생산자)와 가져가는 프로세스(소비자)가 각각 하나 이상 있을 때, 다음 문제가 발생한다.

(1) 생산자 프로세스 둘이 동시에 같은 버퍼 공간에 데이터를 쓰는 문제, 소비자 프로세스 둘이 동시에 같은 버퍼 공간의 데이터를 가져가 이를 조작하는 문제

• 먼저 버퍼 공간에 데이터를 쓰기/가져가기 시작한 프로세스가 데이터를 쓰기 전에 버퍼에 lock을 걸고, 데이터를 다 쓴/가져간 후 unlock하는 식으로 문제를 해결할 수 있다.

• 이의 구현을 위해 필요한 semaphore는 하나(lock/unlock 여부를 표현하는 binary 변수)면 충분하다.

(2) 생산자 프로세스가 데이터를 쓰려고 보니 버퍼가 가득 차있는 문제, 소비자 프로세스가 데이터를 가져가려고 보니 버퍼가 비어있는 문제

• 빈 버퍼 공간이 생기거나 채워진 버퍼 공간이 하나씩 생길 때까지 각 프로세스가 대기하도록 하여 문제를 해결할 수 있다.

• 이의 구현을 위해 필요한 semaphore는 두 개(채워진 버퍼공간의 수를 기록하는 변수, 빈 버퍼공간의 수를 기록하는 변수)가 필요하다.

2) readers-writers 문제

- 하나의 DB에서 동시에 하나 이상의 프로세스가 데이터를 읽으려 하고(reader 프로세스) 또 동시에 하나 이상의 프로세스가 데이터를 쓰려 할 때(writer 프로세스), reader 프로세스는 둘 이상이어도 문제가 발생하지 않지만, reader 프로세스가 읽는 중 writer 프로세스가 데이터를 쓰려 하거나 writer 프로세스가 둘 이상이면 문제가 발생한다.

- 이 문제는 (1)reader 프로세스가 데이터를 읽는 중에는 DB에 lock을 걸어 writer 프로세스가 데이터를 쓰지 못하게 하고, (2)reader 프로세스가 둘 이상인 경우를 위해 현재 데이터를 읽는 중인 reader 프로세스의 개수를 세서, 그 수가 0이 되기 전까지 writer 프로세스가 데이터를 쓰지 못하게 하는 식으로 해결할 수 있다.

- 이의 구현을 위해 필요한 semaphore는 세 개(DB의 lock/unlock 여부를 표현하는 binary 변수, reader 프로세스의 수를 기록하는 변수, reader 프로세스의 수를 기록하는 변수를 조작할 때 다른 프로세스가 이 변수를 조작하는 것을 막는 lock/unlock 여부를 표현하는 bianry 변수)가 필요하다.

- 그런데 이러한 방식으로 문제를 해결하면, reader 프로세스가 끊임없이 들어와 writer 프로세스는 영원히 데이터를 쓸 수 없는 starvation 문제가 발생할 수 있다. 이 경우 reader 프로세스가 일정 수 이상 데이터를 읽었으면 그 다음에 writer 프로세스가 데이터를 다 쓸 때까지 대기했다가 그 다음으로 대기중이던 reader 프로세스가 데이터를 읽게 하는 식으로 문제를 해결할 수 있다.

3) dining-philosophers 문제

- 원형 테이블에 5명의 철학자가 앉아 있고, 각 철학자의 왼쪽과 오른쪽에는 각각 젓가락이 한 짝씩 있어 테이블 위에 젓가락이 총 5개 있다고 하자. 각 철학자는 양쪽의 젓가락을 하나씩 들어 음식을 먹거나 음식을 먹지 않고 가만히 있을 수 있는데, 젓가락 두 짝이 있어야 음식을 먹을 수 있는데 젓가락은 공유자원이므로 한 철학자가 젓가락을 가져갔다면 다른 철학자는 그 철학자가 젓가락을 다시 내려놓을 때까지 음식을 먹을 수 없다.

- 각 철학자가 음식을 먹기 전에 왼쪽 젓가락과 오른쪽 젓가락을 집어들었을 때 lock을 걸고 음식을 먹은 후에는 unlock하는 알고리즘을 생각해보자. 이 알고리즘은 예를 들어 모든 철학자가 왼쪽 젓가락을 집어든 상황에서는 어떤 철학자도 영원히 음식을 먹을 수 없다는 deadlock 문제가 발생한다.

- 다음 방식으로 문제를 해결할 수 있다.

(1) 철학자가 젓가락 개수보다 적게 테이블에 앉게 하기

(2) 양쪽 젓가락을 모두 집을 수 있는 상황일 때에만 젓가락을 집게 하기

(3) 철학자를 시계 방향 또는 반시계 방향으로 순서대로 번호를 붙인다 할 때, 홀수번 철학자는 왼쪽 젓가락부터 집게 하고 짝수번 철학자는 오른쪽 젓가락부터 집게 하기

- 위 알고리즘 중 ‘양쪽 젓가락을 모두 집을 수 있는 상황일 때에만 젓가락을 집게 하기’ 알고리즘은 다음 방식으로 구현할 수 있다.

(1) 각 철학자의 상태를 먹는 중 / 먹는 차례를 대기 중 / 그 밖의 다른 일을 하는 중 셋으로 구분한다.

(2) i번 철학자가 대기 중 상태가 되었을 때, 그 양쪽 철학자가 모두 먹는 중이 아니라면 i번 철학자에게 젓가락을 집을 권한을 부여한다. 양쪽 철학자 중 어느 하나가 먹는 중이라면 젓가락을 집을 권한을 부여하지 않고 대기한다.

(3) i번 철학자가 음식을 먹은 후에는 i-1번 및 i+1번 철학자가 젓가락을 집을 수 있는 상황인지를 검토하고, 집을 수 있는 상황이라면 젓가락을 집을 권한을 부여한다.

- 이의 구현을 위해서는 공유변수인 각 철학자의 상태 변수, 그리고 그 상태 변수의 lock/unlock 여부를 결정하는 binary 변수, 그리고 각 철학자가 젓가락 집을 권한이 있는지를 저장하는 binary 배열 변수가 필요하다.