Wesloo
All topicsTopics

Operating systems

CPU scheduling algorithms: how process scheduling works

Short answer

CPU scheduling is the operating system's method for choosing which ready process uses the CPU next. It aims to keep the processor busy while limiting waiting and response time. Common methods include FCFS, SJF, SRTF, priority, and round robin, in preemptive or non-preemptive form.

Key points

  • CPU scheduling chooses the next ready process for a CPU core.
  • Preemptive scheduling can interrupt a running task; non-preemptive scheduling waits for release or termination.
  • Common metrics are CPU utilization, throughput, turnaround time, waiting time, and response time.
  • FCFS, SJF, SRTF, priority, and round robin offer different trade-offs.
  • Round robin gives equal turns and is starvation-free.

What CPU scheduling algorithms do

CPU scheduling algorithms decide which ready process gets the CPU at a given moment. A single CPU core handles one task at a time, so the operating system must choose among waiting programs. The scheduler keeps the processor busy and aims to reduce waiting and response time. It selects from processes in memory that are ready to run.

Efficient scheduling supports multitasking and fairness. No single task should take all CPU time while others wait. Different systems use different rules because hardware, workload, and goals differ.

Preemptive and non-preemptive scheduling

Preemptive scheduling can interrupt a running task. It often assigns priorities, so a higher-priority task can run before a lower-priority task that is still active. The lower-priority task pauses and resumes after the higher-priority task finishes.

Non-preemptive scheduling gives the CPU to a process until that process terminates or moves from running to waiting. The running process is not interrupted midway. Because it needs no special hardware such as a timer, this method works on many hardware platforms.

Metrics used to judge a scheduler

CPU utilization measures how busy the processor is. Theoretical use ranges from 0 to 100 percent, while a real-time system often runs from 40 to 90 percent depending on load. Throughput counts completed processes per unit time and varies with process length.

Turnaround time runs from process arrival to completion. It includes waiting for memory, waiting in the ready queue, CPU use, and I/O wait. Waiting time is the time spent in the ready queue; scheduling does not change the time needed once execution starts. Response time is the delay from submission to the first response, which matters in interactive systems.

Common CPU scheduling algorithms

First Come First Serve runs processes in arrival order. It is simple but can make short jobs wait behind long ones. Shortest Job First selects the process with the shortest expected burst time, which can reduce average waiting time but needs good estimates.

Shortest Remaining Time First is the preemptive form of SJF: whichever process has the smallest remaining completion time receives the CPU next. Priority scheduling selects tasks by priority. Round robin gives each process an equal turn in a repeating cycle, which helps achieve starvation-free execution. Round robin is not fully independent; it relies on other scheduling ideas for complete job scheduling.

AlgorithmTypeMain strength
FCFSNon-preemptiveSimple arrival-order service
SJFNon-preemptiveShort jobs finish sooner
SRTFPreemptiveLeast remaining time first
PriorityVariesImportant tasks first
Round RobinPreemptiveEqual turns, starvation-free

Example: comparing waiting times

Take three processes that arrive at time 0 with burst times of 6, 2, and 4 units. Under FCFS in that order, waiting times are 0, 6, and 8 units, for an average of 14/3 units. Under SJF, the order becomes 2, 4, and 6 units, with waiting times of 0, 2, and 6 units and an average of 8/3 units.

With round robin and a time quantum of 2 units, completion times are 12, 4, and 10 units, so waiting times are 6, 2, and 6 units, with an average of 14/3 units. This shows that algorithm choice changes delay even when total work is the same.

Fairness, starvation, and priority effects

Fairness means every process gets a reasonable share of CPU time, so no process waits too long. Round robin supports this by giving equal turns. Priority scheduling can let important tasks run first, but a steady stream of high-priority work can delay lower-priority processes. The scheduler must balance responsiveness for urgent tasks with progress for background work.

Starvation occurs when a process waits indefinitely because others always take precedence. Round robin is described as starvation-free because every process gets a turn. Other methods may need aging or priority adjustment to avoid long waits.

Estimating burst time and scheduling overhead

