[전공생이 설명하는 OS] 쓰레드(Thread)와 동기화 문제

1. 쓰레드의 의미

프로세스의 의미를 두가지 측면에서 설명할 수 있다.

1. (자원 관점) 자원 소유자로서의 최소 단위
2. (제어 관점) schedule 의 최소 단위 / 실행의 단위

보통 개발할 때 하나의 실행 흐름(single execution sequence)만 생각하기 쉽다.. 하지만 실제로 프로세스에는 실타래와 같이 여러개의 실행흐름(multiple execution sequence)이 존재할 수 있다. 이 때 실행의 단위(the unit of execution sequence)를 thread 라고 정의한다. 따라서 현대 os에서 multithreading은 단일 프로세스 내에서 여러개의 실행 흐름을 지원할 수 있는 능력을 의미한다. 가장 중요한 점은 다수의 thread는 같은 프로세스 내의 자원을 공유할 수 있다는 것이다.

 

---

2. Concurrency vs Parallelism

(1) Concurrency

Concurrency

  - 병행성, 동시성

  - 여러 job 들이 interleaving 하면서 진행.

  - 실제로 동시에 진행되고 있지는 않지만, user 입장에서는 동시에 진행되는 듯한 illusion을 제공

(2) Parallelism

Parallelism

  - 병렬성

  - 여러 코어에서 실제로 동시에 실행되고 있는 것을 말함.

  - concurrent 하지 않아도 parallel 할 수 있다.

---

3. Multi-Threading

1) multithread 장단점

프로세스와 스레드

  MS/DOS 의 경우 단일 프로세스-단일 스레드 구조였다. 인터넷이 발전하면서, 동시 접속자를 빠르게 처리해야하는 웹서버의 요구가 생겨났다. 간단하게 프로세스를 여러개로 fork 하는 방법도 있고, 멀티 스레드를 지원하는 방법도 있다. 보통 스레드를 생성하는 것이 더 비용이 저렴하다. One process - Multiple threads 모델은 JVM 환경이 대표적인 예시이다. UNIX 계열의 대부분의 현대 os는 Multiple processes - Multiple threads per process 구조이다. 멀티 스레드는 아래와 같은 장점이 있다.

• 응답성이 좋아진다. (ex. WebServer, Remote Procedure Call)
• 경제성이 좋다. (프로세스 대비 creation, switch, resource sharing, communication, memory space) => Light weight process 라고도 함.
• 멀티코어에서 병렬적으로 수행할 경우 더 좋은 성능을 낸다.

  하지만 스레드가 무한정 증가한다고 계속 좋은 결과를 내지는 않는다. 위의 그래프를 보면 어느 순간 그래프가 급격하게 꺾여서 감소하게 된다. (1) 스레드가 너무 많아서 스케줄링과 switch에 드는 오버헤드가 훨씬 커지기 때문이다.  (2) 또 증가하는 부분을 보면, 스레드 수에 정비례하게 성능이 증가하지 않고 갈수록 완만하게 증가한다. 이는 스레드를 분할하고 다시 합치는 과정에서 serial하게 작업할 수 밖에 없는 부분이 존재하기 때문이다(Amdahl의 법칙).

  그렇다면 언제 멀티코어 환경에서 멀티스레딩을 하는게 좋을까?

1. tasks 가 서로 독립적이어서 병렬로 처리될 수 있는 경우 (task parallelism)
2. 각 스레드에 동등한 workload를 분배할 수 있는 경우 (load balancing)
3. 처리되는 data에 의존성이 없어야한다. 있는 경우 동기화를 해야함. (data parallelism)

2) process image

프로세스 생성(왼쪽)과 스레드 생성(오른쪽) 비용 비교

  Single-threaded process image는 (PCB + User stack + Kernel stack + User address space)를 포함한다. 멀티스레드에서는 각 스레드마다 State(running, block, ...)와 stack 을 따로 가져야하고, 또 os 가 각 스레드를 관리하기 위한 Thread control block도 따로 가져야한다. (`프로세스 이미지`에 대해서는 프로세스(Process)란? 을 참고)

  기존의 Process image 에서 스레드간 공유가 가능한 것과 그렇지 않은 것을 구분할 필요가 있다. 새롭게 스레드가 생성된다고 가정하면, 텍스트 코드나 데이터들은 공유가 가능하므로 새로 복제할 필요가 없다. 하지만 스레드는 각자 다른 실행흐름을 가지므로 배타적으로 관리해야할 정보들을 모아야하고, 이를 모아 구조체로 만든것이 TCB이다. 현대 OS는 오른쪽 그림과 같은 프로세스 이미지를 갖는다. 

