🦖 Operating System Concepts 10th

PART TWO PROCESS MANAGEMENT
Chapter 4 Threads & Concurrency

Threads

💡 Thread

스레드는 CPU 사용(utilization)의 기본 단위다.

• 스레드는 스레드 ID(thread ID), 프로그램 카운터(program counter, PC), 레지스터 집합(register set), 스택(stack)으로 구성된다.
• 스레드는 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 열린 파일이나 신호와 같은 운영체제 자원들을 공유한다.
• 전통적인 프로세스는 하나의 제어 스레드(단일 스레드)를 가지고 있으며, 프로세스가 다수의 제어 스레드(다중 스레드)를 가진다면 프로세스는 동시에 하나 이상의 작업을 수행할 수 있다.

Figure 4.1 Single-threaded and multithreaded processes.

Motivation

애플리케이션은 일반적으로 여러 개의 스레드를 가진 독립적인 프로세스로 구현된다. 다수의 CPU-intensive 작업을 병렬로 처리하며, 멀티 코어 시스템에서 처리 능력을 향상시키도록 설계될 수 있다.

또한 하나의 애플리케이션이 여러 개의 비슷한 작업을 수행할 필요가 있는 상황이 있다. 예를 들어, 웹 서버가 여러 개의 클라이언트로부터 요청을 받는 경우를 살펴보자.

• 만약 웹 서버가 전통적인 단일 스레드 프로세스로 작동한다면, 자신의 단일 프로세스로 한 번에 하나의 클라이언트만 서비스할 수 있게 되어 매우 긴 시간이 소요된다.
• 하나의 해결책은 서버가 요청을 받아들이는 하나의 프로세스로 동작하게 해서, 서버에게 서비스 요청이 들어오면, 프로세스는 그 요청을 수행할 별도의 프로세스를 생성하는 것이다. 하지만 프로세스 생성 작업은 많은 시간과 자원을 필요로 하는 일이라 오버헤드가 크다.
• 대부분은 그렇게 하는 것보다는 프로세스 안에 여러 스레드를 만들어 나가는 것이 더 효율적이다. 웹 서버가 다중 스레드화 되면, 서버는 클라이언트의 요청을 listen 하는 별도의 스레드를 생성한다. 요청이 들어오면 프로세스 대신 스레드를 생성해서 추가적인 요청을 listen 하기 위한 작업을 재개한다.
  

Figure 4.2 Multithreaded server architecture.

Benefits

멀티 스레드 프로그래밍의 이점은 다음과 같은 4가지 큰 카테고리로 나눌 수 있다.

1. Responsiveness. 애플리케이션의 일부분이 block 되거나, 긴 작업을 수행하더라도 프로그램의 수행이 계속되는 것을 허용함으로써, 사용자에 대한 응답성을 증가시킨다.
2. Resource Sharing. 프로세스는 공유 메모리(shared memory)와 메시지 전달(message passing) 기법을 통해서만 자원을 공유할 수 있는 반면, 스레드는 그들이 속한 프로세스의 자원들과 메모리를 공유한다.
3. Economy. 프로세스 생성을 위해 메모리와 자원을 할당하는 것은 비용이 많이 든다. 스레드는 자신이 속한 프로세스의 자원들을 공유하기 때문에, 스레드를 생성하고 문맥 교환하는 것이 더욱 경제적이다. 일반적으로 스레드 생성이 프로세스 생성보다 시간과 메모리를 적게 소비하고, 문맥 교환도 프로세스 사이보다 스레드 사이에서 더 빠르다.
4. Scalability. 멀티 스레드의 이점은 멀티 프로세서 구조에서 더욱 증가할 수 있다. 멀티 프로세서 구조에서는 스레드가 각각의 다른 프로세서(처리기)에서 병렬로 수행될 수 있는 반면, 단일 스레드 프로세스는 프로세서가 아무리 많더라도 오직 한 프로세서에서만 실행된다.

Process vs Thread

	Process	Thread
