Uos2005 Chp5

Chapter 5 Process Scheduling
CPU Scheduling
Objective:
Basic Scheduling Concepts CPU Scheduling Algorithms
Why Multiprogramming?
Maximize CPU/Resources Utilization (Based on Some Criteria)
* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.
CPU Scheduling
Process Execution
CPU-bound programs tend to have a few very long CPU bursts. IO-bound programs tend to have many very short CPU bursts.
CPU-Burst
New Terminate
I/O-Burst
CPU Scheduling
The distribution can help in selecting an appropriate CPU-scheduling algorithms
120 100 60 20 8
frequency
24 16 Burst Duration (ms)
CPU Scheduling
CPU Scheduler The Selection of Process for Execution
A short-term scheduler
New dispatched Ready Waiting
Terminated
Running
CPU Scheduling
Nonpreemptive Scheduling
A running process keeps CPU until it volunteers to release CPU
E.g., I/O or termination
Advantage
Easy to implement (at the cost of service response to other processes)
E.g., Windows 3.1
CPU Scheduling
Preemptive Scheduling
Beside the instances for non-preemptive scheduling, CPU scheduling occurs whenever some process becomes ready or the running process leaves the running state!
Issues involved:
Protection of Resources, such as I/O queues or shared data, especially for multiprocessor or real-time systems. Synchronization
E.g., Interrupts and System calls
CPU Scheduling
Dispatcher
Functionality:
Switching context Switching to user mode Restarting a user program
Dispatch Latency:
Must be fast Stop a process
Start a process
Scheduling Criteria
Why?
Different scheduling algorithms may favor one class of processes over another!
Criteria
CPU Utilization Throughput Turnaround Time: CompletionT-StartT Waiting Time: Waiting in the ReadyQ Response Time: FirstResponseTime
Scheduling Criteria
How to Measure the Performance of CPU Scheduling Algorithms? Optimization of what? General Consideration
Average Measure Minimum or Maximum Values
Variance
Predictable Behavior
Scheduling Algorithms
First-Come, First-Served Scheduling (FIFO) Shortest-Job-First Scheduling (SJF) Priority Scheduling Round-Robin Scheduling (RR) Multilevel Queue Scheduling Multilevel Feedback Queue Scheduling Multiple-Processor Scheduling
First-Come, First-Served Scheduling (FCFS)

The process which requests the CPU first is allocated the CPU Properties:
Non-preemptive scheduling CPU might be hold for an extended period.
CPU request A FIFO ready queue
dispatched

Example
Process P1 P2 P3 Gantt Chart P1 0 P2 P3 0 3 6 CPU Burst Time 24 3 3
Average waiting time P2 P3 24 27 30 = (0+24+27)/3 = 17 Average waiting time P1 30 = (6+0+3)/3 = 3
*The average waiting time is highly affected by process CPU burst times !

Example: Convoy Effect
One CPU-bound process + many I/O-bound processes
CPU
ready queue
I/O device
idle
ready queue
All other processes wait for it to get off the CPU!

Shortest-Job-First Scheduling (SJF)

Non-Preemptive SJF
Shortest next CPU burst first
process P1 P2 P3 P4 9 CPU burst time 6 8 7 3 P3 16 P2 24
Average waiting time = (3+16+9+0)/4 = 7
P4 P1 0 3

Nonpreemptive SJF is optimal when processes are all ready at time 0
The minimum average waiting time!
Prediction of the next CPU burst time?

Long-Term Scheduler A specified amount at its submission time Short-Term Scheduler Exponential average (0<= <=1)
n+1 = tn + (1-) n

Preemptive SJF
Shortest-remaining-time-first
Process P1 P2 P3 P4 CPU Burst Time Arrival Time 8 0 4 1 9 2 5 3
Average Waiting Time = ((10-1) + (1-1) + (17-2) + (5-3))/4 = 26/4 = 6.5
P1 P2 P4 P1 P3 10 17 26 0 1 5

