Lecture Notes for Operating Systems Concepts

28 September 2004 - Scheduling

Outline

Scheduling mechanisms.
Scheduling strategy.
- Eviction and selection strategies.
Implementation details.
Examples

The Scheduler

The scheduler manages the CPUs.
- Shepherds processes to and from the CPU.
- Implements the multi-CPU abstraction.

Process Behavior

Processes lead a simple life.
Blocked processes are not runnable and not ready to run for whatever reason.
The scheduler is responsible for implementing the arrows.

Process Actions

From the state diagram, processes spend their lives running and not running.
- Not running includes blocked and ready.

Process Classes

You can classify processes based on their running and non-running behaviors.
Compute-bound vs. IO-bound computations.

Scheduler Mechanisms

To do process shepherding, the scheduler must
- Evict the CPU resident process.
- Select the replacement process.
To do the multi-CPU abstraction, the scheduler must do the between processes.
- This is also required for process shepherding.

Performance

Schedulers can be judged by how they effect
- overall system performance and
- individual process performance.
These two measurements are frequently in conflict.
- The good of the many vs. the good of the few.

System Performance Measures

Throughput is the number jobs per second.
- High throughput is good.
Utilization is the system busy percentage.
- High utilization is good.
An average of any of the individual process measures.
- High average responsiveness or low average turnaround.

Process Performance Measurements

Service time is the amount of time needed to complete process execution.
Wait time is the time between process entry and first process execution.
Turnaround time is the time between first execution and last execution.
Response time is the time between IO completion and execution in response.

Scheduler Classification

Schedulers can be classified along two dimensions:
1. When they evict the running process.
2. How they select the next running process.

These are the eviction algorithm and selection algorithm respectively.

Each choice of an eviction and selection algorithm leads to a scheduler.

First Come First Serve Selection

Processes gain the CPU in the order they entered the system.
- Treat the ready queue as a queue.
- Assign entry time as the process priority.
  - The ready queue is a priority queue.
- These are not the same under pre-emption.

FCFS Analysis

FCFS selection is easy to implement.
- A strict queue and a simple selection algorithm.
Entry time is a weak property; other, more important properties are ignored.
Except for "queue fairness", FCFS selection is unlikely to provide useful results.

Shortest Job Next Selection

Each process declares its expected compute time.
Order the ready queue by increasing compute time.
Select the head of the queue.
- This is the process with the shortest estimated execution time.

SJN Analysis

SJN minimizes average wait time.
- All the processes in front of you have the smallest possible execution times.
Large duration jobs may be starved.
Accurate job-duration estimates are hard to make.

Priority Selection

Each process P_i has an ordered value p_i called its priority.
- Priority is assigned externally to the OS.
P_i is selected before P_j if p_i < p_j.
Priority assignments may be static or dynamic.
- Dynamic adjustments may be made within the OS or outside it.

Priority Analysis

Priority selection is the most general policy.
- All other selection schemes can be implemented as some variant of dynamic priority selection.
Starvation is possible, particularly with static priorities.
Dynamic priorities make it possible for the OS to react to changing conditions.

Deadline Selection

A periodic process executes every t ticks.
- And has a deadline of t + d.
Select the process with the closest deadline.
- This algorithm should be faimilar to all students.

Round Robin Selection

Strict ready-queue order.
- Evicted processes go to the end of the queue.
With voluntary eviction, this is equivalent to FCFS scheduling.

Non-Pre-Emptive Eviction

The process leaves the CPU when it's good and ready.
- It voluntarily suspends execution.
- It terminates.
The scheduler is powerless to evict the process.
- Except for the OS itself.

Voluntary Eviction

The executing process determines when it leaves the CPU.
- via a yield() or sleep() system call, for example.
Removing pre-emption simplifies the scheduler and decreases scheduling overhead.
Non-pre-emption works well for small, compute-bound sets of processes.

Involuntary Eviction

The scheduler can evict the executing process arbitrarily.
- The process can still voluntarily leave the CPU.

Selection-Based Eviction

Process P_i is executing under SJN selection with expected time t_i.
Process P_j joins the ready queue with expected time t_j < t_i.
To maintain the SJN policy, the scheduler should replace P_i with P_j.
This is known as selection-based eviction.
- Similarly for pure priority selection.

Quantum-Based Eviction

Each process is allowed to occupy the CPU for a specific time known as the quantum (also known as the time slice).
- When the quantum expires, the process is evicted.
Quantum-based eviction and round-robin selection leads to time-sharing OSs.

Single Scheduler Problems

What happens when selection produces several candidate processes?
- Several processes with the same priority, or job time, or deadline.
One scheduler can't meet all process expectations.
- And those that try get complicated quickly.
An OS may support multiple process classes.
- Foreground and background processes, for example.

Multi-Scheduler Systems

Using two or more schedulers can solve these problems.
- At an increase in complexity and scheduling overhead.
Multiple schedulers often uses multiple ready queues.
- On scheduler can move processes between queues.

Implementation Details

Scheduler implementations have to be efficient.

Context Switching

Examples

Linux Scheduling

BSD Unix Scheduling

Windows Scheduling

This page last modified on 14 November 2004.