운영체제 파헤치기3 - 동기화와 교착 상태

레이스 컨디션(Race Condition)

프로세스 혹은 스레드가 공유하는 자원을 공유 자원(shared resource)이라고 합니다.

공유 자원은 메모리, 파일, 전역 변수, 입출력 장치 등이 될 수 있습니다.

공유 자원에 접근하는 코드 중 동시에 실행했을 때 문제가 발생할 수 있는 코드는 임계 구역(critical section)라고 합니다.

프로세스나 스레드가 동시에 임계 구역을 실행하면 데이터가 예상치 못한 방식으로 변경될 수 있습니다.

위 예시에서는 원래 결과값이 25만원이어야 하지만, 프로세스 P1과 P2가 동시에 접근하여 타이밍이 꼬여 20만원으로 잘못된 결과가 발생했습니다. 이러한 상황에서 프로세스나 스레드가 동시에 임계 구역의 코드를 실행할 때 발생하는 문제를 레이스 컨디션(race condition)이라고 합니다.

아래 코드 실행 결과 20000일 것이라고 예상하지만, 결과는 그렇지 않습니다.

public class Main {

    static int sharedResource = 0;
    public static void main(String[] args) {
       Thread thread1 = new Thread(new Increment());
       Thread thread2 = new Thread(new Increment());

       thread1.start();
       thread2.start();

       try {
          thread1.join();
          thread2.join();
       } catch (InterruptedException e) {
          e.printStackTrace();
       }

       System.out.println("Final value of sharedResource" + sharedResource);
    }

    static class Increment implements Runnable {
       public void run() {
          for (int i = 0; i < 10000; i++) {
             sharedResource++;
          }
       }
    }

}

위의 값이 20000이 아닌 이유는 한 스레드가 sharedResource 값을 읽고 증가시키기 전에 다른 스레드로 sharedResource를 읽어 증가가 한 번만 이루어지는 경우가 발생하기 때문입니다.

레이스 컨디션이 발생하면 자원의 일관성이 손상될 수 있으므로, 두 개 이상의 프로세스나 스레드가 임계 영역에 진입할 경우, 반드시 서로의 작업이 완료될 때까지 대기해야 합니다.

 

동기화(Synchronization)

레이스 컨디션을 방지하고 임계 구역을 안전하게 관리하기 위해서는 프로세스와 스레드의 동기화(synchronization)가 필요합니다. 동기화는 다음 두 가지 조건을 준수하며 실행하는 것을 의미합니다.

• 실행 순서 제어: 프로세스 및 스레드를 올바른 순서로 실행
• 상호 배제: 동시에 접근해서는 안 되는 자원에 대해서는 오직 하나의 프로세스 또는 스레드만 접근할 수 있도록 제한

 

동기화 기법

1. 뮤텍스 락 (Mutex Lock)

뮤텍스 락은 상호 배제를 보장하는 동기화 도구로, 접근해서는 안 되는 자원에 동시에 접근하는 것을 방지합니다.

mutual exclusion의 줄임말로, 상호 배제를 의미합니다.

뮤텍스 락의 원리는 임계 구역에 접근하고자 한다면 반드시 락(lock)을 획득(acquire)해야 하고, 임계 구역에서의 작업이 끝났다면 락을 해재(release)해야 합니다.

뮤텍스 락을 사용해서 임계 구역을 안전하게 관리하는 예시

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Main {

    static int sharedResource = 0;
    static Lock lock = new ReentrantLock();

    public static void main(String[] args) {
        Thread thread1 = new Thread(new Increment());
        Thread thread2 = new Thread(new Increment());

        thread1.start();
        thread2.start();

        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Final value of sharedData: " + sharedResource);
    }

    static class Increment implements Runnable {
        public void run() {
            for (int i = 0; i < 100000; i++) {
                lock.lock();
                try {
                    sharedResource++;
                } finally {
                    lock.unlock();
                }
            }
        }
    }

}

두 개의 스레드가 공유 자원(sharedResource)을 동시에 접근하는 상황에서 뮤텍스 락을 통해 레이스 컨디션을 방지하여 데이터의 일관성을 유지합니다.

 

2. 세마포 (Semaphore)

