혼자 정리

[OS Concepts] 4. Threads& Concurrency 본문

운영체제이론

[OS Concepts] 4. Threads& Concurrency

tbonelee 2024. 3. 9. 17:03

'Operating System Concepts - 10th edition' 을 읽고 정리한 내용입니다.

4.1 Overview

  • CPU utlization의 기본 단위
    • 스레드 ID, 프로그램 카운터(PC), 레지스터 셋, 스택으로 구성
    • 동일 프로세스에 속한 다른 스레드와 코드 영역, 데이터 영역, 다른 OS 리소스(open file, signal 등)를 공유

4.1.1 Motivation

  • 멀티스레드 앱의 예시 :
    • 여러 의미지의 섬네일 생성을 위해 각 이미지마다 개별 스레드를 사용
    • 웹 브라우저에서 한 스레드는 네트워크 데이터를 수신하고, 다른 스레드는 이미지나 텍스트를 화면에 띄우는 역할을 할 수 있음
    • 워드 프로세서에서 화면을 띄우는 역할, 유저 입력을 받는 역할, 백그라운드에서 스펠링과 문법 체크 역할을 각각의 스레드로 할당할 수 있다.
  • 멀티코어를 활용하는 앱을 만들 수도 있음
    • CPU 집약적 작업을 멀티코어에서 병렬적으로 진행
  • 하나의 앱이 비슷한 작업을 반복하는 경우 멀티 스레딩이 유용
    • ex) 웹 서버의 요청 처리
      • 서버가 요청을 받았을 때 프로세스 생성을 할 수도 있지만, 동일 작업을 하는 프로세스 생성은 costly
      • 요청을 위한 스레드를 새로 생성해서 후속 요청은 해당 스레드에서 listen하여 처리하도록 하는 것이 더 효율적
  • 대부분의 OS 커널도 멀티 스레드를 사용
    • 시스템 부팅 시점에 리눅스는 여러 커널 스레드를 생성
      • ex) 장치 관리, 메모리 관리, 인터럽트 핸들링

    +-----------------------------------------------------------+
    |       code                data                files       |
    |-----------------------------------------------------------|
    |    registers      |    registers      |    registers      |
    |                   |                   |                   |
    |       stack       |       stack       |       stack       |
    |                   |                   |                   |
    |         PC        |         PC        |         PC        |
    +-------------------+-------------------+-------------------+
    |       ||          |      ||           |     ||            |
    |       ||  <-thread|      ||           |     ||            |
    |       \/          |      \/           |     \/            |
    +-----------------------------------------------------------+

4.1.2 Benefits

멀티스레드 프로그램의 네 가지 주요 장점

  1. Responsiveness
    • 블럭킹 작업이나 오래 걸리는 작업이 있어도 프로그램이 계속 실행될 수 있도록 하여 유저에 대한 반응성을 높일 수 있음
  2. Resource sharing
    • 기본적으로 프로세스의 메모리와 자원을 공유하므로 프로세스 간 리소스 공유에 비해 간편
  3. Economy
    • 프로세스의 리소스를 공유하므로 불필요하게 추가적인 메모리와 리소스 할당을 할 필요가 없음
    • 일반적으로 스레드 생성이 프로세스 생성보다 시간, 메모리 소모가 적음
    • 스레드 간 컨텍스트 스위칭이 프로세스 간 컨텍스트 스위칭보다 일반적으로 더 빠르다
  4. Scalability
    • 멀티 프로세서 아키텍쳐에서 별개의 스레드는 여러 프로세서에서 병렬적으로 돌 수 있기 때문에 싱글 스레드 프로그램에 비해 유리

4.2 Multicore Programming

  • 싱글 코어 환경에서 여러 스레드의 실행은 동시성(concurrency)은 여러 스레드의 실행을 시간에 따라 번갈아 가면서 실행하는 것을 의미(the execution of the threads will be interleaved over time)
  • 멀티 코어 환경에서는 병렬적(parallel)으로 실행 가능
  • concurrency와 parallelism의 구분
    • concurrent system은 하나 이상의 태스크가 계속 진행될 수 있도록 함
    • parallel system은 하나 이상의 태스크가 동시에 실행될 수 있도록 함
    • => parallelism 없는 concurrency 가능
      • 멀티프로세서와 멀티코어 아키텍쳐 등장 이전에는 싱글 프로세서만 존재
      • CPU 스케쥴러가 프로세스 간 빠른 스위칭을 통해 병렬성의 일루전을 만듦
        • 프로세스는 concurrently하게 실행되지만 parallel 하게 실행되지는 않음

