Attenion: we use process scheduling when discussing general scheduling concepts.

Key Objects

  • Introduce CPU-scheduling (object, method, criteria)
  • List some common CPU-scheduling algorithms

Q: Why we address CPU-scheduling instead of scheduling itself?
A: Scheduling of this kind is a fundamental operating-system function. Almost all computer resources are scheduled before use.

Basic Scheduling Concepts

Preemptive and Nonpreemptive Scheduling

1. Preemptive Scheduling

  • Definition: In preemptive scheduling, the operating system can interrupt a running process before it completes, allowing another process to use the CPU. This ensures that no single process monopolizes the CPU for too long.

2. Nonpreemptive Scheduling

  • Definition: In nonpreemptive scheduling, once a process starts executing, it cannot be interrupted until it voluntarily releases the CPU (e.g., by terminating or waiting for I/O).

Components

1. CPU Scheduler

CPU-scheduler, or short-term scheduler, is responsible for selecting one of the processes in the ready queue and allocating the CPU to that process, when the CPU becomes idle.

2. Dispatcher

Different from CPU scheduler, dispatcher is the module that gives control of the CPU to the selected process. Its function involves the following:

  • Switching contex
  • Switching to user mode
  • Jumping to the proper location in the user program to restart

Scheduling Criteria

  • CPU utilization: keep CPU as busy as possible
  • Throughput: the number of processes completed per time unit
  • Turnaround time: the sum of the periods spent waiting, executing and doing I/O
  • Waiting time
  • Response time

Scheduling Algorithms

  • First-Come, First-Served Scheduling (FCFS)
  • Shortest-Job-First Scheduling
  • Priority Scheduling
  • Round-Robin Scheduling (RR)
  • Multilevel Queue Scheduling
  • Multilevel Feedback Queue Scheduling (MLFQ)

Reference: