10. Multiprocessor Scheduling
Multicore: Multiple CPU cores are packed onto a single chip.
-> using threads (to run in parallel)
-> How to schedule jobs on multiple CPUS(or cores)?
Single CPU with Cache
- Cache:
- small, fast, popular data의 copy들을 가진다.
- temporal & spatial 지역성 활용
- Main memory: 모든 데이터를 저장, slower than cache
Cache Coherence(캐시일관성)
:여러 캐시들이 동일한 메모리 위치에 대한 데이터를 보유할 때, 각 캐시가 최신의 일관된 데이터를 유지하도록 보장하는 메커니즘
- how?: 여러개 프로세스들이 메모래에 갱신할 때 항상 공유되도록 한다.(bus snooping)
- 캐시는 자신과 메모리르 ㄹ연결하는 버스의 통신상황 계속 모니터링, 캐시 변경 발생시
- invalidate protocol: 해당 데이터의 복사본을 무효화 시킨다.
- update protocol : 해당 데이터의 모든 복사본도 업데이트 한다.
Synchronization
- lock(&m), unlock(&m) 필요
- ex) list에서 원소 제거하는 과정: critical section 임.
- fine grained 하게 최대한 작게 임계구간 잡아야함.
- locking 많이 -> concurrency 감소 = 성능 감소
Cache Affinity (Processor Affinity)
: 프로세스가 다음에 실행될 때 동일한 CPU에서 실행되는 것이 유리하다.
- 왜냐하면, 해당 CPU 캐시에 일부 정보(state)가 이미 존재하고 있기 때무에 더 빨리 실행될 것이기 때문이다.
Single Queue Multiprocessor Scheduling(SQMS)
- 모든 job들이 single queue에 scheduled.
- 각 CPU는 global shared queue를 보고 다음 job을 고른다.
- 문제:
- 작업이 너무 자주 서로 다른 큐로 이동한다.(스케쥴링 효율저하)(cache affinity저하)
- 공유되는 큐를 사용하므로 locking 형식 필요 -> 확장성(scalability)이 떨어진다.
Scheduling Example with Cache affinity
- Preserving affinity: E 제외 다른 process들은 움직이지 않음.
- 구현 복잡
Multi-Queque Multiprocessor Scheduling(MQMS)
- 단일 queue 문제로 인해, MQMS는 큐도 여러개이다!(CPU 마다 각자 큐 가짐)
- 각 큐는 RR 혹은 다른 스케쥴링 알아서...
- job은 하나의 scheduling queue에 고정.
- data sharing과 동기화 문제 방지한다.
- CPU 개수가 증가할수록, 큐도 증가하기 때문이다.
- 장점: 나은 scability, cache affinity
문제: Load Imbalance issue 
- 여러개 큐를 사용하므로 load imbalance issue 발생...
- 그런데 만약 C가 끝나면 , A가 B,D보다 2배의 CPU 차지
- 심지어 만야 A가 끝나면, CPU0은 놀게 된다.
해결: Migration(job 옮기기)
: 작업을 한 CPU에서 다른 CPU로 이주시키기
- 그러나 한번의 이주만으로는 문제 해결 안됨. 지속적 이주가 필요하다
Migration 필요 여부 결정 how? Work Stealing
- job의 개수가 낮은 큐: source queue
- 다른 target queue들에 훨씬 많은 수의 작업이 있는지 가끔씩 검사한다.
- target queue가 source queue보다 훨씬 많이 차있으면, source queue가 작업을 가져온다.
- 문제:
- 큐 자주 검사 -> overhead 발생 -> 확장성 저하
- 큐 자주 검사 안하면 -> load imbalance 문제 해결 못함.
