Threads & Concurrency

Motivation

• thread 는 process 내의 단위 실행 객체다.
• process 보다 더 작은 단위인 thread 의 도입 계기는 한 프로그램이 다수의 task 들을 병렬적으로 실행해야 하는 경우가 발생하기 때문이다.
• thread 가 없다면, 각 task 에 대해 각각을 수행하는 process 들을 일일히 생성해야 하는데, fork() 는 expensive 한 연산이기 때문에 자원이 매우 비효율적으로 이용된다. 그렇기에 process 내부의 실행 객체인 thread 를 생성하는 것이다.
  
• process 하나에 여러 개의 thread 를 가지는 multi-threaded process 를 살펴보자. thread 는 앞서 말했듯이 별도의 실행 객체이기 때문에 공유되지 않는 각자의 stack 과 register 를 가진다. 이외의 data, text, heap 은 공유한다. 이 때의 장점은 다음과 같다.

1. responsiveness (응답성) : 특정 thread 가 block 되더라도 process 의 실행은 멈추지 않는다.
2. resource sharing : 자원을 효울적으로 사용하고 process 실행의 overhead 를 줄인다.
3. economy : process 보다 thread 의 생성 시간과 context switch time 이 더 적다.
4. utilization of multi-processor architectures : thread 들은 각자 다른 CPU 에 할당할 수 있다.

Multicore Programming

• 다수의 processor 들을 이용해 여러 개의 thread 들을 병렬적으로 수행하는 방식이다.
  
• 위 그림은 concurrent execution (동시성 실행) 을 나타낸다.
• single core system 에서는 한 시점에 하나의 process 가 수행되는데, scheduling 주기가 짧아 user 입장에서는 동시에 여러 process 가 수행되는 것처럼 보이게 하는 방식이다.
  
• 이 그림은 parallelism (병렬성) 을 나타낸다.
• 여러 개의 CPU 가 실제로 여러 개의 process 를 동시에 실행하는 것이다.
• parallelism 에는 여러 가지 프로그래밍 방식이 있는데, 방식에 따라 효율이 달라진다.

Types of parallelism

1. Data Parallelism
   

=> data 들을 여러 개의 subset 으로 나눔.
=> 각각의 core 에 서로 다른 data 를 넣고, 동일한 operation 을 수행하는 방식이다.
=> 위 그림처럼 두 반복문은 범위 data 만 다를 뿐, 같은 연산을 수행한다.
2. Task Parallelism
=> 각각의 core 들이 자신만의 unique 한 operation 을 수행하는 방식이다.

• multicore 은 어려 장점이 있지만, 실행되는 process 간의 균형, data 분배 등 신경 쓸 요소가 많아 구현이 어렵다. 그렇기에 새로운 관점의 디자인이 필요하다.

Multi-Threading Model

• thread 의 종류는 두 가지로 나눌 수 있다.

1. kernel thread : OS 에 의해 관리되는 thread
2. user thread : user space 의 thread library 에 의해 관리되며, OS 의 관여를 받지 않는다.

• OS 는 kernel thread 에만 관여할 수 있기 때문에, kernel / user thread 간의 mapping 관계가 있어야 두 종류의 thread 가 같이 실행될 수 있다.
• multi-thread model 에는 세 가지 원칙이 있다.
  

1. scheduler 는 user thread 의 존재를 인식하지 못한다.
   => mapping 이 필요한 이유와 연관된다. kernel 에 의해 scheduling 될 수 있는 것은 kernel thread 이지만, user 에게 중요한 건 user thread 의 실행이다.
   => ka 가 scheduling 된 시점에는 ud ue 는 실행될 수 없다.
2. kernel thread 가 block 되면, 그에 mapping 된 user thread 들도 같이 block 된다.
   => ka 를 block 해 waiting state 로 만들면, ua ub uc 도 block 된다.
3. kernel thread 는 각자 다른 CPU 에 할당 가능하다
   => parallelism 과 직결되는 특징이다. idle 한 CPU 를 줄여 효율적인 수행이 가능하다.
   => user therad 는 CPU 에 할당할 수 없다.

