728x90

OS 데드락
데드락 조건 4가지
동기화(뮤텍스, 세마포어, 모니터, 스핀락, 어토믹 설명)

들어가기 전

동시다발적으로 실행되는 프로세스(스레드)들은 서로 협력하며 영향을 주고받는다.
이때, 자원의 일관성을 보장하기 위해 프로세스 동기화를 고려해야 한다.
실행 문맥을 갖는 모든 대상은 동기화 대상이다. (스레드도 프로세스도 동기화 대상)

프로세스 동기화

동기화란?

여러 프로세스가 공유 자원에 동시에 접근해도 '공유 자원의 일관성'을 유지하는 것
프로세스들의 수행 시기를 맞추는 것
실행 순서를 위한 동기화와 상호 배제를 위한 동기화가 있다.

1) 실행 순서 제어: 프로세스를 올바른 순서대로 실행되도록 제어

2) 상호 배제 : 동시에 접근해서는 안 되는 자원(=공유 불가능 자원)에 하나의 프로세스만 접근하게 하기

공유 자원과 임계 구역

공유 자원 | shared resource

여러 프로세스 or 스레드가 공유하는 자원 (동시 접근 가능한 자원)
ex. 전역 변수, 파일, 입출력 장치, 보조 기억장치

경쟁 상태 | race condition

2개 이상의 프로세스가 공유 자원을 접근할 때 발생
두 개 이상의 프로세스가 공유 자원 서로 사용하려고 경쟁하는 상황
접근 타이밍이나 순서에 따라 결과값에 영향 줄 수 있는 상태

임계 구역 | critical section

공유 자원에 접근하는 (포함하는) 코드 부분
동시에 접근 시 실행 결과가 달라지는 코드 영역
임계 구역에 진입한 프로세스 이외에는 대기해야 한다.
임계 구역에 2개 이상의 프로세스(스레드)가 동시에 접근하면 문제가 발생한다.

→ 동시 접근 시, 자원의 일관성이 깨질 수 있다.

⬛ 임계 구역 문제 해결 조건

1) 상호 배제 | mutual exclution

한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 들어올 수 없음 (진입 상호 배타적)

2) 진행 | progress

임계 구역에 어떤 프로세스도 진입하지 않았다면 진입하고자 하는 프로세스는 들어갈 수 있어야 함

3) 유한 대기 | bounded waiting

상호 배제 때문에 기다리게 되는 프로세스가 무한정 대기하지 않아야 한다.

동기화 도구(기법) (3)

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다.
공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에,
한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.

⬛ 뮤텍스 락 | Mutex Lock

‘상호 배제’를 위한 동기화 도구 | ‘잠금’ 매커니즘
공유 자원이 하나 인 경우
Lock을 건 주체만 Lock을 해제할 수 있다.

→ available : 프로세스들이 공유하는 전역 변수

→ acquire () 함수 : 임계 구역 잠그는 역할

프로세스가 임계 구역 진입 전 호출
임계 구역 잠겨있다면 임계 구역 열릴 때까지(다른 프로세스 작업 끝나서 lock 이 false될 때까지) 임계 구역을 반복적으로 확인하다가, 끝나서 임계 구역이 열리면 임계 구역 잠그고 자기가 들어감

→ release() 함수 : 임계 구역 잠금 해제 역할

임계 구역에서의 작업 끝나고 호출
현재 잠긴 임계 구역을 열기

⬛ 세마포어 | Semaphore

정의 : 임계 영역에 여러 스레드 접근 가능하고, 카운터 두어

동시에 자원에 접근할 수 있도록 스레드 수를 제어하여 다중 프로세스에서 동기화 시키는 기술

‘상호 배제’를 위한 동기화 도구 | ‘신호’ 매커니즘
공유 자원 여러 개 있는 경우에도 적용 가능
좀 더 일반화된 방식의 동기화 도구
Lock을 걸지않은 주체도 Signal을 보내 Lock을 해제할 수 있다.

