🚪 들어가며

멀티코어(multicore) 프로세서: 여러 개의 CPU 코어가 하나의 칩에 내장된 프로세서

다중 CPU 시대가 오면서 발생한 문제
➡️ 전통적인 응용 프로그램은 오직 하나의 CPU만 사용
➡️ 문제 해결을 위해 응용 프로그램을 병렬(parallel)로 실행되도록 재작성

이를 위해 보통 쓰레드를 이용함.

멀티 쓰레드 응용 프로그램 ➡️ 작업을 여러 CPU에 할당
➡️ 더 많은 수의 CPU = 더 빠른 실행

따라서 멀티프로세서 스케줄링 방법에 대하여 고민해보아야 함.

1️⃣ 배경: 멀티프로세서 구조

캐시 사용 방식의 차이(단일 CPU 하드웨어 vs. 멀티 CPU 하드웨어)

캐시: 메인 메모리에서 자주 사용되는 데이터의 복사본을 저장하는 작고 빠른 메모리

단일 CPU 시스템에는 하드웨어 캐시 계층이 존재 ➡️ 프로그램의 빠른 실행을 위해

예를 들어, load 명령어를 수행하는 프로그램과 하나의 CPU만 있는 간단한 시스템을 가정
CPU는 작은 크기의 캐시(64KB)와 큰 메인 메모리를 갖고 있음. 다음을 통해 캐시의 동작을 살펴보자.

1. 프로그램이 처음 load 명령어를 실행

2. 데이터가 메인 메모리에 존재하므로 데이터를 가져오는 데 긴 시간 소모(약 수십/수백 나노 초)

3. 데이터가 다시 사용될 것으로 예상되는 경우 프로세스는 해당 데이터의 복사본을 CPU 캐시에 저장

4. 프로그램이 다시 같은 데이터를 가져오려고 시도

5. CPU는 해당 데이터가 캐시에 존재하는지 검사

6. 데이터가 캐시에 존재하므로 훨씬 빨리 접근(수 나노 초)되고 프로그램은 빨리 실행

캐시는 지역성(locality)에 기반

시간 지역성(temporal locality): 데이터가 한 번 접근되면 가까운 미래에 다시 접근되기 쉽다는 것
예시) 반복문 안에 있는 변수

공간 지역성(spatial locality): 프로그램이 주소 x의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다는 것
예시) 배열에 차례대로 접근

하드웨어 시스템은 캐시에 어떤 데이터를 저장할지 비교적 정확하게 추측할 수 있고, 캐시는 잘 작동함.

다음과 같이 하나의 시스템에 여러 프로세스가 존재하고 하나의 공유 메인 메모리가 있는 경우를 살펴보자.

                ┌───[Cache|CPU1]
[Main memory]───┤
                └───[Cache|CPU2]

CPU1에서 실행 중인 프로그램이 주소 A의 D 값을 읽는다고 가정하자. 이때, 어떤 문제가 발생할 수 있는지 다음 과정을 통해 살펴보자.

1. 데이터가 CPU1 캐시에 값 D가 존재하지 않음.

2. 시스템은 메인 메모리로부터 데이터를 가져오고 값 D를 얻음.

3. 프로그램이 주소 A의 값을 변경

4. 변경은 캐시에 존재하는 값만 D*으로 변경(메모리에 데이터를 쓰는 것은 시간이 오래 걸리므로 메인 메모리에 기록하는 것은 보통 나중에 함)함.

5. 운영체제가 프로그램의 실행을 중단하고 CPU2로 이동하기로 결정

6. CPU2에서 실행하는 프로그램이 주소 A의 값을 다시 읽음.

7. CPU2의 캐시에는 해당 데이터가 존재하지 않으므로 시스템이 메인 메모리에서 데이터를 가져옴.

8. 이때 D*이 아니라 갱신 전 값인 D를 가져옴!

위와 같은 문제를 캐시 일관성 문제(cache coherence)라고 부른다.
➡️ 이에 대한 기본적인 해결책은 하드웨어에 의해 제공

하드웨어는 메모리 주소를 계속 감시 ➡️ 항상 "제대로"된 상황만 발생하도록 시스템을 관리

특히, 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 항상 공유되도록 함.

버스 기반 시스템에서는 버스 스누핑(bus snooping)이라는 오래된 기법을 사용
➡️ 캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링
➡️ 캐시 데이터에 대한 변경이 발생하면, 다음 중 하나의 조치를 취함.
[조치 1: 무효화(invalidate)] 자신의 캐시에서 복사본을 삭제
[조치 2: 갱신(update)] 새로운 값을 캐시에 기록

