[OSTEP 가상화(virtualization)]Chapter 10 멀티프로세서 스케줄링

 

지금까지 우리는 단일 프로세스 스케줄링에 대해 알아보았다.

그러나 시대가 변하게 되면서 이 원칙들을 여러 CPU 환경에서 동작하도록 바꿔야할 필요성이 대두되었다.

여러 CPU에 작업을 어떻게 스케줄 해야 하는가?
운영체제는 어떻게 작업을 여러 CPU에 스케줄 하는가?
어떤 새로운 문제가 등장하는가?
예전 기술을 적용할 것인가 아니면 새로운 아이디어가 필요한가

📝13.1 배경 : 멸티 프로세스 구조

멀티프로세서 스케줄링을 이해하기 위해 단일 CPU 하드웨어와 멀티 CPU 하드웨어의 근복적인 차이의 이해가 필요하다.

하드웨어 캐시 사용 방식의 차이

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

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

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

 

멀티 프로세서 시스템의 캐시는 훨씬 복잡하다. 

예를 들어, CPU 1에서 실행 중인 프로그램이 주소 A를 읽는다고 가정하자.

1. CPU 1에서 실행 중인 프로그램이 주소 A를 읽는다.
2. CPU 1의 캐시에 데이터가 존재하지 않기 때문에 메인 메모리로부터 값을 가져온다.
3. 프로그램은 주소 A의 값을 변경한다. (변경은 캐시에 존재하는 값만 갱신한다.)
4. 운영체제가 CPU 2로 이동하기로 결정한다.
5. 프로그램이 다시 주소 A의 값을 읽으려고 한다.
6. CPU 2의 캐시에는 데이터가 존재하지 않으므로 메인 메모리로부터 값을 가져온다.
7. 변경되기 전 주소 A의 값을 가져오게 된다.

 

이러한 것처럼 캐시 일관성 문제가 발생한다.

이렇게 메모리와 캐시 사이의 정합성이 맞지 않는다. 즉 동기화가 필요하다는 것이다..

기본적인 해결책은 하드웨어에 의해 제공된다.  하드웨어에서 메모리 주소를 계속 감시하는 것이다.

특히, 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 항상 공유되도록 한다. 버스 기반 시스템에서는 버스 스누핑이라는 오래된 기법을 사용한다. 

 

📝13.2 동기화를 잊지 마시오

일관성 유지에 대한 모든 일을 캐시가 담당한다면, 프로그램 또는 운영체제 자신은 공유 데이터를 접근할 때 걱정할 필요가 있을까?

정답은 예이고 병행성 부분에서의 문제이다. 

 

CPU들이 동일한 데이터 또는 구조체에 접근할 때, 올바른 연산 결과를 보장하기 위해 락과 같은 상호 배제를 보장하는 도익화 기법을 많이 사용한다. 

 

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

멀티프로세서 캐시 스케줄러에서의 마지막 문제점은 캐시 친화성이다. 

간단한 개념으로 CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB에 상당한 양의 상태 정보를 올려 놓게 된다. 다음 번에 프로세스가 실행될 때 동일한 CPU에서 실행되는 것이 유리할 것이다.

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

📝13.4 단일 큐 스케줄링

가장 기본적인 방식은 단일 프로세스 스케줄링의 기본 프레임워크를 그대로 사용하는 것이다. 이러한 방식을 단일 큐 멀티프로세서 스케줄링(SQMS)라고 부른다.

장점은 단순함이다. 기존 정책을 다수 CPU에서 동작하도록 하는 데는 많은 변경이 필요하지 않다. CPU가 2개면 작업을 두 개 선택하면 된다.

 

그러나 명확한 단점이 있는데 

확장성(scalability) 결여

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

불행히도 락은 성능을 크게 저하 시키며 동시성을 매우 줄인다. 

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

캐시 친화성의 문제

예를 들어 5개의 프로세스가 있다고 생각하자 캐

 

 CPU는 공유 큐에서 다음 작업을 선택하기 때문에 각 작업은 CPU를 옮겨 다니게 된다.

그러나 우리는 캐시 친화성을 배웠기에 가능 한 한 프로세스가 동일한 CPU에서 재실행되는 것이 좋다는 것을 알고 있다.

그래서 SQMS도 이것을 시도한다.

📝13.5 멀티 큐 스케줄링

