15. Length-Aware Job Scheduling

Question 1

Shortest Job Next (SJN)

Answer 1

• Invocation: at the completion of a job (non-preemptive)
• Policy: select the job with the shortest length
• The optimal non-preemptive strategy to minimize average response time

Question 2

Flaw of SJN

Answer 2

• If the system receives a steady arrival of short jobs, a long job may not execute and suffer from starvation

Question 3

Shortest Remaining Time (SRT)

Answer 3

• Invocation: at the completion of a job, or at the arrival of a new job (preemptive)
• Policy: select the job with the shortest remaining execution time

Question 4

Flaw of SRT

Answer 4

• If the system receives a steady arrival of short jobs, a long job may not execute and suffer from starvation (same as SJN)
• A long job that is already running may never complete due to the arrival of jobs shorter than its remaining time

Question 5

Highest Slowdown Next (HSN)

Answer 5

• Invocation: at the completion of a job (non-preemptive)
• Policy: select the job with the largest slowdown

Question 6

Slowdown (HSN)

Answer 6

• (t + C_i - a_i) / C_i

Question 7

Static Analysis to Determine Job Length

Answer 7

• Relies on a model of the hardware to derive an approximation of the execution time

Question 8

Offline Measurements to Determine Job Length

Answer 8

• Measure the individual execution time of each job offline and store it in the system for online use

Question 9

Online Estimation to Determine Job Length

Answer 9

• Observe the length of jobs as they complete execution and use that information to predict the length of subsequent jobs

Question 10

Job Length - Simple Averages

Answer 10

• C(n) = average of all previous n job lengths
• Requires the storage of all n completed job lengths

Question 11

Job Length - Simple Averages with Optimization

Answer 11

• C(n) = (C(n-1) * (n-1) + C_(i,n)) / n
• Weighs all old job lengths equally to recent job lengths

Question 12

Job Length - Sliding Window

Answer 12

• C(n) = C(n-1) - (C_{(i, n) - w}) / w + C_(i, n) / w
• Requires the storage of all observations inside the sliding window w

Question 13

Job Length - Exponentially Weighted Move Averages (EWMA)

Answer 13

• C(n) = aC_(i, n) + (1-a)C(n-1)

Question 14

Static Priorities

Answer 14

• Priorities are assigned offline to each task
• Each job inherits the task-level priority

Question 15

Dynamic Task-Level Priorities

Answer 15

• Priority is assigned to each job of a task as soon as the job arrives
• Different jobs of the same task can have different priorities

Question 16

Dynamic Job-Level Priorities

Answer 16

• The priority of a job can change dynamically throughout its execution