[OS] concurrency and thread

Concurrency(병행성)

• 응용 프로그램에서 병행성의 사용은 여러 이점을 가진다.
• 병행성은 병행적인 프로세스들의 집합으로서 응용 프로그램을 구조화함으로써 구현될 수 있다. (e.g. fork()의 사용)

Overhead in Process Model

• 여러 개의 프로세스를 사용하는 모델에서 각각의 프로세스는 독립적이다. 따라서 통신을 위해서는 커널을 통한 IPC가 필요하다. 이는 오버헤드가 크다.
• 또한 이 모델에서 PCB(Process Context Block)는 큰 크기를 가지고 있어, 각각의 프로세스의 생성과 context switching에 오랜 시간이 걸린다.

What is Thread?

• 스레드는 CPU 스케줄링의 기본 단위 또는 한 프로세스 안에서 제어의 흐름이다. 그리고 PC, 레지스터 집합, 스택 공간으로 이루어져 있어 프로세스와 유사하지만 오버헤드를 줄일 수 있도록 크기가 더 작다.
• 각각의 스레드는 자신만이 레지스터 상태와 스택을 가진다.
• 같은 프로세스 안에서 여러 스레드가 생성될 수 있고, 프로세스를 위한 코드와 주소 공간 그리고 운영 자원을 공유할 수 있다.
• 스레드가 실행되는 환경을 task라고 부르며 전통적 프로세스(heavyweight)는 한 스레드가 있는 하나의 task와 같다.
• 스레드는 작은 context를 사용함으로써 생성과 switching에 드는 비용을 줄일 수 있다.

위의 그림에서 왼쪽의 single-threaded process는 기존의 process와 같다. 오른쪽의 multithreaded process는 기존의 PCB보다 훨씬 작은, 여러 개의 TCB를 가지며 공유된 데이터를 통해 통신을 더 쉽게 할 수 있다. 이로 인해 context switching도 더 쉬워진다.

Multithreading(Single Processor)

• 병행성을 달성한다. (병렬적인 것처럼 보인다!)
  • 두 task는 그들이 병렬적으로 수행되는 것처럼 보이나 실제로는 한 시점에 둘 중에 하나만 수행되고 있을 때 병행성을 이루었다고 한다.
  • 이는 하나의 프로세서 시스템에서도 계산 속도를 증가시키는데, 왜냐하면 만약 I/O bound 스레드 블록이 있다면, 커널은 같은 프로세스의 다른 스레드로 switch하기 때문이다.

Multithreading (Multiple Processor or Cores)

• 병렬성을 달성한다. (동시에 여러 스레드를 실행한다.)
  • 두 task는 그들이 동시에 수행될 때 병렬성을 이루었다고 한다.
  • 한 프로세스의 스레드들도 다른 프로세서나 코어(멀티코어)에서 병렬적으로 실행될 수 있다.
  • CPU의 병렬성이 아니라 코어에서 병렬성을 말한다.

Benefits (of threads)

• 병행성(single process)과 병렬성(multi process)을 달성한다.
• 계산과 I/O을 오버랩한다.
• MP 아키텍쳐의 효용성을 높인다.
• 반응적이다.
• 자원을 공유한다.
• 경제적이다.

• Example 1 (Multithreaded Program)

/* Multithreaded Program - 1 */
#include <pthread.h>
#include <stdio.h>

int sum;

void *runner(void *param)
{
    int i, upper = atoi(param);
    sum = 0;
    
    for(i = 1; i <= upper; i++)
        sum += i;
    
    pthread_exit(0);
}

/* Multithreaded Program - 2 */

int main(int argc, char *argv[])
{
    pthread_t tid; /* thread identifier */
    pthread_attr_t attr; /* set of thread attributes */
    
    if(argc != 2){
        fprintf(stderr, "usage: a.out <integer value>\n"); return -1;
    }
    if(atoi(argv[1]) < 0){
        fprintf(stderr, "%d mush be >= 0\n", atoi(argv[1])); return -1;
    }
    pthread_attr_init(&attr); /* get the default attributes */
    pthread_create(&tid, &attr, runner, argv[1]); /* create thread */
    pthread_join(tid, NULL); /* wait for the thread to exit */
    
    printf("sum = %d\n", sum);
}

• 또 다른 예시로 multithreaded server가 존재한다. 스레드의 사용이 가장 효과적인 영역 중 하나는 I/O가 섞여 있는 응용 프로그램이라고 할 수 있다.

Multithreaded server

계속 request를 만들어내는 클라이언트가 존재한다고 가정해 보자. 이 클라이언트의 요청을 수행하는 서버는 스레드를 생성해서 요청을 받아들인다.

• 싱글 프로세서를 사용하는 서버이고, 프로세싱에 2ms, input-output delay에 8ms가 소요된다고 가정하면 하나의 스레드는 1초에 100개의 요청으로 처리할 수 있다.

• 스레드가 2개라고 가정해 보자. 1번 스레드가 프로세싱을 마치고 8ms 동안의 input-output delay가 있는 동안 2번 스레드가 2ms의 프로세싱을 수행할 수 있다. 이 경우 1초에 125개의 요청을 처리할 수 있게 된다.

• 이번엔 I/O에 걸리는 시간을 줄이기 위해 cache를 사용한다고 가정해 보자. hit ratio가 75%라고 가정하면, 평균 I/O 시간은 (0.75x0 + 0.25x8)로 2ms가 된다. input-output delay가 2ms가 되는 것이다. 이때에는 1초에 500개의 요청을 처리할 수 있다.

