동기화와 교착상태(Deadlock)

✔️ 동기화 문제란?

multi process/thread 환경에서 서로 다른 thread가 메모리 영역을 공유하기 때문에 여러 thread가 동일한 자원에 동시에 접근하여 엉뚱한 값을 읽거나 수정하게 되는 동기화 문제가 발생

 

💡 해결 방법

1. Mutex
1개의 스레드만이 공유 자원에 접근할 수 있도록 한다. 경쟁 상황을 방지하는 기법으로 공유 자원을 점유하는 thread가 lock을 걸면, 다른 thread는 unlock 상태가 될 때까지 해당 자원에 접근할 수 없다. (Mutex == binary Semaphore)

acquire()
//critical section (공유 자원을 사용할 수 있는 영역)
release()

2. Semaphore

S개의 thread만이 공유 자원에 접근할 수 있도록 제어하는 동기화 기법. 자원에 접근할 때는 S—, 방출할 때는S++             

semaphore 변수의 값만큼 process/thread들이 동시에 자원에 접근 세마포 값이 0이 되면 모든 자원이 사용 중임.

 

semaphore가 2이고, thread1, 2, 3 (이하, T1, 2, 3)가 동시에 공유 자원에 접근하려고 한다고 가정하자.

만약 T1, T2, T3를 순서대로 실행하고 싶은데, Semaphore가 2라면 S:0 일 때, T3는 실행 될 수 없다.

S: 2 → 1 → 0 → 1 → 0 → 1 → 2
T1 실행 S-- → T2 실행 S-- → T1 종료 S++ → T3실행 S-- → T2 종료 S++→ T3 종료 S++

T3는 T1이 종료되는 시점에 실행이 가능하다.

wait(s)
//critical section (공유 자원을 사용할 수 있는 영역)
signal(s)

 

Mutex는 Semaphore가 0과 1 두 개밖에 존재하지 않는 binary semaphore라고 말하기도 한다.

---

✔️ 교착 상태

둘 이상의 thread가 각기 다른 thread가 점유하고 있는 자원을 서로 기다릴 때, 무한 대기에 빠지는 상황

Deadlock이 일어나는 상황(동시에 모두 성립 해야 한다.)

1. 상호 배제(mutual exclusion)

• 동시에 한 thread만 자원을 점유할 수 있는 상황
• 다른 thread가 자원을 사용하려면 자원이 방출될 때까지 기다림

2. 점유대기(hold-and-wait)

• thread가 자원을 보유한 상태에서 다른 thread가 보유한 자원을 추가로 기다리는 상황

3. 비선점(no preemption)

• 다른 thread가 사용 중인 자원을 강제로 선점할 수 없는 상황
• 자원을 점유하고 있는 thread에 의해서만 자원이 방출 

4. 순환 대기(circular wait)

• 대기 중인 thread들이 순환 형태로 자원을 대기하고 있는 상황

💡 해결 방법

• 무시
  deadlock 발생 확률이 낮은 시스템에서 아무런 조치도 취하지 않고 deadlock을 무시하는 방법
  → 시스템 성능 저하가 없다는 장점이 있다. 현대에는 deadlock이 잘 발생하지 않고, 해결 비용이 크기 때문에 무시 방법이 많이 사용
• 예방
  교착 상태의 4가지 중 하나가 성립하지 않게 하는 방법
  → 순환 대기 조건이 성립하지 않도록 하는 것이 현실적으로 가능하나, 자원 사용의 효율성이 떨어지고 비용이 크다.
• 회피
  thread가 앞으로 자원을 어떻게 요청할지에 대한 정보를 통해 순환 대기 상태가 발생하지 않도록 자원을 할당
  → 자원 할당 그래프 알고리즘을 사용하여 deadlock회피.
• 탐지-회복
  시스템 검사를 통해 deadlock 발생을 탐지, 이를 회복
  → 자원 사용의 효율성이 떨어지고 비용이 크다.