[Operating System] Threads Concurrency

Multithreaded Processes Models

---

Concurrency vs. Parallelism

• Parallelism: 시스템이 둘 이상의 작업을 동시에 수행할 수 있다. -> multiprocessing, multi-core system
  

• Concurrency: 여러 개의 프로그램이 CPU를 돌아가면서 차지한다. -> multiprogramming, single-core system
  

Multithreaded Process

• 프로세스는 두 가지 특성으로 나눌 수 있다.
  • Unit of resource ownership: execution stream과 연관성이 낮다.
  • Unit of execution stream: 스레드가 제어하며, 실행 상태와 dispatching 우선순위가 있다.
    • stack, register

• 어떻게 두 특성을 나눌 수 있을까?
  • 대부분의 최신 OS는 두 특성을 독립적으로 처리한다.
  • Unit of resource ownership -> 프로세스 또는 task
  • Unit of execution stream -> 스레드 또는 lightweight process
    

Multithreading: Basics

• 스레드의 특성
  • 실행 상태(execution state)를 가지고 있다. - running, ready, stopped
  • 실행하지 않을 때는 TCB 또는 stack에 thread context를 저장한다.
  • 로컬 변수에 대한 실행 스택은 스레드마다 가지고 있다.
  • 프로세스의 메모리 주소 공간 및 리소스에 접근할 수 있다.
  • 프로세스의 모든 스레드는 메모리 공간을 공유한다.

• 멀티스레드가 하는 일에 따른 종류
  • data parallel execution: 데이터를 나눠서 동일한 일을 진행한다. (ex. 행렬 곱셈)
  • task parallel execution: 하는 일 자체가 다 다르다.

• 스레드의 state transition
  • Running, ready, blocked (Stopped)
  • 같은 프로세스 안에서 스레드가 공유되므로, 메모리 공간 부족으로 메모리에서 쫓겨나는 경우 (일시중지 상태)가 없다.
  • 싱글 스레드에서의 일시중단: 같은 프로세스의 모든 스레드 일시중단
  • 프로세스의 종료: 프로세스 내의 모든 스레드도 종료됨

Benefits of Multithreaded Process

• Responsiveness - 응답성
  • 하나의 스레드가 차단되더라도 다른 스레드는 여전히 실행할 수 있다.

• Resource sharing - 자원 공유
  • 스레드는 IPC보다 쉽게 프로세스의 자원을 공유한다.
  • IPC가 필요없다.

• Economy - 경제성
  • 소요 시간 단축: 새로운 스레드의 생성과 종료는 프로세스보다 더 적게 걸리며, 두 스레드간의 전환도 context switching보다 더 적게 걸린다.
  • 자원을 적게 사용한다. - code, heap, data는 공유하기 때문

• Scalability - 확장성
  • 프로세스는 멀티 프로세서 아키텍처를 활용할 수 있다.
  • 자원을 늘렸을 때, 그에 비례해서 성능 향상을 기대할 수 있다.

Threads Implementation: User Threads and Kernel Threads

---

User-Level Threads

• 100% 유저가 구현하는 스레드
• 커널은 스레드가 존재한다는 것을 인지하지 못한다. 따라서 유저가 라이브러리까지 구현해야 한다.
• 프로세스를 기반으로 할당한다.
• many to one
  

• 장점
  • 커널이 직접 관여하지 않아 비용이 저렴하다.
  • 직접 스케줄링 알고리즘을 고를 수 있다.
  • OS가 관여하지 않아서 어떤 시스템에서는 run 가능하다.
  • 그러나 치명적인 단점으로 인해 장점이 크지 않다.

• 단점
  • 프로세스가 block되면 모든 스레드도 같이 block된다.
  • 대부분의 시스템 호출이 차단되고 커널이 프로세스를 차단한다.
  • 커널은 프로세서에서만 프로세스를 할당할 수 있다. 한 프로세스 내의 두 스레드는 동시에 실행할 수 없다.
  • 코어가 여러 개가 있어도, 커널은 하나로 인지하므로 멀티코어의 장점을 누릴 수 없다.

Kernel-Level Threads

• user-level과 kernel-level 모두 존재한다.
  -> user와 kernel 1:1 mapping
• 커널은 스레드가 존재함을 완전히 인식한다.
• 스레드를 기반으로 할당한다. 스레드 기능을 위해 System call API와 커널 함수를 지원한다.
• One to one
  

• 장점
  • 커널은 여러 프로세서에서 동일한 프로세스의 여러 스레드를 동시에 스케줄링 할 수 있다.
  • Blocking이 스레드 레벨에서 발생하므로, 하나가 block 되어도 다른 스레드는 정상 작동한다.
  • 커널 루틴도 멀티스레드가 가능하다.

• 단점
  • 스레드 스위칭은 커널을 포함한다. 하지만 이것은 미미한 오버헤드에 불과하다.

Combined Threads

• user-level은 일을 나누는 단위이며, kernel-level은 CPU 스케줄링 단위이다.
• 1:1 mapping이 아닌 many to many

• 특성
  • 사용자 공간에서 스레드가 생성된다.
  • 커널 레벨 스레드 공유를 위해 유저 레벨에서 스케줄링한다. (스레드 기반)
  • 유저 공간에서 스레드 동기화가 수행된다.
  • 프로그래머는 커널 레벨 스레드 수를 조정할 수 있다.
  • 두 방식의 장점 결합

Thread Libraries

---

Thread Libraries

• 스레드 라이브러리는 프로그래머에게 스레드 생성 및 관리를 위한 API를 제공한다.

• 두 가지 기본 구현 방법:
  • 완전히 유저 공간에 있는 라이브러리
  • OS에서 지원하는 커널 레벨 라이브러리

Pthreads

• Pthreads: POSIX standard for threads
  • 스레드 생성 및 조작을 위한 API 정의
  • API는 스레드 라이브러리의 함수 이름만 지정하며, 내부 구현은 개발에 따라 달라질 수 있다.
  • 유닉스 계열 OS에서 일반적

Pthreads API	Description
pthread_create()	새로운 스레드 생성
pthread_exit()	스레드 종료
pthread_join()	특정 스레드가 끝나기를 기다림
pthread_yield()	CPU를 해제하여 다른 스레드가 실행되도록 함

Implicit Threading

• 프로그래머가 스레드를 구현하는 것이 아닌, 컴파일러 및 런타임 라이브러리가 스레드의 생성 및 관리 수행
• 스레드 수가 증가함에 따라 명시적 스레드에서 정확성이 더 떨어졌다.
• 세 가지 방법:
  • Thread Pools
  • OpenMP
  • Grand Central Dispatch

OpenMP

• C, C++, FORTRAN에서의 compiler directives와 API
• 공유 메모리 환경에서 병렬 프로그래밍을 지원한다.
• 병렬 영역을 식별하고, 병렬로 실행할 수 있게 한다.

#pragma omp prallel
{
	printf("hello world!");
}

• 전처리 아랫 줄만 코어 개수만큼 반복 실행하며, 한 줄 이상일 경우 괄호 { }를 사용한다.
• 개수 지정 시: #pragma omp parallel num_threads(n)

#pragma omp prallel for
for (i = 0; i < N; i++) {
	c[i] = a[i] + b[i];
}

• for문 전용 directives
• 컴파일 시: gcc 파일명 -fopenmp