10 – Multiprocessor Scheduling

Multicore Processor

the source of multiprocessor-scheduling proliferation

Multicore

multiple CPU cores are packed onto a single chip

Does not, threads

adding more cores _ _ make that single application run faster, you’ll have to rewrite the application to run in parallel, using _

Cache

small, fast memories

Cache

hold copies of popular data that is found in the main memory

Cache

utilize temporal and spatial locality

Main Memory

holds all of the data

Main Memory

access to this is slower than cache

Bus Snooping

each cache pays attention to memory updates by observing the bus

Bus Snooping

when a CPU sees an update for a data item it holds in its cache, it will notice the change and either invalidate its copy or update it

Mutual Exclusion

when accessing shared data across CPUs, _ _ primitives should likely be used to guarantee correctness

Cache Affinity

keep a process on the same CPU if at all possible

Cache Affinity

a multiprocessor scheduler consider _ _ when making its scheduling decision

Single Queue Multiprocessor Scheduling

put all jobs that need to be scheduled into a single queue

Globally shared queue

SQMS, each CPU simply picks the next job from the _ _ _

Lack of Scalability

cons of Single Queue Multiprocessor Scheduling (1)

Cache Affinity Issue

cons of Single Queue Multiprocessor Scheduling (2)

Preserve affinity for most processes

solution to the cache affinity issue

Multi Queue Multiprocessor Scheduling

consists of multiple scheduling queues

Exactly one

MQMS, when a process enters the system, it is placed on _ _ scheduling queue

Information sharing and synchronization

MQMS, avoids the problems of _ _ _ _

Round Robin

with this, MQMS provides more scalability and cache affinity

Migration

how to deal with load imbalance?

Work Stealing

move processes between queues

Low on processes

a source queue that is _ _ _ is picked, work stealing implementation (1)

Peeks

the source queue occasionally _ at another target queue, work stealing implementation (2)

More full, steal

if the target queue is _ _ than the source queue, the source will _ one or more processes from the target queue

High overhead and trouble scaling

cons of work stealing