Notes on Multiprocessor Scheduling


There are many different types of computers with multiple processors.The most common system in use today is the Symmetric MultiProcessor (SMP).All of the CPUs in an SMP system are identical and can address all of the RAM.


Very little has to be done to schedule a multiprocessor system.

Whenever a CPU needs a process to run, it takes the next task from the ready list.

The scheduling queue must be accessed in a critical section.Busy waiting is usually used.


Some consideration for SMP scheduling

        With multiple CPUs, it is not as likely that a short task will get stuck waiting for a long task to complete.Therefore the selection of the next task is not as important.

        Any task can run on any CPU thereby allowing load balancing.

        Tasks should stay with a single CPU to take advantage of cache loading.

        Gang scheduling attempts to schedule all of the threads of a process together.


Load sharing is a key concept in multiprocessor systems.In an SMP, this isnít much of a problem since any CPU can execute any thread.In systems with distributed memory (each CPU has its own memory and cannot access the RAM of another CPU), load sharing is a major consideration. This is often more of an application concern than an OS concern.


Notes on Real-time Scheduling


Real-time computing requires that the result not only be correct, but produced within a specific time limit.Real-time programming is used in process control to ensure that the system reacts to input in time.Examples are chemical plant control or robotic control.


When a R/T task is created or scheduled, a deadline time and an estimated execution time are specified.The task must be scheduled at or before (deadline time - run time).


There are several R/T scheduling approaches:

        Static predetermined schedules - A schedule is devised before hand from a list of known tasks, execution times and deadline times.

        Static predetermined priorities - Using a list of known tasks, execution times and deadline times, priorities are assigned to each task.A regular priority based scheduler is used.

        Dynamic planning based - When a task is scheduled, the algorithm determines if it can be feasibly executed in time.

        Dynamic best effort - The scheduler tries to meet deadlines by raising the priority of tasks as they approach their deadline.Tasks are aborted if they don't or can't meet their deadline.