14 October 2022 / OS

Threads and Concurrency

Thread와 Concurrency에 대한 개념을 정리하였다.

Overview

Thread는 CPU 스케줄링, 또는 utilization의 기본 단위이다.

각 쓰레드는 Thread ID(TID), Program Counter(PC), register set, stack으로 구성되어 있다.

동일한 프로세스에 속하는 다른 쓰레드들과 code, data section 및 file, signal 등 다른 리소스들을 공유한다.

대부분의 현대 컴퓨터 또는 모바일 기기에서 실행되는 소프트웨어 어플리케이션은 multithreaded 이다.

Examples

Web Server

Multithreaded의 활용 예로는 웹 서버가 있다. 다수의 클라이언트가 생성하는 여러 요청을 처리하는 데에 있어, multithreaded인 서버 프로세스는 클라이언트 요청을 listen 하는 새 thread를 생성하여 처리한다. 이러한 방식은 single-threaded 프로세스가 새 프로세스를 생성하여 처리하는 방식보다 효율적이다.

Multithreaded인 웹 서버의 기본적인 동작 방식은 다음과 같다.

클라이언트 요청을 listen하는 thread를 생성한다.
클라이언트가 요청을 보낸다.
요청을 처리하는 thread를 새로 생성한다.
추가적인 클라이언트 요청을 계속해서 listening한다.

Linux Kernel

대부분의 OS 커널도 multithreaded이다.

Linux의 경우, 각 쓰레드는 디바이스 관리, 메모리 관리, interrupt handling 등의 작업을 수행한다.

ps -ef 명령어로 리눅스 시스템에서 실행 중인 커널 thread들을 볼 수 있다.

kthreadd 라는 커널 thread는 다른 모든 커널 thread의 parent thread에 해당한다.

Multicore Programming

멀티 코어 시스템에서는 여러 개의 코어가 여러 개의 쓰레드를 동시에 병렬(parallel)로 실행할 수 있다.

싱글 코어 시스템에서는 한 번에 한 개의 쓰레드만 실행되며 다른 쓰레드들과 번갈아가며 실행(interleaved)된다.

parallelism vs concurrency
- parallelism: 여러 개의 쓰레드가 동시에 실행되는 것, 병렬성 O
- concurrency: 모든 task가 진행되도록 하여 둘 이상의 task를 지원; 병렬성 X

싱글 코어 시스템에서 실행되는 프로그램은 concurrent 할 수 있지만 parallel하지는 않다.

Programming Challenges

Identify tasks

애플리케이션이 concurrent한 여러 task들로 분리되는 영역을 찾아야 한다. 서로 독립적이라 parallel하게 실행될 수 있는 task들이 이상적이다.
Balance

여러 코어의 작업량이 균등하도록 분배해야 한다.
Data Splitting

task와 마찬가지로 사용되는 데이터도 여러 코어에 분배되어야 한다.
Data Dependency

task가 접근하는 데이터는 task들 사이에 의존성이 있는지 확인해야 한다.

프로그래머는 data dependency를 고려하여 task 실행이 동기화될 수 있도록 보장해야 한다.
Testing and Debugging

병렬 실행되는 프로그램은 싱글 쓰레드 프로그램에 비해 여러 실행 경로가 존재하므로 더 섬세한 테스팅이 필요하다.

Amdahl’s law

프로세서의 코어 수: N

프로그램의 실행에 있어 serial(nonparallel)한 부분의 비율: S

\[speedup \leq\frac{1}{S + \frac{1-S}{N}}\]

N이 무한대로 증가하면, speedup은

\[1/S\]

에 수렴한다.

즉, 코어 개수 증가로 인한 성능 향상은 한계가 있다. 프로그램의 serial portion이 프로그램 실행 속도에 불균형적인 결과를 초래하게 된다.

Data Parallelism, Task Parallelism

여러 개의 코어에 데이터, 혹은 task를 모두 분배할 수 있다.

같은 데이터에 대해 서로 다른 연산을 수행하는 것은 Task parallelism에 해당하고, 서로 다른(분리된) 데이터에 대해 같은 연산을 수행하는 것은 Data parallelism에 해당한다.
둘은 상호 배타적이지 않으며 혼합 가능하다.

Multithreading Models

쓰레드에 대한 지원은 유저 쓰레드 또는 커널 쓰레드에 대해 제공될 수 있다.

유저 쓰레드는 커널 상위에서 커널의 지원 없이 실행되며, System call을 사용하지 않는다. (대신 API 함수 호출)
커널 쓰레드는 OS에 의해 직접 지원, 관리된다.
커널 쓰레드 - 유저 쓰레드 간 관계
1. Many-to-one
2. one-to-one
3. many-to-many

Many-to-one

