lock을 안걸어서 여러 메모리 접근의 일관성이 깨진다. 원하는 serializability(직렬화)가 깨진다. ex) MySQL에서 두 thread가 동일한 변수 (proc_info)에 접근하는 경우 → 해결! 공유변수 접근시 lock을 걸어준다.
Order violation(순서 위반)
두 메모리 접근 간의 원하는 순서가 뒤바뀌는 문제 실행 순서가 보장되지 않는다 ex) thread가 변수를 초기화하기 전에 접근하려는 경우 → 해결! 조건변수를 사용해 순서를 보장한다.
2. Deadlock(교착상태)
deadlock은 thread가 자원을 획득하고 다른 자원을 기다리면서 발생한다. 두 thread가 서로 상대방의 자원을 기다리면 deadlock이 발생한다.
→ cycle이 존재하면 deadlock 발생한다.
Deadlock이 발생하는 이유
Complex Dependency(복잡한 의존성) : 대규모 코드베이스에서 발생한다
Encapsulation(캡슐화): 구현 세부사항을 숨기고 모듈화된 sw를 쉽게 구축한다. 이런 modularity는 lock과 맞지 않다. ex) Java Vector의 Addall() 메서드 → 메서드객체에 대한 lock확보 후 parameter에 대한 lock 을 확보하려 한다면, v1과 v2 모두 공유변수가 되어야 한다.
Deadlock 조건 (Conditions for Deadlock)
Mutual Exclusion(상호배제): 스레드가 필요로 하는 자원을 독점적으로 사용.
Hold-and-wait(점유와 대기): 스레드가 자원을 보유(hold)한 상태에서 추가 자원을 기다린다.
No preemption(비선점): 자원을 강제로 회수할 수 없다.
Circular Wait(순환대기): 스레드가 자원을 요청하며 원형의 대기를 형성한다.
위 4가지 조건이 모두 만족될 때 deadlock이 발생한다. 하나라도 만족하지 않으면 deadlock은 발생하지 않는다.
3. Deadlock Characterization
System Model
각 자원은 여러 인스턴스를 가질 수 있다.
thread가 resource를 사용하는 방법
request(요청) → use(사용) → release(해제)
Resource-Allocation Graph(자원할당 그래프)
그래프는 정점 V와 간선 E의 집합이다.
정점 V는 1. T(스레드) 2. R(자원) type으로 구분한다
간선 E는 1. request(요청) 간선 [T -> R] 2. assignment(할당) 간선[[R -> T]으로 구분한다.
그래프 내 cycle없으면 deadlock 아니다.
cycle 존재하면 deadlock 있을 수도 있다. (모든 resource의 instance=1)
4. Methods for Handling Deadlocks (deadlock 처리방법)
Deadlock을 처리하는데는 3가지 방법이 있다
① 시스템이 deadlock으로 절대 들어가지 않도록 보장
Deadlock Prevention (교착상태 예방)
deadlock 발생조건 4가지 중 적어도 1개가 성립하지 않도록 보장해 교착상태를 예방한다.
1. Circular wait prevention (순환 대기 방지) lock 획득 순서를 정해서 순환대기를 방지한다. ex) 2개의 lock L1, L2가이 있는 경우 항상 L1을 먼저 획득하도록 규칙을 정한다. lock(L1); lock(L2);
문제점! 순서라는게 단순한 규칙에 불과하기 때문에 익숙하지 않은 개발자들이 이것을 무시할 수 있다.
2. Hold-and Wait prevention (점유와 대기 방지) 모든 lock을 한번에, atomically(원자적으로)하게 획득하도록 한다. ex) lock(prevention); lock(L1); lock(L2); unlock(prevention);
문제점! 미리 모든 lock을 획득해야 하기 때문에 불필요한 대기가 생기게 된다 -> Decrease concurrency
3. No Preemption Prevention (비선점 방지) multiple lock(여러 lock) 획득할 때 하나의 lock이 대기 중이면 현재 보유한 lock을 모두 해제(unlock)한 후에 다시 시도한다. -> trylock()
문제점! 시스템이 반복적으로 같은 코드 순서를 진행하며 진행이 안되는 상황인 livelock이 발생할 수 있다. 해결책! 다시 loop하기 전에 random delay를 추가한다 -> 문제점! 캡슐화로 인해 특정 자원이 깊은 곳에 있을 경우 처음부터 다시 시도하는 것이 어려울 수 있다.
4.Mutual Exclusion Prevention (상호배제 방지) 강력한 hardware instruction(하드웨어 명령어)를 사용하여 lock을 사용하지 않고 data sturcturefmf 빌드한다. wait free - compare-and-swap: no lock, no deadlock, but livelock 발생 가능성 있다. ex) [List Insert]
문제점! list에 값을 삽입하는 경우에 race condition이 발생.
해결책! 1. lock 과 unlock코드를 추가한다. 2. compare-and-swap 명령어를 사용해 lock없이 삽입
Deadlock Avoidance (교착상태 회피) : thread가 일생동안 요구하고 사용할 자원에 대한 부가정보를 사전에 제공받아 자원을 할당한다.
② deadlock 감지 및 복구 : deadlock 발생할 수 있도록 허용하고, deadlock 발생 시 이를 감지하고 복구하는 방법.
③ 문제 무시하고 deadlock 발생하지 않은 척 : 저비용 해결책, 수작업으로 재시작 필요,
