[운영체제] 3. 동기화와 교착 상태

본 글은 '이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접' 책을 읽고 정리한 글입니다. 

 

 

✔️ 임계 영역 

프로세스 혹은 스레드가 공유하는 자원을 공유 자원이라고 한다. 만약 두 프로세스 A와 B가 각각 공유 메모리를 쓰고 읽는 작업을 한다고 할 때, A와 B가 실행되는 순서에 따라 다른 결과를 초래할 수 있다. B가 먼저 실행이 된다면 아직 쓰이지 않은 메모리를 읽으려 하기 때문에 문제가 발생할 수 있다. 

1. 프로세스 예시

 

이와 같이 접근 순서에 따라 다른 결과를 나타낼 수 있는 코드 구역을 임계 영역(critical section)이라고 한다. 

 

 

이번에는 동시에 파일을 수정하는 스레드를 생각해보자. 초기 파일에 저장된 값이 'first'라 가정하고 스레드 A는 'thread A'를 파일에 추가하는 작업, 스레드 B는 'thread B'를 파일에 추가하는 작업이다. 

다음과 같이 스레드 A와 B가 동시에 수행될 경우, 스레드 A의 작업 내역은 반영되지 않을 수 있다. 

2. 스레드 예시

 

 

이처럼 프로세스나 스레드를 다룰 때 임계 영역을 동시에 실행하지 않도록 유의해야한다. 

 

 

 

✔️ 경쟁 상태 (race condition)

앞에서 보여준 예시처럼 프로세스 혹은 스레드가 임계 영역의 코드를 실행하여 문제가 발생하는 상황을 경쟁 상태(race condition)라고 한다. 이제 이러한 상황을 레이스 컨디션이라고 부르겠다. 

 

레이스 컨디션이 발생하는 예시를 Swift로 한 번 구현을 해보았다. 

다음은 공유 변수를 100번 동안 1씩 증가시키는 스레드와 공유 변수를 100번 동안 1씩 감소시키는 스레드를 실행하는 코드이다. 

import Foundation

var shared_data: Int = 0

var isThread1Done: Bool = false
var isThread2Done: Bool = false

func increment() {
    for _ in 0..<100 {
        shared_data += 1
    }
    isThread1Done = true
}

func decrement() {
    for _ in 0..<100 {
        shared_data -= 1
    }
    isThread2Done = true
}

// Thread 1
DispatchQueue.global().async {
    increment()
    
}

// Thread 2
DispatchQueue.global().async {
    decrement()
}

// 두 스레드가 끝날 때까지 기다림
while !(isThread1Done && isThread2Done) {
    Thread.sleep(forTimeInterval: 0.01)
}

print("final value: \(shared_data)\n")

 

결과적으로 공유 변수를 100 증가시키고, 100 감소시켰으므로 결과는 0이 될 것을 기대하지만, 실제로는 일정하지 않은 결과가 도출됨을 확인할 수 있다. 

결과

 

이처럼 레이스 컨디션이 발생하면 자원의 일관성이 손상될 수 있기 때문에, 두 개 이상의 프로세스 혹은 스레드가 임계 영역에 접근하고자 한다면 둘 중 하나는 작업이 끝날 때까지 대기해야 한다. 

 

 

✔️ 동기화

레이스 컨디션을 방지하면서 임계 구역을 관리하기 위해서는 프로세스와 스레드가 동기화되어야 한다. 

 

프로세스 혹은 스레드의 동기화는 다음의 두 가지 조건을 준수하며 실행한다. 

• 실행 순서 제어 : 프로세스 및 스레드를 올바른 순서로 실행
• 상호 배제 : 동시에 접근해서는 안되는 자원에 하나만 접근

 

위에서 보여줬던 예시 중 1번 그림의 상황은 올바른 순서로 실행되지 않아 발생하는 문제였으므로 '실행 순서 제어를 위한 동기화'가 필요하고, 2번 그림은 동시에 공유 자원에 접근해 발생하는 문제이므로 '상호 배제를 위한 동기화'가 필요하다. 

 

