Module 3: CPU Scheduling

CPU Scheduling

the sharing of the CPU among read processes

CPU Utilization

Fraction of time a CPU is used by user processes

Throughput Formula

N/T where N = number of processes complete and T = observation time

Response Time Formula

Response Time = T_FirstTime - T_a

T_FirstTime = time a process gets CPU the first time

T_a = Process Arrival Time

Turnaround Time

Turnaround Time = T_complete - T_a

T_complete = time a process complete and terminates

T_a = Process Arrival Time

Waiting Time

T_waiting

where T_waiting is the total time spent by a process in the ready queue

Objective of CPU scheduling for All Systems

Fairness, Policy Enforcement, and Balance

Objective of CPU Scheduling in Batch Systems

Throughput, Turnaround time, and CPU Utilization

Objective of CPU Scheduling in Interactive Systems

Response time, Proportionality

Objective of CPU Scheduling in Real-time systems

Meeting deadlines, Predictability

Fairness

Giving each process a fair share of the CPU

Policy Enforcement

seeeing that state policy is carried out

Balance

keeping all parts of the system busy

Throughput

maximize jobs per hour

Turnaround Time

Minimize time between submission and termination

CPU Utilization

keep the CPU busy all the time

Response Time

respond to request quickly

Proportionality

meet users’ expectations

Meeting deadlines

avoid losing data

Predictability

avoid quality degradation in multimedia systems

Preemptive Scheduling

OS can forcibly take back the CPU

Non-preemptive

the process voluntarily relinquishes the CPU

First Come First Serve (FCFS)

process that arrives first is allocated the CPU first

Shortest Job First (SJF)

• non-preemptive

• POLICY:associate with each process the length of its next CPU burst

• SJF is optimal, delivers min average turnaround time for a given set of processes

Shortest-Remaining-Time-First (SRTF)

• preemptive

• policy: if a new process arrives w/ CPU burst length less than remaining time of current executing proces

Round Robin

Order processes in ready queue in FCFS, assign CPU to list head, CPU is assigned for limited time (quantum)

Quantum

usually 10-100 milliseconds

What is the problem/weakness of FCFS?

avg turnaround increases with large process in front of smaller ones

How does SJF address FCFS’s weakness?

favors short jobs. SJF offers optimal turnaround time

What is SJF’s weakness?

we can’t know in advance the length of a CPU burst

How does RR address SJF’s weakness?

ensures that shorter jobs complete earlier than larger ones

What is RR’s weakness?

decreases throughput

Can we address RR’s weakness? If yes, how?

Yes by adapting the quantum: increase quantum for longer CPU bursts

Is there a CPU scheduling policy with adaptive quantum?

Yes, Multi-Level Feedback Queue (MLFQ)