핵심 질문: 일반적인 병행성 관련 오류들을 어떻게 처리하는가 병행성 버그는 몇개의 전형적인 패턴을 갖고 있다. 튼튼하고 올바른 병행 코드를 작성하기 위한 가장 첫 단계는 어떤 경우들을 피해야 할지 파악하는 것이다.

1. 오류의 종류

복잡한 병행 프로그램에서 발생하는 오류들은 어떤 것들이 있는가? Lu의 연구결과를 보자.

이런 종류의 오류 (비 교착 상태와 교착 상태) 들에 대해 좀 더 자세히 알아보자.

비 교착 상태 오류

Lu의 연구 결과를 따르면, 비 교착 상태 오류가 병행성 관련 오류 과반수를 차지한다. 비 교착 상태 오류의 분류 중 대표적인 원자성 위반과 순서 위반 오류를 살펴보자.

원자성 위반(atomicity violation) 오류

// Thread 1::
if (thd−>proc_info) {
    . . .
    fputs(thd−>proc_info, . . . ) ;
    . . .
}

// Thread 2::
thd−>proc_info = NULL;

쓰레드 1은 thd→proc_info가 NULL인지 검사하고 값을 출력한다. 쓰레드 2는 그 값을 NULL로 바꾼다.

쓰레드 1이 NULL인지 검사 후, fputs()를 호출하기 직전에 쓰레드 2로 인터럽트 되어 info가 NULL로 설정될 수 있다. 이후 스레드 1이 실행할 때 NULL 포인터 역참조가 발생해 프로그램이 크래시될 것이다.

다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성(serializability)이 보장되지 않았다. 즉 코드의 일부에 원자성이 요구되었으나, 실행 시에 그 원자성이 위반되었다.

현재 예제 코드는 ”proc_info 필드의 NULL 값 검사와 fputs() 호출 시 proc_info를 인자로 사용”하는 동작이 원자적으로 실행되는 것 (atomicity assumption)을 가정했다. 이 가정이 깨지면, 코드는 의도한 대로 작동하지 않는다.

코드를 어떻게 수정하면 작동할까? 락을 추가하여 어느 쓰레드든 proc_info 필드 접근 시 락을(proc_info_lock) 획득하도록 한다. 이 자료 구조를 사용하는 다른 모든 코드들도 락으로 보호해야 한다.

pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;

// Thread 1::
pthread_mutex_lock(&proc_info_lock);
if (thd−>proc_info) {
    . . .
    fputs(thd−>proc_info, . . . ) ;
    . . .
}
pthread_mutex_unlock(&proc_info_lock);

// Thread 2::
pthread_mutex_lock(&proc_info_lock);
thd−>proc_info = NULL;
pthread_mutex_unlock(&proc_info_lock);

순서 위반(order violation) 오류

// Thread 1::
void init() {
    . . .
    mThread = PR_CreateThread(mMain, . . . ) ;
    . . .
}

// Thread 2::
void mMain ( . . . ) {
    . . .
    mState = mThread−>State;
    . . .
}

이 코드에서 쓰레드 2는 mThread 변수가 이미 초기화된 것으로 가정하고 있다. 만약 쓰레드 1이 먼저 실행되지 않았다면 NULL 포인터를 사용하기 때문에 크래시가 일어나거나, 더 최악의 경우 임의의 메모리 주소를 참조하게 된다.

순서 위반의 정의는 다음과 같다.

“두 개의(그룹의) 메모리 참조 간의 순서가 바뀌었다(즉, A가 항상 B보다 먼저 실행되어야 하지만 실행 중에 그 순서가 지켜지지 않았다).”

이러한 오류를 수정하는 법은 순서를 강제하는 것이다. 이전에 논의했던 컨디션 변수가 잘 맞는다. 코드를 재작성해보자.

pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER;
int mtInit = 0;

// Thread 1::
void init() {
    . . .
    mThread = PR_CreateThread(mMain, . . . ) ;

    // 쓰레드가 생성되었다는 것을 알리는 시그널 전달
    pthread_mutex_lock(&mtLock);
    mtInit = 1;
    pthread_cond_signal(&mtCond);
    pthread_mutex_unlock(&mtLock);
    . . .
}

// Thread 2::
void mMain ( . . . ) {
    . . .
    // 쓰레드가 초기화되기를 기다린다
    pthread_mutex_lock(&mtLock);
    while (mtInit == 0)
        pthread_cond_wait(&mtCond, &mtLock);
    pthread_mutex_unlock(&mtLock);

    mState = mThread−>State;
    . . .
}

수정된 코드에서는 mtLock이라는 락, 그에 대한 컨디션 변수 mtCond, 그리고 상태 변수 mtInit을 추가하였다. 초기화 코드가 실행되면, mtInit을 1로 설정하고 시그널을 발생시킨다. 쓰레드 2가 이 시점 이전에 실행되었다면 상태 변경을 대기한다.

쓰레드 간의 순서가 문제가 된다면 컨디션 변수(또는 세마포어)를 이용하여 해결할 수 있다.

비 교착 상태 오류: 정리

비 교착 상태 오류의 대부분(97%)은 원자성 또는 순서 위반에 대한 것이었다. 이러한 오류 패턴들을 유의하면 관련 오류들을 좀 더 줄일 수 있다.

3. 교착 상태 오류

복잡한 락 프로토콜을 사용하는 다수의 병행 시스템에서 교착 상태(deadlock) 라는 고전적 문제가 발생한다. 예를 들어 락 L1을 갖고 있는 쓰레드 2가 락 L1이 해제되기를 기다리고 있을 때 교착 상태가 발생한다. 교착 상태가 발생할 가능성이 있는 코드를 보자.

Thread 1:     Thread 2:
lock(L1);     lock(L2);
lock(L2);     lock(L1);

쓰레드 1이 락 L1을 획득한 후 문맥 교환이 발생해 쓰레드 2가 락 L2를 획득하고 락 L1을 획득하기 시도할 때 교착 상태가 발생한다.

각 쓰레드가 상대방이 소유하고 있는 락을 대기하여 누구도 실행할 수 없게 된다. 그래프에서는 사이클의 존재는 교착 상태의 발생 가능성을 의미한다.

교착 상태는 왜 발생하는가

쓰레드 1,2가 같은 순서로 락을 획득한다면 교착 상태는 절대 발생하지 않는다. 그러면 교착 상태는 왜 발생할까?

코드가 많아지면서 구성 요소 간에 복잡한 의존성이 발생하기 때문이다. 운영체제를 생각해보면, 가상 메모리 시스템이 디스크 블럭을 가져오기 위해 파일 시스템에 접근한다. 파일 시스템은 디스크 블럭을 메모리에 탑재하기 위해 메모리 페이지를 확보해야 하고, 이를 위해 가상 메모리 시스템에 접근한다. 순환 의존성이 자연스럽게 발생한다.

또 다른 이유는 캡슐화의 성질 때문이다. 소프트웨어 모듈화가 개발을 쉽게 하기 때문에 상세한 구현 내용은 감추도록 구현한다. 하지만 이런 모듈화 때문에 교착 상태가 일어날 수 있다.

자바의 Vector 클래스의 addAll()메서드를 보자.

Vector v1, v2;
v1.addAll(v2);

이 메소드는 v1에 대한 락 뿐만 아니라 v2에 대한 락도 획득해야 한다. 하지만 어떤 쓰레드가 v2.addAll(v1)을 호출하면 교착 상태가 발생할 수 있다. 이 모든 상황은 호출한 응용 프로그램이 모르게 진행된다.

교착 상태 발생 조건

교착 상태가 발생하기 위해서는 네 가지 조건이 충족되어야 한다.

• 상호 배제 (Mutual Exclusion): 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장한다 (예, 쓰레드가 락을 획득함).
• 점유 및 대기 (Hold-and-wait): 쓰레드가 자신에게 할당된 자원 (예 : 이미 획득한 락)을 점유한 채로 다른 자원 (예 : 획득하고자 하는 락)을 대기한다.
• 비 선점 (No preemption): 자원 (락)을 점유하고 있는 쓰레드로부터 자원을 강제적 으로 빼앗을 수 없다.
• 순환 대기 (Circular wait): 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원 (락)을 갖고 있는 쓰레드들의 순환 고리가 있다.

네 조건 중 하나라도 만족시키지 않는다면 교착 상태는 발생하지 않는다.

교착 상태의 예방

순환 대기

아마도 가장 실용적이며 자주 사용되는 교착 상태 예방 기법은 순환 대기가 절대 발생하지 않도록 락 코드를 설정하는 것이다.

락 획득을 하는 전체 순서(total ordering)을 정할 수 있다. 락 L1, L2 두 개만 시스템에 존재한다면, L1은 무조건 L2 이전에 획득하도록 하여 교착 상태를 피할 수 있다.

복잡한 시스템의 경우 두 개 이상의 락이 존재할 것이고, 전체 락의 요청 순서를 정의하는 것이 어려울 것이다. 이를 위해 부분 순서(partial ordering)를 제공하는 것이 락 획득 구조를 만드는데 유용할 것이다. Linux의 메모리 매핑 코드가 부분 순서를 이용한 좋은 예시이다. 소스 코드를 보면, 열 개의 서로 다른 그룹으로 무묶인 락과 획득 순서가 있다.

• Code

    /*
     * Lock ordering:
     *
     *  ->i_mmap_rwsem        (truncate_pagecache)
     *    ->private_lock        (__free_pte->block_dirty_folio)
     *      ->swap_lock        (exclusive_swap_page, others)
     *        ->i_pages lock
     *
     *  ->i_rwsem
     *    ->invalidate_lock        (acquired by fs in truncate path)
     *      ->i_mmap_rwsem        (truncate->unmap_mapping_range)
     *
     *  ->mmap_lock
     *    ->i_mmap_rwsem
     *      ->page_table_lock or pte_lock    (various, mainly in memory.c)
     *        ->i_pages lock    (arch-dependent flush_dcache_mmap_lock)
     *
     *  ->mmap_lock
     *    ->invalidate_lock        (filemap_fault)
     *      ->lock_page        (filemap_fault, access_process_vm)
     *
     *  ->i_rwsem            (generic_perform_write)
     *    ->mmap_lock        (fault_in_readable->do_page_fault)
     *
     *  bdi->wb.list_lock
     *    sb_lock            (fs/fs-writeback.c)
     *    ->i_pages lock        (__sync_single_inode)
     *
     *  ->i_mmap_rwsem
     *    ->anon_vma.lock        (vma_merge)
     *
     *  ->anon_vma.lock
     *    ->page_table_lock or pte_lock    (anon_vma_prepare and various)
     *
     *  ->page_table_lock or pte_lock
     *    ->swap_lock        (try_to_unmap_one)
     *    ->private_lock        (try_to_unmap_one)
     *    ->i_pages lock        (try_to_unmap_one)
     *    ->lruvec->lru_lock    (follow_page_mask->mark_page_accessed)
     *    ->lruvec->lru_lock    (check_pte_range->folio_isolate_lru)
     *    ->private_lock        (folio_remove_rmap_pte->set_page_dirty)
     *    ->i_pages lock        (folio_remove_rmap_pte->set_page_dirty)
     *    bdi.wb->list_lock        (folio_remove_rmap_pte->set_page_dirty)
     *    ->inode->i_lock        (folio_remove_rmap_pte->set_page_dirty)
     *    bdi.wb->list_lock        (zap_pte_range->set_page_dirty)
     *    ->inode->i_lock        (zap_pte_range->set_page_dirty)
     *    ->private_lock        (zap_pte_range->block_dirty_folio)
     */

락의 순서를 정의하기 위해서는 코드와 다양한 루틴 간의 상호 호출 관계를 이해해야 한다. 조금만 실수해도 교착 상태가 발생하게 된다.

*"락 주소를 사용하여 락 요청 순서를 강제하는 방법도 있다.”*

if (m1 > m2) { // 락을 주소의 내림차순으로 획득
    pthread_mutex_lock(m1);
    pthread_mutex_lock(m2);
} else {
    pthread_mutex_lock(m2);
    pthread_mutex_lock(m1);
}
// m1 != m2를 가정

점유 및 대기

점유 및 대기는 원자적으로 모든 락을 단번에 획득하도록 하면 예방할 수 있다.

lock(prevention);
lock(L1);
lock(L2);
. . .
unlock(prevention);

prevention 락을 획득하여 필요한 락을 원자적으로 획득하도록한다.

이 해법은 문제점이 많다. 캡슐화가 어렵다. 필요한 락들을 정확히 파악해야하고, 그 락들을 미리 획득해야하기 때문이다. 또한 락이 필요할 때 요청하는 것이 아니라 미리 한번에 획득하기 때문에 병행성이 떨어진다.

비선점

일반적으로 락을 해제하기 전까지는 락을 보유하고 있는 것으로 보기 때문에 여러 락을 획득하는 것에는 문제의 소지가 있다. 왜냐하면 락을 이미 보유하고 있는 채로 다른 락을 대기하기 때문이다.

때문에 많은 쓰레드 라이브러리들은 이러한 상황을 피할 수 있도록 유연한 인터페이스 집합을 제공한다. trylock() 루틴의 경우 획득 가능하다면 락을 획득하거나 현재 락이 점유된 상태이니 나중에 다시 시도라하라는 것을 알리는 -1을 리턴한다.

trylock() 인터페이스를 이용하면 교착 상태 가능성이 없고 획득 순서에 영향을 받지 않는 락 획득 방법을 만들 수 있다.

top:
lock(L1);
if (trylock(L2) == −1) {
    unlock(L1);
    goto top;
}

다른 쓰레드가 같은 프로토콜을 사용하면서 락을 다른 순서로 획득하려고 해도 교착 상태는 발생하지 않는다. 하지만 무한반복(livelock) 문제가 생긴다.

두 쓰레드가 이 순서로 계속 시도하면서 락 획득에 실패하는 것도 가능하긴 하다(확률은 낮지만). 반복문에 지연 시간을 무작위로 조절해서 경쟁하는 쓰레드 간의 반복 간섭 확률을 줄일 수 있다.

상호 배제

마지막 예방 기법은 상호 배제 자체를 없애는 방법이다. 일반적인 코드는 모두 임계 영역을 포함하고 있기 때문에 어려운 일이다. 어떻게 할까?

wait-free 자료구조를 고안했다. 명시적 락이 필요없는 강력한 하드웨어 명령어를 사용하여 자료구조를 만들면 된다는 것이다.

Compare-And-Swap 명령이 대표적인 예제이다.

int CompareAndSwap(int *address, int expected, int new) {
    if (*address == expected) {
        *address = new;
        return 1; // 성공
    }
    return 0; // 실패
}

어떤 한 값을 원자적으로 임의의 크기만큼 증가 시키는 경우를 구현하자.

void AtomicIncrement(int *value, int amount) {
    do {
        int old = *value;
    } while (CompareAndSwap(value, old, old + amount) == 0);
}

락을 획득하여 갱신한 후 락을 해제하는 대신, CAS 명령어를 사용하여 값을 갱신하기하기를 반복적으로 시도한다. 이 경우 락을 획득할 필요도 없고, 교착 상태가 발생할 일도 없다.(무한 반복은 발생할 수 있지만)

좀 더 복잡한 리스트 삽입 예제를 살펴보자. 리스트 헤드에 개체를 삽입하는 코드이다.

void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n->value = value;
    do {
        n->next = head;
    } while (CompareAndSwap(&head, n->next, n) == 0);
}

next 포인터가 현재의 헤드를 가리키도록 갱신하고, 새로 생성된 노드는 리스트의 헤드가 되도록 동작한다. 이 코드를 처리하는 도중 다른 쓰레드가 새로운 헤드를 추가했다면, Compare-And-Swap은 실패하고 삽입 과정을 다시 시도한다.

스케줄링으로 교착 상태 회피하기

교착 상태의 예방보다 회피하는 것이 유용할 때가 있다. 교착 상태를 회피하기 위해서는 여러 쓰레드가 어떤 락을 획득하게 될 것인지에 대해 전반적으로 파악하고 있어야 하며, 그것을 바탕으로 쓰레드들을 스케줄링하여 교착 상태가 발생하지 않도록 그때그때 보장한다.

4개의 쓰레드가 2개의 프로세서에서 스케줄링 된다고 가정하자. 똑똑한 스케줄러라면 T1과 T2가 동시에 실행만 하지 않는다면 교착 상태가 절대로 발생하지 않도록 할 수 있다.

또 다른 예를 살펴보자

이 경우 T1, T2, T3가 동시에 실행되면 안된다.

T1, T2, T3이 모두 한 프로세서에서 실행되도록 보수적인 방법을 택하기 때문에 전체 작업이 끝나기까지 오랜 시간이 걸린다. 때문에 스케줄링으로 교착 상태를 회피하는 것은 보편적으로 사용되는 방법은 아니다.

유명한 예시로 Dijkstra의 Banker’s Alogrithm이 있다. 전체 작업에 대한 모든 지식을 알고있는 임베디드 시스템에서 작업을 실행하며 필요한 락을 획득하는 경우이다.

발견 및 복구

마지막 전략은 교착 상태 발생을 허용하고, 발견하면 복구하도록 하는 방법이다. 예를 들어 운영체제가 1년에 한 번 멈춘다고 했을 때 시원하게 재부팅을 하는 방법이 있다. 교착 상태가 아주 가끔 발생한다면 꽤 유용한 방법이다.

많은 데이터베이스 시스템들이 교착 상태를 발견하고 회복하는 기술을 사용한다. 이는 주기적으로 실행되며 자원 할당 그래프를 그려서 사이클이 생겼는지를 검사한다. 사이클이 발생하는 경우, 시스템은 재부팅되어야 한다.

1. 세마포어: 정의

세마포어는 정수 값을 갖는 객체로서 두 개의 루틴(sem_wait(), sem_post())을 가진다. 초기값에 의해 동작이 결정되기 때문에 제일 먼저 값의 초기화가 필요하다.

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

세마포어 s 를 선언하고, 3번째 인자로 1을 전달하여 세마포어의 값을 1로 초기화한다. em_init()의 두 번째 인자는 모든 예제에서 0이다. 이 값은 같은 프로세스 내의 쓰레드 간에 세마포어를 공유한다는 뜻이다.

초기화된 후에는 sem_wait(), sem_post()라는 함수를 호출하여 세마포어를 다룰 수 있다.

int sem_wait(sem_t *s) {
    decrement the value of semaphore s by one;
    wait if value of semaphore s is negative;
}

int sem_post(sem_t *s) {
    increment the value of semaphore s by one;
    if there are one or more threads waiting, wake one;
}

1. sem_wait() 는 세마포어 값이 1 이상이라면 즉시 리턴한다. 아니라면, 세마포어 값이 1이 될 때까지 호출자를 대기시킨다. 여러 쓰레드들이 함수를 호출할 수 있기 때문에 대기 큐에 여러 쓰레드가 존재할 수 있다. 대기 방식은 spin과 sleep 두가지가 있다.
2. sem_post()함수는 대기하지 않는다. 세마포어 값을 증가시키고 대기 중인 쓰레드를 하나 깨운다.
3. 세마포어가 음수라면 그 값은 현재 대기 중인 쓰레드의 개수와 같다.

위 두개의 함수는 원자적으로 실행된다고 가정한다. 아직은 race condition에 대한 걱정은 하지 말자.

2. 이진 세마포어 (락)

우선 세마포어를 “락”으로 사용해보자.

sem_t m;
sem_init(&m, 0, X); // X로 세마포어 초기화하기.
sem_wait(&m);
// 임계 영역
sem_post(&m);

X의 값이 무엇이 되어야 할까? 1이 되어야할 것이다.

쓰레드가 2개일 때를 생각해보자. 쓰레드 A는 세마포어 값을 1에서 0으로 감소시키고 임계 영역에 진입한다. 세마포어의 값이 0이기 때문에 바로 리턴한다. 이때 쓰레드 B가 sem_wait()을 호출해 임계영역에 진입을 시도한다면 어떻게 될까?

쓰레드 B는 세마포어 값을 -1로 감소시키고 대기 상태가 된다. 쓰레드 A가 이후에 작업을 완료하고 sem_post()를 호출하면 세마포어 값이 0이되고, 쓰레드 B가 다시 깨어난다. 이제 락을 획득하여 작업을 완료한 후 세마포어 값이 다시 1이 된다.

락은 두 개의 상태 (사용 가능, 사용 중) 만 존재하므로 이진 세마포어 (binary semaphore) 라고도 불린다.

3. 컨디션 변수로서의 세마포어

어떤 조건이 참이 되기를 기다리기 위해 현재 쓰레드를 멈출 때에도 세마포어는 유용하게 사용될 수 있다.

sem_t s;

void *child(void *arg) {
    printf(“child\n ”);
    sem_post(&s); // 시그널 전달: 동작 끝
    return NULL;
}

int main(int argc, char *argv[]) {
    sem_init(&s, 0, X); // X의 값은 무엇이 되어야 할까?
    printf(“parent: begin\n ”);
    pthread_t c;
    Pthread_create(c, NULL, child, NULL);
    sem_wait(&s); // 자식을 여기서 대기
    printf(“parent: end\n ”);
    return 0;
}

다음과 같이 자식 쓰레드의 종료를 기다리게 하고 싶다.

parent: begin
child
parent: end

부모 프로세스는 자식 프로세스 생성 후 sem_wait()를 호출하여 자식의 종료를 대기한다. 자식은 sem_post()를 호출하여 종료되었음을 알린다.

이를 위해 세마포어의 값을 어떻게 초기화 해야할까?

정답은 0이다. 두가지 상황이 발생할 수 있다.

1. 자식 프로세스 생성 후, 아직 자식 프로세스가 실행을 시작하지 않은 경우(준비 큐에만 들어 있고 실행 중이 아니다).

   이 경우 자식이 sem_post()를 호출하기 전에 부모가 sem_wait()를 호출할 것이다. 부모 프로세스는 자식이 실행될 때까지 대기하기 위해서는 sem_wait() 호출 전에 세마포어 값이 0보다 같거나 작아야 한다. 때문에 0이 초기값이 되어야 한다. 부모가 실행되면 세마포어 값을 감소(-1로)시키고 대기한다. 자식이 실행되었을 때 sem_post()를 호출하여 세마포어의 값을 0으로 증가시킨 후 부모를 깨운다. 그러면 부모는 sem_wait()에서 리턴을 하여 프로그램을 종료시킨다.

2. 부모 프로세스가 sem_wait()를 호출하기 전에 자식 프로세스의 실행이 종료된 경우이다. 이 경우, 자식이 먼저 sem_post()를 호출하여 세마포어의 값을 0에서 1로 증가시킨다. 부모가 실행할 수 있는 상황이 되면 sem_wait() 를 호출한다. 세마포어 값이 1인 것을 발견할 것이다. 부모는 세마포어 값을 0으로 감소시키고 sem_wait()에서 대기 없이 리턴한다. 이 방법 역시 의도한 결과를 만들어낸다.

4. 생산자/소비자 (유한 버퍼) 문제

이를 해결하기 위해 empty와 full이라는 두개의 세마포어를 사용한다.

int buffer[MAX];
int fill = 0;
int use = 0;

void put(int value) {
    buffer[fill] = value; // f1
    fill = (fill + 1) % MAX; // f2
}

int get() {
    int tmp = buffer[use]; // g1
    use = (use + 1) % MAX; // g2
    return tmp;
}

sem_t empty;
sem_t full;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty); // P1
        put(i); // P2
        sem_post(&full); // P3
    }
}

void *consumer(void *arg) {
    int i, tmp = 0;
    while (tmp != −1) {
        sem_wait(&full); // C1
        tmp = get(); // C2
        sem_post(&empty); // C3
        printf(“%d\n ”, tmp);
    }
}

int main(int argc, char *argv[]) {
    // . . .
    sem_init(&empty, 0, MAX); // empty는 MAX
    sem_init(&full, 0, 0); // full은 0
    // . . .
}

첫 번째 시도

소비자 쓰레드는 sem_wait(&full)을 호출한다. 버퍼가 차있지 않다면(full의 세마포어 값 ≤ 0)이라면 대기 상태가 된다. 생산자 쓰레드는 sem_wait(&empty)을 호출한다. 처음에 MAX(=1)로 초기화해놨기 때문에 empty의 세마포어 값이 0으로 감소하고 버퍼를 채운다. 이후 생산자는 sem_post(&full)을 호출하여 소비자 쓰레드를 깨운다.

이번에는

MAX 값이 더 크다면 생산자와 소비자 쓰레드가 여러개가 있다면 어떨까? 경쟁 조건이 발생할 것이다. put(), get()을 잘 보자.

생산자 A와 B가 put()을 거의 동시에 호출했다고 가정하자. 생산자 A가 버퍼의 첫번째 공간에 데이터를 채우고 fill의 카운터 변수를 1로 변경하기 직전에 생산자 B가 인터럽트된다면, 똑같이 버퍼의 첫번째 공간을 채우게 된다.

해답: 상호 배제의 추가

버퍼를 채우고 버퍼에 대한 인덱스를 증가하는 동작은 임계 영역이기 때문에 신중하게 처리해야된다. 지금까지 배운 이진 세마포어와 몇개의 락을 추가해 해결해보자.

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&mutex); // P0
        sem_wait(&empty); // P1
        put(i); // P2
        sem_post(&full); // P3
        sem_post(&mutex); // P4
    }
}