동기화 기법 

이제 실행 순서 제어와 상호 배제를 보장하기 위한 동기화 기법들을 알아보자.

 

1. 뮤텍스(Mutex) 

뮤텍스는 락(lock)을 가진 프로세스만 이 공유 자원에 접근할 수 있게 하는 방법으로, 상호 배제를 보장하는 동기화 도구이다. 

 

뮤텍스 락의 원리는 다음과 같다. 

1. 임계 구역에 접근하기 위해서는 락이 있어야 한다. 

2. 임계 구역에서의 작업이 끝났다면 락을 해제해야 한다. 

 

예를 들어, 하나의 화장실을 여러 사람이 사용하고자 하는 상황을 생각해보자. 화장실에 가기 위해서는 열쇠가 필요하고, 첫 번째로 온 사람은 열쇠를 들고 화장실에 들어간다. 그 사이에 다른 사람이 와도 열쇠가 없으므로 화장실에 갈 수 없다. 다 이용한 사람이 화장실에서 나오면 열쇠를 제자리에 갖다두고, 다음 사람이 그 열쇠를 가지고 화장실에 간다. 

이때 화장실 열쇠, 즉 락(lock)이 공유 자원이다. 

 

뮤텍스 락에서 대기 중인 프로세스가 락이 풀렸는지 확인하기 위해서 반복문을 돌면서 확인한다. 이는 바쁜 대기(busy waiting)의 한 종류인 스핀락(spinlock)이라고 한다.  

 

2. 세마포어 (Semaphore)

뮤텍스는 하나의 공유 자원을 고려하였다면, 세마포어는 여러 개의 공유 자원을 이용하는 방식이다. 즉, 공유 자원에 접근할 수 있는 프로세스의 수를 정해 접근을 제어한다. 

 

세마포어에서는 이전에 사용 중이던 공유 자원이 해제되면 대기 중인 프로세스에 신호를 보내는 시그널링 메커니즘이 사용된다. 

 

3. 조건 변수와 모니터

다음 동기화 기법은 모니터인데, 그 전에 조건 변수란 실행 순서 제어를 위한 동기화 도구로, 특정 조건 하에 프로세스를 실행/일시 중단함으로써 프로세스나 스레드의 실행 순서를 제어한다. 

 

모니터는 공유 자원과 공유 자원을 다루는 함수로 구성된 동기화 도구로, 상호 배제와 실행 순서 제어를 위한 동기화 둘 다 가능하다. 프로세스 및 스레드가 공유 자원에 접근하기 위해서는 공유 자원 연산을 통해 모니터로 진입한다. 모니터 안에 진입하여 실행되는 프로세스는 항상 하나여야 한다. 

 

 

스레드 안전 

스레드 안전이란 멀티스레드 환경에서 어떤 변수나 함수, 객체에 동시 접근이 이루어져도 문제가 없는 상태를 말한다. 레이스 컨디션이 발생했다면 이는 스레드 안전하지 않는 상황이다. 

 

Swift에서 스레드 안전하게 하기 위해 `DispatchSemaphore`, `NSLock` 등을 사용할 수 있다. 위에서 레이스 컨디션이 발생하는 코드에서 `DispatchSemaphore`를 사용하여  스레드 안전하게 바꿔본다면 다음과 같다. 

// 접근 가능한 스레드를 1개로 제한 
let semaphore = DispatchSemaphore(value: 1)

func increment() {
    for _ in 0..<100 {
        semaphore.wait()
        shared_data += 1
        semaphore.signal()
    }
    isThread1Done = true
}
    
func decrement() {
    for _ in 0..<100 {
        semaphore.wait()
        shared_data -= 1
        semaphore.signal()
    }
    isThread2Done = true
}

 

결과

 

✔️ 교착 상태 (deadlock)

