Thread Scheduling & Multiple-Processor Scheduling

이전 글인 Scheduling Algorithms에서 process scheduler를 다뤘다. process scheduler는 오직 kernel thread의 scheduling을 다룬다. 이번 글은 user thread가 어떻게 thread 라이브러리에 의해 kernel thread에 사상(mapping)되는지 살펴볼 것이다. (무슨 말인지 모르겠다면 Multi Thread Programming 글의 Multithreading Models 항목을 보자)

1. Contention Scope

Many-to-One, Many-to-Many 모델을 구현하는 시스템에서는 동일한 process에 속한 user thread들끼리 CPU를 경쟁하기 때문에 Process-Contention Scope(PCS)가 발생한다. 따라서 thread library를 이용해 scheduling 및 관리돼야 한다.

어떤 kernel thread가 CPU에 사상될 것인지는 System-Contention Scope(SCS)에 관련 있다. Windows, Solaris, Linux 같은 One-to-One 모델은 오직 SCS만을 사용한다.

PCS scheduling은 전형적으로 우선순위에 의해 이루어진다. 프로그래머는 thread의 우선순위를 정할 수 있고, thread library는 가장 높은 우선순위를 가진 thread를 선택한다. thread의 우선순위가 같은 경우 현재 실행 중인 thread를 선점한다. 이 경우, 우선순위가 같아도 Round-Robin 처럼 time-slicing을 해줄지는 미지수이다.(보장되지 않는다.)

2. Pthread Scheduling

POSIX Pthread library는 Contention Scope의 명시를 위해 PCS 또는 SCS를 지정할 수 있다.

* PTHREAD_SCOPE_PROCESS는 PCS scheduling을 사용하여 thread를 schedule한다. Many-to-Many, Many-to-One 모델에서 시스템 정책에 따라 LWP로 schedule한다. 

* PTHREAD_SCOPE_SYSTEM은 SCS scheduling을 사용하여 thread를 schedule한다. One-to-One 모델은 따로 처리할 것이 없지만, Many-to-Many 모델을 사용하는 시스템은 LWP를 kernel thread와 1:1로 매칭할 수 있도록 생성하고 LWP에 user thread를 바인딩함으로써 One-to-One 모델을 사용하는 효과를 낸다.

LWP는 light-weight process의 줄임말로, Solaris와 NetBSD 등(Many-to-Many 사용하는 시스템)에서 사용하는 용어이다. Linux, Windows, FreeBSD에선 thread와 같다.

* pthread_attr_setscope(pthread_attr_t* attr, int scope)

* pthread_attr_getscope(pthread_attr_t* attr, int* scope)

위 두 함수는 Contention Scope를 지정하고, 가져올 수 있는 함수이다. 아래는 Contention Scope를 다루는 예제이다.

#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS 5

int main(int argc, char* argv[])
{
    int i, scope;
    pthread_t tid[NUM_THREADS];
    pthread_attr_t attr;

    /* get the default attributes */
    pthread_attr_init(&attr);

    /* first inquire on the current scope */
    if(pthread_attr_getscope(&attr, &scope) != 0)
        fprintf(stderr, "Unable to get scheduling scope\n");
    else {
        if(scope == PTHREAD_SCOPE_PROCESS)
            printf("PTHREAD_SCOPE_PROCESS"); // SCS
        else if(scope == PTHREAD_SCOPE_SYSTEM)
            printf("PTHREAD_SCOPE_SYSTEM"); // PCS
        else
            fprintf(stderr, "Illegal scope value.\n");
    }

    /* set the scheduling algorithm to PCS or SCS */
    pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

    /* create the threads */
    for(i = 0; i < NUM_THREADS; i++)
        pthread_create(tid[i], &attr, runner, NULL);

    /* now join on each thread */
    for(i = 0; i < NUM_THREADS; i++)
        pthread_join(tid[i], NULL);

    return 0;
}

/* Each thread will begin control in this function */
void* runner(void* param)
{
    /* do some work */
    pthread_exit(0);
}

