1What is CPU Scheduling?
CPU Scheduling is a fundamental function of an operating system to decide which process runs next.
2What is the role of a CPU scheduler?
A CPU scheduler chooses which process to run next from the ready queue.
3What is a scheduling algorithm?
A scheduling algorithm is a method used by the CPU scheduler to select the next process to execute.
4Why is CPU scheduling done?
CPU scheduling is done to ensure the CPU is not idle and to maximise CPU utilisation.
5Name the main aims of CPU scheduling.
Fairness, Efficiency, Response time, Turnaround time, Throughput.
6Define Fairness in CPU scheduling.
Fairness ensures all processes get a fair share of CPU time and avoids starvation.
7Define Efficiency in CPU scheduling.
Efficiency maximises CPU utilisation, keeping the CPU busy close to 100% of the time.
8Define Response Time in CPU scheduling.
Response time is the time taken to respond to a process request.
9Define Turnaround Time in CPU scheduling.
Turnaround time is the total time between job submission and completion.
10Define Throughput in CPU scheduling.
Throughput is the number of jobs completed within a given time period.
11What are the two main types of CPU scheduling?
Pre-emptive Scheduling and Non-pre-emptive Scheduling.
12What is Pre-emptive Scheduling?
In pre-emptive scheduling, the OS can temporarily suspend a process to run higher-priority or time-sliced processes.
13What is Non-pre-emptive Scheduling?
In non-pre-emptive scheduling, a process releases the CPU only after completion, voluntarily.
14Give examples of pre-emptive CPU scheduling algorithms.
Round Robin, Multilevel Queues, Multilevel Feedback Queues.
15Describe the Round Robin (RR) algorithm.
Each process is given a fixed time slice (time quantum). If a process does not finish, it is preempted and added to the end of the ready queue.
16What factors affect Round Robin performance?
Average waiting time, time quantum size: short quantum → too many switches, long quantum → behaves like FCFS.
17Round Robin formula for Turnaround Time
TT = Waiting Time (TW) + Burst Time (TB)
18Round Robin formula for Average Waiting Time
AWT = Σ TW of all processes / Number of processes
19Round Robin example (Time Slice = 2ms, P1=10,P2=1,P3=2,P4=1,P5=5): Average Waiting Time?
AWT = (9 + 2 + 3 + 5 + 10)/5 = 5.8ms
20Round Robin example: Average Turnaround Time?
ATT = (19 + 3 + 5 + 6 + 15)/5 = 9.6ms
21Describe Multilevel Queue Scheduling.
Processes are permanently assigned to separate queues based on priority/type, each queue has its own algorithm, higher queues have priority.
22Describe Multilevel Feedback Queue Scheduling.
Processes can move between queues based on CPU burst time to prevent starvation and optimise response.
23Give examples of non-preemptive algorithms.
First Come First Serve (FCFS), Shortest Job First (SJF), Priority Scheduling.
24Describe FCFS scheduling.
The first process to request the CPU is allocated the CPU. Once allocated, it runs until completion or I/O.
25FCFS Average Waiting Time formula
AWT = Σ TW of all processes / Number of processes
26FCFS example (P1=10,P2=1,P3=2,P4=1,P5=5): Average Waiting Time?
AWT = (0 + 10 + 11 + 13 + 14)/5 = 9.6ms
27FCFS Average Turnaround Time formula
ATT = Σ TT of all processes / Number of processes
28FCFS example: Average Turnaround Time?
ATT = (10 + 11 + 13 + 14 + 19)/5 = 13.4ms
29Describe Shortest Job First (SJF) scheduling.
Process with the smallest next CPU burst is executed first; ties are broken using FIFO.
30Why is SJF considered optimal?
SJF provides the minimum average waiting time.
31SJF example (P1=10,P2=1,P3=2,P4=1,P5=5): Average Waiting Time?
AWT = (9 + 0 + 2 + 1 + 4)/5 = 3.2ms
32SJF example: Average Turnaround Time?
ATT = (19 + 1 + 4 + 2 + 9)/5 = 7ms
33Describe Priority Scheduling.
CPU is allocated to the process with the highest priority; ties are broken using FIFO.
34Problem with Priority Scheduling?
Starvation of low-priority processes.
35Solution to Priority Scheduling starvation?
Aging: gradually increase the priority of waiting processes.
36Priority Scheduling formula
TT = TW + Burst Time, AWT = Σ TW / Number of processes, ATT = Σ TT / Number of processes
37Comparison of algorithms (short summary)
RR: AWT 5.8ms, ATT 9.6ms, Fair, Medium Efficiency; FCFS: AWT 9.6ms, ATT 13.4ms, Unfair, Low; SJF: AWT 3.2ms, ATT 7ms, Unfair, High; Priority: AWT 8.2ms, ATT 12ms, Unfair, Low (if no aging).