프로세스 동기화

운영체제

프로세스 동기화

realizers 2023. 3. 21. 21:44

728x90

협력적 프로세스는 시스템 내에서 다른 프로세스와 협력하여 서로의 프로세스에 영향을 주거나 영향을 받는 프로세스입니다.
협력적 프로세스는 논리 주소 공간(코드나 데이터)을 공유하거나 공유 메모리 또는 메시지 전달을 통해서만 데이터를 공유할 수 있는데 이러한 공유 데이터를 공유하게 되면 데이터 일관성이 깨질 수 있습니다. 그렇기 때문에 우리는 어떻게 공유 데이터에 대해 일관성을 보장할 수 있는지 살펴보겠습니다.

Race Condition이란

우선 공유 데이터를 공유하면 어떻게 데이터 일관성이 깨질 수 있는지 파악해야합니다. 파악하기 위해서는 race condition(경쟁 상태)에 대해 간략하게 알 필요성이 있습니다.
race condition이란 두 개 이상의 프로세스 또는 스레드가 하나의 리소스에 대해 접근하여, 타이밍이나 순서 등이 최종적 결과값에 영향을 줄 수 있는 상태입니다.

🤔 race condition이 발생하는 코드

아래의 예제를 보면 race condition이 발생할 수도 있고, 발생하지 않을 수도 있습니다.
2개의 Thread를 만들어 Counter 클래스의 increment 메서드에 접근하여 count 변수의 값을 증가시키고 있습니다. 이때 T1 스레드와 T2 스레드가 동시에 count 변수에 접근하게 된다면 동일한 값을 증가시키게 됩니다. 즉 두 스레드가 공유 데이터(count)에 접근하여 race condition으로 인해 데이터 일관성이 깨지게 됩니다.

public class Counter {

    private int count = 0;

    public void increment() {
        this.count++;
    }

    public int getCount() {
        return count;
    }
}

public class RaceConditionTest {

    private static final ExecutorService executor = Executors.newFixedThreadPool(2);

    @Test
    void example() throws InterruptedException {

        Counter counter = new Counter();
        int threadCount = 1000;
        CountDownLatch latch = new CountDownLatch(threadCount);

        for (int i = 0; i < threadCount; i++) {
            CompletableFuture.runAsync(() -> {
                try {
                    counter.increment();
                } finally {
                    latch.countDown();
                }
            }, executor);
        }
        latch.await();

        assertThat(counter.getCount()).isEqualTo(threadCount);
    }
}

Critical Section이란

Critical Section이란 임계구역입니다. 각 프로세스에는 Critical Section이라는 코드 부분을 포함하고 있습니다. Critical Section에서는 공유 데이터에 접근하고 갱신할 수 있습니다.
한 프로세스가 Critical Section에서 수행하는 동안 다른 프로세스들은 Critical Section에 접근할 수 없습니다. 즉 동시에 두 개 이상의 프로세스나 스레드는 임계구역 안에서 실행될 수 없습니다.
프로세스 또는 스레드는 임계구역에 진입하기 위해서는 진입 허가를 요청해야 합니다. 이러한 요청을 구현하는 코드 부분을 진입 구역이라 부르고, 임계구역 뒤에는 퇴출 구역이 있습니다.
운영체제 내에서 임계구역을 다루기 위해서 선점형 커널과 비선점형 커널의 두가지 일반적인 접근법이 사용됩니다.

💡 Critical Section의 문제 해결 조건

임계구역 문제를 해결하기 위해서는 3가지 조건을 충족해야 합니다.

상호 배제(Mutual Exclusion)

하나의 프로세스 또는 스레드가 임계구역(Critical Section)에 들어간다면 다른 프로세스 또는 스레드는 접근할 수 없습니다.

진행(Progress)

임계구역(Critical Section)에 들어간 프로세스나 스레드가 없는 상태에서, 들어가고자 하는 프로세스나 스레드가 여러개 있디면
누가 그 임계구역으로 진입할 수 있는지 결정해줘야 합니다. 또한 이 결정은 무한정 연기될 수 없습니다.

한정된 대기(bounded waiting)

하나의 프로세스 또는 스레드가 임계구역(Critical Section)에 진입하여 오랫동안 나오지 않으면 다른 프로세스나 스레드가 집입할 수 없게 됩니다. 이러한 기아를 방지하기 위해 한 번 임계구역(Critical Section)에 들어간 프로세스나 스레드가 다음에 진입할 때 제한을 둬야 합니다.

💡 선점형 커널과 비선점형 커널

운영체제 내에서 임계구역을 다루기 위해 선점형 커널과 비선점형 커널의 두 가지 일반적인 접근법이 사용됩니다.

선점형 커널이란

프로세스나 스레드가 커널 모드에서 수행되는 동안 선점되는 것을 허용합니다.

비선점형 커널이란

커널 모드에서 수행되는 프로세스나 스레드의 선점을 허용하지 않고, 해당 프로세스나 스레드가 커널 모드를 빠져나갈 때까지 봉쇄되거나, 자발적으로 CPU 제어를 양보할 때까지 계속 수행하게 됩니다.(종료되거나 대기 큐에 적재되기 전까지)

