Outline

Thread

• Thread : CPU 이용의 기본 단위. process보다 가벼운 개념이다.

• Thread의 구성요소

  • Thread id
  • Program Counter
  • register set
  • stack

• thread는 같은 process에 속한 다른 thread와
  code, data section, OS resources(open files, signal 등)을 공유한다.

• process는 하나의 제어 thread를 갖고 있다.
  process가 thread를 나누지 않고, 그냥 그 자체로 하나의 thread인 경우를
  중량 프로세스(heavyweight process)라고 한다.

• 만약 process가 multi thread를 가진다면, process는 동시에 하나 이상의 작업을 수행할 수 있다.

• 중량 프로세스에서 context switching : process switching
  경량 프로세스에서 context switching : CPU switching, thread context switching

Single & Multithreaded Processes

• Single-Threaded Process == 단일 thread == heavyweight process
• Multi-Threaded Process == 다중 thread
  • Multi-Threaded Process의 thread들은 code, data, files를 모두 공유한다.
  • 함수는 부르는 대로 하나씩 순차적으로 실행되는데,
    thread는 한번 만들어지면 실행할 때 알아서 실행한다.
    여러 개의 함수가 동시에 동작될 수만 있으면 각각을 하나의 thread로 생각 할 수 있다.

Multithread Motivation

ex 1. Multithreaded Server Architecture

• Web Server는 Client로부터 web page나 이미지, 소리 등에 대한 request를 받는다.
• 하나의 Web Server에 수천 개의 Client들이 접근할 수 있다.
  그래서 만약 Web Server가 single thread process로 작동한다면,
  자신의 single process로 한 번에 하나의 Client만 서비스할 수 있게 되어
  Client는 자신의 요구가 서비스되기까지 매우 긴 시간을 기다려야 할 것이다.
• Web Server가 Multithread화 된다면,
  Server는 Client의 request를 listen하는 별도의 thread를 생성한다.
  request가 들어오면 다른 process를 생성하는 것이 아니라,
  request을 서비스할 새로운 thread를 생성하고 추가적인 요청을 listen하기 위한 작업을 재개한다.
• 즉, Server는 항상 같은 일을 하기 때문에 process를 매번 새로 생성하는 것이 아니라
  특정한 request에 response할 thread를 할당하여 생성하고 처리하는 식이 훨씬 효율적이다.

현대의 컴퓨터와 모바일 기기에서 작동하는 거의 모든 SW 응용들은
Multithread를 이용한다.

ex 2. 계산대

• 마트 계산대의 구조가 윗그림, 아랫그림이 있다고 가정하자.
  윗그림은 점원이 손님의 계산을 직렬로 순차적으로 처리하고.
  아랫그림은 점원이 돌아다니며 손님의 계산을 돌아가면서 처리한다.

• 손님의 줄: thread / 점원 : CPU 라고 생각해보자.

• 처리시간 = 대기시간 + 작업시간
  윗그림과 아랫그림에서의 평균 처리시간을 비교해보자.
  

• 윗그림의 평균 처리시간
  (10 + (10 + 5) + (10 + 5 + 2) + .. + (10 + 5 + 2 + 8 + 1)) / 5
  = (10 + 15 + 17 + 25 + 26) / 5
  = 93 / 5
  = 18.6

• 아랫그림의 평균 처리시간
  = (5 + 8 + 17 + 24 + 26) / 5
  = 80 / 5
  = 16

윗그림의 평균 처리시간(18.6) > 아랫그림의 평균 처리시간(16)
multithread가 더욱 효과적이라는 결론을 내릴 수 있다.

Benefit

1. Responsiveness : 응답성
2. Resource sharing : 자원 공유
3. Economy : 경제성
4. Scalability : 확장성

---

Multicore Programming

Multicore

• Thread를 사용하는 이유는 Multi Processing을 하기 위함.
• 일반 개인용 PC는 multiprocessor를 사용하지 않고, multicore를 사용한다.
  • multiprocessor : CPU 여러 개.
  • multicore : CPU가 하나인데, 그 안에 core가 여러 개.

Parellelism VS Concurrency

• Parellelism :
  “하나 이상의 Task를 물리적으로 동시에 처리할 수 있다.” 라는 의미(진짜 동시에)
  core가 2개 이상 있어야 함. 병렬처리로 인해 더욱 효율적이다.
  

• Concurrency :
  “하나 이상의 Task가 함께 있으나 독립적으로 번갈아 가며 진행되고 있다.”(진짜 동시는 아님)
  

Amdahl’s Law

그렇다면 Core가 많아질수록 빨라지는가?
→ 그것은 아니다. (Amdahl’s Law 으로 증명)

• Amdahl’s Law :
  컴퓨터 시스템의 일부를 개선할 때, 전체적으로 얼마나 성능이 향상되는지 계산하는 수식
  • $N$ : core 개수
  • $S$ (= 1-P) : Serial 한 부분
  • $P$ (= 1-S) : Parallel 한 부분 (성능이 개선된 부분)
    

