요즘 나오는 CPU에는 멀티 코어, 쿼드 코어, 헥사 코어 등으로 광고하는 것을 볼 수 있다. 이렇듯 요즘엔 멀티 프로세서 시스템이 보편화되고 있다. 이러한 CPU에선 어떻게 스케줄링해서 사용해야 할까?

하나 이상의 CPU가 있으면 지금까지는 고려하지 않았던 몇 가지 문제가 발생할 수 있다. 가장 중요한 것은 일반적인 프로그램은 단일 CPU만 사용한다는 것이다. 이말인 즉슨, CPU가 여러 개라고 해서 하나의 프로그램이 더 빨리 실행되는 것은 아니라는 것이다. 이러한 문제를 해결하려는 방법 중 하나는 스레드를 사용해서 병렬로 실행될 수 있도록 다시 설계하는 것이다. 이렇게 만든 멀티스레드 프로그램은 수행해야 하는 작업을 여러 CPU에 나눠서 실행할 수 있기 때문에 CPU가 여러 개라면 더 빠르게 실행될 수 있다. 다른 방법으로는 멀티 프로세서에서 사용할 수 있는 스케줄러를 사용하는 것이다.

1. 멀티 프로세서의 종류와 특징

1.1 프로세싱 기법에 따른 구분

1) 비대칭 멀티프로세싱(Asymmetric multiprocessing)

• 하나의 master 프로세서가 다른 프로세서들을 관리감독하는 형태
• master 프로세서가 모든 스케줄링 결정과 입출력 처리, 로드 밸런싱을 다 결정한다.
• 다른 프로세서들은 User 코드만 수행한다.
• 한 프로세서가 다 처리하기 때문에 공유자원이 존재하지 않고 프로세서 간의 이동이 필요없다.

2) 대칭 멀티프로세싱(Symmetric multiprocessing(SMP))

• 대부분의 멀티프로세서가 이러한 형태다.
• 각각의 프로세서가 동등한 권한으로 프로세싱하는 형태
• 각각의 프로세서는 각자 스케줄링을 진행한다.
• 프로세스들은 하나의(공동의) 준비큐거나, 각 프로세서마다의 private 준비큐에 저장되어 있으며, 모든 프로세서에는 각각의 스케줄러가 있어야 한다.
• 때문에 동시에 여러 프로세서에서 공유자원에 접근할 시 동기화 문제가 발생할 수 있다.

1.2 메모리 접근에 따른 구분

1) Uniform Memory Access

• 하나의 공유된 메모리에 여러개의 프로세서가 할당된 형태
• 하나의 메모리를 공유하여 사용한다.
• 프로세서가 어느 메모리를 참조하든 접근속도가 동일하다.

2) Non-Uniform Memory Access(NUMA)

• 각각의 프로세서에 메모리가 따로 담겨있는 형태
• 만약 다른 프로세서에서 자신의 메모리를 참조할 때 속도가 느리므로, 스케줄링 시에 이를 고려해줘야 한다.
• 이 때 필요한 개념이 Affinity 이다.
  

2. 프로세서 선호도(Processor Affinity)

프로세스 스케줄링 시에, 특정 프로세서에 지정을 해주는 것, 프로세스는 특정 프로세서에서만 실행하게 된다.

프로세스는 현재 돌고있는 프로세서의 메모리에 address space 등의 메모리를 차지할 것이다. (NUMA의 경우)
이 때, 다른 프로세서의 메모리에 있는 데이터를 참조한다면 시간이 오래걸릴 것이다. 그래서 한 프로세서에서 다른 프로세서로의 이주를 피하고 같은 프로세서에서 처리하려는 현상이다. 이 현상을 이용해 자원소모를 최소화할 수 있다.

즉, 자신이 현재 돌고있는 프로세서의 메모리와, 자신이 접근하려는 데이터가 있는 메모리를 같도록 만들어줄 때 Processor Affinity를 활용하기도 한다.

• soft Affinity : 같은 프로세서에서 돌 수 있도록 우선순위를 높여주는 등 노력은 하지만, 보장은 안되는 경우
• hard Affinity : 특정 프로세서에만 돌도록 완전히 보장시켜주는 경우

3. 부하 균등화(load balance)

SMP에서 프로세서가 하나 이상(처리기마다 준비큐가 존재)이라는 것을 최대한 활용하려면 부하를 모든 프로세서에 균등하게 배분하는 것이 매우 중요하다. 프로세서 선호도와 엇갈리는 역할이지만 절대적인 기준은 없고 상황에 따라 달리해야한다.

