(4) Deadlock / 세마포어 & 뮤텍스

 

TL;DR

• Race condition이란? 2개 이상의 프로세스(스레드)들이 하나의 자원(공유 자원)에 동시에 접근하려 경쟁하는 상태
• Critical section(임계구역)이란? 공유 데이터에 접근하려는 코드를 의미한다.
• 뮤텍스란? 하나의 스레드만이 공유자원에 접근할 수 있도록하여 경쟁 상황을 방지하는 기법
• 세마포어란? 임계 구역에 여러 스레드가 들어갈 수 있고, counter를 두어서 허용 가능한 스레드를 제한해 경쟁 상황을 방지하는 기법 
• Deadlock 이란? 둘 이상의 프로세스가 서로가 가진 자원을 필요로 하며 무한 대기에 빠지는 상황이다.

 

 

---

동기화 문제

둘 이상의 프로세스나 스레드가 공유 데이터에 접근하는 상황, 즉 경쟁 상태를 해결하는 방법이다.
Concurrency Control (병행 제어) 와 같은 표현이다.

 

✅ Race Condition (경쟁 상태)

2개 이상의 프로세스(스레드)들이 하나의 자원(공유 자원)에 동시에 접근하려 경쟁하는 상태이다. 여러 프로세스가 공유 자원을 사용한다고 해서 무조건 Race Condition에 놓이는 것은 아니다. kernel 내부 데이터에 동시에 접근하려 해야 Race Condition에 놓였다고 할 수 있다.

• CPU가 여러개인 Multiprocessor System의 경우 메모리를 공유하므로 문제가 발생할 수 있다.
• 여러 프로세스들이 공유 메모리를 사용할 때 커널 내부 데이터를 접근하는 루틴들이 겹치면 문제가 발생할 수 있다.

 

🔺 Race Condition 예시

 

✅ Critical Section (임계 구역)

공유 데이터에 접근하려는 코드를 의미한다.

• 하나의 프로세스가 자신의 임계구역을 수행하는 동안에는 다른 프로세스는 그들의 임계구역에 들어갈 수 없어야 한다. 즉 임계구역 내의 코드는 원자적으로 실행되어야 한다.
• (임계구역에 진입하는 부분을 entry section이라고 부르고 임계구역에서 나오는 부분은 exit section이라고 부른다.)
• 임계 구역에 대한 접근을 제한하기 위해 locking 메커니즘이 필요하다.

 

✅ 동기화 문제 해결 방법

🔺 Mutex

• 하나의 스레드만이 공유자원에 접근할 수 있도록하여 경쟁 상황을 방지한다.
• lock의 획득과 반환을 통해 공유자원 접근을 제어한다.
  임계 구역에 들어갈 때 락을 획득(Acquire)한 스레드가 나올 때 해제(Release) 할 때까지 다른 프로세스 또는 스레드가 접근하지 못하도록 한다.
• busy waiting을 통해 CPU가 낭비된다 = 성능상의 이슈가 있을 수 있다.

 

🔺 Semaphore

• 임계 구역에 여러 스레드가 들어갈 수 있고, counter를 두어서 허용 가능한 스레드를 제한한다.
  • 가용 자원의 수를 S값으로 초기화하고, 자원에 접근할 때에는 S-- 연산을 수행하여 세마포어 값을 감소시키고 자원의 사용이 끝나면 S++ 연산을 수행하여 세마포어 값을 증가시킨다.
  • 세마포어 값이 0이 되면 모든 자원이 사용중인 것을 의미하고 이후 자원을 사용하려는 프로세스는 세마포어 값이 0보다 커질 때까지 block 된다.
  • 현재 수행 중인 스레드가 아닌 다른 스레드가 세마포어를 해제할 수 있다.
• wait 함수와 signal 함수를 사용
• busy waiting을 통해 CPU가 낭비된다

 

👆 Busy Waiting 해결 방법?

Block and wake up 방식

• 자원 획득을 희망하지만 자원을 획득할 수 없는 프로세스는 block 시킨다
  → block된 프로세스의 PCB를 semaphore의 wait-queue에 넣는다.
• 다른 프로세스가 자원을 반납하면 block된 프로세스들 중 하나가 wakeup 된다.
  → wakeup된 프로세스의 PCB를 ready-queue로 옮긴다.

 

• 단, 프로세스의 상태를 block에서 ready로 변경하는 데에 따른 오버헤드가 있다.

 

 

🔺 Monitor

• 프레임워크나 라이브러리 그 자체에서 제공되는 동기화 기법
  • 모니터 내에서는 한 번에 하나의 프로세스 만이 활동할 수 있다.
  • 공유 데이터는 monitor 내부의 procedure를 통해서만 접근할 수 있다.
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.

 

 

Deadlock

데드락이란 시스템 자원에 대한 요구가 뒤엉킨 상태이다. 즉, 둘 이상의 프로세스가 서로가 가진 자원을 필요로 하며 무한 대기에 빠지는 상황이다.

 

 

✅ Deadlock 발생 조건

상호 배타, 보유 및 대기, 비선점, 환형 대기 4가지 조건이 모두 만족될 때 발생할 수 있다.

• 조건1) Mutual exclusion (상호 배타)
  • 자원 공유가 불가능하다.
  • 예를 들어 특정 자원의 인스턴스가 2개이면 최대 2개의 프로세스만 해당 자원을 사용할 수 있다.
• 조건2) Hold and wait (보유 및 대기)
• 조건3) No Preemption (비선점)
  • 다른 프로세스가 보유중인 자원을 뺏어올 수 없다.
• 조건4) Circular wait (환형 대기)
  • 자원 할당도 상에 원이 만들어져야 한다.
  • 자원 할당도 : 자원은 네모로, 자원의 인스턴스는 점으로, 프로세스는 원으로, 자원의 할당은 화살표로 표시된다.

 

✅ Deadlock 처리 방법

1. 교착 상태 방지 : 데드락의 발생 조건을 막는다.

• 상호 배타 방지 : 자원을 공유 가능하게 한다.
  • 원천적으로 불가능한 경우가 대부분
    → CPU, 메모리, 디스크, 프린트 모두 불가능하고 read only 파일 정도만 가능하다.
• 보유 및 대기 방지
  • 프로세스가 동시에 모든 자원을 잡거나 순차적으로 자원을 잡는 경우 다 잡지 못하면 소유한 자원을 놓는다.
  • 자원 활용률이 저하되거나 기아(starvation) 문제가 발생할 수 있다.
• 비선점 방지 : 자원을 선점 가능하게 한다.
  • 원천적으로 불가능한 경우가 대부분
    → 프린터 선점을 가능하게 하면 난리가 날 것.. CPU context switching을 강제로 할 수는 있겠으나 부작용이 있을 것이다.
• 환형 대기 방지 : 자원에 번호를 부여해 오름차순으로 요청하게 한다던가 등의 방법
  • 자원 활용률이 저하되는 문제

2. 교착 상태 회피 : 프로세스의 자원 요청을 신중하게 승인한다.

• OS가 안전하게(교착 상태 발생하지 않게) 자원을 할당해주기

3. 교착 상태 검출 및 복구

• 주기적으로 검사해서 교착 상태 발생하면 복구하기
• 검사에 따른 overhead 발생
• 복구 시에는 이전 상태로 되돌려야 하므로, 이전 상태 기억해야 하는 비용이 발생된다.

4. 교착 상태 무시

• 교착 상태 잘 일어나지 않으니까 발생하면 기기 재시동하기 ㅎ