• multi-threading model 은 mapping 관계의 양상에 따라 다음과 같이 분류할 수 있다.

1. Many to One
   

• 하나의 kernel thread 에 다수의 user thread 가 mapping 된다.
• user thread 는 library 가 따로 관리해 kernel 개입이 필요없기 때문에 빠르고 overhead 가 작다는 장점이 있다.
• 하지만, kernel thread 가 block 될 때 덩달아 많은 user thread 가 block 되고, mapping 되지 않아 idle 한 CPU 가 많다는 단점이 있다.

2. One to One
   

• kernel / user thread 가 일대일 mapping 되며, many to one 의 정 반대의 장단점을 가진다.
• kernel thread 의 blocking 의 영향을 덜 받고, multi processor 의 장점을 잘 살린다.
• kernel thread 생성은 expensive 하기 때문에, user thread 의 생성 갯수가 제한된다.

3. Many to Many
   

• 앞의 두 모델을 합친, kernel / user thread 가 다대다로 mapping 되는 모델이다.
• 어떤 양상으로 mapping 할지 정하는 작업을 multiplexing 이라고 하며, 이는 필수다.
• 앞의 두 모델의 장점들을 모두 가진다.

4. Two level model

• many to many 와 one to one 이 공존하는 모델이다. user thread 의 소속이 두 가지인 것이다.
• one to one model 에 소속된 user thread 를 bound thread 라고 한다.
  
• LINUX 의 경우에는 어떤 모델을 사용할까?
• kernel level 을 살펴보면, 각 user thread 들은 task_struct 타입의 PCB 를 각자 할당받는 것을 알 수 있다. 각 thread 는 별도로 실행되는 객체이기 때문이다. PCB 생성에는 system call 이 필요한데, 이는 각 user thread 가 kernel level 과 연결되는 매개체 즉, kernel thread 와 연결되어 있다는 의미이다.
• 그러므로, LINUX 는 one to one model 을 사용한다고 간주할 수 있다.

Thread Libraries

• thread library 는 thread 생성과 관리에 대한 API 로, thread 와 관련된 함수들을 제공한다.
• 구현하는 방법에는 두 가지가 있다.

1. library 를 user space 에서 제공
   => API 를 통해 함수를 호출해도 kernel 관여 없이 user level 에서만 동작하는 방법이다.
2. kernel level library 형태
   => kernel 의 도움을 받아 system call 의 형태로 library 함수를 호출한다.
   => LINUX 에서는 thread 생성 시 PCB 를 생성해야 하기 때문에 이 형태를 사용한다.
   

• thread library 함수를 통해 thread 를 생성, 관리하는 예시다.
• thread library 이용을 위해 pthread.h 를 include 해준다.
• pthread_attr_init(&atrr) : thread 를 어떻게 생성, 관리할지에 대한 속성을 불러온다.
• pthread_create(&tid, &atrr, runner, argv[1])
  => thread 생성 함수이다.
  => 1, 2 번째 인자는 각각 thread id 와 관리에 관한 attribute 다.
  => 세 번째 인자는 실제 thread 에서 동작하는 함수다. 생성 후 runner 와 main 이 concurrently 수행된다. 별도의 PCB 를 가지지만, text 와 data 영역을 공유한다. 그렇기에 오른쪽의 함수 body 내에 있는 전역 변수 sum 은 main 과 공유된다.
• pthread_join(tid, NULL)
  => tid를 thread id 로 가지는 thread 의 종료를 기다린다. 종료 이후에는 다음 line 으로 program counter 이 이동해 출력문을 실행한다.
• fork() 의 wait 함수와 유사하다.

Multi-Threading Issues