• Push 이주
  특정 task가 주기적으로 각 프로세서의 부하를 검사하고 만일 불균형 상태면 과부하인 프로세서에서 쉬고 있거나 덜 바쁜 프로세서로 프로세스를 이동시킴으로써 부하를 분배한다.
• Pull 이주
  쉬고 있는 처리기가 다른 처리기의 프로세스 pull하여 자기 쪽으로 가져온다.

4. 멀티프로세서 구조

싱글 프로세서 시스템에서 멀티프로세서 시스템으로 갈 때 가장 중요한 것은 하드웨어 캐시의 사용과 CPU간의 데이터 공유이다.

우선 싱글 프로세서와 멀티 프로세서의 근본적인 차이에 대해 알아보자.

CPU에는 아주 빠른 캐시가 있다.(하드웨어 캐시는 메인 메모리에 비해 작은 대신 액세스가 빠른 메모리이다.) 위와 같이 싱글 프로세서에는 하나의 캐시가 존재한다. 캐시에는 메인 메모리에 있는 현재 프로세스에서 자주 사용되는 데이터들이 저장되어 있다. 자주 사용되는 데이터를 아주 빠른 캐시에 저장해둠으로써 비교적 느린 메모리를 빠른 것처럼 보이게 할 수 있다. 예를 들면, 어떤 프로그램에서 필요한 데이터를 메인 메모리에서 가지고 온다고 가정하겠다. 메모리는 느리기 때문에 아주 오랜 시간이 걸려서 데이터를 가져오게 된다. 그런데 다음에 동일한 데이터를 또 다시 메모리에서 가지고 온다고 하면 어떨까? 매번 느린 메모리에서 데이터를 가지고 오는 것이 마음에 들지 않을 것이다. 따라서 자주 사용될 것 같은 데이터를 캐시에 저장해서 해당 데이터가 필요할 때마다 빠르게 가지고 옴으로써 훨씬 더 빠르게 실행되게 만들어 준다.

그렇다면 캐시에는 어떤 데이터가 저장되는 것이 효과적일까? 이는 지역성(locality)이라고 하는 개념이 해결해준다.(캐시는 지역성 기반으로 작동한다.) 지역성이라고 하는 이 특성은 시간(temporal) 지역성과 공간(Spatial) 지역성이 있다. 시간 지역성이란 지금 사용한 데이터는 곧 다시 사용될 가능성이 높다는 개념이고, 공간 지역성은 어떤 데이터가 사용되었다면 그 근처에 존재하는 데이터들도 사용될 가능성이 높다는 개념이다. 이러한 지역성이라는 특성을 활용해서 캐시에 데이터를 저장할 수 있다.

그러면 어제 위와 같이 하나의 메모리를 공유하는 시스템에 프로세서가 여러 개라면 어떻게 될까? CPU가 여러 개가 되었기 때문에 캐시도 여러개가 된 것을 볼 수 있다. 지역성을 기반한 캐시는 프로세서가 하나인 시스템에선 매우 단순하고 성능을 개선해주지만, 멀티 프로세서 환경으로 가면 문제가 생긴다. 메인 메모리를 수정하는 것은 매우 느리기 때문에 CPU는 쓰기 작업을 수행할 때 메인 메모리의 값을 변경하는 대신 캐시의 값만 수정하고 메인 메모리는 나중에 업데이트 하는데, 업데이트 되기 전에 다른 프로세서가 메인 메모리의 값을 읽으면 동시성 문제가 생긴다. 그래서 멀티 프로세서를 사용하는 프로그램을 짤 땐 lock을 거는 등 주의해서 짜야한다.

예와 함께 더 자세히 알아보자.
CPU가 2개 있는 위와 같은 시스템에서 프로그램을 동작하는 예에 대해 설명한다. CPU1에서 실행되는 프로그램이 메모리에서 A 데이터를 가지고 왔다. 이때 가지고 온 A 데이터를 수정해서 CPU1 캐시에 쓴다. 근데 컴퓨터는 메모리에 수정된 값을 바로 저장하지 않는다. 이는 메모리는 너무 느리기 때문에 최대한 적게 접근하려고 하기 때문인데, 이렇게 수정된 값을 메모리에 바로 적용하지 않는 것을 delayed write라고 한다. 어쨌든 그런 뒤에 동일한 프로그램을 이제는 CPU2에서 실행한다. A라는 데이터가 필요해 메모리에서 가지고 온다. 그럼 이 때 가져온 A라는 데이터는 이미 CPU1에서 가져와서 수정이 되었는데도 불구하고 수정되지 않은 데이터를 가지고 온 셈이다. 이러한 큰 문제를 cache coherence(캐시 일관성)이라고 한다. 이런 문제는 어떻게 해결할까?

