OS: 프로세스 동기화 알고리즘 (1)

1. 동기화란?
 동기화란 협력하는 프로세스 사이의 실행 순서 규칙을 보장하는 것을 말합니다. 예를 들어서 프로세스 A와 프로세스 B가 어떤 한 공유 영역을 두고 멀티스레딩으로 실행이 된다고 한다면, 그 스레드들이 공유 영역에 동시에 접근하려고 할 때 순서를 정해주는 것을 말합니다.

 그럼 왜 스레드마다 접근 순서를 정해줘야 할까요? 그것은 바로 '경쟁 상태' 때문입니다. 경쟁 상태(Race Condition)는 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말합니다. 그러니까 어떤 스레드가 공유 영역의 데이터에 동시에 접근하려고 할 때 일정한 순서를 정해주지 않으면 각각 다른 결과값을 나타낼 수 있는 것을 말합니다.

 예를 들어 프로세스 A와 B가 있고 공용 데이터 value = 5가 있습니다. 그리고 각각의 코드는

A:
1) value--;
2) printf("%d",value);

B:
3) value++;
4) printf("%d",value);

이렇게 짜여져 있다고 봅시다. 이 때 두 프로세스는 순서에 따라서 다른 결과값을 가지게 됩니다. 순서가 1, 2, 3, 4 순서일 때는 프로세스 A에서는 4가 출력될 것이고, 프로세스 B에서는 5가 출력될 것이죠. 하지만 순서가 3, 4, 1, 2라면 프로세스 A에서는 5가 출력될 것이고, 프로세스 B에서는 6이 출력될 것입니다. 이러한 경우를 막기 위해서 순서를 정해주는 것이 필요합니다.

 위의 코드에서 value를 사용하는 문장과 같이 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부를 보고 '임계영역(Critical Section)'이라고 합니다. 그리고 이런 것들을 해결하기 위해서 사용되는 알고리즘을 '상호배제(Mutual Exclusion)'이라고 합니다.

2. 동기화를 위한 조건
 동기화를 위해서는 3가지 조건이 필요합니다.

• 상호배제 : 한 프로세스가 임계영역에서 수행 중일 때는 다른 프로세스는 임계영역에서 수행할 수 없다.
• 진행 : 임계영역에 수행하는 프로세스가 없고 여러 프로세스가 임계영역으로 들어가려고 한다면 임계영역으로 들어갈 프로세스가 선정되어야 한다.
• 제한된 대기 : 한 프로세스가 임계영역을 요청하였다면 유한시간 대기 후에는 임계영역에 진입해야 한다.

이러한 조건을 갖추면서 동기화 문제를 해결하기 위해서 많은 알고리즘들을 만들어 왔습니다. 다음 글에서는 그 알고리즘들에 대해서 세세하게 알아보도록 하겠습니다.