참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

Thread

What is Thread?

Thread 는 CPU를 이용하는 기본단위이다. 따라서 스레드는 프로세스에 속해져 있는 개념이다. 스레드는 스레드 ID, 프로그램 카운터, 레지스터, 스택으로 구성되어 있고 앞으로 설명할 Multi-Threading 덕분에 한 프로세스가 여러 thread 를 가지게 되는 것이 가능해졌다. 한 프로세스에 속해져있는 여러 스레드는 프로세스의 코드, 파일이나 데이터, OS의 자원 등을 서로 공유할 수도 있다.

Multi-Threading

우리가 브라우저에서 여러 탭을 열어놓고 사용한다고 생각해보자. 만약 한 프로세스가 하나의 스레드만 가질 수 있다면, 서버에 연결, 데이터 불러오기, 사용자에게 입력받기 등 모든 작업이 순차적으로 이루어지기 때문에 꽤나 많은 시간이 소요될 것이다. 그리고 네트워크는 한번에 한 프로세스에만 연결되는 것이 아니니 서버에서 다른 모든 프로세스들이 처리되기까지 기다려야하는 상황이 생길지도 모른다. 그러나 Multi-Threading 이 가능하다면, 하나의 스레드는 페이지를 로딩, 다른 스레드는 네트워크에서 다른 작업이 동시에 가능할 것이다.

대부분의 운영체제는 multi-threading 을 사용하고 특히 운영체제의 kernel에서 multi-threading 을 사용하는 경우가 많다. kernel을 구성하게 되는 다수의 스레드는 인터럽트 처리, 메모리 관리 등 다양한 역할을 나눠서 부담하게 된다.

Why Multi-Threading?

Multi-Threading 을 사용했을 때 얻을 수 있는 이점은 다음과 같다.

1. 한 스레드가 block 되거나 interrupt에 의해 중단되어도 다른 스레드는 계속해서 작업을 진행할 수 있기 때문에 사용자에 요청에 즉각적으로 응답할 수 있다.
2. Shared-Memory 나 Message-Passing 으로만 자원을 공유할 수 있는 프로세스와는 달리 thread는 단일한 프로세스에 속하면서 프로세스의 자원들을 함께 공유하기 때문에 자원을 공유할 때 발생하는 오버헤드가 적다.
3. 프로세스가 새로운 프로세스를 생성하는데 드는 메모리나 시간의 비용보다 새로운 스레드를 생성하는데 드는 부담이 더 적다. 더불어 프로세스간의 context switch는 프로세스가 서로 공유하는 자원이 없기 때문에 서로 완전히 교환하기에 큰 오버헤드가 발생하는데 스레드는 자원을 공유하고 있기 때문에 context switch의 부담이 적다.
4. Multi-Processing system 에서 프로세스의 갯수가 늘어남에 따라 더 병렬적인 작업의 수행이 가능해졌다.

Multicore Programming

Multicore programming 은 한 프로세서 칩이 여러 컴퓨팅 코어를 가지고 있는 것을 의미한다. 코어가 여러개 존재하기 때문에 Multi-threading 기법은 더 큰 효과를 보일 수 있게 되었다.

어떤 시스템이 여러 코어를 가지지 않고 단일한 코어를 가지고 연산을 수행한다고 해보자. 한 코어는 하나의 스레드만 실행이 가능하다. 따라서 아무리 multi threading 이 multi processing 에 비해 더 적은 오버해드를 가지고 있다고 해도 time sharing 을 통한 다수의 작업 진행에는 한계가 있다. 반면 어떤 컴퓨터 시스템이 다수의 코어를 가지고 있다고 한다면, 각 코어마다 각각의 스레드를 할당 할 수 있기 때문에 진정한 의미에 ‘동시’ 작업이 가능해진다.

Concurrency vs. Parallelism

위 설명에서 지속적으로 병렬(Parllelism), 병행(Concurrency) 라는 용어를 사용했다.

Concurrancy
어떤 시스템이 모든 작업을 진행하게 하고 다수의 작업을 지원하는 것을 말한다. 우리가 앞서 공부했던 time-sharing이 이런 concurrency를 가능하게 한다. CPU가 여러 코어를 가지고 있다고 해도 여러 작업을 나누어서 빠른 속도로 교환하면서 실행한다. 우리의 눈에는 동시에 여러 작업이 실행되는 것 처엄 보이지만, 사실 아닌 것이다.

Parallelism
어떤 시스템이 여러 작업을 동시에 수행할 수 있는 것을 말한다. 여기서 말하는 ‘동시’는 우리 눈에 그렇게 보이는 것이 아니라. 진정한 의미에서 다수의 작업이 동시에 수행되는 것을 말한다. 이것이 가능하려면 여러 스레드가 동시에 사용되어야 하고, 한개의 코어에 스레드가 각각 할당이 되게 된다.

Amdhal’s Law

응용프로그램의 모든 구성요소가 병렬적으로 구성되어 있지는 않다. 응용프로그램은 순차적인 요소와 병렬적인 요소로 구성되어 있기 때문에 아무리 많은 CPU 코어가 있다고 해도 성능을 무한히 확장시킬 수는 없다. Amdhal’s Law는 공식을 통해서 우리가 코어갯수에 따라 최대로 확장시킬 수 있는 성능향상을 가늠해볼 수 있게 한다.