가장 기본적인 해결방법은 하드웨어에 의해 제공된다. 메모리 접근을 모니터링하는 것이다. 각각의 캐시는 메인 메모리에 연결한 버스를 관찰하고 메모리 업데이트를 관찰한다. 그런 뒤에 CPU가 캐시에서 데이터를 수정하면 그것을 인식해 나중에 메모리가 캐시에서 수정된 데이터를 가져올 때 적절히 처리할 수 있도록 한다.

4.1 동기화

캐시가 일관성을 제공하기 위해 아까 언급한 방법을 수행한다고 할 때 프로그램이 공유 데이터에 접근할 때는 어떤 것을 걱정해야 할까? 그에 대해 동시성에 대해 알고 있다고 가정하고 간단하게 짚고 넘어가보자.

CPU에서 공유 데이터에 접근할 때 상호 배제(lock 등)를 사용하여 정확성을 보장해줘야 한다. 예를 들어 여러 CPU에서 동시에 데이터에 접근하는 경우 lock이 없다면 데이터가 어떻게 변해있을 지 예상할 수 없다. 예를 들어 CPU1과 CPU2가 동시에 5라는 데이터에 접근했다고 가정하자. 그 후 CPU1은 5를 1로 바꾸고 CPU2는 5를 2로 바꿨다고 한다면, 현재 데이터는 어떤 값을 가지고 있을 까? 만약 1이 저장되어 있다면 CPU2의 입장에선 당황스럽지 않을까? 이렇게 일관성을 보장할 수 없기 때문에 lock이라는 개념이 필요하다.

4.2 캐시 선호도(Cache Affinity)

마지막 문제는 캐시 선호도이다. 특정 CPU에서 프로그램을 수행하면 해당 프로그램은 해당 CPU의 캐시에 여러 가지 데이터를 저장한다. 다음에 다시 수행될 때 캐시에 저장된 정보를 가지고 더 빠르게 수행할 수 있다. 하지만 만약 CPU가 여러 개라서 다음에 수행될 때 다른 CPU에서 수행된다면 어떻게 될까? 또다시 필요한 데이터를 가지고 와야 하는 문제가 발생한다. 즉, 성능이 나빠지는 것이다. 따라서 멀티 프로세서에서의 스케줄러는 프로그램을 스케줄링할 때 캐시 선호도를 고려해서 프로그램을 동일한 CPU에서 계속 실행되도록 스케줄링 해줘야 한다.

5. 멀티 프로세서 스케줄링

5.1 싱글 큐 스케줄링(SQMS)

이전까지 알아본 싱글 프로세서에서 쓰던 스케줄러를 그대로 사용하는 것이다. 하나의 큐에 작업들을 넣어서 처리하는 이러한 방식을 SQMS(Single Queue Multiprocessor Scheduling)이라고 한다. 이 방법은 단순하다는 장점이 있다.

하지만 SQMS에서는 두 가지 문제가 발생한다.
첫 번째 문제는 확장성 부족(a lack of scalability)이다. 스케줄러가 여러 CPU에서 잘 작동하는 지 확인하기 위해 아까 위에서 lock을 사용한다고 했다. 하지만 lock을 사용하면 성능을 크게 저하시킬 수 있다. 실제로 이렇게 사용하게 되면 실제 프로그램 수행 시간보다 lock을 처리하는 작업에 더 많은 시간을 사용할 수도 있다.

두 번째 문제는 캐시 선호도이다. 예를 보며 알아보자.

위와 같이 큐가 있고 CPU는 4개가 있다고 가정했을 때, 순서대로 수행된다면 어떻게 될까? A프로세스 기준으로, A가 CPU0에서 time slice를 모두 사용해서 ready 상태로 돌아간 뒤에 다음 스케줄링이 될 때 CPU1에서 수행된다고 하면 캐시 선호도가 전혀 적용되지 않는 것을 볼 수 있다.

이러한 문제를 해결하기 위해 SQMS에서는 별도의 메커니즘을 사용해 캐시 선호도를 구현한다.

SQMS에서는 위와 같이 캐시 선호도를 구현한다. 그런데 E프로세스의 입장에서 보면 캐시 선호도가 전혀 적용되고 있지 않다. 이와 같이 SQMS에서는 캐시 선호도가 적용되는 프로세스도 있는 반면 적용되지 않는 프로세스가 존재할 수 있다.

