스레드 & 동시성

본 자료 정리는 'Operating System Concepts'(Tenth Edition) - Abraham Silberschatz 원서에 출처합니다.
Copyright © 2020 John Wiley & Sons, Inc.

Chapter 4: Threads & Concurrency

• Overview
• Multicore Programming
• Multithreading Models
• Thread Libraries
• Implicit Threading
• Threading issues (프로그래머가 아니라 운영체제가 고려해야 할 사항들)

Objectives (목표)

• 스레드의 기본 구성 요소를 식별하고 스레드와 프로세스를 대조
• 다중 스레드 프로세스 설계의 주요 이점과 주요 과제를 설명
• 스레드 풀, 포크 조인 및 Grand Central Dispatch를 포함하여 암시적 스레딩에 대한 다양한 접근 방식 설명
• Ptherads, Java 및 Windows 스레딩 API를 사용하여 다중 스레드 애플리케이션을 설계

Overview

A thread is a basic unit of CPU utilization.
(스레드는 CPU 이용의 기본 단위이다.)

스레드 구성요소

• 스레드 ID
• 프로그램 카운터 (PC)
• 레지스터 집합
• 스택

스레드는 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 열린 파일이나 신호와 같은 운영체제 자원들을 공유한다.

과거 프로세스는 하나의 제어 스레드만을 가지고 있었지만, 현재는 다수의 제어 스레드(multithreaded)를 가지며 프로세스는 동시에 하나 이상의 작업을 수행할 수 있다.

Single and Multithreaded Processes

Motivation

하나의 응용 프로그램이 여러 개의 비슷한 작업을 처리해야 할 상황에서, 만약 웹 서버가 단일 스레드 프로세스로 작동한다면, 한 번에 하나의 클라이언트만 처리할 수 있게 돼서 매우 긴 시간이 걸리게 된다.

이를 위한 방법으로는, 서버에게 서비스 요청이 들어오면, 프로세스는 그 요청을 수행할 별도 프로세스를 생성하는 것이다.

하지만 프로세스 생성 작업은 매우 많은 시간을 소비하고 많은 자원을 필요로 한다.

따라서 대부분은 프로세스 안에 여러 스레드를 만들어 나가는 것이 더 효율적이다.

(Process creation is heavy-weight while thread creation is light-weight)

Multithreaded Server Architecture

Benefits

• 응답성 (responsiveness) : 프로세스의 일부가 차단되거나 긴 작업을 수행하는 경우 프로그램이 계속 실행하는 것을 허용함으로써, 사용자에 대한 응답성을 증가시킨다.

• 자원 공유 (resource sharing) : 스레드는 프로세스의 리소스를 공유하므로 공유 메모리 또는 메시지 전달보다 쉽다.

• 경제성 (economy) : 스레드는 자신이 속한 프로세스의 자원들을 공유하기 때문에, 스레드를 생성하고 문맥 교환하는 것이 프로세스에서 문맥 교환하는 것 보다더욱 빠르고 효율적이다.

• 규모 적응성 (scalability) : 다중 프로세서 구조에서 각각의 스레드는 다른 프로세서에서 병렬로 수행될 수 있기 때문에 규모 적응성에서 이점을 갖는다.

Multicore Programming

다중 스레드 프로그래밍은 multicore 또는 multiprocessor 시스템과 향상된 동시성을 보다 효율적으로 사용하기 위한 메커니즘을 제공한다.

• 동시성(concurrency) : 하나 이상의 작업을 수행한다.
• 병렬성(parallelism) : 시스템이 동시에 둘 이상의 작업을 수행할 수 있음을 의미한다.

Concurrency vs. Parallelism

Concurrency - 하나 이상의 작업이 모두 다 조금씩 진행 (어디서든 가능)
Parallel - 완전히 동시에 실행 (멀티코어에서 가능)

• Concurrent execution on single-core system

• Parallel execution on a multi-core sysyem

Programming Challenges

프로그래머가 멀티코어 또는 멀티프로세서 시스템을 구현하기 위해서는 다음과 같은 도전과제를 극복해야 한다.

- 태스크 인식 (dividing activities) : 단위로 분할
- 균형 (balance) : 작업량을 균등하게 배분
- 데이터 분리 (data splitting) : 데이터 나누기
- 데이터 종속성 확인 (data dependency)
- 태스팅과 디버깅 (testing and debugging)