void *consumer(void *arg) {
    int i, tmp = 0;
    while (tmp != −1) {
        sem_wait(&mutex); // C0
        sem_wait(&full); // C1
        tmp = get(); // C2
        sem_post(&empty); // C3
        sem_post(&mutex); // C4
        printf(“%d\n ”, tmp);
    }
}

int main(int argc, char *argv[]) {
    // . . .
    sem_init(&empty, 0, MAX); // empty는 MAX
    sem_init(&full, 0, 0); // full은 0
    sem_init(&mutex,0 ,1); // lock은 1로 초기화
    // . . .
}

이제 put()/get() 코드에 락을 추가했다. 그런데 아직도 동작하지 않는다. 왜일까? 교착 상태 때문이다.

생산자와 소비자 쓰레드가 각 하나씩 있다고 하자. 소비자가 먼저 실행이 되었다. mutex(c0 라인)를 획득하고  sem_wait(&full)(c1 라인)을 호출한다. 아직 데이터가 없기 때문에 소비자는 대기해야한다. 여기서 중요한 것은 소비자가 아직도 락을 획득하고 있다는 것이다.

생산자가 실행된다. 실행이 가능하면 데이터를 생성하고 소비자 쓰레드를 깨울 것이다. 불행하게도 이 쓰레드는 먼저 mutex를 획득하기 위해 sem_wait(&mutex)를 실행한다(p0 라인). 이미 락은 소비자가 획득한 상태이기 때문에 생산자 역시 대기에 들어간다.

순환 고리가 생겼다. 소비자는 mutex를 갖고 있으면서 다른 full 시그널을 발생시키기를 대기하고 있다. full 시그널을 발생시켜야 하는 생산자는 mutex에서 대기중이다. 생산자와 소비자가 서로를 기다린다. 전형적인 교착 상태이다.

최종, 제대로 된 해법

락의 범위를 줄여야 한다. mutex를 획득하고 해제하는 코드를 임계영역만을 감싸도록 하자

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty); // p1
        sem_wait(&mutex); // p1.5 
        put(i); // p2
        sem_post(&mutex); // p2.5
        sem_post(&full); // p3
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&full); // c1
        sem_wait(&mutex); // c1.5
        int tmp = get(); // c2
        sem_post(&mutex); // c2.5
        sem_post(&empty); // c3
        printf(“%d\n ”, tmp);
    }
}

int main(int argc, char *argv[]) {
    // . . .
    sem_init(&empty, 0, MAX); 
    sem_init(&full, 0, 0); 
    sem_init(&mutex, 0,1); 
    // . . .
}

이제 멀티 쓰레드 프로그램에서 사용 가능한 유한 버퍼를 만들었다!

5. Reader-Writer 락

삽입 연산은 리스트의 상태를 변경하고 (전통적인 임계 영역 보호 방식으로 해결 가능하다), 검색은 자료 구조를 단순히 읽기만 한다. 삽입 연산이 없다는 보장만 된다면 다수의 검색 작업을 동시에 수행할 수 있다. 이와 같은 경우를 위해 만들어진 락이 reader-writer 락이다

typedef struct _rwlock_t {
    sem_t lock; // 이진 세마포어 (기본 락)
    sem_t writelock; // 하나의 쓰기 또는 다수의 읽기 락을 위한 락
    int readers; // 임계 영역 내에 읽기를 수행중인 reader의 수
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
    rw−>readers = 0;
    sem_init(&rw−>lock, 0, 1);
    sem_init(&rw−>writelock, 0, 1);
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw−>lock); // readers를 변경하기 위해 이진 세마포어 사용
    rw−>readers++;
    if (rw−>readers == 1)
        sem_wait(&rw−>writelock); // 읽기용 락이 writelock 획득
    sem_post(&rw−>lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw−>lock);
    rw−>readers−−;
    if (rw−>readers == 0)
        sem_post(&rw−>writelock); // 마지막으로 읽기용 락이 writelock 해제
    sem_post(&rw−>lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw−>writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw−>writelock);
}

이 코드는 간단하다. 자료 구조를 “갱신”하려면 새로운 동기화 연산 쌍을 사용한다. 락을 획득하기 위해서는 rwlock_acquire_writelock()을 사용하고 해제하기 위해서 rwlock_release_writelock()을 사용한다. 내부적으로는 writelock 세마포어를 사용하여 하나의 쓰기 쓰레드만이 락을 획득할 수 있도록 하여, 임계 영역 진임 후에 자료 구조를 갱신한다.

읽기 락을 획득시 읽기 쓰레드(reader)가 먼저 락을 획득하고 읽기 중인 쓰레드의 수를 표현하는 reader 변수를 증가시킨다. 첫 번째 읽기 쓰레드가 읽기 락을 획득할 때 중요한 과정이 있다. 읽기 락을 획득시 writelock 세마포어에 대해 sem_wait()을 호출하여 쓰기 락을 함께 획득한다. 획득한 쓰기 락은 읽기 락을 해제할 때 sem_post()로 다시 해제한다.

이 과정을 통해서 읽기 락을 획득하고 난 후, 다른 읽기 쓰레드들이 읽기 락을 획득할 수 있도록 한다. 다만, 쓰기 락을 획득하려는 쓰기 쓰레드 (writer)들은 모든 읽기 쓰레드가 끝날 때까지 대기하여야 한다. 임계 영역을 빠져나오는 마지막 읽기 쓰레드가 “writelock”에 대한 sem_post()를 호출하여 대기 중인 쓰기 쓰레드가 락을 획득할 수 있도록 한다.

이 방식은 몇 가지 단점이 있다.

쓰기 쓰레드에게 불리하다. 쓰기 쓰레드에게 기아 현상이 발생하기 쉽다. 쓰기 쓰레드가 대기 중일 때는 읽기 쓰레드가 락을 획득하지 못하도록 하여 기아 현상의 발생을 완화할 수 있다.

6. 식사하는 철학자

다섯 명의 “철학자”가 식탁 주위를 둘러앉았다. 다섯 개의 포크가 철학자 사이사이에 놓여있다. 철학자는 생각 중에는 포크가 필요 없고, 식사하기 위해서는 양쪽의 포크를 모두 들어야한다. 이 포크를 잡기 위한 경쟁과 그에 따른 동기화가 문제가 병행 프로그래밍에서 다루려는 식사하는 철학자 문제

while (1) {
    think();
    getforks();
    eat();
    putforks();
}

주요 쟁점은 getfork()와 putfork()의 루틴을 작성하되 교착 상태의 발생을 방지해야 하고, 어떤 철학자도 못 먹어서 굶주리면 되며 병행성이 높아야 한다(즉, 가능한 많은 철학자가 동시에 식사를 할 수 있어야 한다).

int left(int p) { return p; }
int right(int p) { return (p + 1) % 5; }

이 문제를 해결하기 위해서 세마포어가 필요하다. 각 포크마다 한 개씩 총 다섯 개가 있고 sem_t fork[5]로 정의한다.

불완전한 해답

각 포크에 대한 세마포어를 1로 초기화했고, 각 철학자는 자신의 순번을 알고 있다고 가정하자.

void getforks() {
    sem_wait(forks[left(p)]);
    sem_wait(forks[right(p)]);
}

void putforks() {
    sem_post(forks[left(p)]);
    sem_post(forks[right(p)]);
}

원리는 간단하다. 포크가 필요하면 락을 획득하고, 식사를 완료 후 포크를 내려놓는다.

모든 철학자가 자신의 왼쪽 포크를 집고 있다면, 모든 철학자는 오른쪽 포크를 얻기 위해 계속해서 대기하게 된다. 교착 상태가 발생한다.

해답: 의존성 제거

최소한 하나의 철학자가 다른 순서로 포크를 집도록 하면 된다.

void getforks() {
    if (p == 4) {
        sem_wait(forks[right(p)]); // 오른쪽 포크 먼저 집도록
        sem_wait(forks[left(p)]);
    } else {
        sem_wait(forks[left(p)]);
        sem_wait(forks[right(p)]);
    }
}

7. 쓰레드 쓰로틀링

너무 많은 쓰레드가 동시에 작업을 수행하지 않도록, 세마포어를 사용하여 동시에 실행되는 쓰레드 수를 제한한다.

문제 상황 예시

예를 들어, 수백 개의 쓰레드를 만들어 병렬 작업을 수행한다고 가정하자. 코드의 특정 부분에서는 각 쓰레드가 많은 양의 메모리를 점유해 계산을 수행하는데, 이 부분을 ‘메모리 집중 구역’이라고 칭하자. 만약 모든 쓰레드가 동시에 이 메모리 집중 구역에 진입하게 되면, 물리 메모리의 총량을 초과하는 메모리 할당 요청이 발생할 것이다. 이로 인해 시스템은 스래싱(thrashing) 을 시작하여, 디스크와의 페이지 교환이 빈번하게 일어나고 전체 계산 성능이 급격히 저하될 것이다.

세마포어를 이용한 해결 방안

이 문제를 해결하는 간단한 방법은 세마포어를 사용하는 것이다. 세마포어의 초기 값은 메모리 집중 구역에 동시에 진입할 수 있는 최대 쓰레드 수로 설정한다. 그 다음, 이 구역에 sem_wait()와 sem_post() 함수 호출을 감싸서 세마포어를 적용한다. 이렇게 하면, 세마포어가 자연스럽게 메모리 집중 구역에서 동시에 실행될 수 있는 쓰레드 수를 제한하게 된다.

8. 세마포어 구현

저수준 동기화 기법인 락과 컨디션 변수를 사용하여 우리만의 세마포어를 만들어보자. 제마포어(Zemaphore)다..

typedef struct __Zem_t {
    int value;
    pthread_cond_t cond;
    pthread_mutex_t lock;
} Zem_t;

// 오직 하나의 쓰레드만 이 문장을 호출할 수 있다.
void Zem_init(Zem_t *s, int value) {
    s−>value = value;
    Cond_init(&s−>cond);
    Mutex_init(&s−>lock);
}

void Zem_wait(Zem_t *s) {
    Mutex_lock(&s−>lock);
    while (s−>value <= 0)
        Cond_wait(&s−>cond, &s−>lock);
    s−>value−−;
    Mutex_unlock(&s−>lock);
}

void Zem_post(Zem_t *s) {
    Mutex_lock(&s−>lock);
    s−>value++;
    Cond_signal(&s−>cond);
    Mutex_unlock(&s−>lock);
}

하나의 락과 하나의 상태 변수와 세마포어 값을 나타내는 변수 하나를 사용한다.

Dijkstra가 정의한 세마포어와 여기서 정의한 제마포어 간의 중요한 차이 중 하나는 세마포어의 음수 값이 대기 중인 쓰레드의 수를 나타낸다는 부분이다. 사실 제마포어에서는 이 값이 0 보다 작을 수가 없다. 이 방식이 구현하기도 쉽고 현재 Linux에 구현된 방식이기도 하다.

세마포어를 사용하여 락과 컨디션 변수를 만드는 것은 매우 까다로운 문제이다. 세마포어로 컨디션 변수 구현에 성공한다면, 당신은 뛰어난 개발자의 소양을 가지고 있는 것이다.

쓰레드가 계속 진행하기 전에 어떤 조건이 참인지를 검사해야 하는 경우가 많이 있다. 예를 들면 자식 쓰레드가 작업을 끝냈는지 여부를 알 필요가 있다. 이런 걸 어떻게 구현할 수 있을까?

volatile int done = 0;

void *child(void *arg) {
    printf(“child\n ”);
    done = 1;
    return NULL;
}

int main(int argc, char *argv[]) {
    printf(“parent: begin\n ”);
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    while (done == 0)
    ; // spin
    printf(“parent: end\n ”);
    return 0;
}

위처럼 공유 변수로 구현할 수 있다 하지만 부모 쓰레드가 spin 하면서 자원을 낭비하고 있다. 이 방법 대신 부모 쓰레드가 특정 조건이 만족될때까지 잠자면서 기다리는 것이 더 좋다.

1. 정의와 루틴들

조건이 참이 될 때까지 기다리기 위해 컨디션 변수를 활용할 수 있다. 일종의 큐 자료로서, 어떤 실행의 상태가 원하는 것과 다를 때 조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐이다. 쓰레드가 상태를 변경시켰을 때, 대기 중이던 쓰레드를 깨워 이어서 진행될 수 있도록 한다.

pthread_cond_t c; 라고 써서 c가 컨디션 변수가 되도록 선언하고 초기화한다. 컨디션 변수에는 wait() 과 signal() 이라는 두 가지 연산이 존재한다.

wait() 은 쓰레드가 스스로를 잠재우기 위해 호출하는 것이고, signal()은 쓰레드가 무엇인가를 변경했기 때문에 조건이 참이 되기를 기다리며 잠자고 있던 쓰레드를 깨울 때 호출한다.

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);

wait()에서 유의할 것은 mutex를 매개변수로 사용한다는 것이다.

”wait()가 호출될 때 mutex는 잠겨있다고 가정한다. wait()의 역할은 락을 해제하고 호출한 쓰레드를 재우는 것이다. 어떤 다른 쓰레드가 시그널을 보내서 쓰레드가 깨어나면, wait()에서 리턴하기 전에 락을 재획득해야 한다.”

조건이 만족되어 잠에서 깨어났더라도 락을 획득못하면 다시 sleep 상태로 들어간다는 말이다. 이렇게 복잡한 이유는 쓰레드가 스스로를 재우려고 할 때, 경쟁 조건의 발생을 방지하기 위해서이다.

int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void thr_exit() {
    Pthread_mutex_lock(&m);
    done = 1;
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

void *child(void *arg) {
    printf(“child\n ”);
    thr_exit();
    return NULL;
}

void thr_join() {
    Pthread_mutex_lock(&m);
    while (done == 0)
        Pthread_cond_wait(&c, &m);
    Pthread_mutex_unlock(&m);
}

int main(int argc, char *argv[]) {
    printf(“parent: begin\n ”);
    pthread_t p;
    Pthread_create(&p, NULL, child, NULL);
    thr_join();
    printf(“parent: end\n ”);
    return 0;
}

1. 부모 쓰레드가 자식 쓰레드를 생성하고, 계속 실행하여 thr_join()을 호출하고 자식 쓰레드를 기다리는 경우

   부모 스레드는 thr_join()에서 done이 아직 1이 아니기 때문에 잠들게 된다. 자식 스레드의 실행 종료 후, 부모 스레드가 깨어나게 된다.

2. 자식 쓰레드가 생성되자마자 즉시 실행되는 경우

   자식 쓰레드가 즉시 실행되기 때문에, 부모 스레드가 thr_join()에 진입할 때 이미 done은 1이다. thr_join() 함수에서 대기가 일어나지 않고 바로 리턴한다.

매우 중요한 사실이 있다. 부모 쓰레드가 조건을 검사할 때(이 예제에서는 done의 값) if 문이 아니라 while 문을 사용한다는 사실이다

thr_exit(), thr_join()의 중요성을 이해할 수 있도록 몇 가지 구현의 방식을 살펴보자.

void thr_exit() {
    Pthread_mutex_lock(&m);
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

void thr_join() {
    Pthread_mutex_lock(&m);
    Pthread_cond_wait(&c, &m);
    Pthread_mutex_unlock(&m);
}

자식 쓰레드가 생성된 즉시 실행되어서 thr_exit()를 호출하는 경우를 생각해 보자. 이 경우 자식 스레드가 시그널을 보내는 시점에는 깨워야할 스레드가 없다. 부모 스레드가 실행되면 깨워줄 스레드가 없게된다. 이를 통해 done이라는 상태 변수의 필요성을 알 수 있다.

void thr_exit() {
    done = 1;
    Pthread_cond_signal(&c);
}

void thr_join() {
    if (done == 0)
        Pthread_cond_wait(&c);
}

여기서는 경쟁 조건이 발생한다. 만약 부모 쓰레드가 thr_join() 을 호출하고 done이 0인 것을 확인하고 잠자려고 한다. wait()가 호출되기 직전에 인터럽트가 발생하게 된다면 자식 스레드가 먼저 실행될 것이다. 이후에는 위 예시와 비슷하게 부모가 wait() 호출하여 잠자게 되고, 깨워줄 스레드가 없게된다.

시그널을 보내기 전에 항상 락을 획득하자

2. 생산자/소비자(유한 버퍼) 문제

다음으로 살펴볼 동기화 문제는 Dijkstra가 처음 제시한 생산자/소비자(producer/consumer) 문제이다. 유한 버퍼(bounded 버퍼) 문제로도 알려져 있다. lock 대신 일반화된 세마포어를 발명하게 된 이유가 이 문제 때문이다.

여러 개의 생산자 쓰레드와 소비자 쓰레드가 있다고 하자. 생산자는 데이터를 만들어 버퍼에 넣고, 소비자는 버퍼에서 데이터를 꺼내어 사용한다. 이러한 관계는 실제로 시스템에서 자주 일어난다. 예를 들어 멀티 쓰레드 웹 서버의 경우 생산자는 HTTP 요청을 작업 큐 (유한 버퍼) 에 넣고, 소비자 쓰레드는 이 큐에서 요청을 꺼내어 처리한다.

grep foo file.txt | wc -l와 같은 문장처럼 파이프 명령으로 한 프로그램의 결과를 다른 프로그램에게 전달할 때도 유한 버퍼를 사용한다. UNIX 쉘은 출력 결과를 UNIX 파이프 라는 곳으로 전송한다. 파이프의 한쪽 끝에는 wc 프로세스의 표준 입력과 연결되어 있다. grep 프로세스가 생산자가 되고 wc 프로세스가 소비자가 된다.

유한 버퍼는 공유 자원이고, 경쟁 조건의 발생을 방지하기 위해 동기화가 필요하다. 이를 위해 코드를 살펴보자.

공유버퍼를 위해 한 개의 정수를 사용하고, 공유 버퍼에 값을 넣는 함수, 값을 꺼내는 함수 두 개가 있다.

int buffer;
int count = 0;

void put(int value) {
    assert(count == 0);
    count = 1;
    buffer = value;
}

int get() {
    assert(count == 1);
    count = 0;
    return buffer;
}

• put()

  버퍼가 비어있다고 (count == 0 인지 확인하고), 값을 버퍼에 넣고 count를 1로 설정해 가득 찼음을 표시한다.

• get()

  버퍼가 찼는지 확인하고 (count == 1 인지), 값을 꺼낸 후 버퍼가 비었다고 설정한다.

두개의 스레드에서 하나는 put()하고 다른 하나는 get()을 수행한다고 생각했을 때, 당연히 제대로 동작하지 않을 것이다.

불완전한 해법

cond_t cond;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // p1
        if (count == 1) // p2
            Pthread_cond_wait(&cond, &mutex); // p3
        put(i); // p4
        Pthread_cond_signal(&cond); // p5
        Pthread_mutex_unlock(&mutex); // p6
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // c1
        if (count == 0) // c2
            Pthread_cond_wait(&cond, &mutex); // c3
        int tmp = get(); // c4
        Pthread_cond_signal(&cond); // c5
        Pthread_mutex_unlock(&mutex); // c6
        printf(“%d\n ”, tmp);
    }
}

컨디션 변수 하나와 그것과 연결된 mutex 락을 사용하는 방식을 먼저 시도해보자.

생산자는 버퍼가 빌 때까지 기다린다(p1-p3). 소비자도 버퍼가 차기를 기다린다(c1-c3). 생산자와 소비자가 하나씩인 경우에는 잘 동작하지만, 소비자가 더 많아지면 문제가 있다.

첫 번째 문제.

wait()함수 전의 if문과 관계가 있다.

생산자와 소비자 1, 2가 존재한다고 가정하자.

1. 소비자 1이 먼저 실행된다. 버퍼가 비어있기 때문에 wait()를 호출하고 잠들게 된다.
2. 생산자가 실행된다. 버퍼가 비어있으므로 버퍼를 채운다. 이후 다시 생산자가 실행되면서 버퍼가 차있기 때문에 잠들게 된다.
3. 소비자 2가 갑자기 끼어든다. 버퍼가 차있기 때문에 이를 소비하게된다.
4. 이제 소비자 1이 실행된다. wait()가 실행된 코드를 지나 get()을 호출하게 되는데, 버퍼가 비어있게 된다!

코드가 의도한대로 동작하지 못했다.

문제의 원인은 Tc1이 깨어나서 실행되기까지의 사이에 유한 버퍼의 상태가 변경되었기 때문이다. 시그널은 쓰레드를 깨우기만 하고, 깨어난 쓰레드가 실제 싱행되는 시점에 그 상태가 유지된다는 보장은 없다. 이런 식으로 시그널을 정의하는 것을 Mesa Semantic이라 한다. 대비되는 개념은 Hoare Semantic인데 구현하기는 더 어렵지만 깨어난 즉시 쓰레드가 실행되는 것을 보장한다.

개선된, 하지만 아직도 불완전한: if문 대신 while문

while문을 사용하게 된다면, 위 경우에서 소비자 1이 깨어나게 되더라도, 버퍼가 비었는지를 다시 확인하고 잠들게 될 것이다. Mesa semantic의 컨디션 변수에서 가장 기본적인 법칙은 언제나 while 문을 사용하라는 것이다.

하지만 아직도 코드에는 버그가 있다. 컨디션 변수가 하나라는 것과 관계가 있다.

cond_t cond;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // p1
        while (count == 1) // p2
            Pthread_cond_wait(&cond, &mutex); // p3
        put(i); // p4
        Pthread_cond_signal(&cond); // p5
        Pthread_mutex_unlock(&mutex); // p6
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // c1
        while (count == 0) // c2
            Pthread_cond_wait(&cond, &mutex); // c3
        int tmp = get(); // c4
        Pthread_cond_signal(&cond); // c5
        Pthread_mutex_unlock(&mutex); // c6
        printf(“%d\n ”, tmp);
    }
}

두 번째 문제.

이 문제는 소비자 1, 2가 모두 먼저 실행되어 대기 상태에 있을 때 발생한다.

1. 생산자가 실행되어 버퍼를 채우고, 소비자 1을 깨웠다고 가정하자. 생산자는 다시 잠들 것이다.
2. 소비자 1은 버퍼를 소비하고, 대기 중인 스레드를 하나 깨운다. 어떤 스레드를 깨워야할까?
3. 당연히 생산자를 깨워야하겠지만, 소비자 2를 깨웠다고 가정해보자.
4. 소비자 2는 while문에서 버퍼가 비어있는걸 확인하고 다시 잠들게 된다.

이럴수가! 모든 스레드가 잠들어버렸다.

시그널을 보내는 것은 꼭 필요하지만 대상이 명확해야 한다. 소비자는 다른 소비자를 깨울 수 없고 생산자만 깨워야 하며, 반대로 생산자의 경우도 마찬가지다.

단일 버퍼 생산자/소비자 해법

두 개의 컨디션 변수를 사용하여 시스템의 상태가 변경되었을 때 깨워야 하는 쓰레드에게만 시그널을 제대로 전달한다.

생산자 쓰레드가 empty 조건 변수에서 대기하고 fill에 대해서 시그널을 발생한다. 정반대로 소비자 쓰레드는 fill 에 대해서 대기하고 empty에 대해서 시그널을 발생시킨다. 이를 통해 반드시 소비자는 생산자를 깨우고, 생산자는 소비자를 깨우게 된다.

cond_t empty, fill;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // p1
        while (count == 1) // p2
            Pthread_cond_wait(&empty, &mutex); // p3
        put(i); // p4
        Pthread_cond_signal(&fill); // p5
        Pthread_mutex_unlock(&mutex); // p6
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // c1
        while (count == 0) // c2
            Pthread_cond_wait(&fill, &mutex); // c3
        int tmp = get(); // c4
        Pthread_cond_signal(&empty); // c5
        Pthread_mutex_unlock(&mutex); // c6
        printf(“%d\n ”, tmp);
    }
}

최종적인 생산자/소비자 해법

마지막 변경을 통해 병행성을 증가시키고 더 효율적으로 만든다. 버퍼 공간을 추가하여 대기 상태에 들어가기 전에 여러 값들이 생산될 수 있도록 하는 것, 그리고 여러 개의 값이 대기 상태 전에 소비될 수 있도록 하는 것이다.

버퍼의 구조와, put() / get() 함수를 수정했다.

int buffer[MAX];
int fill = 0;
int use = 0;
int count = 0;

void put(int value) {
    buffer[fill] = value;
    fill = (fill + 1) % MAX;
    count++;
}

int get() {
    int tmp = buffer[use];
    use = (use + 1) % MAX;
    count−−;
    return tmp;
}

생산자와 소비자의 대기 상태 로직도 변경하였다.

cond_t empty, fill;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // p1
        while (count == MAX) // p2
            Pthread_cond_wait(&empty, &mutex); // p3
        put(i); // p4
        Pthread_cond_signal(&fill); // p5
        Pthread_mutex_unlock(&mutex); // p6
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // c1
        while (count == 0) // c2
            Pthread_cond_wait(&fill, &mutex); // c3
        int tmp = get(); // c4
        Pthread_cond_signal(&empty); // c5
        Pthread_mutex_unlock(&mutex); // c6
        printf(“%d\n ”, tmp);
    }
}

생산자는 모든 버퍼가 현재 가득 차 있다면 대기 상태에 들어가고, 소비자도 모든 버퍼가 비어 있다면 대기에 들어간다.

3. 컨디션 변수 사용 시 주의점

// 몇 byte나 힙이 비었는가?
int bytesLeft = MAX_HEAP_SIZE;
cond_t c;
mutex_t m;

