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.

Contents

• Multiprocessor scheduling
• Real time scheduling
• Rate Monotonic Analysis

Classifications of Multiprocessor Systems

• Loosely coupled multiprocessor
  • Each processor has its own memory and I/O channels
  • Covered later (Chapter 13) under distributed systems
• Functionally specialized processors
  • Such as I/O processor
  • Controlled by a master processor
  • Covered later (Chapter 11) under I/O systems
• Tightly coupled multiprocessing
  • Processors share main memory
  • Controlled by operating system

Independent Parallelism

• Processes are independent applications or jobs
• No synchronization between processes is needed
• Advantages: more than one processor is available
  • Average response time to users is less (see queueing theory result on multiserver vs. single server queues)

Coarse and Very Coarse-Grained Parallelism

• Synchronization among processes at a very gross level
• Good for concurrent processes running on a multiprogrammed uniprocessor
• Can by supported on a multiprocessor with little change
• Cost of synchronization can be moderatelhy high, since synchronization is not frequent

Medium-Grained Parallelism

• Parallel processing or multitasking within a single application
• Single application is a collection of threads
• Threads usually interact frequently
• Cost of synchronization must be very low

Fine-Grained Parallelism

• Highly parallel applications
• Specialized and fragmented area
• Not supported by general purpose operating systems

Decisions that must be made in Scheduling

• Assignment of processes to processors
• Use of multiprogramming on individual processors
• Actual dispatching of a process

Assignment of Processes to Processors

• Static processor assignment
  • Permanently assign process to a processor
  • Dedicate short-term queue for each processor
  • Less overhead
  • Processor could be idle while another processor has a backlog
• Dynamic processor assignment
  • Treat processors as a pooled resource and assign process to processors on demand
  • Global queue
  • Schedule to any available processor

Who is in control?

• Master/slave architecture
  • Key kernel functions always run on a particular processor
  • Master is responsible for scheduling
  • Slave sends service request to the master
  • Disadvantages
  • Failure of master brings down whole system
  • Master can become a performance bottleneck
• Peer architecture
  • Operating system can execute on any processor
  • Each processor does self-scheduling
  • Complicates the operating system
    • Make sure two processors do not choose the same process
  • The dominant architecture today (SMP)

Process Scheduling

• Single queue for all processes
• Multiple queues are used for priorities
• All queues feed to the common pool of processors
• Specific scheduling discipline is less important with more than on processor (see graphs in text)

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

Thread Scheduling

• Allows parallel execution with a process
• An application can be a set of threads that cooperate and execute concurrently in the same address space
• Running threads on separate processors yields a dramatic gain in performance

Multiprocessor Thread Scheduling Approaches

• Load sharing (distinguished from "load balancing")
  • Processes are not assigned to a particular processor (single queue)
• Gang scheduling
  • A set of related threads is scheduled to run on a set of processors at the same time
• Dedicated processor assignment
• Threads are assigned to a specific processor
• Dynamic scheduling
• Number of threads in a process can be altered during course of execution

Load Sharing

• Load is distributed evenly across the processors
• No centralized scheduler required
• Use global queues, with any discipline

• Central queue needs mutual exclusion
• May be a bottleneck when more than one processor looks for work at the same time
• Preemptive threads are unlikely resume execution on the same processor
• Cache use is less efficient
• If all threads are in the global queue, all threads of a program will not gain access to the processors at the same time (may cause more blocking (hence more context switching), more paging, more swapping)

Gang Scheduling

• Simultaneous scheduling of threads that make up a single process
• Useful for applications where performance severely degrades when any part of the application is not running
• Threads often need to synchronize with each other

Scheduling Group

Dedicated Processor Assignment

• When application is scheduled, its threads are assigned to a processor
• Some processors may be idle
• No multiprogramming of processors
• Timing is very predicatable (see real time below)
• Makes sense when there are many processors
• Especially for special-purpose architectures, such as real-time simulators and signal processors

Dynamic Scheduling