Preemptive or Non-preemptive?
Criteria such as AWT (Average Waiting Time)
0 or 0 1 2 1 10 10 11 11
Preemptive AWT = ((2-1)+0) = 0.5 Non-preemptive AWT = (0+(10-1))/2 = 9/2 = 4.5
* Context switching cost ~ modeling & analysis
Priority Scheduling
CPU is assigned to the process with the highest priority A framework for various scheduling algorithms:
FCFS: Equal-Priority with TieBreaking by FCFS SFJ: Priority = 1 / next CPU burst length
Priority Scheduling
Process P1 P2 P3 P4 P5 CPU Burst Time 10 1 2 1 5 Priority 3 1 3 4 2
Gantt Graph P2 P5 0 1
Average waiting time = (6+0+16+18+1)/5 = 8.2 P1 6 P3 P4 16 18 19
Priority Scheduling
Priority Assignment
Internally defined use some measurable quantity, such as the # of open files, Average CPU Burst
Average I/O Burst
Externally defined set by criteria external to the OS, such as the criticality levels of jobs.
Priority Scheduling
Preemptive or Non-Preemptive?
Preemptive scheduling CPU scheduling is invoked whenever a process arrives at the ready queue, or the running process relinquishes the CPU. Non-preemptive scheduling CPU scheduling is invoked only when the running process relinquishes the CPU.
Priority Scheduling
Major Problem
Indefinite Blocking (/Starvation)
Low-priority processes could starve to death!
A Solution: Aging
A technique that increases the priority of processes waiting in the system for a long time.
Round-Robin Scheduling (RR)

RR is similar to FCFS except that preemption is added to switch between processes.
ready running
Interrupt at every time quantum (time slice)
Goal: Fairness Time Sharing

CPU
FIFO
The quantum is used up!
New process

Process P1 P2 P3 CPU Burst Time 24 Time slice = 4 3 3
P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30 AWT = ((10-4) + (4-0) + (7-0))/3 = 17/3 = 5.66

Service Size and Interval
Time quantum = q Service interval <= (n1)*q if n processes are ready. IF q = , then RR FCFS. IF q = , then RR processor sharing. The # of context switchings increases! process
0 0 0 6 10 10 10
quantum context switch # 12 0 6 1 1 9

=> 1/11 of CPU is wasted!
If context switch cost = 10% time quantum


Turnaround Time
process (10ms) quantum = 10 P1 P2 P3
0 10 10 20 20 0 0 30 0
quantum = 1
10 10 10 20 20 20 30 30 30
Average Turnaround Time = (10+20+30)/3 = 20 => 80% CPU Burst < time slice
ATT = (28+29+30)/3 = 29
Multilevel Queue Scheduling

Partition the ready queue into several separate queues => Processes can be classified into different groups and permanently assigned to one queue.
System Processes Interactive Processes
Batch Processes
Multilevel Queue Scheduling

Intra-queue scheduling
Independent choice of scheduling algorithms.
Inter-queue scheduling
a. Fixed-priority preemptive scheduling
a. e.g., foreground queues always have absolute priority over the background queues.
b. Time slice between queues

a. e.g., 80% CPU is given to foreground processes, and 20% CPU to background processes.
c. More??
Multilevel Feedback Queue Scheduling

Different from Multilevel Queue Scheduling by Allowing Processes to Migrate Among Queues.
Configurable Parameters:
a. # of queues b. The scheduling algorithm for each queue c. The method to determine when to upgrade a process to a higher priority queue. d. The method to determine when to demote a process to a lower priority queue. e. The method to determine which queue a newly ready process will enter. *Inter-queue scheduling: Fixed-priority preemptive?! * All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.
Multilevel Feedback Queue Scheduling

Example
quantum = 8 quantum = 16
FCFS
*Idea: Separate processes with different CPU-burst characteristics!
Multiple-Processor Scheduling
CPU scheduling in a system with multiple CPUs A Homogeneous System
Processes are identical in terms of their functionality.
Can processes run on any processor?
A Heterogeneous System
Programs must be compiled for instructions on proper processors.
Load Sharing Load Balancing!!
A queue for each processor
Self-Scheduling Symmetric Multiprocessing
A common ready queue for all processors.

Self-Scheduling Need synchronization to access common data structure, e.g., queues. Master-Slave Asymmetric Multiprocessing One processor accesses the system structures no need for data sharing
Load Balancing
Push migration: A specific task periodically checks for imbalance and migrate tasks Pull migration: An idle processor pulls a waiting task from a busy processor Linux and FreeBSD do both!
Processor Affinity
The system might avoid process migration because of the cost in invalidating or repopulating caches Soft or hard affinity
Symmetric Multithreading (SMT), i.e., Hyperthreading
A feature provided by the hardware Several logical processors per physical processor
Each has its own architecture state, including registers.
Issues: Process Synchronization
Multiple-Processor Scheduling SMT Superscalar SMT

