임계구역 문제
임계구역이란?
임계구역 : multi thread 시스템에서 쓰레드가 공통의 변수를 바꾸거나, table을 업데이트하거나 파일에 써서 생기는 코드의 한 부분. 즉 공유 자원에 접근하는 코드의 영역을 말한다.
1. 임계구역에 동시에 접근해서 생기는 잘못된 동작
- 이전의 bank account 문제. child와 parent가 공통의 변수인 balance에 동시에 접근하면서 총 잔액이 실제와 다르게 되는 상황 발생.
=> 공통 변수인 balance에 대한 동시 업데이트.
- 위의 그림에서 balance를 업데이트 하는 부분이 임계 구역이며, 이 각각의 쓰레드가 임계 구역을 가지는 코드를 가지고 있기에 잘못된 결과가 출력될 수 있는 것이다.
2. 임계구역 문제를 해결하는 방법
- Mutual Exclusion (상호 배타) : 오직 한 쓰레드만 진입할 수 있다. context switching이 일어나더라도 임계 구역에는 한 쓰레드만 진입할 수 있다.
- Progress (진행) : 쓰레드의 진입 유무는 유한 시간 내에 결정된다.
- Bounded waiting (유한 대기) : 어느 쓰레드든지 유한 시간 내에 임계구역 안에 들어갈 수 있다. 즉 대기 시간이 유한하다.
이 3가지가 모두 만족되어야 임계구역 문제를 해결할 수 있다.
3. 프로세스/쓰레드 동기화
: 임계구역 문제를 해결하기 위해, 프로세스 실행 순서를 제어하기 위해, busy wait등 비효율성을 제거하기 위해 동기화가 필요.
동기화 도구
- semaphores : 세마포어, 전통적인 동기화 도구
- monitors : 자바에서 이용하는 도구
- mics
4. semaphores(세마포어) - 상호 배타 처리
세마포어 : 다익스트라가 고안한, 두 개의 원자적 함수로 조작되는 정수 변수로서, 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 사용된다. 상호 배타를 처리하는 방법이다.
- 즉 세마포는 정수형 변수와 두 개의 동작(P, V)로 이루어져 있다.
- 이 2개의 동작 P와 V는 현대에 이르러 P는 acquire로, V는 release로 사용된다.
- 이 semaphore를 java의 notation으로 나타내면 아래와 같다.
class Semaphore
{
int value = 1; //number of permits, 권한의 개수. 현재는 1.
Semaphore(int value)
{
}
void acquire()
{
value--;
if (value < 0)
{
add this process/thread to list;//세마포어 안의 큐 리스트에 추가
block;
}
}
void release()
{
value++;
if (value <= 0)
{
remove a process P from list;//세마포어 안의 큐 리스트에서 제거
wakeup P;
}
}
}위의 코드를 보면, 세마포어 안에 큐가 존재하는 것을 볼 수 있다. 이 queue를 이용해 semaphore가 임계 구역에 value개 초과의 쓰레드가 존재하지 않게 하는 것을 알 수 있다.
<semaphore 가 실제로 어떻게 동작하는지 위의 코드와 그림을 통해 알아보자>
임계 구역에 접근하는 모든 코드는, 임계 구역에 접근하기 전 acquire()을 호출한다. 임계 구역에 접근하는 코드가 실행된 후에는 release()를 호출한다.
아래와 같은 코드 예시가 있다.
acquire();
balance = balance + n;//여기서 공통 변수는 balance. 임계 구역에 접근하는 코드
release();-
이렇듯 임계 구역에 접근하는 코드가 있으면 이 코드를 실행하기 전 acquire()을 호출하고, 코드가 실행된 후 release()를 호출한다.
-
acquire()을 호출하기 전의 value가 1이라면 acquire()을 호출하고 나서는 value가 1 감소해 0이 되지만 acquire()의 if문 내의 조건(value < 0)을 만족하지 않았기 때문에 임계 구역에 접근하는 코드는 무사히 실행된다(임계 구역에 진입).
-
그런데 release()가 실행되기 전 context switching이 일어나서 다른 쓰레드로 넘어가 버렸다고 가정하자. 이번에는 같은 변수에 접근하는 임계 구역을 가진 코드가 실행되는데, 이 코드 또한 실행되기 전 acquire()을 호출할 것이다.
-
현재의 value값은 0이고, acquire()가 호출되었을 때의 value값은 -1이다. acquire()의 if문 내의 조건(value < 0)을 만족하기 때문에 이 쓰레드는 임계 구역에 접근하지 못하고 semaphore내부의 queue에 대기할 것이다.
-
이후 1번의 쓰레드가 release()를 실행하면 value값은 0이 되어 release()내부의 if문 조건(value <= 0)이 만족된다. 따라서 semaphore안의 queue에 block되어있던 2번 쓰레드가 큐 내부에서 탈출해 wakeup상태가 되고, 2번 쓰레드가 임계 구역에 접근할 수 있게 되었다.
==> 이처럼 semaphore는 임계 구역에 접근하는 쓰레드의 수를 제한할 수 있다. 세마포어를 통해 임계구역 문제를 해결하는 방법 중 하나인 상호 배타 문제를 처리할 수 있다.