[종류]
(a) 이진 세마포어 (=바이너리 세마포어) : 0과 1 두 가지 값만 가지는 세마포어
(b) 카운팅 세마포어 : 여러 개의 값을 가질 수 있는 세마포어여러 자원에 대한 접근 제어

(1) busy-waiting 방식 | non blocking 구현

자원이 없다면 while 루프 돌면서 기다리는 방식

while 루프를 돌며 대기하기 때문에 busy-waiting이 발생

wait(S) {
  while (S <= 0);  // 대기 시점에 S<=0 이라면, while 루프를 돌며 대기를 함

  S--;  // 접근 가능한 자원 1개이상이면 자원을 획득 S-- 처리하고 임계구역 진입
}

signal(S) {
  S++;  // 임계 구역 내 작업 마친 뒤 점유하던 자원을 해제함.
}

→ 전역 변수 S = 임계 구역 진입 가능한 프로세스의 개수 = 사용 가능한 공유 자원의 개수

→ wait() 함수 : 대기 신호

→ signal() 함수 : 임계 구역 앞에서 기다리는 프로세스에게 진입 신호

기존에는 wait() 안에서 while()문으로 S 공유 자원 접근 가능한 지 반복적으로 확인하며 대기했는데, 이는 바쁜 대기임
→ 사실 반복적으로 확인하는 건 CPU 사이클 낭비다

(2) block-wakeup 방식 구현

자원이 없다면 blocked 상태에서 기다리는 방법입니다. (= sleep lock)

자원이 생기면 wakeup으로 block 상태인 프로세스를 깨우는 작업을 합니다.

→ 전역 변수 S = 임계 구역 진입 가능한 프로세스의 개수 = 사용 가능한 공유 자원의 개수

wait() {
	S--;
  if( S < 0 ) {
    block();
		//즉, 대기 중일 때 사용할 자원 없다면 '대기상태'로 만든다. 
		// 해당 프로세스의 PCB를 '대기 큐'에 삽입
  }
}

signal() { 
	S++; 
	if( S <= 0) {
      //신호 반환 시점에 S<=0 인 것은 대기 중인 프로세스가 있다는 뜻
      //이 때에만 대기 큐에서 프로세스를 꺼내어 깨운다
	   // 대기 큐의 프로세스를 ‘준비 상태’로 만듬
     // 해당 프로세스의 PCB를 대키 큐에서 꺼내고 '준비 큐'에 삽입
		wakeup(p) 
	}
}

block과 wakeup은 다음과 같이 동작합니다.

block() : 커널은 block을 호출한 프로세스를 suspend 시키고 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣습니다.
wakeup(P) : block된 프로세스 P를 wakeup 시키고 이 프로세스의 PCB를 ready queue로 옮깁니다.

추가 | 실행 순서 제어를 위한 세마포어 활용

변수 S를 처음부터 0으로 초기화
먼저 실행할 프로세스 뒤에 signal() 함수 호출
다음에 실행할 프로세스 앞에 wait() 함수 호출

→ 이렇게 하면 프로세스 간 실행 순서 제어 동기화 가능하다.

🎈 세마포어와 뮤텍스의 차이점

(1) 가장 큰 차이점은 뮤텍스가 동기화 대상이 자원의 하나라면, 세마포어는 하나 이상일 때 사용된다.

(2) 뮤텍스는 Locking 메커니즘으로 락을 걸은 쓰레드만이 임계 영역을 나갈때 락을 해제할 수 있지만, 세마포어는 Signaling 메커니즘으로 락을 걸지 않은 쓰레드도 signal을 사용해 락을 해제할 수 있다.

추가 | 스핀락(Spinlock)

스핀락은 다중 프로세스 또는 스레드가 공유 자원에 접근을 동기화하는 데 사용되는 동기화 메커니즘 중 하나이

자원 해제될 때까지 반복적으로 검사하여 Busy Waiting(바쁜 대기) 상태임

임계 구역(critical section)에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 락

