Process Scheduling

  • Maximize CPU use, quickly switch processes onto CPU for time sharing
  • Process scheduler selects among available processes for next execution on CPU
  • Maintains scheduling queues of processes
    • Job queue – set of all processes in the system
    • Ready queue – set of all processes residing in main memory, ready and waiting to execute
    • Device queues – set of processes waiting for an I/O device
    • Processes migrate among the various queues

  • Representation of Process Scheduling


  • Long-term scheduler (or job scheduler)–selects which processes should be brought into the ready queue
  • Short-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPU
    • Sometimes the only scheduler in a system
  • Schedulers (Cont.)

  • Short-term scheduler is invoked very frequently (milliseconds) => (must be fast)
  • Long-term scheduler is invoked very infrequently (seconds, minutes) => (may be slow)
  • The long-term scheduler controls the degree of multiprogramming
  • Processes can be described as either:
    • I/O-bound process – spends more time doing I/O than computations, many short CPU bursts
    • CPU-bound process – spends more time doing computations; few very long CPU bursts

  • Addition of Medium Term Scheduling

    Context Switch

  • When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch.
  • Context of a process represented in the PCB
  • Context-switch time is overhead; the system does no useful work while switching
    • The more complex the OS and the PCB -> longer the context switch
  • Time dependent on hardware support
    • Some hardware provides multiple sets of registers per CPU -> multiple contexts loaded at once