[OSTEP] Virtualization) 10. Multi-CPU Scheduling

sunjoo9912·2022년 4월 10일
0

OSTEP 운영체제

목록 보기
7/17
post-thumbnail

[OSTEP] 10. Multi-CPU Scheduling

CH 10. 멀티프로세서 스케쥴링 (고급)

  • 여러 CPU에 작업을 어떻게 스케쥴해야 하는가?

1. 배경: 멀티 프로세서 구조

  • 단일 CPU 하드웨어와 멀티 CPU하드웨어의 차이점:
    다수의 프로세서 간에 데이터 공유, 하드웨어 캐시의 사용 방식에 차이 발생

  • 단일 CPU 시스템에는 하드웨어 캐시 계층 존재
    -> 자주 접근되는 데이터를 캐시에 임시로 저장
    -> 시스템은 크고 느린 메모리를 빠른 메모리처럼 보이게 한다

  • 캐시는 지역성에 기반한다
    -> 시간 지역성(temporal locality): 데이터가 한 번 접근되면 가까운 미래에 다시 접근되기 쉽다
    -> 공간적 지역성(spatial locality): 프로그램이 주고 x의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다

캐시 일관성 문제(cache coherence)

  • 하나의 시스템에 여러 프로세서가 존재하고 하나의 공유 메인 메모리가 있는 경우
    -> 캐시 일관성 문제 발생

  • 기본적인 해결책은 하드웨어에 의해 제공된다
    -> 메모리 주소를 계속 감시하여 항상 제대로된 상황만 발생하도록
    -> 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 항상 공유되도록

버스 스누핑(bus snooping)

  • 버스 기반 시스템에서는 버스 스누핑 기법을 사용한다

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

2. 동기화를 잊지 마시오

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

  • CPU들이 동일한 데이터 또는 구조체에 접근/갱신할 때, 올바른 연산 결과를 보장하기 위해 lock과 같은 상호 배제를 보장하는 동기화 기법 사용
    (락-프리(lock-free) 데이터 구조 등의 다른 방식은 복잡함 & 특별한 경우에만 사용된다)

  • lock 사용법:
    간단한 mutex (ex. pthread_mutex_t m;)를 할당하여 루틴의 시작에 lock(&m) , 마지막에 unlock(&m) 추가한다

  • CPU의 개수가 증가할수록 동기화된 자료구조에 접근하는 연산은 매우 느리게 된다

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

  • 캐시 친화성(cache affinity)

  • CPU에서 실행될 때 프로세스는 해당 CPU 캐시와 TLB에 상당한 양의 상태 정보를 올려 놓게 됨
    -> 다음 번에 프로세스가 실행될 때 동일한 CPU에서 실행되는 것이 유리
    -> 프로세스가 매번 다른 CPU에서 실행되면 실행할 때마다 필요한 정보를 캐시에 탑재해야 함

4. 단일 큐 스케쥴링

  • 단일 큐 멀티프로세서 스케쥴링 (single queue multi processor scheduling, SQMS)
    -> 단일 프로세서 그케쥴링의 기본 프레임 워크 그대로 사용
    -> CPU가 2개라면 실행할 작업 두 개를 선택한다.

확장성(scalability) 결여

  • 스케쥴러가 다수의 CPU에서 제대로 동작하게 하기 위해 코드에 일정 형태의 락 삽입
    -> 락은 시스템의 CPU 개수가 증가할수록 성능을 크게 저하시킬 수 있다
    -> 동기화 오버헤드

캐시 친화성 문제

  • 실행할 5개의 작업(A, B, C, D, E)이 있고 4개의 프로세서가 있는 경우

캐시 친화성 문제 해결

  • 대부분의 SQMS 스케쥴러는 가능한 프로세스가 동일한 CPU에서 실행될 수 있도록 함
    -> 특정 작업들(ex. A, B, C, D)에 대하여 캐시 친화성을 고려하여 스케쥴링 & 다른 작업들(ex. E)은 오버헤드를 균등하게 하기 위해 여러 군데로 분산시키는 정책 사용

  • 다음에는 다른 작업(ex. E가 아닌 작업)을 이동시켜 일종의 친화성에 대한 형평성도 추구할 수 있다

