앞에 까지는 CPU가상화와 메모리 가상화를 다루었다.
이번 포스팅부터는 Concurrency에 대해 다룬다. 그 첫 시작이 Thread이다!

Threads

1. Concurrency 문제

Concurrency는 빠르게 전환하며 여러 작업을 수행하여 동시에 여러 작업이 실행되는 것처럼 보이는 것이다.
현재 방식에서는 여러개의 프로세스가 CPU 자원 하나를 놓고 스케줄링을 통해 자원을 할당받아 사용한다. 이 방식을 single core 방식이라 한다. single core에서도 여러 작업을 concurrent하게 실행할 수 있고 작업 간에는 context switch가 일어난다.

위 그림과 같이 여러개의 프로세스가 하나의 자원을 잡으려 하고, 동시성 문제를 해결하기 위해 아래 그림과 같이 줄을 세운다.
이런 방식을 사용하면 동시성 문제는 해결되지만 효율성 문제가 있다.

2. Motivation

Thread가 무엇인지 설명하기 전에 Thread가 등장한 배경부터 알아보자.
프로세스는 프로그램에 대한 추상화를 제공하고 OS는 프로세스 간 보호와 독립을 보장한다. 하지만 프로세스만 사용하기에는 여러 문제가 있다.

첫 번째로는 하나의 프로세스는 multi-cores에서 이점을 발휘할 수 없다. 스레드를 이용하면 하나의 프로세스를 여러 코어로 동시에 실행할 수 있다.

두번째는 프로세스끼리 협력하도록 프로그램을 작성하기가 복잡하고 어렵다.

세 번째는 새로운 프로세스를 만드는 것은 expensive한 작업이다. process마다 page table이 존재하고 virtual address가 존재하기 때문이다.

네 번째는 프로세스간 통신하는데 overhead가 크다.

마지막으로 프로세스간 높은 Context Switch 비용이 든다는 점이다.

어떻게 하면 프로세스 내에서 값 싸게 concurrency를 증가시킬 수 있을지에 대한 답으로 Thread 개념이 등장한다. 즉, 프로세스 내에서 여러 Thread가 concurrency하게 수행

3. Thread

1. Thread 설명

Thread는 하나의 실행중인 프로세스에 대해 새롭게 추상화 한 것으로 프로세스 내에서 실행되는 흐름의 단위이다.
일반적으로는 하나의 프로그램은 하나의 스레드를 가지고 있지만, 프로그램의 환경에 따라 둘 이상의 스레드를 동시에 실행할 수 있다. 이를 멀티 스레드라고 한다.
스레드는 자신만의 Thread ID, PC와 SP를 포함한 registers set 그리고 Stack을 가진다.
[싱글 스레드] [멀티 스레드]

멀티 스레드 프로그램은 하나 이상의 실행 지점을 가지며, 다수의 PCs(Program Counter)를 가진다. 다수의 스레드는 하나의 address space를 공유한다.

2. Threads간 Context switch

각 Thread는 자신만의 PC(program counter)와 registers의 집합을 가진다. 하나 또는 그 이상의 Thread Control Blocks(TCBs)는 각 스레드의 상태를 저장한다.
한 프로세스 내에서 현재 실행중인 스레드 T1에서 T2로 Context switch 과정을 살펴보자.
1. T1의 register 상태가 저장된다.
2. T2의 register 상태가 복원된다.
3. address space는 동일하게 유지한다.
즉, 레지스터만 해당 스레드에 맞게 갈아 끼워주면 된다.

Thread는 자신만의 stack 공간을 가지며, Address Space는 공유한다.

4. Process vs Thread

1. process와 thread 차이

1. 스레드는 하나의 프로세스에 종속되어 있다.
2. 프로세스는 다수의 스레드를 가질 수 있다.
3. 스레드간 데이터 공유는 프로세스에 비해 cheap하다. (모든 스레드는 같은 address space를 가지기 때문)
4. 스레드는 스케줄링의 단위이다.
5. 프로세스는 thread를 실행하는 컨테이너이다. (PID, address space, user and group ID, open file descrptors, current working directory, etc.)
6. 프로세스는 정적이지만, 스레드는 동적이다.

2. Multi-threading의 장점

1. 동시성을 값 싸게 수행할 수 있다.
2. 큰 task를 여러 thread가 협력하여 수행할 수 있다.
3. 여러 thread가 병렬적으로 수행할 수 있으므로 Throughput이 증가한다.
4. Responsiveness. 동시에 오는 event에 대해 빠르게 처리할 수 있다.
5. 자원 공유(address space 공유)
6. multi-core 구조를 활용하여 병렬 프로그래밍을 가능하도록 한다.
   병렬 프로그래밍은 여러 코어에서 동시에 여러 작업을 수행. Parallelism는 빠르게 context switch를 하며 동시에 수행하는 것처럼 보이지만, 병렬 프로그래밍은 실제로 동시에 수행

5. Threads의 종류

Thread는 Kernel-level Threads와 User-level Threads로 나눌수 있다. 각각에 대해 특징을 알아보자.

