[Operating System] Chapter 4: Threads

Motivation

 

현대의 응용 프로그램들은 대부분 multithreaded환경입니다. Process를 생성하거나 Process를 기준으로 context switch를 하면 Process자체가 너무 큰 단위이다보니 overhead가 발생합니다. 하지만 Thread의 생성이나 context switch는 이에 비해 가볍게 수행할 수 있어서 Thread가 중요해졌습니다. *kernel들은 일반적으로 multithreaded입니다.

 

Multithreaded Server Architecture

 

multithread환경을 이용한 서버 구조는 다양한 사용자의 요청들을 비동기적으로 처리할 수 있어 효율성이 올라갑니다:

Multithreaded Server Architecture

 

만약 single-thread 환경이었다면, server는 request를 받아들인 후 client가 socket을 보내기 전까지는 다른 신호를 받을 수 없습니다. *현재 wait()상태에 있기 때문에. 하지만 request를 받아들인 후 thread를 생성하여 client의 socket을 thread가 기다리게 하고, server는 다른 client의 request를 기다리게 하면 효율성이 더욱 올라갈 것입니다.

 

Benefits

 

multithread를 사용하면 다음의 이점들이 있습니다:

• Responsiveness: 프로세스의 어느 한 부분이 block을 당해도, 다른 중요한 부분들을 계속 실행할 수 있습니다. 앞선 multithreaded server architecture가 그 예시입니다.
• Resource Sharing: thread들은 process의 자원들을 shared memory나 message passing보다 더욱 쉽게 접근할 수 있습니다. *같은 PCB에 존재하니까, static이나 global변수에 쉽게 접근할 수 있습니다.
• Economy: thread의 생성과 switching은 process의 생성과 switching보다 더 경제적입니다. *PCB에 저장되는 정보들의 양이 thread보다는 훨씬 많기 때문에 switching이나 creation에 overhead가 큽니다.
• Scalability: multithreaded환경은 multiprocessor구조의 장점을 잘 살릴 수 있습니다. *만약 1-process, 1-thread환경에서는 multiprocessor의 이점을 사용할 수 없는 반면, 1-process여도 multi-thread환경이라면 multiprocessor의 이점을 사용할 수 있습니다.

 

Multicore Programming

 

Multicore 혹은 Multiprocessor system은 프로그래머에게 다음과 같은 challenges를 부여합니다:

• Diviing activities
• Balance
• Data splitting
• Data dependency
• Testing and debugging

Parallelism(병렬화)는 두 개 이상의 태스크를 동시에 실행하는 시스템을 말하며, Concurrency(동시성)은 두 개 이상의 태스크를 scheduler를 통해 하나의 processor에서도 실행할 수 있게 하는 것입니다.

 

Parallelism에는 두 가지 종류가 있습니다. (1) Data Parallelism은 같은 태스크를 데이터를 쪼개서 수행함으로써 효율을 늘리는 병렬화를 말합니다. (2) Task Parallelism은 서로 다른 태스크를 수행하는 것을 말합니다.

 

thread의 개수가 그냥 많다고 해서 무조건 성능이 좋아지는 것을 아닙니다. 이를 뒷받침하기 위한 구조적 지원이 필요하며, # thread가 증가하면 이를 관리하기 위한 비용도 늘어날 수 있습니다. 그래서 일반적으로 core당 지원하는 thread의 개수가 정해져있습니다.

Concurrency vs. Parallelism

Single and Multithreaded Processes

 

Amdahl's Law

 

amdahl's law는 서로 독립적인 부분의 성능 향상이 이뤄질 때 총 성능 향상의 비율을 구하는 공식입니다. 예를 들어, 동시에 처리할 수 있는 application이 75%, 동시에 처리하지 않는 serial한 application이 25%일 때, N개로 프로세서의 개수를 늘리면 나타나는 speed up은 다음과 같습니다:

Amdahl's Law

 

이에 따르면 N이 무한히 커질수록, 즉 processor의 개수가 매우 많이 늘어나도 성능 향상의 upper bound는 1/S입니다.

 