4.2.1 Programming Challenges

멀티코어 시스템에 맞는 프로그래밍에는 다섯 가지 도전 과제가 존재

  1. Identifying tasks
    • 별개의 concurrent한 태스크로 나뉘어질 수 있는 영역을 파악하는 것이 필요
  2. Balance
    • 태스크 간 작업 밸류를 균등하게 나누는 것이 중요
    • 전체 프로세스에 별로 중요하지 않은 작업을 위해 별개의 코어를 사용하는 것은 낭비일 수 있다
  3. Data splitting
    • 나뉘어진 작업들에서 사용되는 데이터도 분리된 코어에서 실행될 수 있게 나뉘어야 한다
  4. Data dependency
    • 어떤 태스크가 다른 태스크의 데이터에 접근한다면 태스크의 실행은 동기화되어야 한다
  5. Testing and debugging
    • 멀티코어에서 병렬적으로 실행되는 프로그램은 아주 다양한 실행 경로를 가질 수 있다.
    • 이로 인해 테스팅과 디버깅은 더욱 어려워질 수 있다.

4.2.2 Types of Parallelism

  • Data parallelism
    • 동일한 데이터의 subset을 여러 연산 코어에 분산하여 동일한 작업을 각 코어에서 실행하는 유형
    • ex) 사이즈 $N$의 배열 원소의 합을 구하는 작업
  • Task parallelism
    • 각 스레드는 각자 유니크한 오퍼레이션을 수행 (같은 데이터를 사용할 수도, 아닐 수도)
  • 두 가지 타입은 상호 배타적인 것이 아님. 두 가지가 혼합된 경우도 충분히 가능

4.3 Multithreading Models

  • user threads
    • 유저 레벨에서 제공됨
    • 커널의 도움 없이 관리됨
  • kernel threads
    • OS가 직접적으로 관리
    • 모든 현대적인 OS는 커널 스레드를 지원
  • 유저 스레드와 커널 스레드 간에는 relationship 수립이 필요
    • 'many-to-one model', 'one-to-one model', 'many-to-many model'

4.3.1 Many-to-One Model

  • 여러 유저 레벨 스레드가 하나의 커널 스레드로 맵핑됨
  • 유저 영역의 스레드 라이브러리를 통해 스레드 관리가 이루어짐
    • 보다 효율적(어떤 측면에서?)
  • 단점
    • 스레드가 블락킹 시스템 콜을 호출하면 모든 프로세스가 블락될 수 있음
    • 한 번에 하나의 스레드만 커널에 접근할 수 있기 때문에 멀티코어 시스템에서 스레드가 병렬적으로 실행될 수 없음
  • ex) 자바 초기 버전에서 사용된 Green threads
  • 멀티코어가 보편화 된 시점에서 사용이 많이 줄어듦

4.3.2 One-to-One Model

  • 블락킹 이슈가 없고, 병렬적으로 실행될 수 있음
  • 유저 스레드 생성이 직접적인 커널 스레드 생성을 요구하므로 많은 커널 스레드로 인해 시스템 퍼포먼스에 부담이 될 수 있음
  • 리눅스와 윈도우즈 계열 OS에서 one-to-one 모델을 구현

4.3.3 Many-to-Many Model

  • 여러 유저 레벨 스레드를 그거보다 같거나 더 적은 수의 커널 스레드로 맵핑
  • 커널 스레드의 갯수는 특정 앱이나 머신에 따라 결정될 수 있음
    • ex) 어떤 앱은 4코어보다 8코어에서 더 많은 커널 스레드를 할당할 수 있음
  • 개발자는 원하는 만큼 유저 스레드를 생성 가능 (One-to-One 에서의 단점 해소)
  • 커널이 다른 스레드를 할당할 수 있으므로 유저 스레드의 블락킹 시스템 콜 호출로 전체 프로세스가 블락되지 않음 (Many-to-One의 단점 해소)
  • 멀티프로세서에서 병렬적으로 실행 가능 (Many-to-One의 단점 해소)
  • two-level model은 many-to-many의 구조를 가져가면서 one-to-one도 허용하는 모델
  • 구현하기 어렵다는 단점
  • 프로세싱 코어가 늘어가면서 커널 스레드 갯수의 한계는 덜 중요해져서 대부분의 OS는 one-to-one 모델을 채용
  • 그럼에도 불구하고 몇몇 동시성 라이브러리는 개발자가 태스크를 분별하여 many-to-many 모델을 사용한 스레드에 맵핑하도록 하고 있음