• Number of threads in a process are altered dynamically by the application
• Operating system adjust the load to improve use
• Assign idle processors
• New arrivals may be assigned to a processor that is used by a job currently using more than one processor
• Hold request until processor is available
• New arrivals will be given a processor before existing running applications

How is this different from load sharing and gang scheduling?

Real-Time Systems

• Correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced
• Tasks or processes attempt to control or react to events that take place in the outside world
• These events occur in "real time" and process must be able to keep up with them
• Examples:
  • Control of laboratory experiments
  • Process control plants
  • Robotics
  • Air traffic control
  • Telecommunications
  • Military command and control systems
  • Multimedia servers and players
  • Home appliances (washers, heaters, microwave ovens)

Characteristics of Real-Time Operating Systems

• Deterministic
• Operations are performed at fixed, predetermined times or within predetermined time intervals
• Concerned with how long the operating system delays before acknowledging an interrupt
• Responsiveness
• How long, after acknowledgment, it takes the operating system to service the interrupt
• Includes amount of time to begin execution of the interrupt
• Includes the amount of time to perform the interrupt
• User control
• User specifies priority
• Specify paging
• What processes must always reside in main memory
• Disks algorithms to use
• Rights of processes
• Reliability
• Degradation of performance may have catastrophic consequences
• Attempt either to correct the problem or minimize its effects while continuing to run
• Most critical, high priority tasks execute

Features of Real-Time Operating Systems

• Fast context switch
• Small size
• Ability to respond to external interrupts quickly
• Multitasking with interprocess communication tools such as semaphores, signals, and events
• Files that accumulate data at a fast rate
• Use of special sequential files that can accumulate data at a fast rate
• Preemptive scheduling based on priority, or deadlines
• Minimization of intervals during which interrupts are disabled
• Delay tasks for fixed amount of time
• Special alarms and timeouts
• High reliability
• High end: multiprocessor, high security, fault tolerance

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

• Static table-driven
• Determines at run time when a task begins execution
• Static priority-driven preemptive
• Traditional priority-driven scheduler is used
• Dynamic planning-based
• Dynamic best effort

Deadline Scheduling

• Real-time applications are not concerned with speed but with completing tasks
• Scheduling tasks with the earliest deadline minimizes the fraction of tasks that miss their deadlines
  (This statement is misleading. It depends on whether EDF is applied preemptively or not.)
• Information used
• Ready time
• Starting deadline
• Completion deadline
• Processing time
• Resource requirements
• Priority
• Subtask scheduler

Two Periodic Tasks, viewed as Sequences of Jobs

Scheduling of Periodic Real-time Tasks with completion Deadlines

Optimality Theorem for EDF

• Assuming tasks are independent (periodic or aperiodic)
• EDF will not miss deadline until workload exceeds 100% CPU utilization

We prove this theorem in COP 4613.

Scheduling of Aperiodic Real-time Tasks with starting Deadlines

Rate Monotonic Scheduling

• Assigns priorities to tasks on the basis of their periods
• Highest-priority task is the one with the shortest period

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

• Given a set of independent periodic tasks
• RM is the optimal static priority assignment
• If there is any assignment that causes no missed deadlines, RM will succeed

Schedulability Theorem for RMS

System of tasks is schedulable if:

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

The formula n(2^1/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

• Scheduling classes
• SCHED_FIFO: First-in-first-out real-time threads
• SCHED_RR: Round-robin real-time threads
• SCHED_OTHER: Other, non-real-time threads
• Within each class multiple priorities may be used

Example of POSIX Realtime Scheduling

UNIX SVR4 Scheduling

• Highest preference to real-time processes
• Next-highest to kernel-mode processes
• Lowest preference to other user-mode processes

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

• Priorities organized into two bands or classes
• Real-time (16 levels)
• Variable (16 more levels)
• Priority-driven preemptive scheduler

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.

• First group of slides, one per page
• Second group of slides, one per page
• Third group of slides, one per page
• Fourth group of slides, one per page
• Fifth group of slides, one per page
• Sixth group of slides, one per page
• Seventh group of slides, one per page