10. Multiprocessor scheduling

Question 1

What issues exist with multiprocessor scheduling?

Answer 1

1. Cache coherence. The CPU caches must be carefully managed so they don’t work with an outdated data
2. Race condition when using a single queue or among other shared data structures
3. Cache affinity

Question 2

What are two basic implementation of multiprocessor scheduling and what are their downsides?

Answer 2

SQMS and MQS. SQMS works with a single queue and lets CPUs pick jobs from it. However, the queue itself has to be thread-safe and surrounded by lock which leads to performance decrease. Such scheduler also has to account for cache affinity and place jobs on best-suit CPUs when possible.
MQS works with multiple queues and has a benefit of scaling, the cache affinity in it comes by nature and there is no race condition for a queue. However, the problem of load imbalance has to be taken into account to avoid some CPU being fully loaded while other sits idle. This can be solved by migration of jobs between CPUs.