api: YAML JSON TOON Database
version: 1.0.0
format: json
dataset:
  slug: cpu-scheduling-algorithms
  title: CPU Scheduling Algorithms
  description: Algorithms used by the OS to allocate CPU time.
  summary: The classic CPU scheduling algorithms, each marked preemptive or non-preemptive with a one-line description, from first-come first-served to multilevel feedback queues, plus real-time schedulers such as earliest-deadline-first and the Linux Completely Fair Scheduler.
  use_when:
    - You need to compare scheduling policies by fairness, responsiveness and starvation risk.
    - You are explaining how an OS divides CPU time among processes.
  caveats:
    - Textbook algorithms assume known burst times; real systems estimate them or ignore them.
    - Real schedulers combine ideas, for example priority queues with time slices and aging to avoid starvation.
  related:
    - process-management
    - deadlock-handling
    - memory-management
  category: Operating Systems
  category_slug: operating-systems
  tags: os,scheduling,cpu
  view_count: 0
  entry_count: 13
  fields:
    - section: data
      field: name
      type: string
      example: First-Come First-Served
    - section: data
      field: type
      type: string
      example: Non-preemptive
    - section: data
      field: description
      type: string
      example: Processes run in arrival order; simple but can …
data:
  - name: First-Come First-Served
    type: Non-preemptive
    description: Processes run in arrival order; simple but can cause convoy effect.
  - name: Shortest Job First
    type: Non-preemptive
    description: Runs the process with the shortest estimated burst time.
  - name: Shortest Remaining Time First
    type: Preemptive
    description: Preemptive version of SJF.
  - name: Round Robin
    type: Preemptive
    description: Each process gets a fixed time quantum in cyclic order.
  - name: Priority Scheduling
    type: Variable
    description: Highest priority process runs first.
  - name: Multilevel Queue
    type: Non-preemptive queues
    description: Processes assigned to fixed priority queues.
  - name: Multilevel Feedback Queue
    type: Adaptive
    description: Processes move between queues based on behavior and aging.
  - name: Highest Response Ratio Next
    type: Non-preemptive
    description: Picks the ready process with the highest (waiting time + service time) / service time, which prevents starvation of long jobs.
  - name: Earliest Deadline First
    type: Preemptive
    description: Real-time policy that always runs the task with the nearest deadline; optimal on a single processor when utilization is at most 100%.
  - name: Rate-Monotonic Scheduling
    type: Preemptive
    description: Fixed-priority real-time policy that gives shorter-period tasks higher priority.
  - name: Completely Fair Scheduler
    type: Preemptive
    description: Linux's general-purpose scheduler for many years, tracking each task's virtual runtime in a red-black tree to share CPU time fairly.
  - name: Lottery Scheduling
    type: Preemptive
    description: Randomly selects the next process in proportion to the tickets it holds, giving probabilistic proportional share.
  - name: Fair-Share Scheduling
    type: Preemptive
    description: Divides CPU time among users or groups rather than individual processes.