User Threads and Kernel Threads

 

Thread에는 두 가지 종류가 존재합니다. (1) User thread는 user-level thread library에서 관리하는 thread입니다. 대표적인 libraries로 POSIX Pthread, Window threads, Java threads 등이 있습니다. (2) Kernel thread는 kernel에 의해 관리되는 thread로 대부분의 OS들이 kernel thread를 관리합니다.

 

Multithreading Models

 

이 User thread와 Kernel thread와의 관계에 대한 모델은 다음과 같습니다:

• Many-to-One
• One-to-One
• Many-to-Many
• Two level model

 

Many-to-One

 

이는 하나의 user thread와 하나의 kernel thread가 매핑된 경우를 말합니다. 일반적으로 os 스케쥴링의 단위는 kernel thread입니다. 그렇기 때문에 kernel thread가 block되면 그에 연결된 모든 user threads들이 block되는 것입니다. 이 단점은 Many-to-One 모델에서 드러나는데,

Many-to-One

 

만약 user thread들 중 하나가 wait()명령이나 I/O 작업을 수행해서 block상태에 들어갔다면, 그에 해당하는 kernel thread가 block 상태에 들어가는 것이고, 해당 kernel thread에 연결된 다른 3개의 user thread들도 block이 되는 것입니다. 또한 user thread들이 parallel하게 동작하지 않는다는 단점도 있습니다. kernel thread가 스케쥴의 단위이기 때문에 해당 kernel thread에 붙어있는 user thread들은 동시에 병렬적으로 처리될 수 없는 것입니다.

 

One-to-One

 

각각의 user thread들은 각각의 kernel thread들과 1:1로 연결됩니다. 이는 앞서 말했던 Many-to-One의 단점((1) 하나가 block되면 다른 user thread들도 block, (2) 병렬성 문제)들을 해결합니다. 하지만 user thread가 늘어나는 족족 kernel thread도 늘어나기 때문에 많아지는 thread로 인한 관리 overhead도 무시할 수 없는 문제가 됩니다. 이는 Windows, Linux등의 OS에서 사용됩니다.

One-to-One

 

Many-to-Many

 

여러 개의 User thread들과 여러 개의 kernel thread간의 연결을 허용합니다. 이는 앞서 봤던 두 모델의 단점을 모두 해결합니다. 하지만 이는 user thread들과 kernel thread들간의 실질적인 연결, 매핑을 어떻게 하느냐가 challenge입니다. *어떤 thread들을 kernel thread들에 매핑할까..?

Many-to-Many

 

Two-level model

 

many-to-many 모델과 유사하지만, one-to-one 관계도 허용합니다.

Two-level model

 

Thread Libraries

 

Thread Library는 프로그래머에게 thread의 관리나 생성에 대한 API를 제공해줍니다. thread library를 구현하는 데는 user space에서 온전히 사용가능하게 구현하는 방법과, OS의 지원하에 kernel-level에서 구현하는 방법이 있습니다. 각각 user thread와 kernel thread를 만들 수 있는 API를 제공할 수 있습니다.

 

Pthreads

 

Pthreads는 uesr-level과 kernel-level 모두를 지원합니다. Pthreads는 POSIX thread의 약자로, POSIX는 IEEE에 규정된 명세입니다. 그렇기 때문에 그 명세를 따르는 thread library들을 POSIX라고 부르는 것입니다. 즉 POSIX Standard는 Specification이지 Implementation이 아닙니다.

 

대부분의 UNIX OS에서는 Pthreads를 사용합니다.

 

Pthreads Example

Pthreads Example

 

Windows Multithreaded C Program

Windows Multithreaded C Program

 

*Java threads는 JVM에 의해 관리되며, 이는 OS에 의해 제공되는 thread의 구현입니다. 이는 Thread class를 상속받거나, Runnable interface를 구현하므로써 생성합니다.

Java Multithreaded Program

Java Multithreaded Program

 

Implicit Threading

 