pthread_attr_setscope 함수로 Contention Scope를 PCS 또는 SCS로 지정할 수 있다. 하지만 Windows, Linux 같은 시스템은 One-to-One 모델을 사용하므로 SCS로만 지정할 수 있음을 알아두자.

지금까지 single-processor를 가진 시스템에서 CPU를 scheduling 하는 문제를 다뤘다. multiple-processor를 지원하는 시스템에서는 scheduling이 더 복잡해진다. 왜냐면 여러 개의 CPU를 항상 사용 중인 상태로 유지해야 되고, 효율적으로 사용해야 하기 때문이다. Load sharing 기법은 process를 특정 처리기에 고정시키지 않도록 하여 다중 처리기의 균형을 맞추는 것이다. Load sharing이 이루어져야 다중 처리기를 효율적으로 사용할 수 있다.

이 글에선 기능이 동일한(homogeneous) 경우만 다룬다.

3. Approaches to Multiple-Processor Scheduling

다중처리기 시스템의 CPU scheduling 방법에는 asymmetric multiprocessing(ASMP), symmetric multiprocessing(SMP) 두 가지가 있다. 

ASMP는 하나의 처리기가 모든 scheduling 결정과 kernel code의 실행을 담당하고, 나머지 처리기들은 사용자 코드만을 실행한다. 단지 하나의 처리기만 시스템 자료구조에 접근하므로, system data를 공유할 필요가 없어서 간단하다.

SMP는 각 처리기가 독자적으로 scheduling한다. 모든 process는 공동의(common) ready queue 또는 각 처리기의 ready queue에 있게 된다.

거의 모든 현대 OS(Windows, Solaris, Linux, Mac OS X 등)들은 SMP를 지원한다.

4. Processor Affinity

처리기들은 cache memory를 가질 수 있다. 처리기에 의해 가장 최근에 접근된 데이터가 그 처리기의 cache를 채우게 된다. 만약 process가 context switch를 하는데 다른 처리기로 옮겨간다면, 원래 처리기의 cache에 있던 내용은 무효화(invalidate) 되어야 하고, 새로운 처리기의 cache에 다시 채워야(reload) 한다. cache를 무효화하고 다시 채우는 작업은 비용이 크므로, 대부분의 SMP 시스템은 process를 같은 처리기에서 실행시키려고 한다. 이런 현상을 Processor Affinity라고 한다.

Soft Affinity는 process가 같은 처리기에서 처리되도록 하지만 보장은 되지 않는다. (이주할 수도 있다.) Linux같은 OS는 Hard Affinity를 지원하며, system call을 통해 process는 다른 처리기로 이주하지 않는다고 명시할 수 있다.

5. Load Balancing

SMP 시스템에서 처리기가 하나 이상인 것을 최대한 활용하려면, 부하를 모든 처리기에게 균등하게 배분하는 것이 매우 중요하다. 그래야만 어떤 처리기가 유휴상태인데, process가 대기중인 상태를 방지할 수 있기 때문이다. Load Balancing은 SMP 시스템의 모든 처리기 사이에 부하가 고르게 배분하도록 하는 작업이다.

common ready queue만 가지고 있는 시스템은 한 처리기가 쉬게 되면 곧바로 common ready queue에서 새로운 process를 선택하여 CPU에 할당하기 때문에, Load Balancing이 필요없다. 하지만 SMP를 지원하는 대부분의 OS는 각 처리기가 자신만의 ready queue를 가지고 있으므로 Load Balancing이 필요하다는 것을 명심하자.

Load Balancing은 push migration과 pull migration 두 가지 방식으로 이루어진다. push migration은 특정 task가 주기적으로 각 처리기의 부하를 검사하고, 과부하 처리기가 있으면 process를 덜 바쁜 처리기로 이동한다. 반대로, pull migration은 쉬고 있는 처리기가 과부하 처리기에서 process를 자기 쪽으로 가져온다. push migration과 pull migration은 상호 배타적이지 않다. 예를 들어, Linux의 ULE scheduler는 두 방식 모두를 구현하며, Linux는 200ms 마다 push migration 또는 pull migration을 하여 Load Balancing을 한다.

