[운영체제] 프로세스 동기화와 교착상태

동기화(Synchronization)란 공유자원의 일관성을 유지하는 것이다.

그렇다면 프로세스 동기화란 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것이라고 볼 수 있다.

 

프로세스 동기화의 시작은 경쟁 상태(Race Condition)와 임계 구역(Critical Section)에 대한 이해부터 시작한다.

 

경쟁 상태 (Race Condition)

경쟁 상태란 여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황을 말한다. 쉽게 말해서, 다수의 프로세스 혹은 스레드가 동기화 없이 공유 자원에 접근하려는 현상이다.

이런 현상에서 데이터의 불일치 문제를 발생시킬 수 있다. 따라서 일관성을 유지하기 위해 동기화가 필요하다.

 

경쟁 상태의 예시

count = 3
(Thread 1) count++	(Thread 2) count--
count = 3 ??

 

위의 표처럼 각 스레드가 순서에 상관없이 count++, count--를 실행했다고 가정 했을때, count의 결과값은 항상 3일까?

 

count++과 count--는 각각 세가지 assembly code로 이루어져 있기 때문에 그렇지 않다.

// count++
register1 = count
register1 = register1 + 1
count = register1


// count--
register2 = count
register2 = register2 - 1
count = register2

 

count++와 count-- 가 차례대로 실행되는 과정을 풀어 써보면

T0: register1 = count			{register1 = 3}
T1: register1 = register1 + 1 		{register1 = 4}
T2: count = register1			{count = 4}
T3: register2 = count			{register2 = 4}
T4: register2 = register2 - 1		{register2 = 3}
T5: count = register2			{count = 3}

T0~T5가 순서대로 실행이 됐을 경우 count 값은 3이 될거다. 만약 T1 실행 중에 context switch가 일어나서 다른 쓰레드가 실행된다면? 

context switch란?
여러개의 프로세스가 실행되고 있을 때 기존에 실행되던 프로세스를 중단하고 다른 프로세스를 실행하는 것

T0: register1 = count			{register1 = 3}
T1: register1 = register1 + 1 		{register1 = 4}
// context switch P1 -> P2
T2: register2 = count			{register2 = 3}
T3: register2 = register2 - 1		{register2 = 2}
// context switch P2 -> P1
T4: count = register1			{count = 4}
// context switch P1 -> P2
T5: count = register2			{count = 2}

위 코드처럼 세번의 context switch가 발생한다면 최종값은 2가 될 것이다.

이렇게 실행 순서에 따라 값이 달라지는 현상을 경쟁 상태라고 한다. 경쟁 상태의 가장 근본적인 원인은 메모리 공유다.

 

이런 경쟁상태를 해결하는 해결 방안이 바로 동기화다. 

 

 

임계구역 (Critical Section)

임계구역을 실생활에서 예시를 들자면 탈의실로 비유할 수 있다.

탈의실에는 오직 한 명만 들어갈 수 있다는 규칙이 있다. (백화점의 탈의실로 생각해주세요)

 

이제 단어를 조금 바꿔주면, 동기화에서 탈의실을 임계구역이라고 하고 오직 한 명만 들어갈 수 있는 것을 상호배제라고 한다. 즉, 임계구역은 코드 상에서 경쟁상태가 발생할 수 있는 특정 부분을 말한다. 위에서 예시로 들었던 count++, count--의 코드 한줄 한줄이 임계구역이라고 볼 수 있다.

 

임계구역으로 인해 발생하는 문제들을 임계구역문제라고 하고, 이를 해결하기 위해서는 다음 조건들을 만족해야한다.

 

1. Mutual Exclusion (상호 배제)

- 이미 한 프로세스가 임계구역에서 작업 중이면 다른 모든 프로세스는 임계구역에 진입하면 안된다.

 

2. Progress (진행)

- 임계구역에서 작업 중인 프로세스가 없다면, 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야한다.

 

3. Bounded Waiting (한정 대기)

- 프로세스가 임계구역에 들어가기 위해 요청한 후 부터 그 요청이 허용될 때까지 다른 프로세스들이 임계구역에 들어가는 횟수에 한계가 있어야한다. 쉽게 말해서, 임계구역에 진입하려는 프로세스가 무한정 기다려서는 안된다.

 

 

임계 구역을 보호하고 경쟁 상태를 방지하기 위한 방법으로 Mutex, Semaphore, Monitor가 있다. 이들은 모두 공유된 자원의 데이터를 여러 스레드/프로세스가 접근하는 것을 막는 공통적인 역할을 한다.

Mutex