thread를 사용하는 수가 늘어남에 따라 프로그래머가 많은 수의 thread들을 관리하기가 힘들어졌습니다. 이에 compiler와 run-time libraries들이 알아서 thread들을 생성하고 관리하는 것을 implicit threading이라고 부릅니다. 이에 Thread Pools, OpenMP, Grand Central Dispatch와 같은 방법들이 존재합니다.

 

Threading Issues

 

Thread를 이용할 때 발생할 수 있는 issues들에 대해 살펴봅니다.

 

Semantics of fork() and exec()

 

만약 multithreaded환경의 process를 fork()한다면, 새롭게 생성되는 process도 multithreaded환경인가? 이에 UNIX 기반 OS들은 두 가지 fork()를 제안함으로써 해결합니다.

 

exec()의 경우는 간단합니다. 기존의 process가 multithreaded 이건 아니건 새로운 process로 바뀌는 것이기 때문에 그냥 초기화되어 single-threaded환경이 됩니다.

 

Signal Handling

 

signal은 UNIX system에서 프로세스에게 어떤 이벤트가 일어났음을 알려주는데 사용됩니다. signal handler:

1. Signal is generated by particular event
2. Signal is delivered to a process
3. Signal is handled by one of two signal handlers:
   1. default
   2. user-defined

 

이때, 모든 signal들은 기본적으로 default handler에 의해 처리됩니다. 하지만 user-defined signal handler를 설정하면 default를 덮어쓰기가 가능합니다. 이때 multithreaded 환경의 process에게 signal이 간다면 어떤 thread가 이를 처리해야할까요?:

• signal을 받은 thread에게 전달한다.
• process에 존재하는 모든 threads들에게 전달한다.
• process의 특정한 thread 하나에 전달한다.
• signal을 보낼 때 thread specific하게 보내게 한다.

 

Thread Cancellation

 

thread가 종료되지 않은 상태에서 강제로 종료할 때 (이때 종료되는 thread를 target thread라고 부릅니다):

• Asynchronous cancellation은 target thread가 cancellation 명령을 받자마자 종료합니다.
• Deffered cancellation은 target thread가 종료되어도 되는 때까지 명령을 수행하다가 종료가 가능하면 그때 종료합니다.
• 이 두 cancellation은 애초에 thread가 cancellation을 허용할 때의 얘기입니다.

Thread Cancellation

 

*위 표에서 State가 Disable인 thread가 cancellation을 허용하지 않은 thread입니다.

OS마다 다르지만, Disable state인 thread에 cancellation을 요청하면 그 명령은 pending되어 저장됩니다.

 

deffered mode는 해당 thread가 cancellation point에 도달하면 그 thread를 종료합니다 (i.e. pthread_testcancel()). 그 후 cleanup handler를 호출합니다.

 

Thread-Local Storage

 

Thread-local storage (TLS)는 thread만의 global 혹은 static 변수라고 생각하면 편합니다. 일반적으로 thread안에서 사용하는 전역변수나 static 변수들은 thread들이 공통으로 접근할 수 있는 공간에 저장됩니다. 그렇기에 thread안에서 여러 함수들에서 사용할 수 있도록 전역변수나 static변수를 만들고 싶지만, 다른 thread들이 접근할 수 없도록 하고 싶다면 TLS을 사용하면 됩니다.

 

Scheduler Activations

 

M:M이나 two-level model의 경우 user thread와 kernel thread간의 실질적인 매핑을 설정하는 것이 중요한 과제입니다. 이를 위해 user thread와 kernel thread사이에 lightweight process (LWP)가 존재합니다. LWP는 kernel thread과 1:1 매핑되는 process로 schedule과 관련된 정보를 upcall을 통해 user threads, 혹은 thread library에 전달합니다. 그렇다면 thread library는 그 상황에 맞게, schedule 상황에 맞게 user thread들을 LWP, kernel thread에 새롭게 할당합니다. 이런 user thread와 kenel thread들 간의 소통을 통해 더욱 효율적인 매핑이 가능해집니다. *참고로 user thread에게 LWP는 하나의 processor처럼 보일 수 있습니다. schedule에 대한 정보를 알려주니까...

Scheduler Activations