5. 멀티 큐 스케쥴링

  • 일부 시스템은 멀티 큐, 예를 들어 CPU마다 큐를 하나씩 둔다

  • 멀티 큐 멀티프로세서 스케쥴링(multi-queue multiprocessor scheduling, MQMS)
    -> 기본적인 스케쥴링 프레임워크는 여러 개의 스케쥴링 큐로 구성
    -> 각 큐는 RR같은 특정 스케쥴링 규칙을 따른다

  • 작업이 시스템에 들어가면 하나의 스케쥴링 큐에 배치된다.
    -> 배치된 큐의 결정은 적당한 방법을 따른다 (ex. 무작위, 다른 큐보다 작은 수의 작업이 있는 큐로 배치, ...)
    -> 그 후는 각각이 독립적으로 스케쥴되기 때문에 공유 및 동기화의 문제를 피할 수 있다

예.

  • 2개의 CPU와 4개의 작업(A, B, C, D)
  • CPU는 각자 하나씩의 스케쥴링 큐를 가짐

  • 확장성 좋음
    -> CPU 개수가 증가할수록 큐의 개수도 증가
    -> 락과 캐시 경합(cache contention) 문제 X
    (cache contention: when two or more CPUs alternately and repeatedly update the same cache line)

  • 친화성 좋음
    -> 작업이 같은 CPU에서 계속 사용됨
    -> 캐시에 저장된 내용을 재사용하는 이점

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

  • 2개의 CPU와 4개의 작업(A, B, C, D) 중 하나(예. C)가 종료된 경우
    -> A가 B와 D보다 2배의 CPU를 차지하게 된다

  • 위 상태에서 작업 A도 종료된 경우
    -> CPU 하나는 유휴 상태가 된다

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

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

  • 예. B또는 D 중 하나를 다른 CPU로 이동시킨다
    -> 한 번의 작업 이주로 워크로드가 균형을 이루게 됨

  • 예. 이 경우 한 번의 이주만으로는 문제가 해결되지 않는다
    -> 작업들을 지속적으로 이주시켜야

이주의 필요 여부를 어떻게 결정할까?

  • 작업 훔치기(work stealing): 작업 개수가 낮은 (소스)큐가 가끔 다른 (대상) 큐에 훨씬 많은 수의 작업이 있는지를 검사
    -> 대상 큐가 소스 큐보다 더 가득 차 있다면 워크로드 균형을 맞추기 위해 소스는 대상에서 하나 이상의 작업을 가져온다

  • 큐를 너무 자주 검사하게 되면 -> 높은 오버헤드 -> 확장성 문제

  • 큐를 자주 검사하지 않으면 -> 심각한 워크로드 불균형 문제

6. Linux 멀티프로세서 스케쥴러

  • Linux 커뮤니티에서는 멀티프로세서 스케쥴로를 위한 단일화된 방식 존재하지 않았음
  1. O(1) 스케쥴러
  • 멀티 큐 사용
  • 우선순위 기반 스케쥴러(MLFQ와 유사)
    -> 프로세스의 우선순의를 시간에 따라 변경하여 우선순위가 가장 높은 작업 선택
    -> 상호작용 가장 우선시함
  1. Completely Fair Scheduler(CFS)
  • 멀티 큐 사용
  • 결정론적 비례배분 방식 (보폭 스케쥴링과 유사)
  1. BF 스케쥴러(BFS)
  • 단일 큐 사용
  • 비례배분 방식: Earliest Eligible Virtual Deadline First (EEVDF) 방식에 기반

7. 요약

  • 단일 큐 방식(SQMS)
    -> 정점: 구현 용이, 워크로드 균형 맞추기 용이
    -> 단점: 많은 개수의 프로세서레 대한 확장성과 캐시 친화성 bad

  • 멀티 큐 방식(MQMS):
    -> 장점: 확장성 좋음, 캐시 친화성 좋음
    -> 단점: 워크로드 불균형의 문제, 구현 복잡

profile
✧°₊·♡∗ˈ‧₊

0개의 댓글