slides 12 - Scheduling

Question 1

CPU scheduler

Answer 1

When CPU becomes idle, it selects next job from ready queue

Question 2

CPU Dispatcher

Answer 2

• Swaps processes
• Steps:
  1. Switch context from one process to another
  2. Switch to user mode
  3. Jump to proper location in user program and resume

Question 3

Preemptive vs non-preemptive

Answer 3

• Preemptive: running process can be interrupted
• Non-preemptive: any new process must wait for running process to finish CPU cycle

Question 4

Preemptive vs non-preemptive examples (2 each)

Answer 4

PREEMPTIVE
1. process switches running -> ready
2. process switches waiting -> ready

NON-PREEMPTIVE
1. process switches running -> waiting
2. process terminates

Question 5

CPU utilization

Answer 5

capacity used/total capacity

Question 6

Efficiency

Answer 6

useful work/total work

Question 7

Throughput

Answer 7

number of processes completed per unit time

Question 8

Turnaround time

Answer 8

Interval from submission to completion of a process

Question 9

Waiting time

Answer 9

Sum of periods spent in ready queue

Question 10

Response time

Answer 10

Time from submission to time the request got the first response - start of response is taken

Question 11

Estimating runtime of jobs (formula)

Question 12

First-come, first-served scheduling

Answer 12

• Jobs that arrives first is given CPU first
• Convoy effect: if we have a lot of I/O bound processes waiting on I/O and a CPU bound process gets on the CPU first, its going to hold the CPU for a long time and the IO processes will have to wait in the ready queue for a long time

Question 13

Shortest-job-first scheduling

Answer 13

• Non-preemptive
• Assume a set of jobs have already arrived and in ready queue
• Select job with shortest burst size
• Minimal average waiting time

Question 14

Shortest remaining time next scheduling

Answer 14

• Preemptive
• Selects job with smallest REMAINING burst size

Question 15

Round-robin scheduling

Answer 15

• Has a quantum (time slice): length before preemption of a process
• Ready queue is a circular queue
• If executing process has more time -> goes back to ready queue
• If executing process terminates -> select another job
• Benefit: fair - a job gets1/n of the CPU every q time units

Question 16

Round-robin scheduling issues

Answer 16

• Job needs to wait at most (n-1) x q before running again
• More jobs in queue/large quantum size -> slow jobs
• Small quantum size -> many context switches, inefficient
• Good quantum size = average size of job

Question 17

Priority scheduling

Answer 17

• CPU given to process with highest priority
• Equal priorities handled thru FCFS
• Convention: low priority numbers = higher priority
• Preemptive: current job evicted if higher priority process arrives
• Nonpreemptive: ready queue sorted by priority

Question 18

Priority scheduling issues

Answer 18

• Starvation: low priority processes blocked if high number of incoming higher priority jobs
• Solution: aging -> gradually increasing priority of jobs not selected