4.4. Thread Libraries

  • Thread library는 개발자가 스레드를 생성/관리할 수 있는 API를 제공
  • 스레드 라이브러리 구현의 두 가지 갈래
    • 유저 영역에 라이브러리를 제공하여 커널 지원을 받지 않는 방법
      • 라이브러리를 위한 모든 코드와 데이터 구조는 유저 공간에 존재
      • 라이브러리 함수 호출은 시스템 콜이 아닌 유저 영역의 로컬 함수 호출을 의미
    • OS가 지원하는 커널 레벨 라이브러리 구현
      • 라이브러리의 코드와 데이터 구조는 커널 영역에 존재
      • 라이브러리 API 호출은 보통 커널의 시스템 콜 호출로 이어짐
  • 주요 세 가지 스레드 라이브러리
    • POSIX Pthreads
      • 유저 레벨로 제공될 수도 있고, 커널 레벨로 제공될 수도 있음
    • Windows
      • 커널 레벨로 제공됨
    • Java
      • 보통 JVM이 호스트 OS 위에서 동작하므로 보통 호스트 OS에서 사용 가능한 스레드 라이브러리를 통해 구현됨
  • POSIX, 윈도우즈에서 전역적으로 선언된 데이터는 동일 프로세스 내의 스레드 간에 모두 공유됨
  • 자바는 전역 데이터 개념이 없으므로 공유가 필요한 데이터는 명시적으로 위치시켜야 한다
  • 스레드 생성의 두 가지 전략
    • asynchronous threading
      • 부모가 자식 스레드를 생성한 후 다시 작업을 재개
      • 각 스레드가 독립적이므로 보통 스레드 간 데이터 공유가 적음
      • 멀티스레드 서버, responsive한 유저 인터페이스에 많이 사용됨
    • synchronous threading
      • 부모 스레드가 하나 이상의 자식을 생성하고 모든 자녀가 종료한 후에 작업을 재개하는 전략
      • 부모가 생성한 스레드는 동시에 실행되지만 부모는 잠시 작업을 멈춤
      • 모든 스레드가 작업을 마치면 종료하고 부모에 join하게 됨
      • 모든 자식이 join한 후에 부모는 작업을 재개
      • 보통 많은 스레드 간 데이터 공유가 이루어짐
      • divide and conquer 전략?
  • 예제에서는 동기적 스레딩 전략을 사용

Pthreads

  • Pthreads : 스레드 생성과 동기화에 대해 정의한 POSIX standard를 일컬음
  • specification이지 implementation이 아님
  • 윈도우즈를 제외한 많은 시스템이 Pthreads를 구현

아래는 스레드 하나를 생성하여 양의 정수의 합을 구하는 예제 코드이다

#incldue <pthread.h>
#include <stdio.h>

#include <stdlib.h>

int sum; /* 공유 데이터 */
void *runner(void *param); /* 스레드가 실행할 함수 */

int main(int argc, char *argv[]) {
    pthread_t tid; /* 스레드 식별자 */
    pthread_attr_t attr; /* 스레드 속성 */

    /* 스레드의 기본 속성을 설정 */
    pthread_attr_init(&attr);
    /* 스레드 생성 */
    pthread_create(&tid, &attr, runner, argv[1]);
    /* 스레드 종료를 기다림 */
    pthread_join(tid, NULL);

    printf("sum = %d\n", sum);
}

/* 스레드가 실행할 함수 */
void *runner(void *param) {
    int i, upper = atoi(param);
    sum = 0;

    for (i = 1; i <= upper; i++) {
        sum += i;
    }

    pthread_exit(0);
}

