CPU Schedulers and The Dispatcher

To effectively manage processes, the OS utilizes different levels of scheduling and a specific mechanism to grant CPU control.

1. Types of Schedulers

• Long-Term Scheduler (Job Scheduler): Selects processes from a pool (on disk) and loads them into memory for execution. It controls the degree of multiprogramming (the number of processes in memory). It executes less frequently.
• Short-Term Scheduler (CPU Scheduler): Selects from among the processes in memory that are ready to execute and allocates the CPU to one of them. It must be extremely fast to minimize overhead.
• Medium-Term Scheduler: Used in systems that support swapping. It can temporarily remove a process from memory (swapping out) and later return it (swapping in), usually to improve the process mix or free up memory.

Comparison Table of Schedulers [2019 Q2]:

Exam Tip [2019 Q2]: When asked to discuss the differences among these three schedulers, draw this table and explain the function of each scheduler in detail.

2. The Dispatcher

While the scheduler selects a process, the Dispatcher is the module that actually gives control of the CPU to the process selected by the short-term scheduler. Its functions include:

• Switching context.
• Switching to user mode.
• Jumping to the proper location in the user program to restart that program.

Dispatch Latency: The time it takes for the dispatcher to stop one process and start another running. This must be as small as possible.

CPU Scheduling Fundamentals and Criteria

In a multiprogramming environment, the objective is to have some process running at all times to maximize CPU utilization. The CPU Scheduler (Short-term scheduler) selects from among the processes in memory that are ready to execute and allocates the CPU to one of them.

Preemptive vs. Non-Preemptive Scheduling

Scheduling decisions happen under four circumstances:

1. A process switches from Running to Waiting (e.g., I/O request).
2. A process switches from Running to Ready (e.g., timer interrupt).
3. A process switches from Waiting to Ready (e.g., I/O completion).
4. A process Terminates.

If scheduling takes place only under 1 and 4, the system is Non-Preemptive (Cooperative). Otherwise, it is Preemptive.

Scheduling Optimization Criteria

To compare scheduling algorithms, we use several metrics:

• CPU Utilization: Range is 0 to 100 percent. In a real system, it should range from 40% (lightly loaded) to 90% (heavily loaded).
• Throughput: Number of processes that complete their execution per time unit.
• Turnaround Time ($T_{at}$): The interval from the time of submission of a process to the time of completion ($Finish - Arrival$).
• Waiting Time ($W_t$): The sum of the periods spent waiting in the ready queue ($T_{at} - Burst\ Time$).
• Response Time: The time from the submission of a request until the first response is produced (critical for time-sharing systems).

Non-Preemptive Algorithms: FCFS and SJF

1. First-Come, First-Served (FCFS)

The simplest algorithm. The process that requests the CPU first is allocated the CPU first.

• Problem: The Convoy Effect. Consider one CPU-bound process and many I/O-bound processes. The I/O processes wait behind the long CPU process, leaving I/O devices idle. When the CPU process finally finishes, the I/O processes zip through and then wait for the CPU again. This leads to low hardware utilization.

2. Shortest-Job-First (SJF) - Non-Preemptive

This algorithm associates with each process the length of the process's next CPU burst. When the CPU is available, it is assigned to the process with the smallest next burst.

• Pros: It is optimal, as it gives the minimum average waiting time for a given set of processes.
• Cons: It is difficult to know the length of the next CPU burst in advance (often predicted using exponential averaging).

Preemptive Scheduling: SRTF and Round Robin

1. Shortest-Remaining-Time-First (SRTF)

The preemptive version of SJF. If a new process arrives with a CPU burst length less than the remaining time of the current executing process, the current process is preempted.

PYQ SJF Comparison (Non-Preemptive vs Preemptive) [2019 Q3 — 14 marks]:

Non-Preemptive SJF: At time 0, only P1 is available. P1 runs from 0-7. At time 7, P2(4), P3(1), P4(4) are ready → order by burst: P3(1), P2(4), P4(4).

Waiting Times: P1=0, P2=8-2=6, P3=7-4=3, P4=12-5=7. AWT = (0+6+3+7)/4 = 4 ms

