[OS] CH32_Concurrency Bug: Deadlock 발생 조건 & 예방법

32.2 Non-Deadlick bugs

non-deadlock bugs의 두가지 주요 타입: atomicity violation bugs and order violation bugs.

 

Atomicity-Violation Bugs

- atomicity violation: 코드는 atomic한데 실행시에는 그렇지 않음

- ex)

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

 Thread 2::
 thd->proc_info = NULL;

thread1이 proc_info가 null이 아니여서 fputs()을 하려고 하는 직전에 interrupt가 되서 thread2가 실행되면,

thread2가 info가 null이 되고, thread1이 다시 이어 실행하면 info가 null인데 fputs()실행됨

 

- 해결책:

  공유되는 변수 참조 주변에 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 Bugs

- order violation: A가 항상 B전에 실행되는데 순서가 실행 중에 강요되지 않은 경우

- 해결책:

  condition variables 사용하기, lock 사용하기, state variable 사용

  

 

 32.3 Deadlock Bugs

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

thread1이 lock1을 잡고 lock2를 기다리는데, thread2가 lock2를 잡고 lock1을 기다리는 상황.

 

 

Deadlocks은 왜 발생하는가?

- 구성 요소들 사이에 복잡한 종속성이 발생

- encapsulation의 본질 때문에

  modularity는 lock과 잘 맞지 않음

ex) java vector class & AddAll()

Vector v1,v2;

v1.AddAll(v2); // v2의 모든 데이터를 v1에 옮김

이 코드를 실행 중에 다른 thread가 v2.AddAll(v1) 실행하면 deadlock 발생함

 

Conditions for Deadlock

deadlock 발생 4가지 조건

- Mutual exclusion

- Hold-and-wait:

thread는 추가적인 자원(획득하려는 lock)을 얻기를 기다리는 동안 이미 보유한 자원(이미 획득한 lock)을 가지고 있는다

- No preemption:

자원들은 이를 획득한 thread로부터 제거되지 않는다.

- Circular wait:

각각의 thread들이 하나 이상의 체인의 다음 thread로부터 요청 받아지는 자원을 가지고 있는 circular chain이 존재 

 

4조건 중 하나라 해당되지 않으면 deadlock은 발생하지 않음

 

Prevention

- Circular wait

해결책: lock획득의 total ordering를 제공 

lock이 여러개이고 복잡한 시스템에서는 전체 순서 제공하는게 힘드므로 partial ordering 제공

ex) 메모리 매핑에서의 partial lock ordering

if (m1 > m2) { // grab in high-to-low address order
	pthread_mutex_lock(m1);
	pthread_mutex_lock(m2);
} else {
	pthread_mutex_lock(m2);
	pthread_mutex_lock(m1);
}

 

- Hold-and-wait

해결책: 모든 lock들을 한번에 얻기

pthread_mutex_lock(prevention); // begin acquisition
2 pthread_mutex_lock(L1);
3 pthread_mutex_lock(L2);
4 ...
5 pthread_mutex_unlock(prevention); // end

prevention lock 사이에서 thread switch 일어나지 않음을 보장

문제점:

1. 구현할 때, 어떤 lock들이 필요한지 미리 알아야 함 -> 어렵

2. 동시에 작업하기 힘들어짐 -> concurrency 감

 

- No Preemption

해결책: pthread_mutex_trylock() 같이 계속 lock을 기다리지 않고 리턴하는 방식 이용

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

L1을 얻고 L2를 얻으려는데 못 얻으면 L1도 포기하고 돌아감 (다음에 다시 시도)

 

문제점:

- livelock

두 개의 thread가 반복적으로 이 시퀀스 시도하고 둘 다 실패하는 것을 반복하면 진행되지 않음

예를 들어, T1이 L1을 얻고 L2를 얻으려고 시도했는데 T2가 가지고 있어서 포기하고 L1도 놓고 돌아감

이 때, T2는 L2를 얻고 L1을 얻으려는데 T1이 가지고 있어서 포기하고 L2도 놓고 돌아감

다음에 또 동시에 T1은 L1, T2는 L2 먼저 잡게되면 이 루틴이 계속 반복되어 진행되지 않 

 

- Mutual Exclusion

해결책: 상호 배제의 필요성을 없애기. 강력한 하드웨어 명령어를 사용하여, lock이 필요없는 데이터 구조 만들기

ex) CompareAndSwap(int *address, int expected, int new);

 

 

Scheduling을 통한 Deadlock 해결

ex1)

     T1   T2   T3  T4
L1  yes  yes  no  no
L2  yes  yes  yes  no

ㄴ T1(thread)이 L1,L2 (lock) 필요로 함...

 

이 경우 영리한 스케쥴러라면 T1, T2를 동시에 실행시키지 않음 -> deadlock 발생 안함

T3랑 T1이랑 동시에 작동됨

 

ex2)

     T1   T2   T3  T4
L1  yes  yes  yes  no
L2  yes  yes  yes  no

 

Detect and Recover

deadlock을 일시적으로 허용해주고, deadlock을 탐지해서 조취 취하기