나중 쓰기(write-back) 캐시는 메인 메모리에 쓰기 연산이 지연되기 때문에 캐시 일관성 문제를 훨씬 복잡하게 만듦.

2️⃣ 동기화를 잊지 말기

일관성 유지에 대한 모든 일을 캐시가 담당한다면, 프로그램 또는 운영체제는 공유 데이터를 접근할 때 걱정할 필요가 있을까? ➡️ YES(추후 책의 "병행성"에 관한 부분에서 자세히 설명)

CPU들이 동일한 데이터 또는 구조체에 접근 시(특히, 갱신 시)
➡️ 올바른 연산 결과를 보장하기 위해 락과 같이 상호 배제를 보장하는 동기화 기법이 많이 사용됨.

락-프리(lock-free) 데이터 구조 등의 다른 방식은 특별한 경우에만 사용함(복잡함).

예를 들어, 여러 CPU가 동시에 사용하는 공유 큐가 있다고 가정

캐시의 일관성을 보장하는 프로토콜이 존재
➡️ 락 없이는 항목의 추가나 삭제가 제대로 동작하지 않음.
➡️ 구조체를 원자적으로 갱신하기 위해서는 락이 필요

다음은 연결 리스트에서 원소 하나를 삭제하는 코드이다.

typedef struct __Node_t {
  int value;
  struct __Node_t *next;
} Node_t;

int List_Pop() {
  Node_t *tmp = head; // 이전 head를 기억
  int value = head−>value; // 값도 기억
  head = head−>next; // head를 다음 포인터로 이동 
  free(tmp); // 이전 head 해제
  return value; // head의 값을 반환
}

두 CPU의 쓰레드가 동시에 이 루틴으로 진입한다고 가정하자. 이때, 어떤 문제가 발생할 수 있는지 다음 과정을 통해 살펴보자.

1. 쓰레드 1이 첫 번째 행을 실행하면 head의 현재 값을 tmp에 저장한다.

2. 그 후 쓰레드 2가 첫 번째 행을 실행하면 head의 같은 값을 tmp에 저장한다.

3. tmp는 스택에 할당된다. (각 쓰레드는 자신만의 스택을 가지고 있음.)

4. 각 쓰레드는 동일한 헤드 원소를 제거하려고 한다.

5. 제대로 된 상황에서 각 쓰레드는 리스트의 첫 번째 원소를 한 번씩 제거해야 한다.

6. 그러나 헤드 원소를 두 번 삭제하고 같은 데이터 값을 두 번 반환하는 등의 문제를 야기한다.

이러한 문제에 대한 해결책은 락(lock)을 사용하여 올바르게 동작하도록 만드는 것이다.

위의 경우 간단한 mutex를 할당하고 루틴의 시작과 마지막에 관련 코드를 추가하여 문제를 해결할 수 있다.
➡️ 이러한 접근 방식은 성능 측면을 비롯한 문제들이 있음.
➡️ CPU의 개수가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느리게 됨.

3️⃣ 마지막 문제점: 캐시 친화성

멀티프로세서 캐시 스케줄러의 마지막 문제점은 캐시 친화성(cache affinity)이다.

CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB(Translation Lookaside Buffer, 변환 색인 버퍼)에 상당한 양의 상태 정보를 올려 놓게 된다.
➡️ 다음 번에 프로세스가 실행될 때 동일한 CPU에서 실행되는 것이 유리
➡️ 해당 CPU 캐시에 일부 정보가 이미 존재하므로 더 빨리 실행

하드웨어의 캐시 일관성 프로토콜 ➡️ 다른 CPU에서 실행되더라도 프로그램이 제대로 실행됨.

멀티프로세서 스케줄러는 스케줄링 결정을 내릴 때 캐시 친화성을 고려해야 함.
➡️ 가능한 한 프로세스를 동일한 CPU에서 실행하는 방향으로 결정

4️⃣ 단일 큐 스케줄링

단일 큐 멀티프로세서 스케줄링(single queue multiprocessor scheduling, SQMS)

단일 프로세서 스케줄링의 기본 프레임워크를 그대로 사용하는 것

장점

단순함: 기존 정책을 다수 CPU에서 동작하도록 하는 데 많은 변경이 필요하지 않음.
➡️ CPU가 2개라면 실행할 작업 두 개를 선택

