Operating System Scheduling Algorithms: Types and Examples
Learn six important OS scheduling algorithms, including FCFS, SJF, Priority, SRTF, Round Robin, and Multilevel Queue scheduling. Embedded Tech Development Academy (ETDA).
Operating System Scheduling Algorithms: A Complete Technical Guide
Introduction to Operating System Scheduling
An Operating System (OS) manages hardware resources and provides an environment for executing application programs. One of its most important responsibilities is process scheduling, which determines how CPU time is distributed among multiple processes. Since several programs may be ready to execute at the same time, the operating system needs scheduling algorithms to decide which process should receive CPU access and for how long.
Operating System scheduling directly affects CPU utilization, throughput, response time, waiting time, turnaround time, and overall system performance. Different scheduling techniques are designed for different environments, including batch processing systems, interactive operating systems, real-time applications, and resource-constrained devices.
Scheduling is also important in Embedded Systems and Internet of Things (IoT), where multiple tasks may need to process sensor data, communicate through UART, SPI, I2C, or CAN, and respond to external interrupts. Embedded developers must understand CPU scheduling, task prioritization, context switching, and preemptive execution to develop efficient firmware and real-time applications.
At Embedded Tech Development Academy (ETDA), operating system concepts are connected with practical embedded programming and real-time application development. As a Top Embedded Training Institute in Bangalore, Embedded Tech Development Academy (ETDA) helps learners build technical knowledge relevant to Embedded Systems and Internet of Things (IoT), supported by assured placement support for career preparation.
What Is a Process in an Operating System?
A process is a program in execution. A program is a passive set of instructions stored on a storage device, whereas a process is an active entity loaded into memory and executed by the CPU.
A process contains several important elements:
Program code: Instructions executed by the processor.
Program counter: Stores the address of the next instruction.
CPU registers: Hold temporary processing information.
Stack: Stores function calls, local variables, and return addresses.
Data section: Contains global and static variables.
Heap: Provides memory for dynamic allocation.
Process States
A process generally moves through different states during execution:
New: The process is being created.
Ready: It is waiting for CPU allocation.
Running: Its instructions are being executed.
Waiting/Blocked: It is waiting for an event or I/O operation.
Terminated: Its execution has finished.
The operating system maintains process information in a Process Control Block (PCB), which stores process state, register values, scheduling information, and memory-management details.
What Is a Process Scheduler?
A process scheduler is an operating system component responsible for selecting a process from the ready queue and allocating CPU time to it. Its main objective is to use processor resources efficiently while maintaining acceptable system responsiveness.
Preemptive and Non-Preemptive Scheduling
Scheduling algorithms are broadly classified into two categories:
Non-preemptive scheduling: Once a process receives the CPU, it continues until it terminates or enters a waiting state.
Preemptive scheduling: The operating system can interrupt a running process and allocate the CPU to another process.
Preemptive scheduling is useful in interactive systems and real-time applications, while non-preemptive scheduling is simpler to implement in certain batch-processing environments.
Important Scheduling Performance Metrics
CPU utilization: Percentage of time the CPU remains busy.
Throughput: Number of processes completed per unit of time.
Turnaround time: Total time between process arrival and completion.
Waiting time: Total time spent waiting in the ready queue.
Response time: Time from process arrival until its first CPU response.
Six Important CPU Scheduling Algorithms
First-Come, First-Served (FCFS) Scheduling
FCFS is one of the simplest CPU scheduling algorithms. Processes are executed in the order in which they arrive in the ready queue. It follows the FIFO (First-In, First-Out) queue structure.
Characteristics:
Non-preemptive scheduling.
Easy to understand and implement.
Processes are handled according to arrival time.
May produce high average waiting time.
Limitation: The convoy effect occurs when short processes wait behind a long-running process. This reduces responsiveness and can affect CPU and I/O utilization.
Shortest Job Next (SJN) Scheduling
Shortest Job Next, also called Shortest Job First (SJF), selects the process with the smallest expected CPU burst time.
Characteristics:
Traditionally implemented as a non-preemptive algorithm.
Can minimize average waiting time when CPU burst times are known.
Suitable for batch systems where execution times can be estimated.
Difficult to apply accurately when execution time is unknown.
Advantages and Limitations
SJF improves average waiting time compared with many other algorithms when its assumptions are satisfied. However, long processes may experience starvation if shorter jobs continuously arrive. Operating systems can estimate CPU bursts using previous execution behaviour, but exact future execution time is generally unavailable.
Priority-Based Scheduling
In priority scheduling, every process is assigned a priority value. The CPU is allocated to the highest-priority ready process. If multiple processes have the same priority, FCFS can be used to determine their execution order.
Characteristics:
Can be preemptive or non-preemptive.
Priorities may depend on deadlines, process importance, or resource requirements.
Useful when certain tasks require faster service.
Priority Inversion and Starvation
A low-priority process may wait indefinitely if higher-priority processes keep arriving. This is called starvation. Aging gradually increases the priority of waiting processes to reduce this problem.
Priority inversion occurs when a high-priority task waits for a resource held by a lower-priority task. Priority inheritance is one technique used to address it, particularly in real-time Embedded Systems.
Shortest Remaining Time First (SRTF)
Shortest Remaining Time First is the preemptive version of SJF. The scheduler selects the process with the smallest remaining CPU burst time.
Characteristics:
Preemptive scheduling algorithm.
A running process can be interrupted when a process with a shorter remaining time becomes ready.
Can reduce average waiting time under suitable conditions.
Requires knowledge or estimation of remaining execution time.
SRTF is useful in environments where short jobs need preference, but frequent preemption can increase context-switching overhead.
Round Robin (RR) Scheduling
Round Robin is a preemptive scheduling algorithm commonly used in time-sharing systems. Each process receives a fixed CPU time interval called a time quantum.
When the quantum expires, the running process is preempted and moved to the back of the ready queue if it has not completed. The next ready process receives CPU time.
Role of Context Switching
During a context switch, the operating system saves the current process state in its PCB and restores the state of the next process. This allows multiple processes to share CPU resources.
A very small time quantum increases context-switching overhead, while an excessively large quantum makes Round Robin behave more like FCFS. Selecting an appropriate quantum is essential for performance.
Multilevel Queue Scheduling
Multilevel Queue Scheduling divides the ready queue into multiple separate queues based on process characteristics or requirements. Each queue may use a different scheduling algorithm.
For example:
System processes may use priority scheduling.
Interactive processes may use Round Robin.
Batch processes may use FCFS.
Queue Priority and CPU Allocation
Each queue can have a fixed priority, or the operating system can allocate CPU time among queues using a time-sharing mechanism. With strict fixed priorities, lower-priority queues may experience starvation. Multilevel Queue Scheduling is useful when process categories are clearly defined.
Scheduling in Embedded Systems and IoT
CPU scheduling is especially important in Embedded Systems and Internet of Things (IoT) because devices frequently execute multiple tasks with different timing requirements. For example, an Internet of Things (IoT) monitoring device may read temperature sensors, update a display, transmit data through a wireless module, and monitor alarms.
Real-Time Operating Systems (RTOS) commonly use priority-based preemptive scheduling. A high-priority task can interrupt a lower-priority task when necessary. Developers must also consider task deadlines, interrupt latency, synchronization, and context-switching overhead.
At Embedded Tech Development Academy (ETDA), these operating system concepts support learning in Embedded Systems, Internet of Things (IoT), RTOS, and microcontroller-based development. A Top Embedded Training Institute in Bangalore should connect scheduling theory with practical programming exercises, and Embedded Tech Development Academy (ETDA) offers assured placement support as part of its career-oriented training approach.
Frequently Asked Questions
What is a scheduling algorithm in an operating system?
A scheduling algorithm is a method used by an operating system to select the next process from the ready queue for CPU execution.
Why is CPU scheduling important?
CPU scheduling improves processor utilization, throughput, response time, and overall system performance by managing how processes access the CPU.
What is FCFS scheduling?
First-Come, First-Served is a non-preemptive scheduling algorithm that executes processes in their order of arrival using a FIFO queue.
What is the difference between SJF and SRTF?
SJF generally selects the process with the shortest CPU burst without preempting a running process. SRTF is its preemptive version and selects the process with the shortest remaining execution time.
What is a time quantum in Round Robin scheduling?
A time quantum is the fixed CPU time interval allocated to a process before the scheduler moves to the next ready process.
Which scheduling algorithm is commonly used in RTOS?
Priority-based preemptive scheduling is commonly used in RTOS environments because it allows important or time-critical tasks to receive CPU time promptly.
Conclusion
Operating System scheduling algorithms determine how processes share CPU resources and directly influence system performance. FCFS, SJF, Priority Scheduling, SRTF, Round Robin, and Multilevel Queue Scheduling each offer different advantages and limitations. Selecting an appropriate algorithm depends on process execution time, priority, responsiveness requirements, context-switching overhead, and system workload.
Understanding process states, CPU scheduling, ready queues, PCBs, preemption, and context switching is essential for software developers and embedded engineers. These concepts become particularly important when building Embedded Systems and Internet of Things (IoT) applications that require predictable task execution and efficient resource management.
Embedded Tech Development Academy (ETDA) helps learners connect operating system fundamentals with practical Embedded Systems development, Linux concepts, RTOS programming, and Internet of Things (IoT) applications. Recognized in its training focus as a Top Embedded Training Institute in Bangalore, Embedded Tech Development Academy (ETDA) emphasizes technical skill development and assured placement support to help students prepare for embedded software and firmware engineering opportunities.
Author: ETDA Trainers
Experience: 10+ Years of Industry Experience in Embedded Systems, IoT, and Embedded C Programming