[OS] Thread

[ Overview ]

지금까지는 프로세스가 single thread of control로 실행하는 것을 전제로 하였다. 즉, 프로세스가 한 번에 하나의 작업만을 수행할 수 있는 것이다. 하지만 프로세스는 multiple therads of control, 즉 하나의 프로세스가 여러 작업을 수행하는 것이 가능하다. 이를 가능하게 하는 것이 바로 thread 이다.

Thread is ...

• lightweight of process (LWP)
• basic unit of CPU utilization
• comprises a therad ID(TID), a program counter, a register set, and a stack

여러 개의 프로세스로 여러 작업을 동시에 수행하는 멀티프로세싱(multiprocessing)으로 CPU의 사용효율을 높일 수 있다. 하나의 프로세스 내에서도 여러 개로 나눠 동시에 하나 이상의 작업을 수행하여 CPU의 사용효율을 높일 수 있다. 하나의 프로세스에서 나누어진 lightweight process를 스레드라고 하며, 하나의 프로세스에서 여러 개의 작업을 수행하는 것을 멀티스레딩(multithreading)이라고 한다.  스레드는 CPU 입장에서 가장 기본적(작은) 점유 단위이며, 각 스레드는 TID, program counter, register set, stack을 가진다. 

 

 

Benefits of Multithreading

• Responsiveness
  : allows continued execution
  프로세스의 일부분이 blocked 되어 있더라도 non-blocking으로 계속 실행할 수 있다. web server와 같은client-server system에서의 멀티스레딩을 예로 들 수 있다. 서버는 클라이언트로부터 요청을 받으면 새로운 스레드를 만들어 그 스레드로 요청을 처리한다. 새로운 스레드가 작업을 수행하기 때문에 서버의 메인 스레드는 클라이언트로부터 끊임 없이 새로운 요청을 받을 수 있게 된다. (클라이언트로부터 받은 요청 개수만큼 스레드를 생성하기 때문에, 스레드 생성 가능한 범위까지만 요청을 받을 수 있다)
• Resurce Sharing
  : threads share resources of process, and it is easier than shared-memory or message-passing
  멀티스레드 프로세스는 하나의 프로세스 내에서 스레드 단위로 나뉘는 것이기 때문에 같은 프로세스 내에 포함된 스레드들은 프로세스의 코드, 데이터, 파일을 공유한다. 멀티 프로세싱에서 두 프로세스가 데이터를 공유해야기 위해서는 shared-memory, message-passing와 같은 방법을 이용하는데(IPC), 멀티 스레딩의 경우 이러한 과정을 거칠 필요가 없다. 
• Economy
  : cheaper than process creation
  멀티프로세싱의 경우 모든 프로세스가 메모리에 로드되어야 한다. 만약 동일한 동작을 수행하는 프로세스가 여러 개라면 비효율적이다. 멀티스레딩의 경우 여러 스레드가 코드를 공유하기 때문에 효율적이다.
  : lower overhead than context switching between processes
  또한 컨텍스트 스위칭에서도 멀티스레딩이 더 효율적이다. 멀티프로세싱과 멀티스레딩 모두 컨텍스트 스위칭을 해야하지만, PCB보다 TCB에 담긴 정보가 더 적기 때문에 스레드 전환이 속도가 더 빠르다.
• Scalability
  : process can take advantage of multiprocessor architectures
  멀티프로세서/멀티코어 시스템에서 여러 개의 코어가 각각 스레드를 동시에 수행할 수 있다. 즉, 병렬 처리가 가능하다

 

(+) 병렬성(parallel) vs 동시성(concurrency)

동시 처리의 경우 여러 개의 작업을 빠르게 번갈아가면서 수행하여 사용자로 하여금 동시에 실행되는 것처럼 보이게 하는 것이다. 병렬 처리의 경우 여러 개의 CPU 코어가 각 스레드를 동시에 실행한다.

 

 

---

[ Multicore Programming ]

멀티코어 시스템에서의 멀티스레딩은 동시성(concurrency)을 더욱 효율적으로 할 수 있다. 4개의 스레드를 수행해야한다고 가정하자. 싱글코어 시스템에서는 하나의 CPU 코어가 4개의 스레드를 time sharing 하며 처리할 것이다. 코어가 4개인 멀티코어 시스템에서는 시분할(time sharing) 할 필요 없이 각 코어가 하나의 스레드를 수행하면 된다. 코어가 2개라면 각 CPU 코어가 2개의 스레드만 시분할로 처리하면 된다.

 

Challenges

