[CPU 스케줄링 #3] 멀티 프로세서 SQMS, MQMS

배경 : 멀티 프로세서 구조

• 단일 CPU 하드웨어와 멀티 CPU 하드웨어의 근본적인 차이에 대한 이해가 필요
  • 다수의 프로세서 간에 데이터의 공유
  • 하드웨어 캐시의 사용 방식
• 단일 CPU 시스템에는 하드웨어 캐시 계층이 존재한다.
  • 자주 사용 되는 데이터의 복사본을 저장하는 작고 빠른 메모리
  • 프로그램이 처음 이 load 명령어를 실행할 때, 데이터가 메인 메모리에 존재하므로 데이터를 가져오는 데 긴 시간이 소모된다
  • 데이터가 다시 사용될 것으로 예상한 프로세서는 읽은 데이터의 복사본을 CPU 캐시에 저장한다.
  • 프로그램이 나중에 다시 같은 데이터를 가져오려고 하면, CPU는 우선 해당 데이터가 캐시에 존재하는지 검사한다.
  • 캐시에 존재하기 때문에 데이터는 훨씬 더 빨리 접근되고 프로그램은 빨리 실행된다.
• 캐시는 지역성(locality)에 기반한다.
  • 시간 지역성(temporal locality)
    • 데이터가 한번 접근되면 가까운 미래에 다시 접근되기 쉽다는 것
    • 루프에서 여러번 반복해서 접근되는 변수 또는 명령어 자체를 상상해보면 됨.
  • 공간 지역성(spatial locality)
    • 프로그램이 주소 x의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다는 것
    • 전체 배열을 차례대로 접근하는 프로그램 또는 순차적으로 실행되는 명령어들을 생각해보면 됨

• 멀티 프로세서 시스템에서 캐시를 사용하는 것은 훨씬 복잡하다.
• 하나의 시스템에 여러 프로세서가 존재하고, 하나의 공유 메인 메모리가 있을 때 어떤 일이 일어나는가 ?
  • 예를들어 CPU 1에서 실행 중인 프로그램이 주소 A를 (D 값을) 읽는다고 가정하자.
  • 데이터가 CPU 1 캐시에 존재하지 않기 때문에 시스템은 메인 메모리로부터 데이터를 가져오고 값 D를 얻는다. 그런 후 프로그램은 주소 A의 값을 변경한다. 변경은 캐시에 존재하는 값만 D’ 로 갱신한다.
  • 메모리에 데이터를 쓰는 것은 시간이 오래걸리므로 메인 메모리에 기록하는 것은 보통 나중에 한다.
  • 운영체제가 프로그램의 실행을 중단하고, CPU 2로 이동하기로 결정한다고 가정하자. 프로그램은 주소 A의 값을 다시 읽는다. CPU 2의 캐시에는 그러한 데이터가 존재하지 않고 따라서 시스템은 메인 메모리에서 데이터를 가져온다. 이떄 D’가 아니라 D를 가져온다.
  • 이러한 문제를 캐시 일관성 문제 라고 한다.
  • 이 문제의 해결에 대한 내용은 생략하고, 기본적인 해결책은 하드웨어에 의해 제공된다.
  • 하드웨어는 메모리 주소를 계속 감시하고, 항상 “제대로” 된 상황만 발생토록 시스템을 관리한다.
  • 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 항상 공유되도록 한다.
  • 버스 기반 시스템에서는 버스 스누핑(bus snooping) 이라는 기법을 사용한다.
    • 캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링 한다.
    • 캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효화 시키거나 갱신한다.

 

동기화를 잊지 마시오.

• CPU들이 동일한 데이터 또는 구조체에 접근할 때, 올바른 연산 결과를 보장하기 위해 락과 같은 상호 배제를 보장하는 동기화 기법이 많이 사용된다.
• 락-프리(lock-free) 데이터 구조 등의 다른 방식은 복잡할 뿐만 아니라 특별한 경우에만 사용된다.
• 캐시의 일관성을 보장하는 프로토콜이 존재한다 하더라도, 락이 없이는 항목의 추가나 삭제가 제대로 동작하지 않을 것이다.
• 구조체를 원자적으로 갱신하기 위해서는 락이필요하다.
• 이러한 접근 방식이 문제가 없는 것은 아니다. 특히, 성능 측면에서 문제가 있다. CPU의 개수가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느리게 된다.

 

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

• 멀티 프로세서 캐시 스케줄러의 마지막 문제점은 캐시 친화성(cache affinity)이다.
• CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB에 상당한 양의 상태 정보를 올려 놓게 된다.
• 다음 번에 프로세스가 실행될 때 동일한 CPU에서 실행되는 것이 유리하다. 해당 CPU 캐시에 일부 정보가 이미 존재할 수 있기 때문이다.
• 하드웨어의 캐시 일관성 프로토콜 덕분에 다른 CPU에서 실행되더라도 프로그램이 제대로 실행될 것이다.
• 멀티프로세서 스케줄러는 스케줄링 결정을 내릴 때 캐시 친화성을 고려해야 한다.
• 가능한 한 프로세스를 동일한 CPU에서 실행하려고 노력하는 방향으로 결정해야 한다.

단일 큐 멀티프로세서 스케줄링( Single Queue Multiprocessor Scheduling, SQMS )

• 단일 프로세서 스케줄링의 기본 프레임워크를 그대로 사용하는 가장 기본적인 방식
• 기존 정책을 다수 CPU에서 동작하는 데 많은 변경이 필요치 않기 때문에 단순하다.
  • 모든 작업이 하나의 공용 Queue에 들어간다.
  • CPU가 2개라면 실행할 작업 두 개를 선택한다.

확장성(scalability) 결여

• 스케줄러가 다수의 CPU에서 제대로 동작하기 위해서 코드에 일정 형태의 락을 삽입한다.
• 락은 SQMS 코드가 단일 큐를 접근할 때 (실행시킬 다음 작업을 찾을 때) 올바른 결과가 나오도록 한다.
• 락은 성능을 크게 저하시킬 수 있고, 시스템의 CPU 개수가 증가할 수록 더욱 그렇다.
• 단일 락에 대한 경쟁이 증가할 수록 시스템은 락에 점점 더 많은 시간을 소모하게 되고, 실제 필요한 일에 쓰는 시간은 줄어들게 된다.

캐시 친화성

• 실행할 5개의 작업이 있고, (A,B,C,D,E) 4개의 프로세서가 있다고 가정하자.
• 시간이 흐르면서 각 작업은 주어진 타임 슬라이스 동안 실행되고, 다음 작업이 선택되었다고 가정하자.

 

 

• 각 CPU는 공유 큐에서 다음 작업을 선택하기 때문에 각 작업은 CPU를 옮겨 다니게 된다.
• 캐시 친화성 관점에서 보면 잘못된 선택을 하는 것이다.
• 이 문제를 해결하기 위해 대부분의 SQMS 스케줄러는 가능한 한 프로세스가 동일한 CPU에서 재실행 될 수 있도록 시도한다.
• 특정 작업들에 대해서 캐시 친화성을 고려하여 스케줄링하고 다른 작업들은 오버헤드를 균등하게 하기 위해 여러 군데로 분산시키는 정책을 사용한다.

• A 부터 D까지의 작업은 각각 자신의 프로세서에서 실행되고 오직 E만이 하나의 프로세서에서 다른 프로세서로 이동한다. (But 이러한 기법은 구현이 복잡해 질 수 있다.)

 

멀티 큐 스케줄링 (Multi-Queue Multiprocessor Scheduling, MQMS)

• 단일 큐 스케줄러로 인한 문제 때문에 일부 시스템은 CPU 마다 큐를 하나씩 둔다.
• 각 큐는 RR 같은 특정 스케줄링 규칙을 따를 것( 어떤 스케줄링 기법이든 사용 가능)
• 작업이 시스템에 들어가면 하나의 스케줄링 큐에 배치된다.
• 배치될 큐에 결정은 적당한 방법을 따른다. ( 무작위로 할 수도 있고, 다른 큐보다 작은 수의 작업이 있는 큐로 배치될 수도 있다.)
• 각각 독립적으로 스케줄 되기 때문에 단일 큐 방식에서 보았던 정보의 공유 및 동기화 문제를 피할 수 있다.

 

• 예를들어,,
• 2개의 CPU와 A, B, C, D 네 개의 작업이 시스테에 존재한다고 가정
• CPU는 각자 하나씩의 스케줄링 큐를 가지고 있으므로 운영체제는 각 작업을 배치할 큐를 결정해야 한다.
• 다음과 같은 결정을 내렸다고 하자.

• 큐 스케줄링 정책에 따라 각 CPU는 현재 2개씩 작업을 가지고 있다. 예를 들어 라운드 로빈의 경우 다음과 같은 스케줄이 생성될 수 있다.

• MQMS 가 SQMS 에 비해 가지는 명확한 이점은 확장성이 좋다는 것이다.
• CPU 개수가 증가할수록, 큐의 개수도 증가하므로 락과 캐시 경합(cache contention) 은 더이상 문제가 되지 않는다.
• 또한, MQMS는 본질적으로 캐시 친화적이다.
• 작업이 같은 CPU에서 계속 실행되기 때문에 캐시에 저장된 내용을 재사용하는 이점을 얻게 된다.

But 새로운 문제점

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

• 앞의 예와 동일한 설정을 가정하자(4개의 작, 2개의 CPU). 그러나 그 중 하나(예, C) 가 종료 되다고 하자. 이제 다음과 같은 스케줄링 큐를 가진다.

• 각 큐에 라운드 로빈 정책을 실행한 경우, 다음과 같은 스케줄을 얻을 수 있다.

• A가 B와 D보다 2배의 CPU를 차지하고 이는 우리가 원하는 결과가 아니다. 설상가상으로 A와 C가 모두 종료하여 B와 D만 남게 된다고 가정하자. 스케줄링 큐는 다음과 같을 것이다.

• CPU 0은 유휴 상태가 된다

워크로드의 불균형 을 대처하는 방법

이주 (migration)

• 작업을 한 CPU에서 다른 CPU로 이주 시킴으로써 워크로드 균형을 달성한다,

• 다시 한 번, 하나의 CPU는 유휴 상태이고 다른 CPU는 몇몇 작을 가지고 있다고 하자.
• 운영체제는 B 또는 D 중 하나를 CPU 0로 이동시킨다. 이 한 번의 작 이주로 워크로드가 균형을 이루게 되고 모두가 행복하게 된다.

• 좀 더 까다로운 경우는 그 이전 예에서 발생한다. A는 혼자 CPU 0에 있고 B와 D 는 CPU 1에서 번갈아 실행되고 있다.
• 이 경우 한 번의 이주만으로는 문제가 해결되지 않는다.
• 해결책은 작업들을 지속적으로 이주시키는 것이다.

• A는 CPU 0에 혼자 있고 B와 D는 CPU 1에서 번갈아 실행되고 있다. 몇 번의 타임 슬라이스 후 B는 CPU 0로 이주하여 A와 경쟁한다. 그동안 D는 CPU 1에서 몇 개의 타임 슬라이스 동안 혼자 실행된다. 따라서 워크로드의 균형이 맞게 된다.

물론 가능한 많은 다른 이주 패턴이 존재한다. 이주의 필요 여부를 어떻게 결정할까?

• 작업 훔치기(work stealing)
  • 작업 훔치기에서는 작업의 개수가 낮은 (소스) 큐가 가끔 다른 (대상) 큐에 훨씬 많은 수의 작이 있는지를 검사한다.
  • 대상 큐가 소스 큐보다 더 가득 차 있다면 워크로드 균형을 맞추기 위해 소스는 대상에서 하나 이상의 작업을 가져온다.
  • 큐를 너무 자주 검사하게 되면 높은 오버헤드로 확장성에 문제가 생기게 된다.
  • 반면 다른 큐를 자주 검사하지 않으면 심각한 워크로드 불균형을 초래할 가능성이 있다. 시스템 정책 설계에 흔히 있는 일로서 적절한 값을 찾아내는 것은 마법의 영역이다.

Linux 멀티 프로세서 스케줄러

• 리눅스 커뮤니티 에서는 멀티 프로세서 스케줄러를 위한 단일화된 방식이 존재하지 않았다.
  • O(1) 스케줄러
    • 멀티 큐, 우선순위 기반 스케줄러(MLFQ와 유사), 프로세스의 우선순위를 시간에 따라 변경하여 우선순위가 가장 높은 작을 선택하여 다양한 목적을 만족시킨다
  • Completely Fair Schedular(CFS)
    • 멀티 큐, 결정론적(deteministic) 비례배분(proportional share) 방식이다(전에 논의했던 보폭 스케줄링에 가까움).
  • BFS 스케줄러
    • 단일 큐, 또한 비례배분 방식이다. 그러나 Earliest Eligible Virtual Deadline First(EEVDF)라고 알려진 더 복잡한 방식에 기반을 둔다.

요약

멀티프로세서 스케줄링의 두 가지 방식을 비교하면, 단일 큐(SQMS)는 구현과 워크로드 균형이 쉽지만 확장성과 캐시 성능이 떨어지고, 멀티 큐(MQMS)는 확장성과 캐시 성능은 좋지만 워크로드 불균형과 구현이 복잡하다. CPU 스케줄러는 작은 변경으로도 큰 영향을 미치므로, 모든 상황에 적합한 범용 스케줄러 구현은 매우 어렵다. 

번외 ) 내가 햇갈렸던 포인트

• 단일 CPU 인 상황에서 대표 스케줄링 방식이 MLFQ, FCFS, SJF, STCF, RR
  • 목적: 한 개의 CPU 자원을 얼마나 효율적으로 분배 할지
• 멀티 CPU 인 경우 스케줄링 방식이 SQMS, MQMS
  • 목적: 여러 CPU 간의 작업 균형을 유지하기 위해

 

출처 : 운영체제 아주 쉬운 세 가지 이야기