Screen Version

School of Computer Science & Engineering
University of New South Wales
 Advanced Operating Systems 
 COMP9242 2002/S2 

SMP Scheduling

How schedule a multiprocessor?

Issues:

Scalability:

How many CPUs to support?

Application mix:

SMP for

• time-shared multi-tasking environment,
• web server,
• highly parallel applications?

Architecture:

caching, memory bandwidth...

Scheduler organisation

Single scheduler for all CPUs

 

• Not really SMP.
• Not scalable.

Global ready queue:

CPU schedules itself from global queue.

• Course-grain locking of ready queue.
• Limited scalability.

Per-CPU ready queues

 

• Scalable.
• Load balancing?
• Process migration?

Issues: Address-space distribution

Restrict address spaces (tasks) to a single CPU.

+

Most sharing is within task.

• Good cache performance (maybe?)

+

Unmapping pages only affects single CPU.

• Only requires invalidating local TLB entries.

-

No performance gain for multithreaded tasks.

• Multiple CPUs only enhance throughput.
• Not a general solution.

Gang scheduling (co-scheduling):

Always schedule all threads of a task at once on different CPUs.

+

Maximum concurrency for parallel applications.

+

Minimises intra-task communication latency.

-

High bus contention.

+

Appropriate. for parallel number-crunching

-

May have some CPUs idle.

==> Used mostly on supercomputers.

Fixed processor assignment

A thread has a processor affinity and will only run on that CPU:

+

Minimal contention for kernel data structures.

+

Minimal kernel communication overhead.

+

Cache friendly.

+

Highly scalable.

-

No strict global priorities.

-

No load balancing.

Ok for:

• non-real-time systems,
• mostly short processes,
• NUMA machines,
• with additional load balancing & process migration.