[ OS ] 5.Multiprocessor Scheduling

들어가며

지금까지는 CPU Core가 하나인 경우의 스케줄링 알고리즘들을 봤다. 하지만 현대에는 다중 코어를 사용하는 만큼 이번에는 여러 코어가 사용될 때의 스케줄링 알고리즘을 보려 한다.

Multiprocessor Architecture

위 그림에서 보이는 SMP(Symmetric Multi-Processing)는 초기의 멀티 프로세서 시스템 구조이다. 각 코어는 자체 캐시를 가지고 있고, 각 CPU는 더 큰 공유 캐시를 가지고 있다. 그리고 모든 CPU는 하나의 공통 메모리에 연결되어 있다. 이 구조는 모든 프로세서가 하나의 공유 메모리에 균등하게 접근한다. 간단하고 균형이 잡혀있는 구조이지만, 프로세서 수가 증가하면 메모리 접근 경합이 심해질 수 있다.

NUMA(Non-Uniform Memory Access)는 앞서 말한 SMP의 한계를 극복하기 위해 발전된 구조이다. SMP와 유사하게 두개의 CPU가 있으며, 각각 여러 코어와 캐시를 포함하고 있다. 각 프로세서 또는 프로세서 그룹이 자체 로컬 메모리를 가지고 있다. NUMA 아키텍처는 프로세서들이 다른 프로세서의 메모리에 접근할 수 있지만, 접근 시간이 다를 수 있다. 하지만 더 많은 프로세서를 효율적으로 지원할 수 있게 해준다.

이제 대략적인 아키텍처에 대해 알아보았으니 멀티 프로세서 알고리즘에 대해 알아보자.

Single-Queue Scheduling(SQMS)

기존에는 CPU가 1개여서 매번 1개의 작업을 가져와서 실행을 했었지만, SQMS는 CPU의 개수가 N개인 경우 N개의 작업을 선택하여 실행한다. 위 그림에서는 4개의 CPU이므로 한번에 A, B, C, D의 job을 꺼내온 걸 볼 수 있다. SQMS는 하나의 time slice가 끝났을 때, 큐에서 다음 작업을 꺼내와 할당한다.(round-robin 방식으로 동작한다고 가정) 그림의 경우에는 A,B,C,D가 끝나고 다음 E가 cpu 0의 A 다음 작업으로 할당된 것을 볼 수 있다.

위 그림에서 A의 실행 흐름을 보기 위해 A만 색칠해 보았다. 이렇게 동작하게 된다면 문제가 있다. 첫 time slice에서 A가 cpu 0에서 동작하여 cpu 0에서 A에 관한 캐시를 할당하고 작업을 하지만 다음 time slice 에서는 cpu1에서 동작한다. 이렇게 되면 cpu 0에서 사용하던 A에 관한 캐시를 사용하지 못하고 cpu 1은 메모리에서 다시 A에 관한 데이터를 가지고 와야 한다. 이런 식으로 반복되다 보면 메모리 지역성이 떨어지게 된다.(위 NUMA 아키텍처에서 작업이 옮겨갈때마다 CPU가 메모리에서 점점 멀어진다고 볼 수 있음) 또한, 각각의 CPU들이 자신들의 clock으로 동작하기 때문에 동기화 문제가 발생할 수 있다.

이런 방식으로 동작하게 된다면, scalability(자원이 늘어나면 늘어날수록 선형적으로 성능이 좋아질 것으로 기대되는 바)가 좋아질 수 없다. 병렬적으로 동작하지 않기 때문이다.

따라서 이런 문제들을 개선한 다음 스케줄러를 보자

Multi-Queue Scheduling(MQMS)

MQMS는 위 SQMS의 문제를 개선한 스케줄링 알고리즘이다. 위 그림처럼 CPU 개수별로 하나의 큐를 가지고 있다. cpu0에는 Q0의 A, C 작업만 round robin으로 할당된 것을 볼 수 있고, cpu1에는 Q1의 작업을 round robin 형태로 할당된 것을 볼 수 있다. 이런 방식으로 동작하면 SQMS와 다르게 메모리의 지역성이 좋아진 것을 알 수 있다.

Load imbalance

