OS Scheduler

Multiprocessor Scheduling

How do you assign processes to processors? This is a fundamental question that I need to answer.

Two architectural styles:

  1. Multiprocessor is uniform
  2. Multiprocessor is heterogeneous

Assuming architectural style 1, you can either a) Assign processes to a dedicated processor b) Migrate processes between processors


It seems intuitive to go with option b), because there are way more processes that processors. But see discussion on Multiprogramming. Answer is not clear.

Style 2 requires special software.

So how to assign processes to processors? Some options:

Option 1.a: static assignment

  • Low system overhead, because decision is made once.
  • Permits group or gang scheduling
  • Processor can be idle while another has a backlog Option 1.b: process migration
  • Potential high overhead due to migration Option 1.ab: dynamic load balancing
  • Have a static assignment, but migrate processes sometimes

Implementation Architecture

The professor introduces two main ways to architect this.

  1. Master/slave architecture
  • Key kernel functions always run on a particular processor ( RTLinux design)
  • Master is responsible for scheduling
  • Slave sends service request to the master and waits for result

Advantage: simple design, similar to uniprocessor. Disadvantages

  • Failure of master brings down whole system
  • Master can become a performance bottleneck
  1. Peer architecture
  • Kernel can execute on any processor
  • Each processor does self-scheduling
  • Complicates the operating system
  • Make sure two processors do not choose the same process

Style 2 requires special software.

see Thread Scheduling for the 4 ways that scheduling is done.