CPU Scheduling

References:

  1. Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 5

5.1 Basic Concepts

5.1.1 CPU-I/O Burst Cycle

5.1.2 CPU Scheduler

5.1.3. Preemptive Scheduling

5.1.4 Dispatcher

5.2 Scheduling Criteria

5.3 Scheduling Algorithms

The following subsections will explain several common scheduling strategies, looking at only a single CPU burst each for a small number of processes. Obviously real systems have to deal with a lot more simultaneous processes executing their CPU-I/O burst cycles.

5.3.1 First-Come First-Serve Scheduling, FCFS

Process Burst Time
P1
24
P2
3
P3
3

5.3.2 Shortest-Job-First Scheduling, SJF

Process Burst Time
P1
6
P2
8
P3
7
P4
3

Process Arrival Time Burst Time
P1
0
8
P2
1
4
P3
2
9
p4
3
5

5.3.3 Priority Scheduling

Process Burst Time Priority
P1
10
3
P2
1
1
P3
2
4
P4
1
5
P5
5
2

5.3.4 Round Robin Scheduling

Process Burst Time
P1
24
P2
3
P3
3

5.3.5 Multilevel Queue Scheduling

5.3.6 Multilevel Feedback-Queue Scheduling

5.4 Thread Scheduling

5.4.1 Contention Scope

5.4.2 Pthread Scheduling


Figure 5.8

5.5 Multiple-Processor Scheduling

5.5.1 Approaches to Multiple-Processor Scheduling

5.5.2 Processor Affinity

5.5.3 Load Balancing

5.5.4 Multicore Processors

5.5.5 Virtualization and Scheduling

5.6 Operating System Examples

5.6.1 Example: Solaris Scheduling

Figure 5.12

5.6.2 Example: Windows XP Scheduling


Figure 5.14

5.6.3 Example: Linux Scheduling


Figure 5.15


Figure 5.16

5.7 Algorithm Evaluation

5.7.1 Deterministic Modeling

Process Burst Time
P1
10
P2
29
P3
3
P4
7
P5
12

5.7.2 Queuing Models

N = Lambda * W

5.7.3 Simulations


Figure 5.17

5.7.4 Implementation

5.8 Summary

Material Omitted from the Eighth Edition:

Was 5.4.4 Symmetric Multithreading ( Omitted from 8th edition )


omitted