프로세스 1과 2가 자원 A와 B를 모두 가져야만 작업을 진행할 수 있다고 할 때, 프로세스 1과 2가 각각 자원 A와 B를 갖고 있다고 해보자. 이런 경우에 프로세스 1은 자원 B를 기다리고 프로세스 2는 자원 A를 기다리며, 두 프로세스는 아무런 작업도 진행하지 않고 멈추게 된다. 

 

이처럼 일어나지 않을 사건을 기다리며 프로세스의 진행이 멈춰 버리는 현상을 교착 상태(deadlock)라고 한다. 

 

교착 상태의 발생 조건 

교착 상태가 발생하는 상황에는 4가지 필요 조건이 있으며, 4가지가 모두 만족해야 발생한다. 

 

1) 상호 배제 

이는 동기화 기법에서 나온 상호 배제와 같은 의미이다. 하나의 자원에 하나의 프로세스만 접근이 가능하다면 교착상태가 발생할 수 있다. 

 

2) 점유와 대기

한 프로세스가 어떤 자원을 할당받은 상태(점유)에서 다른 자원을 할당받기를 기다리는 경우(대기)에 교착 상태가 발생할 수 있다. 

 

3) 비선점 

비선점은 어떤 프로세스가 가진 자원을 다른 프로세스가 강제로 빼앗지 못하는 것을 의미한다. 

 

4) 원형 대기 

원형 대기는 프로세스와 프로세스가 기다리는 자원이 원의 형태를 이루는 경우를 말한다. 

3. 원형 대기 예시

 

교착 상태의 해결 방법

교착 상태를 해결하는 방법은 예방, 위험이 있을 때 회피, 검출 후 회복의 방법이 있다. 

 

1. 교착 상태 예방 

교착 상태는 위에서 언급한 4가지 조건을 충족해야 발생할 수 있다고 했다. 즉, 4가지 중 하나라도 충족하지 않으면 교착 상태가 발생하지 않는다. 

한 프로세스에 필요한 자원을 몰아주고, 그 다음 다른 프로세스에 필요한 자원을 몰아준다면 점유와 대기 조건을 만족하지 않는다. 

또한, 자원에 번호를 붙인 후 각 프로세스가 본인이 점유한 자원보다 큰 번호의 자원만 요구할 수 있다면 원형 대기 조건을 만족하지 않는다. 

4. 원형 대기 예방

나는 이 부분이 이해가 잘 되지 않았었는데, 조금 풀어서 생각해보자.

원형 대기의 조건은 각 프로세스가 필요로 하는 자원이 원을 이루고 있는 형태였다. 위 그림에서는 '대기'라고 써진 부분이 이제 해당 자원을 기다리고 있다는 의미이다. 이 경우에 `프로세스C`가 `자원X`를대기하지 않는다면 `프로세스B`가 요구하는 `자원Z`를 `프로세스C`가 점유하지 않고 `프로세스B`에게 양보할 수 있게 되는 것이다. 이 방식으로 교착 상태를 예방 할 수 있다. 

 

 

2.  교착 상태 회피 

회피는 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방법이다. 교착 상태 회피는 기본적으로 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다. 만약 자원이 무한하다면 교착 상태가 발생하지 않을 텐데, 한정된 자원 내에서 동시에 너무 많은 프로세스가 자원을 요구하기 때문에 교착 상태가 발생한다는 것이다. 따라서 자원을 조금만 할당하는 방식이 교착 상태 회피이다. 

 

3. 교착 상태 검출 후 회복 

검출 후 회복은 교착 상태 발생 후 이를 처리하는 사후 조치이다. 이 경우, 운영체제는 프로세스가 자원을 요구할 때마다 자원을 할당하고 주기적으로 교착 상태의 발생 여부를 검사한다. 

그러다 교착 상태가 검출되면 프로세스를 자원 선점을 통해 회복시키거나, 교착 상태에 놓인 프로세스를 강제 종료함으로써 회복시킨다.