Types of Parallelism

• Data parallelism : 동일한 데이터의 하위 집합을 여러 코어에 배포하고 각 코어에서 동일한 작업을 수행한다.
  - (e.g. 100만개의 데이터 더하기 (연산 하나), 각 코어가 동일 연산 수행)

• Task parallelism : 각 스레드가 고유한 작업을 수행하는 여러 코어에 스레드 분산한다.
  - (e.g. 4가지의 다른 종류의 통계연산 실행, data는 동일하지만 각 core마다 다른 연산 수행)

Amdahl's Law

직렬(비병렬) 및 병렬 구성 요소가 모두 있는 애플리케이션에 추가 코어를 추가하여 성능 향상을 식별한다.

• S is serial portion (순차적으로 처리해야되는 부분)
• 1-S - 병렬적으로 처리될 수 있는 부분
• N is processing cores (cpu core의 개수)
• speedup - 최대로 속도향상이 될 수 있는 한계점

(e.g. 응용 프로그램이 75% 병렬, 25% 직렬인 경우 2코어에서 4코어로 이동하면 속도가 1.6배에서 2.28배로 빨라진다.)

N이 무한대에 접근함에 따라 속도 향상은 1/S에 접근한다.
(e.g. 50% 가 serial일 때, N을 무한대로 늘리더라도 최대 속도 향상은 1/0.5 = 2배 이다.)

Amdahl's Law2

응용 프로그램의 직렬 부분은 추가 코어를 추가하여 얻은 성능에 불균형적인 영향을 미친다.

Multithreading Models

• User threads : 커널 위에서 지원되고 user-level 스레드 라이브러리에 의해 커널 지원 없이 관리된다.

  • 세 가지 주요한 스레드 라이브러리: POSIX Pthreads, Windows threads, Java threads

• Kernel threads : 커널에서 직접 지원 및 관리한다.

  • Windows, Linux 및 macOS를 포함한 거의 모든 최신 운영 체제
    -> 커널 스레드 지원

Three multithreading models

• Many-to-One
• One-to-One
• Many-to-Many

Many-to-One

단일 kernel 스레드에 많은 user-level 스레드가 매핑된다.

(-) 하나의 스레드가 차단되면 모두 차단된다.
(-) 한 번에 하나의 스레드만 커널에 있을 수 있으므로 다중 스레드는 multicore 시스템에서 병렬로 실행되지 않을 수 있다.

• 현재 이 모드를 사용하는 시스템은 거의 없다.
  (e.g. Solaris Green Threads)

One-to-One

각 user-level 스레드가 kernel 스레드에 매핑된다.

사용자 수준 스레드를 생성하면 커널 스레드가 생성된다.

(+) 스레드가 차단 시스템 호출을 할 때 다른 스레드가 실행되도록 허용함으로써 Many-to-One 보다 더 많은 동시성을 가진다.
(+) 다중 스레드가 다중 프로세서에서 병렬로 실행될 수 있다.

(-) 오버헤드로 인해 때때로 프로세스당 스레드 수가 제한된다.

• 대부분의 OS가 이 방식을 사용한다.
  (e.g. Windows, Linux)
  

Many-to-Many Model

다수의 user-level 스레드를 더 작거나 같은 수의 커널 스레드로 다중화한다.

(+) OS가 충분한 수의 커널 스레드를 생성할 수 있도록 한다.
(+) 다중 스레드가 다중 프로세서에서 병렬로 실행될 수 있다.
(+) 스레드가 차단 시스템 호출을 만들 때 다른 스레드가 실행되도록 허용한다.

(-) 구현하기 까다롭다.

num(user threads) >= num(kernel threads)

Two-level Model

Many-to-Many 모델의 변형이다.

많은 사용자 수준 스레드를 더 작거나 같은 수의 커널 스레드에 다중화하지만 사용자 수준 스레드를 커널 스레드에 바인딩할 수도 있다.

num(user threads) >= num(kernel threads) && One-to-One model 가능

Thread Libraries

스레드 라이브러리(thread library)는 프로그래머에게 스레드 생성 및 관리를 위한 API를 제공한다.

구현하는 두 가지 주요 방법

• 커널 지원 없이 완전히 사용자 공간에 있는 라이브러리
• OS에서 직접 지원하는 커널 레벨 라이브러리