---

4. Multithreading Models

1) Kernel-Level Threads (KLTs)

  - 스레드 관련 모든 작업을 커널이 담당한다. (안정적이다.)

  - Windows와 Solaris 는 커널 스레드를 사용한다.

  - Pthreads(POSIX 스레드) 에서는 PTHREAD_SCOPE_SYSTEM 옵션으로 커널 스레드를 사용할 수 있다.

  - system call 에 의존하기 때문에 mode switch가 필연적이다. (오버헤드가 존재한다.)

OS별 스레드

  - OS의 종류마다 제공하는 thread api 가 존재한다. (UNIX-POSIX pthreads, Windows-Win32 threads, JVM-Java threads, Android-Android threads)

2) User-Level Threads (ULTs)

  - library 형태로 논리적인 멀티스레드를 지원한다.

  - 모드 전환 없이, 프로시저 콜만큼의 속도로 매우 빠르게 멀티스레드를 사용할 수 있다.

  - 커널이 스레드의 존재를 모르기 때문에 안정성이 떨어진다. (ex. 한 스레드가 유저 레벨에서 block 되면 모든 스레드가 정지한다.) => 되도록 non-blocking 함수를 쓰는 등의 작업이 필요

 

3) Hybrid Threads

  - KLTs의 안정성과 ULTs 의 속도를 모두 취하기 위한 절충안. (ex, Java thread)

 

---

5. Race condition

  아래 코드는 메인 스레드가 자식 스레드를 2개 만들고, 하나는 공유변수를 1000번 increment 하고 다른 하나는 1000번 decrement 하는 경우이다. 

/* bad sharing */
#include <pthread.h>
#include <stdio.h>
#define ITER 1000

void *thread_increment(void *arg);
void *thread_decrement(void *arg);
int x;

int main() {
    pthread_t tid1, tid2;
    pthread_create(&tid1, NULL, thread_increment, NULL);
    pthread_create(&tid2, NULL, thread_decrement, NULL);

    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);

    if (x != 0)
        printf("BOOM! counter=%d\n", x);
    else
        printf("OK counter=%d\n", x);
}

/* thread routine */
void * thread_increment (void *arg) {
    int i, val;
    for (i=0; i< ITER ; i++) {
        val = x;
        printf("%u: %d\n", (unsigned int)pthread_self(), val);
        x = val + 1;
    }
    return NULL;
}

void * thread_decrement (void *arg) {
    int i, val;
    for (i=0; i< ITER ; i++) {
        val = x;
        printf("%u: %d\n", (unsigned int)pthread_self(), val);
        x = val - 1;
    }
    return NULL;
}

예상되는 결과는 0이 되어야 할 것 같지만, 그렇지 않다. 어떤 결과가 나올지는 보장할 수 없다.

실행 결과 예시

그 이유는 (x = val + 1) 과 (x = val - 1) 이라는 코드가 atomic 하지 않기 때문이다. 바이트 코드의 어셈블리어로 보면 3단계의 명령어로 이루어져 있다.

1. 전역변수 x를 레지스터로 load
2. 해당 레지스터의 값을 1만큼 decrement (또는 increment)
3. 전역변수 x의 메모리 주소에 store

이 3가지의 어셈블리 코드가 중간에 끊기지 않고 실행되어야 한다. 그런데 2번을 수행하고 나서 time-out interrupt가 발생해 context switch가 진행되고, 다시 원래 스레드로 돌아왔을 때 3번 명령을 실행한다. 즉, 최신화된 x 값을 load 하면서 시작하는 것이 아니라 예전에 저장되어 있던 outdated 한 x 값을 덮어쓰면서 시작한다. 이런 상황 때문에 공유변수에 대한 동기화 문제가 발생한다.