멀티코어 프로그래밍 기본 개념

Intro

멀티코어 프로그래밍의 기본 개념을 살펴보기 위해 동시성(Concurrency)과 병렬성(Parallelism)의 차이를 알아보고, 데이터 병렬 처리와 작업 병렬 처리를 살펴본 뒤, 마지막으로 멀티 스레딩 기법에 대해 살펴보자.

Concurrency vs Parallelism

• Concurrency: 동시성

  • 동시성은 모든 task가 진행되도록 하여, 둘 이상의 task를 병행하는 것이다. 병렬성과 동의어가 아니다.

• Parallelism: 병렬성

  • 병렬성은 둘 이상의 task가 동시에 진행되는 것이다.

기존 컴퓨터는 대부분 싱글 코어로 구성되어 있었다. 이때도 여러 프로그램이 동시에 실행되는 것처럼 보였다. 하지만 이는 CPU가 여러 프로그램을 번갈아가며 실행해 모든 프로세스의 작업이 동시에 진행되도록 만드는 것이다. 이때 병렬성이 아닌 동시성을 가졌다고 볼 수 있다.

멀티코어 시스템 프로그래밍의 기술적 어려움

멀티코어 시스템 프로그래밍을 위해서는 다음과 같은 기술적 어려움을 극복해야 한다.

1. Identifying tasks

   • 작업 영역 중 병렬화 가능한 부분을 적절히 찾아내어야 한다.

2. Balance

   • 병렬화된 작업의 기여도가 균등하게 배분되어 최대한 효율적으로 자원을 사용할 수 있어야 한다.

3. Data splitting

   • 작업이 병렬화 되는 것처럼 작업에 사용되는 데이터도 병렬화 되어야 한다.

4. Data dependency

   • 한 작업이 소비하는 데이터가 다른 작업에도 사용된다면 작업 간 동기화를 고려하여 데이터의 의존성을 관리해야 한다.

5. Testing and debugging

   • 동시성, 병렬성을 가지는 프로그램은 그렇지 않은 프로그램보다 실행 경로도 많고 디버깅이 복잡하다.

Amadahl's law

암달의 법칙은 멀티코어 프로그래밍에서 코어의 증가와 성능 향상의 관계를 나타내는 법칙이며, 주요 골자는 코어의 수가 아무리 증가하여도 성능 향상의 상한은 프로그램 내 순차적(병렬의 반대)으로 실행되는 부분에 의해 결정된다는 것이다.

Data parallelism vs Task parallelism

병렬처리는 크게 데이터 병렬 처리와 작업 병렬 처리로 나뉜다.

• Data parallelism
  • 데이터를 여러 코어에 분산하여 처리하는 것이다.
  • 여러 코어에 동일한 데이터의 부분집합을 나누어 연산을 수행한다.
  • 예를 들어 1부터 N까지의 합을 구하는 경우, 1부터 N까지의 합을 구하는 작업을 M개의 코어가 각각 나누어 총합을 구하도록 하는 것이다.
  • 이때 각 코어는 같은 작업이지만 다른 데이터를 처리한다.
• Task parallelism
  • 작업을 여러 코어에 분산하여 처리하는 것이다.
  • 여러 코어에 고유의 연산을 수행하도록 분배한다.
  • 예를 들어 코어 1은 더하기 연산을 코어 2는 곱하기 연산을 수행하는 것이다.

Multithreading models

스레드는 유저 계층 혹은 커널에 둘 다 존재할 수 있다. 유저 계층의 스레드는 커널의 지원 없이 관리되고, system call을 하지 않는다. 커널의 스레드는 OS에 의해 직접적으로 관리된다. 또한 유저 스레드와 커널 스레드에는 관계가 형성될 수 있으며 크게 N:1, 1:1, N:N의 관계를 가질 수 있다.

Many-to-One model (N:1)

N개의 유저 스레드를 한 개의 커널 스레드와 맵핑하는 방식이다. 한 번에 한 스레드만 커널에 접근할 수 있기 때문에 여러 개의 스레드가 병렬적으로 실행될 수 없다. 스레드가 blocking system call을 하면 프로세스 전체가 blocking 된다.

스레드 관리는 유저 계층에 있는 스레드 라이브러리가 수행한다.

N:1 모델은 멀티코어의 이점을 충분히 활용하지 못해 일부 시스템에서만 사용된다.

One-to-One model (1:1)

하나의 유저 스레드에 하나의 커널 스레드를 맵핑한다. 따라서 여러 스레드가 병렬적으로 실행될 수 있으며, 한 스레드가 blocking system call을 해도 마찬가지이다.

다만 유저 스레드가 증가하면 커널 스레드도 비례하여 증가하기 때문에 시스템의 자원을 많이 소모한다.

Many-to-Many model (N:N)

이 모델에서는 유저 스레드의 수보다 작거나 같은 수의 커널 스레드가 존재한다. 커널 스레드의 수는 어플리케이션이나 하드웨어에 의해 결정된다.

병렬 수행이 불가한 1:1 모델과 자원 소모가 큰 N:1 모델의 단점을 보완한 모델이다. 프로그래머는 필요한 만큼 유저 스레드를 생성하면 그에 대응되는 커널 스레드가 생성되며, 한 스레드가 blocking system call을 수행해도 다른 스레드가 실행될 수 있다.

하지만 코어 수의 증가로 커널 스레드 수를 제한할 필요가 없어짐에 따라 대부분의 OS는 1:1 모델을 사용한다.

Thread library

스레드 라이브러리는 스레드를 생성/관리하기 위한 API를 제공한다. 스레드 라이브러리의 구현 방법은 크게 두 가지인데,