Java Threads

  • 모든 자바 프로그램은 최소한 하나의 스레드로 이루어짐
  • 명시적으로 스레드를 생성하는 두 가지 방식
    • Thread 클래스를 상속받아 run() 메소드를 오버라이드
    • Runnable 인터페이스의 public void run() 메소드를 구현

다음은 Runnable을 구현한 Task클래스를 사용하는 예시

Thread workder = new Thread(new Task());
worker.start();
  • start() 메소드를 호출하면,
    • 메모리를 할당하고 JVM에 새 스레드를 초기화
    • run() 메소드를 호출하여 JVM에 의해 스레드가 실행되도록 함
try {
    worker.join();
}
catch (InterruptedException ie) { }
  • Pthreads와 Windows 라이브러리의 join 메소드와 동일하게 스레드 종료를 대기하기 위해 join() 메소드를 사용

4.5 Implicit Threading

  • 동시성/병렬 프로그래밍을 돕기 위해 스레드의 생성/관리를 애플리케이션 개발자에서 컴파일러, 런타임 라이브러리로 넘기는 전략이 등장 - implicit threading
  • 개발자가 병렬적으로 실행될 수 있는 것들을 (스레드가 아닌) 태스크로 구분해줘야 함
  • 그러면 런타임 라이브러리가 개별 스레드로 맵핑시켜준다. (보통은 many-to-many 모델 사용)
  • 개발자는 병렬 태스크를 구분. 라이브러리는 스레드 생성/관리를 담당

4.5.1 Thread Pools

  • 멀티 스레드로 웹 서버를 구성한다고 해보자
    • 서버가 요청을 받으면 처리하기 위해 별개의 스레드를 생성한다.
    • 이러한 스레드 생성은 두 가지 이슈를 만든다.
      1. 한 번 사용하고 버릴 스레드를 생성하기 위해 시간을 소모
      2. 시스템에 활성화된 스레드의 갯수 상한이 없기에 시스템 리소스를 소진시킬 수 있음.
  • 이를 개선하기 위해 thread pool 사용
  • 프로그램이 시작할 때 여러 스레드를 생성하여 풀에 놓고 필요할 때 가져다 쓰는 방식
  • 장점 :
    1. 스레드를 생성해서 쓰는 것보다 빠름
    2. 동시에 존재할 수 있는 스레드 갯수를 제한할 수 있음
    3. 태스크의 실행을 생성 메커니즘과 구분함으로써 태스크의 실행 전략을 달리할 수 있음 (ex. 일정 시간 지연 후에 실행되도록 스케쥴링, 주기적으로 실행하도록)
  • 풀의 스레드 갯수는 시스템의 CPU 갯수, 물리 메모리 갯수, 예상되는 동시적 클라이언트 요청 갯수 등을 바탕으로 휴리스틱하게 결정.
    • 동적으로 조정되도록 할 수도 있음

4.5.2 Fork Join

  • main 부모 스레드는 하나 이상의 스레드를 생성(forks)하고 자식이 종료하고 join하기를 기다린다. 그러면 그 결과들을 받아서 합치게 된다.
  • 이러한 동기적 모델은 명시적 스레드 생성으로 구현할 수도 있지만 implicit 스레딩으로도 가능하다.
    • 스레드 생성/관리는 라이브러리가 관리
  • 자바 1.7에서 도입된 fork-join 라이브러리는 recursive divde-and-conquer 알고리즘에 활용될 수 있다.

4.6 Threading Issues

4.6.1 The fork() and exec() System Calls

  • 모든 스레드를 복사하는 fork (fork())와 호출한 스레드만 복사하는 fork (pthread_atfork())가 존재
  • exec()를 호출하면 모든 프로세스를 덮어씌우니 스레드도 덮어씌우게 됨
  • 따라서 fork 후 exec()를 호출할 것이면 모든 스레드를 복제하는 것은 불필요.
  • 만약 fork 후 exec()를 호출하지 않는다면 모든 스레드를 복제해야 함

