[OSTEP-10] Multi-CPU Scheduling

배경

• 고사양 컴퓨터에만 존재하던 멀티 프로세서 시스템은 일반적이게 되었으며 심지어 모바일 장치에도 사용되고 있음
• 여러개의 CPU 코어가 하나의 칩에 내장된 멀티코어 프로세서가 대중화의 근본 원인임
• 다중 CPU 시대가 오면서 많은 문제가 발생했는데 더 많은 CPU 를 추가해도 빨리 실행되지 않는다는 점이였음
• 이 문제를 해결하기위해 응용 프로그램을 병렬로 실행되도록 다시 작성함

 

여러 CPU 에 작업을 어떻게 스케줄 해야 하는가.

운영체제는 어떻게 작업을 여러 CPU 에 스케줄 해야하는가? 어떤 새로운 문제가 등장하는가?

배경: 멀티 프로세서 구조

• 멀티 프로세서 스케줄링에 대한 문제점을 이해하기 위해서는 멀티 CPU 하드웨어와 단일 CPU 하드웨어의 근본적인 차이에 대해 알고 있어야 함
• 다수의 프로세서간의 데이터 공유, 하드웨어 캐시의 사용 방식에서의 차이가 발생함
• 단일 CPU 시스템에는 하드웨어 캐시 계층이 존재함, 메인 메모리에서 자주 사용되는 데이터의 복사본을 저장하는 작고 빠른 메모리임

캐시

• 캐시는 지역성 에 기반함, 지역성은 시간 지역성(temporal locality) 와 공간 지역성(spatial locality) 의 두 종류가 있음
• 시간적 지역성은 데이터가 한번 접근되면 가까운 미래에 다시 접근이 된다는 가정
• 공간 지역성은 주소 X의 데이터를 접근하면 X 주변의 데이터가 접근되기 쉽다는 가정

하나의 시스템에 여러 프로세서가 존재하고 공유 메인 메모리가 있을 경우 (캐시 일관성 문제)

 

• CPU 1이 주소 A 에 존재하는 D 값을 읽고 주소 A 의 값을 D`로 변경 (메인 메모리에는 반영 😵)
• CPU2 가 주소 A 존재하는 D 값을 읽을 경우 데이터 불일치 문제 발생
• 하드웨어가 메모리 주소를 계속 감시하고 항상 “제대로” 된 상황만 발생토록 시스템을 관리함
  • 여러개의 프로세스들이 하나의 메모리에 갱신할때는 항상 공유되도록 함
• 버스 기반 시스템에서는 버스 스누핑(bus snooping) 이라는 오래된 기법을 사용함
  • 캐시 데이터에 대한 변경을 관찰하다, 변경이 발생하면 복사본을 무효화 시키거나 갱신 함
  • write-back 캐시는 메인 메모리에 쓰기 연산이 지연되기때문에 캐시 일관성 유지문제를 훨씬 복잡하게 만듬

동기화를 잊지말기

• 일관성 유지에 대한 모든 일을 캐시가 담당한다고 해서 공유 데이터를 접근할 때 걱정할 필요가 없는건 아님
• CPU들이 동일한 데이터 또는 구조체에 접근할때, 올바른 연산 결과를 보장하기위해 상호 배제를 보장하는 동기화 기법이 많이 사용됨
• 락을 사용하여 올바르게 동작하게 만들 수 있지만 이러한 접근 방식은 성능 측면에서 문제가 있고, CPU 의 개수가 증가할 수록 동기화된 자료구조에 접근하는 연산은 매우느림

캐시 친화성

• CPU 에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB(Translation Lookaside Buffer)(Page Table 캐시) 에 상당한 양의 상태정보를 올려놓게 됨
• 하드웨어의 캐시 일관성 프로토콜 덕분에 다른 CPU 에서 실행되더라도 프로그램이 제대로 실행될 것임
  • 가능한 한 프로세스를 동일한 CPU에서 실행하려고 노력하는 방향으로 결정해야함

단일 큐 스케줄링

• 가장 기본적인 방식은 단일 프로세서 스케줄링의 기본 프레임워크를 그대로 사용하는 것

문제점

1. 동기화 문제로 인한 락으로 인한 성능 저하 (CPU 개수가 많아질수록 심각해짐)
2. 캐시 친화성 문제. 실행할 5개의 작업이 있고 4개의 프로세스가 있다고 가정할때 각 작업이 여러 프로세스를 거쳐서 실행될 수 있음
   1. 대부분의 SQMS 스케줄러는 가능한 한 프로세스가 동일한 CPU 에서 재실행 될 수 있도록 시도함. 구체적으로 특정 작업들에 대해서 캐시 친화성을 고려하여 스케줄링하고 다른 작업들은 오버헤드를 균등하게 하기 위해 여러 군데로 분산시키는 정책을 사용함.

 

 

멀티 큐 스케줄링 (multi-queue multiprocessor scheduling, MQMS)

• 단일 큐 스케줄러로 인한 문제 때문에 일부 시스템은 멀티 큐, 예를 들어 CPU 마다 큐를 하나씩 둠
• SQMS 에 비해 가지는 명확한 이점은 캐시 친화성과 동기화 문제가 어느정도 해결됨
• 하지만 워크로드의 불균형 문제가 생김 (load imbalance)
  • 특정 프로세서 큐의 작업이 먼저 빨리 종료될 경우를 상상해보자

 

• 이때 A 작업은 B와 D 작업보다 CPU를 2배이상 차지하고있음

워크로드 불균형 문제 해결방법

• 작업을 이리저리로 migration 시키는 것

 

• 위와 같은 경우는 걍 B와 D 둘중하나 Q0 큐로 이동시키면됨

 

• 이런 경우가 어려움, 이때 한번의 이주만으로는 문제가 해결되지않음. 그래서 잦은 이주를 통한 워크로드의 균형을 맞춰야하는데 이때 어느정도의 캐시 친화성문제가 생길 수 있을 것 같음
  • 어려운 부분은 이주 필요여부를 결정하는 방식임
• 이는 작업 훔치기를 통해 어느정도 해결이 가능하지만 큐를 너무 자주검사하게 되면 오버헤드로 확장성에 문제가 생기게 됨
  • 확장성이 멀티 큐 스케줄링의 가장 중요한 목적