1. 유저 스페이스만을 위해 제공되는 라이브러리

   • 함수 호출 시 system call이 아닌 유저 스페이스에서의 local 함수 호출이다.

2. 커널 단계에서 제공되는 라이브러리

   • 함수 호출 시 커널에 대한 system call이 수행된다.

스레드 라이브러리는 크게 두 가지로 나뉜다.

1. Pthread

   • POSIX standard를 기반으로 하며, 마치 자바스크립트와 같이 기준이 되는 명세를 개발자가 구현하는 것이다.
   • 유닉스 계열에서 사용된다.

2. Windows thread

   • Windows OS에서 스레드를 관리하는 스레드 라이브러리이다.

Threading issues

멀티스레드 프로그램을 작성할 때 고려해야 할 사항은 크게 5가지이다.

1. Semantics of fork and exec

   • 스레드가 fork() system call을 수행해 새로운 프로세스를 생성하면 새 프로세스는 모든 스레드를 복제할 것인가? fork()를 호출한 스레드만 복제할 것인가?

   • 만약 fork() 이후 exec()을 수행한다면 fork()를 호출한 스레드만 복제해도 된다. exec()을 수행하면 프로세스의 메모리 영역이 초기화되기 때문이다.

   • 아니라면 전체 스레드를 복제해야 한다.

2. Signal handling

   • 시그널은 프로세스에게 특정 이벤트가 발생했음을 알리는 것이다.

   • 모든 시그널은 다음과 같은 패턴을 따른다.

     1. 시그널은 특정 이벤트에 의해 생성된다.
     2. 프로세스에 전달된다.
     3. 전달된 시그널은 프로세스에 의해 처리되어야 한다.

   • 시그널은 기본 시그널 핸들러 혹은 유저가 정의한 시그널 핸들러에 의해 처리된다.

   • 어떤 시그널은 무시될 수도 있고, 잘못된 메모리 접근과 같은 시그널은 프로그램을 종료시킬 수 있다.

   • 멀티스레드 프로그램에서는 어떤 스레드가 시그널을 받아야 하는지 결정해야 한다. 특정 스레드가 시그널을 받을 수도, 모든 스레드가 받을 수도 있다.

   • 동기 시그널의 경우 시그널을 야기한 스레드에 전달되고, 비동기 시그널은 상황마다 다르다. 프로세스 종료와 같은 시그널은 모든 스레드에게 전달된다.

3. Thread cancellation of target thread

   • 스레드는 완료되기 전에 강제 종료될 수 있다.

   • 예를 들어, 병렬로 DB를 탐색하다가 하나의 스레드가 결과를 찾으면 나머지 스레드는 종료된다.

   • 타겟 스레드는 종료되어야 하는 스레드를 말한다.

   • 비동기 취소는 다른 프로세스에 의해 즉시 종료되는 것이고, 연기(deffered)된 취소는 타겟 스레드가 스스로 종료되어야 하는지를 확인하고 순차적으로 종료하는 것이다.

   • 스레드 취소는, 취소되어야 하는 스레드에 자원이 할당되어 있거나, 스레드 간 공유 데이터를 갱신하는 동안 최소되는 경우를 고려해야 한다.

4. Thread-local storage (TLS)

   • 프로세스 내 스레드는 데이터를 공유한다. 다만 각 스레드가 본인만의 데이터를 필요로 하는 경우 TLS를 사용한다.
   • 지역변수와는 다른 개념이다. 지역변수는 단건의 함수 호출에서만 사용되지만 TLS는 여러 함수 호출에 걸쳐 사용된다.
   • TLS는 스레드별로 고유한 정적 데이터라고 생각할 수 있다.
   • 대부분의 스레드 라이브러리가 TLS를 지원한다.

5. Scheduler activations

   • 커널과 스레드 라이브러리 간 통신은 many-to-many model이나, two-level model에서 중요하게 고려되어야 한다.
   • N개의 유저 스레드를 M개의 커널 스레드에 어떻게 매핑할 것인가?
   • 이 문제를 해결하기 위해 Lightweight Process(LWP)가 중간에 위치한 자료구조로서 동작한다.
     • LWP는 커널 스레드 수를 동적으로 조절하여 최대의 성능을 낼 수 있게 한다.
     • 유저 스레드 라이브러리 입장에서 LWP는 유저 스레드를 스케줄링 하는 처리기로 보인다.
     • 커널 스레드마다 하나의 LWP가 연결된다. 이것은 OS가 프로세스에서 실행하기 위해 스케줄링하는 커널 스레드이다.
     • 커널 스레드가 block되면 LWP 또한 block되고, 마찬가지로 유저 스레드 또한 block된다.
   • 유저 스레드 라이브러리와 커널이 소통하는 방식은 scheduler activation으로 알려져 있고, 이를 위한 방법 중 하나는 upcall이다.
     • 커널은 어플리케이션에 LWP를 제공하고, 어플리케이션은 유저 스레드를 가용한 LWP로 스케줄한다. 또 커널은 어플리케이션에게 특정 이벤트에 대해 알린다.
     • Upcall은 스레드 라이브러리의 upcall handler에 의해 처리된다.
     • 스레드가 block되면
       • upcall이 발생한다. 커널은 어플리케이션에게 새로운 LWP를 할당한다.
       • 어플리케이션은 새로운 LWP에서 upcall handler를 실행한다. block된 스레드의 상태를 저장하고 사용하던 LWP를 반환한다.
       • upcall handler는 새로운 LWP에 다른 스레드를 스케줄한다.
     • 스레드 block이 해제되면
       • upcall이 발생한다. 커널은 어플리케이션에게 새로운 LWP를 할당하거나, 다른 스레드로부터 선점하여 upcall handler를 실행한다.