CPU Scheduling

CPU scheduling is a process which allows one process to use the CPU while the execution of another process is on hold (in waiting state) due to unavailability of any resource like I/O etc... thereby making full use of CPU.

The aim of CPU scheduling is to make the system efficient, fast and fair.

We have 2 types of scheduling:

• Long Term Scheduling: For example the number of jobs executing at once in the primary memory.

• Short Term Scheduling: A small time scale, for example right now we have multiple processes wanting to run on CPU, which ones shall execute first.

Short Term Scheduling

The kernel runs the scheduler at least when:

• A process switches from running to waiting.

• An interrupt occurs.

• A process is created or terminated.

Non-preemptive system: The scheduler must wait for one of these events.

Preemptive system: The scheduler can interrupt a running process.

Criteria for comparing scheduling algorithms

• CPU Utilization: The percentage of time that the CPU is busy.

• Throughput: The number of processes completing in a unit of time.

• Turnaround time: The length of time it takes to run a process from initialization to termination, including all the waiting time.

• Waiting time: The total amount of time that a process is in the ready queue.

• Response time: The time between when a process is ready to run and its next I/O request.

Scheduling Algorithms

1. FCFS: First Come, First Served.

2. Round Robin: Use a time slice and preemption to alternate jobs.

3. SJF: Shortest Job First.

4. Shortest Remaining Time First (SRTF): A Preemptive SJF.

5. Multilevel Feedback Queues: Round robin on each priority queue.

FCFS

• The scheduler executes jobs to completion in arrival order.

• In early FCFS schedulers, the job did not relinquish the CPU even when it was doing I/O.

• We will assume a FCFS scheduler that runs when processes are blocked on I/O, but that is non-preemptive, i.e., the job keeps the CPU until it blocks (say on an I/O device).

Advantage: FCFS is simple to implement.

Disadvantages: Average wait time is highly variable as short jobs may wait behind long jobs.

FCFS may lead to poor overlap of I/O and CPU since CPU-bound processes will force I/O bound processes to wait for the CPU, leaving the I/O devices idle.

Round Robin

• Variants of round robin are used in most time sharing systems.

• Add a timer and use a preemptive policy.

• After each time slice, move the running thread to the back of the queue.

• Selecting a time slice:

  • Too large: Waiting time suffers, degenerates to FCFS if processes are never preempted.

  • Too small: Throughput suffers because too much time is spent context switching.

Balance these tradeoffs by selecting a time slice where context switching is roughly 1% of the time slice.

Today:

• Typical time slice is 10-100 ms.

• Context switch time is 0.1-1 ms.

• Advantage: It's fair; each job gets an equal shot at the CPU.

• Disadvantage: Average waiting time can be bad.

Shortest Job First

Schedule the job that has the least (expected) amount of work (CPU time) to do until its next I/O request or termination.

Advantages:

• Provably optimal with respect to minimizing the average waiting time.

• Works for preemptive and non-preemptive schedulers.

• Preemptive SJF is called SRTF (shortest remaining time first).

Disadvantages:

• Impossible to predict the amount of CPU time a job has left.

• Long running CPU bound jobs can starve.

Multilevel Feedback Queues

Multilevel feedback queues use past behavior to predict the future and assign job priorities.

MLFQ overcomes the prediction problem in SJF.

• If a process is I/O bound in the past, it is also likely to be I/O bound in the future (programs turn out not to be random).

• To exploit this behavior, the scheduler can favor jobs that have used the least amount of CPU time, thus approximating SJF.

• This policy is adaptive because it relies on past behavior and changes in behavior result in changes to scheduling decisions.

Adjusting Priorities in MLFQ:

• Job starts in highest priority queue.

• If job's time slices expires, drop its priority one level.

• If job's time slices does not expire (the context switch comes from an I/O request instead), then increase its priority one level, up to the top priority level.

CPU bound jobs quickly drop in priority and I/O bound jobs stay at a high priority.

Summary

1. FCFS: Not fair, and average waiting time is poor.

2. Round Robin: Fair, but average waiting time is poor.

3. SJF: Not fair, but average waiting time is minimized assuming we can accurately predict the length of the next CPU burst. Starvation is possible.

4. Multilevel Queuing: An implementation (approximation) of SJF.

Our modeling assumed that context switches took no time, which is unrealistic.

Example #1 (FCFS & RR)

5 Jobs, 100 seconds each, time slice is 1 second and context switch time of 0

1. Using FCFS, each job will complete in 100 seconds and then do a context switch, we can calculate average completion time (100 + 200 + 300 + 400 + 500 / 5 = 300).

1. Now for Round Robin, each job will get executed based on time slice (quantum time) for 1 second and move to the next job.

So if we calculate the completion time for round robin, each job will accomplish 1 second of work every 5 seconds, we can get FCFS completion time and minus it from the other 4 jobs to get the completion time for the first job, as its the first job which executed the time slice. The same applies for job 2 which will be 500 - 3 = 497 etc...

1. Now to calculate the wait time which is the time that the job waits until it gets executed, we can do it by computing completion time - length (burst time)

Example #2 (FCFS & RR)

5 Jobs of length 50, 40, 30, 20 and 10, time slice 1 second and context switch time of 0 seconds

1. Using FCFS, we first get the first burst time (length) which is 50 then to get the second job burst time we add 50 + 40 = 90 etc...

1. For round robin with a time slice (quantum time) of 1, the first job that will finish is job 5 because it needs to reach only 10 which would take 10 x 5 = 50 completion time, the formula used is Length x Job number.

1. Finally, for the waiting time we calculate using same formula which is completion time - length

Example #3 (FCFS & RR & SJF)

5 Jobs of length 50, 40, 30, 20 and 10 seconds each, time slice of 1 second and context switch time is 0

1. We calculate FCFS & RR same as Example 1 and 2

1. For SJF, we must pick the shortest Job First, which in this case is Job 5 which is = 10. after that we go to the second shortest job which is job 4 which is equals to 10 + 20 = 30 then to job 3 which is 30 + 30 = 60 etc...

1. Finally, for the waiting time we calculate using same formula which is completion time - length