[OSTEP 운영체제 정리] - Concurrency Problem

비 교착 상태 오류

원자성 위반 오류( atomicity violation )

다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성이 보장되지 않았다.
즉, 코드의 일부에 원자성이 요구되었으나, 실행 시에 그 원자성이 위반되었다.

**[MySQL]**
Thread 1:
if (thd->proc_info) {
	...
	fputs(thd->proc_info, ...);
	...
}
Thread 2:
thd->proc_info = NULL;

thd 자료 구조의 proc_info필드를 두개의 다른 쓰레드가 접근한다.

Thread 1: 값이 NULL인지 검사후 값을 출력

Thread 2: 값을 NULL로 설정

만약 스레드 1이 체크(즉, if)를 수행한 후 fputs()를 호출하기 전에 인터럽트가 걸리면, 스레드 2가 그 사이에 실행되어 포인터를 NULL로 설정할 수 있다. ➡️ 크래시 발생

 

해결 방법 : proc_info 접근시 proc_info_lock이라는 변수 획득

pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;

Thread 1:
pthread_mutex_lock(&proc_info_lock);
if (thd->proc_info) {
	...
	fputs(thd->proc_info, ...);
	...
	}
pthread_mutex_unlock(&proc_info_lock);

Thread 2:
pthread_mutex_lock(&proc_info_lock);
thd->proc_info = NULL;
pthread_mutex_unlock(&proc_info_lock);

순서 위반 오류( order violation )

• 두 (그룹의) 메모리 접근 간의 원하는 순서가 바뀌었다.
• A는 항상 B보다 먼저 실행되어야 하지만, 실행 중에 이 순서가 강제되지 않는다.

Thread 1:
void init() {
	...
	mThread = PR_CreateThread(mMain, ...);
	...
}
Thread 2:
void mMain(...) {
	...
		mState = mThread->State; 
	...
}

Thread2: mThread 변수가 이미 NULL이 아닌 것으로 초기화 된다고 가정

1이 먼저 실행되지 않았다면 2는 NULL 포인터를 사용하기 때문에 크래쉬된다.

?

만약 스레드 2가 생성되자마자 실행된다면, 스레드 2 내에서 mMain()이 호출될 때 mThread 의 값이 설정되지 않을 것이다. → 이로 인해 NULL 포인터 역참조가 발생할 수 있다.

해결방법 : 순서를 강제하자 ⇒ 이러한 종류의 동기화는 컨디션 변수 !!

pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER; //락
pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER; //컨디션 변수
int mtInit = 0; // 상태 변수

Thread 1:
void init() {
	...
	mThread = PR_CreateThread(mMain, ...);
	// 쓰레드가 생성되었다는 것을 알리는 시그널
	pthread_mutex_lock(&mtLock);
	mtInit = 1;
	pthread_cond_signal(&mtCond);
	pthread_mutex_unlock(&mtLock);
	...
}

Thread 2:
void mMain(...) {
	...
	// 쓰레드가 초기화 되기를 대기
	pthread_mutex_lock(&mtLock);
	while (mtInit == 0)
	pthread_cond_wait(&mtCond, &mtLock);
	pthread_mutex_unlock(&mtLock);
	mState = mThread->State;
	...
}

교착 상태 오류

Circular dependencies

Thread 1:
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);
Thread 2:
pthread_mutex_lock(L2);
pthread_mutex_lock(L1);

락 L1을 가진 쓰레드1은 다른락 L2를 기다림. 그렇지만 L2가 가짐.. → DeadLock

Context switch 로 인해 L1 획득후, Thread2 실행

교착 상태는 왜 발생하는가

1. 코드가 많아지면서 구성 요소 간에 복잡한 의존성이 발생하기 때문 [ 예시 : 운영체제 ]파일 시스템은 블록을 읽어들이기 위해 메모리 페이지가 필요할 수 있으며, 따라서 가상 메모리 시스템에 접근하게 된다. (FS -> VMS)
2. 가상 메모리 시스템은 디스크에서 블록을 페이징하기 위해 파일 시스템에 접근해야 할 수 있다 (VMS -> FS)
3. 캡슐화(encapsulation) 의 성질 때문v1에 더해지는 벡터뿐만 아니라 인자로 전달되는 v2에 대한 락도 같이 획득해야한다. 그렇지 않을 경우 교착 상태 발생
4. Vector v1, v2; Thread 1: v1.AddAll(v2); Thread 2: v2.AddAll(v1);