동작 원리: 해당 자원이 다른 프로세스에 의해 점유되지 않았는지 확인하고, 점유되어 있지 않다면 스핀락을 획득하여 작업을 수행한다. 만약 다른 프로세스가 자원을 점유하고 있다면 스핀락은 계속해서 반복하여 자원의 해제를 기다린다.

적용 상황: 자원에 대한 접근이 짧은 시간 동안 보유될 것으로 예상될 때, 적은 오버헤드로 동작하여 효과적이다.

추가 | 어토믹(Atomic) 연산

→ 동기화 기법을 atomic 하게 해라

어토믹 연산은 하나의 연산이 다른 연산과 중간에 간섭받지 않도록 보장하는 연산

여러 쓰레드가 공용 자원을 동시에 접근하는 상황에 원자적 연산을 사용하여 다른 연산이 중간에 끼어들지 못하게 할 수 있다.

동작 원리: 멀티스레드 환경에서 공유된 변수에 대한 동시적인 접근 문제를 해결하기 위해 사용된다. 여러 단계의 명령어를 단일 연산으로 간주하고, 중간에 다른 스레드가 개입하지 않도록 보장한다.

적용 상황: 여러 스레드가 동시에 공유된 자원에 접근하는 상황에서 데이터 무결성을 유지하고 경쟁 조건을 방지하기 위해 필요하다.

⬛ 모니터 | Monitors

사용자(개발자)가 다루기 편한 자동으로 처리하는 동기화 도구이다.
(상호 배제, 실행 순서 제어)를 위한 동기화 모두 제공함
공유자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간 동기화를 시킨다.
모니터 안에는 하나의 프로세스만이 있을 수 있음
ex. Java의 경우 synchronized 키워드 모니터 기능 제공

모니터 특징

(1) 임계구역에 진입하고자 하는 프로세스는 모니터에 작업을 요청한다.

(2) 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에게 알려준다.

1) 상호 배제를 위한 동기화

인터페이스를 위한 큐 (왼쪽)
공유 자원에 접근하고자 하는 프로세스는 (인터페이스를 위한 큐)에 삽입
큐에 삽입된 순서대로 (한 번에 하나의 프로세스만 모니터에 진입해서) 공유 자원 이용

2) 실행 순서 제어를 위한 동기화

조건 변수 (condition variable) 활용 : wait(), signal() 호출할 수 있는 특별한 변수

프로세스, 스레드의 실행 순서 제어하기 위한 특별한 변수

모니터 안에는 하나의 프로세스만이 있을 수 있음

(1) 특정 프로세스가 아직 실행될 조건 되지 않았을 때는 wait를 통해 실행을 중단한다.

(2) 특정 프로세스가 실행될 조건 충족되었을 때는 signal을 통해 실행을 재개한다.

데드락

1) 상호 배제 : 포크는 한 사람이 사용해버리면 다른 사람이 사용할 수 없는 배타적 자원이다.

2) 점유와 대기 : 한 철학자가 포크를 들고, 다른 철학자의 포크를 얻길 기대하는 상황이다

3) 비선점: 옆 사람의 포크를 강제로 뺏을 수는 없다.

4) 원형 대기 : 서로가 서로의 포크를 원한다.

교착 상태 | 데드락 (Deadlock)

교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다.
두 개 이상의 프로세스들이 서로가 가진 자원을 기다리는 상태
정의 : 프로세스가 자원을 얻지 못해 다음 작업을 못하는 상태

📌 (현재 임계 영역에 a, b 공유자원 2개 있다)
A 스레드 , B 스레드 공유 자원에 동시에 접근할 때,
A는 (a + b) 를 하고 싶은 상태로, a를 먼저 선점했고
B는 (a * b) 를 하고 싶은 상태로 b 를 먼저 선점했다.
각자 원하는 작업을 완료하기 위해서는 서로가 가진 자원을 마져 가져야 하는데,
서로가 원하는 걸 서로가 가진 상태로 놔주지를 않으니까 작업 못한 상태로 꼬인 상태 ‘Deadlock’ 상태가 된다.

