7. Multiprocessor Scheduling

1. Multiprocessor Scheduling

(1) 멀티 코어 프로세서의 발생은 멀티프로세서 스케줄링의 확산의 원인

  - Multicore : 여러 개의 cpu 코어는 하나의 칩으로 감싸짐

 

(2) 더 많은 cpu를 추가하는 것은 싱글 애플리케이션을 빠르게 만들 수 없음 -> 스레드를 사용하여 병렬 상태에서 수행하도록 애플리케이션을 다시 작성

**core의 개수가 늘어나는 이유 : cpu의 속도를 빠르게 하기 위해선 clock speed를 높여야됨 -> cpu에서 열이 많이 나고 power wall problem

=> core의 개수를 늘리거나 multi-threading

 

 

2. Background : Single CPU with cache

 

(1) cache

  - 작고 빠른 메모리

  - 메인 메모리에서 발견된 popular data의 복사본을 가짐

  - 시간적, 공간적 locality를 사용

 

(2) 메인 메모리

  - 모든 데이터를 가짐

  - 메인 메모리에 대한 access는 캐시보다 느림

 

=> 데이터를 캐시에 보관하면, 시스템은 느린 메모리가 빠르게 보이도록 할 수 있음

** 캐시 : 캐시에서 데이터를 가져오는 것은 메인 메모리에서 가져오는 것보다 빠름, 메인 메모리의 일부분을 가져와서 저장, 누구를 캐시에 갖다 넣는지에 따라 성능이 결정됨

캐시를 만드는 것은 무엇을 갖다 놓는게 좋을지 생각하는게 중요

 

캐시는 temporal, spartial locality를 기반으로 만들어졌고 덕분에 성능이 좋아짐

캐시 메모리는 cpu 안에 존재하고 메인 메모리에서 copy해서 가져옴

 

 

3. Background : Cache Coherence

(1) 여러 캐시에 저장된 공유된 리소스 데이터의 일관성

  0. 메모리를 공유하는 캐시를 가진 2개의 cpu

  1. cpu0은 address 1의 데이터를 읽음

  2. D는 업데이트 되고, cpu1이 스케줄링 됨

 

3. cpu1은 address 1의 값을 다시 읽음

 

=> cpu1은 올바른 값인 D' 대신에 오래된 값인 D를 가져옴

 

(2) Bus snooping

  - 각 캐시는 버스를 관찰하면서 메모리 업데이트에 집중함

  - cpu가 캐시가 보관하고 있는 데이터에 대한 업데이트를 볼 때, 변경사항을 확인하고 복사본을 무효화(invalidate)하거나 업데이트(update)함

 

** cpu0으로 D를 가져와서 업데이트 -> D'

캐시는 크게 write-through cache, write-back cache

Write-through cache : 캐시에 write하면 write한 데이터가 메인 메모리에서 업데이트

 -> 위의 그림에선 메인 메모리에서 업데이트 되고 있지 않음, 버스를 타고 메인 메모리로 가야하기 때문에 성능에 오버헤드 발생

  : 매번 업데이트 할 때마다 밑에 씀, bus tracking이 더 많음

 

Write-back cache : cpu1이 돌기 시작하면, 캐시에 아무것도 없기 때문에 캐시에 리스가 발생, 메인 메모리에서 가져와야함, 결과적으로 메인 메모리에서 똑같은 데이터를 가져오는데 cpu0, 1에선 다른 데이터를 갖게 됨 >> cache coherence

자기만 업데이트, 오버헤드가 적어서 더유용함, invalidate하는게 오버헤드가 적음

write-back + invalidation으로 캐시 디자인

캐시 컨트롤러 안에 coherence를 해결하기 위한 소프트웨어가 있음 -> 오버헤드가 큼

 

버스 : 어떤 캐시에 뭐가 업데이트 되었는지 알고 있어야됨

 

 

4. Don't forget Synchronization

(1) cpu를 통해 공유된 데이터에 접근할 때, 정확성을 보장하기 위해 mutual exclusion primitives를 사용해야함

 

//Simple List Delete Code

pthread_mutex_t m;
typedef stuct _Node_t {
	int value;
    struct _Node_t *next;
} Node_t;

int List_Pop() {
	lock(&m);
    Node_t *tmp = head;
    int value = head->value;
    head = head->next;
    free(tmp);
    unlock(&m);
    return value;
}

뮤텍스를 lock하고 리스트의 헤더와 헤더 안의 값을 저장함

헤더는 헤더 다음을 가리키게 설정하고 처음 헤더를 넣었던 tmp를 free

lock했던 뮤텍스를 unlock

 

 

5. Asymmetric vs. Symmetric Multiprocessing Scheduling

(1) cpu 스케줄링은 cpu가 여러 개일 때 더 복잡

(2) 프로세서가 동일하다고 가정 -> homogeneous (단순함을 위한 기능 측면에서)

(3) 2가지 접근법

  - Asymmetric multiprocessing : 오직 하나의 프로세서만 시스템 데이터 구조체에 접근할 수 있으며 데이터 공유의 필요성을 완화

 - Symmetric multiprocessing (SMP) : 각 프로세서는 글로벌하게 공유된 큐나 여러개의 private 큐에 접근하고 업데이트해서 self-scheduling을 함

 

**Homogeneous : cpu는 동일

AMP : 각 cpu가 하는 일들이 다름, 하나의 cpu가 ready queue에서 가져와서 다른 cpu에게 나눠줌

