출처 : 공룡책과 ostep
경쟁 조건, 임계 영역
여러개의 프로세스가 동일한 데이터에 접근했을 때, 접근이 일어난 순서에 따라서 결과값이 달라지는것을 경쟁조건, Race condition이라고 한다.
Critical section problem은 프로세스들이 협력적으로 데이터를 공유할 수 있도록 그들의 활동을 Synchronize하는 데 사용할 수 있는 프로토콜을 설계하는 것이다.
- 여러 프로세스들에서 공유 데이터에 접근하는 부분의 코드를 임계영역으로 정의한다.
- 그리고 해당 영역에 접근하기 위해 permission을 요구하도록 한다.
- 이 요청을 보내는쪽을 entry section이라고 한다.
- 그리고 entry section은 exit section으로 끝나야 한다.
- 마지막으로 exit section 이후에도 남아있는 코드를 remainder section이라 한다.
do {
// entry section (진입 구역)
// critical section (임계 구역)
// exit section (종료 구역)
// remainder section (나머지 구역) - 임계구역과 관련없는 작업
} while (true);
- Critical section problem은 아래 세가지를 만족해야 한다.
- Mutual exclusion : 특정 프로세스가 임계영역 코드를 실행중이라면 다른 프로세스는 임계영역 코드를 실행할 수 없다.
- Progress : 만약 아무 프로세스도 임계영역을 실행중이지 않고, 어떤 프로세스가 임계영역 진입을 원한다면, remainder영역을 실행중이지 않은 프로세스들만 어떤 프로세스가 다음이 될지에 대한 결정에 참여 할 수 있다. 그리고 이러한 결정은 무기한 지연되어서는 안된다.
- Bounded waiting : 한 프로세스가 자신의 임계 구역에 진입 요청을 한 후, 그 요청이 승인되기 전까지 다른 프로세스들이 자신의 임계 구역에 진입할 수 있는 횟수에 대한 한계 또는 제한이 존재한다.
참고로 싱글코어 프로세서라면 세상 쉬운 문제이다. 공유자원을 수정할 때는 인터럽트를 막아버리면 된다.
또한 이 문제는 Preemptive Kernels에서 발생한다. Nonpreemptive Kernels는 커널에 다른프로세스가 진입해있다면 커널을 양보할 때 까지 기다린다
Peterson’s solution
int turn;
boolean flag[2];
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
/* do nothing (wait) */
;
/* critical section */
flag[i] = false;
/* remainder section */
}
- turn : 지금 임계구역에 진입이 허가된 프로세스
- flag[] : 임계구역 진입이 준비된 프로세스 일단 flag로 진입의사를 알리고 j프로세스에게 양보한다. 그리고 j의 진입의사가 실제로 있었다면, 루프를 돌며 기다린다. 결국 turn을 마지막에 바꾼 프로세스가 상대 프로세스의 임계영역 진입을 기다린다.
프로세스 i: flag[i] = true, turn = j
프로세스 j: flag[j] = true, turn = i
이제 이 솔루션이 Mutual Exclusion, Progress, Bounded waiting을 만족하는지 확인해야한다.
Mutual Exclusion :
- 프로세스가 임계영역에 진입하려면
flag[j] == false || turn == i을 만족해야함 - 동시에 두 프로세스가 진입하려 한다면
flag[i], flag[j]는 true - 이 두가지가 의미하는건 두 프로세스는 동시에 while문을 수행하고 있을 수 없다는 것이다. (turn값이 그것을 방지)