Definition	프로세스는 실행중인 프로그램이다.	스레드는 프로세스의 세그먼트(CPU 사용의 기본 단위)다.
Lightweight	X	O
Creation/Termination time	⬆️	⬇️
Context Switching	문맥 교환 시간이 더 많이 소요된다.	문맥 교환 시간이 더 적게 소요된다.
Resource	자원을 더 많이 소모한다.	자원을 더 적게 소모한다.
Sharing	프로세스끼리 자원을 공유하지 않으며, 일반적으로 독립적이다.	스레드끼리 데이터와 코드 등의 자원을 공유한다.

Fig. 28.2 Single and Multi- Thread Applications

Multicore Programming

멀티코어란, 단일 컴퓨팅 칩에 여러 컴퓨팅 코어를 배치하는 시스템이며, 각 코어는 운영체제에 별도의 CPU로 보인다. 멀티 스레드 프로그래밍은 이러한 여러 컴퓨팅 코어를 보다 효율적으로 사용하고 동시성(concurrency)을 향상시키는 기법을 제공한다.

• 동시성(Concurrency) — 단일 컴퓨팅 코어가 있는 시스템에서는 처리 코어가 한 번에 하나의 스레드만 실행할 수 있기 때문에 시간이 지남에 따라 스레드의 실행이 인터리브(interleave)된다. concurrent 시스템은 모든 작업이 진행되게 하여 둘 이상의 작업을 지원하며, CPU 스케줄러가 프로세스 간에 빠르게 전환해 각 프로세스가 진행되도록 하여 구현된다.

  Figure 4.3 Concurrent execution on a single-core system.

• 병렬성(Parallelism) — 여러 코어가 있는 시스템에서는 일부 스레드가 병렬로 실행될 수 있다. 병렬 시스템은 둘 이상의 작업을 동시에 수행할 수 있다.

  Figure 4.4 Parallel execution on a multicore system.

Programming Challenges

멀티 코어 시스템으로 발전하는 트렌드로 인해, 운영체제 설계자는 여러 코어를 활용하여 병렬 수행할 수 있도록 스케줄링 알고리즘을 개발해야 하고, 애플리케이션 프로그래머는 기존 프로그램을 멀티 스레드를 사용하도록 수정하고 멀티 스레드 프로그램을 설계해야 하는 도전 과제에 당면해 있다.

일반적으로 멀티 코어 시스템을 위해 프로그래밍에는 다섯 개의 극복해야 할 도전 과제가 있다.

1. 테스크 인식(Identifying tasks) — 애플리케이션을 분석하여 독립된 동시성(concurrent) 태스크로 나눌 수 있어야 한다. 이상적으로 태스크는 서로 독립적이고 개별 코어에서 병렬 실행될 수 있어야 한다.
2. 균형(Balance) — 병렬로 실행될 수 있는 태스크를 찾은 후, 균등한 기여도로 작업할 수 있도록 나눠야 한다.
3. 데이터 분리(Data splitting) — 애플리케이션이 독립된 태스크로 나누어지는 것처럼, 태스크가 접근하고 조작하는 데이터 또한 개별 코어에서 사용할 수 있도록 나누어져야 한다.
4. 데이터 종속성(Data dependency) — 태스크가 접근하는 데이터는 둘 이상의 태스크 사이에 종속성이 없는지 검토되어야 한다. 종속적인 경우에는 태스크의 수행을 잘 동기화해야 한다.
5. 테스팅 및 디버깅(Testing and debugging) — 프로그램이 멀티코어에서 병렬로 실행될 때, 다양한 실행 경로가 존재할 수 있으므로, 단일 스레드 애플리케이션을 테스팅하고 디버깅하는 것보다 훨씬 어렵다.

Types of Parallelism

일반적으로 데이터 병렬 실행과 태스크 병렬 실행의 두 가지 유형이 존재한다.

Data Parallelism

