Digital Systems Process Scheduling

Scheduling

• A key concept in computer multitasking and multiprocessing operating system design, and in real-time operating system design

  • The way processes are assigned priorities in a priority queue

Process Scheduling

• In operating systems (OS), process scheduling is the process of deciding which process to run on the CPU and for how long, ensuring efficient and fair resource allocation among multiple processes

• It's a crucial function of the OS, especially in multitasking environments, where multiple processes compete for CPU time

Program vs Process

• Program is a set of instructions written to perform a task, stored in memory

• Process is the active execution of a program, using system resources like CPU and memory

• Program is static, a process is dynamic, representing the program in action

• When we execute a program that was just compiled, the Operating System will generate a process to execute the program

• process (Job) refers to program code that has been loaded into a computer’s memory so that it can be executed by the central processing unit (CPU). A process can be described as an instance of a program running on a computer

Process States

A process can be in one of the following states:

1. Created/New: Process is being created

2. Ready: Process is waiting to be assigned to CPU

3. Running: Process is currently being executed by the CPU

4. Blocked (Waiting): Process is waiting for an event (e.g., I/O completion)

5. Terminated: Process has finished execution

Additional Process States to support Virtual Memory

Processes are "stored" on HD

• Swapped out and waiting: (suspended & waiting) In systems that support virtual memory, a process may be swapped out, that is, removed from RAM and placed on HD by the scheduler. From here the process may be swapped back into the waiting state

• Swapped out and blocked(suspended & blocked) Processes that are blocked may also be swapped out. It might be swapped back in again under the same circumstances as a swapped out

CPU Scheduling Criteria

• CPU Utilization: Keep CPU as busy as possible

• Throughput: number of processes that complete their execution per time unit

• Turnaround Time: amount of time to execute a particular process

• Waiting Time: amount of time a process has been waiting in the ready queue

• Response Time: Time taken from request submission to first response

• Fairness: Ensure equal opportunity for all processes

Context Switching

• The process of saving the state of a running process and loading the state of the next process

• Introduces overhead but is essential for multitasking

Deadlock

Occurs when a group of processes is permanently blocked, each waiting for a resource held by another process in the group

Circular waiting on resources, preventing progress

Deadlock Example

Process A holds Resource X and needs Resource Y, while Process B holds Resource Y and needs Resource X. Neither process can continue because they are waiting for each other’s resources

Starvation

Low-priority processes never get CPU time

Starvation Example

In a CPU scheduling scenario, a process with a lower priority might never get scheduled if there are always higher-priority processes ready to run

Running Multiple Processes

• In most OS, multi-tasking – running multiple processes on the machine interleaved over time

  • This may be the actual parallel running of processes (e.g, multiple CPUs or cores)

  • And/or time slicing between processes - quickly and frequently switching between which process is running to give the impression they are all running simultaneously

Types of Time Slicing

• Cooperative – the process indicates when it is ok to stop for a moment

• Pre-emptive – the OS decides when to switch and it’s done without the process’s involvement

  • Most OS use pre-emptive multi-tasking and the part of the kernel that decides who to switch between processes is the scheduler

Types of Scheduling

1. Long-Term Scheduling (Job Scheduling)

2. Medium-Term Scheduling

3. I/O Scheduling

4. Short-Term Scheduling (CPU Scheduling)

Short-Term Scheduling (CPU Scheduling)

• Decides which process gets the CPU next

• Runs frequently (every few milliseconds)

• Uses scheduling algorithms like FCFS, Round Robin, SJF, Priority Scheduling

Scheduling Algorithms

• First-Come, First-Served (FCFS) – Non-preemptive (Cooperative), runs in order of arrival

• Shortest Job Next (SJN or SJF) – Runs the shortest process first

• Round Robin (RR) – Each process gets a fixed time slice (time quantum)

• Priority Scheduling – Higher priority processes execute first

• Multilevel Queue Scheduling – Divides processes into different priority queues

First Come, First Serve (FCFS) Scheduling

• The simplest scheduling algorithm

• Processes are executed in the order they arrive in the ready queue

• It follows a non-pre-emptive (Cooperative) scheduling approach

How Does FCFS Work?

1. The process that arrives first gets executed first

2. The CPU is allocated until the process completes execution

3. The next process in the queue gets executed after the previous process finishes

FCFS Example

Turnaround Time (TAT) = Completion Time - Arrival Time

• TAT(P1) = 5 - 0 = 5 , TAT(P2) = 8 - 1 = 7 , TAT(P3) = 16 - 2 = 14 , TAT(P4) = 22 - 3 = 19

Waiting Time (WT) = Turnaround Time - Burst Time

• WT(P1) = 5 - 5 = 0 , WT(P2) = 7 - 3 = 4 , WT(P3) = 14 - 8 = 6 , WT(P4) = 19 - 6 = 13

FCFS Advantages

• Simple to implement

• Fair since processes are scheduled in order of arrival

FCFS Disadvantages

• Poor response time for long processes

• Convoy effect: A long process delays all other processes

Round Robin (RR) Scheduling

• A pre-emptive scheduling algorithm

• Each process gets a fixed time (time quantum) for execution

• If a process doesn't complete within the time quantum, it is pre-empted and moved to the end of the queue

How does RR Work?

1. The CPU executes each process for a fixed time quantum (e.g., 4 ms)

2. If a process completes within the quantum, it terminates

3. If not, it is moved to the end of the queue and waits for the next turn

RR Example

• P1 starts at 0 ms and runs for 4 ms (remaining: 1 ms)

• P2 starts at 4 ms and runs for 3 ms (finishes)

• P3 starts at 7 ms and runs for 4 ms (remaining: 4 ms)

• P4 starts at 11 ms and runs for 4 ms (remaining: 2 ms)

• P1 resumes at 15 ms and runs for 1 ms (finishes)

• P3 resumes at 16 ms and runs for 4 ms (finishes)

• P4 resumes at 20 ms and runs for 2 ms (finishes)

Average Turnaround Time = (15+6+18+19)/4 = 14.5 ms

Average Waiting Time = (10+3+10+13)/4 = 9 ms

RR Advantages

• Pre-emptive: Avoids long waiting times for short processes

• Better response time than FCFS

RR Disadvantages

• Overhead due to frequent context switching

• Choosing the wrong time quantum can impact performance

FCFS vs RR

Feature	FCFS	RR
Pre-emptive	No	Yes
Fairness	No (Convoy Effect)	Yes (Time Quantum)
Response Time	High (Bad)	Low (Good)
Overhead	Low	High (Context Switching)

Why is Scheduling Important?

• Ensures fairness: No process is left waiting indefinitely

• Maximises CPU utilisation: Prevents CPU idleness

• Minimises response time: Provides quick interaction in time-sharing systems

• Balances system load: Distributes work efficiently among processors

  • Efficient multitasking and resource utilization, ensuring that multiple processes can run concurrently without significant slowdowns or instability