동기화와 교착 상태

자원 공유

위 그림처럼 프로세스 혹은 스레드가 공유하는 자원을 공유 자원(shared resource)이라고 한다. 공유 자원은 메모리나 파일이 될 수도 있고, 전역 변수나 입출력장치가 될 수도 있다.

다수의 프로세스 혹은 스레드가 공유 자원에 접근하는 코드 중 동시에 실행했을 때 문제가 발생할 수 있는 코드를 임계 구역(critical section)이라고 한다.

 

예를 들어, 프로세스 A가 실행된 뒤 프로세스 B가 실행되는 것은 문제가 되지 않지만, 프로세스 B가 실행된 뒤 프로세스 A가 실행되는 것은 문제가 될 수 있다. 즉, 프로세스 A의 '공유 메모리 공간에 데이터를 쓰는 코드'와 프로세스 B의 '공유 메모리 공간을 읽는 코드'는 임계 구역이 된다.

 

동시에 파일을 수정하는 스레드도 임계 구역이 발생할 수 있다. 각 스레드들이 파일을 수정하는 과정은 (1) 파일을 읽어 들이고 (2) 원하는 내용을 작성한 뒤, (3) 작성한 내용을 저장하는 과정과 같다. 스레드 A와 B가 동시에 수행될 경우, 스레드 A의 작업 내역은 반영되지 않을 수 있다.

스레드 A	(1) 파일 읽기	(2) 파일 쓰기(thread A)	(3) 파일 저장
스레드 B		(1) 파일 읽기	(2) 파일 쓰기(thread B)	(3) 파일 저장
파일 내용	first	first	first	first thread A	first thread B

 

혹은 실행 도중에 문맥 교환이 발생하는 경우에도 스레드 A의 작업은 반영되지 않을 수 있다. 따라서 각 스레드가 파일을 수정하는 코드는 임계 구역이 된다.

작업 순서	스레드 A 파일 읽기	스레드 A 파일 쓰기	스레드 B 파일 읽기	스레드 B 파일 쓰기	스레드 A 파일 저장	스레드 B 파일 저장
파일 내용	first	first	first	first	first	first thread A	first thread B

 

위 예시들처럼 프로세스 혹은 스레드가 동시에 임계 구역의 코드를 실행하여 문제가 발생하는 상황을 레이스 컨디션이라고 한다.

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

 

레이스 컨디션을 방지하면서 임계 구역을 관리하기 위해서는 프로세스와 스레드가 동기화되어야 한다. 프로세스 혹은 스레드의 동기화는 다음의 2가지 조건을 준수하며 실행하는 것을 의미한다.

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

동기화에는 실행 순서 제어를 위한 동기화가 있고, 상호 배제를 위한 동기화가 있다.

---

동기화 기법

뮤텍스 락(mutex lock)

동시에 접근해서는 안되는 자원에 동시 접근이 불가능하도록 상호 배제를 보장하는 동기화 도구이다. 뮤텍스 락은 '상호 배제를 위한 락(lock)'이라는 뜻이다.

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

 

전형적인 뮤텍스 락은 프로세스 및 스레드가 공유하는 변수(lock)와 2개의 함수(acquire, release)로 구현된다.

• 공유하는 변수: 뮤텍스 락의 '락' 역할을 수행
• acquire(): 락을 획득하기 위한 함수
• release(): 획득한 락을 해제하기 위한 함수

임계 구역에 진입하려면 프로세스 및 스레드가 공유하는 락을 획득하는 과정인 lock.acquire()을 호출해야 한다. 만약, 이후 다른 프로세스 및 스레드가 lock.acquire()을 호출하더라도 락을 획득할 수 없고, 락이 해제될 때까지 기다려야 한다. 임계 구역의 작업이 끝나면 락을 해제하기 위해 lock.release()를 호출하며, 만약 임계 구역 앞에서 대기하는 프로세스 혹은 스레드가 있었다면 그때 락을 획득하고(lock.acquire() 호출에 성공) 임계 구역에 진입하게 된다.

lock.acquire()
// 임계 구역
lock.release()

 

 

 

① 프로세스 P1 acquire() 호출 → 임계 구역 진입

② 프로세스 P2 acquire() 호출, lock을 획득하지 못해 임계 구역 접근 불가

③ 프로세스 P1 임계 구역 작업 종료, release() 호출

④ 프로세스 P2 임계 구역 진입

 

 

 

 

 

파이썬, C/C++ 등의 프로그래밍 언어에서는 뮤텍스 락을 지원하고 있으므로 사용자가 직접 acquire(), release() 함수를 구현할 필요 없다. 뮤텍스 락이라는 표현을 사용하지는 않지만 자바도 락을 지원한다.

// os.Mutex.java

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

