Multiprocessor and Real Time Scheduling


These notes follow closely the organization of Chapter 10 in Stallings' text. For that reason, they are mainly in outline form. Please read the text for the details.

Stallings' treatment of both multiprocessor and real time scheduling is a bit patchy. He touches on several different topics, intending to give a flavor of each subject, but does not give a good view of the "big picture". The topics covered are just a few (somewhat disconnected) glimpses of a much bigger picture. We have a separate course, COP 4613 Real Time Systems, that gives more complete coverage to the one area.

There are links at the end to some other notes on real-time scheduling.


Classifications of Multiprocessor Systems

Independent Parallelism

Coarse and Very Coarse-Grained Parallelism

Medium-Grained Parallelism

Fine-Grained Parallelism

Decisions that must be made in Scheduling

Assignment of Processes to Processors

Who is in control?

Process Scheduling

Intuitively, what might make the specific scheduling discipline less important with multiple CPUs?

Thread Scheduling

Multiprocessor Thread Scheduling Approaches

Load Sharing

Advantages: Disadvantages:

Gang Scheduling

Scheduling Group

Dedicated Processor Assignment

Dynamic Scheduling

How is this different from load sharing and gang scheduling?

Real-Time Systems

Characteristics of Real-Time Operating Systems

Features of Real-Time Operating Systems

In COP 4613, we look at real-time operating systems in more detail, and do some experiments using one such system, Real-Time Linux.

Degrees of Preemptive Scheduling of Real-Time Processes

These figures, from the text, can be a little bit confusing. The are a case of "mixing apples and oranges". Generally, all of these models are supported, and which one applies depends on the priority (or deadline) of the new process relative to those of the other processes.

Real-Time Scheduling

Deadline Scheduling

Two Periodic Tasks, viewed as Sequences of Jobs

Scheduling of Periodic Real-time Tasks with completion Deadlines

Optimality Theorem for EDF

We prove this theorem in COP 4613.

Scheduling of Aperiodic Real-time Tasks with starting Deadlines

Rate Monotonic Scheduling

This example differs from the first in assuming scheduling is nonpreemptive. Otherwise, task B could preempt task A, and still make its deadline with EDF. We only need to keep the processor idle if we cannot preempt it. By the way, I think Stallings' use of the term "unforced" idle times, is a bit confusing, because the scheduler is enforcing idle times, even though it is not forced to. The "unforced" comes from the latter.

Periodic Task Timing Diagram

A Task Set with RMS

Optimality Theorem for RMS

Schedulability Theorem for RMS

System of tasks is schedulable if:

U <= n(21/n - 1)

Where U = C1/T1 + C2/T2 + ... + Cn/Tn

The formula n(21/n - 1) converges to ln 2 for large values of n. The value of ln 2 is about 0.693.

We prove this theorem in COP 4613.

See the notes with links at the end of this file, for more detail on RMS.

"Linux" (POSIX Realtime) Scheduling

Example of POSIX Realtime Scheduling

UNIX SVR4 Scheduling

SVR4 Dispatch Queues

Note that there is a cute way of implementing the search for the highest priority nonempty queue. If the processor has a bit-scan instruction that can be used. If there is no bit-scan instruction, a floating point normalize instruction can be used. By the way, one beauty of the bit vector data structure in SMP programming is that most architectures support an atomic operation for modifying one bit, so no mutual exclusion mechanism is required to protect the bit vector.

Windows 2000 Scheduling

Rate Monotonic Analysis

There is a separate course on Real Time Systems at FSU, COP 4613. In that course we go into real time scheduling in greater depth, along with other aspects of real time systems. One of the topics we cover is "Rate Monotonic Analysis", an approach to the design of real-time systems starting from rate monotonic scheduling. The following notes are from a tutorial on Rate Monotonic Analysis developed by Ray Obenza, of the Software Engineering Institute at Carnegie Mellon University. You may find them interesting. If we have time in class (perhaps during the recitation section) we may look at them. In particular, it is interesting to look at the third group, which is on rate monotonic scheduling of periodic tasks and includes an application of the utilization bound theorem mentioned above.

© 2002 T. P. Baker & Florida State University. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means without written permission. (Last updated by $Author: cop4610 $ on $Date: 2002/09/26 20:06:06 $.)