Operating Systems Lecture Notes

2014 September 23 • Scheduling

---

Outline

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

The Story So Far

• A system accepts processes and runs them until they're done.

  

• The system and processes should behave in desirable ways.
  • Processes should move through the system as quickly as possible.
  • All parts of the system should be busy all the time.

Promises

• The operating system magically multiplies system facilities.
  • Threads and the virtual CPU.
• The operating system provides an imaginary environment for processes.
  • An isolated process running in its own system.
• The operating system provides dials a process uses to manipulate its environment.

The Problem

• How should the system and processes be managed to behave properly?
• How should the operating system fulfill its promises?
• How should the conflict between the previous two questions be resolved?
• The scheduler plays a large part in answering these questions.

A Simple Solution

• The simplest possible answer to these questions is to admit one process at a time.

  

  • The scheduler admits the next waiting process.
  • The process in the system executes until it's done.
• Is this a solution? Is it a good solution?

Analysis

• The simple solution
  • solves some problems (virtual machines),
  • doesn't solve some problems (system utilization), and
  • is unclear on some problems (abstract CPUs).
• A more detailed analysis requires sharper criteria.

Scheduler Criteria

• Schedulers can be judged by how they effect
  • overall system performance and
  • individual process performance.
  • Other, larger criteria (efficiency, convenience, protection).
• Schedulers can also be judged on less (or non-) functional criteria.
  • How well a scheduler supports other OS abstractions.

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.

Process Measures Example

• The one-at-a-time scheduler does well on all process performance measurements.
  • Wait and response times are zero.
  • Service and turnaround times are equal.
• That's just ducky. Or is it?

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 individual process measures.
  • High average responsiveness or low average turnaround.

System Measures Example

• The one-at-a-time scheduler provides poor utilization and poor throughput.
  • Poor throughput is perhaps less obvious than poor utilization.
• But it depends on the processes.
  • If processes use everything, then utilization is good.
  • If processes are minimal and simple, then throughput is good.

Conflicts Abound

• System and process criteria often conflict.
  • The good of the many vs. the good of the few.
• Criteria within a category also frequently conflict.
  • Simple vs omnivorous processes and system criteria.
• Schedulers (and operating systems) usually represent these conflicts; they don't resolve them.

Trade-Offs

• Schedulers (and operating systems) usually can't resolve conflict.
  • Resolution requires strong (or arbitrary) assumptions.
• Instead, represent trade-offs as dials in the scheduler (and operating system).
  • More informed parties set the dials to trade-off as appropriate.
  • Performance tuning, for example.

Understanding Trade-offs

• Lots of good knowledge is necessary for
  • representing trade-offs well, and
  • making good trade-offs.
• Processes are central to both system and process trade-offs.
  • Understanding processes and their behavior becomes important.

Process States

• Processes lead a simple life.

  Blocked: a process is unable run. Running: the process is in the CPU.

• Ready: the process can run, but isn't in the CPU.

Process Execution

• From the state diagram, processes spend their lives running and not running.

  

  • Not running includes blocked and ready.
• A process could be not running for many reasons.
  • But usually it's blocked waiting for a resource.

Process Behavior

• Process behavior can be ordered along an activity continuum.

  

• The continuum extremes are Compute-bound and IO-bound computations.

Simple Scheduling Redux

• The simple process model shows how one-at-a-time scheduling fails systems:

  

• Letting in more than one process at a time improves system throughput.
  • Without effecting (too much) system performance.

But Wow

• What does a many-process scheduler have to do?
  • Figure out which processes to admit.
  • Figure out when to admit them.
• And most importantly, figure out how to recover from the mistakes that will inevitably occur.
  • And figure out how to make fewer, less severe mistakes.

Scheduling Illustrated

Scheduling Levels

• There are at least four levels of scheduling possible:
  1. Admission (long-term, job) scheduling.
  2. System (mid-term, process) scheduling.
  3. Device (short-term) scheduling.
  4. Thread scheduling.
• There’s lots of other scheduling going on.
  • Disk-arm scheduling.

Simplifications

• Ignore (mostly) admission and system scheduling.
• Concentrate on the CPU device scheduler.
  • And on the thread scheduler, somewhat.
• The device scheduler works with processes.
  • Thread = process, for the most part.

  

Scheduler Classification

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

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

Eviction Algorithms

• No eviction algorithm: the scheduler never evicts a running process.
• Actual eviction algorithms fall into two categories:
  • Absolute: eviction is well defined, sorta.
  • Relative: eviction depends on other entities, usually processes.

  

No Eviction

• Non-preemptive schedulers don't evict (or preempt) processes.
  • Easy to implement.
  • Misbehaving processes are a problem.
• The OS may provide tools for cooperative scheduling
  • yield() - Move from CPU to ready queue.
  • swap(id) - Swap places with the identified process.

Absolute Eviction

• Quantum schedulers evict running processes at regular intervals.
  • Defining “regular” can be tricky.
• The quantum gives the interval size in time.
  • Quantum size is an important dial in schedulers and OSs.
• Premature eviction can also usually occur.
  • Via cooperative scheduling, or obvious eviction points.

Relative Eviction

• Priority schedulers evict processes to maintain a priority invariant.
• Each process is assigned a comparable value called a priority.
  • Priority assignment is another important dial.
• The priority invariant constrains running process relative to the waiting process.
  • For example, the running process priority is no less than any waiting process priority.

Hybrid Eviction

• It's possible to combine various eviction algorithms into a new algorithm.
  • A quantum priority scheduler, for example.
• Combine various versions of the same eviction algorithm.
  • Have short-, medium-, and long-quantum processes.
  • But now processes have to be assigned to versions.

Selection Algorithms

• Once a process leaves the CPU, which process gets next crack?
• Order the waiting processes into a queue.
  • The queue head is the next process.
• Similar to eviction, queue ordering can be relative or absolute.
  • No selection (a set of waiting processes) is possible but...

Absolute Selection

• Absolute scheduling imposes a strict (more or less) queue ordering on waiting processes.
  • New processes join at the tail, waiting processes leave at the head.
  • Queued processes may leave, when canceled, for example.

Relative Selection

• Relative selection uses the (or perhaps a) priority to order waiting processes.
  • The queue becomes a priority queue.
• Any process satisfying the priority invariant is selected next.

Hybrid Selection

• When several processes satisfy the priority invariant, which one is selected?
• Absolute and relative selection are frequently combined in the same algorithm.
  • Strictly queue same-priority processes.
  • Or could rely on a secondary priority.
• A selection algorithm often contains several versions of the same selection algorithm.
  • Queues for high, medium, or low priority processes.

First Come First Serve Scheduling

• Processes gain the CPU in the order they entered the system.
  • Treat the ready queue as a queue.
• Usualy no eviction algorithm

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 Scheduling

• 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.

Round Robin Scheduling

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

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.

Summary

• Schedulers manage process flow through and within a system.
• Schedulers comprise evection and selection algorithms.
  • Different choices of each lead to different schedulers.
• There are many schedulers in a system, and the all (should) coordinate to provide good management.

---

This page last modified on 2012 February 8.