즉, 여러 개의 스레드를 사용하면 요청을 처리하는 데에 걸리는 시간을 크게 단축시킬 수 있다.

User-level vs kernel-level Thread

• User-level threads: 유저 레벨에서 라이브러리 호출을 통해 커널 위에서 유지된다.

  • 스레드 관리가 유저 레벨에서 된다.

  • 커널 모드로 전환할 수 없고, 빠르며 간편하다.

  • 애플리케이션에 특화된 스케줄링이 가능하다.

  • Blocking problem이 있다

    • 하나의 스레드에서 I/O 처리를 하기 시작했을 때 다른 스레드에서 다른 일을 하게 할 수 없다.
    • 멀티프로세서의 concurrency를 유지할 수 없다. 커널이 스레드의 존재를 모르기 때문이다.

  • 멀티프로세서의 이점을 누릴 수 없다.

• Kernel-level threads: 운영체제 안, 즉 커널 안의 함수를 사용한다.

  • 커널에 의해 관리된다.
  • 유저 레벨 스레드와 비교해서 느리다.
  • Blocking problem이 없다.
  • 대부분의 현대 OS들은 커널을 지원한다.

• 유저와 커널 스레드 사이에 관계가 있어야 한다.

Multithreading Models(Mapping Model)

• Thread libraries: 스레드를 생성하고 관리하기 위한 API이다. Mapping은 이 라이브러리에 의해 가능해진다. 유저 레벨과 커널 레벨의 라이브러리가 해 주는 일에 차이가 있다.

  • user level lib: No mapping, 유저 레벨의 스레드가 여러 개 생성되어 있어도 커널은 스레드 하나만이 존재한다고 생각한다.
  • kernel level lib: mapping, 매핑에는 다양한 방식이 존재한다.

Thread Mapping and scheduling

• 유저 레벨에서의 스케줄은 thread library를 통해 커널 레벨 스레드와 매핑됨으로써 수행된다.
• 커널 레벨의 스케줄은 물리적 CPU 혹은 코어들과 커널 레벨의 스레드들이 (OS) 커널을 통해 매핑됨으로써 수행된다.

• 병렬 실행

  • Virtual processor(커널 레벨 스레드)에 있는 스레드의 병행성
  • 물리적 코어들에 있는 스레드의 병행성

• 실제 병렬성

  • 하나의 스레드 : 하나의 코어의 1:1 관계로 가능하다.
    • thread pinning을 통해 스레드에 매핑될 CPU를 지정할 수 있다.

Threading Issues

Semantics of fork() and exec

fork()는 부른 스레드만을 복사할까, 모든 스레드를 복사할까?

• 만약 exec()이 fork() 이후에 바로 호출되면, 모든 스레드를 복사할 필요가 없다. (exec()이 모든 스레드를 포함해서 전체의 프로세스를 대신하기 때문이다.)
• 그렇지 않다면 프로세스는 모든 스레드를 복사해야 한다.

Signals(software interrupt)

UNIX 시스템에서 시그널들은 프로세스에게 부분적인 이벤트가 발생했음을 알리기 위해 사용된다.

• 받는 것은 소스와 시그널에 이유에 달렸다.
  • 동기적 시그널(Synchronous signals)은 시그널을 발생시킨 동작을 수행한 프로세스에 전달된다. (e.g. illegal memory access, division by 0)
  • 비동기적 시그널(Asynchronous signals)은 동작 중인 프로세스 바깥에서 발생한 이벤트에 의해 발생된다. (e.g Ctrl+C와 같은 특정한 키의 사용으로 프로세스를 끝내기)

Signal handling

• 하나의 스레드를 가진 프로그램에서의 signal handling:
  • 시그널은 특정 이벤트에 의해 생성된다.
  • 시그널은 프로세스로 전달된다.
  • 시그널은 default signal handler나 user-defined signal handler에 의해 처리된다.
• 여러 개의 스레드를 가진 프로그램에서의 signal handling:
  • 시그널을 시그널을 적용할 스레드에 전달한다. (e.g. synchronous signals)
  • 시그널을 프로세스의 모든 스레드에 전달한다. (e.g. process termination signal)
  • 시그널을 프로세스의 특정 스레드에 전달한다. (e.g. some asynchronous signals to non-blocking threads)
  • 특정 스레드에 프로세스로 전달되는 모든 시그널을 받도록 할당한다.

Thread Cancellation

스레드가 일을 마치기 전에 끝내려고 할 때 두 가지의 일반적인 접근법이 존재한다.

• Asynchronous cancellation은 목표가 된 스레드를 즉시 끝낸다.
• Deferred cancellation은 목표가 된 스레드가 취소되어야 하는지 주기적으로 확인하게 해 준다.

Thread Pools & Thread Local Storage

스레드가 필요할 때마다 매번 스레드를 생성하면 오버헤드가 발생할 수 있다. 이를 방지하기 위해 스레드를 pool 방식으로 구현해서 일정 개수를 미리 생성해 두고 그 개수를 초과하면 새로 생성한다. 이 경우에는 스레드가 할 일을 마치면 다시 원래의 개수로 돌아간다.

• Thread pools
  • 할 일을 기다리는 많은 스레드가 존재하는 풀을 만든다.
  • 이점
    • 새 스레드를 생성하는 것보다 요청에 응답하는 게 조금 더 빨라진다.
    • 애플리케이션에 존재하는 스레드의 개수를 풀의 크기에 제한할 수 있다.
• Thread Local Storagd(TLS)
  • 각각의 스레들이 자기 자신만의 데이터를 가지게 한다.