Race Condition(경쟁 상태)이 발생하는 사례란?

* 본 내용은 운영체제를 공부하며 추후 복습하기 위해 포스팅하는 게시물입니다.

 

Race Condition(경쟁 상태)

- 특정 변수의 값을 증가시키거나 감소시키는 작업은 여러 개의 명령어로 구성되어 있어, 서로 다른 프로세스가 동일한 변수를 동시에 증가시키거나 감소 시키는 작업 시 순서가 예상과 다르게 작동하면 결과값에 영향을 줄 수 있는 상태를 의미

 

* 프로그램적으로 해결할 수 있는 조건

1) Mutual Exclusion

 - 프로세스가 Critical Section 부분을 수행 중일 때 다른 프로세스가 Critical Section에 진입하면 안됨

 

2) Progress

 - Critical Section을 수행하는 부분이 없다면 프로세스를 진입할 수 있게 해줘야함

 

3) Bounded Waiting

 - 프로세스가 Critical Section에 진입하려 요청 할 때 무한정 대기하지 않게 유한 대기해야함

ex) 3개의 서로 다른 프로세스가 존재하며 3개의 프로세스가 critical section에 진입하기 위해 요청했지만 1개의 프로세스를 제외한 나머지 프로세스가 서로 교대하며 critical section에 진입한다면 1개의 프로세스가 critical section에 진입할 수 없음

 

Race Condition이 발생하는 여러 케이스가 존재하지만 이번 게시물에서는 대표적인 케이스와 이를 해결하기 위한 알고리즘, Semaphore, Monitor에 대해 알아본다.

 

1. OS에서 Race Condition이 발상하는 케이스

1) 커널안에 코드를 수행하는 중 인터럽트 발생하는 케이스

•  커널안에 있는 변수를 증가시키는 중 인터럽트가 발생하여 인터럽트 처리 함수에서는 해당 변수를 감소시킬 때 변수의 결과값에 문제가 발생(인터럽트별 처리 함수의 코드는 커널에 존재함)
• 사용자 프로세스는 해당 프로세스에 할당받은 메모리에만 존재할 수 있지만 커널은 서로 다른 프로세스가 공유하기 때문에 발생
• 해결법 : 작업을 할 때 인터럽트 발생하더라도 작업이 완료된 후 인터럽트가 발생하도록 처리순서를 부여

 

2) 프로세스가 System Call를 호출하여 커널 모드로 수행 중일 때 Context Switch가 발생하는 케이스

• 사용자 프로세스가 System Call를 호출하면 커널 모드로 커널안에 존재하는 변수를 수정할 수 있다. 할당된 CPU 사용시간이 만료되면 Context Switch가 발생하는데 새롭게 CPU를 할당받은 사용자 프로세스가 이전 프로세스와 동일한 System Call를 호출하여 수정하고 있던 변수에 대한 작업을 수행할 때 결과적으로 변수값에 문제가 발생하는 케이스
• 해결법 : 사용자 프로세스가 System Call를 호출하여 커널모드의 작업을 완료한 후 종료될 때 Context Switch가 발생할 수 있게 한다. 즉, 커널모드에 있다면 CPU의 제어권을 빼앗지 않음

 

3) 여러 프로세스의 공유 메모리 내 커널 안 변수에 접근하는 케이스

• CPU가 여러 개인 시스템에서 공유 메모리 속 데이터를 여러 프로세스가 접근할 때 발생하는 케이스 
• 해결법 : 커널 안 변수에 접근할 때 lock/unlock을 걸어 매 순간 변수에 접근하는 프로세스는 1개로 한정한다. 

Race Condition이 발생하지 않고 공유데이터에 접근하기 위한 알고리즘의 발전은 Algorithm 1, Algorithm 2, Piterson's  Algorithm으로 발전되어 왔다.

 

Algorithm 1

 

프로세스 Pi가 진입 할 때 자신의 차례(turn = 0)가 아니면 busy waiting(spin lock)이 발생하며, 자신의 차례일경우 Critical Section을 수행 후 차례를 프로세스 Pj에게 넘긴다. 

int turn = 0;

while(turn != 0) {
}

critical section
turn = 1;

 

문제점 : 두 프로세스의 수행 빈도수가 확연히 다를경우 수행 빈도수가 많은 프로세스가 수행되지 않는다.

ex) Pi 프로세스의 빈도수가 많으며 Pj 프로세스의 빈도수는 한번일 때, Pi 프로세스가 먼저 수행된 후 Pj 프로세스가 수행, 그 후 Pi 프로세스가 수행되며 Pj 프로세스가 수행되지 않기 때문에 Pi 프로세스는 수행되지 않는다.

 

Algorithm 2

 

모든 프로세스의 사용여부를 나타내는 boolean[] 배열을 선언하여 프로세스 Pi가 진입할 때 사용중으로 체크하며, 다른 프로세스가 사용중이 아닐 때 Critical Section을 수행한다.

boolean flag[2]

flag[i] = true;
while(flag[j]) {
}

critical section
flag[i] = false;

 

문제점 : Pi, 프로세스가 flag[i] = true 코드를 수행하고 CPU의 제어권을 뺏긴 후 Pj 프로세스가 flag[j] = true를 수행하면 두 프로세스가 서로 양보하는 상황(Progess)이 발생한다.

 

 

Piterson's Algorithm

 

이전 Algorithm 1과 Algorithm 2에서 사용하는 turn, flag 변수를 모두 사용하는 알고리즘

flag[i] = true;
turn = j;

while(flag[j] && turn == j) {
}

critical section

flag[i] = false;

 

문제점 : busy waiting(spin lock) 발생

 

모든 경우의 수를 고려하며 구현할 때 복잡성이 증가되는 원인은 변수를 증가할 때 여러 개의 명령어로 구성되어 있기 때문(즉, 데이터를 Load, 연산, 데이터 save로 여러 명령어로 나뉘어져 있음)

 

여러 개의 명령어를 하나의 명령어로 지원하는 하드웨어가 바로 Test&Set

boolean lock = false;

while(test_set(lock)) {
}
critical section
lock = false