단점

1️⃣ 확장성(scalability) 결여

스케줄러가 다수의 CPU에서 제대로 동작하게 하기 위해 코드에 일정 형태의 락을 삽입
➡️ 락은 SQMS 코드가 실행시킬 다음 작업을 찾기 위해 단일 큐에 접근할 때 올바른 결과가 나오도록 함.

락은 성능을 크게 저하시킬 수 있음.(동기화 오버헤드) ➡️ 시스템의 CPU 개수가 증가할수록 심해짐.

단일 락에 대한 경쟁이 증가할수록 시스템은 락에 점점 더 많은 시간을 소모

2️⃣ 캐시 친화성

실행할 5개의 작업과 4개의 프로세서가 있다고 가정하자. 다음은 이때의 스케줄링 큐의 모습이다.

Queue → [A] → [B] → [C] → [D] → [E] → NULL

다음은 작업들이 타임 슬라이스 동안 반복되며 실행될 때 작업 스케줄의 모습이다.

CPU 0 | [A][E][D][C][B] ...
CPU 1 | [B][A][E][D][C] ...
CPU 2 | [C][B][A][E][D] ...
CPU 3 | [D][C][B][A][E] ...
        시간의 흐름 →

각 CPU는 공유 큐에서 다음 작업을 선택하므로 각 작업은 CPU를 옮겨 다니게 됨.
➡️ 캐시 친화성 관점에서 보면 잘못된 선택

이 문제의 해결을 위해 대부분의 SQMS 스케줄러는 가능한 한 프로세스가 동일한 CPU에서 재실행될 수 있도록 시도
➡️ 특정 작업들에 대한 캐시 친화성을 고려하여 스케줄링 & 다른 작업들은 오버헤드 균등을 위해 분산시키는 정책

다음의 예시를 통해 이를 살펴보자.

CPU 0 | [A][E][A][A][A] ...
CPU 1 | [B][B][E][B][B] ...
CPU 2 | [C][C][C][E][C] ...
CPU 3 | [D][D][D][D][E] ...
        시간의 흐름 →

E만 프로세서를 이동하며 실행되고 있으며, 첫 번째 작업 스케줄과 비교하여 대부분의 작업에게 친화성을 보존하고 있다.

추후 다른 작업을 이동시킴으로써 친화성에 대한 형평성도 추구할 수 있음. ➡️ 구현이 복잡해질 수 있음.

5️⃣ 멀티 큐 스케줄링

멀티 큐 멀티프로세서 스케줄링(multi-queue multiprocessor scheduling, MQMS)

단일 큐 스케줄러로 인한 문제 ➡️ 일부 시스템은 CPU마다 큐를 하나씩 두는 등 멀티 큐를 마련해 둠.

MQMS에서 기본적인 스케줄링 프레임워크는 여러 개의 스케줄링 큐로 구성
➡️ 각 큐는 RR 등 특정 스케줄링 규칙을 따름

작업이 시스템에 들어가면 하나의 스케줄링 큐에 배치: 무작위 또는 비교적으로 작업이 적은 큐 등

그 후 각각의 큐에 담긴 작업들끼리 독립적으로 스케줄
➡️ 단일 큐 방식의 정보 공유 및 동기화 문제를 피할 수 있음.

다음의 예시를 통해 이를 더 알아보자.

2개의 CPU와 4 개의 작업이 시스템에 존재한다고 가정하자. CPU마다 스케줄링 큐를 하나씩 가지고 있으므로 다음과 같이 작업이 배치되었다고 하자.

Q0 → [A] → [C]
Q1 → [B] → [D]

RR의 경우 다음과 같은 스케줄이 생성될 수 있다.

CPU 0 | [A][A][C][C][A][A][C][C][A][A][C][C] ...
CPU 1 | [B][B][D][D][B][B][D][D][B][B][D][D] ...
        시간의 흐름 →

장점

SQMS에 비해 확장성이 좋다.

CPU 개수 증가 ➡️ 큐의 개수 증가: 락과 캐시 경합(cache contention)은 더 이상 문제가 되지 않음.

작업이 같은 CPU에서 계속 실행 = 캐시에 저장된 내용을 재사용 ➡️ MQMS는 본질적으로 캐시 친화적

단점

워크로드의 불균형(load imbalance) 문제

방금 전의 예시와 동일한 상황(4개의 작업, 2개의 CPU)에서 작업 하나(C)가 종료되었다고 가정하자.