주된 스레드 라이브러리

• POSIX Pthreads, Windows, Java

Asynchronous vs. synchronous threading

Example:

Pthreads

• 사용자 수준 또는 커널 수준으로 제공될 수 있다.
• 스레드 생성을 위한 POSIX 표준(IEEE 1003.1c) API 및
  동기화
• 코드 구현 x, 명세만 제공

Multithreaded C Program using Pthreads API

-> 전역변수

-> P.T (부모 스레드)

-> C.T (자식 스레드)

Pthreads Code for Joining 10 Threads

Multithreaded C Program using Windows API

-> P.T (부모 스레드)

-> C.T (자식 스레드)

Implicit Threading

다중 코어 처리의 성장에 따라 수백, 수천 개의 스레드를 가진 Application이 등장하게 되었다.

스레딩의 생성과 관리 책임을 프로그래머로부터 컴파일러와 실행시간 라이브러리에게 넘겨주는 암묵적 스레딩(Implicit threading)을 사용하면 멀티 스레딩을 효율적으로 활용할 수 있다.

이 방법은 개발자는 병렬 작업만 실행하면 되고 라이브러리가 세부 사항을 결정하는 것이다.

이는 여러가지 방법이 있다.

• Thread Pools
• Fork Join
• OpenMP
• Grand Central Dispatch
• Intel Thread Building Blocks (TBB)

Thread pools

웹 서버는 요청을 받을 때마다 새로운 스레드를 만들어 준다. 하지만 이는 여러 문제가 있다.

하나의 웹 서버에 수 천개의 스레드를 생성하고 종료하는데에는 오버헤드가 발생한다. 또한 메모리 고갈 문제가 발생한다.

이에 대한 해결 방안이 작업을 기다리는 풀에 여러 스레드를 미리 만들어 두는 것이다.

스레드 풀의 장점

(+) 일반적으로 새 스레드를 만드는 것보다 기존 스레드로 요청을 처리하는 것이 약간 빠르다.
(+) 스레드 풀은 임의 시각에 존재할 스레드 개수에 제한을 둔다. 이러한 제한은 많은 수의 스레드를 병렬 처리할 수 없는 시스템에 도움이 된다.
(+) 태스크를 생성하는 방법을 태스크로부터 분리하면 태스크의 실행을 유연하게 할 수 있다.

Java Thread Pools

• Java.util.concurrent package
  • Single thread executor - newSingleThreadExecutor()
    -스레드 하나만 가지는 pool 생성
  • Fixed thread executor - newFixedThreadPool(int size)
    -size 만큼의 스레드를 가지는 pool 생성
  • Cached thread executor - newCachedThreadPool()
    -무제한의 스레드를 가지는 pool 생성

Fork Join

부모 스레드는 자식 스레드를 생성(fork)한 다음 대기 및 조인(join)

그러나 스레드는 포크 단계에서 직접 구성되지 않고 병렬 작업이 지정된다.

라이브러리는 생성된 스레드 수를 관리하고 스레드에 작업을 할당한다.

스레드 풀의 동기 버전이다.

Fork Join in Java

재귀 분할 정복 알고리즘을 위해 설계된 Fork-join 라이브러리
(e.g. Quicksort, Mergesort)

하나의 큰 문제를 나누어 병렬 실행한다. 작업을 더 이상 나눌 수 없게되면 fork를 시켰던 부모 스레드로 조인해나가며 전체 문제를 해결한다.

Fork Join in Java2

OpenMP

C, C++, FORTRAN용 컴파일러 지시문 및 API 세트이다.

공유 메모리 환경에서 병렬 프로그래밍을 위한 지원을 제공한다.

병렬 영역(parallel regions)을 병렬로 실행할 수 있는 코드 블록으로 식별한다.

• 코어 수 만큼 스레드를 생성한다.

Grand Central Dispatch

• macOS 및 iOS 운영 체제용 Apple 기술이다.

• 개발자가 병렬로 실행할 코드(작업) 섹션을 식별할 수 있도록 하는 런타임 라이브러리, API, 언어 확장의 조합이다.

• dispatch queue에 작업을 배치한다.

  • queue에서 제거될 때 스레드 풀의 사용 가능한 스레드에 할당된다.

