[OS] 멀티프로세서 스케줄링/ 단일 큐 스케줄링 / 멀티 큐 스케줄링 장단점 알아보기

※ 개요 

다중 CPU 시대가 오면서 많은 문제가 발생하였다. 가장 중요한 것은 전통적 응용프로그램은 오직 하나의 CPU만 사용한다는 것이다.

더 많은 CPU를 추가해도 더 빨리 실행되지 않는다.

이 문제를 해결하려면 응용 프로그램을 병렬(parallel)로 실행되도록 다시 작성해야 한다. 보통 쓰레드를 이용한다. 

 

 - 멀티 쓰레드 응용 프로그램은 작업을 여러 CPU에 할당하며, 따라서 더 많은 수의 CPU가 주어지면 더 빠르게 실행된다. 

- 응용 프로그램뿐 아니라 운영체제가 새로 직면한 문제는 멀티프로세서 스케줄링이다. 

- 지금까지 단일프로세서 스케줄링의 많은 원칙들을 여러 CPU에서 동작하도록 어떻게 확장할 수 있을까? 

---

※ 단일 CPU 하드웨어 vs 멀티 CPU 하드웨어

[단일 CPU 시스템]

- 하드웨어 캐시 계층이 존재한다. 이 캐시는 프로그램을 빠르게 실행하기 위해 존재한다.

캐시가 장착된 하나의 CPU

[캐시]

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

- 메인 메모리는 모든 데이터를 저장하지만 느리다. 

- 캐시는 시간 지역성(temporal locality)와 공간 지역성(spatial locality)에 기반한다.

- 시간 지역성은 데이터가 한번 접근되면 가까운 미래에 다시 접근되기 쉽다는 것이다.

- 공간 지역성은 프로그램이 주소 x의 데이터에 접근하면 x 주변의 데이터가 접근되기 쉽다는 것이다.

---

[멀티 CPU 시스템]

: 단일 CPU 시스템에 비하여 문제점 2가지가 있다. 

 

▶ 1. 캐시 일관성 문제 (cache coherence) 

CPU1에서 실행 중인 프로그램이 주소 A를 읽고, 값을 변경하였다. 변경은 캐시에 존재하는 값만 변경한다.

메모리에 데이터를 쓰는 것은 시간이 오래 걸리므로 보통 나중에 한다. 운영체제가 프로그램의 실행을 중단하고 CPU2로 이동하기로 결정하였다. 이때 프로그램은 주소 A의 값을 읽는다. CPU2의 캐시에는 데이터가 존재하지 않으므로 메인 메모리에서 데이터를 가져온다.

이때 두 CPU의 캐시에 저장된 데이터 값이 달라지게 된다. 

 

- 해결책

: 하드웨어는 메모리 주소를 계속 감시하고, 항상 올바른 순서로 처리되도록 시스템을 관리한다. 특히, 여러 개의 프로세스들이 하나의 메모리를 갱신할 때는 항상 공유되도록 한다. 버스 기반 시스템에서는 버스 스누핑(bus snooping) 이라는 기법을 사용한다. 

캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링한다. 

메모리를 공유하는 캐시가 장착된 두 개의 CPU

- 주의 : 일관성 유지에 대한 모든 일을 캐시가 담당하더라도, 프로그램 또는 운영체제는 동기화를 위해 추가 작업을 해주어야 한다.

즉, CPU들이 동일한 데이터에 접근할 때 (특히, update) 올바른 연산 결과를 보장하기 위해 락과 같은 상호 배제를 보장하는 동기화 기법이 많이 사용된다. 구조체를 원자적으로 갱신하기 위해서는 락(lock)이 필요하다. 그러나 CPU의 개수가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느리게 된다. 즉, 성능이 나빠진다.

 

 

▶ 2. 캐시 친화성 문제

- CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB(translation lookaside buffer, page table의 cache)에 상당한 양의 상태 정보를 올려 놓게 된다. 때문에 다음 번에 프로세스가 실행될 때 동일한 CPU에서 실행되는 것이 유리하다. 해당 CPU 캐시에 일부 정보가 이미 존재하고 있기 때문에 더 빨리 실행될 것이기 때문이다. 반면 프로세스가 매번 다른 CPU에서 실행되면 실행할 때마다 필요한 정보를 캐시에 다시 탑재해야 하기 때문에 프로세스의 성능은 더 나빠질 것이다. 

즉, 가능한 한 프로세스를 동일한 CPU에서 실행하려고 노력하는 방향으로 결정해야 한다. 

 

---

※ 운영체제는 어떻게 작업을 여러 CPU에 스케줄 해야 하는가? 

- 멀티 프로세서 시스템의 스케줄러 개발 방법에는 2가지가 있다.

▶ 1.  단일 큐 스케줄링 (single queue multiprocessor scheduling, SQMS)

[장점]

- 기존의 단일 CPU 스케줄러가 있다면 하나의 큐밖에 없기 때문에 구현이 간단하다. 

 

[단점]

1. 동기화 오버헤드 때문에 확장성 (scalability)이 좋지 않다.

스케줄러가 다수의 CPU에서 제대로 동작하게 하기 위해 코드에 일정 형태의 락을 삽입한다.

락은 SQMS 코드가 단일 큐를 접근할 때 (즉, 실행시킬 다음 작업을 찾을 때) 올바른 결과가 나오도록 한다.

그러나 불행히도 락은 성능을 크게 저하시킬 수 있고, 시스템의 CPU 개수가 증가할수록 더욱 그렇다.

단일 락에 대한 경쟁이 증가할수록 시스템은 락에 점점 더 많은 시간을 소모하게 되고 실제 필요한 일에 쓰는 시간은 줄어든다.

 

2. 캐시 친화성에 문제가 있다.

 

▶ 2. 멀티 큐 스케줄링 (multi-queue multiprocessor, MQMS)

- 단일 큐 스케줄러로 인한 문제를 해결

- CPU마다 큐를 하나씩 둔다. 

- CPU는 각자 하나씩의 스케줄링 큐를 가지고 있으므로 운영체제는 각 작업을 배치할 큐를 결정해야 한다.

 

[장점]

1. 확장성이 좋다. CPU 개수가 증가할수록, 큐의 개수도 증가하므로 락과 캐시 경합(cache contention)은 더 이상 문제가 되지 않는다.

2. 캐시 친화적이다. 작업이 같은 CPU 에서 계속 실행되기 때문에 캐시에 저장된 내용을 재사용하는 이점을 가진다.

 

[단점]

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

예를 들어, 4개의 작업 2개의 CPU 가 있다고 가정하자.

CPU-a의 큐에는 작업 A와 B가 있고, CPU-b의 큐에는 작업 C와 D가 있다.

만약 A와 B 작업이 모두 종료하여 B와 D만 남았다면 CPU-a는 놀고 있고 CPU-b만 사용하게 된다.

 

그렇다면 어떻게 이 오버헤드 불균형 문제를 해결할 수 있을까? 

 

[워크로드 불균형 해결책]

- 작업을 한 CPU에서 다른 CPU로 이주(migration) 시킴으로써 워크로드 균형을 달성한다. 

이때 많은 다른 이주 패턴이 존재한다. 

 

그렇다면 여기서 또 다른 문제는 이주 필요 여부를 어떻게 결정할까?

바로 작업 훔치기 (work stealing)이라는 기술을 사용한다. 작업의 개수가 낮은 소스큐가 다른 대상큐를 감시한다. 대상 큐가 소스 큐보다 더 가득 차 있다면 워크로드 균형을 맞추기 위해 소스는 대상에서 하나 이상의 작업을 가져온다.