1. Kernel-level Threads

OS-managed threads

1. OS가 직접 관리하는 Threads이다.
2. OS가 threads와 process를 생성하고 관리한다.
3. 모든 스레드 연산은 커널에서 구현된다.
4. 스레드 생성과 관리는 system call로 요청된다.
5. OS는 모든 스레드를 스케줄한다.
6. 프로세스를 만드는 것보다 스레드를 생성하는 것이 더 값 싸다.
   Windows, Linux, Solars, Mac OS X 등에서 사용된다.
   

Limitation

1. 여전히 비싼 비용이 든다.
2. 스레드 연산은 모두 system call로 이루어진다.
3. 반드시 커널이 각각의 스레드의 상태에 대해 가지고 있어야 한다. (동시에 사용가능한 스레드에 제한을 줄 수 있음)
4. OS는 증가하는 스레드에 대해 scale을 잘 해야 한다.
5. Kernel-level threads는 모든 프로그래머, 언어, runtime system 등을 지원하기 위해 general 해야한다.

2. User-level Threads

Thread Library가 지원

1. user-level에서 구현되는 스레드이다.
2. 프로그램에 연결된 라이브러리가 스레드를 관리한다.
3. 스레드는 OS에 보이지 않는다.
4. 모든 스레드 연산은 procedure call로 이루어진다. (kernel 관여X)
5. 작고 빠르다.
6. Portable
7. application 요구에 맞게 조정이 가능하다.
   

Limitation

1. kernel이 스레드에 대해 알 수 없기 때문에 일반적으로 non-preemptive 스케줄링에 의존한다.
2. OS는 user-level threads에 대해 알지 못하기 때문에 좋지 않은 결정을 내릴 수 있다.
   - idle thread 밖에 없는 프로세스를 스케줄링
   - thread가 I/O를 시작할 때 전체 프로세스를 Block
   - lock을 잡고 있는 스레드를 가진 프로세스를 스케줄링 하지 않음
3. 모든 Blocking system call은 커널에서 non-blocking call을 통해 라이브러리에서 흉내내져야 한다. 즉, kernel과 thread manager 사이에 협력이 필요하다.
4. multi-core CPU의 이점을 활용할 수 없다.
   커널에서는 프로세스에 대한 개념밖에 없기 때문에... 즉 스레드를 모름

6. Thread관련 Issue

1. Race Condition

Race condtion이란 두 개 이상의 스레드가 공통 자원에 대하여 읽거나 쓰는 동작을 할 때, 공유 데이터에 대한 접근이 어떤 순서로 이루어졌는지에 따라 그 실행 결과가 달라지는 것을 말한다. 아래 예시를 살펴보자.

counter = counter + 1 (default is 50) 연산이 주어진다. 최종적으로 기대되는 결과는 52이다. 위 그림에서 thread1은 eax에 메모리 값(counter 값)을 가져오고 eax값을 1 증가시키는 작업을 한 후 interrupt가 발생하여 thread2가 실행된다. thread2는 thread1과 같은 작업을 반복하지만 이 때 thread2는 eax값을 1 증가시킨 뒤 해당 메모리(counter)에 저장하는 코드까지 모두 수행 후 interrupt가 발생하여 thread1이 수행된다. 이 때 eax값은 51이므로 couter최종적으로 51을 저장한다.

만약 여기서 thread1이 메모리에 저장하는 명령을 수행한 후 인터럽트가 발생하고 thread2의 경우도 마찬가지로 진행된다면 정상적으로 52가 저장될 것이다. 이렇게 race condition은 실행할 때마다 따라 결과가 달라 질 수 있다. (Indeterminate)

2. Indeterminate(비결정성)

프로그램의 실행 결과가 실행할 때마다 변하는 것을 말한다. 이 때 결과는 어느 스레드가 언제 수행되는지에 의존한다.

3. Critical section

공유된 변수를 접근하는 코드로 하나 이상의 스레드에 의해 동시에 수행 되어서는 안된다.
-다수의 스레드가 critical section을 수행하는 경우 race condition이 발생할 수 있다. 위의 그림 예시에서 공유 변수인 counter에 thread1과 thread2가 동시에 접근하여 race condition이 발생하는 것을 볼 수 있다.

-critcal section에 대해 원자적으로 수행하는 것을 지원해야 한다. (mutual exclusion) => thread1이 critcal section을 빠져나갈 때 까지 thread2가 기다려야 한다. 즉, critical section에는 한 번에 하나의 thread만 원자적으로 수행할 수 있어야 한다.

4. Mutual exclusion

만약 한 스레드가 critical section에서 실행중이라면, 다른 스레드가 critcal section에 접근하여 실행하는 것을 막는 것을 보장하는 특성이다.

5. Locks

critical section을 하나의 원자적인 명령어처럼 수행하도록 보장한다.
lock부터 unlock까지 하나의 single instruction으로 여기도록 한다.

7. Threads Interface

1. Thread_create

2. Thread_join

다음에는 Thread의 Issue들을 해결하기 위한 기법중 하나인 Lock에 대해 알아보겠습니다.