• Task expression

  • Block is in "^{}" (병렬로 실행할 부분을 나타냄)
  • Swift closure

Threading Issues

• fork() 및 exec() 시스템 호출의 의미
• Signal handling
  • 동기/비동기
• 타켓 스레드의 스레드 취소
  • 비동기 또는 지연되는 경우
• Thread-local storage
• Scheduler 활성화

Semantics of fork() and exec()

• fork()는 호출 스레드만 복제하는가 아니면 모든 스레드를 복제하는가?
  - 일부 UNIX 시스템에는 두 가지 버전이 있다.

• exec()는 일반적으로 정상적으로 작동한다 .
  - 모든 스레드를 포함하여 실행 중인 프로세스를 교체한다.

Signal Handling

신호 (signal)는 UNIX 시스템에서 특정 이벤트가 발생했음을 프로세스에 알리기 위해 사용된다.

신호처리기 (signal handler)는 신호를 처리하는 데 사용된다.

1) 신호는 특정 이벤트에 의해 생성된다.
2) 신호가 프로세스에 전달된다.
3) 신호는 두 가지 신호 처리기 중 하나에 의해 처리된다.
- (default / user-defined)

모든 신호에는 신호를 처리할 때 커널이 실행하는 기본 핸들러 (default handler)가 있다.

• 사용자 정의 신호 처리기 (User-defined signal handler)는 기본값을 재정의할 수 있다.
• 단일 스레드의 경우 신호가 프로세스로 전달된다.

Signal Handling 2

다중 스레드의 경우 신호를 어디로 전달해야 하는가?

• 신호가 적용되는 스레드에 신호 전달

• 프로세스의 모든 스레드에 신호 전달
  (e.g. 프로그램이 예기치 않게 종료된 경우)

• 프로세스의 특정 스레드에 신호 전달

• 프로세스에 대한 모든 신호를 수신할 특정 스레드 할당

Thread Cancellation

스레드가 완료되기 전에 종료하는 것이다. (강제종료)

취소되는 스레드는 타켓 스레드이다.

두 가지 일반적인 접근 방식

• 비동기 취소 (asynchronous cancellation) : 하나의 스레드가 타겟 스레드를 즉시 종료한다.
• 연기된 취소 (deferred cancellation) : 타켓 스레드가 종료해야 하는지 주기적으로 확인한다.
  (terminate 할 수 있는 상황인지 주기적으로 check)

Thread Cancellation 2

pthread_cancel() 호출은 취소만 요청하지만 실제 취소는 스레드 상태에 따라 다르다.

스레드에 취소가 비활성화(disabled)되어 있으면 스레드가 활성화(enabled)할 때까지 취소가 보류 상태로 유지된다.

default type은 deferred이다.

• 스레드가 취소 지점 (cancellation point)에 도달한 경우에만 취소가 발생한다.
  • 즉, pthread_testcancel()
  • 그 후 정리 처리기(cleanup handler)가 호출된다.

Thread-Local Storage

스레드 로컬 저장소(Thread-Local Storage)를 사용하면 각 스레드가 자체 데이터 복사본을 가질 수 있다.

스레드 생성 프로세스를 제어할 수 없을 때 유용하다. (e.g. 스레드 풀을 사용하는 경우)
지역 변수와 다르다

• 단일 함수 호출 중에만 표시되는 지역 변수
• 함수 호출에서 볼 수 있는 TLS

static 데이터와 유사하다. 그러나 TLS는 각 스레드마다 고유하다.

Scheduler Activations

M:M 및 Two-level 모델 모두 응용 프로그램에 할당된 적절한 수의 커널 스레드를 유지하기 위해 통신이 필요하다.

일반적으로 사용자 스레드와 커널 스레드 간에 중간 데이터 구조를 사용한다.

• light weight process(LWP)
  • 프로세스가 사용자 스레드를 실행하도록 예약할 수 있는 가상 프로세서이다.
  • 커널 마다 각 LMP가 달려있다.

스케줄러 활성화(scheduler activation)는 *upcall을 제공한다.
-*upcall: 커널에서 스레드 라이브러리의 upcall handler로의 통신 메커니즘

이 통신을 통해 애플리케이션은 올바른 수의 커널 스레드를 유지할 수 있다.

수정해야될 사항이 있거나 잘못 번역된 문장이 있을경우 댓글로 알려주세요 :)