• example
  

  • speedup times?
    ➡️ 1 / (25 + 75/1) = 1/100 → 1 / (25 + 75/2) = 1 / (62.5)
    ➡️ 100 / 62.5 = 1.6
    ➡️ core를 1개에서 2개로 늘렸더니, 1.6배 빨라졌다.

  • ("병렬처리를 안했다") == (S = 1)
    ➡️ speedup ≤ 1 / (1 + 0/1) = 1
    ➡️ 최대 1배 빨라짐

  • ("100% 병렬처리 했다") == (S = 0)
    ➡️ speedup ≤ 1 / (0 + 1/N) = N
    ➡️ 최대 N배 빨라짐 (Core 개수가 N개라면, N배 빨라진다)
    하지만 과연 그럴까?

• Amdahl's Law의 숨은 의미 :
  이론적으로 100% 병렬로 처리하면,
  과연 core가 n개일 때, n배만큼 빨라진다고 할 수 있을까?

  • (초록색) : 현실적으로 100% 병렬로 처리하는 것은 불가능하기 때문에
    95%를 병렬처리, 5% 순차처리
  • (초록색) :
    90%를 병렬처리, 10% 순차처리
  • (초록색) :
    75%를 병렬처리, 25% 순차처리
  • (초록색) :
    50%를 병렬처리, 50% 순차처리
    
    ➡️ core가 n개일 때, n배만큼 빨라진다고 할 수 있을지 test하기 위해
    위의 그래프에서 core의 개수를 무한으로 보내어 값을 확인해봤더니,
    알 수 있는 사실은 병렬처리를 최대로(95%까지) 늘려도 성능 개선은 최대 20배까지가 한계임을 알 수 있다.

Amdahl’s Law의 숨은 의미
병렬처리를 할 수 있는 최선(95%)까지 하고 Core개수를 무한으로 늘려봐도,
성능 개선은 최대 20배까지이다.
더 이상 개선을 못한다는 사실도 내포하고 있기 때문에 Amdahl의 저주라고도 불린다.

---

Multithreading Models

User Threads & Kernel Threads

• Thread는 처리되는 위치에 따라 User Thread와 Kernel Thread가 있다.
  
• User Threads : Library에 의해 thread 형태로 만들어져
  user space 내에 존재하는 모든 thread.
• Kernel Threads : OS에 의해 직접 지원되고 관리되며
  kernel space 내에 실행되는 스레드.
  • user thread는 나중에 kernel thread와 결합해서 최종적으로 돌아 간다.
  • 최종적으로 동작하는 thread는 Kernel space에서 돌아가야 한다.
  • Kernel thread는 kernel를 가지고 있는 모든 OS에서 지원한다.

궁극적으로 User Threads는 나중에 Kernel Threads와 결합하여 동작하기 때문에
User Threads와 Kernel Threads의 연관 관계를 확립하는 4가지 일반적인 model이 있다.

1. Many-to-One model

• Many-to-one model == User-to-kernel model :
  여러 개의 user thread가 하나의 kernel thread와 연결된 model.
  • thread관리는 User Space의 Thread Library에 의해 행해진다.
    따라서 효율적일 수 있지만,
    한 thread가 봉쇄형 system call을 할 경우, 전체 process가 봉쇄된다.
  • 또한, 한 번에 하나의 Thread만이 kernel에 접근할 수 있기 때문에,
    다중 thread가 다중 core systsem에서는 병렬로 실행될 수 없다.
  • 현대 컴퓨터의 Multicore 이점을 살릴 수 없기 때문에
    현재 이 model을 사용 중인 시스템은 거의 없다.
    

2. One-to-one model

• One-to-one model :
  user thread 각각을 kernel thread와 매칭하여 연결된 model.
  • 이 모델은 하나의 thread가 봉쇄적 system call을 호출하더라도
    다른 thread가 실행될 수 있기 때문에 Many-to-One model보다
    더 많은 병렬성을 제공한다.
  • 이 모델의 유일한 단점은 User Threads를 만들려면
    해당 Kernel Threads를 만들어야 하며,
    많은 수의 Thread가 시스템 성능에 부담을 줄 수 있다는 것이다.
  • 하지만 최근에는 대부분의 시스템에서 core 수가 증가함에 따라
    kernel thread 수를 제한하는 것의 중요성이 줄어들었기 때문에
    One-to-one model이 가장 많이 사용된다.
    

3. Many-to-many model

• Many-to-many model :
  user thread와 kernel thread들이 섞이며 연결된 model.
  • 개발자는 필요한 만큼 많은 User Threads를 생성할 수 있다.
    그리고 상응하는 Kernel Threads가 Multiprocessor에서 병렬로 수행될 수 있다.
  • 또한 Thread가 봉쇄형 system call을 발생시켰을 때,
    Kernel이 다른 thread의 수행을 schedule할 수 있다.
  • 이 모델이 가장 융통성 있는 모델인 것처럼 보이지만,
    실제로는 구현하기 어렵다.
    

4. Two-level model

• Two-level model :
  1:1, N:N model이 binding된 model.
  • Many-to-many model을 변형시킨 model이다.
    Many-to-many model에서
    한 User Threads가 하나의 Kernel Threads에만 연관되는 것을 허용하는 model.
  • 구현하기 어렵다.
    

---

Threads Library

• Thread Library :
  프로그래머들에게 thread를 생성하고, 관리하기 위한 API를 제공한다.

• 현재 세 종류 Library가 주로 사용된다.

  1. POSIX Pthreads
  2. Windows Threads
  3. Java

Pthreads

Windows Threads

---

Implicit Threading

---

Threading Issues

---

OS Exmaples

---