Multiprocessor Scheduling

Multiprocessor Scheduling

Multicore processor의 등장으로 multiprocessor-scheduling이 필요하게 되었다.

우리는 threads를 활용하여 여러 개의 CPU들에 jobs을 schedule 해주어야 한다.

---

Single CPU with cache

Cache에는 main memory에 있는 popular data들을 복제하여 저장해놓는다. Cache는 Main Memory에 비해 접근이 빠르다.

---

Cache coherence

CPU 0과 CPU 1이 data D를 다룬다고 할 때, 각각의 cache들은 private한 성질을 가지고 있으므로, CPU 1은 update 된 D'가 아닌 D를 가져오게 된다. 따라서 CPU에서 update data를 cache에서 발견했을 때, 바뀌었다는 것을 알려주고 invalidate 해주거나 update 해주어야 한다.

---

Cache Affinity

process를 어지간하면 같은 CPU에서 계속 돌려주는 것이 좋다.

Multiprocessor scheduler는 scheduling decision을 할 때 cache affinity를 반드시 고려해야 한다.

queue에서 뽑히는데로 CPU가 가져가면 확장성이 떨어지게 된다.

위와 같이 Scheduling하면 affinity를 보존 할 수 있으나 scheduling하는 과정 자체가 복잡해진다.

---

Multi-queue Multiprocessor Scheduling (MQMS)

MQMS는 multiple shceduling queue들로 이루어져있다.

각각의 queue들은 특정한 scheduling discipline을 따라야 한다.

한가지 job이 들어오면, 반드시 한개의 queue에만 할당된다.

이 방식은 information sharing과 synchronization의 문제를 피할 수 있다.

RR을 사용한 scheduling

---

Load Imbalance issue of MQMS

위와 같이 Q0에는 job이 할당되지 않아 CPU 0이 idle한 경우가 발생할 수도 있다.

Q0가 비어있으면 Q1에 있는 job을 migrate시켜준다.

확장성을 최대로 하기 위해 job을 계속 migrate시키는 방법도 있다

work stealing에 실행 과정과 단점