7 - Scheduling Introduction

Question 1

What are scheduling policies also called?

Answer 1

disciplines

Question 2

What is the workload?

Answer 2

the processes running in the system

Question 3

What are jobs?

Answer 3

processes

Question 4

What is the purpose of a scheduling metric?

Answer 4

lets us compare different scheduling policies

Question 5

What is turnaround time?

type of metric

Answer 5

a scheduling and performance metric

Question 6

What is the formula for turnaround time?

Answer 6

the time which the job completes minus the time which the job arrived in the system;
T turnaround = T completion - T arrival

Question 7

What is another scheduling metric that is at odds with performance?

Answer 7

fairness

Question 8

What is the most basic algorithm?

Answer 8

First-In-First-Out or First Come, First Serve

Question 9

If all the jobs run for the same amount of time and arrive at the same time, which is the optimal algorithm?

Answer 9

FIFO, FCFS

Question 10

If all the jobs run for different amount of time and arrive at the same time, which is the optimal algorithm?

Answer 10

Shortest Job First, SJF

Question 11

What is the convoy effect?

Answer 11

A number of relatively-short potential consumers of a resource get queued behind a heavyweight consumer

Question 12

Which algorithm is considered optimal?

theoretically

Answer 12

Shortest Job First

Question 13

If all the jobs run for different amounts of time, arrive at different times, and don’t need to run to completion at once, which is the optimal algorithm?

Answer 13

Shortest Time-to-Completion First, STCF also known as Preemptive Shortest Job First, PSJF

Question 14

How does Shortest Job First function?

Answer 14

It runs the shortest job first, then the next shortest, and so on.

Question 15

Is SJF preemptive?

Answer 15

No, SJF is non-preemptive.

Question 16

Using which algorithm can the scheduler preempt a job and run another job?

Answer 16

Shortest Time-to-Completion, STCF

Question 17

How does STCF work?

Answer 17

Any time a new job enters the system, the STCF determines which of the remaining job, including the new job, has least time left, and schedules that one.

Question 18

Time-shared machines gave birth to what metric?

Answer 18

response time

Question 18

Which algorithm should be used if we knew job lengths, and that jobs only used the CPU, and our only metric was turnaround time?

Answer 18

STCF

Question 19

What is response time?

Answer 19

the time from when the job arrives in a system to the first time it is scheduled

Question 20

What is the formula for response time?

Answer 20

T response = T first run - T arrival

Question 21

What does the last job have to do in STCF?

Answer 21

it has to wait for the previous jobs to run in their entirety before being scheduled just once.

Question 22

How does Round-Robin work?

Answer 22

It runs a job for a time slice/scheduling quantum and then switches to the next job in the run queue. it repeatedly does so until the jobs are finished.

Question 23

What is Round-Robin also known as?

Answer 23

time-slicing

Question 24

What is true of the time slice in RR?

Answer 24

It must be a multiple of the timer-interrupt period.

Question 25

When programs run, in what do they build up a great deal of state?

Answer 25

CPU Caches, TLBs, branch predictors, other on-chip hardware

Question 26

What causes the CPU Caches, TLBs, branch predictors, other on-chip hardware to be flushed and new state relevant to the currently-running job to be brought in?

Answer 26

Switching to another job.

Question 27

By response time, what betters RR performance?

Answer 27

a shorter time-slice

Question 27

Why is a too short time-slice problematic?

Answer 27

the cost of context-switching will dominate overall performance

Question 28

What is the ideal size of a time slice?

Answer 28

long enough to amortize the cost of switching without making it so long that the system is not responsive.

Question 29

If the only metric was response time, which is the optimal algorithm?

Answer 29

Round-Robin

Question 30

If turnaround time was the only metric, which algorithm would be the worst?

Answer 30

Round Robin

Question 31

What does turnaround time care about?

Answer 31

when jobs finish

Question 32

What are the two schedulers? What do they optimize and do bad?

Answer 32

SJF,STCF & RR.
SJF,STCF optimizes turnaround time but does bad for response time
RR optimizes response time but does bad for turnaround time

Question 33

Why won’t the currently-running job be using the CPU during the I/O?

Answer 33

It is blocked waiting for I/O to be done.

Question 34

When a job requests I/O, what can a scheduler do?

Answer 34

probably schedule another job on the CPU at that time.

Question 35

Usually, the OS knows how much about the length of each job?

Answer 35

very little

Question 36

What happens when the I/O request is completed?

Answer 36

An interrupt is raised, and the OS runs and moves the process that requested the I/O from blocked to ready state

Question 37

What is a multi-level feedback queue?

Answer 37

a scheduler that uses the recent past to predict the future

Question 38

How can I maximize the utilization of systems?

Answer 38

by overlapping operations

Question 39

When is overlap used?

Answer 39

performing disk I/O, sending messages to remote machines

Question 40

What is amortization?

Answer 40

By performing the operation fewer times, the total cost to the system is reduced.