단일 큐 스케줄러의 문제 때문에 일부 시스템은 멀티 큐 즉 CPU마다 작업 큐를 따로 둔다. 이 방식을 멀티 큐 멀티프로세스 스케줄링(MQMS)라고 부른다.

 

MQMS에서 기본적인 스케줄링 프레임워크는 여러 개의 스케줄링 큐로 구성되며 각 큐는 라운드 로빈 같은 특정 스케줄링 규칙을 따른다. 예를 들어 2개의 CPU가 있다고 가정하자.

큐 스케줄링 정책에 따라 각 CPU는 현재 2개씩 작업을 가진다. 

이 경우 라운드 로빈으로 스케줄을 생성해보자

 

MQMS는 SQMS보다 명확하게 확장성이 좋다. CPU 개수가 증가할수록, 큐의 개수가 증가하므로 락과 캐시 경합은 더 이상 문제가 되지 않는다. 

또한 MQMS는 본질적으로 캐시 친화적이다. 

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

 

하지만 새로운 문제점이 생긴다.

멀티 큐 기반 방식의 근본적인 문제점인 워크로드의 불균형이다.

 

예시를 보자 C 작업 없이 Q0에 A만 있다고 가정해보자 

여기서 알 수 있듯이, A가 B,D보다 2배의 CPU를 차지한다. 여기서 A가 종료되면 더 상황이 심각해진다.

딱봐도 좋은 방법이 아니다. 효율적이기 위해서는 B나 D가 CPU0에서 진행되는게 효율적일 것이다.

 

이 기초 아이디어가 바로 이주라고 한다. 작업을 이리저리 이동시키는 것이다. 

이러한 방법을 통해 워크로드의 균형을 달성할 수 있다. 예시를 보자

이 경우 B나 D를 CPU 0으로 이동시키면 된다.

이 경우는 여러번 이동시켜야 균형을 할 수 있을 것이다. 

 

그런데 이렇게 보면 드는 생각이 있을 것이다.

이거 자주 바꿔도 되는건가?

 

이주는 작업 훔치기라는 기술을 사용한다. 작업 훔치기는 작업의 개수가 낮은 큐가 가끔 다른 큐의 작업의 수를 검사한다.

검사를 통해 작업을 가져오는 것이다.

이 방법은의 문제는 큐를 너무 자주 검사하면 오버헤드가 너무 높아진다는 것이다. 

 

📝요약

📝 13.1 배경: 멀티프로세스 구조

• 단일 CPU와 멀티 CPU 하드웨어의 근본적인 차이는 캐시 사용 방식에서 드러난다.
• 캐시 지역성
  • 시간 지역성: 한 번 접근한 데이터는 가까운 미래에 다시 접근될 가능성이 높다.
  • 공간 지역성: 특정 주소 데이터를 접근하면 인접 데이터도 접근 가능성이 높다.
• 멀티프로세서 캐시 문제
  • 캐시 일관성 문제 발생: 데이터가 CPU 간 이동 시 변경된 데이터가 반영되지 않을 수 있음.
  • 해결책: 하드웨어 기반 동기화(예: 버스 스누핑).

📝 13.2 동기화를 잊지 마시오

• 캐시 일관성을 유지해도 병행성 문제는 여전함.
• 다수 CPU에서 공유 데이터 접근 시 락(lock) 등 동기화 기법 필요.

---

📝 13.3 캐시 친화성 문제

• CPU 캐시와 TLB에 상태 정보를 올린 프로세스는 같은 CPU에서 재실행되는 것이 유리하다.
• 이를 고려하지 않으면 성능 저하 발생.

---

📝 13.4 단일 큐 스케줄링 (SQMS)

• 단일 큐로 작업 스케줄링, 단순함이 장점.
• 단점
  • 확장성 부족: 락 경쟁으로 성능 저하.
  • 캐시 친화성 저하: 작업이 여러 CPU로 이동하며 캐시 재사용 불가.

---

📝 13.5 멀티 큐 스케줄링 (MQMS)

• 각 CPU에 개별 큐를 두는 방식.
• 장점
  • 확장성 우수: 락 경합 감소.
  • 캐시 친화적: 작업이 같은 CPU에서 실행되며 캐시 재사용 가능.
• 단점
  • 워크로드 불균형: 작업이 특정 CPU에 몰리면 효율 저하.
  • 해결책: 작업 이주(work stealing)
    • 작업 수가 적은 큐가 다른 큐의 작업을 가져옴.
    • 너무 자주 검사하면 오버헤드 증가.