time
Utilization++ Throughput++ Performance++
occupied issue slot unused issue slot
: 13
: 10
: 11
Thread Scheduling
Two Scopes:
Process Contention Scope (PCS): m:1 or m:m
Priority-Driven
System-Contention Scope (SCS): 1:1
Pthread Scheduling
PCS and SCS
Pthread_attr_setscope(pthread_attr_t *attr, int scope) Pthread_attr_getscope(pthread_attr_t *attr, int *scope)
Operating System Examples

Process Local Scheduling
E.g., those for user-level threads Thread scheduling is done locally to each application.
System Global Scheduling

E.g., those for kernel-level threads The kernel decides which thread to run.
Operating System Examples Solaris

Priority-Based Process Scheduling
Real-Time System
Kernel-service processes
Time-Sharing
low A default class
Interactive
Each LWP inherits its class from its parent process


Real-Time
A guaranteed response
System
The priorities of system processes are fixed.
Time-Sharing
Multilevel feedback queue scheduling priorities inversely proportional to time slices
Interactive
Prefer windowing process

priority 0 5 10 15 20 25 30 35 40 45 50 55 59 high Time quantum 200 200 160 160 120 120 80 80 40 40 40 40 20 Time quantum exp. 0 0 0 5 10 15 20 25 30 35 40 45 49 Return from sleep 50 50 51 51 52 52 53 54 55 56 58 58 59
low
Interactive and time sharing threads

The selected thread runs until one of the following occurs:
It blocks. It uses its time slice (if it is not a system thread). It is preempted by a higher-priority thread.
RR is used when several threads have the same priority.


Two New Classes in Solaris 9
Fixed Priority
Non-adjusted priorities in the range of the time-sharing class
Fair Sharing
CPU shares, instead of priorities
Operating System Examples Windows XP

Priority-Based Preemptive Scheduling
Priority Class/Relationship: 0..31 Dispatcher: A process runs until
It is preempted by a higher-priority process. It terminates Its time quantum ends It calls a blocking system call
Idle thread
A queue per priority level

Operating System Examples Windows XP

Each thread has a base priority that represents a value in the priority range of its class. A typical class Normal_Priority_Class Time quantum thread
Increased after some waiting
Different for I/O devices.
Decreased after some computation

The priority is never lowered below the base priority.
Favor foreground processes (more time quantum)

Operating System Examples Windows XP A Typical Class

Realtime
Timecritical Highest Above normal
High
Above Normal normal
Below Idle normal priority
31 26 25 24 23 22 16
15 15 14 13 12 11 1
15 12 11 10 9 8 1
15 10 9 8 7 6 1
15 8 7 6 5 4 1
15 6 5 4 3 2 1
Base Priority
Normal Below normal Lowest Idle
Real-Time Class
Variable Class (1..15)
Operating System Examples Linux Ver. 2.5+

Nemeric Priority 0 . . 99 100 . . . 140 Time Quantum
Scheduling Algorithm
O(1) SMP, load balancing, and processor affinity Fairness and support for interactive tasks Priorities
Real-time: 0..99 Nice: 100..140
Real Time Tasks Other Tasks
200ms . . . . . . . . 10ms
Operating System Examples Linux Ver. 2.5+

Each processor has a runqueue
An active array and an expired array Switching of the two arrays when all processes in the active array have their quantum expired. Priority-Driven Scheduling
Fixed Priority Real-Time Dynamic Priority nice x, for x <= 5
Interactive tasks are favored. The dynamic priority of a task is recalculated when its quantum is expired.
Algorithm Evaluation
A General Procedure
Select criteria that may include several measures, e.g., maximize CPU utilization while confining the maximum response time to 1 second Evaluate various algorithms
Evaluation Methods:
Deterministic modeling Queuing models Simulation Implementation
Deterministic Modeling
A Typical Type of Analytic Evaluation
Take a particular predetermined workload and defines the performance of each algorithm for that workload
Properties
Simple and fast Through excessive executions of a number of examples, trends might be identified But it needs exact numbers for inputs, and its answers only apply to those cases
Being too specific and requires too exact knowledge to be useful!
Deterministic Modeling
FCFC
P1 0
process CPU Burst time P1 10 P2 29 P3 3 P4 7 P5 12
P2 10
P3 P4 39 42 49
P5 61
Average Waiting Time (AWT)=(0+10+39+42+49)/5=28 Nonpreemptive Shortest Job First
P3 P4 P1 P5 0 3 10 20 32
AWT=(10+32+0+3+20)/5=13 Round Robin (quantum =10)
P2 61
P1 0
P2 P3 P4 P5 P2 P5 P2 10 2023 30 40 50 52 61
AWT=(0+(10+20+2)+20+23+(30+10))/5=23
Queueing Models
Motivation:
Workloads vary, and there is no static set of processes
Models (~ Queueing-Network Analysis)