공유된 자원의 데이터 혹은 임계영역등에 하나의 프로세스 혹은 스레드가 접근하는 것을 막아줌 (동기화 대상이 하나)

스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행(상호배제) 되도록 하는 기술

 

한 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법이고 Key에 해당하는 객체를 소유한 스레드/프로세스만이 공유자원에 접근할 수 있다. Mutual Exclusion Lock의 축약어로 Lock을 걸어주면서 상호배제를 달성한다. 즉, 뮤텍스 락을 설정한 프로세스만이 락을 해제할 수 있다.

 

ex) 1칸 뿐인 화장실의 열쇠

- 사람은 프로세스 혹은 스레드, 화장실은 공유자원, 화장실 키는 공유자원에 접근하기 위해 필요한 어떤 객체

 

Semaphore

공유된 자원의 데이터 혹은 임계영역 등에 여러 프로세스 혹은 스레드가 접근하는 것을 막아줌 (동기화 대상이 하나 이상)

 

사용하고 있는 프로세스/스레드의 수를 공통으로 관리하는 하나의 값을 이용해 상호배제를 달성한다.

자원을 사용하지 않는 상태가 될 때, 대기하던 프로세스가 즉시 자원을 사용하고 이미 다른 프로세스에 의해 사용중이라는 사실을 알게 되면, 재시도 전에 일정시간 대기(유한대기)해야 한다.

 

ex) 여러개 칸의 화장실과 빈 칸의 개수를 보여주는 전광판

- 전광판의 숫자가 0보다 클때 화장실에 입장 할 수 있고 입장할때 빈 칸의 개수를 하나 빼고, 나올 때 빈칸의 개수를 하나 더해준다.

- 모든 칸에 사람이 있을 경우 전광판의 숫자는 0이고, 이때 들어가고자 하는 사람이 있다면 빈 칸의 개수가 1혹은 양수로 바뀔 때까지 기다려야한다.

 

위의 예시처럼 세마포어는 공통으로 관리하는(전광판) 하나의 값을 이용해 상호배제를 달성한다. 아까와 똑같이 화장실이 공유자원이며 사람들이 프로세스/스레드이다. 그리고 화장실 빈 칸의 개수는 현재 공유자원에 접근할 수 있는 스레드, 프로세스의 개수를 나타낸다.

 

Monitor

모니터는 프로세스 또는 스레드를 동기화하는 방법 중 하나로서 에러를 발생시킬 수 있는 세마포어와 뮤텍스보다 비교적 많이 쓰이고 특히 자바에서 많이 쓰인다.

 

세마포어와 뮤텍스는 언제 어떤 상황에서 에러가 발생할까?

 

1. wait(mutex)와 signal(mutex) 연산의 순서가 뒤바뀌었을때

- 여러 프로세스가 임계구역에 동시에 진입했을때

 

2. signal(mutex)를 써야 할 곳에 wait(mutex)를 썼을 때

- 두번째 wait(mutex)연산에서 교착 상태가 발생한다.

 

3. wait(mutex)나 signal(mutex)가 누락되었을때 프로세스는 영원히 block된다.

 

이처럼 세마포어나 뮤텍스를 잘못 사용하면 오류가 쉽게 발생한다. 이를 해결하기 위해 간단한 동기화 도구들을 통합하여 고급언어 구조물 중 하나인 모니터를 사용한다.

 

 

모니터의 구성요소

 

- mutex

  임계구역에서 상호배제를 보장하는 장치, 임계구역에 진입하려면 mutex lock을 취득해야함

 

- condition variable

  waiting queue를 가짐. 스레드들이 대기 상태로 머무는 곳

condition variable에서 주요 동작

wait
thread가 자기 자신을 condition variable의 waiting queue에 넣고 대기 상태로 전환

signal
waiting queue에서 대기중인 스레드 중 하나를 깨움

broadcast
waiting queue에서 대기중인 스레드 전부를 깨움

 

모니터 사용

// cv : condition variable
// m : mutex

acquire(m);  // 모니터의 락 취득
while(!p) {
	wait(m,cv);  // 조건 충족 안되면 waiting
}
...
signal(cv2); or broadcast(cv2);
release(m);  // 모니터의 락 반환

• 락 반환이 되지 않은 상태에서 다른 스레드가 접근한다면 스레드 자기 자신을 어떤 큐에 넣고 기다리는데 그 큐를 entry queue라고 부른다.
• 조건이 충족되지 않을때 대기하는 큐를 waiting queue라고 부른다.

 

Mutex Semaphore 차이점

가장 큰 차이점은 동기화 대상의 개수이다. 위에서 예시든 화장실의 개수

