Lecture Notes for Operating Systems

Process scheduling, 15 September 1999

1. scheduling - what is it

   1. which process gets to execute next

   2. scheduling objectives - fairness, utilization (total) vs. efficiency (useful), response time, turnaround, throughput

   3. pre-emptive vs. non-pre-emptive scheduling

   4. job characteristics are unpredictable - lots of guessing, adjusting, and modeling.

   5. user defined scheduling objectives

   6. scheduling overhead - picking and switching

2. shortest job first

   1. minimize the average completion time

   2. batch-oriented, interactive jobs require estimation - arithmetic vs. geometric averages

3. round robin

   1. a quantum (or a time slice) - how long a process runs before being stopped by the scheduler

   2. processes are queued; the head runs; stopped processes are re-queued

   3. setting the quantum appropriately relative to scheduler overhead

4. priority

   1. all processes are not created equally - some should be run before others.

   2. priority captures the notion of relative importance among processes

   3. static vs. dynamic and user vs system priority assignments

   4. dynamic system adjustments recover from bad guesses and other events - premature context switching

5. multiple queues

   1. an alternative - have varying quantum

   2. high priority short quantum (interactive) low priority long quantum (compute intensive)

   3. scheduling complexity quickly grows - unintended consequences, increasing overhead

6. guaranteed scheduling

   1. contract to provide a certain level of service

   2. quality of service (QoS)

7. lottery scheduling

   1. probabilistic scheduling - select process i with probability pi

   2. for the lottery, pi is p's tickets over total tickets

   3. flexible, instantaneous

   4. economic scheduling - auctioning and bidding

8. real-time scheduling

   1. model

      1. process have finite, known duration

      2. events trigger processes - periodic or aperiodic

      3. deadlines on process termination

   2. reaction times, bounded response

   3. hard and soft real-time systems

   4. fixed process set

   5. periodic utilization - execution/period; schedulable

   6. dynamic vs. static scheduling

   7. rate monotonic scheduling - priority proportional to occurrence frequency: e.g. every 20 msec -> 50 times a sec -> priority 50

   8. deadline, periodic and aperiodic; earliest deadline first scheduling

   9. laxity, from now to the latest possible starting time; least laxity scheduling

   10. special operating systems - stripped down, high performance, timer rich.

9. two-level scheduling

   1. not all runnable processes fit in main store - disk swap space

   2. now two types of movement are needed - main store-cpu and disk-main store

   3. the scheduler needs to handle both kinds of movement, or you need two schedulers

   4. criteria - residency, last cpu access, process size, priority

10. policy vs. mechanism

    1. policy - what you want to happen

    2. mechanism - how you can cause something to happen

    3. example - policy: run as many jobs as possible (high throughput); mechanisms: shortest jobs first, kill long jobs.

    4. one of the principle mistakes in system design (of any kind) is to specify mechanism instead of policy.

11. examples

    1. nt

       1. four priority classes - real time, high, normal, idle; real time is static, others dynamic

       2. seven priority levels - time critical, highest, above normal normal, below normal, lowest, idle

       3. classes and levels combine to provide over-all priority

    2. solaris

       1. scheduling classes - time sharing, real time, and system

       2. real time - high priority, pre-empts os, other features

       3. dynamically loaded modules - parameter tables and actual functions

       4. ia class - overcomes ts-rr performance problems; violates layering

This page last modified on 20 September 1999.