void *allocate(int size) {
    Pthread_mutex_lock(&m);
    while (bytesLeft < size)
        Pthread_cond_wait(&c, &m);
    void *ptr = . . . ; // 힙에서 메모리를 할당 받음
    bytesLeft −= size;
    Pthread_mutex_unlock(&m);
    return ptr;
}

void free(void *ptr, int size) {
    Pthread_mutex_lock(&m);
    bytesLeft += size;
    Pthread_cond_signal(&c); // 시그널 전달 대상은?..
    Pthread_mutex_unlock(&m);
}

멀티 쓰레드 기반 메모리 할당 라이브러리 예제를 살펴보자.

메모리 할당 코드를 호출하면, 공간이 생길 때까지 기다려야할 수도 있다. 반대로 쓰레드가 메모리를 반납 시, 메모리 공간의 발생을 알리는 시그널을 생성할 수 있다. 이 시그널을 날릴 때, 어떤 스레드가 깨어나야 될까?

이러한 시나리오를 살펴보자

1. 쓰레드 1이 allocate(100), 쓰레드 2가 allocate(10) 를 호출한다. 아직 여유 공간이 없어 둘다 대기 상태가 된다.
2. 쓰레드 3은 free(50)을 호출한다. 상식적으로 생각하면, 스레드 2를 깨워야할 것이지만, 코드는 원하는대로 동작하지 않는다.

해법은 단순하다.

pthread_cond_signal()을 대기 중인 모든 쓰레드를 깨우는 pthread_cond_broadcast()로 바꿔서 사용하면 된다. 다만 깨어날 필요가 없는 불필요한 쓰레드가 모두 깨어나 성능에 안좋은 영향을 미칠 수 있다.

이런 경우를 포함 조건(covering condition)이라고 한다. 쓰레드가 깨어나야하는 모든 경우를 다 포함하기 때문이고, 모든 스레드가 깨어나기 때문에 문맥전환 오버헤드가 크다.

일반적으로 시그널을 브로드캐스트(broadcast)로 바꿨을 때만 프로그램이 동작한다면 아마도 버그가 존재하는 것일 거다. 앞서 다룬 메모리 할당 문제의 경우 브로드캐스트를 적용하는 것이 가장 자명한 해법이다.

핵심 질문: 자료 구조에 락을 추가하는 방법

어떤 방식으로 락을 추가해야 그 자료 구조가 정확하게 동작하게 만들 수 있을까? 더 나아가, 자료 구조에 락을 추가하여 여러 쓰레드가 병행성을 지원하면서 동시에 고성능을 얻기 위해 무엇을 해야 할까?

1. 병행 카운터

간단한 자료구조인 카운터를 어떻게 thread safe하게 할까?

typedef struct _ _counter_t {
    int value;
} counter_t;

void init(counter_t *c) {
    c−>value = 0;
}

void increment(counter_t *c) {
    c−>value++;
}

void decrement(counter_t *c) {
    c−>value−−;
}

int get(counter_t *c) {
    return c−>value;
}

간단하지만 확장성 없음

typedef struct __counter_t {
    int value;
    pthread_mutex_t lock;
} counter_t;

void init(counter_t *c) {
    c−>value = 0;
    Pthread_mutex_init(&c−>lock, NULL);
}

void increment(counter_t *c) {
    Pthread_mutex_lock(&c−>lock);
    c−>value++;
    Pthread_mutex_unlock(&c−>lock);
}

void decrement(counter_t *c) {
    Pthread_mutex_lock(&c−>lock);
    c−>value−−;
    Pthread_mutex_unlock(&c−>lock);
}

int get(counter_t *c) {
    Pthread_mutex_lock(&c−>lock);
    int rc = c−>value;
    Pthread_mutex_unlock(&c−>lock);
    return rc;
}

간단하고 가장 보편적인 병행 자료구조 디자인 패턴을 따른다. 자료구조를 조작할 때, 락을 획득하고 그 호출문이 리턴할 때 락이 해제되도록 했다.

이 방식은 Monitor를 사용하여 만든 자료 구조와 유사하다. 모니터 기법은 객체에 대한 메소드를 호출하고 리턴할 때 자동적으로 락을 획득하고 해제한다.

제대로 동작하지만, 성능이 문제다. 각 쓰레드가 특정 횟수만큼 공유 카운터를 증가시키는 벤치마크를 실행하자.

9-3bdd-4e38-8ad4-4c3409ae0fbc:image.png)

더 많은 CPU가 동작할수록 단위 시간당 총 수행량이 늘어날 것으로 기대하지만, 단일 쓰레드로 카운터를 백만 번 갱신하는 데 대략 0.03초가 걸렸다. 두 개의 쓰레드로 카운트 값을 백만 번 갱신하는 데 약 5초 이상이 걸렸다.

이상적으로는 하나의 쓰레드가 하나의 CPU에서 작업을 끝내는 것처럼 멀티프로세서에서 실행되는 쓰레드들도 빠르게 작업을 처리하고 싶을 것이다(완벽한 확장성: perfect scaling).

확장성 있는 카운팅

확장 가능한 카운터가 으면 Linux의 몇몇 작은 멀티코어 기기에서 심각한 확장성 문제를 겪을 수 있다고 한다. 이를 위해 개선된 방법인 엉성한 카운터(sloppy counter)가 있다.

엉성한 카운터는 하나의 논리적 카운터로 표현되는데, CPU 코어마다 존재하는 하나의 물리적인 지역 카운터와 하나의 전역 카운터로 구성되어 있다.

엉성한 카운터의 기본 개념은 다음과 같다. 쓰레드는 지역 카운터를 증가시킨다. 이 지역 카운터는 지역 락에 의해 보호된다. CPU들에 분산되어 있는 쓰레드들은 지역 카운터를 경쟁 이 갱신할 수 있다. 확장성이 있다고 볼 수 있다.

지역 카운터의 값은 주기적으로 전역 카운터로 전달되는데, 이때 전역 락을 사용하여 지역 카운터의 값을 전역 카운터의 값에 더하고, 그 지역 카운터의 값은 0으로 초기화한다.

S라는 값을 두어, 지역 카운터가 S가 넘어가면 글로벌 카운터를 업데이트 한다.

S의 값이 낮다면 성능이 낮은 대신 전역 카운터의 값이 매우 정확해진다. S의 값이 매우 크다면 성능은 탁월하겠지만 전역 카운터의 값은 CPU의 개수와 S의 곱만큼 뒤처지게 된다.

typedef struct __counter_t {
    int global;
    pthread_mutex_t glock;
    int local[NUMCPUS];
    pthread_mutex_t llock[NUMCPUS]; 
    int threshold;
} counter_t;

void init(counter_t *c, int threshold) {
    c−>threshold = threshold;

    c−>global = 0;
    pthread_mutex_init(&c−>glock, NULL);

    int i;
    for (i = 0; i < NUMCPUS; i++) {
        c−>local[i] = 0;
        pthread_mutex_init(&c−>llock[i], NULL);
    }
}

void update(counter_t *c, int threadID, int amt) {
    pthread_mutex_lock(&c−>llock[threadID]);
    c−>local[threadID] += amt; 
    if (c−>local[threadID] >= c−>threshold) {
        pthread_mutex_lock(&c−>glock);
        c−>global += c−>local[threadID];
        pthread_mutex_unlock(&c−>glock);
        c−>local[threadID] = 0;
    }
    pthread_mutex_unlock(&c−>llock[threadID]);
}

int get(counter_t *c) {
    pthread_mutex_lock(&c−>glock);
    int val = c−>global;
    pthread_mutex_unlock(&c−>glock);
    return val;
}

2. 병행 연결 리스트

연결 리스트에서 병행 삽입 연산을 thread safe하게 해보자

삽입 연산을 시작하기 전에 락을 획득하고 리턴 직전에 해제한다. 매우 드문 경우지만, malloc()이 실패할 경우에 미묘한 문제가 생길 수 있다. 그런 경우가 발생한다면 실패를 처리하기 전에 락을 해제해야 한다.

typedef struct __node_t {
    int key;
    struct __node_t *next;
} node_t;

typedef struct __list_t {
    node_t *head;
    pthread_mutex_t lock;
} list_t;

void List_Init(list_t *L) {
    L−>head = NULL;
    pthread_mutex_init(&L−>lock, NULL);
}

int List_Insert(list_t *L, int key) {
    pthread_mutex_lock(&L−>lock);
    node_t *new = malloc(sizeof(node_t));
    if (new == NULL) {
        perror(“malloc ”);
        pthread_mutex_unlock(&L−>lock);
        return −1;
    }
    new−>key = key;
    new−>next = L−>head;
    L−>head = new;
    pthread_mutex_unlock(&L−>lock);
    return 0;
}

int List_Lookup(list_t *L, int key) {
    pthread_mutex_lock(&L−>lock);
    node_t *curr = L−>head;
    while (curr) {
        if (curr−>key == key) {
            pthread_mutex_unlock(&L−>lock);
            return 0;
        }
        curr = curr−>next;
    }
    pthread_mutex_unlock(&L−>lock);
    return −1;
}

삽입 연산이 병행하여 진행되는 상황에서 실패를 하더라도 락 해제를 호출하지 않으면서 삽입과 검색이 올바르게 동작하도록 수정할 수 있을까? 삽입 코드에서 임계 영역을 처리하는 부분만 락으로 감싸도록 코드 순서를 변경하고, 검색 코드의 종료는 검색과 삽입 모두 동일한 코드 패스를 사용토록 할 수 있다.

이 방법이 동작하는 이유는 코드 일부는 사실 락이 필요 없기 때문이다.

malloc() 자체가 thread safe하다면, 쓰레드는 언제든지 경쟁 조건과 다른 병행성 관련 버그를 걱정하지 않으면서 검색할 수 있다. 공유 리스트 갱신 때에만 락을 획득하면 된다.

void List_Init(list_t *L) {
    L−>head = NULL;
    pthread_mutex_init(&L−>lock, NULL);
}

void List_Insert(list_t *L, int key) {
    // 동기화를 할 필요 없음
    node_t *new = malloc(sizeof(node_t));

    if (new == NULL) {
        perror(“malloc ”);
        return;
    }
    new−>key = key;

    // 임계 영역만 락으로 보호
    pthread_mutex_lock(&L−>lock);
    new−>next = L−>head;
    L−>head = new;
    pthread_mutex_unlock(&L−>lock);
}

int List_Lookup(list_t *L, int key) {
    int rv = −1;
    pthread_mutex_lock(&L−>lock);
    node_t *curr = L−>head;
    while (curr) {
        if (curr−>key == key) {
            rv = 0;
            break;
        }
        curr = curr−>next;
    }
    pthread_mutex_unlock(&L−>lock);
    return rv; // 성공 혹은 실패
}

확장성 있는 연결 리스트

병행이 가능한 연결 리스트를 갖게 되지만 확장성이 좋지 않다. 병행성을 개선하는 방법 중 하나로 hand-over-hand locking(또는 lock coupling) 이라는 기법이 있다.

개념은 단순하다. 전체 리스트에 하나의 락이 있는 것이 아니라 개별 노드마다 락을 추가하는 것이다. 리스트를 순회할 때 다음 노드의 락을 먼저 획득하고 지금 노드의 락을 해제하도록 한다.

개념적으로는, 리스트 연산에 병행성이 높아지지만, 노드를 순회할때마다 락 획득과 해제가 필요하니 속도 개선을 기대할 수는 없다.

3. 병행 큐

큰 락을 사용하는 것이 병행 자료 구조를 만들기에 표준이다. 근데, 큐에서는 이 방법을 사용하지 않을 것이다.

typedef struct __node_t {
    int value;
    struct __node_t *next;
} node_t;

typedef struct __queue_t {
    node_t *head;
    node_t *tail;
    pthread_mutex_t headLock;
    pthread_mutex_t tailLock;
} queue_t;

void Queue_Init(queue_t *q) {
    node_t *tmp = malloc(sizeof(node_t));
    tmp−>next = NULL;
    q−>head = q−>tail = tmp;
    pthread_mutex_init(&q−>headLock, NULL);
    pthread_mutex_init(&q−>tailLock, NULL);
}

void Queue_Enqueue(queue_t *q, int value) {
    node_t *tmp = malloc(sizeof(node_t));
    assert(tmp != NULL);
    tmp−>value = value;
    tmp−>next = NULL;

    pthread_mutex_lock(&q−>tailLock);
    q−>tail−>next = tmp;
    q−>tail = tmp;
    pthread_mutex_unlock(&q−>tailLock);
}

int Queue_Dequeue(queue_t *q, int *value) {
    pthread_mutex_lock(&q−>headLock);
    node_t *tmp = q−>head;
    node_t *newHead = tmp−>next;
    if (newHead == NULL) {
        pthread_mutex_unlock(&q−>headLock);
        return −1;
    }
    *value = newHead−>value;
    q−>head = newHead;
    pthread_mutex_unlock(&q−>headLock);
    free(tmp);
    return 0;
}

두 개의 락이 있는데, 하나는 큐의 헤드에, 다른 하나는 테일에 사용되는 것을 알 수 있다. 이 두 개 락의 목적은 큐에 삽입과 추출 연산에 병행성을 부여하는 것이다. 일반적인 경우에는 삽입 루틴이 테일 락을 접근하고 추출 연산이 헤드 락만을 다룬다.

큐는 멀티 쓰레드 프로그램에서 자주 사용된다. 멀티 쓰레드 프로그램에서 사용하기 위해서는 큐가 비거나 가득 찬 경우, 쓰레드가 대기하도록 하는 기능이 필요하다. 이를 위해 사용하는 것이 그 유명한 조건 변수(condition variable) 이다.

4. 병행 해시 테이블

이전에 학습한 병행 리스트를 사용하여 구현하였으며 잘 동작한다. 전체 자료 구조에 하나의 락을 사용한 것이 아니라 해시 버켓 (리스트로 구현되어 있음) 마다 락을 사용하여서 성능이 우수하다.

#define BUCKETS ()

typedef struct __hash_t {
    list_t lists[BUCKETS];
} hash_t;

void Hash_Init(hash_t *H) {
    int i;
    for (i = ; i < BUCKETS; i++) {
        List_Init(&H−>lists[i]);
    }
}

int Hash_Insert(hash_t *H, int key) {
    int bucket = key % BUCKETS;
    return List_Insert(&H−>lists[bucket], key);
}

int Hash_Lookup(hash_t *H, int key) {
    int bucket = key % BUCKETS;
    return List_Lookup(&H−>lists[bucket], key);
}

1. 락: 기본 개념

balance = balance + 1;

다음과 같은 임계 영역이 있고, 락을 사용하기 위해 임계 영역을 감쌌다.

lock_t mutex; // 전역 변수로 선언된 락
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

락은 하나의 변수이기 때문에, 락을 사용하기 위해서는 락 변수를 먼저 선언해야한다. 이 락은 사용 가능 상태(어느 스레드도 락을 가지고 있지 않음)거나, 사용 중(임계 영역에서 정확히 하나의 쓰레드가 락을 획득한 상태)이다.

lock() 호출을 통해 락 획득을 시도한다. 사용 가능 상태라면 쓰레드는 락을 획득하여 임계영역 내로 진입한다. 이 쓰레드를 소유자(owner)라고 한다. 만약 다른 쓰레드가 lock()을 호출한다면, 락이 사용중인 동안에는 lock()함수가 리턴하지 않는다.

락 소유자가 unlock()을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다. 다른 스레드가 lock()을 호출한 상태가 아니라면 사용가능 상태를 유지하고, 대기 중이던 쓰레드가 있다면 그 쓰레드가 락을 획득한다.

락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다. 락은 쓰레드에 대한 제어권을 일부 이양받을 수 있게 해준다. 락을 통해 프로그래머는 임계 영역 코드 내에서 하나의 쓰레드만 동작하도록 보장할 수 있다. 프로세스들의 혼란스러운 실행 순서에 약간의 질서를 부여할 수 있다.

2. Pthread 락

쓰레드 간에 상호 배제(mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex라고 부른다. 상호 배제는 한 쓰레드가 임계 영역 내에 있다면 이 쓰레드의 동작이 끝날 때까지 다른 쓰레드가 임계 영역에 들어 올 수 도록 제한한다고 해서 얻은 이름이다.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

// 래퍼를 사용하여 락과 언락 시 에러를 확인하도록 하였다.
Pthread_mutex_lock(&lock); // pthread_mutex_lock()을 위한 래퍼.
balance = balance + 1;
Pthread_mutex_unlock(&lock);

POSIX 방식에서는 변수 명을 지정하여 락과 언락 함수에 전달하고 있다. 다른 변수를 보호하기 위해서 다른 락을 사용할 수도 있기 때문이다.

거친 락 (Coarse-Grained Locking)

• 하나의 락이 큰 임계 영역을 제어함.
• 쉽게 구현할 수 있지만, 병렬성이 제한됨.

세밀한 락 (Fine-Grained Locking)

• 여러 락이 서로 다른 데이터나 자료구조를 보호함.
• 한 번에 여러 쓰레드가 서로 다른 락으로 보호된 코드 내에 진입 가능.
• 병렬성은 향상되지만, 데드락 등의 복잡한 이슈에 대처해야 함.

3. 락 구현

어떻게 락을 만들어야 할까? 어떤 종류의 하드웨어 지원이 필요할까? 운영체제는 무엇을 지원해야 할까?

사용 가능한 락을 위해서는 하드웨어와 운영체제의 도움이 필요하다.

4. 락의 평가

1. 상호 배제
   • 임계 영역 내로 다수의 쓰레드가 집입하는 것을 막을 수 있는가
2. 공정성
   • 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가
   • starvation이 발생하는가?
3. 성능
   • 락 사용 시간적 오버헤드 평가
   • 하나의 쓰레드가 락을 획득하고 해제하는 과정에서의 부하는 얼마나 되는가?
   • 락 경쟁시

5. 인터럽트 제어

초창기 단일 프로세스 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용했다.

void lock() {
    DisableInterrupts();
}
void unlock() {
    EnableInterrupts();
}

임계 영역에 집입하기 전에, 인터럽트를 막는다면 임계 영역 내 코드는 원자적으로 수행될 수 있다. 이 방법의 주요 장점은 단순하다는 것이다.

그러나 단점이 많다.

1. 요청을 하는 쓰레드가 인터럽트를 활성/비활성화하는 특권 연산을 실행할 수 있도록 허용해야한다. 이를 다른 목적으로 사용하지 않음을 신뢰할 수 있어야 한다.
   • 프로그램이 시작과 동시에 lock()을 호출하여 프로세서를 독점할 수 있다.
2. 멀티 프로세서에서 적용할 수 없다.
   • 프로세서 마다 각자의 인터럽트 활성화 여부는 서로 영향을 끼치지 않는다. A에서 비활성화했더라도 B에서 접근할 수도 있다.
3. 장시간 인터럽트 중지는 중요한 인터럽트 시점을 놓치게될 수 있다.
4. 비효율적이다. 최신 CPU들에서는 인터럽트 관련 명령이 일반적인 명령에 비해 느린 경향이 있다.

이런 이유로, 상호 배제를 위한 인터럽트의 비활성화는 제한된 범위에서만 사용되어야 한다. 예를 들어 운영체제가 내부 자료구조에 대한 원자적 연산을 위해 인터럽트를 비활성화할 수 있다.

Dekker와 Peterson의 알고리즘 하드웨어 지원 없이 원자성을 지원하기 위한 개념을 제시했다. 그러나 하드웨어의 지원이 있다면 더 쉽게 해결할 수 있다는 것을 알게된 후 필요가 없어졌다.

6. Test-And-Set (Atomic Exchange)

멀티프로세서에서는 인터럽트를 중지시키는 것이 의미가 없다. 이에 시스템 설계자들은 락 지원을 위한 하드웨어를 설계하기 시작했다. 오늘날에는 모든 시스템이 이런 기능을 가지고있다.

하드웨어 기법 중 가장 기본은 Test-And-Set 명령어 또는 원자적 교체라고 불리는 기법이다. 이를 이해하기 위해 간단한 플래그 변수로 락은 구현해보자.

typedef struct __lock_t { int flag; } lock_t;

void init(lock_t *mutex) {
    // 0: 락 사용 가능
    // 1: 락 사용 중
    mutex−>flag = 0;
}

void lock(lock_t *mutex) {
    while (mutex−>flag == 1) // flag 변수를 검사 (test) 한다
    ; // spin−wait (do nothing)
    mutex−>flag = 1; // 이제 설정 (set) 한다
}

void unlock(lock_t *mutex) {
    mutex−>flag = 0;
}

쓰레드가 lock()을 호출하여 플래그 값이 1인지 검사(test)한다. 1일 경우 다른 스레드가 락을 사용 중이다. 이때 while문으로 spin-wait하며 다른 스레드가 unlock()을 호출하여 플래그를 0으로 바꿀때까지 기다린다. while문을 탈출한 후, 플래그를 1로 설정(set)하여 락을 보유하고 있다고 표시한다.

이 방식에는 두가지 단점이 있다.

1. 정확성

   시작할 때 flag = 0이라 하자. 쓰레드 1이 flag = 1을 실행하기 직전에 인터럽트가 일어난다면? 두 쓰레드 모두 플래그를 1로 설정하도록 하는 타이밍이 존재한다. 결국 두 쓰레드 모두 임계 영역에 진입하게 될 것이다.

2. 성능

   사용 중인 락을 대기하는 과정에서 spin-wait 방식은 다른 쓰레드가 락을 해제할 때까지 시간을 낭비한다. 단일 프로세서 환경에서는 락을 소유한 쓰레드도 실행되지 못하는 시점이 존재하게 된다.

7. 진짜 돌아가는 스핀 락의 구현

위 예제는 아이디어는 좋았지만, 하드웨어의 지원 없이는 동작이 불가능하다. 다행이 어떤 시스템에서는 이 개념에 근간한 락 구현을 위한 어셈블리 명령어를 제공한다. SPARC에서는 ldstub, x86에서는 xchg이다.

일반적으로 Test-And-Set 이라고 불리며, C코드의 일부를 사용해 동작을 정의해보자.

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; // old_ptr의 이전 값을 가져옴
    *old_ptr = new; // old_ptr 에 new 값을 저장함
    return old; // old의 값을 반환함
}

ptr이 가리키고 있던 예전의 값을 반환하고 동시에 new값을 ptr에 저장한다. 여기서 핵심은 이 동작들이 원자적으로 수행된다는 것이다.

“test and set”이라는 부르는 이유는, 검사하는 동시에 메모리에 새로운 값으로 설정하기 때문이다. 이 강력해진 명령어 만으로 더 간단한 spin-lock을 만들 수 있다.

typedef struct __lock_t {
    int flag;
} lock_t;

void init(lock_t *lock) {
    // 0은 락이 획득 가능한 상태
    // 1은 락을 획득했음
    lock−>flag = 0;
}

void lock(lock_t *lock) {
    **while (TestAndSet(&lock−>flag, 1) == 1)**
    ; // spin
}

void unlock(lock_t *lock) {
    lock−>flag = 0;
}

• 락이 사용가능 상태일 경우

  TestAndSet(flag, 1)을 호출하게 되면, 이전 값인 0을 리턴하고 flag를 1로 만든다. flag 값을 검사한 쓰레드는 while문을 회전하지 않고도 락을 획득하게 된다.

  동작 이후에는 unlock()을 통해 다시 flag를 0으로 만든다.

• 락이 사용 중인 상태

  TestAndSet(flag, 1)을 호출하게 되면, 이전 값인 1을 리턴하고 flag를 1로 만든다. 다른 쓰레드에서 락이 해제될 때까지 while문을 반복하다가, flag가 0이 되었을 때, TestAndSet()은 0을 리턴하는 동시에 flag를 1로 만든다. 원자적이다.

락의 값을 검사(Test)하고 설정(Set)하는 동작을 원자적 연산으로 만들어 하나의 쓰레드만 락을 획득할 수 있도록 했다. 이제 제대로 동작하는 상호 배제 함수를 만드는 방법을 배웠다.

지금 설명한 방식이 스핀 락(spin lock)이라고 불린다. 이것이 가장 기초적인 형태의 락으로서, 락을 획득할 때까지, CPU 사이클을 소모하면서 회전한다. 이 방식을 제대로 사용하려면 선점형 스케줄러여야한다.

8. 스핀 락 평가

• 정확성

  상호 배제가 가능하다면, 스핀락은 임의의 시간에 단 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 한다. 제대로 동작하는 락이다.

• 공정성

  스핀락은 어떠한 공정성도 보장해줄 수 없다. 실제로 while문을 회전 중인 쓰레드는 경쟁에서 밀려 계속 그 상태에 머물러 있을 수도 있다. 쓰레드가 굶주리게 될 수 있다.

• 성능

  단일 CPU의 경우 스핀락의 성능 오버헤드가 매우 클 수 있다. 한 스레드가 락을 가지고 있고, N - 1개의 다른 스레드가 있다고 가정하자. 락을 획득하려는 나머지 스레드들을 하나씩 깨울 수 있다. N -1 가 CPU에 할당되있는 동안 사이클이 낭비된다.

  멀티 CPU의 경우 (쓰레드 개수가 CPU 개수와 대충 같다면) 꽤 합리적으로 동작한다. CPU 1에서 실행중인 A가 락을 획득한 후 B가 락을 획득하려고 할때, B는 CPU 2에서 기다리기 때문에 CPU 1에서 CPU 사이클이 낭비되지 않는다.

9. Compare-And-Swap

또 다른 하드웨어 기법은 SPARC의 Compare-And-Swap, x86에서는 Compare-And-Exchange가 있다.

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

