CPU Scheduling (FCFS, SJF, RR)

In a multiprogramming system, multiple processes are kept in memory at the same time. When a process has to wait for I/O, the OS takes the CPU away from that process and gives it to another process. This is called CPU Scheduling.

1. Scheduling Criteria

Different CPU scheduling algorithms have different properties. The criteria used for comparing these algorithms include:

• CPU Utilization: Keep the CPU as busy as possible.
• Throughput: The number of processes that complete their execution per time unit.
• Turnaround Time: The amount of time to execute a particular process (from submission to completion).
• Waiting Time: The amount of time a process has been waiting in the ready queue.
• Response Time: The amount of time it takes from when a request was submitted until the first response is produced.

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

By far the simplest CPU scheduling algorithm. The process that requests the CPU first is allocated the CPU first. It is implemented using a FIFO queue.

• Type: Non-preemptive.
• Pros: Simple to understand and implement.
• Cons: Suffers from the Convoy Effect—where short processes get stuck waiting behind a massive, long-running process, drastically increasing the average waiting time.

3. Shortest-Job-First (SJF)

Associates with each process the length of its next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst.

• Type: Can be preemptive (Shortest Remaining Time First) or non-preemptive.
• Pros: Gives the minimum average waiting time for a given set of processes.
• Cons: It is practically impossible to know the exact length of the next CPU burst in advance. It can also cause Starvation, where long processes never get to run because short jobs keep arriving.

4. Round Robin (RR)

Designed specifically for time-sharing systems. It is similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of time, called a Time Quantum (or time slice), is defined.

The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

• If the process's CPU burst exceeds the quantum, the process is preempted and put back at the tail of the ready queue.
• Pros: Fair allocation of CPU. Excellent response time for interactive systems. No starvation.
• Cons: If the time quantum is too small, there is massive overhead from constant context switching. If the quantum is too large, RR degrades into FCFS.

5. Priority Scheduling

A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order.

• Problem: Starvation. A steady stream of high-priority processes can leave a low-priority process waiting indefinitely.
• Solution: Aging. A technique of gradually increasing the priority of processes that wait in the system for a long time.