🌟교착 상태 발생 조건 4가지조건 충족 🌟

상호배체 (Mutual Exclusion)

: 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장한다.

점유 및 대기(Hold-and-wait)

: 쓰레드가 자신에게 할당된 자원(이미 획득한 락)을 점유한 채로 다른 자원을 대기한다.

비선점(No preemption)

: 자원(락)을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수는 없다.

순환 대기(Circular wait)

: 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원(락)을 갖고 있는 쓰레드들의 순환 고리가 있다.

교착 상태의 예방

순환 대기(Circular wait)

락 획득을 하는 전체 순서를 정한다.

L1과 L2가 두개의 락만이 시스템에 존재한다면 L1을 무조건 L2전에 획득하도록 하면 교착 상태를 피할 수 있다.

복잡할 경우, 부분 순서 를 제공(Partial ordering)

Linux의 메모리 메핑 과정, 락에 대한 획득 순서들이 있다.

---

 

점유 및 대기(Hold-and-wait)

pthread_mutex_lock(prevention);
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);
...
pthread_mutex_unlock(prevention);

원자적으로 모든 락을 단번에 획득하도록 하면 예방할 수 있다.

---

비선점(No preemption)

top:
pthread_mutex_lock(L1);
if (pthread_mutex_trylock(L2) != 0) {
pthread_mutex_unlock(L1);
goto top;
}

pthread_mutex_trylock()

락을 획득하거나 현재 락이 점유된 상태이니 락을 획득하기 원한다면 나중에 다시 시도하라는 것을 알리는 -1 값을 리턴한다.

새로운 문제 발생 : LiveLock( 무한 반복 )

두개의 쓰레드가 시도를 반복하며 획득을 실패 ⇒ 무한 반복

해결 방법 : 반복문에 지연시간을 랜덤으로 조절하는 것이다.

---

상호배체 (Mutual Exclusion)

wait-free(대기없는) 자료구조로 해결된다? !

int CompareAndSwap(int *address, int expected, int new) {
	if (*address == expected) {
		*address = new;
		return 1; // 성공
	}
	return 0; // 실패
}

//어떠한 값을 원자적으로 임의의 크기만큼 증가하는 경우
void AtomicIncrement(int *value, int amount) {
	do {
		int old = *value;
	} while (CompareAndSwap(value, old, old + amount) == 0);
}

락을 획득하여 값을 갱신한 후에 락을 해제하는 대신,
이 코드에서 CompareAndSwap 명령어를 사용하여 값에 새로운 값을 갱신하도록 반복 시도
이와 같은 방식을 사용하면 락을 획득할 필요가 없으며 교착상태 발생할 수도 없다.

 

[ 리스트 삽입 예제 : 리스트 헤드에 개체를 삽입하는 코드이다. ]

간단한 삽입문을 실행하는 이 코드가 만약 여러 쓰레드에 의해 동시에 호출이 되면 경쟁 조건이 발생된다.
void insert(int value) {
	node_t *n = malloc(sizeof(node_t));
	assert(n != NULL);
	n->value = value;
	n->next = head;
	head = n;
}

삽입문의 앞뒤에 락의 획득과 해제 코드를 두어 해결하는 방법이 있긴하다.

void insert(int value) {
	node_t *n = malloc(sizeof(node_t));
	assert(n != NULL);
	n->value = value;
	pthread_mutex_lock(listlock); // 임계 영역의 시작
	n->next = head;
	head = n;
	pthread_mutex_unlock(listlock); // 임계 영역의 끝
}

void insert(int value) {
	node_t *n = malloc(sizeof(node_t));
	assert(n != NULL);
	n->value = value;
	do {
		n->next = head;
	} while (CompareAndSwap(&head, n->next, n) == 0);
}

스케줄링으로 교착상태 회피하기

쓰레드 4개가 프로세서 두개에 스케줄링

옆에는 쓰레드들의 락 요청에 대한 정보를 정리한 것

똑똑한 스케줄러라면 T1과 T2를 동시에 실행만 하지 않는다면 교착 상태가 절대 발생하지 않도록 할 수 있다.

발견 및 복구

마지막 전략은 교착 상태 발생을 허용하고,

교착 상태를 발견하면 복구하도록 하는 방법이다.

---

[출처]
https://github.com/remzi-arpacidusseau/ostep-translations/blob/master/korean/README.md

ostep-translations/korean/README.md at master · remzi-arpacidusseau/ostep-translations

 

해당 책을 기반으로 정리하였습니다.