public class Mutex {
    static int sharedData = 0; // 공유 데이터
    static Lock lock = new ReentrantLock(); // 락 선언
    
    public static void main(String[] args){
        Thread thread1 = new Thread(new Increment());
        Thread thread2 = new Thread(new Decrement());
        
        thread1.start(); // 첫 번째 스레드 시작
        thread2.start(); // 두 번째 스레드 시작
        
        try {
            thread1.join(); // 첫 번째 스레드 종료 대기
            thread2.join(); // 두 번쨰 스레드 종료 대기
        } catch (InterruptedException e){
            e.printStackTrace();
        }
        
        // 최종 공유 데이터 값 출력
        System.out.println("Final value of sharedData: " + sharedData);
    }
    
    static class Increment implements Runnable {
        public void run() {
            for(int i=0; i<1000000;i++) {
                lock.lock(); // 락 획득
                try {
                    sharedData++; // 공유 데이터 증가
                }finally {
                    lock.unlock(); // 락 해제
                }
            }
        }
    }

    static class Decrement implements Runnable {
        public void run() {
            for(int i=0; i<1000000;i++) {
                lock.lock(); // 락 획득
                try {
                    sharedData--; // 공유 데이터 감소
                }finally {
                    lock.unlock(); // 락 해제
                }
            }
        }
    }
}

---

세마포(semaphore)

뮤텍스 락은 하나의 공유 자원을 고려하는 동기화 도구이고, 세마포는 뮤텍스 락과 비슷하지만, 공유 자원이 여러 개 있는 상황에서도 동기화가 가능한 도구이다.

 

세마포도 뮤텍스락과 비슷하게 하나의 변수와 2개의 함수로 구성된다.

• 변수 S: 사용 가능한 공유 자원의 개수를 나타내는 변수 → 임계 구역에 진입할 수 있는 프로세스의 개수
  공유 자원의 개수가 S개일 경우, 임계 구역에 진입하여 동시에 실행 가능한 프로세스 혹은 스레드도 S개이다.
• wait() 함수: 임계 구역 진입 전 호출하는 함수
• signal() 함수: 임계 구역 진입 후 호출하는 함수

wait()
// 임계 구역
signal()

 

wait()는 함수 호출 시 가장 먼저 (1) 사용 가능한 공유 자원의 개수를 나타내는 변수 S를 1 감소시키고, (2) 변수 S의 값이 0보다 작은지 여부를 확인한다.

• S를 1 감소시켰을 때 S가 0 이상이라는 것은 사용 가능한 공유 자원의 개수가 남아 있었음을 의미한다. 이 경우, wait()를 호출한 프로세스 및 스레드는 임계 구역에 진입한다.
• S를 1 감소시켰을 때 S가 0 미만이라는 것은 사용 가능한 공유 자원의 개수가 남아 있지 않았음을 의미한다. 변수 S의 값이 0보다 작으면 (3) wait()를 호출한 프로세스 및 스레드는 대기 상태로 전환되어 임계 구역에 진입할 수 없게 된다.

wait() {
	S--; // (1)
    if (S < 0) { // (2)
    	sleep(); // (3)
    }
}

 

signal() 함수는 임계 구역에서의 작업이 끝난 프로세스 및 스레드가 호출한다. signal()은 함수 호출 시 가장 먼저 (1) 사용 가능한 공유 자원의 개수를 나타내는 변수 S를 1 증가시키고, (2) 변수 S의 값이 0 이하인지 확인한다.

• S를 1 증가시켰을 때 S가 0보다 크다는 것은 사용 가능한 공유 자원의 개수가 1개 이상 남아 있음을 의미한다.
• S를 1 증가시켰을 때 0 이하라는 것은 임계 구역에 진입하기 위해 대기하는 프로세스가 존재함을 의미한다. 이 경우 (3) 대기 상태로 접어든 프로세스 중 하나를 준비 상태로 전환한다.

siganl(){
	S++; // (1)
    if (S <= 0) { // (2)
    	wakeup(p) // (3)
    }
}

 

아래처럼 공유 자원이 2개, 접근하려는 프로세스가 3개이고, P1→P2→P3 순으로 임계 구역에 접근한다고 가정하면, 다음과 같은 순서로 실행된다.

 

① 프로세스 P1 wait() 호출, S를 1 감소시키면 S = 1 이므로 임계 구역 진입

② 프로세스 P2 wait() 호출, S를 1 감소시키면 S = 0 이므로 임계 구역 진입

③ 프로세스 P3 wait() 호출, S를 1 감소시키면 S = -1 이므로 대기 상태로 전환

④ 프로세스 P1 임계 구역 작업 종료. signal() 호출. S를 1 증가시키면 S=0이므로 대기 상태였던 P3을 준비 상태로 전환

⑤ 깨어난 프로세스 P3 임계 구역 진입