SMP : 모든 프로세스가 동일한 일을 함, cpu가 각각 ready queue에서 가져와서 동일하게 동작, 큐의 형태는 글로벌하게 하나만 가지거나 private하게 하나씩 따로 가짐, cpu가 symmetric하게 연결

 

 

 

6. Single Queue Multiprocessor Scheduling (SQMS)

(1) 스케줄링이 필요한 모든 작업을 하나의 큐에 넣음

  - 각 cpu는 글로벌하게 공유된 큐로부터 다음 작업을 단순하게 고름

 - SQMS는 locking의 형식이 필요함 -> scalability 부족

 - 작업들이 대기열에서 너무 많이 이동함

 

**큐가 1개 : single queue ~

cpu의 개수가 많으면 큐에 access하게 위해 lock, unlock을 많이 하기 때문에 확장성에 문제가 생김

돌아가는 프로세스가 어떤 큐에 들어갈 지 예측할 수 없고 캐시의 내용이 변경되거나 떨어지므로 성능이 떨어짐

 

 

 

7. Cache affinity (Processor Affinity)

(1) 프로세스가 특정 cpu에서 수행중일 때 캐시 메모리에서 어떤 일이 일어날지에 대해 생각해보자

  - 프로세스는 cpu의 캐시에 상당한 양의 state를 구축

  - 다음에 프로세스가 실행될 때, 해당 state의 일부가 이미 cpu의 캐시 안에 있는 경우 더 빠르게 수행

  - 시스템이 프로세스 이동을 허용하면, cpu의 캐시 메모리의 컨텐츠는 쓸모가 없게 되고 해당 cpu는 컨텐츠를 다시 채워야 함

  - 동일 cpu에서 수행하는 프로세스를 가진 cache (processor) affinity가 필요함

  - 2가지 가능성

   : soft affinity - 동일 cpu에서 수행중인 프로세스를 보관하려고 노력하지만 보장할 수 없음 (이주할 가능성이 있음)

   : hard affinity - 이주를 금지함 -> 프로세스가 이주하지 못하게 하는 시스템 콜 제공 (리눅스)

  - 멀티프로세서 스케줄러는 스케줄링 결정을 내릴 때 cache affinity를 고려해야함

 

** 캐시의 내용이 계속해서 없어지면 문제가 생김

캐시를 최대한으로 이용하려면: 안움직이게 하는게 제일 좋음 -> 프로세서들이 여러 cpu에 들어가지 않기 때문에 큐를 최대한으로 이용할 수 있음 -> affinity : 특정 프로세스에 계속 돌자고하는 친화력을 갖게됨

프로세스를 만들 때 affinity를 지정해서 특정 cpu에서 돌도록 요청할 수 있음

 

(2) 예시

- 가능한 최대한으로 affinity를 보존

  : A - D의 작업은 프로세서 간 이동할 수 없음

  : 오직 E만 cpu 사이에서 이동 가능

 

- 이런 구현은 복잡함

 

 

 

8. Multi-Queue Multiprocessor Scheduling (MQMS)

(1) MQMS는 여러 개의 스케줄링 큐로 구성됨

  - 각 큐는 특정 스케줄링 원칙을 따름

  - 작업이 시스템으로 들어갈 때, 특정 하나의 스케줄링 큐에 배치됨

  - 정보 공유와 synchronization의 문제를 피함

 

(2) RR을 사용하여 시스템은 스케줄을 생성 (아래예시)

** 새로운 job이 들어왔을 때는 어떤 큐에 들어갈 지 미리 정해짐

 

- MQMS는 더 많은 scalability와 cache affinity를 제공

 

 

(3) Load Imbalance Issue of MQMS

 - Q0의 C가 끝난 후:

A는 B와 D보다 2배의 cpu를 얻게 됨

 

- Q0의 A가 끝난 후:

cpu0는 idle 상태로 남겨짐

 

 

9. Load Balancing Algorithm in MQMS

(1) Load balancing은 모든 프로세서를 통해 균등하게 분배된 workload를 보관하려고 함

(2) Load balancing은 일반적으로 각 프로세서에 private queue(multi scheduling queues)를 가지는 시스템에서만 필요함

(3) SMP를 지원하는 대부분의 운영체제는 프로세스의 private queue를 가짐

(4) 2가지 접근

  - Push migration : 특정 작업은 주기적으로 각 프로세서에 load를 확인하고 균등하게 load를 분배

  - Pull migration : idle 프로세서는 사용중인 프로세서로부터 대기중인 작업을 가져옴

(5) 위의 접근은 동시에 구현될 수 있음

 

**push migration - os의 프로세스가 주기적으로 각 큐에 있는 로드를 체크하고 그 중 몇 개의 프로세스가 없으면 다른 것에서 가져와서 넣어줌

pull migration - 각자의 cpu에서 코드가 돌면서 나의 큐를 체크하다가 내 큐의 job이 특정 개수보다 작아지면 다른 것에서 가져옴

 

(6) 예시

 

simple case - Q0는 Q1에서 가져옴

tricky case - cpu1의 B를 cpu0로 이주하고, A를 cpu1로 가져옴

 

 

 

10. Work Stealing

(1) 큐 간의 job을 이동

  - 구현

     : 작업이 적은 소스 큐가 선택됨

     : 소스 큐는 때때로 다른 타겟 큐를 엿봄

     : 만약 타겟인 큐가 소스 큐보다 더 차있으면, 소스는 타겟으로부터 하나 이상의 job을 steal

 - 단점 : 높은 오버헤드와 scaling에서 문제가 발생