뮤텍스 락은 하나의 공유 자원을 고려하는 동기화 도구입니다. 하지만 한 번에 3개, 4개 이상의 프로세스나 스레드가 특정 자원을 사용할 경우에는 세마포를 활용할 수 있습니다.

세마포는 뮤텍스 락과 유사하지만, 보다 일반적인 동기화 방식입니다. 세마포를 사용하면 여러 개의 공유 자원이 있는 상황에서도 동기화가 가능하게 됩니다.

'세마포'라는 용어는 철도 신호기에서 유래되었습니다.

프로세스나 스레드가 임계 구역에 접근하려 할 때, 신호를 받아야 진입할 수 있으며, 신호가 없을 경우 대기해야 합니다.

세마포는 공유 자원의 개수를 나타내는 변수 s와 wait() 및 signal() 연산으로 구성됩니다.

• 변수 S: 사용 가능한 공유 자원의 개수
• wait() 함수: 임계 구역 진입 전 호출하는 함수
• signal() 함수: 임계 구역 진입 후 호출하는 함수

wait() 함수

wait() {
    S--;
    if (S < 0) {
        sleep();
    }
}

• (S-1)가 0 이상이면, 사용 가능한 공유 자원이 남아 있으므로 프로세스나 스레드가 임계 구역에 진입할 수 있음
• (S-1)가 0 미만이면, 자원이 부족하므로 해당 프로세스나 스레드는 대기 상태로 전환되어 임계 구역 진입 불가

signal() 함수

signal() {
    S++;
    if (S <= 0) {
        wakeup(p);
    }
}

• signal()은 임계 구역에서 작업을 마친 프로세슨 스레드가 호출
• S 값을 1 증가시키고, S<=0이면 대기 중인 프로세스를 깨워 준비 상태로 전환

세마포를 사용해서 임계 구역을 안전하게 관리하는 예시

import java.util.concurrent.Semaphore;

public class Main {

    static int sharedResource = 0;
    static Semaphore semaphore = new Semaphore(1);

    public static void main(String[] args) {
        Thread thread1 = new Thread(new Increment());
        Thread thread2 = new Thread(new Increment());

        thread1.start();
        thread2.start();

        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Final value of sharedResource: " + sharedResource);
    }

    static class Increment implements Runnable {
        public void run() {
            for (int i = 0; i < 100000; i++) {
                try {
                    semaphore.acquire();
                    sharedResource++;
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    semaphore.release();
                }
            }
        }
    }

}

두 개의 스레드가 공유 자원(sharedResource)을 동시에 접근하는 상황에서 세마포를 통해 레이스 컨디션을 방지하여 데이터의 일관성을 유지합니다.

세마포는 크게 이진 세마포(Binary Semaphore)와 카운팅 세마포(Counting Semaphore)로 나뉩니다.
- 카운팅 세마포: 공유 자원이 여러 개 있을 때 사용 가능하며, 자원의 개수를 S 값으로 표현
- 이진 세마포: S 값이 0 또는 1만 가지는 세마포로, 뮤텍스 락과 유사하게 동작위의 예시는 카운팅 세마포입니다.

위의 예시는 카운팅 세마포입니다.

 

3. 조건 변수와 모니터 (condition variable and monitor)

조건 변수(condition variable)는 실행 순서를 제어하는 동기화 도구로, 특정 조건이 충족될 때까지 프로세스나 스레드의 실행을 일시 중단할 수 있습니다. 이는 wait()과 signal() 함수를 통해 제어됩니다.

• 실행 조건이 충족되지 않았을 때 wait()을 호출하면 해당 프로세스 및 스레드는 대기 상태가 됨
• 실행 조건이 충족되면 signal()을 호출하여 대기 상태의 프로세스 및 스레드를 재개

모니터(monitor)는 공유 자원과 그 자원을 다루는 함수(인터페이스)로 구성된 동기화 도구로, 상호 배제와 실행 순서 제어를 모두 제공합니다.

• 상호 배제

프로세스 및 스레드는 공유 자원에 접근하기 위해 반드시 모니터를 통해야 하며, 모니터 내부에서는 하나의 프로세스 및 스레드만 실행될 수 있습니다. 이미 모니터 내에서 실행 중인 프로세스 및 스레드가 있을 경우 큐에서 대기해야 합니다.

• 실행 순서 제어