데이터 병렬 실행은 동일한 데이터의 부분집합을 다수의 컴퓨팅 코어에 분배한 뒤 각 코어에서 동일한 연산을 실행하는 데 초점을 맞춘다.

Task Parallelism

태스크 병렬 실행은 데이터가 아니라 태스크(스레드)를 다수의 코어에 분배한다. 각 스레드는 고유의 연산을 실행한다. 다른 스레드들이 동일한 데이터에 대해 연산을 실행할 수 있고, 서로 다른 데이터에 연산을 실행할 수도 있다.

Figure 4.5 Data and task parallelism.

기본적으로 데이터 병렬 처리에는 여러 코어에 데이터를 분배하는 것이 포함되고, 태스크 병렬 처리에는 여러 코어에 태스크를 분배하는 것이 포함된다. 그러나 데이터와 태스크 병렬 처리는 상호 배타적이지 않으며 실제로 애플리케이션은 이 두 가지 전략을 혼합하여 사용할 수 있다.

💡 Amdahl’s Law

암달의 법칙은 순차(serial) 작업과 병렬 작업으로 이루어진 애플리케이션에 컴퓨팅 코어를 추가했을 때 얻을 수 있는 잠재적인 성능 이득을 나타내는 공식이다. $N$ 개의 처리 코어를 가진 시스템에서 실행되는 응용 중 반드시 순차적으로 실행되어야만 하는 구성요소를 $S$ 라고 하면 이 공식은 다음과 같이 표현된다.

$speedup$ ≤ $\frac {1} {S+\frac {(1-s)} {N}}$

$N$ 이 무한대로 가까워지면 속도는 $1/S$ 에 수렴한다. 순차 작업이 차지하는 비율이 코어를 추가해서 얻을 수 있는 성능 향상에 불균형적인 영향을 미친다.

Multithreading Models

사용자 스레드(user threads)를 위한 지원은 사용자 수준에서, 커널 스레드(kernel threads)를 위한 지원은 커널 수준에서 제공된다.

• 사용자 스레드 — 커널 위에서(without kernel support) 관리된다.
• 커널 스레드 — 운영체제에 의해(by the operating system) 직접 지원되고 관리된다.

궁극적으로 사용자 스레드와 커널 스레드는 어떤 연관 관계가 존재해야 한다. 이 연관 관계를 확립하는 세 가지 일반적인 방법으로 다대일, 일대일, 다대다 모델이 있다.

Figure 4.6 User and kernel threads.

Many-to-One Model

다대일 모델은 많은 사용자 수준 스레드를 하나의 커널 스레드로 매핑한다.

Figure 4.7 Many-to-one model.

• 스레드 관리는 사용자 공간의 스레드 라이브러리에 의해 행해진다.
• 한 스레드가 blocking 시스템 콜을 할 경우, 전체 프로세스가 block 된다.
• 한 번에 하나의 스레드만이 커널에 접근할 수 있기 때문에, 멀티 스레드가 멀티코어 시스템에서 병렬로 실행될 수 없다.

다중 처리 코어가 대부분의 컴퓨터 시스템에서 표준이 되었고, 다중 처리 코어의 이점을 살릴 수 없기 때문에 이 모델을 사용 중인 시스템은 거의 존재하지 않는다.

One-to-One Model

일대일 모델은 각 사용자 스레드를 각각 하나의 커널 스레드로 매핑한다.

Figure 4.8 One-to-one model.

• 하나의 스레드가 blocking 시스템 콜을 호출하더라도 다른 스레드가 실행될 수 있기 때문에 다대일 모델보다 더 많은 병렬성을 제공한다.
• 멀티 프로세서에서 멀티 스레드가 병렬로 수행되는 것을 허용한다.
• 이 모델의 유일한 단점은 사용자 스레드를 만들려면 해당 커널 스레드를 만들어야 하며 많은 수의 커널 스레드가 시스템 성능에 부담을 줄 수 있다는 것이다.

Linux와 Windows 운영체제 제품군은 일대일 모델을 구현한다.