유저 쓰레드는 여러 개인데 커널 쓰레드는 하나인 경우이다.

한번에 한 쓰레드만 커널에 접근하며 병렬로 수행되지 않는다.

한 쓰레드가 blocking system call을 호출하면 전체 프로세스가 blocked 된다.

멀티 코어의 이점을 활용하지 못하므로 거의 사용되지 않는 모델이다.

One-to-one

유저 쓰레드와 커널 쓰레드가 1:1로 대응된다.

쓰레드가 blocking system call을 하더라도 나머지 쓰레드는 계속 실행 가능하다.

CPU 이용률을 높일 수 있다.

단점

유저 쓰레드 하나당 대응되는 커널 쓰레드가 필요해진다. -> 시스템 부하

Many-to-many

이 모델은 여러 개의 유저 쓰레드를 작거나 같은 개수의 커널 쓰레드로 Multiplexing 해준다. (User-level threads >= Kernel-level threads)

커널 쓰레드의 수는 어플리케이션, 또는 CPU 코어 수 등 하드웨어적 요인에 의해 결정된다.

A Variation to Many-to-many

Two-level model로도 알려져 있다.

기존 Many-to-many 모델과 유사하지만, 추가로 1:1 대응 기능도 지원한다.

구현이 복잡하다.

Effect on Concurrency

One-to-one 모델은 가장 Parallelism이 높지만, 시스템 부하가 가장 크다.

Many-to-many 모델은 개발자가 필요한 만큼 유저 쓰레드를 생성 가능하며 대응되는 커널 쓰레드가 병렬로 작업을 수행할 수 있다. 또한 one-to-one과 마찬가지로, 한 쓰레드가 blocking system call을 해도 커널이 다른 쓰레드를 수행 가능하다. 단 모든 유저 쓰레드에 대응하지는 못 할 수 있다.

코어 개수 증가에 따라 커널 쓰레드 수 제한의 중요도가 감소했다.

따라서 대부분의 OS가 현재 One-to-one 모델을 사용하고 있다.

Thread Libraries

쓰레드 라이브러리는 프로그래머가 쓰레드를 생성/관리할 수 있는 API를 제공한다.

구현 방법
1. 전적으로 유저 레벨에서 지원
  
  커널의 도움 없이 유저 스페이스에서 쓰레드 라이브러리를 제공한다. 함수 호출은 system call이 아닌 로컬 함수 호출에 해당한다.
2. 커널 레벨 라이브러리 제공
  
  API에서의 함수 호출은 system call을 야기한다.
3개의 대표적 쓰레드 라이브러리
1. Pthreads (POSIX Threads) - 유저, 커널 혼합
2. Windows - 커널 레벨
3. Java Thread API - 호스트 OS dependent

쓰레드 생성

Asynchronous Threading

parent는 child 생성 후 자신의 실행을 재개한다.

parent와 child는 동시/독립적으로 실행된다.

독립적이므로, data sharing이 거의 없다.

주로 multithreaded server나, 반응형 UI에 사용된다.
Synchronous Threading

parent는 child 생성 후 자신의 실행을 재개하지 않고, child가 종료될 때까지 기다린다.

child들은 concurrent하게 실행되며 모든 child 종료 후 parent 실행이 재개된다.

자식이 끝나면 join하며 모든 자식들이 parent에 join 해야 parent의 실행이 재개된다.

data sharing이 많다. 예) Parent 쓰레드가 자식들의 계산 결과를 취합

C에서 main() 함수가 실행되면 최초의 단일 쓰레드가 실행된다.

PThreads

C에서는 #include <pthreads.h> 로 사용 가능하다.

pthread_join() 으로 생성한 쓰레드의 종료를 wait할 수 있다.

Windows Threads

C에서 #include <windows.h> 로 사용 가능하다.

Implicit Threading

개발자 대신 compiler/run-time library가 쓰레드를 생성/관리한다.

개발자는 parallel task들을 식별만 하면 된다.

Threading Issues

단일 쓰레드 프로그램에 비해 고려해야 할 사항이 많다.

fork() 또는 exec() 호출

모든 쓰레드 복제? 또는 호출이 발생한 쓰레드만 복제?
- UNIX 에서는 두 가지 버전을 모두 제공한다.
  - exec() 가 fork() 이후 바로 호출되면 해당 쓰레드만 복제
  - 그렇지 않으면, 모든 쓰레드를 복제
Signal handling

signal을 어디로 전달할 것인가 -> signal 발생 쓰레드, 모두, 또는 특정 쓰레드?

또는 모든 signal을 전달받는 특정 쓰레드를 지정할 수도 있다.
- Synchronous signals (프로세스 내부 이벤트)
  - 예) Illegal Memory Access, Division by 0
  - Signal을 야기한 동작을 수행한 쓰레드에 전달된다.