교착 상태 필요 조건 | 4가지

이 네 가지 중 하나라도 만족하지 않으면 교착 상태 X
네 가지 모두 만족해야 교착 상태 발생 O

1) 상호 배제

한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 '배타적 자원’

2) 점유 대기

자원 할당받은 상태에서 다른 자원 할당받기를 기다리는 상태
특정 프로세스가 점유하고 있는 자원을 다른 프로세스가 요청하는 상태

3) 비선점

어떤 프로세스도 다른 프로세스 자원을 강제로 뺏지 못하는 상태

4) 원형 대기

프로세스 A→ B, 프로세스 B→C, 프로세스 C→ A
프로세스들이 서로가 서로의 자원을 대기하는 상태

교창 상태 해결 방법

→ 예방 / 회피 / 검출 후 회복

(1) 예방

애초에 교착 상태 발생하지 않도록 예방하기
교착 상태 발생 조건 4가지 중 하나라도 사전에 막아버린다.

[상호 배제] 예방

시스템 내 상호 배타적인 **모든 자원을 공유하도록 만들어버리자. (**현실적X)

[점유 대기] 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 대기하지 못해버리게
특정 프로세스에 자원 모두 할당해버리거나, 아예 할당하지 않는 방식으로 배분

→ 다만, 자원의 활용성이 떨어지고, 이런 식의 동작은 결국 거의 모든 프로세스가 일괄 작업 방식으로 처리되어 시스템 효율이 떨어진다.

[비선점] 예방

모든 자원을 뺏을 수 있도록 만드는 방법이다.
그런데, 임계 구역을 보호하기 위해 lock을 사용하면 자원을 뺏을 수가 없다.
따라서 시스템 내 모든 자원을 뺏을 수 있도록 만들 수가 없다. 현실적 X

[원형 대기] 예방

자원에 번호 붙이고 반드시 오름차순으로만 자원 할당함
어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률 달라지고, 번호 붙이기도 어려움

(2) 회피

교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주

자원 할당량 조절하여 교착 상태 해결하는 방식
교착 상태 발생하지 않을 만큼만 자원 할당

→ 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 하는데, 시스템 전체 자원 수는 유동적이므로 쉬운 일이 아니다.

📌 은행원 알고리즘 : 교착 상태 되지 않도록 회피하는 자원 할당 방식
⇒ 모든 자원의 최대 할당량을 예상해서 미리 시뮬레이션으로 교착 상태 가능성을 조사한 뒤, 상태를 안전 상태와 불안전 상태로 나눠서 안전 상태를 유지할 수 있는 요구 만 수락하고, 불안전 상태를 초래할 수 있는 사용자의 요구는 만족될 수 있을 때까지 계속해서 거절하는 방법 (회피)이다.

(3) 교착 상태 검출

교착 상태 발생을 인정하고 사후에 조치하는 방식
프로세스가 자원 요구 시 일단 할당, 교착 상태 검출되면 회복

(1) 선점을 통한 회복

: 교착 상태 해결될 때까지 한 프로세스씩 자원 몰아주는 방식

(2) 프로세스 강제 종료를 통한 회복

: 교착 상태에 놓인 프로세스 모두 강제 종료

: 교착 상태 해결될 때까지 한 프로세스씩 강제 종료

기아 상태 | Starvation

특정 프로세스 우선순위가 낮아서 원하는 자원 계속해서 할당받지 못하는 상태

교착 상태 vs 기아 상태

(1) 교착 상태는 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태를 말하고,

기아 상태는 프로세스가 원하는 자원을 계속 할당받지 못하는 상태이다.

(2) 교착 상태는 여러 프로세스가 공유 자원 점유를 원할 때 발생하고,

기아 상태는 여러 프로세스가 자원을 점유하기 위해 경쟁할 때 특정 프로세스가 영원히 자원을 할당받지 못하는 것이다.