Compare-And-Swap 기법의 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는가 것이다. 만약 일치한다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경한다. 불일치한다면 아무 것도 하지 않는다. 원래의 메모리 값을 반환하여 CompareAndSwap를 호출한 코드가 락 획득의 성공 여부를 알 수 있도록 한다.

앞서 작성한 Test-And-Set 방법을 사용했을 때와 같은 방식으로 락을 만들 수 있다.

typedef struct __lock_t {
    int flag;
} lock_t;

void init(lock_t *lock) {
    // 0은 락이 획득 가능한 상태
    // 1은 락을 획득했음
    lock−>flag = 0;
}

void lock(lock_t *lock) {
**while (CompareAndSwap(&lock−>flag, 0, 1) == 1)**
    ; // spin
}

void unlock(lock_t *lock) {
    lock−>flag = 0;
}

락이 사용가능할 경우, actual, expected 모두 0이다. 이제 flag는 1로 변경되고 이를 리턴한다. 락이 사용 중인 경우, actua(1)과 expected(0)는 서로 다르다. while문을 회전하며 대기하다가, 다른 쓰레드에서 락을 해제하면 두 값이 0으로 같아져 flag를 다시 1로 설정하고, 락을 획득할 수 있다.

CompareAndSwap 명령어는 TestAndSet 보다 더 강력하다. 대기 없는 동기화(wait-free synchronization)를 다룰 때 알게될 것이다.

10. Load-Linked 그리고 Store-Conditional

어떤 플랫폼은 임계 영역 진입 제어 함수를 제작하기 위한 명령어 쌍을 제공한다. MIPS 구조에서는 load-linked와 store-conditional 명령어를 앞뒤로 사용하여 락 이나 기타 병행 연산을 위한 자료 구조를 만들 수 있다.

Alpha, PowerPC, 그리고 ARM에서도 유사한 명령어를 지원한다.

int LoadLinked(int *ptr) {
    return *ptr;
}

int StoreConditional(int *ptr, int value) {
    if (no one has updated *ptr since the LoadLinked to this address) {
        *ptr = value;
        return 1; // 갱신 성공
    } else {
        return 0; // 갱신 실패
    }
}

LoadLinked는 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장한다. StoreConditional 명령어는 동일한 주소에 다른 store가 없었던 경우에만 저장을 성공한다. 성공한 경우 LoadLinked가 탑재했던 값을 갱신하고 1을 반환한다. 실패하면 갱신하지 않고 0을 반환한다.

void lock(lock_t *lock) {
while (1) {
    while (LoadLinked(&lock−>flag) == 1)
    ; // 0이 될 때까지 spin
    if (StoreConditional(&lock−>flag, 1) == 1)
        return; // 1로 변경하는 것을 성공한 경우 완료
        // 아니라면 처음부터 다시 시도
    }
}

void unlock(lock_t *lock) {
    lock−>flag = 0;
}

lock()부분의 코드를 보자. 쓰레드가 while 문을 돌며 flag가 0이 되기를 기다린다(락이 해제된 상태). 락이 획득 가능한 상태가 되면 쓰레드는 store-conditional 명령어로 락 획득을 시도하고 만약 성공한다면 쓰레드는 flag 값을 1로 변경한다. 그리고 임계 영역 내로 진입한다.

좀더 짧게 작성할 수도 있다.

void lock(lock_t *lock) {
    while (LoadLinked(&lock−>flag)||!StoreConditional(&lock−>flag, 1))
    ; // spin
}

11. Fetch-And-Add

마지막 하드웨어 기반의 기법은 Fetch-And-Add 명령어로 원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시킨다.

int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

fetch-and-add 명령어를 사용하여 티켓 락을 만들어보자.

typedef struct __lock_t {
    int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock) {
    lock−>ticket = 0;
    lock−>turn = 0;
}

void lock(lock_t *lock) {
    **// lock 획득을 원할 때, FetchAndAdd()를 통해 자신의 차례 획득**
    int myturn = FetchAndAdd(&lock−>ticket);
    **// 다른 쓰레드에서 락을 해제해 내 턴이 올때까지 spin-lock**
    while (lock−>turn != myturn)
    ; // spin
}

void unlock(lock_t *lock) {
    FetchAndAdd(&lock−>turn);
}

하나의 변수만을 사용하는 대신 이 해법에서는 티켓(ticket) 과 차례(turn) 조합을 사용하여 락을 만든다. fetch-and-add를 통해 자신의 턴(myturn)을 확인하고, 자신의 차례(myturn == turn)일 때 임계영역에 진입한다. 언락 동작 시에는 turn을 증가 시켜 다음 차례를 알려준다.

이전까지 접근 방법과의 가장 중요한 차이점은 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이다. 쓰레드가 티켓 값을 할당받았다면, 미래의 어느 시점에 실행되기 위해 스케줄되어 있다는 것이다. 이전까지는 이러한 보장이 없었다. 예를 들어 Test-And-Set의 경우 다른 쓰레드들은 락을 획득/해제하더라도 어떤 쓰레드는 계속 회전만 하고 있을 수 있다. 즉 이번 해법은 *공정성에* 있다.

12. 요약: 과도한 스핀

이제까지 소개한 하드웨어 기반의 락은 간단하고, 그리고 제대로 동작한다. 하지만 때로는 이러한 해법이 효율적이지 않은 경우도 있다.

락을 소유중인 쓰레드 0이 실행 중 인터럽트가 발생하면, 락을 기다리는 또 다른 쓰레드는 계속해서 기다려야한다. N개의 쓰레드가 하나의 락을 획득하기 위해 경쟁하게 되면 상황이 더 심각해진다. N-1개의 쓰레드에 할당된 CPU 시간동안 spin하며 사이클이 낭비된다.

13. 간단한 접근법: 무조건 양보

하드웨어의 지원을 받아 많은 것을 해결하였다. 동작이 검증된 락과 락 획득의 공정성 (티켓 락을 사용한 경우)까지도 해결할 수 있었다. 그러면 쓰레드가 락을 해제하기를 기다리며 스핀만 무한히 하는 경우에는 어떻게 해야 할까?

가장 단순하고 친근한 방법은 락 해제를 기다리며 spin 해야하는 경우 cpu를 양보하는 것이다.

void init() {
    flag = 0;
}

void lock() {
    while (TestAndSet(&flag, 1) == 1)
        yield(); // CPU 양보
}

void unlock() {
    flag = 0;
}

단일 CPU 시스템에서 이런 방식은 잘 작동한다. 락 획득을 시도했지만 다른 쓰레드가 사용 중이라면 CPU를 양보한다.

100개 정도의 쓰레드가 락을 획득하기 위해 경쟁하는 경우는 어떨까? 락을 기다리는 99개의 쓰레드들이 run-and-yield하게 될 것이다. spin-lock 보다는 나을 수도 있지만, 여전히 문맥 교환 비용을 생각하면 비효율적이다.

또한 굶주림 문제는 아직 손대지도 못했다. 어떤 쓰레드는 무한히 양보만 하고 있을 수도 있다.

14. 큐의 사용: 스핀 대신 잠자기

이전 방법들은 너무 많은 부분을 운에 맡겼다. 스케줄러가 좋지 않은 선택을 한다면 기다리거나 CPU를 양보해야 한다. 둘 다 낭비의 여지가 있고 쓰레드가 굶주릴 수 있다.

어떤 쓰레드가 다음으로 락을 획득할지를 명시적으로 제어할 수 있어야 한다. 이를 위해 운영체제로부터 적절한 지원을 받고, 큐를 이용한 대기 쓰레드들을 관리할 것이다.

간단히 Solaris의 방식으로 해보자.

park(): 호출하는 쓰레드를 잠재우는 함수 unpark(threadID): threadID로 명시된 특정 쓰레드를 깨우는 함수

이 두 루틴은 이미 사용 중인 락을 요청하는 프로세스를 재우고 해당 락이 해제되면 깨우도록 하는 락을 제작하는 데 앞뒤로 사용할 수 있다.

TestAndSet 개념을 락 대기자 전용 큐와 함께 사용하여 효율적인 락을 만들 것이고, 큐를 사용하여 굶주림 현상을 방지할 것이다.

typedef struct __lock_t {
    int flag;
    int guard;
    queue_t *q;
} lock_t;

void lock_init(lock_t *m) {
    m−>flag = 0;
    m−>guard = 0;
    queue_init(m−>q);
}

void lock(lock_t *m) {
    while (TestAndSet(&m−>guard, 1) == 1)
    ; // 회전하면서 guard 락을 획득
    if (m−>flag == 0) {
        m−>flag = 1; // 락 획득
        m−>guard = 0;
    } else {
        queue_add(m−>q, gettid());
        m−>guard = 0;
        park(); // 잠재우기
    }
}

void unlock(lock_t *m) {
    while (TestAndSet(&m−>guard, 1) == 1)
    ; // 회전하면서 guard 락을 획득
    if (queue_empty(m−>q))
        m−>flag = 0; // 락을 포기함. 누구도 락을 원치 않음.
    else
        unpark(queue_remove(m−>q)); // 락을 획득함 (다음 쓰레드를 위해)
    m−>guard = 0;
}

guard 변수를 사용하여 flag와 큐의 삽입과 삭제 동작을 스핀 락으로 보호한다. 이 방법은 스핀을 완전히 배제하지는 못했다. 하지만 스핀 대기 시간은 꽤 짧다. 사용자가 지정한 임계 영역에 진입하는 것이 아니라 락과 언락 코드 내의 몇 개의 명령어만 수행하면 되기 때문이다.

lock() 에 추가된 동작이 있다. lock()을 호출했는데 다른 쓰레드가 이미 락을 보유중이라면, gettid()를 호출하여 현재 실행 중인 쓰레드 ID를 얻고, 락 소유자의 큐에 자기 자신을 추가하고 guard 변수를 0으로 변경한 후 CPU를 양보한다.

다른 쓰레드가 깨어났을 때 flag 변수가 0으로 설정되지 않는다. 깨어날 때는 guard 락을 획득한 상태가 아니기 때문에 flag를 1로 변경할 수 없다. 따라서 그냥 1인 채로 두고 락을 획득하려는 다음 쓰레드로 직접 전달한다. flag는 0이 되었다 다시 1이 되는게 아니라 그냥 계속 1이다.

마지막으로, park() 직전에 경쟁 조건이 발생한다. 한 쓰레드는 락이 사용중이라 park()를 실행하려고 한다. 그 직전에 락 소유자한테 CPU가 할당되면 문제가 생길 수 있다.

경쟁 조건이 어떻게 발생하는가?

1. B가 park()를 호출하기 바로 직전에 CPU 스케줄링이 발생하여 A가 실행된다.
2. A가 락을 해제하고 B를 깨우기 위해 unpark()를 호출한다.
3. 하지만 B는 아직 park()를 호출하지 않았으므로, 실제로는 깨워질 수 없다. 따라서 B는 락이 해제되었음에도 불구하고 계속 대기 상태에 머물게 된다.

이러한 문제를 해결하기 위해 Solaris 운영체제는 setpark() 시스템 콜을 도입했다.

guard 변수의 역할을 커널에서 담당하는 것도 하나의 방법이다. 커널은 락 해제와 실행 중인 쓰레드를 큐에서 제거하는 동작을 atomic하게 처리하기 위해 주의를 기울여야 한다.

15. 다른 운영체제, 다른 지원

좀 더 효율적인 락을 만들기 위한 운영체제 지원 내용을 살펴보았다. 다른 운영체제들도 유사한 기능을 지원하지만 세부적인 내용은 다르다.

Linux의 경우 futex라는 것을 지원한다. 각 futex는 특정 물리 메모리 주소와 연결되어 있으며 futex마다 커널 내부의 큐를 밖고 있다. 호출자는 futex를 호출하여 필요에 따라 잠을 자거나 깨어날 수 있다.

• futex_wait(address, expected)

  address 값이 expected와 같으면 쓰레드를 잠재운다. 같지 않다면 즉시 리턴한다.

• futex_wake(address)

  큐에서 대기하는 쓰레드 하나를 깨운다.

void mutex_lock (int *mutex) {
    int v;

    if (atomic_bit_test_set (mutex, 31) == 0)
        return;
    atomic_increment (mutex);
    while (1) {
    if (atomic_bit_test_set (mutex, 31) == 0) {
        atomic_decrement (mutex);
        return;
    }

    v = *mutex;
    if (v >= 0)
        continue;
    futex_wait (mutex, v);
    }
}