- Asynchronous signals (프로세스 외부 이벤트)
  - 예) Ctrl + C로 프로세스 종료
  - 경우에 따라 전달되는 양상이 다르다.
  - 보통 비동기적 signal은 다른 프로세스로 전달된다.
  - 일부 비동기 signal은 모든 쓰레드에 전달되어야 한다.
UNIX의 몇몇 멀티쓰레딩 버전은 accept할 signal과 decline할 signal을 각각 지정 가능하다.

asynchronous signal은 그것을 block하지 않고 있는 쓰레드에만 전달되는 경우도 있다. signal은 한 번만 처리되어야 하므로, signal을 block하지 않은 첫 쓰레드에만 전달된다.

함수에 argument로 tid를 명시하여 해당 쓰레드에만 signal을 전달할 수도 있다.
```
 pthread_kill (pthread_t tid , int signal);
```
- Semantics of signal handling
  - signal 생성 -> 프로세스에 전달 -> 처리
  - Handlers 종류
    1. Default Handler
      - signal에 대한 기본 동작을 커널이 수행
      - 예) SIGINT -> 프로세스 종료
    2. User-defined Handler
      - 기본 동작을 무시하고 유저가 정의한 동작을 수행하도록 할 수 있다.
쓰레드 취소 처리
- Asynchronous cancellation (강제 종료), deffered cancellation (스스로 종료)
- 공유 자원을 update하다가 쓰레드 종료될 경우의 처리?
- 예) 작업 완료되면 강제 종료, 유저가 버튼을 누르면 종료
- 삭제 대상 쓰레드: Target thread
- Asynchronus Cancellation
  - 다른 프로세스에 의해 즉시 종료됨
  - 자원 할당된 상태거나, 공유 데이터를 갱신 중 취소되는 경우 문제 발생 가능
  - 필요한 시스템 자원이 회수되지 않을 수 있음
- Deferred(지연된) Cancellation
  - 타겟 쓰레드가 스스로 종료 여부를 판단함, 순차적 종료 가능
  - target thread가 취소 여부를 결정하는 flag 검사 후에만 취소가 일어남
Thread-Local Storage (TLS)

쓰레드들은 기본적으로 데이터를 공유한다.

그러나, 쓰레드가 자신만의 자원을 필요로 하는 경우가 있다.

지역 변수와 혼동할 수 있으나, 지역 변수와는 달리 전체 함수 scope에서 사용 가능하다.

쓰레드별로 고유한 static data로 볼 수 있다.
Scheduler Activations

고려해야 할 마지막 문제는 커널과 쓰레드 라이브러리 간 통신이다.

Many-to-many 와 Two-level models 에서 필요하다.

많은 시스템이 유저와 커널 쓰레드 사이에 Lightweight Process (LWP)를 두어, 커널 쓰레드의 수를 동적으로 조절한다.

유저 쓰레드의 입장에서는 LWP가 유저 쓰레드를 스케쥴링하는 Virtual processor로 보인다.

어플리케이션은 경우에 따라 여러 개의 LWP를 필요로 할 수 있다(특히, I/O 오퍼레이션이 많이 일어나는 어플리케이션의 경우).

커널이 어플리케이션에게 LWP를 할당한다.

예) 5개의 다른 파일을 read하는 application -> 5개의 LWP 필요
- upcall
  
  커널에서 LWP 방향으로 전달되는 이벤트 알림이다. 어플리케이션이 LWP를 통해 유저 쓰레드를 스케쥴링하므로, 커널은 LWP를 통해 어플리케이션에게 특정 이벤트를 알리게 된다.
  
  upcall은 LWP 위에서 실행되는 upcall handler를 통해 처리된다. upcall handler는 반드시 virtual processor에서 실행되어야 한다.
  - Upcall 발생
    
    쓰레드가 block 되어야 하는 상황에서 upcall을 일으키는 이벤트가 발생한다. 커널이 특정 어플리케이션에게 upcall로 알림으로써 최종 block이 발생한다.
    1. block이 발생하기 전, 커널은 새로운 LWP를 어플리케이션에게 할당하며, 어플리케이션은 새 LWP에서 upcall handler를 실행한다.
    2. 이후 block이 발생하면 block된 쓰레드의 상태를 저장하고, 사용하던 LWP를 반환한다.
    3. 남는 LWP는 다른 쓰레드를 스케쥴링하는 데에 사용한다.
    4. Block되었던 쓰레드가 기다리던 이벤트가 발생 시, 커널은 다시 LWP를 통해 upcall을 발생시켜 해당 쓰레드에게 계속 실행될 수 있음을 알린다. 이때 커널은 새 LWP를 할당하거나 다른 것에서 선점하여 실행시킨다.