Shortest Job First and SRTF depend on knowing or estimating how long a process will run. In practice, the operating system may use past behavior to predict the next burst. Context switches also cost time because the scheduler must save and restore process state. A very small time quantum in round robin increases fairness but can raise overhead from frequent switching.

Interactive and real-time considerations

In interactive systems, response time matters more than total turnaround time because a process may produce output early and continue computing. Real-time systems need predictable behavior, so a basic algorithm may be unsuitable. The scheduler must match the algorithm to the system's performance goals and design.

From ready queue to running state

CPU scheduling is also called process scheduling. When several programs wait, the scheduler picks one according to its rules and hands that program control of the CPU. The main task is to ensure that if the CPU becomes idle, the operating system picks at least one process from the ready queue. This keeps work moving and avoids an idle processor.

Multi-core scheduling

A multi-core CPU can run several processes at once. Scheduling algorithms assign tasks to cores to improve performance. The operating system may use a shared ready queue, per-core queues, or a mix of both.

Choosing an algorithm for a system

The choice depends on factors such as CPU utilization, throughput, turnaround time, waiting time, and response time. Using a complex algorithm in a simple system, or basic scheduling in a real-time environment, can reduce performance. Different operating systems choose algorithms that fit their performance goals and design, including time-sharing or priority-based scheduling.

For broader context, see How Operating System Works: Architecture and Functions. Memory behavior also affects scheduling; see Virtual memory paging file size and system guide. Kernel design affects scheduling implementation; see Monolithic Kernel vs Microkernel: Key Differences.

Questions people also ask

What is CPU scheduling in an operating system?

It is the process the operating system uses to decide which ready process gets the CPU at a given time. Since one core handles one task at a time, scheduling keeps the processor busy and manages multiple tasks.

What is the difference between preemptive and non-preemptive scheduling?

Preemptive scheduling can interrupt a running task, often based on priority. Non-preemptive scheduling lets the process keep the CPU until it terminates or moves to waiting.

Which CPU scheduling algorithm is starvation-free?

Round robin is described as starvation-free because it gives each process an equal turn in a repeating cycle.

What metrics are used to evaluate CPU scheduling?

Common metrics include CPU utilization, throughput, turnaround time, waiting time, and response time.

Related pages

  • How Device Drivers Work: OS and Hardware Bridge

    Device drivers are programs that translate operating system requests into hardware commands and return device status. They run with different privilege levels, can be generic or manufacturer-specific, and are loaded only when needed. Without the right driver, hardware may fail, run slowly, or lose features.

  • RTOS vs General Purpose OS: Key Differences

    An RTOS prioritizes deterministic timing and deadlines for mission-critical tasks, while a general-purpose OS prioritizes flexibility, throughput, and user experience for broad computing. The right choice depends on whether the application has strict timing constraints or general computing needs.

  • Operating System Deadlocks: Causes and Prevention

    A deadlock happens when processes block forever while each holds a resource another process needs. It requires four conditions at once and can be handled by prevention, avoidance, detection and recovery, or, in rare cases, by ignoring it.

  • File systems comparison: NTFS, FAT32, exFAT, and ext4

    NTFS, FAT32, exFAT, and ext4 serve different operating systems and storage needs. NTFS suits Windows internal drives, ext4 suits Linux, while FAT32 and exFAT help with broad compatibility. The right choice depends on OS support, file size limits, and whether the drive needs journaling or permissions.

  • 32-bit vs 64-bit OS: Key Differences

    A 32-bit operating system can address up to 4 GB of RAM, while a 64-bit system can address far more. The choice affects memory use, software support, and hardware requirements.

  • Monolithic Kernel vs Microkernel: Key Differences

    A monolithic kernel runs all operating system services in one shared kernel address space, while a microkernel keeps only essential functions in the kernel and moves other services to user space. The first favors speed and simple system calls; the second favors isolation, smaller kernel size, and easier maintenance.

How this page was prepared

Before writing, the topic was researched in the sources below. The page then passed automatic quality checks.

Report a mistake on this page