Multiprocessor Scheduling

Question 1

What are the three multiprocessor systems?

Answer 1

1. Multicore processor
2. Multiprocessor
3. Multithreaded core

Question 2

What does the cache of a CPU hold?

Answer 2

Copies of popular data that’s found in the main memory

Question 3

What does the main memory of a CPU hold?

Answer 3

All data

Question 4

Is access to the cache faster or slower than access to the main memory of a CPU?

Answer 4

Faster

Question 5

What two forms of locality does the cache of a CPU utilize?

Answer 5

Temporal & spatial locality

Question 6

A multiprocessor with a cache must ensure … of shared resource data stored in multiple caches

Answer 6

consistency

Question 7

What sort of primitives should be used to guarantee correctness when accessing shared shared data across CPUs in a multiprocessor with cache?

Answer 7

Mutual exclusion primitives

Question 8

Will a process on a multiprocessor run faster or slower if its executed on the same CPU as it has its states stored in the cache of?

Answer 8

Faster

Question 9

What problem is it important that a multiprocessor considers when making its scheduling decisions?

Answer 9

Cache affinity

Question 10

Give the definition:
The binding & unbinding of a process/thread to a CPU/CPUs, so that the process/thread only executes on the designated CPU/CPUs

Answer 10

Cache affinity

Question 11

Describe the policy of Single Queue Multiprocessor Scheduling (SQMS)

Answer 11

Puts all jobs that need to be scheduled into a single/global queue

Question 12

A synonym for SQMS is:

Answer 12

Asymmetric MultiProcessing (AMP)

Question 13

Describe the structure of SQMS

Answer 13

One processor/core manages the scheduling queue - master processor - while the rest are slave processors

Question 14

What are the pros of SQMS?

Answer 14

Simple
Reduced data sharing

Question 15

What are the cons of SQMS?

Answer 15

Lack of scalability
Cache affinity
Complex

Question 16

What does the lack of scalability that SQMS has mean that we have to insert in a multiprocessor?

Answer 16

Locking

Question 17

Describe the MQMS policy

Answer 17

Consists of multiple scheduling queues. Where each processor has its own scheduling queue & an incoming job is assigned to a specific processor (queue)

Question 18

What’s a synonym for MQMS?

Answer 18

Symmetric MultiProcessing (SMP)

Question 19

What are the pros of MQMS?

Answer 19

• Better cache affinity
• Scalability

Question 20

What are the cons of MQMS?

Answer 20

Load imbalance

Question 21

Give the definition:
Some processes having more workloads in a multiprocessor

Answer 21

Load imbalance

Question 22

What are the 3 solutions to load imbalance?

Answer 22

1. Migration
2. Continously switching jobs
3. Work stealing

Question 23

Give the definition:
Binding jobs to specific cores

Answer 23

Processor affinity

Question 24

What type of affinity is this?
Jobs are expected to execute on a single processor, but it’s possible to migrate them between processors

Answer 24

Soft affinity

Question 25

What type of affinity is this? Jobs are specified to (can only be executed on) a subset of processors

Answer 25

Hard affinity

Question 26

What is processor affinity used to avoid high memory access overhead in?

Answer 26

Non-Uniform Memory Access (NUMA)

Question 27

What type of affinity does Linux deploy?

Answer 27

Soft affinity

Question 28

What type of affinity does Linux provide with the sced_setaffinity() system call?

Answer 28

Hard affinity

Question 29

What type of multiprocessing is this? Heterogeneous cores on a single chip

Answer 29

Heterogeneous multiprocessing

Question 30

⭐️ Give the definition: A simple but unscalable method for scheduling on multiprocessor systems

Answer 30

SQMS

Question 31

⭐️ Give the definition: The widely used scheduling method for modern multiprocessor systems

Answer 31

MQMS

Question 32

⭐️ Give the definition: An architecture that introduces new challenges for scheduling

Answer 32

Heterogeneous scheduling

Question 33

SQMS generally offers better cache affinity than MQMS (T/F)

Answer 33

False

Question 34

In MQMS, all cores/processors must use the same scheduling algorithm (T/F)

Answer 34

False