Many-to-Many Model

다대다 모델은 여러 개의 사용자 수준 스레드를 그보다 작은 수, 혹은 같은 수의 커널 스레드로 멀티플렉스 한다.

Figure 4.9 Many-to-many model.

• 스레드가 blocking 시스템 콜을 발생시켰을 때, 커널이 다른 스레드의 수행을 스케줄 할 수 있다.
• 개발자는 필요한 만큼 많은 사용자 수준 스레드를 생성할 수 있고, 상응하는 커널 스레드가 멀티 프로세서에서 병렬로 수행될 수 있다.
  다대일 모델은 개발자가 원하는 만큼의 사용자 수준 스레드를 생성하도록 허용하지만, 커널은 한 번에 하나의 커널 스레드만 스케줄 할 수 있기 때문에 진정한 병렬 실행이 불가능하다. 또한 일대일 모델은 더 많은 concurrent 실행을 제공하지만, 개발자가 한 애플리케이션 내에 너무 많은 스레드를 생성하지 않도록 주의해야 한다. 다대다 모델은 이러한 두 가지의 단점들을 어느 정도 해결했다.
  
• two-level model이라고 불리기도 하는 다대다 모델의 변형은 많은 사용자 스레드를 적거나 같은 수의 커널 스레드로 멀티플렉스 시킬뿐 아니라 한 사용자 스레드가 하나의 커널 스레드에만 연관되는 것을 허용한다.

  Figure 4.10 Two-level model.

다대다 모델은 실제로 구현하기가 어렵고, 대부분의 시스템에서 처리 코어 수가 증가함에 따라 커널 스레드 수를 제한하는 것의 중요성이 줄어들었다. 결과적으로 대부분의 운영체제는 이제 일대일 모델을 사용한다.

Implicit Threading

멀티 코어 처리의 성장에 따라 수천 개의 스레드를 가진 애플리케이션이 등장하게 되면서, 프로그래머는 Programming Challenges 뿐 아니라 추가 난관을 극복해야 한다.

이러한 어려움을 극복하고 동시성 및 병렬 애플리케이션 설계를 도와주는 한 가지 방법은 스레딩의 생성과 관리 책임을 애플리케이션 개발자로부터 컴파일러와 런타임 라이브러리에게 넘겨주는 것(transfer the difficulty)이다. 암묵적 스레딩(implicit threading)이라고 불리는 이 전략은 점점 널리 사용되고 있다.

암묵적 스레딩에서 애플리케이션 개발자가 병렬로 실행할 수 있는 태스크—not threads—를 식별해야 한다. 태스크는 일반적으로 함수로 작성되며, 런타임 라이브러리는 일반적으로 Many-to-Many Model 을 사용하여 별도의 스레드에 매핑된다. 이 방법의 장점은 개발자는 병렬 작업만 식별하면 되고 라이브러리가 스레드 생성 및 관리에 대한 특정 세부 사항을 결정한다는 것이다.

Thread Pools

매 요청마다 새로운 스레드를 만들어주는 멀티 스레드 서버는 여러 문제를 갖고 있다.

1. 서비스할 때마다 스레드를 생성하는 시간이 소요된다. 심지어 이 일만 끝나면 바로 폐기될 스레드다.
2. 모든 요청마다 새 스레드를 만들어서 서비스하다보면, 시스템에서 동시에 실행할 수 있는 최대 스레드 수의 한계를 정해야 한다. 스레드를 무한정 만들면 언젠가는 CPU 시간, 메모리 공간 같은 시스템 자원이 고갈된다.

이러한 문제들을 해결해 줄 수 있는 방법의 하나가 스레드 풀(thread pool)이다.

스레드 풀의 기본 아이디어는 프로세스를 시작할 때 아예 일정한 수의 스레드들을 미리 풀로 만들어두고, 이 스레드들은 작업을 기다리는 것이다.