⑥ 프로세스 P2 임계 구역 작업 종료. signal() 호출. S를 1 증가시키면 S=1

⑦ 프로세스 P3 임계 구역 작업 종료. signal() 호출. S를 1 증가시키면 S=2

 

세마포도 뮤텍스 락처럼 여러 프로그래밍 언어에서 지원하고 있다.

import java.util.concurrent.Semaphore;

public class Sem {
    static int sharedData = 0; // 공유 데이터
    // 세마포 생성, 공유 자원 1개
    static Semaphore semaphore = new Semaphore(1);

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

        thread1.start(); // 첫 번째 스레드 시작
        thread2.start(); // 두 번째 스레드 시작

        try {
            thread1.join(); // 첫 번째 스레드 종료 대기
            thread2.join(); // 두 번쨰 스레드 종료 대기
        } catch (InterruptedException e){
            e.printStackTrace();
        }

        // 최종 공유 데이터 값 출력
        System.out.println("Final value of sharedData: " + sharedData);
    }

    static class Increment implements Runnable {
        public void run() {
            for(int i=0; i<1000000;i++) {
                try {
                    semaphore.acquire(); // 세마포 획득
                    sharedData++; // 공유 데이터 증가
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    semaphore.release(); // 세마포 해제
                }
            }
        }
    }

    static class Decrement implements Runnable {
        public void run() {
            for(int i=0; i<1000000;i++) {
                try {
                    semaphore.acquire(); // 세마포 획득
                    sharedData--; // 공유 데이터 감소
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    semaphore.release(); // 세마포 해제
                }
            }
        }
    }
}

 

이진 세마포와 카운팅 세마포

세마포는 크게 2가지 종류로 구분할 수 있는데, 하나는 이진 세마포이고, 또 하나는 카운팅 세마포이다. 위 세마포는 카운팅 세마포로, 공유 자원이 여러 개 존재하는 경우에 사용할 수 있는 세마포이다. 이진 세마포는 S가 0과 1의 값을 가지는 세마포로, 사실상 뮤텍스 락과 유사하게 동작한다.

---

조건 변수와 모니터

조건 변수

실행 순서 제어를 위한 동기화 도구로, 특정 조건 하에 프로세스를 실행/일시 중단함으로써 프로세스나 스레드의 실행 순서를 제어할 수 있다.

조건 변수에 대해 wait()와 signal() 함수를 호출할 수 있는데, wait() 함수는 호출한 프로세스 및 스레드의 상태를 대기 상태로 전환하는 함수이고, signal() 함수는 wait()로 일시 중지된 프로세스 및 스레드의 실행을 재개하는 함수이다.

• 아직 특정 프로세스가 실행될 조건이 되지 않았을 때는 wait()를 통해 실행을 중단한다.
• 특정 프로세스가 실행될 조건이 충족되었을 때는 signal()을 통해 실행을 재개한다.

 

 

 

 

cv라는 조건 변수가 있고, 프로세스 P1의 실행 도중에 조건 변수 cv에 대해 wait() 함수가 호출하면, 해당 프로세스는 다른 스레드가 cv.signal()을 호출하기 전까지 대기 상태로 접어든다.

 

 

 

 

 

 

모니터(monitor)

공유 자원과 그 공유 자원을 다루는 함수(인터페이스)로 구성된 동기화 도구로, 상호 배제를 위한 동기화뿐만 아니라 실행 순서 제어를 위한 동기화까지 가능하다.

프로세스 및 스레드는 공유 자원에 접근하기 위해 반드시 정해진 공유 자원 연산(인터페이스)을 통해 모니터 내로 진입해야 하고, 모니터 안에 진입하여 실행되는 프로세스 및 스레드는 항상 하나여야 한다. 이미 모니터 내로 진입해 실행 중인 프로세스 및 스레드가 있다면 큐에서 대기해야 한다.

 

조건변수를 함께 활용하면 실행 순서 제어를 위한 동기화도 구현할 수 있다.

예를 들어 동시에 실행되는 프로세스 A, B 중 반드시 A가 먼저 실행되고, 다음으로 B가 실행되어야 하는 조건이 있다고 가정하면, 프로세스 B는 모니터 내에서 실행되기에 앞서 프로세스 A의 실행이 끝났는지를 검사한다.

• 프로세스 B가 프로세스 A보다 나중에 모니터 내로 진입했을 경우, '프로세스 A가 먼저 실행되고, 프로세스 B가 실행되어야 한다.'는 조건이 충족외어 프로세스 B는 모니터 내로 진입해 실행된다.

조건을 충족한 경우