정리하자면, 캐시 선호도 문제가 생기는데, 모든 CPU가 한 개의 큐에서 작업을 가져오기 때문에 작업이 여러 개의 CPU 사이를 왔다갔다하게 되어 성능이 나빠진다. 따라서 SQMS의 구현체는 대부분 캐시 선호도를 보존하기 위한 알고리즘을 포함한다.
그렇다면 이러한 문제가 있는 SQMS가 최선일까?

5.2 멀티 큐 스케줄링(MQMS)

위에서 발생한 SQMS의 문제점을 보완한 MQMS(Multi Queue Multiprocessor Scheduling)에 대해 알아볼 것이다. SQMS와의 차이점은 큐가 여러개이다. CPU는 각각 하나 또는 그 이상을 가지며 각각의 큐는 RR과 같은 특정한 스케줄링 방법을 사용한다. 작업이 시스템에 들어오면 heuristic에 따라 하나의 큐에만 배치가 된다. 그런 뒤엔 CPU 독립적으로 스케줄링되기 때문에 SQMS에서 발생한 문제들을 방지할 수 있다. 예를 보며 이해해보자.

위와 같이 2개의 CPU가 존재하며 각각의 CPU에 개별적으로 큐가 존재한다고 가정하면, CPU는 자신이 처리할 큐에 있는 작업들만 처리하므로 위와 같이 캐시 친화도가 잘 적용된다. 그렇다면 지금의 MQMS에는 문제점이 없을까? 그건 아니다. 지금은 큐에 있는 작업 수가 같았고 모두 완료가 되지 않아서 문제가 발생하지 않았지만 다른 예에서는 어떨까?

위의 예를 보면, 아까의 예에서 Q0에 있던 C 프로세스가 완료된 상태이다. 문제점이 보이는가? A 프로세스가 CPU를 독점하고 있다. 이는 B, D입장에서 화를 낸다. “아니 왜 쟤만 많이 실행해?”

여기선 라인 잘 탄 A마저 완료되어 Q0에는 더이상 작업이 없어 CPU0가 놀고 있다.
이제는 B, D 프로세스가 화를 내는 것이 아닌 사용자도 화를 낸다. “아니 왜 저 CPU는 쉬는거지?”
이러한 문제를 load imbalance(부하 불균형)이라고 한다. 즉, 특정 큐에 들어간 작업어떻게 하면 해결할 수 있을까?

아주 간단하게 생각하면 B, D 프로세스 중 하나를 Q0로 옮기는 것이다. 이러한 것을 migration 이라고 한다. 이렇게 프로세스를 이동하면 load balance를 만족시킬 수 있다. 예를 보며 migration을 살펴보자.

즉, 이 상태에서 Q1에 있는 B, D 중 하나를 Q0으로 옮겨주면 끝이다. 그럼 이런 경우는 어떨까?

위와 같은 경우에서는 B, D 중 하나를 옮긴다고 해서 해결될 거 같진 않다. 그 이유는 옮기는 순간 Q1에서 또 문제가 발생하기 때문이다. 이런 문제는 어떻게 해결하면 좋을까? 답은 계속 이동하는 것이다. B를 이동시켰다가 A도 이동시켰다가 하는 등 프로세스들을 계속 이동시키는 것이다. 그럼 결국 아래와 같이 수행될 것이다.

이렇게 하면 load balance가 지켜진다. 이렇게 프로세스를 이동할 때 무엇을 어디로 이동할 지 결정하는 방법에는 work stealing(작업 훔치기)가 있다. 이는 작업이 적은 큐가 다른 큐를 보고 작업이 많아 보이면 작업을 훔쳐버린다.

그런데 이렇게 작업을 훔쳐가면서까지 load balance를 맞추려고 하다 보면 근본적인 문제에 부딪히게 된다. 애초에 SQMS에서 lock에 의한 오버헤드가 발생했고 확장 문제가 발생해서 MQMS로 넘어왔는데 너무 자주 작업을 훔치게 되면 동일한 문제가 발생한다. 그렇다고 훔치치 않으면 load balance에 문제가 발생하므로 이 둘을 잘 조율할 수 있는 값을 찾는 것이 숙제다.

6. 정리

SQMS는 단순하지만 캐시 선호도 문제와 lock에 의한 오버헤드라는 문제가 있었고, MQMS는 확장성이 뛰어나고 캐시 선호도를 잘 처리하지만, load imbalance라는 문제가 발생했고 SQMS보다 복잡했다.

참고

https://icksw.tistory.com/127?category=878876
https://kdy1.github.io/post/study/os/multi-process-scheduling/
https://ch4njun.tistory.com/117