2-5. Virtualization: Multiprocessor Scheduling

• 복수의 CPU core가 하나의 칩 안에 들어가 있는 multicore processor의 대두로 multiprocessor scheduling이 필요해졌다.
• 전통적인 응용 프로그램은 하나의 CPU만을 사용해, CPU 추가해도 빨라지지 않는다.
  → thread를 사용해 다시 작성 필요.

Cache가 있는 single CPU 구조

• Cache: 작고, 빠른 memory.

  • 자주 사용하는 data의 복사본 저장.
  • write-back cache: 일단 cache update, 일정 시간/조건에 따라 내리기.
  • write-through cache: update 한 순간 update (즉시).
  • temporal locality: 한번 access한 것은 또 금방 access할 확률 크다. (반복문)
  • spatial locality: 어떤 지점을 access했으면 근처 data access 확률 크다.

• Main Memory: 모든 data 저장, cache보다 느림.

Cache Coherence (consistence) 문제

(multicore일 때 문제가 더 복잡해짐)

• Bus Snooping: Bus를 monitoring하면서 memory 변경을 감지한다.
  → cache를 invalidate 하거나, update한다.

• CPU 간 공유 데이터를 접근할 때, 정확성을 위해 mutual exclusion (mutex) 설정이 쓰인다.

복수의 CPU가 있으면 CPU Scheduling은 더 복잡해지는데, Processor들이 동일 구조라 가정하면, 두 가지 접근이 가능하다.

• Asymmetric multiprocessing: 오직 하나의 processor가 system data에 접근하여, data sharing의 문제를 경감한다.
  

• Symmetric multiprocessing (SMP): 각 프로세서가 전역 공유 queue 또는 각각의 private queue에 대해 각자 schedule한다.
  

Simple Queue Multiprocessor Scheduling (SQMS)

모든 작업들을 하나의 globally shared queue에 넣는다.
각 CPU는 그 Queue에서 순차적으로 다음 작업을 뽑는다.

-> Scheduler가 다수의 CPU에서 제대로 동작하게 하기 위해 lock을 도입해야 하는데, Scalability(확장성)의 결여가 발생한다. (lock 늘렸을 때 성능이 그만큼 안나옴.)
각 작업들이 CPU를 계속 옮겨 다니게 된다. (cache affinity ↓)

Cache Affinity (캐시 친화성)

Process migration을 하면, CPU cache에 구축해 놓은 내용들이 무쓸모된다.
새 CPU는 cache를 다시 채워야 한다.
-> cache affinity 필요: 가능한 한 process를 한 CPU에서 동작하게 한다.

• Soft affinity (pinning): 같은 CPU에 process가 동작하도록 시도. (강제 X)
• Hard affinity: migration 금지: process가 migrate 못하도록 system call을 제공한다. (e.g., Linux)
  

  Multi-Queue Multiprocessor Scehduling (MQMS)

  MQMS는 복수의 scheduling queue로 이루어져 있다.
  system에 job이 들어오면, 정확히 하나의 queue에 안착한다.

1. Locking 문제 해결 (synchronization)
2. job이 움직이는(cache) 문제 없음. (information sharing; cache affinity)
   

-> Load imbalance 문제가 있을 수 있다. (simple queue에선 발생 안함)

Load balancing은 모든 processor에 거쳐 workload를 공평하게 배분하려 노력한다.
-> processor가 private queue를 가진 system에서만 필요.

• Push migration: Load 큰 데서 빼서 작은 데에 넣는다.
• Pull migration: Load 적으면 많은 데서 떼온다..
  둘 다 Affinity 문제 생길 수 있다. (지켜야 하는 애들 지정)
  
• Work Stealing: 대상 Queue가 Source Queue보다 가득 차 있으면 뺏어온다. (=Pull migration)
  • 단점: overhead↑, scalability ↓