←Back to Subject
Notes
Notes
Study material and explanations
Diagrams
Diagrams
Visualize concepts easily
Mnemonics
Mnemonics
Tricks to remember faster
One Night Prep
One Night Prep
Short and focused revision
Revision
Revision
Quick summary and key points
Important Questions
Important Questions
Practice most relevant questions
Notes

Process Scheduling: Queues, Schedulers, Preemptive vs Non-Preemptive & Scheduling Criteria

Study material and explanations for Unit 2

Process Scheduling: Queues, Schedulers, Preemptive vs Non-Preemptive & Criteria

1. What is Process Scheduling?

In a multiprogramming or time-sharing system, dozens of processes compete for the CPU at the same time. Process Scheduling is the activity of the Operating System’s Process Manager that removes the currently running process from the CPU and selects the next process from the Ready Queue based on a specific scheduling strategy.

The 3 Process Scheduling Queues:

As processes enter the system and change states, the OS places their PCBs into three main queues:

  1. Job Queue: Holds all processes in the system that have arrived and are waiting on the hard disk to be brought into main memory (RAM).
  2. Ready Queue: Holds all processes that are residing in Main Memory (RAM) and are ready and waiting to execute on the CPU.
  3. Device (Waiting) Queues: Holds processes that are currently blocked waiting for a specific I/O device (e.g., Disk Queue, Printer Queue).

2. Types of Schedulers (Long-Term, Short-Term & Medium-Term)

The OS uses three types of schedulers to move processes between these queues:

Figure 2.4: The 3 Types of OS Schedulers
1. Long-Term Scheduler (Job Scheduler)
Moves processes from Disk (Job Queue) → RAM (Ready Queue). Controls Degree of Multiprogramming.
2. Short-Term Scheduler (CPU Scheduler)
Picks a process from Ready Queue (RAM) → Allocates CPU. Runs every few milliseconds!
3. Medium-Term Scheduler (Swapper)
Temporarily swaps processes out of RAM to Disk (and back in) to free up memory.

Comparison Table: Long-Term vs Short-Term vs Medium-Term Scheduler

Basis Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler
1. Also Called Job Scheduler CPU Scheduler Process Swapper
2. What It Does Selects jobs from Disk (Job Queue) and loads them into RAM (Ready Queue). Selects a ready process from Ready Queue and allocates the CPU to it. Swaps processes out of RAM to Disk (and swaps them back in later).
3. Execution Speed Executes infrequently (once every few seconds or minutes). Executes extremely fast and frequently (every 10–100 ms). Executes at medium frequency when RAM becomes full.
4. Effect on Degree of Multiprogramming Controls (Increases) the Degree of Multiprogramming (number of processes in RAM). Does not change the number of processes in RAM. Reduces the Degree of Multiprogramming during memory shortage.

(Note: A good Long-Term Scheduler selects a balanced mix of I/O-Bound Processes—which spend most of their time doing I/O—and CPU-Bound Processes—which spend most of their time doing heavy CPU calculations).

3. Preemptive vs Non-Preemptive Scheduling

Every CPU scheduling algorithm falls into one of two categories depending on whether the OS can forcibly take the CPU away from a running process:

Figure 2.5: Preemptive Scheduling vs Non-Preemptive Scheduling
1. Non-Preemptive Scheduling
  • Once the CPU is given to a process, it CANNOT be taken away forcibly!
  • The process keeps the CPU until it finishes its CPU burst or voluntarily waits for I/O
  • Algorithms: FCFS, Non-Preemptive SJF, Non-Preemptive Priority
2. Preemptive Scheduling
  • The OS CAN forcibly interrupt (preempt) a currently running process in the middle of execution!
  • Happens when a higher-priority/shorter job arrives or when the Time Quantum expires
  • Algorithms: SRTN, Round Robin (RR), Preemptive Priority

Detailed Comparison: Preemptive vs Non-Preemptive Scheduling

Basis Preemptive Scheduling Non-Preemptive Scheduling
1. Basic Rule The CPU can be taken away from a running process before it finishes. Once allocated, a process holds the CPU until it finishes or blocks for I/O.
2. Response Time Very Fast / Low Response Time (short/urgent tasks don’t get stuck behind long jobs). Poor / High Response Time (short tasks must wait if a long job is running).
3. Context Switch Overhead High overhead due to frequent context switching. Low overhead (switches only when a process finishes or blocks).
4. Synchronization Needed? Yes (shared data can be corrupted if preempted mid-update). Simpler; less risk of race conditions on a single CPU.
5. Examples Round Robin (RR), SRTN (Preemptive SJF), Preemptive Priority. FCFS (First-Come, First-Served), SJF (Non-preemptive).

4. CPU Scheduling Criteria (Performance Metrics)

How do we compare different scheduling algorithms (FCFS, SJF, Round Robin) and decide which one is best? We use 5 standard Scheduling Criteria (and every numerical problem in Unit 2 uses their formulas!):

1. CPU Utilization (Maximize ↑)

  • Definition: The percentage of time that the CPU remains actively busy executing processes (ideally between 40% on a lightly loaded system and 90%+ on a busy system).
  • Goal: Maximize CPU Utilization.

2. Throughput (Maximize ↑)

  • Definition: The total number of processes completed per unit of time (e.g., 15 processes per second).
  • Goal: Maximize Throughput.

3. Turnaround Time — TAT (Minimize ↓)

  • Definition: The total time interval from the moment a process arrives (is submitted) until the moment it completely finishes execution. It includes waiting time in queues + I/O time + actual CPU execution time.

Formula: Turnaround Time (TAT) = Completion Time (CT) - Arrival Time (AT)

  • Goal: Minimize Turnaround Time.

4. Waiting Time — WT (Minimize ↓)

  • Definition: The total amount of time a process spends sitting idle in the Ready Queue waiting for its turn on the CPU.

Formula: Waiting Time (WT) = Turnaround Time (TAT) - Burst Time (BT)

  • Goal: Minimize Waiting Time.

5. Response Time — RT (Minimize ↓)

  • Definition: The time from the submission (Arrival Time) of a request until the VERY FIRST response / first CPU allocation is produced (not completion!).

Formula: Response Time (RT) = First CPU Start Time - Arrival Time (AT)

  • Goal: Minimize Response Time (especially important in interactive desktop and mobile systems).

💡 Exam Preparation Tips for DAVV BCA

  • Memorize the two golden numerical formulas inside the boxes above:
    1. TAT = CT - AT (Turnaround Time = Completion Time − Arrival Time)
    2. WT = TAT - BT (Waiting Time = Turnaround Time − Burst Time)
  • For the 5 Scheduling Criteria, always state which 2 we want to Maximize (CPU Utilization, Throughput) and which 3 we want to Minimize (Turnaround Time, Waiting Time, Response Time)!