Mutex Lock

프로세스나 스레드가 임계구역에 진입하기 전 반드시 Lock을 획득하고, 임계구역을 빠져나올 때는 Lock을 반환해야 합니다.
Mutext Lock은 available 이라는 변수를 가지는데 이 available 변수 값이 Lock의 가용 여부를 표시합니다. 만약 Lock이 가용하다면 acquire() 메서드를 호출하여 Lock을 획득하고, 다른 프로세스나 스레드가 접근하지 못하도록 Lock은 곧 사용불가 상태가 됩니다.
사용 불가 상태의 Lock을 획득하려고 시도하는 프로세스나 스레드는 Lock이 반환될 때까지 대기하게 됩니다.
Mutex Lock의 단점은 busy waiting을 해야 합니다. 프로세스나 스레드가 Lock을 획득하여 임계구역에 있는 동안 임계구역에 들어가고자 하는 다른 프로세스나 스레드들은 반목문을 통해 계속하여 acquire 메서드를 호출하고 있을것입니다. Lock이 가용해지길 기다리면서 계속하여 반복 회전하고 있기 때문에 spinLock이라고도 합니다. busy waiting은 CPU Cycle을 낭비하게 됩니다.

Semaphore

세마포어는 Signaling 매커니즘이라는 점에서 뮤텍스와 다릅니다. 세마포어는 락을 걸지 않은 스레드도 signal을 보내 락을 해제할 수 있습니다.
세마포어는 이진 세마포어와 카운팅 세마포어로 나뉩니다.

💡 이진 세마포어

이진 세마포어의 값은 0과 1 사이의 값만 가능합니다. 이진 세마포어는 Mutex Lock과 비슷하게 동작합니다.
만약 어떠한 프로세스나 스레드가 Lock을 사용할 수 없으면 0이고, 사용할 수 있으면 1입니다. 이렇게 0또는 1의 값만 갖는 세마포어를 이진 세마포어라 합니다.

💡 카운팅 세마포어

카운팅 세마포어는 0과 1뿐만 아니라 0, 1, 2, 3, 4, 5 ... 등의 값을 가질 수 있는, 즉 도메인 제한이 없는 카운팅 세마포어 입니다.
예를들어 주문을 접수받는 키오스크가 5개가 있습니다. 이때 사용자가 주문을 접수하고자 서버에 요청을 하면, 키오스크가 5개 있으므로 공유자원은 5개로 설정이 됩니다. 그리고 사용자가 키오스크를 사용할때마다 그 값은 하나씩 감소됩니다. 그러다 사용하고자 하는 키오스크가 없어지면 0이되고, 누군가 키오스크를 다 사용하고 반환하면 다시 1이 증가됩니다. 이런식으로 세마포어는 변수는 공유자원의 개수를 나타내는 변수입니다.
카운팅 세마포어는 유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용될 수 있습니다. 세마포어는 가용한 자원의 개수로 초기화됩니다는 위의 예를통해 이해할 수 있습니다.

wait() 메서드와 signal 메서드

wait()와 signal()는 연산 시 세마포어의 정수값을 변경하는 연산은 반드시 원자적으로 수행되어야 합니다. 즉 하나의 프로세스 또는 스레드가 세마포어의 값을 변경하면, 다른 어떤 프로세스나 스레드가 동시에 동일한 세마포어의 값을 변경할 수 없습니다.
세마포어 변수 S는 초기화를 제외하면 atomic operation인 wait, signal 메서드로만 접근 가능한 정수 타입의 변수입니다.
wait는 shared data를 확인하여 사용 가능한 shared data가 없으면 wait입니다. 반면 사용 가능한 shared data가 있으면 signal 입니다.

🤔 Mutex Lock과 Semaphore의 차이점은 뭘까?

세마포어에는 이진 세마포어가 있습니다. 그렇기 때문에 세마포어는 뮤텍스가 될 수 있지만, 반대로 뮤텍스는 세마포어가 될 수 없습니다. 세마포어에는 카운팅 세마포어도 존재하기 때문입니다.
동기화 대상의 개수입니다. 뮤텍스는 동기화 대상이 오직 하나뿐인데, 세마포어는 동기화 대상이 하나 이상일 때 사용됩니다.
뮤텍스는 Locking 매커니즘으로 락을 걸은 스레드만이 임계구역을 나갈때 락을 해제할 수 있습니다. 반면 세마포어는 Signaling 매커니즘으로 락을 걸지 않은 스레드도 signal을 보내 락을 해제할 수 있습니다.

🤔 Semaphore는 어떻게 동작할까?

카운팅 세마포어로 예를들어보겠습니다. 3개의 공유자원을 사용할 수 있다는 가정하에 Critical Section에는 이미 P1, P2, P3의 프로세스로 인해 더이상 가용할 수 있는 자원이 없습니다. 이때 P4가 Critical Section에 진입하고자 한다면 가용할 자원이 없으므로 Waiting Queue에 적재되게 됩니다. 그리고 시간이 지나 Critical Section에 가용할 자원이 생긴다면 Waiting Queue에서 기다리고 있던 P4가 Critical Section에 진입하게 됩니다.
또한 실행중인 프로세스가 signal operation을 수행하게 되면 Waiting Queue에서 대기하고 있던 하나의 프로세스가 깨어나게 됩니다. 그리고 가용할 수 있는 자원이 +1이 되어 깨어난 프로세스는 Critical Section에 진입하게 됩니다.