서버는 스레드를 생성하지 않고 요청을 받으면 대신 스레드 풀에 제출하고 추가 요청 대기를 재개한다. 풀에 사용 가능한 스레드가 있으면 깨어나고 요청이 즉시 서비스된다. 풀에 사용 가능한 스레드가 없으면 사용 가능한 스레드가 생길 때까지 작업이 대기된다.

💡 브라우저의 스레드 풀과 멀티스레딩 지원

자바스크립트는 싱글 스레드로 동작하지만, 브라우저는 스레드 풀과 Web Worker를 통해 멀티스레딩을 지원한다. 이는 무거운 연산이나 블로킹 I/O 작업을 메인 스레드가 아닌 백그라운드 스레드에서 처리해 UI 반응성을 유지하기 위함이다. 스레드 풀에서 처리된 작업은 이벤트 루프(Event Loop)를 통해 결과를 메인 스레드로 전달된다.

스레드 풀(Thread Pool)은 물리 스레드와 Task Queue로 구성되며, Chrome의 경우 base::ThreadPoolInstance가 이를 관리한다. 개발자는 직접 스레드를 생성하지 않고 Task Runner를 사용해 작업을 전송한다.

Cf. Chromium Docs - Threading and Tasks in Chrome

Fork Join

fork-join 메소드를 사용하면 메인 부모 스레드가 하나 이상의 자식 스레드를 생성($fork$)한 다음 자식의 종료를 기다린 후 $join$하고 그 시점부터 자식의 결과를 확인하고 결합할 수 있다. 이 동기식 모델은 종종 명시적 스레드 생성이라고 특징지어지지만 암묵적 스레딩에도 사용될 수 있다. 후자의 상황에서, fork 단계에서는 스레드가 직접 구축되지 않고 대신 병렬 작업이 식별된다. 이 fork-join 모델은 라이브러리가 생성할 실제 스레드 수를 결정하는 동기 버전의 스레드 풀이다.

OpenMP

OpenMP는 C, C++ 또는 FORTRAN으로 작성된 API와 컴파일러 지시어(directives)의 집합이다. OpenMP는 공유 메모리 환경에서 병렬 프로그래밍을 할 수 있도록 도움을 준다.

OpenMP는 병렬로 실행될 수 있는 블록을 병렬 영역(parallel regions)이라고 부른다. 병렬 영역에 컴파일러 디렉티브를 삽입하면, OpenMP가 런타임 라이브러리에 해당 영역을 병렬로 실행하라고 지시한다.

#include <omp.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
    /* sequential code */
    #pragma omp parallel
    {
    	printf("I am a parallel region.");
    }

    /* sequential code */

    return 0;
}

Grand Central Dispatch

Grand Central Dispatch (GCD)는 macOS 및 iOS 운영체제를 위해 Apple에서 개발한 기술이다. 개발자가 병렬로 실행될 코드 섹션(tasks)을 식별할 수 있도록 하는 런타임 라이브러리, API, 언어 확장(extensions)의 조합이다. OpenMP와 마찬가지로 GCD는 스레딩에 대한 대부분의 세부 사항을 관리한다.

GCD는 실행시간 수행을 위해 태스크를 디스패치 큐(dispatch queue)에 넣어서 스케줄 한다. 큐에서 태스크를 제거할 때 관리하는 스레드 풀에서 가용 스레드를 선택하여 태스크를 할당한다. GCD는 직렬(serial)과 병행(concurrent)의 두 가지 유형의 디스패치 큐를 유지한다.

References

• Operating System Concepts 10th
  • PART TWO PROCESS MANAGEMENT
    • Chapter 4 Threads & Concurrency
• 운영체제 공룡책 전공강의 | 주니온 - 인프런
  • 섹션 3. Chapter 4. Thread & Concurrency
    • 07. 쓰레드의 이해: Chapter 4. Thread & Concurrency (Part 1)
    • 08. 멀티쓰레딩: Chapter 4. Thread & Concurrency (Part 2)
• Chromium Docs - Threading and Tasks in Chrome