• 프로세스 B가 프로세스 A보다 먼저 모니터 내로 진입했을 경우, '프로세스 A가 먼저 실행되고 B가 실행되어야 한다'는 조건에 어긋나므로, 특정 조건 변수(cv)에 대해 cv.wait()를 호출해 프로세스 B를 대기 상태로 접어들게 할 수 있다.
  프로세스 B가 대기하고 있는 사이 프로세스 A가 모니터 내로 진입해 실행될 수 있고, 실행 이후 cv.signal()을 호출해 대기 상태에 있던 프로세스 B를 모니터 안으로 재진입 시킬 수 있다.

조건을 충족하지 못해 실행 순서 제어를 위한 동기화가 이루어진 경우

---

스레드 안전

멀티스레드 환경에서 어떤 변수나 함수, 객체에 동시 접근이 이루어져도 실행에 문제가 없는 상태를 의미한다. 레이스 컨디션이 발생했다면 이는 스레드 안전하지 않은 상황이지만, 어떤 함수가 스레드 안전하다면, 이는 여러 스레드에 의해 호출되어도 레이스 컨디션이 발생하지 않는 것을 의미한다.

---

교착 상태

일어나지 않을 사건을 기다리며 프로세스의 진행이 멈춰 버리는 현상을 말한다. 아래 그림처럼 프로세스 A는 자원 X를 점유한 채 프로세스 B가 점유하고 있는 자원 Y의 사용이 끝나기를 기다리고, 프로세스 B는 자원 Y를 점유한 채 프로세스 A가 점유한 자원 X의 사용이 끝나기를 기다린다고 가정하면, 두 프로세스는 서로가 가진 자원을 기다리다가 프로세스를 실행하지 못하는 교착 상태가 발생한다.

교착 상태 예시

교착 상태 발생 조건

교착 상태가 발생하는 상황에는 4가지 필요 조건이 있다. 이 중 하나라도 만족하지 않는다면 교착 상태는 발생하지 않고, 4개의 조건이 모두 만족할 때 교착 상태가 발생할 가능성이 생긴다고 보면 된다.

1. 상호 배제
   한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상호 배제의 상황에서 교착 상태가 발생할 수 있다.
2. 점유와 대기
   한 프로세스가 어떤 자원을 할당받은 상태(점유)에서 다른 자원 할당받기를 기다린다면(대기) 교착 상태가 발생할 수 있다.
3. 비선점
   어떤 프로세스도 다른 프로세스의 자원을 강제로 뺴앗지 못하는 경우 교착 상태가 발생할 수 있다.
4. 환형 대기
   프로세스와 프로세스가 요청한 자원이 원의 형태를 이루는 경우 교착 상태가 발생할 수 있다.

교착 상태 해결 방법

운영체제는 교착 상태의 발생 조건에 부합하지 않도록 자원을 분배하는 방식으로 교착 상태를 예방할 수 있고, 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있을 때 자원을 할당하지 않는 방식으로 교착 상태를 회피할 수도 있다. 또 자원을 제약 없이 할당하다가 교착 상태를 검출한 후 회복할 수 있다.

• 교착 상태 예방
  교착 상태를 발생시키는 4가지 필요 조건 중 하나를 충족하지 못하게 하는 방법이다.
  - 한 프로세스에 필요한 자원을 몰아 주고, 그 다음에 다른 프로세스에 필요한 자원을 몰아 주면 점유와 대기 조건을 만족하지 않으므로 교착 상태가 발생하지 않는다.
  - 할당 가능한 모든 자원에 번호를 매기고 오름차순으로 할당하는 경우도 원형 대기 조건을 만족하지 않으므로 교착 상태가 발생하지 않는다.
• 교착 상태 회피
  교착 상태가 발생하지 않을 정도로만 조심하면서 자원을 할당하는 방법이다. 교착 상태 회피는 기본적으로 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다.
  프로세스에 할당할 수 있는 자원이 충분한 상황에서는 프로세스들이 한두 개의 적은 자원만 요구한다면 교착 상태가 발생하지 않지만, 자원이 한정된 상황에서는 모든 프로세스들이 한 번에 많은 자원을 요구한다면 교착 상태가 발생할 위험이 증가한다.
  교착 상태 회피 알고리즘으로 은행원 알고리즘이 있다.
• 교착 상태 검출 후 회피
  교착 상태의 발생을 인정하고 처리하는 사후 조치에 해당하며, 운영체제는 프로세스가 자원을 요구할 때마다 그때 그때 자원을 할당하고 주기적으로 교착 상태의 발생 여부를 검사한다. 교착 상태가 검출되면 프로세스를 자원 선점을 통해 회복시키거나, 교착 상태에 놓인 프로세스를 강제 종료함으로써 회복시킬 수 있다.
  - 자원 선점을 통한 회복: 교착 상태가 해결될 때까지 다른 프로세스로부터 강제로 자원을 빼앗아 한 프로세스에 몰아서 할당하는 것

---

참고 자료

이것이 취업을 위한 컴퓨터 과학이다