11. Concurrency - Threads

Concurrency: Threads

Concurrency

• 이 단원에서 다루는 것은 concurrency다.
• concurrency는 사용자 공간에서도 나타난다.
  • multi-threaded program을 실행할 때 발생한다.
• concurrency는 kernel 공간에서도 나타난다.
  • kernel 내부에서도 여러 실행 흐름이 동시에 shared resource에 접근할 수 있다.
• 따라서 OS가 고민해야 하는 문제는 다음과 같다.
  • multi-threaded program을 어떻게 지원할 것인가?
  • shared resource에 대한 접근을 어떻게 조정할 것인가?

Motivation

• process는 새로운 프로그램을 실행하기 위한 좋은 abstraction이다.
• OS는 process를 통해 다음을 제공한다.
  • protection
  • isolation
• 하지만 process만으로는 한계가 있다.
  • 하나의 process는 multi-core를 제대로 활용하기 어렵다.
  • 협력하는 여러 작업을 여러 process로 만들면 프로그래밍이 번거롭다.
  • process 생성 비용이 크다.
  • process 간 communication overhead가 크다.
  • process 간 context switching도 비싸다.
• 그래서 핵심 질문은 다음과 같다.
  • 하나의 process 안에서 더 싸게 concurrency를 늘릴 수 없을까? > thread

What is a Thread?

• thread는 program 안에서 실행되는 instruction sequence, 즉 하나의 실행 흐름이다.
• thread는 다음을 자기 것으로 가진다.
  • Thread ID
  • Register set
    • PC
    • SP
    • 기타 CPU register
  • Stack
• 반면 같은 process 안의 thread들은 다음을 공유한다.
  • address space
  • code
  • data
  • heap
  • open file 등 process-level resource
• 즉 thread는 process와 execution state를 분리한 개념이다.
• process는 resource container에 가깝고, thread는 실제로 CPU 위에서 실행되는 단위에 가깝다.

Using Threads

#include <stdio.h>
#include <pthread.h>

void *hello(void *arg)
{
    printf("hello, world\n");
    return NULL;
}

int main()
{
    pthread_t tid;

    pthread_create(&tid, NULL, hello, NULL);
    printf("hello from main thread\n");

    pthread_join(tid, NULL);
    return 0;
}

• pthread_create()를 호출하면 새로운 thread가 만들어지고, 지정한 함수부터 실행한다.
• 위 예시에서는 main thread와 새로 만든 thread가 동시에 실행될 수 있다.
• 그래서 출력 순서는 항상 고정되어 있지 않을 수 있다.

Address Space with Threads

• 같은 process 안의 thread들은 하나의 address space를 공유한다.
• 즉, code/data/heap은 공유되며 각 thread는 자기 stack/PC(현재 실행 중인 instruction 위치)/SP(자기 stack의 현재 위치)를 가진다.
• thread 사이에는 protection이 없다.
  • 같은 process 안의 thread는 같은 주소 공간을 보기 때문에, 한 thread가 잘못된 pointer로 heap이나 global data를 망가뜨리면 같은 process의 다른 thread도 영향을 받는다.
• Question: Which one is faster?
  • Process creation vs. thread creation > thread
  • Process switch vs. thread switch > thread

Processes vs. Threads

• thread는 하나의 process에 속한다.
• 하나의 process는 여러 thread를 가질 수 있다.
• thread 사이의 data sharing은 싸다.
  • 모두 같은 address space를 보기 때문이다.
• scheduling의 단위는 thread / process는 thread가 실행되는 container

Benefits of Multi-threading

cheap concurrency + shared memory + parallelism

• 1. concurrency를 싸게 만들 수 있다.
  • process를 여러 개 만드는 것보다 thread를 여러 개 만드는 것이 일반적으로 가볍다.
• 2. program structure를 개선할 수 있다.
  • 큰 작업을 여러 cooperative thread로 나눌 수 있다.
• 3. throughput을 높일 수 있다.
  • 한 thread가 I/O를 기다리는 동안 다른 thread가 computation을 수행할 수 있다.
• 4. responsiveness를 높일 수 있다.
  • 예를 들어 web server는 여러 client request를 동시에 처리해야 한다.
• 5. resource sharing이 쉽다.
  • 같은 process 안의 thread들은 address space를 공유하기 때문이다.
• 6. multi-core architecture를 활용할 수 있다.
  • 여러 thread를 여러 core에서 병렬로 실행할 수 있다.

Threads Interface

• Pthreads(POSIX Threads): POSIX 표준 API이며, thread 생성과 synchronization을 위한 interface를 제공한다.
• Pthreads API는 behavior를 정의한다.
  • 실제 구현은 thread library나 OS가 맡는다.
• Unix-like OS에서 널리 사용된다.
  • Linux
  • macOS
  • Solaris
  • FreeBSD
  • NetBSD
  • OpenBSD
• Windows는 별도의 thread API를 가진다.
  • Win32/Win64 threads

