[운영체제] Multiprocessor Scheduling

멀티프로세서 구조

단일 CPU 시스템에서는 하드웨어 캐시 계층이 존재한다. 이 캐시는 프로그램을 빠르게 실행하기 위해 존재한다.

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

 

자주 접근되는 데이터를 캐시에 임시로 가져다 둠으로써 시스템은 크고 느린 메모리를 빠른 메모리처럼 보이게 하는 것이다.

 

캐시는 지역성에 기반한다.

• 시간 지역성: 데이터가 한 번 접근되면 가까운 미래에 다시 접근되기 쉽다.
• 공간 지역성: 프로그램이 주소 x의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다.

만약에 하나의 시스템에 여러 프로세스가 존재하고 하나의 공유 메인 메모리가 있다면 어떻게 될까.

 

다음은 멀티프로세서에서 발생할 수 있는 문제점 중 하나이다.

CPU0에서 실행 중인 프로그램이 주소 A(= 값은 D)를 읽는다고 해보자.
처음에는 데이터가 CPU0 캐시에 존재하지 않기 때문에 메인 메모리로부터 데이터를 가져와 값 D를 얻는다. 이후 프로그램은 주소 A의 값을 변경하는데, 캐시에 존재하는 값만 D'로 갱신한다.

운영체제가 프로그램의 실행을 준당하고 CPU1로 이동하고자 한다.
프로그램은 주소 A의 값을 다시 읽는다. CPU1의 캐시에는 그러한 데이터가 존재하지 않기 때문에 메인 메모리에서 데이터를 가져온다. 이때 D'이 아니라 옛날 값인 D를 가져온다.

 

이러한 문제를 캐시 일관성 문제(cache coherence)라고 부른다.

 

이를 해결하기 위한 방법으로 버스 스누핑(bus snooping)이 있다.

캐시가 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링하여 캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효화시키거나 갱신하는 것이다.

 

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

CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB에 정보를 올려 놓게 되는데, 다음 번에 프로세스가 실행될 때에도 동일한 CPU에서 실행되는 것이 유리할 것이다. 

반대로, 매번 다른 CPU에서 실행된다면 실행할 때마다 필요한 정보를 다시 캐시에 탑재해야 되기 때문에 프로세스의 성능은 나빠질 수밖에 없다.

따라서 캐시 친화성을 고려해야 한다.

---

단일 큐 스케줄링

단일 큐 멀티프로세서 스케줄링(SQMS)은 모든 작업을 하나의 전역 큐(single queue) 안에 넣어둔다.

여러 CPU 중 하나가 실행 가능한 상태가 되면, 이 전역 큐에서 다음 작업을 꺼내 실행하는 것이다.

 

그러나 이 SQMS에도 단점이 있다.

 

1) 확장성 결여

• 다수의 CPU가 전역 큐에 접근하기 때문에 일정 형태의 락(lock)을 삽입하는데, 락은 성능을 크게 저하시킬 수 있다.

2) 캐시 친화성

• 같은 작업을 매번 다른 CPU가 실행할 수 있다.
• 예를 들어, 아래와 같이 A, B, C, D, E의 5개 작업이 있고 4개의 프로세서가 있다고 가정하자.

• CPU0 ~ CPU3이 순서대로 작업을  가져가 실행하고 있다. 결과적으로 같은 작업이 CPU마다 번갈아 실행되므로, 캐시 친화성 관점에서 잘못된 선택이 되는 것이다.

• 그래서 이를 해결하기 위해 SQMS는 같은 작업들은 같은 CPU에서 실행하도록 배정할 수 있다.
• 아래 그림을 보면, A ~ D는 항상 같은 CPU에서 실행되므로 캐시 친화성을 보전하고 있는 것을 볼 수 있다.

• 단, 이렇게 된다면 스케줄링 알고리즘이 복잡해지고 구현 난이도가 상승한다.

---

멀티 큐 스케줄링

SQMS의 문제를 해결하기 위해 CPU마다 큐를 하나씩 두는 방식이 멀티 큐 멀티프로세서 스케줄링(MQMS)이다.

각 큐는 라운드 로빈 같은 특정 스케줄링 규칙을 따를 것이고 물론 어떤 스케줄링 기법도 사용 가능하다.

 

예를 들어, 2개의 CPU (CPU0, CPU1)에 4개의 작업(A, B, C, D)이 시스템에 존재한다고 가정하자.

이때 운영체제는 각 큐에 아래와 같은 작업을 각각 배치해야겠다고 결정했다.

라운드 로빈의 스케줄링 정책을 가진다면 아래처럼 스케줄이 형성되는 것이다.

• 장점
  • 확장성이 좋다. CPU의 개수가 증가해도 큐의 개수도 증가하므로 락과 캐시 경합은 문제가 되지 않는다.
  • 캐시 친화적이다. 작업이 계속 같은 CPU에서 실행되고 있다.
• 단점
  • 워크로드의 불균형(load imbalance)이 발생한다.
  • 만약, Q0에서 C가 종료되었을 때 Q0에는 A만 남는다. CPU0은 계속 A만 실행하게 되므로 A가 B, D 보다 2배의 CPU 시간을 독접하게 된다.

• Q0에서 A마저 종료되었을 때 Q0은 완전히 비게 되고, CPU0은 할 일이 없어서 idle 상태가 된다. 
• 반면, CPU1은 여전히 B, D를 처리 중이기 때문에 부하 불균형이 발생하게 되는 것이다.

• 해결방안
  • 이주(migration)를 해주면 된다. 운영체제가 작업을 다른 큐로 옮겨서 균형을 맞추는 것이다.
  • Q0가 비었을 때 Q1에서 B나 D를 CPU0 쪽으로 옮긴다.

• 까다로운 상황
  • 만약에 CPU0은 A만 처리하고 CPU1은 B와 D를 번갈아 처리하고 있었다면 어떻게 될까.
  • 균형을 맞추기 위해 작업을 지속적으로 바꿔가며 실행해야 한다. 결과적으로 이주가 잦아지면서 오버헤드가 증가하게 된다.