void mutex_unlock (int *mutex) {

    if (atomic_add_zero (mutex났 0x80000000))
        return;

    futex_wake (mutex);

16. 2단계 락

2단계 락 기법은 락이 곧 해제될 것 같은 경우라면 회전 대기가 유용할 수 있다는 것에서 착안하였다.

첫 번째 단계에서는 곧 락을 획득할 수 있을 것이라는 기대로 회전하며 기다린다. 만약 첫 회전 단계에서 락을 획득하지 못했다면 두 번째 단계로 진입하여 호출자는 잠에 빠지고 락이 해제된 후에 깨어나도록 한다.

앞서 본 Linux의 락은 이러한 형태를 갖는 락이지만 한 번만 회전한다. 일반화된 방법은 futex가 잠재우기 전에 일정 시간 동안 반복문 내에서 회전하도록 하는 것이다.

17. 요약

방금 보인 기법은 락이 실제 어떻게 구현되는지를 보여준다. 일부 하드웨어 지원 (강력한 명령어의 형태)과 일부 운영체제의 지원(예, park()와 unpark()와 같은 형태)을 받아 락을 구현하였다.

핵심 질문: 쓰레드를 생성하고 제어하는 방법 운영체제가 쓰레드를 생성하고 제어하는데 어떤 인터페이스를 제공해야 할까? 어떻게 이 인터페이스를 설계해야 쉽고 유용하게 사용할 수 있을까?

1. 쓰레드 생성

멀티 쓰레드 프로그램 작성시, 가장 먼저할 일은 새로운 쓰레드의 생성이다. POSIX를 통해 쉽게 할 수 있다.

POSIX(Portable Operating System Interface)는 운영체제 간에 이식성(Portability)을 높이기 위한 API(Application Programming Interface)와 명령어 셋 등을 정의하는 표준입니다.

주로 UNIX와 UNIX-like 시스템(예: Linux, macOS)에서 사용되며, 이 표준을 따르는 운영체제에서는 동일한 또는 유사한 프로그래밍 인터페이스를 제공함으로써, 소프트웨어의 이식성을 높입니다.

POSIX 표준에는 파일 시스템, 프로세스 관리, 스레드 관리, 입출력, 메모리 관리 등 다양한 부분이 포함되어 있습니다. 여기서 pthread_create 함수는 POSIX 스레드(POSIX Threads, 또는 Pthreads)를 생성하기 위한 C 라이브러리 함수 중 하나입니다. 이 함수를 사용하면 운영체제가 지원하는 스레드를 생성하고 관리할 수 있습니다.

#include <pthread.h>
int pthread_create(
            pthread_t*      thread,
      const pthread_attr_t* attr,
            void*           (*start_routine)(void*),
            void*           arg);

thread는 pthread_t 타입 구조체를 가르키는 포인터이다. 이 구조체가 쓰레드와 상호작용하는데 사용되기 때문에 쓰레드 초기화 시 pthread_create()에 이 구조체를 전달한다.

attr은 쓰레드의 속성을 지정하는데 사용된다. 스택의 크기, 쓰레드의 스케줄링 우선순위 같은 정보를 지정하기 위해 사용될 수 있다. 대부분 NULL로 지정하며 디폴드 값으로 사용한다.

(*start_routine)(void*) 는 이 쓰레드가 실행할 함수이다. C언어의 함수 포인터를 통해 전달된다. void* 타입을 인자로 받고 void* 타입을 리턴하는데, 어떤 타입의 결과도 반환할 수 있기 때문이다.

arg는 실행할 함수에게 전달할 인자를 나타낸다.

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

typedef struct {
    int a;
    int b;
} myarg_t;

void *mythread(void *arg) {
    myarg_t *args = (myarg_t *) arg;
    printf("%d %d\n", args->a, args->b);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p;
    myarg_t args = { 10, 20 };
    int rc = pthread_create(&p, NULL, mythread, &args);
    ...

두 개의 인자를 전달받는 새로운 쓰레드를 생성한다. 두 인자는 myarg_t 타입으로 묶여지고, 생성된 쓰레드에서 전달받은 인자를 타입 변환을 통해 얻을 수 있다.

2. 쓰레드 종료

다른 쓰레드가 작업을 완료할 때가지 기다려야 한다면 어떻게 해야할까?

POSIX 쓰레드에서는 pthread_join()을 부르면 된다.

int pthread_join(pthread_t thread, void **value_ptr);

이 루틴은 두개의 인자를 받는데, 첫번째는 pthread_t 값을 받아 어떤 쓰레드를 기다릴지 명시한다. 두번째는 반환 값에 대한 포인터이다(void *).

#include <stdio.h>
#include <pthread.h>
#include <assert.h>
#include <stdlib.h>

typedef struct { int a; int b; } myarg_t;
typedef struct { int x; int y; } myret_t;

void *mythread(void *arg) {
    myret_t *rvals = malloc(sizeof(myret_t));
    rvals->x = 1;
    rvals->y = 2;
    return (void *) rvals;
}

int main(int argc, char *argv[]) {
    pthread_t p;
    myret_t *rvals;
    myarg_t args = { 10, 20 };
    pthread_create(&p, NULL, mythread, &args);
    pthread_join(p, (void **) &rvals); **// 스레드 p가 끝날때까지 대기한다.**
    printf("returned %d %d\n", rvals->x, rvals->y);
    free(rvals);
    return 0;
}

void *mythread(void *arg) {
    myarg_t *args = (myarg_t *) arg;
    printf("%d %d\n", args->a, args->b);
    myret_t oops; // ALLOCATED ON STACK: BAD!
    oops.x = 1;
    oops.y = 2;
    return (void *) &oops;
}

쓰레드에서 값이 어떻게 변경되는지를 유의해야한다. 특히, 쓰레드의 콜 스택에 할당된 값을 가르키는 포인터를 반환하면 안된다. 위 코드에서 myret_t oops 에 할당된 값은, 쓰레드가 리턴될 때 자동으로 해제된다. 현재 해제된 포인터를 가르키는 것은 좋지 않다.

위위 코드 처럼 pthread_create()로 쓰레드를 생성하고, 그 직후에 pthread_join()을 호출하는 것은 이상한 방식이다. procedure call을 사용하면 더 쉽게 이 작업을 할 수 있다. 일반적으로는 여러개의 쓰레드를 생성해 놓고 쓰레드가 끝나기를 기다린다.

모든 멀티 쓰레드 코드가 조인 루틴을 사용하지는 않는다. 멀티 쓰레드 웹서버의 경우, 여러개의 작업 쓰레드를 생성하고 메인 쓰레드를 이용하여 사용자의 요청을 받아 작업자에게 전달하는 작업을 무한히 할 것이다. 이런 프로그램은 join이 필요없다.

특정 작업의 병렬적 실행에서 다음 단계로 넘어가기 전에 병렬 수행 작업의 완료를 확인하기 위해 join을 사용한다.

3. 락

쓰레드의 생성과 조인 다음으로 가장 유용한 함수는 락(lock)을 통해 임계 영역에 대한 상호 배제 기법이다.

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

다음과 같이 임계 영역을 보호할 수 있다.

pthread_mutex_t lock;
pthread_mutex_lock(&lock);
x = x + 1; // 임계 영역의 코드
pthread_mutex_unlock(&lock);

사실 이 코드는 올바르게 동작하지 않는다.

첫 번째, 초기화를 하지 않았다. 올바를 값을 가지고 시작했다는 것을 보장하기 위해 올바르게 초기화해주어야한다. 초기화에는 두가지 방법이 있다.

pthread_mutext_t lock = PTHREAD_MUTEX_INITALIZER;

이 방식은 락을 디폴트 값으로 설정한다. 동적으로 호출하려면 어떡하띾?

int rc = pthread_mutex_init(&lock, NULL);
assert(rc == 0); // 성공했는지 꼭 확인해야 한다.

첫번째 인자는 락 자체의 주소이고, 정상적으로 획득했는지를 확인하는 작업이 필요하다. 락 사용이 끝났다면, pthread_mutex_destory()를 호출해주어야 한다.

락과 언락 루틴 외에도 락 관련 루틴들이 더 존재한다.

int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_timedlock(pthread_mutex_t *mutex,
                            struct timespec *abs_timeout);

trylock은 락이 이미 사용중이라면 실패코드를 변환한다. timedlock은 타임아웃이 끝나거나 락을 획득하거나의 두 조건 중 하나가 발생하면 리턴한다.

두 함수를 사용하지 않는 것이 좋다. 그러나 락 획득 루틴에서 무한정 대기를 피하기 위해 사용되기도 한다. 특히, 이후 교착 상태를 공부할 때 보게될 것이다.

4. 컨디션 변수

한 쓰레드가 계속 진행하기 전에 다른 쓰레드가 무언가를 하는 것을 기다릴 때, 쓰레드 간에 일종의 시그널 교환 메커니즘이 필요하다.

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cond);

컨디션 변수의 사용을 위해서는 연결된 락이 “반드시” 존재해야 한다. 위 루틴 중 하나를 호출하기 위해서는 그 락을 갖고 있어야 한다.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

// 스레드 1
pthread_mutex_lock(&lock);
while (ready == 0) {
    pthread_cond_wait(&cond, &lock);
}
pthread_mutex_unlock(&lock);

// 스레드 2
pthread_mutex_lock(&lock);
ready = 1; // while (ready == 0) 탈출
pthread_cond_signal(&cond);
pthread_mutex_unlock(&lock);

pthread_cond_wait() 는 호출 쓰레드를 수면(sleep) 상태로 만들고 다른 쓰레드로부터 시그널을 대기한다. pthread_cond_signal() 을 통해 잠자는 쓰레드를 깨울 수 있다.

시그널을 보내고 전역 변수 ready를 수정할 때 반드시 락을 가지고 있어야한다. 이를 통해 경쟁 조건의 발생을 방지한다.

시그널 대기 함수에서는 락을 두번째 인자로 받고 있지만, 시그널 보내기 함수에서는 cond만 인자로 받는다. 이러한 차이의 이유는, 시그널 대기 함수에서는 호출 쓰레드를 재우고 락을 반납(release)해야하기 때문이다.

pthread_cond_wait()는 깨어나서 리턴하기 직전에 락을 다시 획득한다. 처음 락을 획득한 때부터 마지막에 락을 반납할 때까지 pthread_cond_wait()를 실행한 쓰레드들은 항상 락을 획득한 상태로 실행된다는 것을 보장한다.

두 쓰레드 간 시그널을 주고 받을 때, 락과 컨디션이 없이 간단히 플래그를 사용하고 싶을 수도 있다.

// 스레드 1
while (ready == 0); // spinlock

// 스레드 2
ready = 1;

절대로 하지 마라. 일단 성능이 좋지 않고, 오류가 발생하기 쉽다.

5. 컴파일과 실행

pthread플래그를 명령어 링크 옵션 부분에 추가하여 사용하여 pthread 라이브러리와 링크할 수 있도록 명시해야 한다.

prompt> gcc −o main main.c −Wall −pthread

6. 요약

쓰레드 생성과 락을 통한 상호 배제의 구현, 컨디션 변수를 이용한 시그널과 대기 등 pthread 라이브러리의 기본 지식을 소개하였다. 강인하고 효율적인 멀티 쓰레드 코드를 작성하기 위해서는 인내와 세심한 주의가 답이다.

멀티 쓰레드 코드 작성을 위한 몇가지 팁이다.

• 간단하게 작성하라
• 쓰레드 간의 상호동작을 최소로 해라
• 락과 컨디션 변수를 초기화하라
• 반환 코드를 확인하라
• 쓰레드 간에 인자를 전달하고 반환받을 때는 조심해야 한다
• 각 쓰레드는 개별적인 스택을 가진다
• 쓰레드 간에 시그널을 보내기 위해 항상 컨디션 변수를 사용하라
• 메뉴얼을 사용하라

프로세스가 문맥교환을 하고 정보를 저장하기 위해 PCB가 존재하듯이, 쓰레드도 TCB가 존재한다. 프로세스와의 가장 큰 차이는 역시 주소 공간을 공유한다는 것이다.

프로세스와 쓰레드의 더 큰 차이는 스택에 있다. 멀티 쓰레드 프로그램의 주소 공간에는 하나의 스택이 아니라 쓰레드마다 스택이 할당되어있다.

오른쪽은 두개의 쓰레드를 가지는 시스템의 주소공간이다.

스택에서 할당되는 변수들이나 매개변수, 리턴 값 등 스택에 넣는 정보들이 모두 쓰레드의 스택인 쓰레드-로컬 저장소(thread-local storage)에 저장된다.

그러나 스레드 로컬 저장소로 인해 정교한 주소 공간의 배치가 무너진다. 이전에는 주소 공간에 더이상 여유가 없을때만 문제가 생겼다. 이제는 예전만큼 상황이 깔끔하지는 않지만, 스택의 경우는 보통 크지 않아 대부분의 경우 문제가 되지 않는다.

1. 예제: 쓰레드 생성

“A”, “B”를 출력하는 독립적인 두개의 스레드를 실행해보자.

#include <stdio.h>
#include <assert.h>
#include <pthread.h>
#include "common.h"
#include "common_threads.h"

void *mythread(void *arg) {
    printf("%s\n", (char *) arg);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    int rc;
    printf("main: begin\n");
    pthread_create(&p1, NULL, mythread, "A");
    pthread_create(&p2, NULL, mythread, "B");
    // join waits for the threads to finish
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
    printf("main: end\n");
    return 0;
}

메인 프로그램은 mythread()를 실행할 두개의 스레드를 생성한다. 스케줄러의 동작에 따라 다르겠지만, 쓰레드가 생성되면, 즉시 실행될 수도 있고 준비(Ready) 상태에서 실행은 되지 않을 수도 있다.

두개의 쓰레드를 생성한 후, 메인 쓰레드는 pthread_join()을 호출하여 다른 쓰레드의 동작 종료를 기다린다.

코드가 더 앞에 있다고 더 먼저 실행되는 것이 보장되는게 아니다. 쓰레드의 실행 순서가 다양하게 존재할 수 있다. 스케줄링에 따라 “B”가 “A”보다 먼저 출력될 수도 있다.

쓰레드의 생성이 함수 호출과 유사하게 보인다. 함수 호출은, 함수 실행 후 caller에게 리턴한다. 그러나 쓰레드는 생성되고, 생성된 스레드는 호출자와 별개로 실행된다. 함수의 리턴 전에 스레드가 실행될 수도 있고, 그보다 이후에 실행될 수도 있다.

이를 통해, 쓰레드는 일을 더 복잡하게 만든다는 것을 알 수 있다.

2. 훨씬 어려운 이유: 데이터의 공유

아래 코드를 통해 전역 공유 변수를 갱신하는 두 개의 쓰레드 예시를 보자.

#include <stdio.h>
#include <pthread.h>
#include "ommon.h"
#include "common_threads.h"
static volatile int counter = 0;

// mythread()
// Simply adds 1 to counter repeatedly, in a loop
// No, this is not how you would add 10,000,000 to
// a counter, but it shows the problem nicely.

void *mythread(void *arg) {
    printf("%s: begin\n", (char *) arg);
    int i;
    for (i = 0; i < 1e7; i++) {
        counter = counter + 1;
    }
    printf("%s: done\n", (char *) arg);
    return NULL;
}

// main()
//
// Just launches two threads (pthread_create)
// and then waits for them (pthread_join)

int main(int argc, char *argv[]) {
    pthread_t p1, p2;
    printf("main: begin (counter = %d)\n", counter);
    pthread_create(&p1, NULL, mythread, "A");
    pthread_create(&p2, NULL, mythread, "B");
    // join waits for the threads to finish
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
    printf("main: done with both (counter = %d)\n", counter);
    return 0;
}

mythread() 함수는 counter를 10,000,000번 더한다. 두 개의 쓰레드가 모두 실행된다면, 2천만이 나와야할 것이다.

1 prompt> gcc −o main main.c −Wall −pthread
2 prompt> ./main
3 main: begin (counter = 0)
4 A: begin
5 B: begin
6 A: done
7 B: done
8 main: done with both (counter = 20000000)

하지만 단일프로세서라고 하더라도 기대한 대로 결과가 나오지 않는다.

1 prompt> ./main
2 main: begin (counter = 0)
3 A: begin
4 B: begin
5 A: done
6 B: done
7 main: done with both (counter = 19345221)

한 번더 실행해도 이상하다.

1 prompt> ./main
2 main: begin (counter = 0)
3 A: begin
4 B: begin
5 A: done
6 B: done
7 main: done with both (counter = 19221041)

원하는 값이 나오지도 않았고, 실행의 결과도 다르다. 왜 그럴까?

3. 제어없는 스케줄링

왜 이런 현상이 발생하는지를 이해하려면 counter 갱신을 위해서 컴파일러가 생성한 코드의 실행 순서를 이해해야 한다. x86에서 counter를 증가하는 코드의 순서는 다음과 같다.

100 mov 0x8049a1c, %eax
105 add $0x1, %eax
108 mov %eax, 0x8049a1c

현재 counter는 50이 저장되어있다. 쓰레드 1이 그 값을 %eax에 반입하고 1을 더하는 연산을 완료한 시점(105)에 타이머 인터럽트가 발생했다. 이제 쓰레드 2에서 똑같은 연산을 시도하게 되면 50이라는 값을 읽게될 것이다. 그러면 스레드 1, 2가 모두 끝난 시점에 counter 값은 51이 될것이다.

정상적으로 동작하는 프로그램이라면 52가 되어야할 것이다.

이처럼, 명령어의 실행 순서에 따라 결과가 달라지는 상황을 race condition이라고 부른다. race condition 상황에서 실행할때마다 다른 결과를 가진다. 이를 비결정적이라고 한다.

멀티 쓰레드가 같은 코드를 실행할 때, 경쟁 조건이 발생하기 때문에 이러한 코드 부분을 임계 영역(critical section)이라고 부른다. 공유 자원에 접근할 때, 하나 이상의 쓰레드에서 동시에 실행되면 안되는 영역을 일컫는다.

이러한 코드에 필요한 것은 상호 배제(mutual exclusion)이다. 하나의 쓰레드가 임계 영역 내의 코드를 실행 중 일 때는 다른 쓰레드가 실행할 수 없도록 보장해준다.

4. 원자성에 대한 바람

임계 영역 문제의 해결 방안 중 하나는, 아주 강력한 명령어 한 개로 의도한 동작을 수행하여 인터럽트 발생 가능성을 원천적으로 차단하는 것이다.

memory−add 0x8049a1c, $0x1

이는 메모리 상에 어떤 값을 더하는 명령어이다. 하드웨어가 해당 명령의 원자성을 보장한다고 가정하면, 수행 중에 인터럽트가 발생하지 않고 원하는 값으로 변경될 것이다. 만약 인터럽트가 발생한다면, 명령어가 실행이 안된 상태거나 종료된 이후일 것이다.

원자적이라는 말은 “하나의 단위”를 뜻하며 “전부 아니면 전무”로 이해될 수도 있다.

mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c

이 세개의 명령어를 원자적으로 실행하고 싶다고 가정하자. 위 명령어들을 하나의 명령어로 대신할 수 있다면 좋겠지만 일반적으로는 불가능하다. 어셈블리에게 B-tree를 원자적으로 갱신하는 명령어가 필요할까? 놉!

하드웨어적으로는 동기화 함수(synchronization primtives) 구현에 필요한 기본적인 명령어 몇개만 필요하다. 하드웨어 동기화 명령어와 운영체제의 지원을 통해 한번에 하나의 쓰레드만 임계 영역에서 실행하도록 구성된 “제대로 작동하는” 멀티 쓰레드 프로그램을 작성할 수 있다.

5. 또 다른 문제: 상대 기다리기

이제까지는 병행성 문제를 공유 변수 접근에 관련된 쓰레드 간의 상호 작용 문제로 정의하였다. 하지만 실제로는 하나의 쓰레드가, 다른 쓰레드의 어떤 동작이 끝날 떄까지 대기해야하는 상황이 빈번하게 발생한다.

프로세스가 디스크 I/O를 요청하고 응답까지 잠든 경우가 좋은 예시이다. I/O 작업 완료 후 잠들었던 프로세스가 다시 깨어나 이후 작업을 진행한다.

6. 정리: 왜 운영체제에서?

왜 이런걸 운영체제에서 다루는걸까? 이것이 “역사” 이기 때문이다. 운영체제는 최초의 병행 프로그램이었고 운영체제 내에서 사용을 목적으로 다양한 기법들이 개발되었다. 나중에는 멀티 쓰레드 프로그램이 등장하면서 응용 프로그래머들도 이 문제를 고민하게 되었다.

시도 때도 없이 발생하는 인터럽트가 앞서 언급한 모든 문제들의 원인이다. 페이지 테이블, 프로세스 리스트, 파일 시스템 구조 그리고 대부분의 커널 자료 구조들이 올바르게 동작하기 위해서는 적절한 동기화 함수들을 사용해야 한다.

시스템의 전체 페이지들 중 일부분만 메인 메모리에 유지된다는 것을 가정하면, 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있다.

교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것이다. 즉, 디스크로부터 페이지를 가져오는 횟수를 최소로 만드는 것이다.

캐시 히트와 미스이 횟수를 안다면, 프로그램의 평균 메모리 접근 시간 (Average memory access time, AMAT) 을 계산할 수 있다.

$T_{M}$은 메모리 접근 비용, $T_{D}$은 디스크 접근 비용 $P_{Hit}$은 캐시 히트 확률, $P_{Miss}$는 캐시 미스 확률이다.

2. 최적 교체 정책

최적 미스 정책은 미스 발생 횟수를 최소화한다. 페이지를 내보내야할 때, 지금부터 가장 먼 시점에 필요하게 될 페이지를 버린다.

페이지 3 미스가 발생했을 때, 가장 과거에 참조된 페이지 0을 교체하게 된다.

그러나 미래는 일반적으로 알 수 없다. 그래서 실제적인 구현을 불가능하며, 해당 기법은 비교 기준으로서 다른 정책이 얼마나 ‘정답’에 가까운지 알 수 있을 것이다.

3. 간단한 정책: FIFO

시스템에 페이지가 들어오면 큐에 삽입되고, 교체 시에는 큐의 테일에 있는 페이지가 아웃된다.

페이지 3 미스 발생 시, 가장 나중에 접근되었던 페이지 2를 아웃시킨다.

4. 간단한 정책: 무작위 선택

메모리 압박이 있을 때, 페이지를 무작위로 선택하여 교체한다. 구현하기는 쉽지만, 내보낼 블럭을 제대로 선택하려는 노력은 하지 않는다. FIFO보다는 약간 더 좋은 성능을 보이고, 최적 정책보다는 약간 나쁜 성능을 보인다.

5. 과거 정보의 사용: LRU

스케줄링 정책에서와 같이 미래에 대한 예측을 위해 과거 사용 이력을 활용해보자. 어떤 프로그램이 최근에 한 페이지를 접근했다면 가까운 미래에 그 페이지를 다시 접근하게 될 확률이 높다. 빈도수(frequency), 최근성(recency)이라는 과거 정보를 활용하고, 지역성의 원칙(principle of locality)라는 특성에 기반을 둔다.

두가지 방식이 있는데, Least-Frequently-Used(LFU)는 가장 적은 빈도로 사용된 페이지를 교체한다. Least-Recently-Used(LRU)는 가장 오래전에 사용된 페이지를 교체한다.

3번 페이지 미스 발생 시, 가장 오래전에 사용된 페이지 2를 아웃시킨다. 적어도 이 예제에서는, 지금까지 중에 가장 높은 히트 비율을 보여준다.

6. 워크로드에 따른 성능 비교

워크로드에 지역성이 없다면, 어느 정책을 사용하든 상관이 없다.

20%의 페이지들에서 80%의 참조가 일어나고, 나머지 80% 페이지들에 대해서 20%의 참조가 일어나는 상황이다.

FIFO, 무작위 정책보다 LRU가 더 좋은 성능을 보인다.

해당 워크로드는 50개의 페이지들을 순차적으로 참조한다. 1-50을 순차적으로 참조하는 것을 10000번 반복한다.

LRU와 FIFO 정책에서 좋지 못한 성능을 보인다. 오래된 페이지를 내보낸다는 특성으로 인해 캐시 크기가 49라고 할지라도 50개 페이지를 순차 반복하는 경우 히트율이 0%가 된다.

7. 과거 이력 기반 알고리즘 구현

LRU를 완벽하게 구현하기 위해서는 많은 작업이 필요하다. 페이지 접근마다 해당 페이지를 자료구조의 맨 앞으로 이동해야되고, 가장 오래전에 사용된 페이지 관리를 위해 모든 메모리 참조 정보를 기록해야한다.

이 작업을 더 효율적으로 하기 위해, 하드웨어의 지원을 받는다. 페이지의 접근이 있을 때마다 하드웨어가 시간 필드를 갱신한다. 이렇게 갱신된 시간 필드를 활용해 페이지 교체를 수행한다.

페이지 수가 증가하게 되면, 가장 오래 전에 사용된 페이지를 찾는 것은 매우 고비용의 연산이 된다. 가장 오래된 페이지를 꼭 찾아야만 할까? 대신 비슷하게 오래된 페이지를 찾아도 되지 않을까?

8. LRU 정책 근사하기

연산량이라는 관점에서 볼 때, LRU를 근사하는 식으로 만들면, 구현이 훨씬 쉬워진다. 실제로 현대의 많은 시스템도 이런 방식을 택하고 있다.

이 개념을 위해 use bit(reference bit)라는 약간의 하드웨어의 지원이 필요하다. 페이지가 참조될 때마다 하드웨어는 use bit를 1로 설정한다. 운영체제는 이를 0으로 바꾼다.

use bit를 적절히 활용하기 위한 방법 중, 시계 알고리즘(clock algorithm)이란 것이 있다. 시계 바늘이 특정 페이지를 가르키면서 use bit가 1이라면 최근에 사용되었다는 뜻이기 때문에 교체 대상이 되지 않는다. 해당 페이지의 user bit를 0으로 설정하고 다음 페이지를 가르킨다. use bit가 0일 페이지를 가르킨다면 그 페이지가 교체 대상이 된다. 최악의 경우(모든 use bit가 1인 경우) 모든 페이지를 다 돌 수도 있다.

완벽한 LRU보다 좋은 성능을 보이지는 않지만, 과거 정보를 고려하지 않는 다른 기법에 비해서는 성능이 더 좋다.

9. 갱신된 페이지(Dirty Page)의 고려

시계 알고리즘을 추가적으로 개선하기 위해서, OS가 페이지 교체 대상을 선택할 때, 메모리에 탑재된 이후에 변경 여부를 추가적으로 고려한다.

어떤 페이지가 변경되어 dirty 상태가 되었다면, 그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야 하기 때문에 비용이 비싸다. 만약 변경되지 않았다면 내보낼 때 추가 비용은 없다. 때문에 dirty page 대신 수정된 적 없는 페이지를 내보내는 것을 선호한다. 하드웨어는 이를 지원하기 위해 dirty bit(modified bit)를 둔다.

예를 들어, 시계 알고리즘은 교체 대상을 선택할 때 사용되지 않은 상태이고 깨끗한 페이지를 먼저 찾는다. 이런 페이지를 찾지 못할 경우, 수정되었지만(더티 상태이지만) 한동안 사용되지 않았던 페이지를 찾는다.

10. 다른 VM 정책들

페이지 교체 정책 말고도 여러 정책이 존재한다. 운영체제는 언제 페이지를 메모리로 불러들일지를 결정하기 위한 페이지 선택 정책이 존재한다.

대부분의 운영체제는 요구 페이징(demand paging) 정책을 사용한다. 말 그대로 “요청된 후 즉시” 즉, 페이지가 실제로 접근될 때 메모리로 읽어들인다.

운영체제는 어떤 페이지가 곧 사용될 것이라는 것을 대략 예상할 수 있기 때문에 미리 메모리로 선반입(prefetching)할 수도 있다. 예를 들어 페이지 P가 탑재될 때, P + 1도 함께 탑재되어야 한다고 가정할 수 있다.

또 다른 정책은 운영체제가 변경된 페이지를 디스크에 반영하는데 관련된 방식이다. 한번에 한 페이지 씩 디스크에 쓰는 것이 아니라, 기록해야할 페이지를 메모리에 모은 후, 한 번에 기록한다. 이를 clustering 또는 grouping이라고 부른다.

11. 쓰래싱 (Thrashing)

메모리 사용 요구가 감당할 수 없을만큼 많고, 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우 어떡할까?

이런 경우 시스템은 끊임없이 페이징을 할 수 밖에 없고, 이런 상황을 쓰래싱(Thrashing)이라고 한다.

몇몇 초기 운영체제들은 다수 프로세스 중 일부 프로세스의 실행을 중지시키고, 나머지 프로세스를 메모리에 올려 실행하도록 했다.

최신 운영체제들은 더 과감한 방법을 사용하기도 한다. 예를 들어, Linux의 일부 버전에서는 ‘메모리 부족 킬러’를 동작시켜 메모리 요구가 많은 프로세스를 강제로 종료함으로써 메모리 부족 상황을 해결하려고 시도한다. 이 방법은 효과적으로 메모리 부족 문제를 해결할 수 있지만, 중요한 프로세스를 종료하게 되면 다른 문제가 발생할 수 있다.

12. 요약

지금까지 언급했던 알고리즘의 중요성은 점차 퇴색되고 있다. 메모리 접근 시간과 디스크 접근 시간의 차이가 점차 증가하고 있기 때문이다. 디스크에 페이징 하는 비용이 너무 비싸기 때문에 빈번한 페이징을 감당할 수 다. 과도한 페이징에 대한 최적의 해결책은 아주 간단하다. 그냥 더 많은 메모리를 구입해라.

→ ??

이를 위해 메모리 계층에 레이어의 추가가 필요하다. 현대 시스템에서는 하드 디스크 드라이브가 이 역할을 맡아, 메모리 계층 최하단에는 HDD가 존재하고 그 위에 물리 메모리가 있다.

핵심 질문: 물리 메모리 이상으로 나아가기 위해서는 어떻게 할까? OS는 어떻게 크고 느린 장치를 사용하면서 마치 커다란 가상 주소 공간이 있는 것처럼 할 수 있을까?

왜 프로세스에게 굳이 큰 주소 공간을 제공해야할까?

편리함과 사용 용이성 때문이다. 주소 공간이 충분히 크면, 프로그램의 자료 구조들을 위한 충분한 메모리 공간이 존재하는지 걱정하지 않아도 된다. 필요할 경우 OS에게 요청만 하면 될 것이다.

스왑 공간의 추가를 통해 OS는 실행되는 각 프로세스들에게 큰 가상 메모리가 있는 것 같은 환상을 줄 수 있다.

1. 스왑 공간 (Swap space)

디스크에 페이지들을 저장할 수 있는 공간을 스왑 공간이라고 부른다. 메모리 페이지를 읽어서 이곳에 쓰고(swap out) 스왑 공간에서 페이지를 읽어 메모리에 탑재시킨다(swap in). OS는 스왑 공간의 모든 페이지들의 디스크 주소를 가지고 있어야 한다.

프로세스 0,1,2가 물리 메모리를 공유하고 있다. 유효한 페이지만 물리 메모리에 존재하고, 나머지들은 디스크에 swap out 되어있다. 프로세스 3의 경우는 모든 페이지가 스왑 공간에 있어, 현재 실행 중이 아님을 알 수 있다.

이를 통해, 스왑 공간의 사용을 통해, 시스템이 실제 물리적으로 존재하는 메모리 공간보다 더 많은 공간이 존재하는 것처럼 가장할 수 있다는 것을 알 수 있다.

2. Prsent Bit

이제 페이지 스왑을 위한 기능을 다뤄보자. 하드웨어 기반의 TLB를 사용하는 시스템을 가정하자.

페이지가 디스크로 스왑되는 것을 가능하게 하려면, 하드웨어가 PTE에서 해당 페이지가 물리 메모리에 존재하지 않는다는 것을 표현해야한다(소프트웨어 TLB의 경우는 OS가).

하드웨어는 present bit를 사용하여 1인 경우 페이지가 물리 메모리에 존재한다는 것을 의미하고, 0일 경우 메모리에는 존재하지 않고 디스크 어딘가에 존재한다는 것이다. 물리 메모리에 존재하지 않은 페이지에 접근하는 행위를 Page Fault 라고 부른다.

3. Page Fault

하드웨어 기반/ 소프트웨어 기반 TLB 모두 페이지 폴트에 대한 처리는 OS가 맡는다. OS의 페이지 폴드 핸들러가 그 처리 방식을 규정한다.

만약 요청된 페이지가 메모리에 없고 디스크에 스왑되었다면, 해당 페이지를 메모리로 swap in 한다. 원하는 페이지가 어디에 있는지를 알기 위해, 스왑 공간 상의 위치를 페이지 테이블에 저장한다.

디스크 I/O가 완료되면 PTE를 PFN을 페이지의 메모리 위치로 갱신하고, page fault를 발생시킨 명령어를 재실행한다. 최종적으로, TLB에 주소 변환 정보를 찾아 물리 주소에서 원하는 데이터나 명령어를 가져오게 된다.

I/O 전송 중에는, 해당 프로세스가 Block된 상태여야 한다. 페이지 폴트의 처리 동안 OS는 다른 프로세스를 실행시킨다. 이런 식으로 페이지 폴트 작업과, 다른 프로세스의 실행을 중첩(overlap)시키는 것이 멀티 프로그래밍 시스템에서 하드웨어를 최대한 효율적으로 사용하는 방법 중 하나이다.

4. 메모리에 빈 공간이 없다면?

메모리에 빈 공간이 없다면, 탑재하고자 하는 페이지들을 반입하기 위해 일부 페이지들을 out 시키려 할 것이다. 이를 위한 페이지 교체 정책이 필요하다. 다음 장에서 자세히 다룰 예정이다.

페이지 교체 정책이 비효율적일 경우 프로그램이 디스크와 비슷한 속도로 실행되는 참사가 발생할 수 있다.

5. 페이지 폴트의 처리

프로그램이 메모리에서 데이터를 가져올 때 어떤 일이 발생할까?

하드웨어 기반

하드웨어 기반에서 TLB 미스 시, 세가지 경우가 있다.

1. 페이지가 존재하며, 유효한 경우 (물리 메모리에 페이지가 있지만, TLB에는 없는 경우)
   • TLB 미스 핸들러가 PTE에서 PFN을 가져와 명령어를 재시도한다.
2. 페이지가 유효하지만, 존재하지 않는 경우 (페이지가 swap out 되어있는 경우)
   • 페이지 폴트 핸들러의 실행
3. 페이지가 유효하지 않은 경우 (잘못된 접근)
   • 프로그램 버그 등으로 잘못된 주소를 접근하는 경우의 처리, OS의 트랩 핸들러가 처리한다.

소프트웨어 기반

OS의 페이지 폴트 처리 과정은 다음과 같다.

1. 탑재할 페이지를 위한 물리 프레임 확보
   • 여유 프레임이 없다면, 교체 알고리즘을 실행한다.
2. 물리 프레임 확보 후, I/O 요청을 통해 페이지를 메모리로 swap in 한다.
3. 작업 완료 후, OS는 페이지 테이블을 갱신하고, 명령어를 재시도 한다.
   • 재시도 시 TLB 미스가 발생할 것이다.

6. 교체는 실제 언제 일어나는가?

지금까지는 메모리 공간이 부족할 때 교체가 일어나는 상황을 가정했다. 그러나 이는 효율적이지 않다. 이를 위해 OS는 항상 어느 정도의 여유 메모리 공간을 확보하고 있다.

대부분의 운영체제는 여유 공간의 최솟값(low watermark), 최댓값(high watermark)을 설정한다. 여유 공간이 최솟값 아래로 떨어지면, swap demon / page demon이라고 불리는 백그라운드 스레드를 통해 여유 공간이 최댓값만큼 생길 때까지 페이지를 제거한다.

동시에 여러개를 교체하면 성능이 개선된다. 이를 위 많은 시스템들이 페이지들을 클러스터(cluster)나 그룹(group)으로 나누어 한번에 스왑 파티션에 저장한다.

백그라운드 페이징 스레드를 위해서는, 그림 24.3의 과정이 조금 수정되어야 한다. 교체를 직접 수행하는 것이 아니라, 사용할 수 있는 페이지 여유 공간을 확인하고 부족할 경우 페이지를 비우는 작업을 수행한다.

7. 요약

프로세스가 보기에는 자신의 개별적인 연속된 가상 메모리를 접근하는 것처럼 보인다. 실제로 페이지들은 물리 메모리 임의(불연속적인)위치에 배치되며, 때로는 디스크에서 가져와야 할 때도 있다.

전에 말했듯이, 선형 페이지 테이블을 예시로 들면, 32비트 운영체제의 경우 페이지 테이블 하나의 크기는 4MB 정도 되고, 프로세스가 100개라면 페이지 테이블을 위해 400MB의 메모리가 필요하다.

핵심 질문: 페이지 테이블을 어떻게 더 작게 만들까? 선형 페이지 테이블은 메모리를 과하게 차지한다. 어떻게 테이블의 크기를 줄일까? 주요 개념은 무었이고, 어떤 자료구조를 사용할까?

1. 간단한 해법: 더 큰 페이지

페이지 테이블의 크기를 줄이는 가장 간단한 방법은 페이지의 크기를 늘리는 것이다.

16KB의 페이지를 가정한다면, 18비트의 VPN과 14비트의 offset을 가질 것이다. 4KB 페이지 방식에 비해 VPN이 4배 줄었기 때문에, 테이지 테이블의 크기도 1MB로 줄어들 것이다.

그러나 페이지 크기 증가의 가장 큰 문제는 내부 단편화이다. 내부에 사용되지 않는 공간이 낭비된다. 이는 곧 메모리의 빠른 고갈로 이어진다. 그래서 대부분의 시스템음 4KB/8KB의 페이지를 사용한다.

2. 하이브리드 접근 방법: 페이징과 세그먼트

1KB 크기의 페이지를 갖는 16KB의 주소 공간을 예로 들어보자. 코드 페이지(VPN 0)은 PFN 10에, 힙 페이지(VPN 4)는 PFN 23에, 두개의 스택 페이지(VPN 14, 15)는 PFN 28, 4에 매핑되어 있다. 보이는 것처럼 대부분의 페이지 테이블이 비어있다. 32비트 주소 공간 페이지에서는 더 심할 것이다.

이를 위해 코드, 힙, 스택 세그먼트에 대해 페이지 테이블을 두는 방식을 고안했다.

각 코드, 힙, 스택 세그먼트는 각각의 페이지 테이블을 가진다. 각 테이블은 베이스와 바운드 레지스터를 가져 테이블의 위치와 범위를 표시한다. 각 프로세스는 3개의 페이지 테이블을 가지게 된다.

TLB 미스가 발생하면, seg 비트를 통해 어떤 베이스-바운드 레지스터를 사용할지 결정하고, VPN과 Offset을 통해 주소 변환이 이루어진다.

하이브리드 방식에서 사용되지 않은 페이지는 테이블에서 공간을 차지하지 않아 메모리 관점에서 더 좋다. 그러나 문제 또한 존재한다.

• 여전히 세그멘테이션을 사용한다. 이는 주소 공간에 사용에 있어 특정 패턴을 가정하기 때문에 유연하지 않다.
• 외부 단편화를 유발한다. 페이지 테이블은 크기에 제한이 없기 때문에 다양한 크기를 가져, 메모리 상에서 공간 확보가 더 복잡하다.

3. 멀티 레벨 페이지 테이블

선형 페이지 테이블을 트리 구조로 표현한다. 매우 효율적이기 때문에 현대 시스템에서 많이 사용한다(x86).

멀티 레벨 페이지 테이블의 기본 개념은 간단하다. 먼저, 페이지 테이블을 페이지 크기 단위로 나눈다. 만약 페이지 테이블의 페이지가 유효하지 않은 항목만 있다면 해당 페이지는 할당하지 않는다.

헷갈리면 안되는게, 주소 공간의 페이지를 의미하는게 아니라, 페이지 테이블을 페이지의 단위로 나눈 것이다.

페이지 디렉터리(page directory)라는 자료구조를 통해 각 페이지의 할당 여부와 위치를 파악할 수 있다.

페이지 디렉토리는 페이지당 하니의 entry를 가지고 있다. 페이지 테이블의 시작 부분을 가진다. 즉 베이스 레지스터 같은 느낌이다. page directory entry가 유효한지 알려주는 valid bit와 page frame number로 구성된다.

페이지 디렉터리를 통해 실제로 사용중인 페이지 테이블에만 접근할 수 있도록 해줘 메모리 낭비를 방지할 수 있다.

멀티 레벨 페이지 테이블은 몇가지 장점이 있다.

1. 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당되기 때문에, 보다 작은 크기의 페이지 테이블로 주소 공간을 표현할 수 있다.
2. 페이지 테이블을 페이지 크기로 분할하기 때문에 메모리 관리에 유용하다.
   • 페이지 테이블의 할당이나 확장할 때, free 페이지 풀에서 가져다 쓰면된다.
   • 선형 테이블은 연속된 물리 공간을 가져야하지만, 페이지 디렉터리를 사용하면 페이지들이 물리 메모리 안에서 산재해있어도 되므로 더욱 유연하다.

그러나 TLB 미스 시, 주소 변환을 위해 두 번의 메모리 로드가 발생한다. 페이지 디렉터리 한 번, PTE 한 번.

예제

해당 방식의 주소 공간은, 페이지 디렉터리 엔트리(PDE)의 위치를 찾기 위한 page directory index와, 페이지 테이블의 페이지에서 매핑할 PFN을 찾기 위한 page table index를 가진다.

11 1111 1000 0000

다음 주소를 멀티 레벨 페이지 테이블 방식을 이용하여 변환해보자. 첫번째 4비트(1111)은 15번째 PDE를 나타낸다. PDE 15의 vaild비트가 1이기 때문에, 페이지 테이블의 페이지에 접근할 수 잇다.

이후의 4비트(1110)은 페이지 내에서 원하는 페이지 엔트리(14번째)를 찾는다. 이제 주소의 VPN 부분이 PFN으로 변환되어(111 1110 → 0011 0111) 메모리 접근을 하게될 것이다.

2단계 이상 사용하기

페이지 디렉터리가 너무 커질 수도 있다. 이런 경우, 페이지 디렉터리 자체를 멀티 페이로 나누어서 트리의 단계를 늘릴 수 있다.

4. 역 페이지 테이블

이 방법은 시스템에 단 하나의 페이지 테이블만 둔다. 페이지 테이블은 물리 페이지를 가상 주소의 페이지로 변환한다. 역 페이지 테이블의 엔트리는 물리 페이지를 사용 중인 프로세스의 번호와 해당 가상 페이지 번호를 가지게 된다.

5. 페이지 테이블을 디스크로 스와핑하기

지금까지는 페이지 테이블은 커널이 소유하고 있는 물리 메모리 영역에 있다고 가정했다. (MMU에 저장)

아무리 페이지 테이블 크기를 줄이기 위한 시도를 하고 있지만, 여전히 클수도 있다. 그래서 일부 시스템은 페이지 테이블을 커널의 가상 메모리에 위치시키고, 페이지 테이블을 디스크로 스왑시키기도 한다.

다음 단원에서 자세히 나오게 된다.

핵심 질문: 주소 변환 속도를 어떻게 향상시킬까? 주소 변환을 어떻게 빨리 할까? 페이징에서의 추가 메모리 참조를 어떻게 피할까? 어떤 하드웨어가 추가로 필요할까? OS는 어떤 식으로 이에 개입할까?

OS는 이를 위해 하드웨어의 도움을 받는다. 빠른 주소 변환을 위해 TLB(Translation-lockaside buffer)가 도입되었다. TLB는 MMU의 일부로, 자주 참조되는 가상주소-물리주소 변환 정보를 저장하는 하드웨어 캐시이다.

가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 정보가 있는지를 확인한다. 있을 경우 페이지 테이블에 접근하지 않아도 되기 때문에 페이징의 성능이 크게 향상된다.

1. TLB의 기본 알고리즘

하드웨어 부분의 알고리즘은 다음과 같다.

가상 주소에서 VPN을 추출하고, TLB에 존재하는지 확인한다. 존재한다면(TLB hit) PFN을 추출하여 물리 주소로 변환하고, 메모리에 접근할 수 있다.

만약 변환 정보가 없다면(TLB miss) 페이지 테이블에 접근해야한다. 가상 메모리 참조의 유효성을 검사를 거쳐 유효할 경우 변환 정보를 TLB로 읽어들이게 된다. 해당 작업은 시간이 오래 걸리지만, 이후 같은 가상 주소로 다시 접근한다면, TLB에 정보가 있어 메모리 참조가 빠르게 처리된다.

모든 캐시 설계 철학처럼, “주소 변환 정보가 대부분의 경우 캐시에 있다”라는 가정을 전제로 만들어졌다. TLB 미스가 많아질수록 페이지 테이블 참조를 위한 메모리 접근 횟수가 많아지고, 프로그램이 느려지게 될 것이다.

2. 예제: 배열 접근

배열 a를 순차적으로 탐색한다면, a[0], a[3], a[7]을 접근할 때만 TLB 미스가 발생하고 이외에는 TLB히트이다. 만약 더 큰 페이지의 크기를 가진다면 TLB 히트의 비율이 더 높아질 것이다.

일반적인 경우 페이지는 4KB이기 때문에, 위 예제에서는 a[0]에서 한번만 미스가 발생할 것이다.

TLB 역시 일종의 캐시이기 때문에, 시간 지역성과 공간 지역을 가진다. 실제로 많은 프로그램들은 공간/시간 지역성을 띄고있기 때문에 TLB가 더욱 효과적일 것이다.

3. TLB 미스는 누가 처리할까

CISC 시절에는 하드웨어가 TLB 미스를 처리했다. 하드웨어는 페이지 테이블 base register 정보를 가지고 있고, 미스 발생시 하드웨어에서 테이블 엔트리 정보를 TLB로 반입한 후 미스가 발생했던 명령어를 재실행한다.

현재는 대부분의 컴퓨터가 RISC이다. RISC에서는 소프트웨어가 TLB를 관리한다. TLB 미스가 발생하면 예외 시그널을 발생시켜 커널모드로 진입하고, 트랩 핸들러의 실행을 통해 TLB를 갱신하게 된다.

소프트웨어 관리 TLB의 중요한 사항 2가지를 짚어보자.

• 시스템 콜의 트랩 핸들러와는 조금 차이가 있다. 시스템 콜은 호출 후에 다음 코드가 실행되지만, TLB의 트랩 핸들러가 종료되면 기존 코드를 다시 실행한다.
• TLB 미스 핸들러의 실행에 대해 TLB 미스가 발생할 수 있다. 그래서 OS는 TLB 미스 핸들러를 물리 메모리에 영구적으로 위치시키기도 한다. 이를 통해 핸들러에 대해서는 항상 TLB 히트가 발생한다.

TLB를 소프트웨어로 관리함을 통해, 하드웨어 변경 없이 테이블 구조를 유연하게 변경할 수 있고, 하드웨어가 처리할 일이 없어 더 단순하다.

4. TLB의 구성: 무엇이 있나?

VPN | PFN | 다른 비트들

변환 정보 저장 위치에 제약이 없도록, 모든 항목마다 VPN과 PFN을 가지고 있다. 그래서 하드웨어 측면에서 보면, TLB는 완전 연관 캐시이다.

다른 비트들에는 뭐가 있을까? vaild bit는 유효한 변환 정보를 가지는지 나타낸다. protection bit는 접근 권한(read/write/exec)을 표시한다. 그 이외에도 주소 공간 식별자, dirty bit 등이 존재한다.

5. TLB의 문제: 문맥 교환

TLB의 VPN-PFN 변환 정보는 그것을 탑재시킨 프로세스에서만 유효하다. 만약 프로세스 간 context switch 가 발생한다면 어떡할까?

한 가지 방법은 문맥 교환 시에 TLB를 비우는 것이다. 이를 통해 잘못된 변환 정보의 사용은 막을 수 있겠지만, 새로운 프로세스가 실행될 때마다 TLB 미스가 발생할 것이고, 문맥 교체가 잦을 경우 성능에 부담이 갈 것이다.

이런 부담을 줄이기 위해 몇몇 시스템은 문맥 교환이 발생하더라도 TLB의 내용을 보존할 수 있는 하드웨어 기능을 추가했다. 주소 공간 식별자(Address space Identifier, ASID) 필드를 통해 프로세스 별로 TLB 변환 정보를 구분할 수 있다 (PID와 유사하다).

6. 이슈: 교체 정책

모든 캐시가 그러하듯, TLB에서도 캐시 교체 정책이 매우 중요하다.

가장 흔한 방법은 최저 사용 빈도(least-recently used, LCU) 방식이다. 오래 사용되지 않은 항목일수록 사용될 가능성이 적어 교체 대상으로 적합하다고 가정한다.

랜덤 정책도 있다. 구현이 간단하고 예외 상황의 발생을 피할 수 있다.

7. 실제 TLB

MIPS R4000는 32비트 주소 공간에서 4KB 페이지를 지원한다.

• 가상 페이지 번호(VPN): 19비트로 할당되며, 주소 공간의 절반은 사용자 주소 공간으로 할당된다.
• 물리 프레임 번호(PFN): 24비트로 할당되며, 최대 64GB의 메모리(2^24 개의 4KB 페이지들) 지원이 가능하다.

TLB 항목에는 또한 몇 가지 중요한 비트들이 포함되어 있다:

• 전역 비트(G): 이 비트는 프로세스 간에 공유되는 페이지들을 위해 사용된다. 전역 비트가 설정되면 ASID(Address Space Identifier)는 무시된다.
• ASID 필드: 8비트로, 운영체제는 이 필드를 통해 주소 공간을 구분한다.
• 일관성 비트(C): 이 비트는 페이지가 하드웨어에 어떻게 캐시되어 있는지 판별하는 데 사용된다.
• 더티 비트(D): 페이지가 갱신되면 세팅된다.
• 유효 비트(V): 항목에 유효한 변환 정보가 존재하는지 나타낸다.
• 페이지 마스크 필드: 여러 개의 페이지 크기를 지원할 때 사용된다. 그림에는 나타나있지 않다.

• 가변 크기의 조각들로 분할 (세그멘테이션)

  그러나 다양한 크기로 분할하면서 공간에 대한 단편화가 많이 발생하고, 할당이 어려워진다.

• 동일 크기의 조각으로 분할

  이번 장에서 배우게 될 Paging이 이런 방식이다. 주소 공간을 Page라고 부르는 고정 크기 단위로 나눈다. 물리 메모리는 페이지 프레임이라고 불리는 페이지 배열을 통해 페이지들을 저장한다.

핵심 질문: 페이지를 사용하여 어떻게 메모리를 가상화할 수 있을까? *세그멘테이션의 문제점을 해결하기 위해 페이지를 사용해 어떻게 메모리를 가상화할 수 있을까? 공간과 시간적인 오버헤드를 어떻게 줄일까?*

1. 간단한 예제 및 개요

명확한 이해를 위해 간단한 예시를 들어보자. 총 크기가 64바이트이고 16바이트 페이지 4개로 구성된 주소 공간의 상황을 가정하자. 그러나 실제 주소 공간은 32비트는 4GB, 64비트는 훨씬 크다.

물리 메모리는 128바이트의 크기를 가지고, 고정 크기의 슬롯을 가진다. 일부는 OS를 위한 커널 메모리 공간이다.

페이징은 이전 방식에 비해 많은 장점이 있다.

1. 유연성

   프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 예를 들어, 힙과 스택이 커지는 방향, 어떻게 사용되는 가를 고려할 필요가 없다.

2. 빈 공간 관리가 단순하다.

   만약 64바이트 주소 공간을 물리 메모리에 배치하기 원한다면, 운영체제는 4개의 비어있는 페이지를 찾기만 하면 된다. 이를 위해 OS는 고정 크기의 빈 공간 리스트를 가지고 찾아줄 것이다.

주소 공간의 각 가상 페이지 테이블에 대한 물리 메모리의 위치가 필요할텐데, 운영체제는 프로세스마다 페이지 테이블이라는 자료구조를 유지한다. 주소 공간의 가상 페이지를 물리 메모리에서의 위치가 어디인지 알려주는 주소 변환 정보를 가지고 있다.

페이지 테이블은 프로세스마다 존재한다는 것을 숙지해야한다. 공유 중인 페이지가 없다면,

이제 주소 변환을 실제로 해보자.

movl <virtual address>, %eax

주소 를 eax 레지스터에 탑재하는 과정을 살펴보자

먼저 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 내의 오프셋 2개의 구성 요소를 분할 한다. 위 예의 경우 주소 공간의 크기는 64이기 때문에 6비트가 필요하다($2^6=64$).

페이지의 크기는 64바이트의 공간 중에 16바이트이다. 즉, 4페이지 선택할 수 있어야 하기 때문에 상위 2비트가 그 역할을 한다. 나머지 비트는 페이지 내에서 우리가 원하는 바이트의 위치를 나타낸다.

movl 21, %eax

같은 경우는 아래와 같은 가상 주소 공간을 가진다.

페이지 페이블에서는 VPN을 물리 페이지 번호(물리 프레임 번호)로 매핑한다. (PFN, PPN) 해당 예시의 경우 VPN 1은 PFN 7(111)에 매핑된다고 가정하자. OS는 VPN을 PFN으로 교체하여 가상 주소 변환을 한다.

오프셋은 그대로 가져가고, 그 결과인 1110101이 물리 메모리의 주소이다.

그렇다면, 페이지 테이블은 어디에 저장될까? 페이지 테이블의 내용은 무엇인가? 페이지 테이블의 크기는 얼마인가? 페이징이 시스템을 느리게 만들지는 않을까? 지금부터 알아보자

2. 페이지 테이블은 어디에 저장되는가

페이지 테이블은 매우 커질 수 있다.

4KB 크기의 페이지를 가지는 32비트 주소 공간을 상상해보자. 이 가상 주소는 20비트의 VPN과 12 비트의 오프셋을 가진다. (1KB 페이지를 위해 10비트가 필요하기 때문에, 4KB에서는 12비트가 필요함)

20비트 VPN은 OS가 각 프로세스를 위해 관리해야하는 변환의 개수가 $2^{20}$이라는 것을 의미한다. 물리 주소로의 변환 정보를 저장하기 위해 페이지 테이블 항목(page table entry, PTE)마다 4바이트가 필요하다고 가정하면, 각 페이지 테이블을 저장하기 위해서 4MB($2^{20} * 4byte$) 가 필요하게 된다.

만약 프로세스가 100개가 실행중이라면, 400MB가 필요하게 된다. 만약 64비트 주소 공간을 사용한다면, 더더욱이 커질 것이다.

페이지 테이블의 큰 크기 때문에, 프로세스의 페이지 테이블을 MMU 안에서 유지하지 않는다. 일단 지금은 페이지 테이블은 운영체제가 관리하는 물리 메모리에 상주한다고 가정하자.

나중에 운영체제 메모리 자체의 많은 부분이 가상화 될 수 있다는 것을 알게될 것이다. 페이지 테이블은 OS의 가상 메모리에 저장되기도 하고, 디스크로 스왑되기도 한다.

3. 페이지 테이블에는 실제 무엇이 있는가

페이지 테이블의 구성에 대해 살펴보자. 페이지 테이블은 가상 주소를 물리 주소(물리 프레임 번호)로 매핑하는데 필요한 자료구조이다. 가장 간단한 형태는 선형 페이지 테이블이다. VPN을 인덱스로 PTE를 검색할 수 있다.

이후 페이징 관련 문제를 해결하기 위해 고급 자료 구조가 사용된다.

• Valid bit - 특정 변환의 유효여부 표시, 주소 공간의 스택과 힙 사이는 유효하지 않을 것이다. 이렇게 할당되지 않은 공간을 표시하기 위해 필요하다.
• protection bit - protection bit가 허용하지 않는 방식으로 페이지에 접근하려 하면 트랩 발생
• present bit - 페이지가 물리 메모리에 있는지, 디스크에 있는지(스왑 아웃)
• dirty bit - 메모리에 반입된 후 페이지의 변경 여부
• reference(access) bit - 페이지의 접근 여부 추적, 페이지 인기도 기반의 페이지 교체 알고리즘에 용이하다.

4. 페이징: 너무 느림

페이지 테이블의 크기가 메모리 상에서 매우 크게 증가할 수 있다. 페이지 테이블로 인해 처리 속도가 저하될 수 있다. 간단한 명령어를 예로 들어보자

movl 21, %eax

하드웨어가 주소 변환을 담당한다고 가정하자.

가상주소(21)을 물리주소(117)로 변환하기 위해서 시스템은 페이지 테이블에서 적절한 페이지 테이블 항목 가져오기 / 변환 수행 / 물리 메모리에서 데이터 탑재의 과정을 거친다. 이렇게 하기 위해, 하드웨어는 현재 실행 중인 프로세스의 테이블 페이지 위치를 알아야한다. 일단 하나의 페이지 테이블 베이스 레지스터가 페이지 테이블의 시작 주소를 저장한다고 가정하자

원하는 PTE의 위치를 찾기 위해 1-4 라인의 연산을 수행한다. 이후 페이지 테이블에 접근하여 물리 주소를 매핑하게 된다. 이 경우, 모든 메모리 참조에 대해 먼저 페이지 테이블에서 변환 정보를 반입해야하기 때문에 반드시 한번의 추가적인 메모리 참조가 필요하다. 메모리 참조는 비용이 비싸고, 프로세스의 속도도 2배 이상 느려진다.

하드웨어와 소프트웨어의 신중한 설계가 없다면, 페이지 테이블로 인해 시스템이 매우 느려질 수 있고 많은 메모리를 차지하게 된다.페이징이 메모리 가상화에 필요한 훌륭한 정책처럼 보이지만 이 문제를 해결해야 한다.

5. 메모리 트레이스

int arr[1000];
...
for (i = 0; i < 1000; i++) {
    arr[i] = 0;
}

페이지 크기를 1KB라고 가정하면, 정수 1000개 (4000바이트)를 위해서는 4개의 페이지 테이블이 필요할 것이고, 코드를 위해 1개의 페이지 테이블이 더 필요할 것이다.

메모리 참조의 경우 명령어 반입시 2번(명령어 위치 파악/ 명령어 자체)한다. mov 명령어에서도 한번의 메모리 참조가 이루어지고, 페이지 테이블 한번 접근, 다음 배열 접근을 위해 한번 또 참조된다.

위 코드를 5번 실행시켰을 때의 메모리 트레이스다.

루프 1번에 대해서 보면, 네번의 명령어 반입 / 한번의 메모리 갱신 / 두 과정에서 주소 변환을 위한 페이지 테이블 참조까지 루프당 10번의 메모리 접근이 필요하다. 이렇게 간단한 코드에도 메모리가 복잡하게 동작함을 알 수 있다.

특히, 빈 공간 관리에 초점을 둘 것이다.

페이징 개념을 다룰 때 논의하겠지만, 관리하는 공간이 고정된 크기를 가진다면 빈 공간 관리가 더 쉽다. 그러나 빈 공간들이 가변-크기를 가지게 된다면 재미있어진다. 이런 경우는 malloc() - free()를 사용하는 사용자 수준 메모리 라이브러리나, 세그멘테이션 기반 물리메모리 관리 시스템에서 발생한다. 어느 경우네는 외부 단편화가 존재하게 되기 때문에 빈 공간 관리가 중요하다.

1. 가정

• malloc(), free()에서 제공하는 것과 같은 기본 인터페이스를 가정
• 외부 단편화 방지에 초점을 둔다
• 클라이언트에게 할당된 메모리는 재배치될 수 없다.

2. 저수준 기법들

분할과 병합

다음과 같이 30바이트의 힙이 있다고 가정하자.

빈 공간 리스트에는 2개의 원소가 있다. 각 원소는 주소와 주소 공간의 길이를 가진다.

만약 10바이트가 초과하는 요청에 대해서는 실패하여 NULL을 반환하게 된다. 그러나 10바이트보다 작은, 1 바이트의 요청이 온다면 어떻게 될까?

분할 작업이 발생한다. 2번째 빈 공간이 1과 9의 청크로 나뉘어지게 되고, 1바이트 청크는 리턴되고 남은 청크는 리스트에 남게 된다. 시작 주소가 21이되고 길이가 9로 줄었다.

첫번째 예시에서 이번에는 free(10)이 발생한 상황을 생각해보자. 반환된 공간이 빈 공간 리스트에 들어갈 것이다.

이 경우 10 바이트가 넘는 요청에 대해서 처리를 하지 못하게 될 것이다. 이를 위해 병합 작업이 이루어진다. 새로 해제된 공간이 좌우의 청크와 인접해있다면 병합한다.

할당된 공간의 파악

free(void *ptr) 인터페이스는 크기를 매개변수로 받지 않는다. 포인터가 인자로 전달되면 메모리 영역의 크기를 알아서 파악하여 해당 공간을 빈 공간 리스트에 포함시킨다.

이를 위해 추가 정보를 header블럭에 저장한다.

헤더 블럭에는 할당된 공간의 크기, 무결성 검사를 위한 매직 넘버 등의 기타 정보를 저장한다.

그래서 만약 사용자가 N바이트의 메모리 청크를 요청하게 되면, 라이브러리는 N바이트의 빈 청크를 찾는 것이 아니라 N+헤더 크기 만큼의 메모리 청크를 탐색한다.

빈 공간 리스트 내장

링크드리스트 방식을 활용한다.

| |---|---|

3. 기본 전략

빈 공간 할당을 위한 여러가지 방식이 존재한다. 이상적인 할당기는 속도가 빠르고 단편화를 최소로 해야한다. 그러나 할당과 해제 요청은 무작위로 프로그래머에 의해 결정되기 때문에, 입력에 따라 성능이 달라게 된다. 그러니 많이 사용되는 전략들에 대해 논의만 해보겠다.

최적 적합(Best Fit)

빈 공간 리스트를 검색하여, 요청한 크기와 같거나 큰 메모리 청크를 찾고, 그 후보자 중에서 가장 작은 청크를 반환한다. 한번의 탐색으로 찾을 수 있다.

최적의 크기의 청크를 리턴하기 때문에 공간의 낭비를 줄일 수는 있겠지만, 항상 전체를 탐색하기 때문에 성능저하가 있을 수 있다.

최악 적합(Worst Fit)

최적 적합과 반대로, 가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환하고, 남은 부분은 빈 공간 리스트에 유지한다. 최적 적합에서 남기는 작은 청크들 방식과는 다르게 최대한 많은 큰 청크를 남기려고 시도한다.

마찬가지로 모든 리스트를 탐색하야하며, 대부분의 연구에서 엄청난 단편화가 발생하여 오버헤드 또한 크다.

최초 적합 (First Fit)

간단하게 요청보다 큰 첫번째 블럭을 찾아서 요청만큼 반환한다.

속도가 빠르다는 것이 장점이다. 그러나 리스트의 시작에 수많은 크기가 작은 객체가 생길 수 있다. 이를 해결하기 위해 주소-기반 정렬 방식을 통해 병합을 쉽게하여 단편화를 감소시킬 수 있다.

다음 적합 (Next Fit)

항상 리스트의 처음부터 탐색하는 것이 아니라, 이전에 찾았던 원소를 가리키는 포인터를 유지하고 그 부분부터 탐색을 진행한다. 전체 탐색 방식이 아니기 때문에 최초 적합의 성능과 비슷하다.

4. 다른 접근법

개별 리스트(Segregated Lists)

특정 응용프로그램이 자주 요청하는 청크 크기가 있다면, 그 크기의 청크를 관리하는 별도의 리스트를 유지하는 것이다. 다른 모든 요청들은 일반적인 할당기에 전달된다.

특정 크기의 요청을 위한 청크가 있기 때문에 메모리 단편화 가능성이 상당히 줄어든다. 또한 고정된 크기의 할당과 해제는 검색이 필요 없기 때문에 속도도 빠르다.

그러나 문제는, 특정 크기의 메모리 풀과 일반적인 메모리 풀에 각각 얼마만큼 메모리를 할당해야 할까?이다. Solaris 커널에서는 특수 목적 할당기인 슬랩 할당기(Slab allocator)를 통해 이런 문제를 해결했다.

커널이 부팅될 때, 커널 객체를 위한 여러 객체 캐시를 할당한다. 락, 파일 시스템 아이노드 등 자주 요청되는 자료구조를 캐시로 가진다. 객체 캐시란 지정된 크기의 객체들로 구성된 빈 공간 리스트이기 때문에 할당과 해제가 빠르다. 캐시 공간이 부족하면 추가 슬랩을 요청하고, 참조 횟수가 0이면 슬랩을 회수할 수 있다.

슬랩 할당기 방식은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별 리스트보다 우수하다.

→ 마치 스레드풀/커넥션풀과 같은 느낌?

버디 할당(Buddy Allocation)

빈 메모리를 개념적으로 $2^N$의 크기 공간으로 생각한다. 요청에 대해 적절한 공간을 찾을 때까지 분할한다. 7KB의 요청에 대해서 3번의 분할을 거쳐 8KB의 메모리 블럭이 할당된다. 당연히 33KB 같이 애매하게 큰 요청에 대해서 내부 단편화가 발생할 수 있다.

버디 할당기의 꽃은 메모리 해제 과정이다. 할당된 공간이 다음 공간의 크기와 같다면 병합이 이루어진다. 병합된 크기가 또 다음 공간과 크기가 같다면 또 병합이 이루어지는 것이 반복된다.

그런 뒤 이 공간을 해제할 때는 바로 자신과 함께 쪼개진 메모리, 즉 buddy를 찾고 사용하고 있지 않다면 바로 합병한다. 이렇게 하면 합병을 쉽게 할 수 있다.

기타 아이디어

위 방법들을 확장성에 문제가 있다. 빈 공간의 개수가 늘어나면서 리스트 검색이 느려질 수 있다.

이를 위해 BST, 스플레이 트리, 부분 정렬 트리 등의 자료구조를 활용하기도 한다.

1. 세그멘테이션: base/bound의 일반화

주소 공간의 논리적인 세그먼트마다 base/bound 레지스터가 존재한다. 즉, 코드/스택/힙 세그먼트가 있다. 이를 통해 각 세그먼트를 서로 다른 위치에 배치할 수 있고, 사용되지 않는 물리 메모리 공간 차지를 방지할 수 있다.

위 그림에서는 3개의 세그먼트가 있으니 3쌍의 베이스/바운드 레지스터 집합이 필요하다.

그림 19.1의 주소공간을 사용하여 주소 변환을 해보자. 가상 주소 100번지를 참조한다고 가정하자.

가상 주소 100번지는 코드 세그먼트에 속할때, 참조가 일어나게 되면 베이스 값(32KB)에 오프셋(100)을 더해 100+32KB인 32868이 된다. 이후 주소가 범위 내에 있는지 (100<2KB) 검사하고, 범위 내에 있을 경우 32868을 읽는다. 가상 주소 4200의 힙을 예시로 들어보자. 위와 같이 생각하면, 34KB + 4200이라고 생각하겠지만, 이는 틀렸다. 19.1에서 힙은 4KB로부터 시작하기 때문에 실제로 오프셋은 4200-4KB인 104이다. 이를 통해 주소 변환을 해보면 34KB+104 즉, 34920의 물리 주소로 변환된다.

힙의 마지막을 벗어난 잘못된 주소를 접근하게 된다면, 운영체제가 이를 감지하여 트랩을 발생시킨다. 이를 Segment fault 또는 Segment violation이라고 한다.

2. 세그먼트 종류의 파악

하드웨어 변환을 위해 세그먼트 레지스터를 사용한다. 하드웨어는 가상 주소가 어느 세그먼트를 참조하는지 그리고 그 세그먼트 안에서 오프셋은 얼마인지를 어떻게 알 수 있는가?

VAX/VAS 시스템에서는 다음과 같은 방법이 사용되었다. 세그먼트를 표시하기 위해 14비트를 사용한다. 최상위 2비트는 세그먼트의 종류를 명시하고, 나머지 12비트는 오프셋을 나타낸다.

해당 예시를 보자. 세그먼트 비트는 01 이고, 이는 힙 세그먼트를 의미한다. 오프셋은 0000 0110 1000 로 104이다. 이를 기반으로 베이스/바운드 레지스터를 통해 물리 주소로 변환할 수 있다.

세그먼트를 파악하기 위해 하드웨어적 방법을 사용할 수도 있다.

• 만약 주소가 프로그램 카운터에서 생성되었다면(명령어 반입) 코드 세그먼트를 의미한다.
• 주소가 스택 또는 베이스 포인터에 기반을 둔다면 스택 세그먼트이다.
• 그 이외에는 힙 세그먼트.

3. 스택

스택 세그먼트는 다른 세그먼트와 차이가 있는데, 확장 방향이 반대라는 것이다. 이를 위해 확장 방향을 정해주기 위한 하드웨어를 추가로 사용한다. 예를 들어 주소가 커지는 방향으로 커지면 1, 작아지는 방향으로 커지면 0이다.

가상 주소 15KB에 접근하려 한다고 가정하자. 가상 주소를 이진 형태로 바꾸면 11 1100 0000 0000이다. 또한 세그먼트의 최대 크기는 4KB라고 가정하자

1. 상위 2비트가 11이기 때문에 스택 세그먼트임을 알 수 있다.
2. 오프셋은 1100 0000 0000은 3KB이다. 올바른 음수 오프셋을 얻기 위해서는 세그먼트의 최대 크기를 빼야한다. 즉 음수 오프셋은 3KB-4KB인 -1KB이다.
3. 스택 세그먼트의 베이스인 28KB에서 오프셋 -1KB를 더해준다. 변환된 물리 주소는 27KB가 된다.

바운드 검사는 오프셋의 절댓값을 이용하여 검사한다.

4. 공유 지원

세그멘테이션 기법의 발전에 따라, 메모리 절약을 위해 주소 공간들 간에 특정 메모리 세그먼트를 공유하는 것이 유용하다는 것을 알게되었다. 특히, 코드 공유가 일반적이며, 현재까지도 많은 시스템이 사용중인 방법이다.

공유 지원을 위해, 하드웨어에 protection bit의 추가가 필요하다. 읽기 전용 비트의 경우 공간을 독립성을 유지하면서 여러 프로세스가 주소 공간의 일부를 공유할 수 있다.

5. 소단위 대 대단위 세그멘테이션

지금까지 논의한 것처럼, 코드/스택/힙 세그먼트로 나누는 방식을 대단위 세그멘테이션이라고 부른다. 주소 공간을 비교적 큰 단위로 분할하기 때문이다.

일부 초기 시스템은 주소 공간을 작은 크기의 공간으로 잘게 나눌 수 있었기 때문에, 소단위 세그멘테이션이라고 부른다. 많은 수의 세그먼트들을 관리하기 위해서 세그멘트 테이블 같은 하드웨어 자원을 이용했다.

6. 운영체제의 지원

세그먼트 방식은, 시스템이 각 주소 공간 구성 요소를 세그먼트별 물리 메모리로 재배치하기 때문에 기존에 하나의 베이스/바운드 쌍이 존재하는 방식에 비해 물리 메로리 공간을 엄청 절약할 수 있다. 즉, 스택과 힙 사이의 공간에 물리 메모리를 할당할 필요가 없어졌다는 뜻이다.

이를 위해 두가지 문제를 고민해야한다.

• 문맥 교환 시 세그먼트 레지스터의 저장과 복원
• 미사용 중인 메모리 공간의 관리

일반적으로 생길 수 있는 문제는, 물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워진다는 것이다. 이 작은 빈 공간들에는 새롭게 생겨나는 세그먼트를 할당하기에는 너무 작고, 기존 세그먼트를 확장하기에도 별로다. 이를 외부 단편화라고 한다.

왼쪽 그림에서 24KB의 새로운 세그먼트를 할당하고 싶다고 가정해보자. 미사용 공간의 크기는 24이지만, 8씩 3개로 나뉘어져 있어, 24KB가 들어갈 공간이 없다.

간단한 해결 방법은 압축이다. 세그먼트를 한쪽 방향으로 몰아넣어 여유 공간을 만든다. 세그먼트들은 연속된 공간에 넣기 위해 복사가 일어나는데, 메모리에 부하가 크고 많은 프로세서 시간을 사용하기 때문에 압축의 비용이 많이 든다.

빈 공간 리스트를 관리하는 알고리즘을 사용하는 방법이 있다. 최적/최악/최초 적합, 버디 알고리즘 등 다양한 방법이 존재한다.

효율성을 위해 하드웨어의 자원을 사용한다. 몇새의 레지스터부터 TLB, 페이지 테이블 등 점차 복잡한 하드웨어를 사용하게 된다. 제어는 프로그램이 자기자신의 메모리 이외에 다른 메모리에 접근하지 못한다는 것을 운영체제가 보장한다는 것이다. 유연성 측면에서는 프로그래머가 원하는 대로 주소공간을 사용하고, 프로그래밍하기 쉬운 시스템을 만들기 원한다.

핵심 질문: 어떻게 효율적이고 유연하게 메모리를 가상화하는가?

우리가 다룰 기법은 하드웨어-기반 주소 변환(hardware-base address translation) 또는 주소 변환(address translation)이다. 주소 변환을 통해 명령어 반입, 탑재, 저장 등의 가상 주소를 정보가 실제로 존재하는 물리 주소로 변환한다.

하드웨어가 변환을 가속화 시키는데 도움을 주긴하지만, 하드웨어만으로는 메모리 가상화를 구현할 수 없다. 정확한 변환을 위해서 운영체제가 관여해야한다. 운영체제는 메모리의 빈 공간과 사용중인 공간을 항상 알아야 하고, 메모리의 사용을 제어, 관리한다.

이 모든 작업의 목표는 다음과 같다. 프로그램이 자신의 전용 메모리를 소유하고, 그 안에 자신의 코드와 데이터가 있다는 환상을 만드는 것이다.

1. 가정

메모리 가상화를 위한 첫번째 시도는 매우 간단하다.

• 사용자의 주소 공간은 물리 메모리에 연속적으로 배치되어야 한다.
• 주소 공간은 물리 메모리 크기보다 작다.
• 각 주소 공간의 크기는 동일하다.

논의를 진행하며 각 가정들이 점차 완화되고, 실제적인 메모리 가상화을 알 수 있을 것이다.

2. 사례

주소 변환을 구현을 위해 어떤 것이 필요할까? 왜 그런 기법이 필요할까?

void func() {
    int x = 3000;
    x = x + 3; // 우리가 관심있는 코드
}

다음은 메모에서 값을 탑재하고, 3을 증가시키고 다시 메모리에 저장하는 짧은 코드이다.

128: movl 0x0(\%ebx), \%eax;    # 0+ebx를 eax에 저장 
132: addl \$0x03, \%eax;        # eax레지스터에 3을 더한다   
135: movl \%eax, 0x0(\%ebx);    # eax를 메모리에 다시 저장

x의 주소가 레지스터 ebx에 저장되어 있다고 가정하면, 그 값을 레지스터 eax에 넣고 eax 값을 3 증가시키고, 그 값을 다시 레지스터 ebx에 저장한다. 위 코드와 데이터가 프로세스 주소 공간에 어떻게 배치되어 있는지를 보자. 세 개의 명령어 코드는 주소 128에 위치하고, 변수 x의 값은 15KB(스택)에 위치한다.

명령어가 실행되면 다음과 같은 메모리 접근이 일어난다.

• 주소 128의 명령어를 반입
• 이 명령어 실행 (주소 15 KB에서 탑재)
• 주소 132의 명령어를 반입
• 이 명령어 실행 (메모리 참조 없음)
• 주소 135의 명령어를 반입
• 이 명령어 실행 (15 KB에 저장)

프로그램 관점에서 주소 공간은 0~16KB 이다. 프로그램이 생성하는 모든 메모리 참조는 이 범위 내에 있어야 한다. 메모리 가상화를 위해 운영체제는 프로세스를 물리 메모리 주소 0이 아닌 다른 곳에 위치시켜야 한다.

프로세스가 모르게 메모리를 다른 위치에 재배치시켜야 한다.

3. 동적(하드웨어-기반) 재배치

Base and bound 또는 동적 재배치(dyanmic relocation)이라고 한다.

CPU마다 2개의 레지스터가 필요하다. Base 레지스터와 Bound(limit) 레지스터. base 레지스터는 프로세스의 물리 주소를 저장하고, bound 레지스터는 주소 공간의 크기를 저장한다.

물리 주소는 다음과 같이 결정된다.

physcial address = virtual address + base

128: movl 0x0(%EBX) , % eax

위 명령어를 보면, PC는 128로 설정되고, 하드웨어가 명령어를 반입할 때, PC값을 base 레지스터(32KB)에 더해 32896의 물리 주소를 얻는다.

하드웨어는 프로세스가 참조하는 가상 주소를 통해 데이터가 실제로 존재하는 물리 주소로 변환한다. 이 주소의 재배치는 실행 시에 일어나고, 실행 후에도 주소 공간을 이동할 수 있어 동적 재배치라고도 불린다.

지금까지만 봤을 때는 bound 레지스터의 필요성을 못 느낄 수도 있다. 바운드 레지스터는 보호를 지원하기 위해 존재한다. 바운드보다 큰 가상 주소를 참조하게 되면 예외를 발생시키고 프로세스가 종료된다.

베이스와 바운드 레지스터 쌍은 CPU 칩 상에 존재하는 하드웨어 구조로 CPU당 1쌍 존재한다. 이렇게 주소 변환에 도움을 주는 프로세서의 일부를 MMU(memory managment unit)이라고 부른다.

예제

주소 공간의 크기는 4KB인 프로세스가 물리 주소 16KB에 탑재되어있다고 가정하자. 물리 주소를 얻기 위해서 단순히 베이스 주소를 더해주면 된다. 다만 가상 주소가 너무 크면 폴트가 발생한다.

4. 하드웨어 지원: 요약

5. 운영체제 이슈

base and bound 방식의 가상 메모리 구현을 위해서 운영체제가 반드시 개입해야하는 중요한 세 개의 시점이 있다.

1. 프로세스가 생성될 때 운영체제는 주소 공간이 저장될 메모리 공간을 찾아 조치를 취해야 한다.
2. 프로세스가 종료할 때 (정상적으로 종료될 때 또는 잘못된 행동을 하여 강제적으로 죽게 될) 프로세스가 사용하던 메모리를 회수하여 다른 프로세스나 운영체제가 사용할 수 있게 해야한다.
3. 운영체제는 문맥 교환이 일어날 때, 베이스-바운드 쌍을 저장하고 복원해야 한다. 이를 PCB에 저장한다.
4. 운영체제는 예외 핸들러 또는 호출될 함수를 제공해야 한다. 부팅시 특권 명령어를 통해 핸들러 설치

다음은 하드웨어/OS의 상호작용을 타임라인으로 보여준다. 메모리 변환은 운영체제의 개입 없이 하드웨어에서 처리된다. 프로세스가 잘못된 주소에 접근할 경우 운영체제가 개입한다.

C 프로그램이 실행되면, 스택과 힙이라는 두가지 유형의 메모리 공간이 할당된다.

• 스택(stack) 메모리

메모리의 할당과 반환은 컴파일러에 의해 암묵적으로 이루어져, 자동 메모리라고도 불린다. 함수 안에서 변수를 선언하게 되면, 컴파일러가 함수가 호출될 때 스택에 공간을 확보한다. 함수를 리턴하게 되면, 메모리를 반환하게 되기 때문에 더이상 변수를 사용할 수 없게 된다.

void func() {
    int x;
}

• 힙(heap) 메모리

오랫동안 유지되어야 하는 변수를 위해서는 힙(heap) 메모리가 필요하다. 메모리의 할당과 반환은 프로그래머에 의해 명시적으로 처리된다.

void func() {
    int *x = (int *) malloc(sizeof(int));
    ...
}

위는 코드는 정수에 대한 포인터를 heap에 할당하는 예시이다. 이 경우는 스택과 힙 할당이 모두 발생한다.

2. malloc() 함수

힙에 요청할 공간의 크기를 넘겨주면, 성공시에는 새로 할당된 공간에 대한 포인터를 반환하고 실패시에는 NULL을 반환한다. 함수를 사용하기 위해 stdlib.h를 불러와야 한다.

malloc()의 인자는 size_t 타입의 변수이고 이 변수는 필요 공간의 크기를 바이트 단위로 표시한 것이다. 숫자를 직접 입력하지는 않고, sizeof() 연산자를 이용한다.

malloc()은 void 타입에 대한 포인터를 반환하기 때문에, 해당 주소 공간을 어떤 타입의 자료를 저장할지는 프로그래머가 결정하게 된다. 전형적인 C의 방식. 타입 변환을 이용하여 공간 활용을 결정한다.

3. free() 함수

할당된 메모리를 언제, 어떻게 해제하고 해제 여부를 확인하는 것은 어렵다. 더 이상 사용되지 않는 힙 메모리를 해제하기 위해 프로그래머는 free()를 호출한다. malloc()에 의해 반환된 포인터를 인자로 가진다.

int *x = (int *) malloc(sizeof(int));
...
free(x);

할당된 영역의 크기는 전달되지 않고, 라이브러리가 알고 있다. 어떻게?

*malloc()이나 calloc() 함수를 호출하여 동적 메모리를 할당하면, 실제로 요청된 크기보다 약간 더 많은 메모리가 할당된다. 추가로 할당된 영역에는 메타데이터 정보가 저장되며, 할당된 메모리 블록의 크기, 사용 여부 등의 정보가 포함된다. 이러한 메타데이터는 메모리 블록이 해제되어야 할 때 free() 함수가 몇 바이트의 메모리를 해제해야 하는지 알 수 있게 해준다. 일반적으로 이 메타데이터는 할당된 메모리 블록 바로 앞에 위치하게 된다.*

4. 흔한 오류

메모리 할당 잊어버리기

char *src = "hello";
char *dst;
strcpy(dst, src); // *dst는 메모리에 할당되지 않음. segmentation fault 오류 발생

프로그램이 자신이 접근 권한이 없는 메모리 영역에 접근하려고 시도할 때 Segmentation Fault 오류가 발생한다. 자세한 내용은 OSTEP 16 Segmentation에서 알아보자.

메모리를 부족하게 할당받기

char *src = "hello";
char *dst = malloc(strlen(src)); // 메모리를 부족하게 할당
strcpy(dst, src);

buffer overflow 오류라고 불린다. 경우에 따라 오류가 나지 않을 수는 있지만, 프로그램이 한 번 올바르게 실행된다고 하더라도, 올바른 프로그램이라는 것은 아니다.

char *src = "hello";
char *dst = malloc(strlen(src) + 1);
if (dst != NULL) {
    strcpy(dst, src);
}

위와 같은 코드가 올바른 코드이다.

할당받은 메모리 초기화하지 않기

새로 할당받은 데이터 타입에 값을 넣지 않는다면, 초기화되지 않은 읽기(uninitialized read) 즉 힙으로부터 알 수 없는 값을 읽는 일이 생긴다.

메모리 해제하지 않기

메모리 누수(memory leak). 장시간 실행되는 응용 프로그램이나 운영체제 자체와 같은 시스템 프로그램에서 큰 문제이다. 메모리가 천천히 누수되면서 결국 메모리 부족으로 시스템을 재시작해야한다.

Garbage Collector가 있더라도 메모리 청크에 대한 참조가 있다면, 그 청크를 해제하지 않을 것이다. 이런 현대적인 언어에서도 memory leak은 문제가 된다.

메모리 사용이 끝나기 전에 메모리 해제하기

dangling pointer. 해제된 메모리 포인터를 사용하면 프로그램 크래시가 발생하거나 유효 메모리 영역을 덮어쓸 수 있다. free()를 호출하고 다른 용도롤 malloc()을 호출하면 잘못 해제된 메로리를 재사용할 수 있다.

반복적으로 메모리 해제하기

double free. 해제된 메모리를 관리하게 되는 링크드리스크가 있는데, free()가 두 번 수행되면 같은 메모리가 두번 들어가게 된다. 그러면 다른 변수가 같은 메모리공간을 사용하게 될 수 있다.

free() 잘못 호출하기

malloc() 받은 포인터만 free() 해야한다. 유효하지 않은 해제(invalid frees)는 매우 위험

5. 운영체제의 지원

malloc(), free()를 논의하면서 시스템 콜은 언급하지 않았는데, 두 함수는 라이브러리의 함수일 뿐이다.

malloc 라이브러리는 가상 주소 공간을 관리하지만, 라이브러리 자체는 시스템에게 더 많은 메모리를 요구하고 반환하는 시스템 콜(brk, sbrk)을 기반으로 구축된다.

brk 시스템 콜은 프로그램의 break 위치를 변경하는데 사용된다. break는 힙의 마지막 위치를 나타낸다. brk 는 새로운 break 주소를 나타내는 한 개의 인자를 받는데, 기존 break보다 작다면 힙의 크기를 줄이고 크다면 힙의 크기를 증가시킨다. 직접 사용하려고 한다면, 메모리 할당 라이브러리와 충돌이 발생할 수 있기 때문에 malloc()과 free()를 사용하자.

mmap() 함수를 통해 운영체제에게 메모리를 얻는 방법도 있다. 특정 파일과 연결되지 않고 스왑 영역(swap space)에 연결된 annnoymous 메모리 영역을 만든다. 이 메모리는 힙처럼 취급되고 관리된다.

6. 기타 함수들

calloc()

메모리를 0으로 채워서 반환

realloc()

이미 할당된 공간에 대해 추가 공간이 필요할 때 사용. 더 큰 새로운 영역을 확보하고 옛 영역의 정보를 복사 후 새 영역의 포인터를 리턴

메모리 관점에서 초기 컴퓨터는 많은 개념을 사용자에게 제공하지 않았다.

물리 메모리에 하나의 실행 중인 프로그램(프로세스)이 존재하였고. 쓰고 남은 메모리를 사용했다. 가상화는 거의 존재하지 않았다.

2. 멀티 프로그래밍과 시분할

멀티프로그래밍

여러 프로세스가 준비상태에 있고 운영체제는 이를 전환하면서 실행했다. 예를 들어 한 프로세스가 입출력을 실행하면 CPU는 다른 프로세스로 전환했다. → CPU의 이용률 증가, 효율성 개선

시분할

시간이 오래 걸리는 작업에 대해 일괄처리방식 컴퓨팅에 한계를 느끼고, 실행 중인 작업으로부터 즉시 응답을 얻는 대화식 이용의 개념이 중요해졌다.

시분할을 구현하는 한가지 방법은 하나의 프로세스를 짧은 시간동안 실행시키는 것이다. 이를 위해 프로세스의 모든 상태 정보를 메모리와 디스크 사이에서 전환했다. 이는 메모리가 커질수록 속도가 매우 느려진다. 특히 메모리 내용 전체를 디스크에 저장하는 것이 엄청 느리다.

우리가 할 일은 프로세스를 메모리에 유지하면서, 운영체제가 시분할을 효율적으로 구현할 수 있게하는 것이다.

그림을 보면 세 개의 프로세스(A, B, C)가 메모리의 작은 부분을 나누어 할당 받았다. 이 경우에는 한 프로세스가 다른 프로세스의 메모리를 침법하지 못하도록 하기 위한 보호(protection)가 중요한 문제가 된다.

3. 주소 공간

이런 위험을 염두에 두고 만들어진 개념이 주소 공간(Address Space)이다.

주소 공간은 프로세스의 모든 메모리 상태를 가지고 있다.

• 코드(code, 명령어)
• 스택(stack) - 함수 호출에 대한 현재 위치, 지역 변수, 함수 인자, 반환 값을 저장한다.
• 힙(heap): 동적으로 할당되는 메모리

스택과 힙 영역은 확장이 가능해야한다. 이에 주소 공간의 양 끝단에 위치하고, 확장 방향이 서로 반대이다. 그러나 주소 공간에 여러 쓰레드가 공존한다면 이런 식으로 나누면 안된다.

주소 공간은 운영체제가 실행 중인 프로그램에게 제공하는 개념(abstraction)을 설명한다. 실제로 016KB의 물리 주소에 프로그램이 존재하는게 아니다. 실제로는 임의의 물리 주소에 탑재된다. <그림 16.2>를 보면 각 프로세스의 주소 공간은 016KB겠지만 실제 저장되는 물리 주소는 각각 다르다.

운영체제가 이런 일을 할 때, 운영체제가 메모리를 가상화(virtualizing memory)한다고 말한다. 실행 중인 프로그램들은 자신이 특정한 주소의 메모리에 주소 공간을 가지고 있다고 생각하게 된다.

그러나 실제로 프로세스들은 주소 0으로 시작하는 가상 주소 공간을 가지고, 운영체제는 하드웨어의 지원을 통해 실제로 메모리가 저장된 물리 주소를 읽도록 보장한다. 이것이 메모리 가상화이다.

*핵심 질문: 메모리를 어떻게 가상화하는가? 운영체제는 물리 메모리를 공유하는 다수의 프로세스에게 어떻게 프로세스 전용의 커다란 주소 공간이라는 개념을 제공할 수 있는가?*

4. 목표

투명성 (transparency)

운영체제는 실행 중인 프로그램이 가상 메모리의 존재를 인식하지 못하도록 해야한다. 프로그램은 메모리 가상화의 여부를 모르고, 각자 자신만의 전용 메모리를 소유한 것처럼 행동해야한다.

효율성 (efficiency)

운영체제는 가상화가 시간과 공간 측면에서 효율적이도록 해야한다. 이를 위해 TLB 등의 하드웨어 기능을 통해 시간-효율적인 가상화를 구현한다.

보호 (protection)

운영체제는 프로세스를 다른 프로세스로부터 보호해야 하고, 운영체제 자신도 프로세스로부터 보호해야한다. 자신의 주소 공간 밖의 어느 것도 접근할 수 있어서는 안된다. 프로세스들을 서로 고립(isolate)시켜야 한다.

다음 장부터는, 하드웨어 지원을 포함하여 메모리를 가상화하기 위해 필요한 기본적인 기법을 집중적으로 탐구한다. 또한 빈 공간을 관리하는 방법과 공간이 부족할 때 어떤 페이지를 내보낼 것인가 같은 운영체제 정책들에 대해서도 학습한다.

현재는 여러개의 CPU 코어가 하나의 칩에 내장된 멀티코어 프로세서가 어디에서나 사용된다. 그러나 기존의 전통적인 응용 프로그램(c언어와 같은)은 하나의 CPU만 사용한다. 이를 해결하기 위해 응용 프로그램을 병렬(parrallel)로 실행되도록 다시 작성해야 되며, 보통 쓰레드를 이용한다.

당연하게도 멀티프로세서의 스케줄링 문제가 대두되었다. 여러 CPU에서 작업을 어떻게 스케줄 해야 할까?

1. 배경: 멀티프로세서 구조

멀티프로세서 스케줄링에 대한 새로운 문제점을 이해하기 위해서는 단일 CPU, 멀티 CPU 하드웨어의 근본적인 차이에 대한 이해가 필요하다.

다수의 프로세서 간의 데이터 공유, 하드웨어 캐시 사용 방식에서 차이

단일 CPU 시스템에서는 하드웨어 캐시 계층이 존재한다. 메인 메모리에서 자주 사용되는 작업의 저장본을 캐시라는 작고 빠른 메모리에 저장하여 프로그램의 빠른 실행을 돕는다. 또한 지역성이라는 개념에 기반한다. 데이터가 한번 접근 되면 가까운 미래에 다시 접근되기 쉽다는 시간 지역성과 주소 x에 데이터에 접근했다면 그 주변의 데이터가 접근되기 쉽다는 공간 지역성 개념을 이용한다.

그렇다면 하나의 시스템에 여러 멀티 프로세서가 존재하고 하나의 공유 메모리가 있다면 어떨까?

만약 CPU1가 주소 A를(D값) 읽는다고 가정하자. 데이터가 캐시에 존재하지 않기 때문에 시스템은 메모리에서 데이터를 불러오고 값 D를 얻는다. 이후 CPU1에서 D의 값을 D’로 변경한다. 메모리에 데이터를 쓰는 것은 시간이 오래 걸리기 때문에 우선 캐시에서만 값을 D’으로 변경 후 메모리 쓰기 작업은 미룬다. 이때 운영체제가 CPU 2로 이동하기로 결정하고, CPU2에서 주소 A의 값을 읽게된다면 어떻게 될까? 당연히 메모리에 있는 변경 전 값인 D를 읽게된다.

이를 캐시 일관성 문제(chace coherence)라고 부른다. 기본적인 해결책은 하드웨어에 의해 제공된다. 하드웨어는 메모리 주소를 계속 감시하고, 관리하는 방식이 있다. 특히, 여러개의 프로세스가 하나의 메모리에 갱신할 때에는 항상 공유되도록 한다.

버스 기반 시스템에서는 버스 스누핑이라는 기법을 사용하여 캐시는 자신과 메모리를 연결하는 버스를 계속 모니터링한다. 캐시에 데이터의 변경이 있을 때, 무효화, 갱신, 나중 쓰기 등을 고려해야해서 캐시 일관성 문제가 점점 복잡해진다.

2. 동기화를 잊지 마시오

일관성 유지에 대한 모든 일을 캐시가 담당한다면, 프로그램이나 운영체제는 공유 데이터에 접근할 때 걱정할 필요가 없을까? 당연히 걱정해야한다.

CPU들이 동일한 데이터 또는 구조체에 접근할 때, 올바른 연산 결과의 보장을 위해 상호 배제를 보장하는 동기화 기법을 사용한다. 예를 들어, 여러 CPU가 동시에 접근하는 공유 큐가 있다고 가정하자. 캐시의 일관성을 보장하는 프로토콜이 있다 하더라도 항목의 추가나 삭제와 같은 구조체의 원자적 갱신을 위해서는 락이 필요하다.

만약 두개의 CPU의 쓰레드가 위 작업을 수행한다고 가정하자. 두 작업이 원자적으로 실행된다면 각 쓰레드는 리스트의 head를 한번씩 제거해야할 것이다. 그러나 한 스레드에서 head가 다음 포인터로 이동(10행)하기 전(에 쓰레드 1,2 둘다 같은 head를 읽는다면(7행) 삭제는 한번만 발생할 것이다.

이러한 문제는 락(lock)을 통해 해결될 수 있기는 하지만, CPU 개수가 많아질 수록 연산이 느려진다.

3. 마지막 문제점: 캐시 친화성

CPU에서 실행되는 프로세스는 CPU 캐시와 TLB에 상당한 양의 상태 정보를 저장할 것이다. 그런데 프로세스가 매번 다른 CPU에서 실행된다면, 이런 정보들을 CPU를 옮겨갈 때 마다 새롭게 탑재해야 하기 때문에 프로세스의 성능이 오히려 나빠질 수 있다.

캐시 친화성을 고려하기 위해서는 가능한 한 프로세스를 동일한 CPU에서 실행할 수 있도록 해야할 것이다.

CPU 캐시의 경우 컴퓨터구조, TLB는 이후 VM 부분에서 자세히 배울 수 있다.

4. 단일 큐 스케줄링

멀티프로세서 시스템의 스케줄러에 대해 알아보자. 단일 프로세서에서 하던 것 처럼, 그대로 적용할 수 있다. 이러한 방식을 단일 큐 멀티프로세서 스케줄링(single queue multiprocessor scheduling, SQMS) 이라 부른다.

SQMS의 ****장점은 단순함이다. 만약 CPU가 2개라면, 2개의 실행할 작업을 선택하면 된다.

그러나 SQMS에는 명백한 단점이 있다.

1. 확장성 결여 - SQMS에서는 락을 기반으로 다수의 CPU에 대한 스케줄링을 제어하는데, CPU가 많아질 수록 성능이 크게 저하된다.
2. 캐시 친화성 - 실행할 5개의 작업이 있고 (A, B, C, D, E), 4개의 CPU가 있을 때, 스케줄링 결과는 다음과 같을 것이다.

같은 작업이 여러 CPU에서 실행되니 캐시 친화성 관점에서 잘못된 선택을 하는 것이다.

그래서 대부분의 SQMS 스케줄러는 가능한 한 프로세스가 동일한 CPU에서 재실행될 수 있도록 시도한다.

A~B 작업은 각각 자신의 CPU에서 실행되고, 오직 E만이 프로세서를 이동하며 실행된다. 이런 방식으로 대부분의 작업의 캐시 친화성을 보존하고 있다. 다음에는 다른 작업을 이동시키는 방식을 통해 친화성에 대한 형편성도 추구할 수 있겠지만 그 경우 구현이 복잡해질 수 있다.

5. 멀티 큐 스케줄링

단일 큐 방식의 문제 때문에, 일부 시스템은 CPU마다 큐를 하나씩 둔다. 이 방식을 멀티 큐 멀티프로세서 스케줄링(multi-queue multiprocessor scheduling, MQMS)이라고 부른다.

MQMS 방식은 여러 개의 스케줄링 큐로 구성되고, 각 큐는 RR과 같은 특정 스케줄링 규칙을 따른다. 작업이 시스템에 들어가면 하나의 스케줄링 큐에 배치된다.

예를 들어, 현재 시스템에 CPU 0, 1과 작업 A, B, C, D가 있다고 가정하자. 각각의 스케줄링 큐가 내린 작업 배치가 다음과 같다고 해보자

만약 각 큐의 스케줄링 정책이 RR이라면 다음과 같이 스케줄될 것이다.

MQMS가 SQMS에 비해 가지는 명확한 이점은 확장성이 좋다는 것이다. CPU가 많아질 수록 큐의 개수도 증가하기 때문에 락과 캐시 친화성에 대해 고민할 필요가 없다. MQMS에서 작업은 계속 같은 CPU에서 실행된다.

그렇다고 문제가 없는 것은 아닌다. 멀티 큐의 근본적인 문제는 워크로드의 불균형(load imbalance)이다. 위 예시와 같이 2개의 CPU, 4개의 작업이 존재한다고 가정했을 때, C가 종료된다면 어떨까?

RR 스케줄링 정책을 사용할 경우 스케줄 결과는 다음과 같다. A가 B,D보다 2배의 CPU를 차지하게 되고, 이는 바람직한 스케줄링이라고 할 수 없다. 여기에 A까지 종료된다면, CPU 0은 유후상태가 될 것이다.

이런 문제에 대한 당연한 해결방안은 이주(migration)이다. 작업을 다른 CPU로 이동시켜 워크로드의 균형을 달성한다.

다음과 같은 작업 상황에서는 B 또는 D를 CPU 0 으로 옮기면 된다.

이런 상황에서는 한 번의 이주만으로는 문제가 해결되지 않고, 작업들을 지속적으로 이주시켜 주어야 한다. 이주의 필요 여부를 결정하기 위해, 작업이 적은 큐가 다른 큐를 훔쳐본다. 더 많은 작업을 가지고 있다면 하나 이상의 작어을 가져오게 된다. 물론 큐를 너무 자주 검사하게 되면 이에따른 오버헤드로 인해 확장성에 문제가 생긴다. 적절한 주기를 찾는게 중요하겠지만 마법의 영역이다.

6. Linux 멀티프로세서 스케줄링

Linux에서 멀티프로세서 스케줄링은 크게 세가지 방법이 존재한다. O(1) 스케줄러, CFS 스케줄러, BFS 스케줄러.

• O(1) 스케줄러 - 멀티 큐 방식, 우선순위를 기반으로 우선순위를 시간에 따라 변경하며 우선순위가 높은 작업을 선택한다. (MLFQ와 유사), 특히 상호작용을 우선시한다.
• CFS 스케줄러 - 멀티 큐, 결정론적/비례배분 방식이다.
• BFS 스케줄러 - 단일 큐, 비례 배분 방식이다. EEVDF라는 알고리즘을 기반에 둔다.

7. 요약

멀티프로세서 스케줄링에는 크게 단일 큐 방식과 멀티 큐 방식이 있다.

• 단일 큐 방식: 구현이 간단하고 워크로드의 균형을 잘 맞추는 특징이 있다. 하지만, 많은 프로세서에 대한 확장성과 캐시 친화성이 좋지 않다.
• 멀티 큐 방식: 확장성이 좋고 캐시 친화성을 잘 다루는 반면, 워크로드의 불균형에 취약하고 구현이 복잡하다.

운영체제를 공부하다보니 리눅스는 CFS 스케줄링 방식을 사용한다는 것을 알게 되었다. 이에 조금더 자세히 찾아보게 되었고, linux의 스케줄링에 대해 공부했다. 공부해보니 무조건 CFS를 사용하는건 아니고, 작업의 특성에 따라 달라진다는 것을 알게 되었다. 공부하다가 정리한 내용이라 결론이 궁금한 사람은 마무리 부분만 읽어도 될거 같다.

Scheduling class

리눅스 커널 v2.6.23 부터 scheduling class 라는 것이 도입되었다. 이를 통해 다양한 상황에 맞게 스케줄링 정책을 모듈화할 수 있도록 했다. → 스케줄러 코드의 확장성을 향상

리눅스에서는 스케줄러를 2가지 파트로 나눈다.

코어 스케줄링 코드에서 specific scheduling class 를 호출하는 식으로 스케줄링이 수행된다. specific part에서는 struct sched_class 구조체를 작성해서 코어에 등록해야한다.

• struct sched_class 구조체

struct sched_class {
    ....

    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
    ....

    void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
    struct task_struct *(*pick_next_task)(struct rq *rq);
    ....
};

• enqueue_task: 프로세스(task_struct)를 현재 스케줄러가 관리하는 런큐(rq)에 삽입
• dnqueue_task: 프로세스(task_struct)를 현재 스케줄러가 관리하는 런큐(rq)에서 제거
• check_preempt_curr : 프로세스가 생성되거나 wakeup 했을 때, preemption 가능 여부를 체크한다. 가능할 경우 TIF_NEED_RESCHED 가 flag로 설정되어 있다.
• pick_next_task : 런큐(rq)에서 실행하기 적합한 프로세스(task_struct)를 선택한다. 스케줄러에서 가장 핵심적인 부분

리눅스 커널에서는 어떤 스케줄링 클래스가 존재할까?

v6.5 기준으로 5개가 존재한다.

// kernel/sched/sched.h - v6.5
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

모든 프로세스는 하나의 scheduling strategy에 대응되고, 각 scheduling strategy는 하나의 scheduling class에 대응된다. 스케줄러는 위에서 부터 아래로 내려가며 대응되는 스케줄링이 있는지 확인한다.

Scheduling policies

스케줄링 전략을 이야기하기 위해서는 스케줄링 정책도 알아야될 것 같다. 리눅스에서는 6개의 정책이 존재하고, 크게 두 가지로 분류할 수 있다.

priority

리눅스에서 우선순위는 1139 를 가지고 있다. 1 ~ 99 는 static priority, 100139는 dynamic priority로 나눠진다.

• static priority: 스케줄러가 우선순위를 변경할 수 없고, 사용자가 nice() 시스템 콜을 통해서 우선 순위를 조절할 수 있다. SCHED_FIFO, SCHED_RR 타입에 해당 우선순위를 사용한다.
• dynamic priority: 스케줄러가 IO-bound 작업에 대한 보상으 우선순위를 높이거나, CPU-bound 작업에 대해 우선순위를 낮출 수 있다. 이렇게 변경된 우선순위를 작업의 dynamic priority라고 부른다.

CFS

Completely Fair Scheduler의 약자로, time slice에 대한 개념이 없이, ‘CPU 사용 시간 비율’ 개념을 사용한다. 만약 우선순위가 같은 두 개의 프로세스가 존재한다면, 각각 50%씩 CPU 사용 시간을 할당할 것이다.

그런데, 우선 순위가 같더라도 가중치를 다르게 가져가고 싶을 때는 어떻게 할까?

• weight 개념을 도입하여 weight가 클수록 더 많은 CPU 타임을 받게할 수 있다
• [-20, 19]의 범위를 가지는nice 개념을 도입하여 nice 값이 작을수록 더 큰 우선순위를 가진다.

이 내용들은 SCHED_OTHER, SCHED_BATCH 스케줄링 정책에 부합한다. 즉, nice와 weight 개념은 time-sharing 정책에서 사용된다고 할 수 있다.

Scheduling period

CFS는 CPU 사용시간 비율을 할당하기 위해, 스케줄링 주기를 두어 그 주기마다 프로세스들에게 CPU 사용시간을 할당할 것이다. 그런데, 만약 프로세스의 수가 많아진다면, 프로세스가 할당받는 time slice가 작아지고 context switch로 인한 오버헤드도 커질 것이다.

이에 CFS에서는 0.75ms 최소 time slice를 보장해준다.

virtual time

CFS에서는 각 작업의 실행시간을 누적해서 가지고 있다. CFS에서는 이 값을 통해서 각 작업에게 공정한 시간을 할당하게 된다.

virtual time이라는 개념을 통해 스케줄링이 이루어지는데 다음과 같은 식을 통해 virtual time이 결정된다.

Why does CFS user rb-tree?

min-heap 방식과 rb-tree를 비교하며 알아보자

1. 메모리 연속성

   비교하기 앞서 array와 linkedlist를 비교해보자. array의 경우 메모리에 연속적으로 올라가야하기 때문에, array의 크기가 커질수록 메모리에 적재하는게 쉽지 않을 것이다. linkedlist의 경우 비 연속적인 메모리 기반이기 때문에 부담이 덜할 것이다.

   리눅스에서의 min-heap은 배열로 구현되어 있다. 스케줄링이라는 것은 엄청난 양의 프로세스와 스레드를 관리해야할 것이다. 이 측면에서 보면 rb-tree가 더 유리할 것이라고 생각할 수 있다.

2. 성능

   min-heap을 사용할 경우 최고 우선순위를 가진 프로세스를 찾는 것은 $O(1)$의 시간 복잡도를 가져 $O(log(n))$의 시간 복잡도를 가진 rb-tree보다 빠르지만.

   업데이트, 삭제 연산까지 고려한다면 min-heap은 $O(n)$, rb-tree는 $O(log(n))$을 가지기 때문에 rb-tree가 더 효율적이라고 할 수 있다. 프로세스가 blocked 상태로 전환되기 위해 ruqueue에서 삭제 작업이 이루어진다는 점을 보면, 삭제 작업이 생각보다 많이 이루어진다는 점에서 미루어보아 rb-tree가 사용되는 이유을 알 수 있을거 같다.

run queue

CPU마다 런큐를 가지고 있고, 각각의 스케줄링 클래스 또한 자신의 런큐를 가지고 있다. 예를들어 dl_sched_class는 dl_rq를 가지고, rt_sched_class는 rt_rq를, fair_sched_class는 cfs_rq를 가질 것이다.

CFS는 virtual time을 기준으로 red-black tree를 정렬한다. 즉, 런큐(rb-tree)에 삽입되어 있는 실행가능한 작업들은 모두 virtual 타임을 기반으로 정렬되어있다.

마무리

지금까지 정리한 내용을 통해, 내가 궁금했던 부분을 해소해보자.

Linux 운영체제는 우선순위가 높은 sched_class 부터 낮은 클래스를 돌면서 스케줄링 가능한 프로세스가 있을 경우 그 프로세스를 선택한다.

// 위에서 부터 내려갈 수록 우선순위가 내려간다.(위에서 아래로 탐색)
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

// kernel/sched/core.c - v6.5
static inline struct task_struct *pick_task(struct rq *rq)
{
    const struct sched_class *class;
    struct task_struct *p;

    // 각각의 sched_class를 돌면서 스케줄링 가능한 작업이 있을 경우 선택
    for_each_class(class) {
        p = class->pick_task(rq);
        if (p)
            return p;
    }

    BUG(); /* The idle class should always have a runnable task. */
}

각각의 sched_class는 스케줄링을 위한 rq를 가질 것이고 rq에 스케줄 가능한 작업이 있을 경우 해당 작업이 선택될 것이다.

만약 hard realtime 작업의 경우 dl_sched_class의 rq에 들어있을 것이기 때문에 다른 작업들보다 더 빠르게 수행될 것이다. 추가로 DEADLINE 정책에서는 rq는 deadline을 기반으로 rb-tree에 정렬되어있고 EDF 스케줄링 방식을 사용할 것이다.

soft realtime 작업은 rt_sched_class의 rq 에 있을 것이므로, hard realtime 작업이 rq에 없다면 선택될 것이다. 내부적으로는 RR, FIFO 스케줄링은 사용한다.

마지막으로 normal task는 fair_sched_class의 rq에서 관리되며, 스케줄링 알고리즘은 CFS, rq는 vruntime 기반의 rb-tree 자료구조 형태로 이루어져 있다고 할 수 있겠다.

결국 알고 싶던 내용은 위 세문장이 전부인거 같은데, 너무 힘들게 돌아왔다 ㅋ쿠ㅜ 개인적으로 schduling class, run queue 개념이 이해에 도움이 된 것 같다.

참고

[리눅스 커널] Scheduler - Basic

비례 배분 스케줄리의 예시인 추첨 스케줄링(Lottery Scheduling)을 통해 알아보자

핵심 질문: 어떻게 CPU를 정해진 비율로 배분할 수 있는가?

1. 기본 개념: 추천권이 당신의 몫을 나타낸다.

추첨권(티켓) 이라는 기본적인 개념이 사용된다. A가 75개 B가 25개의 티켓을 가지고 있다고 가정하면, A에게 75%, B에게 25%의 CPU를 할당하는 것이 목적이다.

이 경우 추첨권은 099의 숫자를 가진다. A는 074, B는 75~99 이다. 추첨 값에 따라 실행할 프로세스가 결정된다.

추첨 형식이기 때문에 원하는 비율을 정확히 보장하지는 않지만, 작업이 길어질수록 원하는 비율에 수렴하게 된다.

2. 추첨 기법

추첨권 화폐(ticket currency)

사용자는 자신만의 화폐가치로 추첨권을 자유롭게 할당하고, 시스템은 자동적으로 화폐 가치를 변환한다.

A, B가 각각 100장의 추첨권을 받았다고 가정 했을 때, A는 작업 A1, A2에게 500장씩 추첨권을 할당하고, B는 작업 B1에게 10장의 추첨권을 할당할 있다. 이때, 시스템에서는 A1, A2는 각각 50장, B1은 100장의 추첨권이라는 전역 추첨권으로 화페가치를 변환한다.

추첨권 양도

양도를 통해 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다. 주로 클라이언트/서버 환경에서 유용하다. 클라이언트가 서버에게 측정 작업을 요청했을 때, 추첨권을 잠시 넘겨주는 방식이다.

추첨권 팽창

프로세스가 일시적으로 자신의 추첨권 개수를 늘리거나 줄일 수 있다. 한 프로세스가 과하게 추첨권을 팽창할 수 있으니, 프로세스들이 서로 신뢰할 때 유용하다. 이 경우, 프로세스가 CPU 시간을 더 많이 필요하다면 다른 프로세스와의 통신 없이 혼자서 추첨권 개수를 늘릴 수 있다,

3. 구현

추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 것이다.

A는 099, B는 100149, C는 150~399의 티켓을 할당 받는다.. winner에 난수 300이 할당되었다고 하자. 리스트를 앞에서부터 순회하면서 counter의 값을 증가시킨다. A에서는 100, B에서는 150이 된다. C에서는 400이 된다. C에서 counter 값이 난수 300보다 커지므로 C가 당첨자가 된다.

리스트를 내림차순으로 정렬한다면, 검색 횟수를 최적화할 수 있을 것이다.

4. 예제

같은 개수의 티켓을 보유하고 있고, 동일한 실행 시간을 가지는 프로세스 두 개의 수행 시간을 살펴보자. 두 프로세스를 거의 동시에 종료시키는 것이 목표다.

불공정 지표 (U)

불공정 지표는 첫 번째 작업이 종료된 시간을 두 번째 작업이 종료된 시간으로 나눈 값이다. 1에 가까울수록 종료된 시간이 비슷한 공정 스케줄러라고 할 수 있다.

작업 시간이 짧을 때는 스케줄링의 무작위성 때문에 끝난 시간에 차이가 있지만, 작업의 길이가 길어질수록 추첨 스케줄러의 목적에 가까워진다.

5. 추첨권 배분 방식

추첨권을 작업에게 얼만큼씩 분배해야할까? 추첨권 할당 방식에 따라 시스템의 동작이 크게 달라지기 때문에 어려운 문제이다. 각 사용자가 작업에 대해 아주 잘 안다고 가정하면 추첨권 배분을 사용자에게 위임할 수는 있지만, 근본적인 해결책은 아니다.

6. 왜 결정론적 방법을 사용하지 않는가

무작위성 기반의 스케줄링은 정확한 비율을 보장할 수 없는데, 작업 기간이 짧을 수록 더욱 그렇다. 이에 결정론적 공정 배분 스케줄러인 보폭 스케줄러(stride scheduling)이 고안되었다.

작업 A, B, C가 각각 100, 50, 250의 추첨권을 가지고 있다고 가정하면, 각각의 보폭(stride)는 임의의 큰 값을 추첨권 수를 나눈 값을 가진다(100, 200, 40). 임의의 순서대로 수행될 때마다 각각의 보폭으로 나아간다. 그 이후 가장 덜 나아간 작업중에 선택하는 과정을 반복한다.

분배 횟수를 보면, 추첨권의 개수와 정확히 비례한다. 보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 CPU를 배분한다. 그렇다면 추첨 스케줄링을 쓸 이유가 없지 않은가?

보폭 스케줄링 과정 중간에 새로운 작업이 들어왔다고 가정하면, pass값을 몇으로 설정해야 할까? 0이라면 해당 작업이 CPU를 독점하게 될것이다. 그러나 추첨 스케줄링에서는 프로세스의 상태(pass 값)이 필요없다. 이처럼 새로운 프로세스 추가에 유리하다.

7. 요약

추첨 스케줄러와 보폭 스케줄러 모두 CPU 스케줄러로서 널리 사용되지는 않는다. 추첨권 할당 문제도 있고 입출력과 맞물렸을 때, 제대로 동작하지 않는다.

비례 배분 스케줄러는 추첨권 할당량을 비교적 정확하게 결정할 수 있는 환경에서 유용하다. 예를 들어 가상화 데이터 센터에서 Window 가상머신에 CPU 사이클의 25%를 할당하고 나머지는 Linux 시스템에 할당하고 싶을 대 효과적이다.