operating system
CMET 331 Operating Systems
5. CPU Scheduling
Outline • Basic Concepts • Scheduling Criteria • Scheduling Algorithms • Algorithm Evaluation
Basic Concepts • In a signal-processor system, only one process
can run at a time. The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization
• CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait
• CPU burst distribution
Alternating Sequence of CPU And I/O Bursts
Process Behavior
Bursts of CPU usage alternate with periods of waiting for I/O. (a) A CPU-bound process. (b) An I/O-bound process.
Histogram of CPU-burst Times
CPU Scheduler • Whenever the CPU becomes idle, the operating
system must select one of the processes in the ready queue to be executed.
• The selection process is carried out by the short-term scheduler (or CPU scheduler)
• Note that the ready queue is not necessarily a first-in, first-out (FIFO) queue.
When to Schedule • When scheduling is absolutely required:
1. When a process exits. 2. When a process blocks on I/O
• When scheduling usually done (though not absolutely required)
1. When a new process is created. 2. When an I/O interrupt occurs. 3. When a clock interrupt occurs.
Scheduling Criteria • CPU utilization – keep the CPU as busy as
possible • Throughput – number of processes that
complete their execution per time unit • Turnaround time – amount of time to execute a
particular process • Waiting time – amount of time a process has
been waiting in the ready queue • Response time – amount of time it takes from
when a request was submitted until the first response is produced, not output (for time- sharing environment)
Optimization Criteria • Max CPU utilization • Max throughput • Min turnaround time • Min waiting time • Min response time
Scheduling Algorithms • CPU scheduling deals with the problem of
deciding which of the processes in the ready queues is to be allocated the CPU.
• There are many different CPU scheduling Algorithms —First-Come, First-Served Scheduling —Shortest-Job-First Scheduling —Priority Scheduling —Round Robin Scheduling —Multilevel Queue Scheduling —Multilevel Feedback Queue Scheduling
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:
• Waiting time for P1 = 0; P2 = 24; P3 = 27 • Average waiting time: (0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 300
First-Come, First-Served (FCFS) Scheduling
FCFS Scheduling (Cont.) Suppose that the processes arrive in the order
P2 , P3 , P1 • The Gantt chart for the schedule is:
• 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
P1P3P2
63 300
Shortest-Job-First (SJF) Scheduling • Associate with each process the length of its
next CPU burst. Use these lengths to schedule the process with the shortest time
• Two schemes: —nonpreemptive – once CPU given to the process it
cannot be preempted until completes its CPU burst —preemptive – if a new process arrives with CPU burst
length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF)
• SJF is optimal – gives minimum average waiting time for a given set of processes
Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4
• SJF (non-preemptive)
• Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Example of Non-Preemptive SJF
P1 P3 P2
73 160
P4
8 12
Example of Preemptive SJF Process Arrival Time Burst Time
P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4
• SJF (preemptive)
• Average waiting time = (9 + 1 + 0 +2)/4 = 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
Problem: How to Determine the Length of Next CPU Burst • No accurate way - can
only estimate. • Can be done by using the
length of previous CPU bursts, using exponential averaging
:Define 4. 10 , 3.
burst CPU next the for value predicted 2. burst CPU of length actual 1.
1n
th n nt
1 1 .n n nt
Prediction of the Length of the Next CPU Burst
Examples of Exponential Averaging • =0
—n+1 = n —Recent history does not count
• =1 — n+1 = tn —Only the actual last CPU burst counts
• If we expand the formula, we get: n+1 = tn+(1 - ) tn -1 + …
+(1 - )j tn -j + … +(1 - )n +1 0
• Since both and (1 - ) are less than or equal to 1, each successive term has less weight than its predecessor
• Each process has a priority number. • The process with the highest priority is
scheduled: —Non-preemptive. —Preemptive.
• Shortest Job First is a priority scheduling. How is that?
Priority Scheduling
• Each process has a priority number. • The process with the highest priority is
scheduled: —Non-preemptive. —Preemptive.
• Shortest Job First is a priority scheduling where the priority is the predicted next CPU burst time.
• What is the problem with priority scheduling in general?
Priority Scheduling
• Each process has a priority number. • The process with the highest priority is
scheduled: —Non-preemptive. —Preemptive.
• Shortest Job First is a priority scheduling where the priority is the predicted next CPU burst time.
• Problem: Starvation of low priority processes. • Solution: Aging - as time progresses, increase
the priority of a process
Priority Scheduling
Round Robin (RR) • Each process gets a CPU time quantum, usually 10-
100 milliseconds. After that, it is preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time quantum is q then each process gets 1/n of the CPU time in chunks of at most q units at once. No process waits more that (n-1)q time units to be scheduled.
• Performance: .
— Large q => FCFS. — Small q => Context switch overhead!
Process Burst Time P1 53 P2 17 P3 68 P4 24
• The Gantt chart is:
• Typically, higher average turnaround than SJF, but better response
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
Example of RR with Time Quantum = 20
Activate the application
• Example: Process: p1 p2 p3 p4 Required time: 6 3 1 7
• Schedule: It depends! (on the quantum size)
Question: In general, what would be a good quantum Hint: think of context switch overhead?
Quantum size: 1 2 3 4 5 6+ Average
turnaround time: 11 11.5 10.75 11.5 12.25 10.5
Round Robin: Another example
Turnaround Time Varies With The Time Quantum
Three Level Scheduling
Three-level scheduling.
Multilevel Queue • Ready queue is partitioned into separate
queues. For example: —Foreground (interactive) —Background (batch)
• Each queue has its own scheduling policy. • Inter-queue scheduling. For example:
—Fixed priority scheduling (starvation?). —Time slice between the queues. For example:
• 80% to interactive, 20% to batch. • Think about interference.
Multilevel Queue (Example)
Processor
Ready queue 1
Ready queue 2
Ready queue 3
System processes
SJF
Interactive processes
Round Robin
Batch processes
FCFS
Some Inter-queue scheduling policy.
• A process can move between the various queues. A way to implement aging.
• Multilevel feedback queue scheduler is defined as follows: —number of queues. —scheduling policy for each queue. —method used to upgrade a process. —method used to degrade a process. —method used to introduce a process (which queue) —inter-scheduling between the queues (usually strict
priority).
Multilevel Feedback Queue
Multilevel Feedback Queue (cont.) • Example.
—Three queues: • Q1 - time quantum is 10 milliseconds, FCFS. • Q2 - time quantum is 40 milliseconds, FCFS. • Q3 - First Come First Serve.
—Scheduling: • A new process enters Q1. If it does not complete in first
quantum, it is degraded to Q2. If it does not complete in first quantum, it is degraded to Q3.
• Inter queue scheduling is strict priority.
Multilevel Feedback Queues
• Deterministic modeling (as we did today): —predefined workload and a defined criterion.
• Queuing models: —predefined arrival and service processes and a
defined criterion. • Simulation:
—Simulation assumptions. • Implementation.
How to Evaluate Scheduling Algorithms?
End of Chapter 5