• 어떤 thread 에서 fork() 가 호출되면, 복제되어 생성되는 process 에는 calling thread 만 복제될까? 아니면 parent process 의 모든 thread 들이 복제될까?
• 이는 exec() 의 호출 시점에 따라 달라진다.
• exec() 이 바로 호출되면, calling thread 만이 복제된다. text 영역이 바로 overwrite 되기 때문이다.
• exec() 이 호출되지 않으면, parent process 의 모든 thread 들이 복제된다. parent process 의 일을 child process 가 물려받아 수행하고자 했던 목적이 있을 수 있기 때문이다.

Thread Cancellation

• thread cancellation 은 하나의 thread가 다른 thread의 실행을 중단시키는 과정을 말한다.
• 첫 thread 의 종료 후 중단의 목표가 되는 남은 thread 들을 target thread 라고 한다. target thread 들이 종료되는 양상에는 두 가지가 있다.

1. asynchronous cancellation : target thread 가 즉시 종료된다.
2. deferred cancellation : thread 가 terminate 되어도 안전한지 검사 후 안전한 시점까지 대기한다.
   

Signal Handling

• signal 은 OS 에게 어떤 일이 일어났는지 여부를 신호를 통해 알리는 mechanism 이다.
• signal 에는 두 가지 종류가 있다.

1. synchronous signal : 프로그래밍 상 error 발생 시 (ex. 0으로 나누기)
2. asynchronous signal : process 외부의 일에 대한 signal

• signal 의 전송은 signal handler 의 호출을 통해 이루어진다. signal handler 에는 기본적인 default signal handler 와 사용자가 필요에 의해 정의해 사용하는 user-defined signal handler 가 있다.
• signal 이 전송되면 error 가 발생했다는 것이기 때문에 block 될 수 있다. 그렇기에 signal 이 발생했을 때 어느 thread 에게 전송해야 하는지는 중요한 문제다. 이에는 4 가지의 경우가 있다.

1. signal 이 적용되는 thread 에게만 전송
   => "division by zero" 의 경우에 해당
   => 다른 thread 들은 계속 실행되어도 무방하기 때문이다.
2. 모든 thread 에게 전송
   => 모든 process 를 kill 하는 명령어인 control + c 의 경우에 해당
3. 특정 thread 그룹에 전송
4. 특정 thread 를 지정해 전송
   => tid 를 명시하는 pthread_kill(pthread_t tid, int signal) 의 경우에 해당
   => 위 함수는 이름처럼 thread 를 kill 하는 것이 아닌 signal 을 전송하는 함수다.

Thread Pools

• 과도한 thread 생성은 자원을 낭비할 수 있기 때문에, thread 생성을 제한할 방법이 필요하다.
• Thread pool 은 정해진 갯수의 thread 를 미리 생성해 두고, 요청 시마다 thread 를 할당한다. 이는 thread 의 생성 갯수를 제한해 system stability 를 향상시킨다.
• 한번에 미리 생성한 thread 를 할당만 해주면 되기 때문에 약간 더 빠른 실행 속도를 보여준다.
  
• 위 그림에서 thread pool 에 thread 가 3개 뿐이기 때문에 D request 는 기각되거나, thread 를 반환 받아 여유분이 생길 때까지 wait 해야 한다.

Thread Programming API

• thread library 의 핵심 함수에는 다음의 세 가지가 있다. 이 함수들은 POSIX compatible 이다.

1. pthread_create

#include <pthread.h>
int pthread_create(pthread_t* tid, pthread_attr attr, void* f, void* arg)

• 세 번째 인자는 동작하는 thread 함수의 address 이다. 이 함수는 자신의 stack 과 register 를 가지고, main() 과 concurrently 수행된다.
• 0보다 큰 값을 반환하면 thread 생성이 성공했다는 신호다.

2. pthread_join

#include <pthread.h>
int pthread_join(pthread_t tid, void* thread_return)

• peer thread 의 종료를 기다리는 함수다.
• thread_return 은 종료 후 메시지를 받기 위한 포인터다.

3. pthread_exit

#include <pthread.h>
int pthread_exit(void* thread_return)

• thread 를 terminate 하는 함수다.
• join 을 호출해 기다리고 있던 main thread 에게 thread_return 을 통해 메시지를 전달한다.