4.6.2 Signal Handling

  • signal : UNIX 시스템에서 특정 이벤트 발생을 프로세스에게 알리는 용도로 사용됨
  • 이벤트의 근원과 이유에 따라 동기적으로도 비동기적으로도 받을 수 있음
  • 모든 시그널은 다음 패턴을 가짐
    1. 시그널은 특정 이벤트의 발생을 통해 생성됨
    2. 시그널은 프로세스에 전달됨
    3. 전달된 시그널은 처리되어야 함
  • illegal memory access, division by 0 등이 동기적 시그널의 예시
    • 동기적 시그널은 시그널을 발생시킨 오퍼레이션을 실행한 프로세스에 전달된다
  • 시그널이 실행중인 프로세스 외부의 이벤트에 의해 생성되면 프로세스는 비동기적으로 시그널을 받는다.
    • 컨트롤 + c 신호, 시간 만료 등의 이벤트가 예시
    • 보통 비동기 시그널은 다른 프로세스로 전달된다.
  • 시그널은 두 가지 핸들러에서 처리 가능
    1. 기본 시그널 핸들러
    2. user-defined 시그널 핸들러
  • 모든 시그널은 커널이 실행하는 default signal handler를 가진다.
  • default action은 user-defined signal handler를 통해 오버라이드될 수 있다.
  • 프로세스가 여러 스레드를 가지는 경우 시그널을 전달할 수 있는 여러 옵션이 존재하게 된다.
    1. 시그널이 적용되는 스레드에 전달
    2. 프로세스의 모든 스레드에 전달
    3. 프로세스의 몇몇 스레드에 전달
    4. 특정 스레드가 프로세스의 모든 시그널을 받도록 할당
  • 동기적 시그널은 원인을 제공한 스레드에 전달하면 되므로 명확
  • 비동기적 시그널은 처리 방식이 명확하지 않다.
    • 프로세스 종료 등의 몇몇 비동기 시그널은 모든 스레드에 전달되어야 한다.
    • 대부분의 UNIX 멀티스레딩은 스레드마다 허용할 시그널과 블럭할 시그널을 정할 수 있도록 해놓았다.
      • 따라서 몇몇 케이스에서 비동기 시그널은 블럭하지 않는 스레드로 보내져야 한다.
      • 하지만, 시그널은 한 번만 핸들링되어야 하므로 보통 블럭하지 않는 첫 스레드로 보내지게 된다.

4.6.3 Thread Cancellation

  • Thread cancellation : 스레드가 완료되기 전에 종료시키는 것

  • Target thread : 취소 대상 스레드

  • 스레드 취소 방식 두 가지 :

    • Asynchronous cancellation
      • 하나의 스레드가 다른 스레드를 즉시 종료시킴
    • Deferred cancellation
      • 타겟 스레드가 주기적으로 종료해야 하는지 체크
      • 종료해야 할 때 정리해야 할 것들을 잘 정리하고 종료할 수 있음

  • Asynchronous cancellation 단점

    • 할당된 시스템 리소스 반환이 제대로 이루어지지 않을 수 있음
    • 다른 스레드와 공유하던 데이터를 업데이트하던 중에 종료되면 문제가 생길 수 있음

      Pthreads 예시

  • pthread_cancel(tid) 를 통해 스레드 취소를 init할 수 있음

    • 그저 취소 요청을 큐에 넣는 역할

  • pthread_join()을 통해 종료를 기다릴 수 있음

    • 스레드가 종료되면 해당 함수는 return

  • 취소 요청을 받은 스레드는 cancel state와 cancel type에 따라 취소 진행 여부, 취소 방식을 결정

    • Cancel state가 비활성화되어 있으면 취소 요청은 계속 큐에 남아 있게 된다.
    • 활성화되어 있으면 cancel type에 따라 취소 방식을 결정
      • Deferred cancellation type인 경우 스레드가 cancellation point에 다다른 경우에 취소가 진행됨
      • Pthreads는 cancellation point인 함수를 명시하고 있고, 해당 함수 중 하나가 호출되면 취소가 진행됨
        • 많은 POSIX, 표준 C 라이브러리의 블라킹 함수가 여기에 속함 (ex. read())
        • 스레드가 cancellation point 중 하나인 pthread_testcancel()을 호출하여 취소를 진행시키기도 함(취소 요청이 없는 경우 함수 호출은 아무 효과 없이 지나간다)

  • cleanup handler를 등록하여 스레드가 종료될 때 정리 작업이 이루어도록 할 수도 있다.

