Interrupts

An interrupt is a signal sent to the CPU by hardware or software to indicate that an event requires immediate attention. Interrupts allow the CPU to respond to events asynchronously without constantly polling (checking) devices.

Types of interrupt:

• Hardware interrupt: generated by a hardware device (e.g. keyboard keypress, mouse click, disk I/O completion, timer).
• Software interrupt: generated by a running program requesting an OS service (system call / trap instruction). E.g. a program requesting file I/O.
• Timer interrupt: generated by the system timer at regular intervals; used by the OS scheduler to preempt processes (enforce time quanta in round-robin).
• Exception/fault: generated by an error condition (divide by zero, illegal memory access, overflow). Can be seen as a software interrupt.

Interrupt handling (Interrupt Service Routine — ISR):

1. An interrupt signal is received.
2. The CPU completes the current instruction (it does not stop mid-instruction).
3. The CPU saves the state of the current process (program counter, registers) to the stack/PCB.
4. The CPU disables (masks) further interrupts to avoid nested interrupts (in some systems).
5. The CPU consults the interrupt vector table (IVT) to find the address of the relevant ISR.
6. The ISR executes, handling the interrupt.
7. On completion, the saved state is restored and the original process resumes.

Interrupt priority:

Different interrupts have different priorities. Higher-priority interrupts (e.g. power failure, hardware error) can interrupt lower-priority ISRs. A priority system ensures critical events are handled first.

CPU Scheduling

The scheduler is the OS component that decides which ready process gets CPU time next. Scheduling aims to maximise CPU utilisation, throughput, and fairness while minimising response time and waiting time.

Scheduling criteria:

• CPU utilisation: keep the CPU as busy as possible.
• Throughput: number of processes completed per unit time.
• Turnaround time: total time from process submission to completion.
• Waiting time: total time spent in the ready queue.
• Response time: time from submission to first response (important for interactive systems).

Types of scheduling:

• Preemptive: the OS can forcibly remove the CPU from a running process (e.g. when its time quantum expires or a higher-priority process becomes ready).
• Non-preemptive: a process runs until it voluntarily yields the CPU (blocks for I/O or terminates). Simpler but can cause poor response time.

Scheduling Algorithms

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

Processes are scheduled in the order they arrive in the ready queue. Simple but can cause the convoy effect: a long process at the front of the queue delays all shorter processes behind it, increasing average waiting time. Non-preemptive.

2. Shortest Job First (SJF) / Shortest Job Next (SJN)

The process with the shortest estimated CPU burst is scheduled next. Minimises average waiting time and is optimal for minimising average turnaround time. Problems: requires knowing burst time in advance (difficult in practice); can cause starvation of long processes if short processes keep arriving.

• Non-preemptive SJF: current process runs to completion before next is selected.
• Preemptive SJF (Shortest Remaining Time First, SRTF): if a new process arrives with a shorter burst than the remaining time of the current process, the current process is preempted.

3. Round-Robin (RR)

Each process is given a fixed time quantum (time slice, e.g. 10–100 ms). After its quantum expires, the process is preempted and placed at the back of the ready queue. Designed for time-sharing systems; fair; good response time. Performance depends heavily on the size of the time quantum:

• Too large: degenerates towards FCFS.
• Too small: excessive context switching overhead reduces CPU efficiency.

4. Shortest Remaining Time First (SRTF)

Preemptive version of SJF. The process with the shortest remaining burst time always runs. Optimal for minimising average waiting time but causes starvation and requires estimating remaining burst times.

5. Priority Scheduling

Each process is assigned a priority. The highest-priority ready process is scheduled next. Can be preemptive or non-preemptive. Problem: starvation — low-priority processes may never run. Solution: ageing — gradually increase the priority of waiting processes over time.

6. Multi-level Feedback Queue (MLFQ)

Multiple queues with different priority levels. Processes start in the highest-priority queue. If a process uses its full time quantum (CPU-bound), it is demoted to a lower-priority queue. Interactive/I/O-bound processes that give up the CPU voluntarily are promoted or remain in higher queues. Combines the benefits of multiple algorithms. Used in modern OS kernels (Linux CFS, Windows scheduler).