CPU Scheduling Algorithms & Deadlock Avoidance & Recovery

Define the 5 criteria for comparing CPU scheduling algorithms.

1. CPU Utilization: Keeping the CPU as busy as possible.

2. Throughput: Number of processes completed per time unit.

3. Turnaround Time: Total time from submission to completion.

4. Waiting Time: Total time a process spends in the ready queue.

5. Response Time: Time from request submission until the first response is produced.

What is the Convoy Effect in FCFS scheduling?

When many short processes wait for one big, CPU-bound process to finish, resulting in lower CPU and device utilization.

What is Aging and what problem does it solve?

It is a technique of gradually increasing the priority of processes that wait in the system for a long time to prevent Starvation (where low-priority processes never run).

What is the Banker’s Algorithm?

A deadlock avoidance algorithm used for systems with multiple instances of each resource type. It tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources before deciding whether allocation should be allowed.

Name two methods for Deadlock Recovery via process termination.

1. Abort all deadlocked processes: Breaks the cycle but loses all work.

2. Abort one process at a time: Until the deadlock cycle is eliminated; requires a selection policy (e.g., based on priority).

What does FCFS stand for in CPU scheduling?

First‑Come, First‑Served.

Is FCFS preemptive or non‑preemptive?

FCFS is non‑preemptive.

What data structure is typically used to implement FCFS?

A FIFO queue.