Preemptive SJF (SRTF): At each arrival, check if the new process has a shorter remaining time.

Timeline: P1 runs 0-2. P2 arrives at 2 with burst 4 < P1 remaining 5 → P1 preempted. P2 runs 2-4. P3 arrives at 4 with burst 1 < P2 remaining 3 → P2 preempted. P3 runs 4-5 (completes). P2 resumes 5-8 (completes). P1 resumes 8-13 (completes). P4 arrives at 5, runs 13-17 (completes). Waiting Times: P1=13-7=6, P2=(4-2)+(8-5)=5, P3=4-4=0, P4=13-5=8. AWT = (6+5+0+8)/4 = 4.75 ms

Conclusion: Non-preemptive SJF has lower AWT (4 ms vs 4.75 ms) for this dataset because P3 arrived just at time 4. However, preemptive SJF is more responsive — P3 finished at time 5 instead of waiting until time 8.

2. Round Robin (RR)

Designed specifically for time-sharing systems. Each process is given a small unit of CPU time, called a Time Quantum (or time slice), usually 10–100 milliseconds.

• Mechanics: The ready queue is treated as a circular queue. The scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
• The Quantum Dilemma:
  • If $q$ is very large $\rightarrow$ RR becomes FCFS.
  • If $q$ is very small $\rightarrow$ RR becomes "processor sharing," but the overhead of context switching becomes dominant.
  • Rule of Thumb: 80% of CPU bursts should be shorter than the time quantum.

Gantt Chart (Quantum = 4): P1(4) | P2(3) | P3(3) | P1(4) | P1(4) | P1(4) | P1(4) | P1(4)

PYQ RR with Varying Arrival Times [2023 Q2b — 7 marks]: Consider 5 processes:

Time Quantum = 3 ms

Timeline (Round Robin with arrivals):

• 0-3: Ready queue = [P1, P2]. P1 runs 3ms → remaining 9. Ready queue = [P2, P1].
• 3-5: P2 runs 3ms → remaining 7. P3 arrives at 1, P5 at 2 → ready queue = [P1, P5, P3, P2]. But P3 and P5 were already in queue. Actually let's track the queue properly.

Detailed execution:

Waiting Time Calculation: WT = Finish Time − Arrival Time − Burst Time

• P1: 40 − 0 − 12 = 28 ms
• P2: 44 − 0 − 10 = 34 ms
• P3: 22 − 1 − 4 = 17 ms
• P4: 48 − 4 − 10 = 34 ms
• P5: 47 − 2 − 12 = 33 ms AWT = (28 + 34 + 17 + 34 + 33) / 5 = 29.2 ms

Priority and Multilevel Queue Scheduling

1. Priority Scheduling

A priority (integer) is associated with each process. The CPU is allocated to the process with the highest priority (usually smallest integer = highest priority).

• The Starvation Problem: Low-priority processes may never execute in a heavily loaded system.
• The Aging Solution: Gradually increase the priority of processes that wait in the system for a long time.

PYQ Priority Scheduling Example [2024 Q3b]: Consider 5 processes arriving at time 0:

FCFS Gantt Chart:

FCFS Waiting Times: A=0, B=10, C=11, D=13, E=14. AWT = (0+10+11+13+14)/5 = 9.6 ms

SJF Gantt Chart:

SJF Waiting Times: B=0, D=1, C=2, E=4, A=9. AWT = (0+1+2+4+9)/5 = 3.2 ms ← Minimum

2. Multilevel Queue Scheduling

Partitions the ready queue into several separate queues (e.g., Interactive Foreground vs. Batch Background). Processes are permanently assigned to one queue, and each queue has its own scheduling algorithm.

3. Multilevel Feedback Queue

The most sophisticated algorithm. Unlike the standard multilevel queue, it allows a process to move between queues.

• If a process uses too much CPU time, it is moved to a lower-priority queue.
• If a process waits too long in a lower-priority queue, it is moved to a higher-priority queue (Aging).
• This separates processes based on their CPU burst characteristics (I/O-bound vs. CPU-bound).