Mode State Type
Off Disabled -
Deferred Enabled Deferred
Asynchronous Enabled Asynchronous

4.6.4 Thread-Local Storage

  • TLS를 통해 스레드에 고유한 데이터를 만들 수 있다
  • 로컬 변수 같아 보이지만 로컬 변수는 하나의 함수 안에서만 접근 가능하지만 TLS는 전역적으로 접근 가능
  • 스레드 풀과 같이 개발자가 implicit한 테크닉을 사용할 때는 추가적인 작업이 필요하다. (ex. TLS가 초기 상태인지 체크?)

4.6.5 Scheduler Activations

  • 유저-커널 스레드 간에 m : n 관계가 있을 때 유저 레벨 스레드 라이브러리와 커널 간의 커뮤니케이션을 도와주는 방법
  • LightWeight Process(LWP)
    • 커널과 유저 스레드 라이브러리 사이의 중간 역할
    • 유저 스레드는 LWP를 하나의 가상 프로세서로 간주하여 유저 스레드를 맵핑
    • 하나의 커널 스레드에 부탁되어 있고, OS가 물리 프로세서에 스케쥴링하면 실행됨
    • 커널 스레드가 I/O wait 등으로 블럭되면 LWP와 거기에 부착된 유저 스레드도 블럭된다
  • 애플리케이션에 적절한 LWP의 수는 다양할 수 있다.
    • 싱글 프로세서에서 실행되는 CPU 집약적인 앱은 하나의 LWP로 충분 (어차피 한 번에 하나의 스레드만 실행 가능하므로)
    • I/O 집약적인 앱은 많은 LWP 필요
  • LWP는 동시에 존재하는 각각의 블로킹 시스템 콜 호출마다 필요하다.
    • 프로세서에 네 개 LWP가 있는 상황에서 모두 I/O 입출력 완료를 대기 중이라면, 다섯번째 요청은 그 중 하나의 LWP가 리턴하기를 기다려야 한다.
  • 유저 스레드 라이브러리와 커널은 scheduler activation을 통해 커뮤니케이션
    • 커널이 애플리케이션에 가상 프로세서 집합(LWPs)을 제공
    • 애플리케이션은 유저 스레드를 사용 가능한 가상 프로세서에 스케쥴
    • 이벤트가 발생하는 경우 커널은 upcall로 정보를 전달해줌
      • upcall은 스레드 라이브러리가 upcall handler를 통해 처리해야 하고, upcall handler 또한 가상 프로세서에서 실행되어야 한다.
      • upcall 예시1 (블로킹)
        • 애플리케이션 스레드가 블럭되는 경우, 커널은 스레드가 블럭되는 것과 어떤 스레드가 블럭되는지 알려준다.
        • 커널은 새 가상 프로세서를 앱에 할당
        • 앱은 upcall handler를 새 가상 프로세서에서 실행
          • upcall handler는 블로킹 스레드의 상태를 저장하고 블로킹 스레드가 실행 중이던 가상 프로세서를 놓아준다
          • 그리고 upcall handler는 실행할 수 있는 다른 스레드를 새 가상 프로세서에 할당
      • upcall 예시2 (블로킹 스레드가 대기하고 있던 이벤트 발생)
        • 커널은 upcall을 통해 스레드 라이브러리에 아까 블럭된 스레드가 이제 실행될 수 있다고 알려준다
        • 커널은 새 가상 프로세서를 할당하거나 유저 스레드 중 하나를 preempt하여 그 위에서 upcall handler를 실행할 수 있도록 한다.
        • 블로킹된 스레드가 이제 실행 가능하므로 애플리케이션은 이제 가능한 가상 프로세서에서 이를 실행한다.

4.7 Operating-System Examples

4.7.1 Windows Threads

'운영체제이론' 카테고리의 다른 글

[OS Concepts] 5. CPU Scheduling  (0) 2024.03.09
[OS Concepts] 3. Processes  (0) 2024.03.03
[OS Concepts] 2. Operating-System Structures  (1) 2024.02.05
[OS Concepts] 1. Introduction  (1) 2024.01.28
'운영체제이론' Related Articles more