Pthreads: Thread Creation and Termination

• thread 생성과 종료에 관련된 대표 함수는 다음과 같다.

int pthread_create(
    pthread_t *tid,
    pthread_attr_t *attr,
    void *(*start_routine)(void *),
    void *arg
);

void pthread_exit(void *retval);

int pthread_join(
    pthread_t tid,
    void **thread_return
);

• pthread_create()는 새로운 thread를 만든다.
  • tid: 생성된 thread ID를 저장할 곳
  • attr: thread attribute, 기본값이면 NULL
  • start_routine: thread가 실행할 함수
  • arg: 그 함수에 넘길 인자
• pthread_exit()은 현재 thread를 종료한다.
• pthread_join()은 특정 thread가 끝날 때까지 기다린다.
  • process에서 wait()가 child process를 기다리는 것과 비슷하게 볼 수 있다.

Pthreads: Mutexes

• mutex는 mutual exclusion을 위한 도구다.
• 즉 여러 thread가 동시에 critical section에 들어가지 못하게 한다.
• 대표 함수는 다음과 같다.

int pthread_mutex_init(
    pthread_mutex_t *mutex,
    const pthread_mutexattr_t *mattr
);

void pthread_mutex_destroy(
    pthread_mutex_t *mutex
);

void pthread_mutex_lock(
    pthread_mutex_t *mutex
);

void pthread_mutex_unlock(
    pthread_mutex_t *mutex
);

• pthread_mutex_lock()은 lock을 얻을 때까지 기다린다.
• pthread_mutex_unlock()은 lock을 해제한다.
• shared data를 수정하는 코드는 보통 mutex로 감싸야 한다.

pthread_mutex_lock(&lock);

/* critical section */

pthread_mutex_unlock(&lock);

• thread들은 address space를 공유하기 때문에 data sharing은 쉽지만, 그만큼 race condition이 생기기 쉽다.
• 따라서 thread를 제대로 쓰려면 synchronization이 필수다.

Pthreads: Condition Variables

• condition variable은 어떤 조건이 만족될 때까지 thread를 재우고 깨우는 데 사용한다.
• 대표 함수는 다음과 같다.

int pthread_cond_init(
    pthread_cond_t *cond,
    const pthread_condattr_t *cattr
);

void pthread_cond_destroy(
    pthread_cond_t *cond
);

void pthread_cond_wait(
    pthread_cond_t *cond,
    pthread_mutex_t *mutex
);

void pthread_cond_signal(
    pthread_cond_t *cond
);

void pthread_cond_broadcast(
    pthread_cond_t *cond
);

• pthread_cond_wait()은 조건이 만족될 때까지 기다린다.
• 이때 mutex와 함께 사용된다.
• pthread_cond_signal()은 기다리는 thread 하나를 깨운다.
• pthread_cond_broadcast()는 기다리는 모든 thread를 깨운다.
• condition variable은 단순히 mutual exclusion을 넘어서, thread 간 event coordination을 위해 사용된다.

How to Implement Thread?

• Kernel-level thread
• User-level thread

Kernel-level Threads

• OS가 관리
• OS는 process뿐 아니라 thread도 직접 관리함.
• 모든 thread operation은 kernel에서 구현된다.
• thread 생성과 관리에는 system call이 필요하다.
• OS scheduler가 모든 thread를 scheduling한다.
• process 생성보다는 thread 생성이 싸다.
• 실제 OS에서 널리 쓰인다.
  • Windows
  • Linux
  • Solaris
  • macOS
  • AIX
  • HP-UX
• 장점은 kernel이 thread의 존재를 알고 있다는 점이다.
  • 한 thread가 blocking I/O를 해도 같은 process의 다른 thread를 실행할 수 있다.
  • 여러 thread를 여러 core에 배치할 수 있다.
• 하지만 단점도 있다.
  • thread operation이 system call이므로 여전히 비용이 있다.
  • kernel이 각 thread에 대한 kernel state를 유지해야 한다.
  • 동시에 만들 수 있는 thread 수에 제한이 생길 수 있다.
  • thread 수가 많아질수록 OS scheduler와 kernel 구조가 잘 scale해야 한다.
  • kernel-level thread는 다양한 program, language runtime, library 요구를 모두 지원해야 하므로 일반적이고 무거워질 수 있다.

User-level Threads

• user space에서 구현되는 thread
• thread library가 process 안에 link되어 thread를 관리한다.
• kernel은 user-level thread들의 존재를 모른다.
• kernel 입장에서는 그냥 하나의 process처럼 보인다.
• thread operation은 procedure call로 처리된다.
  • kernel involvement가 없다.
  • system call이 필요 없다.
• 그래서 작고 빠르다.
  • 슬라이드에서는 kernel-level thread보다 10~100배 빠를 수 있다고 설명한다.
• portable하다.
  • OS가 특별히 thread를 지원하지 않아도 library로 구현할 수 있다.