스케줄링 큐는 다음과 같은 모습이 된다.

Q0 → [A]
Q1 → [B] → [D]

RR의 경우 다음과 같은 스케줄이 생성될 수 있다.

CPU 0 | [A][A][A][A][A][A][A][A][A][A][A][A] ...
CPU 1 | [B][B][D][D][B][B][D][D][B][B][D][D] ...
        시간의 흐름 →

A가 B와 D보다 2배의 CPU를 차지하는 상태가 된다. ➡️ 워크로드 불균형 발생

여기서 A까지 종료하면 스케줄링 큐와 CPU 사용 타임라인은 다음과 같다.

Q0 →
Q1 → [B] → [D]

CPU 0 | 
CPU 1 | [B][B][D][D][B][B][D][D][B][B][D][D] ...
        시간의 흐름 →

이처럼 CPU 0은 유휴 상태가 됨을 알 수 있다. ➡️ 워크로드 불균형 심각

MQMS의 조치 ➡️ 이주(migration): 작업을 이리저리 이동시키는 것

두 가지 경우를 통해 이를 살펴보자.

[경우 1]

Q0 →
Q1 → [B] → [D]

이 경우 운영체제는 B 또는 D 중 하나를 CPU 0으로 이동시켜 워크로드의 균형을 이룰 수 있다.

[경우 2]

Q0 → [A]
Q1 → [B] → [D]

이 경우는 한 번 이주를 한다고 해도 동일한 상황이 반복(2개, 1개)되므로 문제가 해결되지 않는다.
➡️ 작업들을 지속적으로 이주시켜야 함.

예시) 작업 B가 CPU 0과 CPU 1을 몇 개의 타임 슬라이스마다 주기적으로 이주
➡️ 이외에도 다양한 이주 패턴이 존재

그렇다면 이주의 필요 여부를 어떻게 결정할 수 있을까?

한 가지 기본적인 접근 방식: 작업 훔치기(work stealing)

방식은 다음과 같다.

1. 작업의 개수가 적은 큐(source queue)가 가끔 다른 큐(target queue)에 훨씬 많은 수의 작업이 있는지를 검사

2. 작업의 개수가 source queue < target queue라면 하나 이상의 source queue로 작업을 가져옴.

이때의 문제점: 큐의 잦은 검사로 인해 오버헤드가 발생하고 이에 따라 확장성에 문제 발생
➡️ 확장성은 멀티 큐 스케줄링의 가장 중요한 목적
➡️ 그렇다고 다른 큐를 자주 검사하지 않으면 심각한 워크로드 불균형 초래

큐 검사에 대한 적절한 값을 찾아내는 것은 다른 주제들의 비슷한 경우와 마찬가지로 어려운 일!

6️⃣ Linux 멀티프로세서 스케줄러

세 가지 스케줄러가 등장: O(1) 스케줄러, Completely Fair Scheduler(CFS), BF 스케줄러(BFS)

O(1)과 CFS는 멀티 큐, BFS는 단일 큐를 사용

O(1) 스케줄러는 우선순위 기반 스케줄러(MLFQ와 유사)
➡️ 프로세스의 우선순위를 시간에 따라 변경하여 다양한 목적 달성(특히, 상호작용을 가장 우선시)

CFS는 결정론적(deterministic) 비례배분(proportional share) 방식(보폭 스케줄링과 유사)

BFS는 셋 중 유일한 단일 큐 방식이며, 비례배분 방식
➡️ Earliest Eligible Virtual Deadline First(EEVDF)라고 알려진 더 복잡한 방식에 기반

🧺 멀티프로세서 스케줄링 정리 하기

단일 큐 방식(SQMS)

• 구현이 용이

• 워크로드의 균형을 맞추기 용이

• 많은 개수의 프로세서에 대한 확장성과 캐시 친화성이 좋지 못함.

멀티 큐 방식(MQMS)

• 확장성이 좋음.

• 캐시 친화성을 잘 처리함.

• 워크로드 불균형에 문제가 있고 구현이 복잡

CPU 스케줄러는 사소한 코드 수정으로 시스템의 동작이 엄청나게 바뀜
➡️ 모든 경우에 다 잘 동작하는 범용 스케줄러를 구현하는 것은 매우 어려움.

📚 참고 문헌

Operating Systems: Three Easy Pieces ― 10: Multiprocessor Scheduling (Advanced)

운영체제 아주 쉬운 세 가지 이야기 ― 13: 멀티프로세서 스케줄링 (고급)