🤔 Semaphore의 장점과 단점은?

장점
- 프로세스나 스레드가 Critical Section에 접근할 수 있도록 조건이 충족되었는지 확인하기 위해 시간이 불필요하게 낭비되지 않기 때문에 busy waiting으로 인한 자원 낭비가 발생하지 않습니다.
단점
- 세마포어는 우선순위가 낮은 프로세스나 스레드가 Critical Section에 먼저 접근하고 우선순위가 높은 프로세스나 스레드가 나중에 접근할 수 있는 우선순위 역전이 발생할 수 있습니다.
- 세마포어의 교착상태를 방지하기 위해서는 wait 및 signal 작업이 올바른 순서로 실행되어야 합니다.

Monitor

세마포어가 프로세스나 스레드간 동기화를 위해서 편리하고 효과적으로 사용될 수는 있지만 세마포어를 자칫 잘못 사용하면 발견하기 어려운 타이핑 오류를 야기할 수 있습니다. 이런 타이핑 오류는 특정 실행 순서로 진행되었을 때만 발생하고, 이러한 순서가 항상 일어나는 것은 아니기 때문입니다.
세마포어는 wait & signal 연산 순서를 바꿔 실행하거나 wait & wait 순서로 구송되어 있으면 교착 상태가 발생합니다. 또한 wait & signal이 시스템 전체에 구성되어 있으면 세마포어의 영향이 미치는 곳이 어딘지 파악하기 힘듭니다. 이러한 단점을 극복하기 위해 모니터가 등장했습니다.
모니터는 임계구역을 지켜내기 위한 방법인 상호 배제 방법으로 구현했으며, 이진 세마포어만 가능합니다.

💡 모니터의 개념

하나의 객체마다 하나의 모니터를 결합할 수 있습니다. 모니터는 객체가 동시에 두 개 이상의 스레드에 접근할 수 없도록 Lock을 제공함으로써 동기화를 수행하는 동기화 도구입니다.
객체에 모니터를 결합하면 하나의 스레드가 해당 객체를 사용하고 있는 동안 다른 스레드들이 객체를 사용할 수 없게 됩니다.
자바에서는 synchronized 키워드로 구현할 수 있습니다.

💡 모니터의 구조

상호 베타 큐

공유 자원에 하나의 프로세스만 집입하도록 하기 위한 큐입니다.
특정 스레드가 공유 자원을 사용하는 함수를 사용하고 있으면 다른 스레드는 접근할 수 없고 상호 베타 큐에서 대기해야 합니다.

조건 동기 큐

공유 자원의 Lock이 해제되길 기다리는 스레드가 대기하는 큐입니다.
진입 스레드가 블록되면서 새 스레드가 진입가능하게 하는 큐입니다. 새 스레드는 조건 동기로 인해 블록된 스레드를 깨울 수 있습니다. 이렇게 깨워진 스레드는 현재 스레드가 나가면 재진입할 수 있습니다.

💡 자바에서의 모니터 원리

상호 배타 큐는 자바에서 synchronized 키워드를 사용해서 지정할 수 있습니다. 반면 조건 동기 큐는 wait, notify, notifyAll 메서드를 사용합니다.
자바에서 synchronized 키워드가 선언된 메서드에 접근하기 위해서는 상호 배타 큐에 적재하게 됩니다.
조건 동기 큐의 경우 wait 메서드를 실행하면 진입한 스레드를 조건 동기 큐에 블록시킵니다. 그리고 notify나 notifyAll 메서드를 사용하여 깨웁니다.

💡 wait 메서드

wait 메서드는 오직 synchronized 블록 내에서만 호출 가능합니다. wait 메서드의 기능은 객체가 가지고 있는 Lock을 release하는 것이기 때문에 만약 wait를 호출하는 스레드가 Lock을 소유하고 있지 않다면 예외가 발생합니다.
Lock을 release하는 것을 조금 더 정확히 표현하면 제어권을 다른 스레드에게 넘겨주는 것입니다. 그리고 release한 스레드는 조건 동기 큐에 적재됩니다.
wait 메서드를 호출하면 Lock을 소유하고 있던 스레드는 Lock을 release하면서 WAITING 또는 TIMED_WAITING 상태로 변하게 되면서 조건 동기 큐에 적재되는데 여기에 적재된 스레드들은 notify나 notifyAll 메서드를 호출함으로써 다시 임계구역으로 이동하게 됩니다.

💡 notify, notifyAll

wait 메서드에 의해 조건 동기 큐에 적재된 스레드를 깨우기 위해서는 notify나 notifyAll 메서드를 사용하여 스레드를 깨울 수 있습니다.
notify보다는 notifyAll을 사용하는게 더 안전한 이유는 뭘까?

참고자료

728x90

저작자표시