전공/운영체제

10. Multiprocessor Scheduling(Advanced)

nongdamgom 2024. 1. 1. 22:09

 

요즘 대세는 multiprocessor에서 multicore로 변하고 있다.

 

 Multi - processor ?
  • CPU 자체가 여러개 
  • 하지만 CPU를 늘리는 것에 물리적으로 한계가 존재함 (크기, 쿨링 문제 등)

 

Multi - core ?
  • 하나의 CPU가 여러개의 core를 가지고 있음
  • 하지만 어차피 single core 용으로 만들어진 프로그램이 많아서, multi - core의 장점이 사라짐

=> 이 문제를 해결하기 위해 threads를 사용

 

 

Threads ?
  • thread끼리 code, data, heap(memory)를 공유함 
  • thread마다 program counter 존재 
  • => 어떤 A라는 프로세스가 여러개의 thread를 사용하며 각 pc를 각 core에 연결해서 multi-core로 돌릴 수 있게 함

 

** 지금부터 CPU == core로 간주함

 

 

Single CPU wiht cache

  • 바로 전에 한 학기동안 컴구에서 cache에 대해 질리게 배웠으므로 간단하게 넘어감
  • temporal locality vs spatial locality 
  • 반복문 vs 배열 생각하면 될 듯 (했던거 또 하기 vs 접근 했던 곳 근처로 연달아 접근하기)

 

 

Cache coherence 

  • 여러 cpu(core)를 사용할 때, 각 cache에서 뭔가를 작성하면, memory와 동기화가 안되어 다른 cpu와 값 충돌이 일어나는 문제 
  • 동기화 방법(컴구 글에 자세히 나와있다)
  • write-back : 기다렸다가 나중에 memory로 옮김
  • wirte-through : cache에서 업데이트 될 때마다 바로바로 memory로 옮김 

 

Cache coherence solution

  • Bus snooping ( write - through의 해결 방법)

=> CPU가 cache를 계속 관찰하다가, 한 CPU에서 바뀐걸 알아챘을 때, 그 값을 update하거나 invaildate 함

 

 

 

 

Don't forget synchronization

typedef struct __Node_t{
	int value;
    sturct __Node_t *next;
} Node_t;

int List_Pop(){
	Node_t *tmp = head;
    int value = head -> value;
    head = head -> next;
    free(tmp);  // 여기서 동기화 문제 발생
    return value;
}

 

  • 두개의 core가 동시에 List_Pop 함수를 실행한다고 생각해보자
  • multi-core는 code, data, heap은 공유하지만, 각 core의 stack(kernel stack)은 분리되어 있음
  • 만약 core 0 에서 free를 먼저 했는데, core1에서 free를 또 해버리면 double free error 발생 

 

Solution

pthread_mtuex_t m;
typedef struct __Node_t{
	int value;
    sturct __Node_t *next;
} Node_t;

int List_Pop(){
    lock(&m)  // unlock 될 때까지, 딱 하나의 core만 사용할 수 있음 
    Node_t *tmp = head;
    int value = head -> value;
    head = head -> next;
    free(tmp);  // 여기서 동기화 문제 발생
    unlock(&m)
    return value;
}

 

  • lock(&m) ~ unlock(&m) 동안 한 번에 하나의 core 또는 process만 접근 허용 
  • => 다른 접근자는 대기해야 함
  • 이 영역을 critical section 이라고 함.

 

 

Cache Affinity

  • multi - core를 사용한다고 무작정 좋은점만 있는 것은 x 
  • 한 process의 실행 core를 계속 옮기면, cache의 장점을 활용할 수 없게 됨 
  • 즉 cache affinity ==  cache 내에 접근 가능 데이터를 많이 쌓아놔서 빠르게 cache 이용 가능 

 

 

Single queue Multiprocessor Scheduling(SQMS)

 

  • 모든 job들을 single ready queue에 넣고 동작 
  • 구현이 쉬운 장점 존재
  • 하지만 critical section을 기다리는 동안, 시간 낭비가 심함 
  • 병렬이 아닌 직렬적으로 실행되기 때문에, scalability가 떨어짐 
  • cache affinity => 있을수도 있고 없을수도 있음

 

Scheduling Example with Cache affinity

 

  • cache affinity를 가장 먼저 생각해서 scheduling
  • 구현하기 어렵다.

 

 

Multi-queue Multi-processor Scheduling(MQMS)

  • single queue가 아닌 multi queue 사용 
  • => 동기화 매커니즘이 필요 없을거라고 생각했으나, 또 생김 

 

MQMS Example

 

  • RR 방식을 사용하여 각 queue를 각 cpu로 분배 
  • more scalability, cache affinity

 

Load Imbalance issue of MQMS

  • 위 처럼 짝수개의 경우에는 문제가 안생기나, 홀수개의 job일 경우 fairness 문제가 생긴다
  • 또한 하나의 ready queue에 job이 몰려있는 경우, utilization이 떨어진다.

 

How to deal with load imbalance?

  • OS가 migration을 통해 불균형을 해결함

  • 주기적으로 process가 많은 쪽에서, 적은 쪽으로 migration을 해준다.

 

 

Work Stealing

  • job을 queue간에 migration 하는 과정 
  • migration이 너무 잦으면 high overhead 문제점 발생 
  • lack of scalability 

=> MQMS는 각 프로세서 마다 queue를 가지고 있기 때문에 원래는 scalability 문제가 발생하지 않았는데, load imblance 문제가 발생하면서 work stealing같은 기법이 생기고, work stealing은 결국 서로다른 프로세서끼리 다른 queue의 lock을 얻기위해 경쟁해야 하므로 lock이 필요해진다. 따라서 역시 scalability가 떨어지는 문제가 발생할 수 있음