모니터 안에 특정 프로세스 B가 들어갔는데, 만약 B가 실행되기 전에 A를 먼저 실행해야 한다는 조건이 있으면, cv.wait()를 호출해 프로세스 B를 대기 상태로 접어들게 할 수 있습니다. 그러면 프로세스 A가 모니터 내로 진입하여 실행될 수 있고, 이후 cv.signal()을 호출해 대기 상태에 있던 프로세스 B를 모니터 안으로 재진입시킬 수 있습니다.

자바의 synchronized 키워드는 모니터를 활용하는 대표적인 예시입이다.

public synchronized void example(int value) {
    this.count += value;
}​​

위 메서드는 synchronized 키워드를 사용하여, 하나의 프로세스 및 스레드만 해당 메서드에 접근할 수 있도록 보장합니다. 다른 스레드가 접근하려면 현재 실행 중인 스레드가 종료될 때까지 대기해야 합니다.

 

스레드 안전(Thread Safety)

스레드 안전이란 멀티스레드 환경에서 여러 스레드가 동시에 변수, 함수, 객체에 접근하더라도 실행에 문제가 발생하지 않는 상태를 의미합니다. 스레드 안전하지 않은 코드에서는 레이스 컨디션이 발생할 수 있습니다.

예를 들어, 자바의 Vector는 내부적으로 동기화가 적용되어 있어 스레드 안전하지만, ArrayList는 동기화가 적용되지 않아 스레드 안전하지 않습니다.

 

교착상태(Deadlock)

프로세스가 실행되기 위해서는 자원이 필요합니다. 하지만 여러 개의 프로세스가 서로 자원을 점유한 채 추가 자원을 기다리기만 하면, 어떤 프로세스도 실행을 진행할 수 없는 상황, 즉 교착 상태(Deadlock) 가 발생할 수 있습니다.

 

교착 상태 발생 조건

다음 네 가지 조건이 모두 충족될 경우, 교착 상태가 발생할 가능성이 생깁니다.

• 상호 배제(Mutual Exclusion): 한 프로세스가 사용하는 자원은 다른 프로세스가 사용할 수 없다.
• 점유와 대기(Hold and Wait): 한 프로세스가 자원을 점유한 상태에서 추가 자원을 요청하며 대기한다.
• 비선점(No Preemption): 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없다. 해당 자원을 사용 중인 프로세스가 스스로 반납해야만 사용할 수 있다.
• 원형 대기(Circular Wait): 프로세스와 프로세스가 요청하는 자원이 원형 형태를 이루는 경우이다.

 

교착 상태의 해결 방법

• 교착 상태 예방(Prevention)

교착 상태를 유발하는 4가지 필요 조건 중 하나 이상을 충족하지 않도록 하는 방법입니다.

가령 한 프로세스에 필요한 자원들을 몰아 주고, 그 다음 다른 프로세스에 필요한 자원을 몰아 주면 점유와 대기 조건을 만족하지 않습니다. 또한 할당 가능한 모든 자원에 번호를 매기고 오름차순으로 할당하면, 원형 대기 조건을 만족하지 않습니다.

1번 포크 → 2번 포크 → 3번 포크 → 4번 포크 → 5번 포크에서 다시 1번 포크를 잡지 못한다.

 

• 교착 상태 회피(Avoidance)

교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조심하면서 자원을 할당하는 방법입니다. 교착 상태 회피는 기본적으로 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주합니다.

 

• 교착 상태 검출 후 회복(Detection & Recovery)

교착 상태 검출 후 회복은 교착 상태의 발생을 인정하고 이를 처리하는 사후 조치입니다. 이 경우, 운영체제는 프로세스가 자원을 요구할 때마다 자원을 할당하고 주기적으로 교착 상태의 발생 여부를 검사합니다. 그러다 교착 상태가 검출되면, 프로세스를 자원 선점을 통해 회복시키거나, 교착 상태에 놓인 프로세스를 강제 종료함으로써 회복시킬 수 있습니다.

자원 선점을 통한 회복은 교착 상태가 해결될 때까지 다른 프로세스로부터 강제로 자원을 빼앗아 한 프로세스에 몰아서 할당하는 것을 의미합니다.

 

참고

강민철. 『 이것이 취업을 위한 컴퓨터 과학이다 』