OS Notes
Processor Scheduling
Introduction
Terms
- scheduler
- The part of an operating system which assigns resources to processes, tasks, or threads.
- dispatcher
- The operating system component which transitions a process to the running state.
Remarks
- The dispatcher moves one task at a time from a
ready queue to the run state.
- The dispatcher is also referred to as the short term scheduler.
Scheduling Levels
Terms
- long term scheduler
- The part of an operating system which places new tasks into the ready state.
Remarks
- The dispatcher is also referred to as the low-level scheduler.
- The long term scheduler is also referred to as the high-level scheduler.
Preemptive vs. Nonpreemptive Scheduling
Terms
- preemption
- The operating system act of interrupting a running task, removing it from the run state, and placing it in the ready state.
- preemptive
- Having the capability of preempting running tasks.
- nonpreemptive
- Not having the capability of preempting running tasks.
- quantum
- The maximum run time allowed for a process before preemption.
Remarks
- Preemptive operating systems limit the time that
a process can remain in the run state.
- In some systems, the maximum time (the time quantum, or time slice)
is the same for all tasks.
- In some systems, the quantum can be set for each process or class
of processes separately.
- Nonpreemptive operating systems allow a task
to remain in the run state until it voluntarily blocks itself
(usually by an I/O request) or completes.
- Modern operating systems are typically preemptive.
- Each context switch imposes an overhead of processing time on the system.
Priorities
Terms
- priority
- An index of importance which can be used to determine scheduling
- static priority
- A priority which is not automatically adjusted by the system.
- dynamic priority
- A priority which is adjusted automatically by the system according to task behavior and system loading.
Remarks
- Static priority can typically be changed by a user or superuser.
- Dynamic priority imposes an overhead on the system.
- Dynamic priority can improve response times and eliminate indefinite postponent.
Scheduling Objectives
Remarks
- Maximize throughput
- Maximize system utilization
- Minimize system overhead
- Minimize average response time
- Minimize maximum response time
- Minimize average turnaround time
- Minimize maximum turnaround time
- Maximize "fairness"
- Minimze failures
- Maximize reliability
- Eliminate indefinite postponement
- Maximize predictability (consistency)
- These objectives sometimes conflict with each other.
Scheduling Criteria
Terms
- I/O bound
- A property of a process in which processor use is low, and I/O requests are high.
- CPU bound
- A property of a process in which processor use is high, and I/O requests are low.
- batch process
- A process which executes without user interaction.
- interactive process
- A process which requires user interaction while executing.
Remarks
- A CPU bound process is also referred to as processor bound.
- Windows programs are typically interactive.
Scheduling Algorithms
Terms
- priority scheduling
- A scheduling policy which schedules tasks in descending order of priority.
- priority aging
- A process which dynamically raises the priority of a task according to the time it has been waiting in the ready queue.
- FIFO scheduling
- A scheduling policy which schedules tasks in the same order in which they enter the ready state.
- Round Robin scheduling
- A scheduling policy which scheduleses tasks in a fixed circular order.
- shortest process first scheduling
- A scheduling policy which schedules tasks in ascending order of estimated processing time.
- shortest remaining time scheduling
- A scheduling policy which schedules tasks in ascending order of estimated remaining processing time.
- fair share scheduling
- A scheduling policy which assigns tasks to groups, and allocates a percentage of CPU time to each group.
Remarks
- Systems typically use a combination of scheduling algorithms.
Priority Scheduling
- A priority scheduling policy dispatches the task with the highest priority.
- Priority aging can be used to reduce starvation of low priority tasks.
First-in-First-out (FIFO) Scheduling
- FIFO scheduling is also referred to as First-Come-First-Served (FCFS).
Round-Robin (RR) Scheduling
- RR scheduling may be used for time sharing users.
Shortest-Process-First (SPF) Scheduling
- SPF scheduling is also referred to as Shortest Job Next (SPN).
- SPF scheduling is also referred to as Shortest Job First (SJF).
- SPF scheduling requires the processing time of each task to be estimated.
- SPF scheduling may be used by a long term scheduler.
- SPF scheduling may be used for batch processing.
- Penalties may be assessed when processing time is understated - e.g., kill the task.
Highest-Response-Ratio-Next (HRRN) Scheduling
| resonse ratio |
= | wait time + expected service time |
|---|
|
| expected service time |
|---|
- Wait time and response ratio are recalculated each time a task is to be dispatched.
- The task with the greatest response ratio is dispatched.
- Expected service time is recalculated each time a process leaves the run state.
- HRRN scheduling prevents indefinite postponement;
each time a task is passed over for scheduling,
its response ratio is raised, and eventually it
will be dispatched.
- The effect of HRRN scheduling is similar to priority aging.
- HRRN scheduling may be used by a short term scheduler.
Shortest-Remaining-Time (SRT) Scheduling
- SRT scheduling, like SPF scheduling, requires an estimate of process time.
- SRT scheduling may be used for short term scheduling.
- SRT is recalculated every time a task leaves the run state.
Multilevel Feedback Queues
- Tasks are grouped into separate groups, or queues.
- Each queue is assigned a priority.
- The dispatcher chooses between queues based on priority.
- The dispatcher chooses from a queue using round robin or FIFO.
- New tasks entering the system are put into the highest priority queue.
- A task which uses its time slice, and is prempted, is moved to the next lower queue.
- A task which does not use its time slice, and is voluntarily blocked, is moved to the next higher queue.
- As a refinement, movement from the lower queues may be postponed
until the task behaves the same way several times.
- There may be a lowest level queue, below which no task can fall.
Deadline Scheduling
Terms
- deadline scheduling
- A scheduling algorithm which dispatches the process with the closest deadline.
Remarks
- deadline scheduling can be used for short-term
scheduling in real time systems.
- Deadline scheduling can consider a number of factors, such as
- Ready time: The time at which a task is ready to be run
- Starting deadline: The time at which a task must start to successfully complete
- Completion deadline: The time at which a task must complete in order to be successful
- Processing time: The time a task needs to execute completely
- Priority: This is the same concept as with multiprogrammed, mono-processor machines
Real Time Scheduling
Terms
Remarks
- Real time systems are used for controlling industrial processes,
cars, robots, and other time critical applications.
- Real time systems often have a fixed set of tasks.
- Reliability is also an important, if not mandatory, goal for
real time systems
Java Thread Scheduling
Remarks
- The Java Virtual Machine (JVM) uses preemptive time slicing.
- The JVM uses preemptive priority based scheduling,
with round robin scheduling being
used for threads with the same priority.
- A Java thread can leave the run state by
- being preempted
- blocking itself with an I/O request
- blocking itself for a specified time with the sleep method.
- voluntarily returning to the ready state with the yield method.
External Links
List of Terms
