1. 개요
뮤텍스(mutex)는 상호 배제(mutual exclusion)의 약자이다.2. 필요한 이유
싱글스레드가 아닌 멀티스레드에서는 아래에서 설명할 임계구역 문제가 발생한다.#!syntax cpp
int a = 0;
int N = 100000;
void Inc()
{
for (int i = 0; i < N; i++)
a += 1;
}
void Dec()
{
for (int i = 0; i < N; i++)
a -= 1;
}
int main()
{
thread t1(Inc);
thread t2(Dec);
t1.join();
t2.join();
cout << "result :" << a << endl;
return 0;
}
이런 코드가 있다고 가정해보자. 이 코드는 사람의 관점으로 봤을 때는 스레드 1은 a의 증가를 10만번하며, 스레드 2는 감소를 10만번하기 때문에 결과가 0이라고 생각할 것이다. 그러나 결과는 실행할 때마다 다르다.
a += 1;은 단순히 눈으로 봤을 때는 a의 값을 1 올려준다는 것으로 보이지만 실제로는
mov eax,dword ptr a
inc eax
mov dword ptr a,eax
이처럼 3줄의 명령어를 실행하는 것이며, 실제로는 임시 변수에 a값을 저장한 뒤 값을 1 증가한 후에 a에 덮어 씌우는 방식이다.inc eax
mov dword ptr a,eax
위의 명령어를 적용한 시간에 따른 표로 설명하자면 아래와 같다.
| 시간 | 스레드 1(Inc) | 스레드 2(Dec) | 설명 |
| 1 | mov eax,dword ptr a | a = 0 일 때, 스레드 1 실행 | |
| 2 | inc eax | ||
| 3 | mov dword ptr a,eax | 스레드 1에 의해 a = 1 | |
| 4 | mov eax,dword ptr a | a = 1일 때, 스레드 2 실행 | |
| 5 | dec eax | ||
| 6 | mov dword ptr a,eax | 스레드 2에 의해 a = 0 | |
| 7 | mov eax,dword ptr a | a = 0 일 때, 스레드 1 실행 | |
| 8 | inc eax | mov eax,dword ptr a | a = 0 일 때, 스레드 2 실행 |
| 9 | mov dword ptr a,eax | dec eax | 스레드 1에 의해 a = 1 |
| 10 | mov dword ptr a,eax | a = 1로 바뀌었지만 스레드 2가 값을 덮어씌워 a = -1이 됨 | |
| ... | ... | ... | ... |
#!syntax cpp
mutex m;
...
m.lock();
a+=1;
m.unlock();
...
이 코드처럼 a+=1;와 a-=1;가 동작하는 코드에 뮤텍스를 사용해 lock(), unlock()처리를 하면 변수의 동시 접근을 해결할 수 있다.
3. 개념
뮤텍스가 무엇인지 이해하기 쉽게 말하면 하나의 길이 있는데, 이 길에는 하나의 방향으로 오직 한 대의 차만이 들어올 수 있다고 치자. 이 때, 서로 다른 방향에서 두 대의 차가 마주 달려온다면 정면충돌 사고가 나거나 서로 오가지 못하여 둘 중 하나는 후진하여 원래 출발 지점으로 돌아가야 한다. 그렇다면 차 두 대가 모두 사고 안 나게 통행하려면 둘 중의 한 대가 먼저 통과하도록 우선권을 부여해야 할 것이다. 이 때에는 한 쪽 끝에서 출발하는 차에게 녹색 불을 켜주고, 반대쪽 끝에 있는 차에게는 빨간 불이 들어와서 길로 들어오지 못하게 하면 된다.[1]3.1. 임계 구역(Critical Section)
'임계 영역'이라고도 한다. 서로 다른 두 프로세스, 혹은 스레드 등의 처리 단위가 같이 접근해서는 안 되는 공유 영역을 뜻한다. 보호되지 않는 임계 구역에 두 처리 단위가 동시에 접근할 때 발생하는 문제를 '임계 구역 문제'라고 한다. 임계 구역을 시작하는 코드 부분을 '입장 구역(entry section)', 임계 영역을 종료하는 코드 부분을 '퇴장 구역(exit section)'이라고 한다. 임계 영역이 아닌 부분은 '나머지 구역(remainder section)'이라고 한다.3.2. 임계 구역 문제
임계 구역으로 설정해야 하는 부분이 임계 구역으로 지정되지 않았을 때 발생하는 문제이다.- 생산자 - 소비자 문제
- 독자 - 저자 문제
- 입출금 문제
대표적인 '생산자-소비자 문제' 로 키보드 입력을 들 수 있다. 일반적으로 키보드 입력은 시스템 메모리 내부에 일정한 크기의 큐를 준비해 두고 사용자가 키보드를 타이핑하면 큐에 타이핑한 문자를 하나씩 넣고, 응용 프로그램은 큐에서 문자를 하나씩 얻어가서 처리하는 방식이다. 우선 큐에 문자를 넣는 부분은 운영체제에서 잘 처리해 준다고 생각하고, 큐에서 문자를 빼가는 쪽만 생각해 보자면...
#!syntax cpp
char queue[32];
int head = 0;
int tail = 0;
...
int getchar()
{
int pos;
char ret;
pos = head;
ret = queue[pos];
pos = (pos + 1) % 32;
head = pos;
return ret;
}
위와 같은
getchar 함수를 생각할 수 있다.[2]호출 이전에는 키 a, b, c를 입력하고 아직 아무도 이 키를 얻어가지 않은 상태라고 한다면,
| head | 0 |
| tail | 3 |
| queue | ['a', 'b', 'c', ...] |
| head | 1 |
| tail | 3 |
| queue | [ |
이제, A, B 두 응용 프로그램이 동시에 버퍼에서 키를 가져가려고 getchar를 A는 한 번, B는 두 번 호출했다고 가정한다. 본래대로라면 키 입력 세 개를 리턴하여 최종 결과는
| head | 3 |
| tail | 3 |
| queue | [ |
1. (A) pos = head = 0;
2. (A) ret = queue[0] = 'a';
Context Switch
3. (B) pos = head = 0;
4. (B) ret = queue[0] = 'a';
5. (B) pos = 1; → head = 1;
6. (B) pos = head = 1;
7. (B) ret = queue[1] = 'b';
8. (B) pos = 2; → head = 2;
Context Switch
9. (A) pos = 1; → head = 1;
| head | 1 |
| tail | 3 |
| queue | [ |
결국, A는 'a', B는 'a', 'b'를 얻어가서 입력값이 왜곡되었다. 더군다나 키 입력값 세 개를 얻어간 상태인데도 버퍼에는 여전히 키 두 개가 남아있다. 즉 getchar 함수 내부에 큐에서 키를 빼내고 head를 조정하는 부분은 두 프로세스, 혹은 스레드가 동시에 실행하면 안 되는 임계 구역이다.
3.3. 뮤텍스
이제 두 처리 단위가 임계 구역에 동시에 접근하지 못하도록 막는 기법이 필요해진다. 이를 '상호 배제(Mutual Exclusion)'이라고 하며 보통 '뮤텍스'로 줄여서 이야기한다. 아주 단순하게 생각하면 뮤텍스는 아래 두 가지 연산만을 지원하면 된다.- lock: 현재의 임계 구역에 들어갈 권한을 얻어온다. 만일 다른 프로세스/스레드가 임계 구역을 수행 중이라면 종료할때까지 대기한다(entry section).
- unlock: 현재의 임계 구역을 모두 사용했음을 알린다. 대기중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있다(exit section).
위의 getchar 함수를 뮤텍스를 활용해 다시 작성한다.
#!syntax cpp
char queue[32];
int head = 0;
int tail = 0;
mutex keymutex;
...
int getchar()
{
int pos;
char ret;
lock(keymutex); /* entry section */
/* critical section begin */
pos = head;
ret = queue[pos];
pos = (pos + 1) % 32;
head = pos;
/* critical section end */
unlock(keymutex); /* exit section */
return ret; /* remainder section */
}
다시 프로세스 A, B가 키 입력을 얻어간다고 하면
1. (A) lock keymutex;
2. (A) pos = head = 0;
3. (A) ret = queue[0] = 'a';
Context Switch
4. (B) lock keymutex: Blocked[3]
Context Switch
5. (A) pos = 1; → head = 1;
6. (A) unlock keymutex;
Context Switch
7. (B) returned from lock
8. (B) ...
9. (B) pos = 3; → head = 3;
10. (B) unlock keymutex;
| head | 3 |
| tail | 3 |
| queue | [ |
3.4. 좁은 의미의 뮤텍스
보통 프로그래밍을 할 때의 뮤텍스는 한 프로세스의 내부에서 여러 스레드의 임계구역 제어를 위해 사용하는 객체를 뜻한다. 특별히 다른 프로세스와 공유해 사용하도록 옵션을 가하지 않는 이상 프로세스 외부에는 공개되지 않는다. 운영체제에 따라서는 trylock 기능을 제공하기도 하는데, 뮤텍스를 잡는데 성공하면 true를, 실패하면 false를 리턴한다. 즉, 임계영역에 진입할 수 없으면 다른 작업을 먼저 수행하면서 대기하는 것이 가능하다.3.5. 세마포어와의 관계
뮤텍스로 세마포어를 구현할 수 있고 세마포어로 뮤텍스를 구현할 수 있다. 세마포어는 동시에 여러 개의 프로세스/스레드가 임계 구역에 접근할 수 있도록 카운트를 가지고 있는데 카운트가 1인 특별한 세마포어가 바로 뮤텍스이다. 뮤텍스를 이용해 세마포어를 구현하면 아래와 같다.1. 뮤텍스를 잡는다.
2. 현재 카운트 값이?
2.1. 0이라면 뮤텍스를 풀고 1.로 돌아가서 재시도한다.
2.2. 1 이상이라면 카운트를 1 감소시키고 뮤텍스를 푼다.
3. 임계구역 수행 후 카운트를 1 증가시킨다.
일반적으로 뮤텍스는 프로세스 내부에서만 공유되는 반면 세마포어는 특별히 옵션을 추가하지 않으면 여러 개의 프로세스에서 접근이 가능하다.
3.6. 읽기/쓰기 뮤텍스
읽기만 하는 스레드와 읽기/쓰기를 모두 하는 스레드가 있다면, 읽기만 하는 스레드는 사실 몇 개가 동시에 수행되어도 관계없다. 반면 쓰기를 수행하는 스레드는 한 번에 하나씩만 수행되어야 한다. 이 때 임계구역에 무조건 하나씩만 진입시키는 뮤텍스를 사용한다면 읽기만 하는 스레드도 한 번에 하나씩만 수행되기 때문에 성능저하가 발생한다. 이를 보완하기 위해 읽기 모드는 이론상 무한대로 잡을 수 있되, 쓰기 모드는 하나만 잡는 것이 가능한 뮤텍스를 읽기/쓰기 뮤텍스라고 한다. 쓰기 스레드가 무한대기하는 상황(Starvation)을 방지하기 위해, 보통 쓰기 스레드가 대기중이라면 이후에 임계 영역에 진입하는 읽기 스레드는 쓰기 스레드가 임계영역을 떠날 때까지 대기하도록 한다.3.7. 참고: 원자적 연산(atomic operation)
보통 뮤텍스, 세마포어 등의 상호배제 연산은 입장 구역에서 진입 가능 여부를 판단하고, 진입이 불가능하면 현재 임계 영역을 수행중인 스레드에게 CPU를 넘겨주는 등의 기능을 내부적으로 처리하기 때문에 상당히 복잡하게 구현되어 있고 수행하는데 시간이 오래 걸린다.[4] 만일 임계 영역 내부에서 변수 하나를 증가시키는 기능만을 수행하기 위해 뮤텍스를 사용한다면 배보다 배꼽이 더 큰 상황이 발생하게 된다. 이를 위해 CPU에서 적은 수의 연산에 한해서 임계구역을 설정한 것처럼 작동하는 기능을 지원하는데 이를 원자적 연산(atomic operation)이라고 한다. 문맥전환이 필요없기 때문에 뮤텍스를 사용했을 때에 비해 매우 빠르게(즉 '가볍게') 작동한다. X86 계열의 CPU라면 어셈블리 명령어 앞에 lock이 붙어 있는 것들이 원자적 연산이다. 대체적으로 compare-and-swap, fetch-and-add 등에 atomic operation을 활용한다. 물론 일반적인 메모리 읽기/쓰기 명령에 비해서는 느리기 때문에 남용하거나 필요없는 부분에 사용하면 시스템 전체의 성능저하를 불러온다.동일한 스레드를 여러 개 시작하고 종료할 때 현재 스레드가 몇 개 작동중인지 알아내고 싶다면 뮤텍스, 혹은 원자적 연산을 사용해 아래와 같이 만들 수 있다.
뮤텍스를 사용한 예제.
#!syntax cpp
int gNoThreads = 0;
mutex gLock;
int threadfunc(void* pParam)
{
/* 시작하면서 스레드 개수를 늘려준다. */
lock(gLock);
gNoThreads++;
unlock(gLock);
/* thread run */
/* 종료하면서 스레드 개수를 감소시킨다. */
lock(gLock);
gNoThreads--;
unlock(gLock);
return 0;
}
원자적 연산을 사용한 예제. - GCC의 인트린식 사용
#!syntax cpp
int gNoThreads = 0;
int threadfunc(void* pParam)
{
/* 시작하면서 스레드 개수를 늘려준다. */
(void)__sync_add_and_fetch(&gNoThreads, 1);
/* thread run */
/* 종료하면서 스레드 개수를 감소시킨다. */
(void)__sync_sub_and_fetch(&gNoThreads, 1);
return 0;
}
원자적 연산을 큰 덩어리의 메모리에 수행하는 것을 보통 트랜잭셔널 메모리(Transactional Memory)라고 한다. 인텔 하스웰 이상의 CPU에서 제공하는 'RTM'과 PowerPC에서 제공하는 'HTM'이 트랜잭셔널 메모리이다.
4. 관련 문서
[1] 기차로 치면 통표폐색과 같이 하나의 선로에 통표를 가진 열차만 들어올 수 있는 것과 같다.[2] 실제로는 큐에 키가 없으면 대기하는 부분이 있어야 하며, head를 이동시키는 부분은 fetch-and-add 등의 연산을 사용할 수도 있지만 최대한 단순화하여 생각한다.[3] 이미 A가 keymutex를 잠가 둔 상태이기 때문에 B는 A가 keymutex를 풀 때까지 대기하여야 한다. 실제로 운영체제에서는 뮤텍스가 잠겨 있으면, 뮤텍스를 소유한 프로세스/스레드로 context switch해준다.[4] 프로그래머들은 보통 무겁다라는 은어를 사용한다. 영어 heavy, light 등에서 직역된 표현.