멀터코어 시스템은 싱글코어 시스템보다 효율적이지만 복잡하다. 프로그래밍 하는 데에 있어 다음과 같은 challenge를 해결해야 한다.

• Identifying tasks
  : 작업에서 나눌 수 있는 부분을 찾을 수 있어야 한다. 각 부분이 다른 부분에 영향을 미치지 않는 경우에만 나워서 병렬적으로 처리할 수 있다. 예를 들어 150만개 숫자의 합을 구하는 경우 150만개의 숫자를 여러 부분으로 나누어 각 부분에서 합을 병렬적으로 구한 후 합칠 수 있다. 하지만 150만개의 숫자를 정렬해야 한다면 파트를 나눠 병렬적으로 정렬한 후 각 파트를 합치는 과정에서 다시 정렬을 해야 한다.
• Balance
  : 각 스레드가 동일한 작업 량을 수행하도록 나눌 수 있어야 한다.
• Data splitting
  : 데이터 역시 각 코어로  알맞게 나누어져야 한다. 
• Data dependency
  : 나누어진 파트의 dependency에 따라 순서대로 스레드가 처리되어야 한다.
• Testin and debugging
  : 싱클 스레드에 비해 테스팅과 디버깅이 어려워진다.

 

Amdahl's Law

speedup ≤ 1 / ( S + ( (1-S) / N ) ),

S: 병렬처리를 할 수 없는, 반드시 순차적으로 실행되어야 하는 범위

N: 코어 개수

 

코어는 무조건 많을수록 좋을까?

암달의 법칙에 따르면 S가 0이 아니라면 코어의 개수가 많아진다고 비례하여 실행속도가 빨라지지 않는다.

 

 

---

[ Multithreading Models ]

• user thread
  : user mode에서 사용되는 스레드, 사용자 수준의 스레드 라이브러리가 관리하는 스레드
• kernel thread
  : kernel mode에서 사용되는 스레드, OS가 직접적으로 관리하는 스레드

커널 스레드를 사용하면 안정적이지만 유저 모드에서 커널 모드로 계속 바꿔줘야 하기 때문에 성능이 저하된다. 반면 유저 스레드를 사용하면 안정성은 떨어지지만 성능은 저하되지 않는다.

 

유저 스레드와 커널 스레드의 관계에 따라 3개의 멀티스레딩 모델이 있다.

 

 

Many-to-One Model

# of user threads : # of kernel threads = N : 1

한 번에 하나의 유저 스레드만 커널에 접근할 수 있기 때문에 멀티코어 시스템에서 병렬 처리를 할 수 없다. 

 

One-to-One Medel

# of user threads : # of kernel threads = 1 : 1

동시성을 높여주고 멀티코어 시스템에서는 여러 개의 스레드를 병렬 처리할 수 있다. 일대일 대응이기 때문에 유저 스레드가 늘어나면 커널 스레드도 늘어나게 되는데, 생성할 수 있는 커널 스레드의 수에는 한계가 있으며, 커널 스레드를 생성하는 것은 오버헤드가 큰 작업이기 때문에 성능 저하가 발생할 수 있다.

 

Many-to-Many Model

# of user threads : # of kernel threads = N : M

위 두 모델을 합친 모델이라고 할 수 있다.

 

 

---

[ Thread Libraries ]

스레드를 생성하고 관리하는 API이다.

대표적으로 POSIX Pthreads, Windows thread, JAVA thread 가 있다.

 

 

---

[ Implicit Threading ]

concurrent 하고 parallel 하게 만드는 것, 즉 멀티코어 시스템에서 멀티스레딩을 구현하는 것은 매우 어렵기 때문에 openAPI와 run-time 라이브러리를 사용한다.

 

Alternative Approaches

• Thread Pools
  : 스레드를 매번 생성하고, 지우는 과정을 반복하면 성능이 저하된다. 그러므로 미리 스레드를 여러 개 만들어서 pool에 저장해두고, 필요할 때 스레드 풀에서 스레드를 할당해주는 방법을 사용한다.
• Fork & Wait(Join)
• OpenMP
  : 컴파일러 지시어를 사용한 C/C++ API이다. 컴파일러 지시어를 통해 컴파일러에게 parallel하게 처리하는 부분을 지시해두고, run time 라이브러리인 openMP를 이용해 해당 부분을 병렬 처리한다.
  omp.h 라이브러리가 필요하며, #pragma omp parallel 컴파일러 지시어를 사용한다.
• Grand Central Dispatch (GCD)
  : Apple에서 개발한 macOS와 IOS를 위한 OS