위 그림의 경우, 작업이 다르게 배정받은 경우 불균형이 생길 수 있다.

load imbalance 해결책

불균형 문제를 해결하기 위해 migration 기능이 있다. 불균형이 생겼을 때, 작업 하나를 다른 쪽으로 옮겨주면 불균형 문제가 해결된다. 이런 migration 정책들은 여러가지가 존재하는데 운영체제별로 다르고, 운영체제의 버젼마다 조금씩 바뀌어가고 있는 중이다. 대표적인 알고리즘 중에는 work stealing이 있다.

work stealing은 작업이 적은 큐(source)가 다른 큐(target)을 주기적으로 확인하고, 타겟 큐가 소스 큐보다 더 많은 작업을 가지고 있다면, 소스 큐가 타겟 큐에서 하나 이상의 작업을 훔쳐와 부하 균형을 잡는다. 어떤 작업을 가지고 올지는 운영체제 정책마다 다르지만, 일반적으로 memory bound하지 않은 작업을 골라서 가지고 온다.

만약, 위 그림의 Tricky Case의 경우, Q0가 Q1의 작업을 가지고 온다고 하더라도 Q1이 D 작업 하나만을 실행시키게 되고 이번엔 Q1이 Q0의 A를 가져올 수 있다. 이런 식으로 계속 왔다 갔다 하는 경우 문제가 있을 수 있지만 운영체제는 최대한 fair하게 동작하게 하려고 구현하고 있다.

Linux CPU Schedulers

Completely Fair Scheduler(CFS)

• SCHED_NORMAL (전통적으로 SCHED_OTHER라고 불림)
• 가중치 기반 공정 스케줄링
• 레드블랙 트리로 구현되어 있음(well balanced)
• 각 노드의 숫자는 작업들이 할당된 시간을 의미, 가장 작은 노드를 선택 후 실행

Real-Time Schedulers

• mlfq와 유사
• SCHED_FIFO와 SCHED_RR
• 우선순위 기반 스케줄링
• sched_setattr() 시스템 콜로 우선순위를 조정해줄 수 있음(기본적으로 우선순위 고정)

Deadline Scheduler

• SCHED_DEADLINE
• EDF(Earliest Deadline First)-like 주기적 스케줄러
• sched_setattr()
• 프로그램들이 주기적으로 실행, 정해놓은 deadline 안에 실행

Completely Fair Scheduler(CFS)

vruntime - 가상 실행 시간

각 작업은 가상 실행 시간(vruntime)을 기준으로 레드-블랙 트리에 저장된다. vruntime은 각 프로세스의 nice값(-20 ~ 19)을 기반으로 계산된다. nice 값이 낮을수록 가중치 비율이 낮고, nice 값이 높을수록 가중치 비율이 높다.

CFS 스케줄러는 프로세스의 우선순위(nice 값)에 따라 CPU 시간을 공정하게 배분하려고 한다. nice 값이 낮은 프로세스는 더 많은 CPU 시간을 할당받고, 높은 프로세스는 더 적은 시간을 할당받는다.

우선순위

priority = nice + 120

CFS는 nice 값이 -20 ~ 19이므로 100 ~ 139까지의 값을 가지게 된다. 그러면 나머지 0~99는 뭘까? 0부터 99까지는 real-time scheduler가 해당된다.

renice command

유저는 nice 값을 -1 ~ -20까지 조정할 수 없다. (root 권한만 가능)

멀티프로세서 환경에서의 CFS

멀티프로세서 환경에서 core의 불균형 문제를 CFS는 어떻게 해결하고 있을까?

load(작업량)의 표현

앞에서는 load를 큐의 길이로 판단을 하였다. 하지만 리눅스에서는 CPU 사용률(CPU utilization)의 합으로 표현한다. 스레드의 load는 CPU 사용률의 평균, core의 load는 계산된 스레드 load의 합으로 표현한다.

현재 이런 load의 균형을 맞춰주기 위해 4ms마다 분배를 시도한다. 그리고 불균형하다라고 판단되었을 때에, 캐시와 NUMA(노드 간 부하 차이가 25% 미만일 경우 부하 균형을 조정하지 않음)를 고려한다.