CPU Scheduling
Resources: the things operated on by processes.
Resources ranges from CPU time to disk space, to I/O
channel time.
Resources fall into two classes:
(1)Preemptive:
OS can take resource away. Use it for something else,
and then give it back later.
Examples: processor or I/O channel.
(2)Non-preemptive:
Once given, it cannot be reused until the process gives it
back. Examples: file space and terminal.
Anything is preemptive if it can be saved and restored.
CPU Scheduling
O.S. makes two related kinds of decisions about resources:
(1) Allocation:
Who gets what? Given a set of requests for
resources, which process should be given which
resources in order to make most efficient use of the
resources?
(2)Scheduling: How long can they keep it? When more
resources are requested than can be granted
immediately, in which order should hay be served?
Examples: processor scheduling and memory scheduling
(virtual memory).
Resource # 1: the processor.
Processes may be in any one of three general scheduling
states: Running, ready and blocked.
CPU Scheduling
Criteria for a good scheduling algorithm:
1. Fairness: every process gets its fair share of CPU.
2. Efficiency (utilization): keep CPU busy.
3. Response time: minimize response time for interactive
users.
4. Throughput: maximize jobs per hour.
5. Minimize overhead (context swaps).
Context switch: changing process. Include save and load
registers and memory maps and update misc tables and
lists.
Clock interrupt: Clock interrupt occurs at fixed time
interval (for 60 Hertz AC frequency, 60 times per second)
and O.S. scheduler can run. Every interrupt is called a
clock tick (a basic time unit in computer systems).
Scheduling – 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.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Categories of Scheduling
Algorithms
• Batch
• Interactive
• Real time
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Scheduling Algorithm Goals
Some goals of the scheduling algorithm under
different circumstances.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Times used in Scheduling
Arrival Time
Burst Time
Completion Time
Turnarounnd Time
Waiting Time
Scheduling in Batch Systems
• First-come first-served (FCFS)
• Shortest job first(SJF)
• Shortest remaining time next(SRTN)
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
First IN First Out (FIFO or FCFS)
Run until finished, usually “finished" means
“blocked." Process goes to the back of run queue
when ready.
Problem: one process can dominate the CPU.
Solution: limit the maximum time that a process can
run without a context switch. The time is called
quantum or time slice.
Shortest Job First (SJF)
• Suitable to batch system.
• Non-preemptive policy.
• Must know the runtime or estimate
runtime of each process.
• All jobs are available at system start-up time.
• Schedule the jobs according to their runtimes.
• Optimal with respect to average turnaround time.
Shortest Remaining Time Next(SRTN)
• A preemptive version of shortest job first
• Scheduler always chooses the process
whose remaining run time is the
shortest.
• Allows new short jobs to get good service
Scheduling in Interactive Systems
• Round-robin scheduling
• Priority scheduling
• Guaranteed scheduling
• Lottery Scheduling
• Fair Share Scheduling
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Round-Robin Scheduling
• Maintain a list of runnable processes.
• Run a process for one quantum then move to
the back of queue. Each process gets equal share
of the CPU.
• If process blocks (say, for I/O or semaphore) then
remove it from the queue and start to run the next
process in queue.
• If a process becomes runnable, add it to the end of
queue.
• Length of quantum:
• Short: too much overhead
• Long: poor response time
• In general: about 100 ms (or about 10K -100K
instructions)
Priority Scheduling
Assign each process a priority. Run the runnable
process with the highest priority.
How to assign priority:
I/O bound jobs have higher
priority CPU bound jobs have
lower priority
If a job uses 1/f of the quantum, then Priority = f.
Unix command “nice" allows a user to lower the job
priority voluntarily.
Problem: high priority job may dominate CPU.
Solution: decrease priority of the running process
at each clock tick (dynamic priority).
Note: Refer Notes/ Galvin text book for all the scheduling algorithm
examples