Load Balancing은 Process Affinity에 반대되기 때문에 주의 깊게 관리되지 않으면, 캐시 메모리에 존재하는 데이터를 활용하는 이점을 완전히 없앨 수도 있다. 어떤 정책이 최선이냐는 절대적인 규칙은 없지만, 한 가지 옵션은 처리기들의 불균등 상태가 임계값(threshold)을 넘을 때만 process를 migration 시킨다.

6. Multicore Processor

SMP 시스템은 다수의 처리기가 다수의 kernel thread를 동시에 실행하도록 한다. CPU의 최근 경향은 하나의 chip 안에 여러 개의 core를 장착하는 것이다. 각 코어는 구조적인 상태를 유지하기 위한 레지스터 집합을 가지고 있어서 OS 입장에서는 별개의 처리기로 보이게 된다. 이런 구조를 Multicore Processor라고 한다. Multicore Processor를 사용하는 SMP 시스템은 각 프로세서가 자신의 chip을 갖는 시스템에 비해 속도가 빠르고 적은 전력을 소모한다.

Multicore Processor는 scheduling 문제를 복잡하게 한다. 아래 그림 1처럼 process가 memory에 접근할 때 cache에 존재하지 않아서 많은 시간(최대 50%)을 기다려야하는 문제가 생기기 때문이다. (cache miss)

[그림 1] Memory Stall

위와 같이 데이터를 사용하기 위해 기다리는 현상을 Memory Stall이라고 한다. Memory Stall을 없애기 위해 최근 하드웨어 설계에서는 하나의 core에 여러개의 hardware thread를 집어넣는다. (예를 들면, Intel의 hyper-threading) 이 구조에서는 한 thread가 memory로부터 데이터를 사용할 수 있을 때까지 기다릴 때, core는 다른 hardware thread로 전환할 수 있다. 이런 구조를 Multithreaded Multicore System이라고 부른다. 아래 그림2는 Multithreaded Multicore System에서 Memory Stall을 해결하는 것을 도시하고 있다.

[그림 2] Multithreaded Multicore System

OS 관점에서 hardware thread는 하나의 처리기로 보인다. 따라서 dual-threaded, dual-core 시스템에서는 4개의 처리기가 OS에게 제공된다. 일반적으로 처리기를 multi-thread화하는 데에는 크게 2가지 방법이 있다.

* coarse-grained multithreading: 한 thread가 Memory Stall과 같은 이유로 block될 때까지 hardware thread를 switch하지 않는다. 다른 hardware thread가 실행되기 전에 명령어 파이프라인이 완전히 정리되어야 하므로, Context Switching 비용이 상당히 많이 든다.

* fine-grained multithreading: 명령어 단위의 주기처럼 작은 주기로 thread switching이 일어난다. 그러나 thread-switching을 지원하는 구조로 이루어져 있어서, overhead가 상대적으로 적다.

multi-threaded multi-core 시스템에서는 kernel level에서 두 단계의 scheduling이 필요하다.

* 어떤 kernel thread가 hardware thread(logical processor)에서 실행될 지 결정하는 scheduling: Scheduling Algorithms 글에서 설명한 scheduler(process scheduler)를 사용할 수 있다.

* 각 core가 어떤 hardware thread를 실행시킬 지 결정하는 scheduling: 여러가지 정책이 있는데, UltraSPARC T1 processor는 Round-Robin Algorithm을 사용한다. Intel의 Itanium은 dual-threaded dual-core processor이다. 각 hardware thread는 0~7의 urgency 값을 가지며, thread switching을 발생시키는 5가지의 event가 발생하면 urgency 값을 비교하여 높은 hardware thread를 core에 할당한다.

 

* 참고

CPU scheduling

https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6_CPU_Scheduling.html