Transcript Scheduling

Cosc 4740
Chapter 5
Process Scheduling
CPU Scheduling
• Short-term Scheduler
– Selects a process from the ready queue when
current process releases the CPU
– Very Fast to avoid wasting CPU time
– Very efficient
• the problem: selecting a CPU algorithm for a
particular system
• Also updates PCBs and controls the queues.
Basic concept of a Process
• CPU–I/O Burst Cycle
– Process execution
consists of a cycle of
CPU execution and I/O
wait
• How to decide which ready process to put
on the CPU next?
Goals
1.
Fairness or Waiting time
•
•
2.
CPU utilization – keep it busy most of the time
•
3.
4.
normally about 40-90% of the time
Response time – for interactive users
Turnaround time
•
5.
amount of time a process has been waiting in the ready queue
– No process will wait “too” long
the time of completion from submission
Throughput:
•
# of processes that complete their execution per time unit
Consider if it is possible to Max all 5 goals
• We want to optimize all the goals
– This is not possible:
• Fairness vs CPU utilization
• All schedulers favor a couple of goals.
– Normally those goals that help the kind of
system it written for.
CPU Scheduler
• Selects from among the processes in memory that are
ready to execute, and allocates the CPU to one of them
• CPU scheduling decisions may take place when a
process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
• Scheduling under 1 and 4 is nonpreemptive
• All other scheduling is preemptive
Dispatcher
• Dispatcher module gives control of the CPU to
the process selected by the short-term scheduler;
this involves:
– switching context
– switching to user mode
– jumping to the proper location in the user program to
restart that program
• Dispatch latency – time it takes for the
dispatcher to stop one process and start another
running
Types of Scheduling Algorithms
• Non-preemptive Scheduling
– A running process is only suspended when it
blocks or terminates
– Pros:
• Decreases turnaround time, high CPU utilization
• Does not require special HW (like a timer)
– Cons:
• Poor performance for response time and fairness
• Limited choice of scheduling Algorithms
• Preemptive scheduling
– A Running process can be taken off the CPU for any
(or no) reason. Suspended by the scheduler
– Pros:
• No limitations on the choice of scheduling algorithms
• Increased Fairness and response time
– Cons
• Addition overheads (frequent context switching)
• deceased CPU utilization and longer turnaround time
FCFS scheduling
• First-Come First Served (non-preemptive)
– CPU is allocated to the process that requests it first
• Pros:
– Simple to understand and implement
– Very fast selection for scheduling
• Cons:
– Avg. waiting time is long and varies
– Not suitable for time-sharing OS
FCFS Example 1
Process Burst Time
P1
24
P2
3
P3
3
• Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1
0
P2
24
P3
27
• Waiting time for P1 = 0; P2 = 24; P3 = 27
• Average waiting time: (0 + 24 + 27)/3 = 17
30
FCFS Example 2
Suppose that the processes arrive in the order
P2 , P3 , P1
• The Gantt chart for the schedule is:
P2
0
•
•
•
•
P3
3
P1
6
30
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than previous case
Convoy effect short process behind long process
SJF Scheduling
• Shortest Job Next: Preemptive or NonPreemptive
• Pros:
– Yields minimum avg. waiting time for a given
set of processes
• Cons:
– Difficult to estimate CPU burst time
– Starvation (indefinite blocking)
Example of Non-Preemptive SJF
Process Arrival Time
P1
0.0
P2
2.0
P3
4.0
P4
5.0
• SJF (non-preemptive)
P1
0
3
P3
7
Burst Time
7
4
1
4
P2
8
P4
12
• Average waiting time = (0 + 6 + 3 + 7)/4 = 4
16
Example of Preemptive SJF
Process Arrival Time
P1
0.0
P2
2.0
P3
4.0
P4
5.0
• SJF (preemptive)
P1
0
P2
2
P3
4
P2
5
Burst Time
7
4
1
4
P4
7
P1
11
• Average waiting time = (9 + 1 + 0 +2)/4 = 3
16
Determining Length of Next
CPU Burst
• Can only estimate the length
• Can be done by using the length of previous
CPU bursts, using exponential averaging
1. t n  actual length of n th CPU burst
2.  n 1  predicted value for the next CPU burst
3.  , 0    1
4. Define :  n 1   t n  1    n .
Round Robin Scheduling
•
•
•
•
•
Preemptive scheduling
Most widely used algorithm
Very simple – CPU isn’t taxed by scheduler
Fair
Each Process is allowed a time interval call
a “quantum” or “time slice”
– Max time process can run on CPU
• If a process is still running at the end of a
quantum, the scheduler preempts it.
• If a process blocks or terminates before it quantum
expires, another is allocated immediately
CPU
Ready queue
O
PQRS
(Then quantum expiries)
P
QRSO
Example of RR
Time Quantum = 20
Process
P1
P2
P3
P4
• The Gantt chart is:
P1
0
P2
20
37
P3
Burst Time
53
17
68
24
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
• Typically, higher average turnaround than SJF, but better
response time
Quantum
• How long should a quantum be?
• Problems:
– quantum is too small (20 ms)
• CPU is under utilized – to much context switching
– quantum is too large (1 second)
• Not fair, poor response time
• Typical quantum between 100ms and
200ms
– When O/S is installed it is tested and adjusted
for specific environment
• OS could monitor itself, but it is complex
– scheduler would not be simple
– So normally done by “hand”.
Priority Scheduling
• Not all processes are equally important
• Each process is assigned a priority (integer
value)
• Process with highest priority runs
• If more than 1 with same highest priority,
then Round Robin among those processes
Priority Scheduling (2)
• A priority number (integer) is associated with each
process
• The CPU is allocated to the process with the highest
priority (smallest integer  highest priority)
– Preemptive
– nonpreemptive
• SJF is a priority scheduling where priority is the
predicted next CPU burst time
• Problem  Starvation – low priority processes may
never execute
Priority Scheduling (3)
• Array of priority queues
Highest
0 PQR
1 OS
2
3 A
Lowest
4C
• Priority must change over time, or low priority
processes will suffer (starve)
– Solution  Aging – as time progresses increase the
priority of the process
Multiple Queue with Dynamic
Priority
• Priority of processes changes dynamically
• Processes are divided into 2 classes
– CPU bound – computation intensive
– I/O bound – most of time I/O is used
• Who should be giving higher priority?
• If you know which the process is:
– I/O bound uses processor for short time, then
I/O operations
– So I/O bound will leave the CPU sooner, then
CPU bound processes
– So give I/O bound higher priority.
• Should quantum size be the same for I/O
and CPU bound processes?
• Vary quantum size w/ dynamic priority
– Higher priority will get lower quantum, since it
is I/O bound and won’t need it for long
Priority
0
1
2
3
Quantum
1 Unit Highest priority/lowest quantum
2 Units
4 Units
8 Units Lowest priority/highest quantum
• How do you know if the process is I/O or
CPU bound??
• It can even change as a processes runs!
• We figure it dynamically
– If a running process uses it’s quantum, then
lower the priority by 1
– If a running process blocks, the raise priority by
1
– Start new process with priority of 0 (highest)
• If I/O bound – we did it right
• If CPU bound – quantum is small anyway.
• Interactive process respond quickly and are
usually I/O bound.
– So good response time
• Fair, since CPU bound process get a longer
quantum as they run.
• Works well when a process changes from
CPU to I/O bound or vise versa.
Multi-Processor Scheduling
• Very complex
• Depends on the underlying HW structure
• Heterogeneous processors: Difficult!
– Process may have code compiled for only 1
CPU.
• Homogeneous processors with separated
ready queues
o load balancing problem
Multi-Processor Scheduling (2)
• Homogeneous processors with shared ready queue
o Symmetric: Processors are self-scheduling
o Need to be synchronized to access the shared ready queue to
prevent multiple processors trying to load the same process in
the queue.
o Asymmetric: There is one master processor who
distributes next processes to the other processors.
• Simpler than symmetric approach
NUMA and CPU Scheduling
Note that memory-placement algorithms can also
consider affinity
Multi-Processor Scheduling (3)
• Processor affinity – process has affinity for
processor on which it is currently running
– soft affinity
– hard affinity
– Variations including processor sets
Real Time Systems
• An absolute deadline for process execution must
be met.
• these take the additional parameter of deadline
into account in scheduling
ie:
P1
P2
P3
P4
P5
deadline
10:00 10:05 9:00 11:00 11:10
• Assign CPU to the process that is in the greatest
danger of missing it’s deadline.
• Hard real-time systems
– guaranteed amount of time. Special purpose
hardware/software machines
• Soft real-time systems
– Based on priority based scheduling.
– Even kernel must be pre-emptive so a critical process
can run.
– Resource allocation is “pre-emptive”. If a critical
process (A) needs a resourced owned by another
process (B), that process B gets process A priority, so it
can release the resource. Once processes B released the
resource it priority is returned to “normal”.
Windows Scheduling
• Windows uses priority-based preemptive scheduling
• Highest-priority thread runs next
• Thread runs until (1) blocks, (2) uses time slice, (3)
preempted by higher-priority thread
• Real-time threads can preempt non-real-time
• 32-level priority scheme
• Variable class is 1-15, real-time class is 16-31
• Priority 0 is memory-management thread
• Queue for each priority
• If no run-able thread, runs idle thread
Windows Priority Classes
• Win32 API identifies several priority classes to which a process can
belong
– REALTIME_PRIORITY_CLASS, HIGH_PRIORITY_CLASS,
ABOVE_NORMAL_PRIORITY_CLASS,NORMAL_PRIORITY_CLAS
S, BELOW_NORMAL_PRIORITY_CLASS, IDLE_PRIORITY_CLASS
– All are variable except REALTIME
• A thread within a given priority class has a relative priority
– TIME_CRITICAL, HIGHEST, ABOVE_NORMAL, NORMAL,
BELOW_NORMAL, LOWEST, IDLE
•
•
•
•
•
Priority class and relative priority combine to give numeric priority
Base priority is NORMAL within the class
If quantum expires, priority lowered, but never below base
If wait occurs, priority boosted depending on what was waited for
Foreground window given 3x priority boost
Windows XP Priorities
Linux Scheduling
•
•
•
•
•
•
•
•
•
Constant order O(1) scheduling time
Preemptive, priority based
Two priority ranges: time-sharing and real-time
Real-time range from 0 to 99 and nice value from 100 to 140
Map into global priority with numerically lower values indicating
higher priority
Higher priority gets larger q
Task run-able as long as time left in time slice (active)
If no time left (expired), not run-able until all other tasks use their
slices
All run-able tasks tracked in per-CPU runqueue data structure
– Two priority arrays (active, expired)
– Tasks indexed by priority
– When no more active, arrays are exchanged
Linux Scheduling (Cont.)
• Real-time scheduling according to POSIX.1b
– Real-time tasks have static priorities
• All other tasks dynamic based on nice value
plus or minus 5
– Interactivity of task determines plus or minus
• More interactive -> more minus
– Priority recalculated when task expired
– This exchanging arrays implements adjusted
priorities
Priorities and Time-slice length
List of Tasks Indexed
According to Priorities
Choosing an Algorithm
• There is no “best” algorithm, just better
suited.
• Need to choose the goals that are more
important to the environment.
Memory and Processes
• When main memory is insufficient, some
processes will be “swapped out” and ready
to run.
• Short-term schedulers works with mediumterm scheduler to bring these process back
into memory.
– Why not just have the Short-term Scheduler do
the work?
Q&A