reference. 캄란 아미니 - 전문가를 위한 C
[동시성 문제]
- 동시성 문제는 동시성 제어 메커니즘이 없을 때만 존재할 수도 있고, 동시성 제어 기술을 사용해서 발생할 수도 있다.
동시성 제어 메커니즘이 없는 경우 - 서로 다른 인터리빙이 전체 상태를 다르게 만들 때 동시성 문제가 발생한다.
(고유한 동시성 문제(intrinsic concurrency) - 제어(동기화) 메커니즘이 없는 동시 시스템에서 발생하는 문제)
전체상태, 인터리빙 간단 설명 -> 동시성 (tistory.com)
고유하다고 하는 이유는 이 문제가 모든 동시 시스템에 본질적으로 존재하기 때문이다. 이 문제는 피할 수 없으며 제어 메커니즘을 이용해 다루어야 한다. 어떤 의미로는 이것이 동시 시스템의 문제라기보다는 동시 시스템의 속성이라고 볼 수 있다. 이 속성 중 비결정적인(non-deterministic) 속성은 우리에게 필요한 결정론적인(deterministic) 프로그램을 개발하지 못하도록 하기 때문에 속성을 문제로 다룬다.
동시성 제어 메커니즘이 있는 경우 - 수정 사항이 적용된 이후에만 발생하기 때문에 동시성 문제를 고칠 때 속성 및 근본 원인이 완전히 다른 새로운 문제가 야기될 수 있는 상황.
(동기화 이후 문제(post-synchronization inssue) - 고유한 동시성 문제를 해결하려고 시도한 이후 발생한 문제)
데이터 경쟁이 확인되어 공유 데이터 자원에 대한 접근을 제어하는 해결 방안을 적용했을 때, 일부 작업들이 데이터 자원에 아예 접근하지 못하는 상황도 발생할 수 있는데 이를 기아 상태(starve)라고 한다. 동시성 문제는 해결되었으나 성격히 완전히 다른 새로운 문제가 발생하는 셈이다.
동기화 이후 문제는 동기화 메커니즘을 잘못된 방식으로 사용할 때만 발생한다.
참고로 제어 메커니즘 차제는 전혀 문제가 되지 않으며 프로그램에 결정론을 다시 도입하려면 제어 메커니즘이 필요하다. 이렇듯 동기화 이후 문제는 시스템의 고유한 속성보다는 개발자가 일으킨 새로운 버그로 볼 수 있다.
[고유한 동시성 문제]
- 하나 이상의 작업이 있는 모든 동시 시스템은 다수의 인터리빙이 존재할 수 있으며, 이러한 인터리빙은 시스템의 고유한 속성이라고 볼 수 있다. 이는 비결정적인 속성이며, 각 실행에서 뒤죽박죽인 순서로 다른 작업의 명령어가 실행되도록 만들지만, 여전히 발생 전 제약(happens-before-constraint)을 따른다.
발생 전 제약 간단 설명 -> 동시성 (tistory.com)
인터리빙은 그 차제로는 문제가 되지 않지만, 어떤 경우 인터리빙이 지켜야 할 일부 제약 조건을 만족하지 못할 때가 있는데, 이 때 인터리빙이 문제를 일으킨다.
즉, 다수의 작업이 동시에 실행되는 동안 수많은 인터리빙이 존재할 수 있는 상황에서 시스템에 대해 불변해야 하는 제약 조건이 실행할 때마다 인터리빙에 의해 변경될 때는 문제가 발생한다.
그러므로 제약 조건이 변경되지 않으며 불변함을 유지하도록 동기화 메커니즘이라는 제어 메커니즘을 도입하는 것이다.
불변 제약 조건은 간단하게 처리할 수 있는 내용부터 거대한 동시 S/W 프로그램에서 모든 외부 데이터 소스에 대한 데이터 무결성(data integrity)을 보존하는 것처럼 매우 복잡할 수도 있다.
--------------------------------------------------------------------[ 여담 ]----------------------------------------------------------------------------
가능한 모든 인터리빙을 만들기란 매우 어려운 것으로 어떤 경우에는 특정 인터리빙이 아주 낮은 확률로만 발생하며,
1/1,000,000 확률로 발생할 수도 있다.
이는 동시 개발의 또 다른 위험한 측면이다. 어떤 인터리빙에 문제가 있는데 1/1,000,000 확률로 발생할 수 있다 하더라도, 문제 발생시 큰 문제로 이어질 수 있기 때문이다.
---------------------------------------------------------------------------------------------------------------------------------------------------------
모든 동시 시스템에는 잘 정의된 최소한의 불변 제약 조건이 있다.
동시 시스템에서 발생하는 인터리빙은 기존에 정의된 불변 제약 조건을 만족해야한다.
조건을 만족하지 못한다면 시스템에 문제가 있는 것으로 보며, 여기서 불변 제약 조건은 매우 중요한 요인인 셈이다.
시스템의 불변 제약 조건을 만족하지 않는 인터리빙이 존재할 때 우리는 시스템에 경쟁 상태(race condition)가 발생했다고 한다.
경쟁 상태란 동시 시스템의 고유한 속성, 즉 인터리빙에 의해 발생한 문제에 해당한다. 경쟁 상태가 발생할 때마다 시스템의 불변 제약 조건을 지키질 못할 위험이 았다.
불변 제약 조건을 충족하지 못한 결과는 논리적 오류나 갑자기 발생하는 충돌로 나타난다.
공유 변수에 저장된 값이 실제 저장된 값이 실제 상태를 반영하지 않는 사례가 많다.
이를 주로 공유 변수에 대한 데이터 무결성을 손상시키는 서로 다른 인터리빙 때문이다.
다음의 의사 코드를 통해 조금 더 알아보자
아래 의사코드는 단 하나의 불변 제약 조건인 <공유된 카운터 변수에는 최종적으로 올바른 값이 있어햐 하고 이 값은 3이어야 한다> 가 있으며, 이 의사 코드는 세 개의 동시 작업과, 모든 작업은 카운터를 1씩 증가해야하는 로직이다.
동시 시스템
{
공유 상태
{
카운터 : 정수 = 0
}
작업 T1
{
A : 정수
1.1. A = 카운터
1.2. A = A + 1
1.3. 카운터 = A
}
작업 T2
{
B : 정수
2.1. B = 카운터
2.2. B = B + 1
2.3. 카운터 = B
}
작업 T3
{
A : 정수
3.1. A = 카운터
3.2. A = A + 1
3.3. 카운터 = A
}
}
모든 작업은 지역 변수를 여러 개 가질 수 있다. 이러한 지역 변수는 해당 작업 전용이며, 다른 작업들은 서로의 변수를 볼 수 없다. 이러한 이유로 A 라는 같은 값을 갖는 지역 변수 두 개가 있을 수 있으며 이들은 하나하나 모두 달라야 하고 해당 변수를 소유한 각 작업에 한정되어야 한다.
참고로 작업은 공유된 변수에서 직접 작동하지 않으며 작업들은 오직 공유된 변숫값을 읽거나 변경할 수만 있다.
이러한 이유로 기본적인 지역 변수 몇 개가 필요하다. 알다시피 작업들은 지역 변수를 증가시킬 수만 있고 공유된 변수는 직접 증가시킬 수 없다.
(지역 변수를 사용한다고 해서 원하는 결과 값을 도출해 주진 않으나, 공유 변수를 직접 활용하여 변경시킬 경우 공유 변수 값이 변하는 문맥이 어디서 실행 될지 모르기 때문에 서로의 스레드에게 영향을 주게된다.
그래서 최소한 서로의 스레드 진행 중에는 공유 변수로 인해 결과 값이 바뀌는 불상사를 배제시키기 위해 지역 변수에다 값을 복사해서 사용하는 것이 좋다)
위의 의사코드의 인터리빙 중 다음과 같은 상황을 예시로 보면
| 작업 스케줄러 | 작업 T1 | 작업 T2 | 작업 T3 |
| 문맥 교환 | |||
| A = 카운터 | |||
| A = A + 1 | |||
| 카운터 = A | |||
| 문맥 교환 | |||
| B = 카운터 | |||
| B = B + 1 | |||
| 문맥 교환 | |||
| A = 카운터 | |||
| 문맥 교환 | |||
| 카운터 = B | |||
| 문맥 교환 | |||
| A = A + 1 | |||
| 카운터 = A |
작업 T2 와 T3 는 둘 다 공유된 카운터 변수의 내부에 값 2를 저장한다. 이러한 상황을 데이터 경쟁(data race)라고 한다.
다음 의사코드는 C로 작성하면 세그멘테이션 오류를 일으키는 예제이다.
동시시스템
{
공유상태
{
char *ptr = NULL // 힙 공간에 있는 메모리 주소를 가리켜야하는 공유된 char 포인터는
// 기본값이 NULL이 된다.
}
작업 P
{
1.1. ptr = (char *)malloc(10 * sizeof(char));
1.2. strcpy(ptr, "hello!");
1.3. printf("%s\n", ptr);
}
작업 Q
{
2.1. free(ptr);
2.2. ptr = NULL;
}
}
이 예제에서 염려하는 불변 제약 조건 중에 작업 충돌을 허용하지 않는다는 조건이 있는데,
이는 작업이 자기 일을 끝까지 완수하지 못하는 경우엔 불변 제약 조건을 갖는다는 것이 모순이 된다.
위의 겨우 두가지의 충돌을 일으키는 인터리빙이 있다.
1.
명령어 2.1 먼저 실행 ->
ptr = NULL 이므로 free 작업에서 충돌 발생 ->
작업 P 는 상관없이 진행
두 작업 모두 같은 프로세스에 속하는 멀티스레딩 사용 사례에서, 두 작업을 포함하는 프로그램 전체에 충돌이 발생한다. 주요 원인은 NULL 포인터를 free 하기 때문이다.
2.
명령어 1.1 실행 ->
명령어 2.2 실행으로 strcpy 에서 ptr 의 NULL 포인터 참조인한 충돌 발생 ->
작업 Q 는 상관없이 진행
이렇듯 동시 시스템에 경쟁 상태가 있다면 논리적 오류나 갑작스러운 충돌과 같은 다른 상황이 발생기 때문에 두 경우 모두 적절하게 해결해야 한다.
동시 시스템에서 모든 경쟁 상태를 다 식별하기는 쉽지 않다. 일부 경쟁 상태는 한참 후에 나타나기도 하기 때문에 동시 프로그램을 다루는 것은 쉽지 않은 일이다.
그럼에도 불구하고 때로는 실행 빈도가 낮은 코드의 분기에서 기존의 경쟁 상태를 찾아내는 경쟁 탐지기(race detector)를 사용할 수 있다.
------------------------------------------------------------------------[ 여담 ]------------------------------------------------------------------------
경쟁 상태는 경쟁 탐지기라는 프로그램 그룹이 감지할 수 있다. 탐지기는 특성이 정적 또는 동적인지에 따라 그룹이 나뉜다.
정적 경쟁 탐지기(static rece detector) - 소스 코드를 살펴보고 관찰한 명령어에 기반해 모든 인터리빙을 만들려고 한다.
동적 경쟁 탐지기(dynamic race detector) - 먼저 프로그램을 실행하고 나서 경쟁 상태가 의심되는 코드가 실행되기를 기다림
경쟁 상태가 발샐할 위험을 줄이고자 둘 다 결합해 사용할 수 있다.
---------------------------------------------------------------------------------------------------------------------------------------------------------
모든 경쟁 조건에 대한 하나의 주된 이유를 찾아보자면, 불변 제약 조건을 만족하기 위해 서로 다른 작업에서 모든 인터리빙에 걸쳐 엄격한 순서로 실행해야 하는 명령어가 항상 많으며, 이 순서를 따르는 인터리빙은 불변 제약 조건을 위반하지 않는다.
다음의 의사 코드를 통해 이해해보자
다음의 의사코드에서의 불변 제쟉 조건은 <1을 출력> 하는 것이다.
동시 시스템
{
공유 상태
{
X : 정수 = 0
}
작업 P
{
1.1. X = 1
}
작업 Q
{
2.1. X를 출력
}
}
위 코드에서 불변 제약 조건 <1을 출력> 을 유지하고 싶으면, 두 작업에서 명령어에 대해 순서를 엄격하게 따르도록 정의해야 한다. 그려려면 명령어 2.1 은 1.1 이후에만 실행되겠끔 해야한다.
이러한 순서를 쉽게 위반하는 다른 인터리빙이 존재하므로 경쟁 상태가 발생한다. 명령어 간에는 엄격한 순서가 필요하지만 원하는 순서대로 두기란 쉽지 않다.
또 다른 의사코드로 마저 생각해보자
다음의 의사 코드는 <언제나 1, 2, 3 순서로 출력> 하는 제약 조건을 가지고자 한다.
동시 시스템
{
공유 상태
{}
작업 P
{
1.1. 3을 출력
}
작업 Q
{
2.1. 1을 출력
}
작업 R
{
3.1. 2를 출력
}
}
단순한 코드일 뿐이지만 어느 작업이 먼저 실행될 지 보장할 수 없으므로 경쟁상태가 발생한다. 그러므로 제약 조건을 유지하려면 Q->R->P 순서로 실행되어야하며, 모든 인터리빙에서 이 순서를 지켜야 한다.
이 예제를 비추어 볼 때 동시 시스템에서 경쟁 상태가 생기려면 공유 상태가 필요하지 않는다는 점이다.
대신, 경쟁 상태를 피하려면 어떤 명령어는 항상 엄격한 순서대로 두어야 한다.
경쟁 상태는 일반적으로 임계 구역(critical section)이라는 작은 명령어 집합이 순서대로 실행되지 않을 때만 발생한다는 점을 주목해야 한다.
반면 임계 구역이 아닌 다른 명령어는 어떠한 순서로도 실행될 수 있다.
공유 상태와 관련해, 작성 가능한 공유 상태와 특정 불변 조건이 둘 다 있다면 공유 상태를 목표로 하는 읽기와 쓰기 명령어 간에 엄격한 순서를 부과할 수 있다.
작성 가능한 공유 상태에 대한 가장 중요한 제약 조건은 데이터 무결성이다.
데이터 무결성이란 간단히 말해 모든 작업이 언제나 공유 상태의 최신값을 읽을 수 있어야 한다는 의미이다.
즉, 공유 상태를 계속해서 수정하기 전에 공유 상태의 업데이트 내역을 인지할 수 있어야 한다.
다음의 공유된 변수 X에 대한 데이터 경쟁이 발생하는 동시 시스템 의사 코드를 보자
동시 시스템
{
공유 상태
{
X : 정수 = 2
}
작업 P
{
A : 정수
1.1. A = X
1.2. A = A + 1
1.3. X = A
}
작업 Q
{
B = 정수
2.1. B = X
2.2. B = B + 3
2.3. X = B
}
}
여기서 발생할 수 있는 인터리빙 중 하나는
명령어 1.1 이 실행 ( X 에 대한 값이 지역 변수 A로 복제) ->
문맥 교환 ->
명령어 2.1 이 실행 ( X에 대한 값은 지역 변수 B로 복제) ->
이 과정에서 A와 B는 모두 같은 값인 2를 가진다.
명령어 2.2 가 실행 ( B 의 값이 5로 증가) ->
명령어 2.3 실행 ( 값 5를 공유 상태 X 에 대입) ->
명령어 1.2 실행 (A 의 값이 3으로 증가) ->
명령어 1.3 실행 ( 값 3을 공유 상태 X 에 대입)
결국 최종적으로 6 의 결과를 원했지만 3의 결과가 나오게 된다.
작업 Q 는 연산이 완료되었지만, 작업 P 는 연산 도중이었기 때문에 해당 연산을 이어나가는 시점에서 데이터 무결성 제약 조건이 손상된 것이다.
해당 코드에서 무결성 제약 조건을 충족시키려면 명령어 1.1 이 2.3 바로 뒤에 실행될 수 있도록 하거나, 명령어 2.1이 명령어 1.3 뒤에만 실행되도록 해야한다.
일부 인터리빙이 공유 상태와 관련된 데이터 무결성에 대한 제약 조건을 위반할 때, 공유 상태에 대한 데이터 경쟁이 존재한다.
데이터 경쟁은 경쟁 상태와 매우 비슷하다. 하지만 데이터 경쟁이 발생하려면 서로 다른 작업 간에 공유 상태가 있어야 하고, 그 공유 상태는 반드시 최소한 하나 이상의 작업이 수정할 수 있어야 한다.
즉, 공유 상태는 모든 작업에 대해서 읽기 전용이어서는 안되며, 이 로직에 따라 공유 상태에 작성할 수 있는 최소한 하나의 작업이 있어야 한다.
다음 의사코드를 통해 경쟁 상태가 발생하는 동시에 읽기 전용인 공유 상태에 대해 데이터 경쟁이 생기지 않는 상황을 보자
제약 조건은 <X에 대한 데이터 무결성을 유지하고 5, 6, 7을 출력하는 것> 이다.
동시 시스템
{
공유 상태
{
X : 정수(읽기 전용) = 5
}
작업 P
{
A : 정수
1.1. A = X
1.2. A = A + 1
1.3. A를 출력
}
작업 Q
{
2.1. X를 출력
}
작업 R
{
B : 정수
3.1. B = X + 1
3.2. B = B + 1
3.3. B를 출력
}
}
서로 다른 print 명령어 사이에는 엄격한 순서가 필요하기 때문에 경쟁 상태가 생긴다.
하지만 공유 변수가 읽기 전용이므로 데이터 경쟁은 없다.
[동기화 이후 문제]
새로운 고유한 문제(new intrinsic inssue) - 제어 메커니즘을 적용한 결과 다른 경쟁 상태나 데이터 경쟁이 생긴다. 제어 메커니즘은 명령어 간에 엄격한 순서를 강제하며, 그 과정에서 새로운 고유한 문제를 야기할 수 있다. 제어 메커니즘이 새로운 인터리빙을 도입하면 새로운 동시성 관련 행위 및 문제를 겪는다. 새로운 경쟁 상태나 데이터 경쟁이 발생한 결과 새로운 논리적 오류와 충돌이 발생할 수 있다. 이러한 문제를 고치려면 도입한 동기화 기술을 프로그램의 로직에 따라 살펴보고 조정해야 한다.
기아 상태(starvation) - 동시 시스템이 있는 작업이 오랫동안 공유 자원에 접근하지 못하는 경우로, 주로 특정 제어 메커니즘을 도입해 발생하는데, 이를 작업이 기아 상태가 되었다고 한다. 기아 상태인 작업은 공유 자원에 접근할 수 없으므로 목적을 효과적으로 실행할 수 없다. 다른 작업이 기아 상태인 작업에 의존한다면, 의존하는 다른 작업 역시 기아 상태가 된다.
교착 상태(deadlock) - 동시 시스템의 모든 작업이 서로를 대기하느라 모든 작업이 진행되지 못할 때를 교착 상태라고 한다. 교착 상태는 주로 잘못된 방식으로 적용된 메커니즘 때문에 다른 작업이 공유 자원이나 잠긴 객체를 해제하기를 기다리면서 무한 루프에 빠지게 되면서 발생한다. 이는 일반적으로 순환 대기(circular wait) 라고 한다. 작업이 대기하는 동안 어느 작업도 실행할 수 없다 보니 시스템이 혼수 상태와 같은 상황이 된다. 교착 상태에서 모든 작업은 멈워서 서로를 기다리지만 작업 중 일부, 하나 또는 두 개의 작업만 멈춰 있고 다른 작업은 계속할 수 있는 상황도 종종 있는데 이를 반교착상태(semi-deadlock)이라고 한다.
우선순위 역전(priority inversion) - 동기화 기술을 도입한 이후, 공유 자원을 사용할 더 높은 권한을 갖는 작업이 우선순위가 낮은 작업 뒤로 블로킹될 때가 있는데, 이러한 방식으로 우선순위 역전이 발생한다. 잘못 구현된 동기화 기술 때문에 발생할 수 있는 부수적인 또 다른 문제에 해당한다.
기아 상태는 동시 시스템에 원래 존재하지 않는다. 동기화 기술이 OS 의 작업 스케줄러에 도입되지 않으면 시스템은 공정해서 어느 작업도 기아 상태가 되지 않는다. 개발자가 제어 메커니즘을 도입해야만 기아 상태가 발생한다.
마찬가지로 교착 상태 역시 개발자가 관여하기 전까지는 동시 시스템에 존재하지 않는다. 대부분의 교착 상태에 대한 주요 원인은 동시 시스템의 모든 작업이 서로가 잠금(lock)을 풀어주기 기다리는 방식으로 잠금을 사용하는 경우이다.
일반적으로 동시 시스템에서 기아 상태보다 교착 상태가 더 흔한 문제이다.
[동기화 기술]
- 동시 시스템은 각각 고유한 불변 제약 조건이 있으며, 모든 인터리빙이 이 조건을 충족하지 않기 때문에, 명령어간에 특정한 순서를 부여하는 방법을 고안해야 한다. 즉, 불변 제약 조건을 만족하면서 제약 조건을 위반하는 인터리빙을 대체할 새로운 인터리빙을 생성해야 한다.
동기화 기술을 사용한 이후 일부 새로운 인터리빙이 있는 완전히 새로운 동시 시스템이 생기고, 이 시스템이 불변 제약 조건을 계속 만족해 동기화 이후 문제가 일절 발생하지 않는다.
참고로 동기화 기술을 도입하려면 새로운 코드를 작성하고 기존 코드를 변경해야 한다. 기존 코드를 변경하면 명령어의 순서, 즉 인터리빙이 효과적으로 변경되고, 새 인터리빙이 있는 새로운 동시 시스템이 손쉽게 생긴다.
새로운 인터리빙을 도입함으로써 서로 다른 작업의 다른 명령어 사이에 발생 전 제약을 추가로 부과할 수 있고, 이는 불변 제약 조건을 만족할 수 있도록 한다.
단일 작업에서는 두 개의 인접한 명령어 사이에는 항상 발생 전 제약 조건이 존재하지만, 동시 시스템에선 서로 다른 두 작업에 있는 두 명령어 사이에 제약 조건이 없으며, 동기화 기술을 사용해 두 작업 사이의 실행 순서를 제어하는 새로운 발생 전 제약 조건을 정의한다.
여러 작업을 동기화하고 이 작업들을 특정 순서에 따르도록 하기에 알맞은 동기화 기술을 도입하는 일은 직접적인 동시 환경에 달려 있다. 예를 들면 멀티프로세싱 프로그램에서 사용된 제어 메커니즘은 멀티스레딩 프로그램에서 사용된 방식과 다를 수 있다.
[바쁜대기 및 스핀락]
- 동시성 문제를 해결하는 일반적인 방법으론 한 작업의 명령어가 다른 작업의 다른 명령어 이후에 실행되도록 하기위해, 해당 작업은 후속 작업이 명령어를 실행하도록 대기해야한다. 동시에 이 작업은 문맥 교환을 통해 CPU를 얻게될 수도 있지만 실행되지 않은 채 대기해야 한다. 즉, 해당 작업은 후속작업이 명령어를 실행할 때까지 멈춰서 대기해야한다.
(인위적으로 후속 명령어를 먼저 실행시키기위해 이전 작업을 대기 상태로 만들어서 후속 작업을 먼저 실행시킨 후, 대기하던 이전 작업을 마저 실행하고자 하는 것)
이전 작업은 후속 작업이 완료되었는지 재차 확인하거나, 후속 작업이 이전 작업에 대해 이제 명령어를 계속 실행해도 된다로 알리는 방식으로 이전 작업이 대기를 풀고 명령어 실행을 이어나갈 수 있다.
다음 의사 코드를 살펴보자
제약 조건은 <A 다음 B 가 출력> 된는 것이다.
동시 시스템
{
작업 P
{
1.1. 'A'를 출력
}
작업 Q
{
2.1. 'B'를 출력
}
}
정의된 불변 제약 조건에 따라 명백히 경쟁 상태가 생겼다.
2.1 다음 1.1 이 실행되는 인터리빙은 해당 제약조건을 위반한다. 그러므로 이 명령어 간에 특정 순서를 따르도록 하는 제어 메커니즘을 사용해야 한다.
다음의 의사코드를 통해 명령어 사이에 다시 순서가 생기도록 설계하여 도입한 방법을 보자
동시 시스템
{
공유 상태
{
완료 : 불리언 = 거짓
}
작업 P
{
1.1. 'A'를 출력
1.2. 완료 = 참
}
작업 Q
{
2.1. '완료'되지 않는 동안 아무것도 하지 않음
2.2. 'B'를 출력
}
}
동기화를 위해 명령어를 추가하므로써 새로운 인터리빙이 추가된 것처럼 보인다. 정확하게 말하면 이전과 비교해 완전히 새로운 동시 시스템을 마주한 것이다. 이전 시스템의 인터리빙과 비교되지 않는 고유한 인터리빙의 집합을 갖는 것이라고 볼 수 있다.
위의 의사 코드를 통해 새롭게 생긴 인터리빙들은 명령어 1.1. 이 언제나 명령어 2.2 이전에 실행되는 공통점을 가지게 된다. 어떤 인터리빙을 선택하거나 문맥 교환이 발생하더라도 위의 순서에는 발생 전 제약 조건이 실행되게 된다.
위의 발생 전 제약이 성립되는 이유는 새로운 공유 상태인 '완료' 를 도입했기 때문이다.
초기 '완료' = 거짓
작업 P 실행 후 '완료' = 참
작업 Q 실행 전 '완료' = 참
작업 Q 실행
또는
초기 '완료' = 거짓
작업 Q 실행 전 '완료' = 거짓
작업 Q 대기
작업 P 실행 후 '완료' = 참
작업 Q 다시 실행 전 '완료' = 참
작업 Q 실행
작업 P가 CPU 코어를 잃고 작업 Q 가 CPU 코어를 얻을 때, 만약 '완료' 가 참이 아니어서 작업 Q가 코어를 다시 잃을 때까지 루프 안에 남아 있다고 한다면, 이는 작업 Q가 CPU 코어를 가지는 동안 필요한 조건이 아직 충족되지 않았으며, 작업 Q는 루프를 떠나지 않고 조건이 충족되었는지 타임 슬라이스(time slice)를 사용해 풀링(pooling)하고 확인하는 것 외에는 아무것도 하지 않는다는 의미이다. 이 과정은 CPU 코어가 회수될 때까지 계속된다.
즉, 작업 Q는 작업 P가 다시 CPU 코어를 받아서 A를 출력할 수 있을 때까지 대기하면서 시간을 낭비한다.
기술 언어로는 작업 Q가 특정 조건이 충족될 때까지 바쁜 대기(busy-wait)를 하고 있다고 한다.
타임 슬라이스 - OS 가 프로세스나 스레드에게 할당해준 CPU 점유 시간
풀링 - 스레드가 특정 조건이나 변수의 상태 변경을 반복적으로 체크하는 것
------------------------------------------------------------------------[ 여담 ]------------------------------------------------------------------------
바쁜 대기(busy-wait)는 효율적이지는 않지만, 이벤트가 발생하기를 기다리는 간단한 방식이다. 바쁜 대기 내부에서는 특별히 수행할 작업이 없으므로 주어진 타임 슬라이스를 완전히 낭비하기 때문에 바쁜 대기는 대기(시간)가 길 때는 피해야 한다. CPU가 낭비되는 시간을 다른 작업이 완료할 수 있도록 주어져야 한다. 반대로 낭비되는 시간이 짧으리라 예측되는 환경에서는 바쁜 대기가 사용된다.
---------------------------------------------------------------------------------------------------------------------------------------------------------
실제 C 프로그램이나 다른 프로그래밍 언어에서 잠금(lock)은 일반적으로 엄격한 순서를 지키기 위해 사용된다. 잠금은 쉽게 말해 객체 또는 변수이며, 상태가 충족되거나 이벤트가 발생하기를 기다리고자 사용한다.
(위에서 사용된 '완료' 는 잠금이 아닌 플래그이다)
잠금은 위의 2.2 명령어를 실행하기 전에 무한 루프에서 플래그의 변화를 얻으려는 것처럼 같은 매커니즘으로 잠금을 얻으려는 것이라고 생각하면 된다. 잠금을 얻어야만 루프를 계속해서 종료할 수 있다. 루프 안에서는 잠금을 사용할 수 있기를 기다린다.
[잠자기 / 알림 메커니즘]
- 위의 의사 코드에서 바쁜 대기 루프를 이용하는 대신, 다른 방식을 사용해 볼 수도 있다. 작업 Q는 '완료' 플래그에서 바쁜 대기를 하는 대신 잠들 수 있으며, 작업 P는 플래그를 참으로 만들 때 플래그의 변경에 대해 작업 Q에 알릴 수 있다.
즉, 작업 Q는 플래그가 참이 아님을 알자마자 잠자기에 들어가며 작업 P가 CPU코어를 더 빨리 얻도록 해서 로직을 실행하게 한다. 그 결과 작업 P는 플래그를 참으로 수정한 다음 작업 Q를 깨운다.
이러한 접근법은 대부분의 OS가 바쁜 대기를 피하고 더 효율적으로 제어 메커지즘을 사용하려는 관습적인(de facto) 구현이다.
다음의 의사코드를 통해 살펴보자
동시 시스템
{
작업 P
{
1.1. 'A'를 출력
1.2. 작업 Q에 알림
}
작업 Q
{
2.1. 잠자기 모드에 돌입
2.2. 'B'를 출력
}
}
작업이 잠들어 있는 한 CPU를 공유하지 않을 것이다. 작업이 잠자기 모드로 들어가면 작업 스케줄러는 이를 인지하고, 잠든 작업에겐 타임 슬라이스를 주지 않는다.
잠든 작업은 바쁜 대기에 들어가지 않으므로 CPU 시간을 낭비하지 않는다. 상태를 풀(pool)하기 위해 바쁜 대기를 하는 대신, 작업은 잠을 자며 상태가 충족될 때 알림을 받는다. 그러면 다른 작업이 사용할 수 있는 CPU 이용량(CPU utilization)이 많이 증가하고, CPU 공유가 필요한 작업이 이를 얻는다.
작업이 잠자기 모드가 될 때 깨워줄 메커니즘이 있어야 한다. 이 메커니즘은 일반적으로 잠든 작업에서 알림 또는 신호 전달(signaling)로 수행된다. 작업은 잠자기 모드를 종료하라고 알림을 받을 수 있고, 깨어나면 작업 스케줄러가 큐에 다시 넣고 CPU를 준다. 그런 다음 작업은 잠자기 모드에 들어갔던 다음 행부터 실행을 이어간다.
위의 코드에서 작업 Q는 실행되자마나 잠자기 모드에 들어간다. 잠자기 모드에 들어갔을 때 작업 P가 알림을 보내고 깨울 때까지 CPU를 점유하지 않는다. 작업 P는 'A'가 출력되었을 때 Q에 알린다. 그러면 작업 Q는 CPU를 얻고 계속해서 'B'를 출력한다.
이 방법은 위에서 설명했 듯 바쁜 대기가 없고 CPU의 시간도 낭비되지 않는다. 잠자기 모드로 들어가거나 잠든 작업을 깨울 때, 두 경우 모두 모든 대부분의 OS, 특히 POSIX 호환 OS가 지원하는 고유 시스템 호출이 있다.
언뜻 보면 위의 방법이 문제를 효율적으로 해결한 것처럼 보인다.
하지만 동기화 이후 문제를 야기하는 인터리빙 존재하는데 내용은 다음과 같은 순서로 진행되었을 때 발생한다.
'A' 를 출력
-> 작업 Q에 알림
-> 잠자기 모드 돌입
-> 'B' 를 출력
위의 인터리빙에서 작업 P는 'A'를 출력 했고, 그 다음 작업 Q에 알린다. 하지만 Q는 아직 CPU를 얻지 않았으므로 잠들지 않았고, CPU를 얻으면 즉시 잠들기 모드로 들어간다. 이후론 Q에 알려줄 실행 중인 작업이 아무것도 없기 때문에 작업 Q는 더이상 CPU를 얻지 못하게되는 반교착 상태를 일으킨다.
(작업 P가 먼저 실행된 관계로 작업 Q가 잠들기 전에 신호를 주기 때문에, 이 신호는 무의미한 행위가 되고, 작업 Q는 실행되자마자 잠들기 때문에 더이상 깨워줄 작업이 없어 'B'를 출력할 수 없게 된다)
이 문제를 해결하려면 불리언(boolean) 플래그를 다시 사용해야 한다.
다음과 같은 의사코드를 통해 불리언 플래그 사용 예시를 확인해보자
동시 시스템
{
공유 상태
{
완료 : 불리어 = 거짓
}
작업 P
{
1.1. 'A'를 출력
1.2. 완료 = 참
1.3. 작업 Q에 알림
}
작업 Q
{
2.1. 완료가 아닌(거짓) 동안
{
2.2. 완료가 거짓이라면 잠자기 모드에 돌입 //원자적
}
2.3. 'B'를 출력
}
}
이 의사코드에서 볼 수 있듯 작업 Q는 만약 플래그 '완료'가 참으로 설정되지 않으면 잠든다.
명령어 2.2 는 플래그를 체크하는 루프 안에 놓이며, '완료' 가 거짓 일 때만 잠든다.
명령어 2.2 에 대한 한가지 중요한 참고 사항은 반드시 원자 명령어야야 한다는 점이다. 그렇지 않으면 해결 방법은 완전할 수 없으며 똑같은 문제를 겪게 된다.
잠든 작업은 작업 P뿐만 아니라 시스템의 무언가에 의해 알림을 받으므로 루프가 필요하다. 실제 시스템에서 OS나 다른 작업은 한 작업에 알림을 줄 수 있다.
작업이 알림을 받고 깨어날 때 작업은 다시 플래그를 체크해야 하며, 만약 플래그가 아직 설정되니 않았다면 다시 자러 간다.
이 방법 또한 완벽한 해결 방법은 아니다. CPU 코어가 여러 개인 머신에서는 반교착 상태를 일으킬 수 있기 때문이다.
모든 동기화 메커니즘은 어떤 종류의 대기를 동반한다. 어떤 작업이 동기화되도록 하는 유일한 방법이다. 어느 지점에서는 작업의 일부가 대기해야만 하고 다른 작업들은 계속되어야 한다.
이 문제에서 바로 세마포어(semaphore)를 도입해야한다.
세마포어는 동시 환경에서 로직이 대기하거나 계속하도록 하는 표준 도구이다.
[세마포어 / 뮤텍스]
- 네덜란드의 유명한 컴퓨터 과학자이자 수학자인 에츠허르 다익스트라(Edsger Dijkstra) 와 그의 팀이 당시 고유한 아키텍처를 가진 Electrologica X8 컴퓨터용 'THE Multiprogramming System' 또는 'THE OS'를 1960년대 설계했다.
벨 연구소가 UNIX 와 C 를 발명하기까지 10년 채 안남은 시기였다. 그들은 THE OS를 작성하기 위해 어셈블리어를 사용했다. THE OS 는 자둥 적업 OS였으며 다층적인 아키텍처였다. 최고 수준은 사용자였으며 가장 낮은 수준은 작업 스케줄러였다. UNIX 용어로 가장 낮은 수준이란 작업 스케줄러와 프로세스 관리 유닛이 모두 커널 링에 있다는 의미이다. 다익스트라와 그의 팀이 동시성과 관련된 어려움을 극복하고, 다른 작업 간 다른 리소스를 공유하기 위해 고안한 아이디어는 세마포어라는 개념이었다.
세마포어란 공유 자원에 대한 접근을 동기화할 때 사용하는 변수 또는 객체이다. 작업이 공유 자원에 접근하려 할 때, 이 공유 자원은 먼저 미리 정의된 세마포어를 검사해야 하고, 공유 자원에 계속해서 접근할 수 있는 권한을 요청해야 한다.
각 세마포어는 공유 자원에 대한 접근을 획득하기 위해 대기하는 작업 대기열이 있는데 이를 임계 구역(critical section)이라고 한다.
임계 구역이란 세마포어가 보호하는 간단한 명령어 집합이다. 작업은 세마포어 뒤에서 기다리지 않고서는 임계 구역에 들어갈 수 없으며, 이 임계 구역을 보호하는 것이 세마포어의 역할이다. 작업이 임계 구역에 들어가려고 할 때마다 특정 세마포어에 알려야 한다.
마찬가지로 작업이 완료되고 임계 구역에서 나가려 할 때 작업은 동일한 세마포어에 이를 알려야 한다.
다음 의사 코드를 통해 공유된 카운터를 증가시키는 두 작업에 관해 세마포어를 기반으로 해결 방안을 알아보자
동시 시스템
{
공유 상태
{
S : 한 번에 하나의 작업만 허용하는 세마포어
카운터 : 정수 = 0
}
작업 P
{
A : 지역 변수
1.1. 임계구역 진입 : EnterCriticalSection(S)
1.2. A = 카운터
1.3. A = A + 1
1.4. 카운터 = A
1.5. 임계구역 떠나기 : LeaveCriticalSection(S)
}
작업 Q
{
B : 지역 변수
2.1. 임계구역 진입 : EnterCriticalSection(S)
2.2. B = 카운터
2.3. B = B + 2
2.4. 카운터 = B
2.5. 임계구역 떠나기 : LeaveCriticalSection(S)
}
}
이 시스템에서는 서로 다른 두 공유 상태가 있다. 공유된 세마포어 S는 다른 공유된 카운터에 대한 접근을 보호하게 되어 있으며, 한 번에 하나의 작업만이 자신이 보호하는 임계 구역에 들어갈 수 있도록 한다.
임계 구역은 EnterCriticalSection(S) 와 LeaveCriticalSection(S) 명령어를 동반하며, 각 작업엔 S가 보호하는 서로 다른 임계 구역이 있다.
작업은 임계 구역에 들어가려면 EnterCriticalSection(S)를 실행해야한다. 만약 다른 작업이 이미 자신의 임계 구역에 있다면 EnterCriticalSection(S)는 블로킹되어 종료되지 않는다. 그러므로 현재 작업은 세마포어가 통과시켜 임계 구역에 들여보내 줄 때까지 기다려야 한다.
EnterCriticalSection(S) 명령어는 시나리오에 따라 다양하게 구현할 수 있다. 단순히 바쁜 대기일 수도 있고, 대기 중인 작업을 잠들게 할 수도 있다. 후자의 접근법이 더 일반적이며, 임계 구역을 기다리는 작업은 보통 잠들기 상태가 된다.
위의 예제에서 세마포어 S는 하나의 작업만이 임계 구역에 들어갈 수 있도록 사용되었다. 하지만 세마포어의 범주는 더 넓으며, 두 개 이상(세마포어가 생성될 때 정의된 특정 숫자까지)의 작업이 임계 구역에 들어가도록 할 수 있다. 한 번에 하나의 작업만 임계 구역으로 들어가게 하는 세마포어는 보통 이진 세마포어(binary semaphore) 또는 뮤텍스(mutex)라고 한다.
뮤텍스틑 세마포어보다 훨씬 더 일반적이며 동시적인 코드에서 항상 볼 수있다. POSIX API 는 세마포어와 뮤텍스를 둘 다 제공하므로 상황에 따라 이들을 사용할 수 있다.
'뮤텍스' 라는 용어는 상호 배제(mutual exclusion)를 의미한다. 작업이 두 개 있고 각 작업에는 같은 공유 자원에 접근하는 임계 구역이 있다고 가정했을 때, 경쟁 상태가 없는 상호에는 배제를 기반으로 한 해결 방법을 위해서는, 작업에 대해 다음 상태가 충족 되어야 한다.
ㅡ 언제든 작업 중 하나만 임계 구역에 들어갈 수 있으며, 다른 작업은 이 작업이 임계 구역을 떠날 때까지 기다려야 한다.
ㅡ 해결 방법에는 교착 상태가 없어야 한다. 임계 구역에 입장하기를 기다리는 작업은 결국 들어갈 수 있어야 한다. 때에 따라서는 대기 시간의 상한선(경합 시간 contention time)을 정한다.
ㅡ 임계 구역에 있는 작업은 다른 작업이 임계 구역에 들어가기 위해 선점(preemption)해 빼낼 수 없다. 즉, 이 해결 방안은 선점이 없어야 하고(preemption free) 협조적(collaborative)이어야 한다.
상호 배제를 기반으로 한 해결책을 개발하기 위해 뮤텍스가 존재하며, 임계 구역도 비슷한 조건을 따라야 하니 주의해야 한다. 임계 구역 내부에는 하나의 작업만 허용할 수 있으며 교착 상태가 없어야 한다. 세마포어 역시 이 두 가지 조건을 만족해야 하지만, 임계 구역에 한 번에 두 개 이상의 작업이 들어갈 수 있게 허용할 수 있다는 점도 주의해야 한다.
상호 배제는 동시성에서 가장 중요한 개념이며, 다양한 제어 메커니즘의 지배적욘 요인이라고 할 수 있다. 즉, 모든 동기화 기술에서 세마포어와 뮤텍스를 사용하는 상호 배제의 흔적을 보게 된다.
세마포어와 뮤텍스는 잠글 수 있는(lockable) 객체라고 한다. 좀 더 공식적인 용어로는, 세마포어를 기다리는 행위와 임계 구역에 입장하는 행위는 세마포어 잠금(lock)과 같다. 마찬가지로 세마포어를 떠나거나 세마포어를 업데이트하는 것 역시 세마포어 잠금 해제(unlock)와 같다.
그러므로 세파모어의 잠금과 해제는 각각 임계 구역에 대한 대기 및 접근 획득, 임계 구역 해제에 사용되는 두 가지 알고리즘이라고 볼 수 있다. 예를 들면 스핀락(spin lock)은 세마포어에서 바쁜 대기에 의해 임계 구역에 대한 접근 권한을 얻는 것이다. 그리고 당연히 다른 유옇의 잠금 및 해제 알고리즘도 존재한다.
잠금 및 해제를 기반으로 다음과 같은 의사 코드를 작성할 수 있다.
동시 시스템
{
공유 상태
{
S : 한 번에 하나의 작업만 허용하는 세마포어
카운터 : 정수 = 0
}
작업 P
{
A : 지역 변수
1.1. 잠금 Lock(S)
1.2. A = 카운터
1.3. A = A + 1
1.4. 카운터 = A
1.5. 잠금 해제 Unlock(S)
}
작업 Q
{
B : 지역 변수
2.1. 잠금 Lock(S)
2.2. B = 카운터
2.3. B = B + 2
2.4. 카운터 = B
2.5. 잠금 해제 Unlock(S)
}
}
여러 작업이 임계 구역에 들어가려 할 때 작업들은 세마포어를 잠그려 하지만, 세마포어에 따라 특정한 수의 작업만이 잠금을 얻어서 임계 구역에 들어가고 다른 작업들은 잠금을 얻기 위해 기다린다. 세마포어에 대해 잠금을 얻으려는 대기를 경합(contention)이라고 한다. 작업이 더 많아지면 경합도 더 많아지며, 경합 시간은 작업의 실행이 얼마나 느려질지에 대한 척도가 된다.
분명 작업이 잠금을 획득하는 경합에 있을 때는 시간이 조금 걸리며, 더 많은 작업이 있을수록 임계 구역에 들어가려면 더 오래 기다려야한다. 경합 상태(contention state)에서 작업이 대기하는 시간을 경합 시간이라고 한다. 경합 시간은 성능 저하를 방지하기 위해 주의 깊에 모니터링해야 하는 동시 시스템에서 비기능적 요구 사항일 수 있다.
뮤텍스는 어떤 동시 작업을 동기화하는 주요 도구라고 결론 내릴 수 있다. 또한 뮤텍스는 POSIX 스레딩 API 및 동시성을 지원하는 거의 모든 프로그래밍 언어에 있다. 뮤텍스와는 별도로 조건 변수 또한 특정 상태가 충족되기 위해 무한히 대기해야 할 때 중요한 역할을 한다.
조건 변수에 관한 내용 설명과 더불어 메모리 장벽(memory barrier) 과 멀티 CPU나 멀티 코어 CPU와 같은 멀티프로세서 유닛이 있는 동시 환경에 대한 내용을 동시성 3 에서 다루고자 한다.