• 뮤텍스는 동기화 대상이 오직 1개일 때 사용하며, 세마포어는 동기화 대상이 1개 이상일 때 사용
• 뮤텍스는 자원을 소유할 수 있고, 세마포어는 자원 소유가 불가능
• 뮤텍스는 상태가 0, 1뿐이므로 Lock을 가질 수 있고, 소유하고 있는 스레드만이 이 뮤텍스를 해제할 수 있습니다. 세마포어는 세마포어를 소유하지 않는 스레드가 세마포어를 해제할 수 있다.

 

뮤텍스와 세마포어는 모두 완벽한 기법이 아니므로 데이터 무결성을 보장할 수는 없으며 모든 교착상태(DeadLock)를 해결하지 못한다.

 

 

교착상태 (DeadLock)

교착상태란 두개 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며, 서로의 작업을 끝나기만을 기다리며 둘 다 영원히 끝나지 않는 상황을 뜻한다.

 

교착상태 발생조건

1. 상호 배제

- 한번에 프로세스 하나만 해당 자원을 사용할 수 있다.

 

2. 점유 대기

- 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

 

3. 비선점

- 프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때까지 기다린다.

(이미 할당된 자원을 강제적으로 빼앗을 수 없음)

 

4. 순환 대기

- 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루면서 대기하는 조건

 

 

교착상태 해결방법

1. 예방

교착상태가 애초에 일어나지 않도록 방지하는 방법으로 교착상태의 발생조건 4가지 중 하나를 부정

하지만 이렇게 발생조건을 방지해서 데드락을 예방하는 방법은 시스템 처리량이나 자원 사용의 효율성을 떨어트리는 단점이 있다.

 

2. 회피

교착상태 발생할 가능성이 있는 자원할당을 하지 않고 안전한 상태에서만 자원 요청을 허용하는 방법

그러기 위해선 아래와 같은 가정이 필요하다.

• 프로세스 수 고정
• 자원의 종류와 수 고정
• 프로세스가 요구하는 최대 자원의 수를 알아야함
• 프로세스는 자원 사용 후 반드시 반납

교착상태 회피하기 위한 알고리즘은 크게 두가지가 있다.

 

1. 은행원 알고리즘

다익스트라가 제안한 기법, 은행에서 모든 고객의 요구를 충족할 수 있도록 현금을 대출해주는 것에서 유래.

모든 자원의 최대 할당량을 가지고 시뮬레이션을 하여 safe state에 들 수 있는지 여부를 검사하여 교착상태의 가능성을 미리 조사하는 알고리즘

Safe state
safe sequence(교착상태를 발생시키지 않고 자원을 할당하는 순서)가 존재하며 모든 프로세스가 정상적으로 종료될 수 있는 상태를 의미

Unsafe state
교착상태가 발생할 가능성이 있는 상태

 

2. 자원 할당 그래프 알고리즘

자원 할당 그래프에 예약 간선을 추가하여 예약 간선으로 설정한 자원에 대해서만 자원 할당을 요청할 수 있고 사이클이 형성되지 않을 때만 자원을 할당받는 방법

자원 할당 그래프: 프로세스가 어떤 자원을 사용중이고, 어떤 자원을 기다리는지 방향성 있는 그래프로 표시한 것
예약 간선: 향후 요청할 수 있는 자원을 가리키는 점선으로 표시된 간선

상호배제: R1, R2, R3, R4

점유 대기: P1, P2, P3

비선점: O

순환 대기: O

=> 교착상태 O

 

3. 탐지

데드락이 발생했는지 여부를 탐색하고 회복 기법 알고리즘에 활용하는 것.

탐지 기법은 지속적으로 교착상태를 확인해야하기 때문에 성능 저하가 발생하게 된다.

 

4. 회복

교착상태가 발생했을 때 해결하는 기법

 

- 사용자 처리

교착상태에 있는 프로세스 중 하나를 사용자가 강제 종료

 

- 시스템 처리

  - 프로세스 중지

    1. 교착상태에 속해있는 모든 프로세스를 중지

    2. 해결될 때까지 프로세스 하나씩 중지

  - 자원 선점

    프로세스들로부터 자원을 빼앗아 교착상태가 해결될 때까지 다른 프로세스들에게 자원을 할당

 

 

---

참고

[OS] 교착상태(Deadlock, 데드락)의 정의, 발생 조건, 해결 방법

 

[ 운영체제 ] 경쟁상태(Race Condition)와 동기화(Synchronization)의 필요성, 임계 구역(Critical Section)

 

[운영체제] Mutex 뮤텍스와 Semaphore 세마포어의 차이

 

[운영체제(OS)] 6. 프로세스 동기화(Process Synchronization)