Ray`s Tech Lab

스레드란

스레드란 하나하나의 실행 단위를 말하며, 흔히 프로세스를 차를 만드는 공장에 비유한다면 스레드를 바퀴를 만드는 일꾼, 모터를 만드는 일꾼 등에 비유하곤 합니다.

이 스레드는 커널 공간에서 구현하는 커널 스레드와 유저 공간에서 구현하는 유저 스레드 두 종류로 나눌 수 있습니다.

커널 스레드 (Kernel Threads)

: 운영 체제의 "커널"이 관리하는 스레드입니다. 프로세스가 생성되면 커널은 하나의 커널 스레드를 만드는데, "프로세스"가 아닌 이 "커널 스레드"가 실질적인 스케쥴링 대상이 되며 하나의 프로세스는 하나 이상의 커널 스레드를 가집니다.  

유저 스레드 (Kernel Threads)

: 유저 공간에서 라이브러리에 의해 관리되는 스레드입니다. 커널은 유저 스레드의 존재를 모르며, 모든 유저 스레드의 관리는 유저 공간에서 이루어집니다. 유저 스레드의 실질적인 수행은 자신이 속한 프로세스의 커널 스레드와 연결돼서 수행됩니다.

좀 더 이해하기 쉽도록, A라는 프로세스에 대해 커널 스레드를 2개 만들 때와 유저 스레드를 2개 만들 때를 도식화해서 보겠습니다.

이때, 실질적으로 스케쥴링 대상이 되는 것은 커널 스레드이며, 커널은 유저 스레드의 존재를 모른다고 했습니다.  따라서 프로세스 A, B가 있는 상황에서 A에 커널 스레드만 2개 있는 경우와 A에 유저 스레드가 2개 있는 경우는 다음과 같이 스케쥴링됩니다.

프로세스 A에 커널 스레드만 2개인 경우, A의 2개 커널 스레드 각각이 스케쥴링 대상이 됩니다. 따라서 A의 0번 스레드와 1번 스레드, 프로세스 B(얘도 B의 커널 스레드라고 볼 수 있겠죠)가 스케쥴링되는 걸 볼 수 있습니다. 그러나 프로세스 A에 유저 스레드가 2개인 경우, 커널은 유저 스레드를 모르며 오직 커널 스레드만이 스케쥴링 대상이 되기 때문에 A의 커널 스레드와 B의 커널 스레드만이 스케쥴링 대상이 됩니다. 이 때 A의 유저 스레드가 2개인 상황에서 A의 커널 스레드가 실행될 때, 0번 스레드(유저 스레드임)와 1번 스레드(유저 스레드임)를 어떻게 배분할지는 스레드 라이브러리가 책임집니다. 즉 유저 스레드는 자신이 속한 프로세스의 커널 스레드가 CPU에 올라왔을 때, 그 커널 스레드와 연결돼서 수행되는 스레드라고 볼 수 있는 것이죠.

"커널 스레드가 실질적인 스케쥴링 대상이다"로 비롯되는 다른 차이점은 어떤 것들이 있을까요? 우선 커널 스레드의 경우 같은 프로세스의 커널 스레드라 할지라도 다른 프로세서에 할당할 수 있는 반면, 같은 프로세스의 유저 스레드들은 다른 프로세서로 할당될 수 없을 수도 있습니다(커널 스레드가 CPU에 올라갔을 때 연결돼서 수행되기 때문). 즉 커널 스레드는 멀티프로세서 시스템에서 유저 스레드보다 더 효율적으로 작동한다고 볼 수 있죠. 그리고 커널 스레드가 시스템콜을 호출하면 해당 스레드만 블로킹되고, 다른 커널 스레드들은 계속 실행될 수 있습니다. 반면 유저 스레드는 하나의 유저 스레드가 시스템콜을 호출하면 같은 프로세스의 다른 유저 스레드들도 블로킹될 수 있습니다. 커널은 그 유저 스레드에 연결된 커널 스레드가 시스템콜을 호출한 거라고 여기기 때문에, 해당 커널 스레드가 블로킹되면서 물려있던다른 유저 스레드들도 블로킹될 여지가 있다는 거죠. 컨텍스트 스위칭 비용의 경우, 커널 스레드의 컨텍스트 스위칭이 유저 스레드의 컨텍스트 스위칭보다 가볍습니다.

표로 정리하면 다음과 같겠습니다.

그럼 이제 유저 스레드가 커널 스레드와 연결되는 3가지 스레드 모델을 살펴보겠습니다.

1. One-to-One Model

각 유저 스레드가 하나의 커널 스레드와 연결되는 모델입니다. 각 커널 스레드는 독립적으로 스케쥴링되므로, 같은 프로세스 내의 유저 스레드들은 각각 다른 프로세서에서 병렬로 실행될 수 있으며 하나의 유저 스레드에서 시스템콜을 호출해도 다른 유저 스레드가 블로킹되지 않습니다. 그러나 유저 스레드의 컨텍스트 스위칭 이점을 볼 수 없는 모델이기도 합니다.

2. Many-to-One Model

여러 유저 스레드가 하나의 커널 스레드와 연결되는 모델입니다. 따라서 같은 프로세스의 유저 스레드들이 서로 다른 프로세서에서 병렬로 실행될 수 없으며, 하나의 유저 스레드에서 시스템콜을 호출한 경우 다른 유저 스레드들도 블로킹될 수 있습니다. 그러나 유저 스레드의 컨텍스트 스위칭 이점을 얻을 수 있는 모델입니다.

3. Many-to-Many Model

여러 유저 스레드가 여러 커널 스레드와 연결되는 모델로 One-to-One과 Many-to-One을 짬뽕한 모델입니다. 같은 프로세스의 유저 스레드가 여러 프로세서에서 병렬로 실행될 수 있으며, 한 유저 스레드가 시스템콜을 호출해도 다른 커널 스레드에 연결된 유저 스레드들이 있으니 유저 스레드들이 모두 블로킹되는 불상사를 막을 수 있습니다. 유저 스레드의 컨텍스트 스위칭 이점도 챙길 수 있으나, 설계와 구현이 매우 복잡하며 유저 스레드와 커널 스레드 간 연결 관계의 관리 등에 오버헤드가 들어감을 감안해야 합니다.

참고로 자바에서 21버전부터 Virtual Thread가 도입됐는데요. 원래는 자바에서 유저 스레드를 만들면 그에 연결되는 커널 스레드도 함께 만들어졌습니다. 즉 기존에는 One-to-One 모델을 사용했던 것이죠. 그러나 Virtual Thread는 Many-to-One과 비슷한 컨셉을 차용해서 컨텍스트 스위칭 비용을 낮췄습니다. 관심있는 분은 다음 글을 보면 될 것 같습니다.

https://techblog.woowahan.com/15398/

피터슨의 알고리즘

컴퓨터 시스템에서 여러 프로세스가 동시에 실행될 때, 공유 자원에 대해 여러 프로세스에서 동시 접근이 가능하다면 데이터 불일치 등의 문제가 발생할 수 있습니다. 이 때 공유 자원에 대해 동시 접근이 발생 가능한 영역을 임계 영역(Critical section)이라 부르며, 이 임계 영역에서 비롯되는 문제들을 막으려면 다음과 같은 요구사항을 만족해야 합니다.

1. 상호 배제 (Mutual Exclusion)

: 한 번에 하나의 프로세스만이 임계 구역에 들어갈 수 있어야 합니다.

2. 진행 (Progress)

: 임계 구역에 들어가려는 프로세스가 없을 때, 어느 프로세스도 임계 구역에 들어갈 수 있어야 합니다.

3. 한정 대기 (Bounded Waiting)

: 각 프로세스는 임계 구역에 들어가기 위해 무한정 기다리지 않아야 합니다.

피터슨의 알고리즘(Peterson's Algorithm)은 위 요구사항들을 만족하는 고전적인 알고리즘으로, 두 프로세스 간의 상호 배제를 위해 만들어졌습니다. 1980년대에 게리 피터슨(Gary L. Peterson)에 의해 제안됐으며, 상호 배제 문제를 간단하고 효율적으로, 이해하기 쉽고 최소한의 변수만을 사용하여 구현할 수 있다는 장점이 있습니다.

피터슨의 알고리즘은 flag 배열과 turn 변수를 사용하여 두 프로세스가 임계 영역에 동시에 진입(즉 경쟁 상태 발생)하는 것을 방지합니다. flag 배열은 각 프로세스가 임계 구역에 들어가기를 원하는지를 표시하며, turn 변수는 임계 구역에 들어갈 차례인 프로세스를 나타내는데요. 이 간단한 구조 덕에 직관적이고 구현하기 쉬운 상호 배제 해결책으로 널리 알려져 있습니다.

피터슨의 알고리즘 동작 순서

피터슨의 알고리즘은 다음과 같은 순서로 각 작업이 순서대로 임계 영역에 들어가게 합니다. 

1. 임계 구역 진입 요청

: 프로세스가 임계 구역(critical section)에 들어가고자 할 때, 자신의 flag를 true로 설정하여 진입 의사를 표시합니다.

2. 양보 설정

: 프로세스는 turn 변수를 상대방 프로세스의 번호로 설정하고, 이를 통해 상대방 프로세스에게 양보할 의사를 나타냅니다.

3. 대기 상태

: 프로세스는 상대방 프로세스의 flag가 true이고, turn이 상대방 프로세스의 번호인 동안 계속해서 기다립니다(상대방 프로세스가 임계 구역에 들어가고자 할 경우 상대방에게 우선권을 주기 위함)

4. 임계 구역 진입

: 상대방 프로세스가 임계 구역에 들어가고자 하지 않거나, turn이 자신의 번호로 설정될 때까지 기다린 후 임계 구역에 진입합니다.

5. 임계 구역 종료

: 임계 구역에서의 작업을 마치면, 자신의 flag를 false로 설정하여 임계 구역에서 나왔음을 알립니다.

6. 비임계 구역 작업

: 비임계 구역에서 다른 작업을 수행합니다.

코드로 나타내면 다음과 같습니다.

// 변수 선언
boolean flag[2] = {false, false};
int turn;

function process0() {
    while (true) {
        // 1. 임계 구역 진입 요청
        flag[0] = true;
        
        // 2. 양보 설정
        turn = 1;
        
        // 3. 대기 상태
        while (flag[1] == true && turn == 1) {
            // busy-wait
        }
        
        // 4. 임계 구역 진입
        // 임계 구역에서 수행할 작업
        print("Process 0 in critical section")

        // 5. 임계 구역 종료
        flag[0] = false;

        // 6. 비임계 구역 작업
        // 비임계 구역에서 수행할 작업
        print("Process 0 in non-critical section")
    }
}

function process1() {
    while (true) {
        // 1. 임계 구역 진입 요청
        flag[1] = true;
        
        // 2. 양보 설정
        turn = 0;
        
        // 3. 대기 상태
        while (flag[0] == true && turn == 0) {
            // busy-wait
        }

        // 4. 임계 구역 진입
        // 임계 구역에서 수행할 작업
        print("Process 1 in critical section")

        // 5. 임계 구역 종료
        flag[1] = false;

        // 6. 비임계 구역 작업
        // 비임계 구역에서 수행할 작업
        print("Process 1 in non-critical section")
    }
}

피터슨의 알고리즘 문제점

1. 두 개 프로세스에서만 적용 가능

: 피터슨의 알고리짐은 기본적으로 두 개의 프로세스 사이에서만 상호 배제를 보장합니다. 2개보다 많은 프로세스를 다룰 경우 알고리즘을 확장해야 하지만, 코드가 복잡해지고 효율성이 떨어질 수 있습니다.

2. Busy waiting

: 피터슨의 알고리즘은 다른 프로세스가 임계 영역에 들어가있는 동안 다른 프로세스는 무한 루프를 통해 대기(Busy waiting)하는데, 이는 CPU 자원의 낭비 및 효율성 저하의 원인이 됩니다. 또한 실시간 시스템인 경우, Busy waiting은 일종의 지연 현상을 초래할 수도 있습니다.