Amdhal’s Law는 위와 같다. 여기서 p는 병렬적으로 처리되는 구성요소의 비율을 의미한다. 책에 나와있는 예를 그대로 사용해보면, 만약 우리가 가진 응용프로그램이 2개의 코어를 가진 시스템에서 실행되고 순차적인 구성요소가 25% 를 차지한다고 했을 때, 병렬적인 요소가 차지하는 비율은 75% 이므로, 1/(0.75+0.75/2) 은 1.6이 된다. 즉, 코어의 갯수가 2개인 시스템에서 이 응용프로그램을 실행하면 실행속도가 1.6배 빨라진다는 것이다. 주목해야 할 점은 N을 무한대까지 늘려본다고 하더라도 최대로 늘어나는 속도는 2배 이상이 되지 않는다. 따라서 코어의 갯수를 아무리 늘린다고 해도 극적인 성능의 향상은 불가능한 것이다.

Challenges in Multicore Programming with Multi-Threading

다수의 코어를 사용하는 시스템에서 Multi-threading 을 사용하기 위해서, 개발자에게는 몇가지 고려해야할 문제들이 있다.

1. 응용프로그램을 병행 가능한 스레드로 나눌 수 있도록 그 지점을 찾을 수 있어야한다. 이를 통해서 응용프로그램을 각각 독립적인 부분으로 나누고 개별 코어에서 병렬적으로 실행될 수 있도록 해야한다.
2. 여러 스레드가 하는 작업들이 균등하게 분배되어서 코어가 낭비되는 일이 없도록 해야한다.
3. 나뉘어진 스레드가 사용하는 데이터들이 각 코어에서 사용이 가능하도록 나뉘어져야 한다.
4. 스레드가 접근하는 데이터에 대해 dependency를 확인하고 동기화해주는 작업이 필요하다.
5. 테스팅과 디버깅이 가능하도록 해야한다.

Type of Paralleism

Data Parallelism

데이터 병렬 실행은 하나의 데이터집합을 다수에 코어에 나누어서 동시에 작업을 수행할 수 있도로고 하는 것이다. 만약 우리가 코어가 2개인 시스템에서 길이가 N인 배열의 모든 요소들의 합을 구한다면, 하나의 스레드가 0부터 N/2-1 까지의 합을 구하고, 별도의 스레드가 N/2 부터 N-1 까지의 합을 구하는 작업을 동시에 수행하도록 할 수 있을 것이다. 중요한 것은 하나의 데이터에 대해서 여러 스레드가 같은 연산을 수행한다는 것이다.

Task Parallelism

태스크 병렬실행은 각 코어가 스레드를 나누어 가지고 서로 다른 기능을 하는 것이다. 여러 스레드가 같은 데이터에 대해 연산을 수행할 수도 있고, 완전히 다른 고유한 작업을 수행할 수도 있다. 이 방법은 데이터 병렬 실행을 포함한다.

Multi-Threading Models

스레드는 user level thread 와 kernel level thread로 나뉘어진다. user-level thread는 커널로 부터 어떤 지원도 받지 않는다. user-level thread는 응용프로그램과 라이브러리로 구현이 되기 때문에 커널의 입장에서는 단일한 process로 인식된다. 그리고 kernel-level thread는 운영체제에 의해 직접 지원되고 관리되는 스레드이다. 이 두 스레드 사이에서는 관계가 존재한다. 그리고 그 종류는 일반 적으로 다음과 같이 나누어진다.

Many-to-One Model

위와 같이 다수의 user-level thread 가 하나의 kernel thread에 맵핑되어 있는 구조를 Many-to-one model 이라고 한다(그림에는 화살표가 들어가있는데, 일방향이 아니라 양방향이다..). 스레드가 사용자의 스레드 라이브러리에 의해 관리되기 때문에 효율적이다. 왜냐하면 kernel을 거치지 않아도 되기 때문에 처리속도가 빠르기 때문이다. 하지만 하나의 Kernel thread에 모두 연결되어 있기 때문에 만약 한 user thread에서 system call을 발생시키면 그 system call 을 kernel thread가 해결할 때까지 전체 프로세스가 block 된다. 스레드를 커널이 관리하지 않기 때문에 어떤 스레드가 system call을 보냈는지 알 수 없기 때문이다.

One-to-One Model

일대일 모델은 각각의 user thread가 하나의 kernel thread에 연결되어 있는 모델이다. 각 user thread에 대해 하나의 kernel thread가 사용되기 때문에 many-to-one model에서 발생했던 blocking 문제가 해결되었다. 그리고 multiprocess 시스템에서 더 많은 병렬실행을 수행할 수 있는 구조이다. 단점은 user thread를 만들 때마다 kernel thread를 만들어야하기 때문에 많은 수의 스레드가 컴퓨터 시스템에 부담이 될 수 있다는 점이다. 이 단점 때문에 일반적으로는 user-level thread가 만들어질 수 있는 숫자를 제한한다. 최근에 이르러서는 코어의 수가 크게 늘어남에 따라 스레드 갯수에 대한 시스템의 부담을 덜게되고 큰 문제는 아니게 되었고 많은 운영체제가 이 모델을 채택하여 사용하고 있다.

Many-to-Many Model

다대다 모델은 다수의 user-level thread가 user-level thread와 같거나 더 적은 수의 kernel level thread와 맵핑되어 있는 모델이다. Multiplexer 로 구성되는 이 모델은 사용자가 원하는 만큼 스레드를 생성할 수 있고, 어느 정도 다수의 kernel-level thread의 수를 확보하기 때문에 병렬성도 보장할 수 있다.

Two-Level Model

다대다 모델에서 조금 변경된 형태로, 다대다 관계를 지원하면서 동시에 하나의 스레드가 하나의 커널에만 연결되도록 한다. 매우 융통성 있고 효울적인 모델처럼 보이지만, 구현이 어렵다는 단점이 있다.