Workload:
a. Arrival rate: the distribution of times when processes arrive. b. The distributions of CPU & I/O bursts
Service rate
Queueing Models
Model a computer system as a network of servers. Each server has a queue of waiting processes
Compute average queue length, waiting time, and so on.
Properties:
Generally useful but with limited application to the classes of algorithms & distributions Assumptions are made to make problems solvable => inaccurate results
Queueing Models
Example: Littles formula
n = w
w
steady state!
n = # of processes in the queue = arrival rate = average waiting time in the queue If n =14 & =7 processes/sec, then w = 2 seconds.
Simulation
Motivation:
Get a more accurate evaluation.
Procedures:
Program a model of the computer system Drive the simulation with various data sets
Randomly generated according to some probability distributions
=> inaccuracy occurs because of only the occurrence frequency of events. Miss the order & the relationships of events.
Trace tapes: monitor the real system & record the sequence of actual events.
Simulation
Properties:
Accurate results can be gotten, but it could be expensive in terms of computation time and storage space. The coding, design, and debugging of a simulator can be a big job.
Implementation
Motivation:
Get more accurate results than a simulation!
Procedure:
Code scheduling algorithms Put them in the OS Evaluate the real behaviors
Implementation
Difficulties:
Cost in coding algorithms and modifying the OS Reaction of users to a constantly changing the OS The environment in which algorithms are used will change
For example, users may adjust their behaviors according to the selected algorithms => Separation of the policy and mechanism!

Uos2005 Chp5

Uploaded by

Copyright:

Available Formats

Uos2005 Chp5

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Uos2005 Chp5

Uploaded by

Copyright:

Available Formats

Chapter 5 Process Scheduling

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

24 16 Burst Duration (ms)

E.g., Windows 3.1

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

First-Come, First-Served Scheduling (FCFS)

First-Come, First-Served Scheduling (FCFS)

Average waiting time P2 P3 24 27 30 = (0+24+27)/3 = 17 Average waiting time P1 30 = (6+0+3)/3 = 3

First-Come, First-Served Scheduling (FCFS)

All other processes wait for it to get off the CPU!

Shortest-Job-First Scheduling (SJF)

Average waiting time = (3+16+9+0)/4 = 7

Shortest-Job-First Scheduling (SJF)

Prediction of the next CPU burst time?

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Shortest-Job-First Scheduling (SJF)

Shortest-Job-First Scheduling (SJF)

* Context switching cost ~ modeling & analysis

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Average waiting time = (6+0+16+18+1)/5 = 8.2 P1 6 P3 P4 16 18 19

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Round-Robin Scheduling (RR)

Interrupt at every time quantum (time slice)

Goal: Fairness Time Sharing

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Round-Robin Scheduling (RR)

P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30 AWT = ((10-4) + (4-0) + (7-0))/3 = 17/3 = 5.66

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Round-Robin Scheduling (RR)

quantum context switch # 12 0 6 1 1 9

If context switch cost = 10% time quantum

Round-Robin Scheduling (RR)

Multilevel Queue Scheduling

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Multilevel Queue Scheduling

b. Time slice between queues

Multilevel Feedback Queue Scheduling

Multilevel Feedback Queue Scheduling

A common ready queue for all processors.

Issues: Process Synchronization

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Multiple-Processor Scheduling SMT Superscalar SMT

Utilization++ Throughput++ Performance++

occupied issue slot unused issue slot

System-Contention Scope (SCS): 1:1

Operating System Examples

System Global Scheduling

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Operating System Examples Solaris

Each LWP inherits its class from its parent process

Operating System Examples Solaris

Operating System Examples Solaris

Interactive and time sharing threads

* All rights reserved, Tei-Wei Kuo, National Taiwan University, 2005.

Operating System Examples Solaris

RR is used when several threads have the same priority.

Operating System Examples Solaris