• application의 필요에 맞게 조정하기 쉽다.
  • runtime system이 직접 scheduling policy를 만들 수 있다.

User-level Threads: Limitations

• user-level thread는 보통 non-preemptive scheduling에 의존한다.
  • 한 thread가 자발적으로 양보하지 않으면 다른 user-level thread가 실행되기 어렵다.
  • Unix signal 등을 이용해 preemptive scheduling을 흉내낼 수는 있다.
• kernel이 user-level thread를 모르기 때문에 잘못된 결정을 할 수 있다.
  • 실제로는 idle thread만 있는 process를 scheduling할 수 있다.
  • 한 user-level thread가 blocking I/O를 호출하면 process 전체가 block될 수 있다.
  • lock을 잡고 있는 thread가 있는데 kernel이 process를 unschedule할 수도 있다.
• blocking system call을 모두 non-blocking call로 흉내내야 할 수 있다.
  • 이를 위해 kernel과 user-level thread manager 사이의 coordination이 필요하다.
• 가장 큰 한계 중 하나는 multi-core CPU를 제대로 활용하기 어렵다는 것이다.
  • kernel 입장에서는 thread가 하나로 보이기 때문이다.
• 즉 user-level thread는 빠르지만, kernel과의 협력이 부족하면 실제 시스템에서는 문제가 생길 수 있다.

Threading Model: One-to-One

• One-to-One, 즉 1:1 모델은 user-level thread 하나가 kernel thread 하나에 대응되는 방식이다.
• 현재 가장 널리 쓰이는 방식
  • Windows XP/7/10
  • Linux
  • Solaris 9+
• 장점은 kernel이 각 thread를 알고 scheduling할 수 있다는 점이다.
• 따라서 multi-core 활용이 가능하다.
• 한 thread가 block되어도 다른 thread를 계속 실행할 수 있다.
• 단점은 thread가 많아지면 kernel thread도 그만큼 많아진다는 점이다.
  • kernel state 관리 비용이 증가한다.
  • thread 생성/전환 비용이 user-level thread보다 크다.

Threading Model: Many-to-One

• Many-to-One, 즉 N:1 모델은 여러 user-level thread가 하나의 kernel thread에 매핑되는 방식.
• kernel은 여러 user-level thread를 모른다.
• user-level thread library가 thread switching을 담당한다.
• 예시는 다음과 같다.
  • Solaris Green Threads
  • GNU Portable Threads
• 장점은 thread operation이 매우 빠르다는 점이다.
• 단점은 user-level thread의 한계를 그대로 가진다.
  • 한 thread가 blocking system call을 하면 전체 process가 block될 수 있다.
  • 여러 core에서 동시에 실행되기 어렵다.
• 따라서 concurrency는 만들 수 있지만, true parallelism은 얻기 어렵다.

Threading Model: Many-to-Many

• Many-to-Many, 즉 M:N 모델은 여러 user-level thread를 여러 kernel thread에 매핑하는 방식이다.
• user-level thread 수와 kernel thread 수를 다르게 둘 수 있다.
• OS는 충분한 수의 kernel thread를 만들고, user-level runtime은 그 위에 많은 user-level thread를 올릴 수 있다.
• 예시는 다음과 같다.
  • Solaris prior to v9
  • IRIX
  • HP-UX
  • Tru64
• 장점은 user-level thread의 빠른 관리와 kernel-level thread의 parallelism을 어느 정도 동시에 얻을 수 있다는 점이다.
• 단점은 구현이 복잡하다는 점이다.
  • kernel과 user-level thread library가 잘 협력해야 한다.
  • scheduling, blocking system call, signal 처리 등이 복잡해진다.

Big Picture: Process vs Kernel-level Threads

• process만 있는 경우에는 context switch가 process 단위로 일어난다.
• 이때 OS kernel은 다음을 바꿔야 할 수 있다.
  • CPU register context
  • address space
• 즉 process A에서 process B로 넘어가면, 실행 흐름뿐 아니라 주소 공간도 바뀜.
• kernel-level thread가 있는 경우에는 하나의 process 안에 여러 thread가 있을 수 있다.
• 같은 process 안의 thread 간 전환은 address space switch가 필요하지 않을 수 있다.
• 따라서 process switch보다 thread switch가 가벼울 수 있다.
• 하지만 다른 process의 thread로 넘어가면 address space switch도 필요하다.

Big Picture: User-level Threads

• user-level thread에서는 kernel이 thread를 직접 switching하지 않는다.
• user-level threading library가 thread context switch를 수행한다.
• 이 경우 kernel은 process 단위로만 scheduling한다.
• process 안에서 어떤 user-level thread가 실행될지는 user-level library가 결정한다.
• 따라서 user-level thread context switch는 빠를 수 있다.
• 하지만 kernel이 thread 정보를 모르기 때문에 blocking I/O나 multi-core 활용에서 문제가 생긴다.

OS Classification