Scheduling

Question 1

What metrics do we consider for scheduling policies?

Answer 1

Turnaround time = time of completion - time of arrival
Fairness
Response time = time first run - time of arrival

Question 2

When might FIFO scheduling pose problems?

Answer 2

If job lengths are not all equal length, then we may have a very poor average turnaround time if a lengthy job arrives before some short jobs. This is the convoy effect.

Question 3

When is shortest job first optimal?

Answer 3

If all the jobs arrive at exactly the same time, then shortest job first has the best turnaround.

Question 4

True or false, shortest job first is a pre-emptive scheduler?

Answer 4

False, it does not interrupt jobs once they have started.

Question 5

True or false, shortest time to completion is a pre-emptive scheduler?

Answer 5

True, jobs can be interrupted if there exists another job with a shorter completion time.

Question 6

True or false, SJF scheduler has good performance for response time?

Answer 6

False, as it only switches between jobs when one completes.

Question 7

When might response time be important for a scheduler?

Answer 7

If there is lots of user interaction, such as keyboard activity.

Question 8

What is Round Robin scheduling?

Answer 8

In RR, instead of running jobs to completion, we run jobs for a time slice, before switching to the next job in the queue.

Question 9

What must we make sure that the time slice is a multiple of, in Round Robin scheduling?

Answer 9

The time slice should be a multiple of the timer interrupt period.

Question 10

True or false, Round Robin scheduling has good performance for turnaround time?

Answer 10

False, it has very poor performance.

Question 11

What problems does a multi-level feedback queue attempt to solve?

Answer 11

Optimising turnaround time when we aren’t sure how long jobs will last, and being responsive and interactive to users.

Question 12

What are the rules of the Multi-Level Feedback Queue?

Answer 12

1) Tasks on higher level priority queues should run.
2) If Tasks have the same priority, they run in Round Robin.
3) When a job is introduced, it starts at highest priority.
4a) When a job uses up an entire time slice while running, its priority is reduced.
4b) If a job gives up the CPU before the time slice is up, its priority stays the same.
4c) Once a job has used up its time at a given priority level, regardless of how many times it has given up the CPU, its priority is reduced.
5) After some time period, all jobs are moved to the highest priority queue.

Question 13

Why might you want to vary the time slice length for different queues on the MLFQ?

Answer 13

So that the time slice is short for high priority jobs, and long for low priority jobs.

Question 14

What is lottery scheduling?

Answer 14

We hold lotteries to see which process should run. Processes each hold a certain number of tickets, and if their ticket is chosen, then they run. For example, if A holds 75 tickets, and B holds 25 tickets, we would expect A to run 75% of the time. Tickets are chosen randomly.

Question 15

When is the lottery scheduler fairest? What is difficult to decide in lottery scheduling?

Answer 15

When the length of each job is longer, it is fairer. It is hard to decide how many tickets each process should be given.

Question 16

How does Stride Scheduling work?

Answer 16

Each job has a stride value. Every time a process runs, we increment its pass value by the stride amount. We then pick the process with the lowest pass value to run.

Question 17

What is the main way the stride scheduling differs from lottery scheduling? Why might we sometimes prefer to use lottery scheduling?

Answer 17

While stride scheduling is deterministic, lottery scheduling is based off random selection. We might prefer to use lottery scheduling, as it is much simpler to add a new process to the scheduler.

Question 18

How does the Completely Fair Scheduler work?

Answer 18

Each process has a virtual runtime, which is incremented whenever a process runs. When a scheduling decision occurs, we pick the program with the lowest virtual runtime. CFS uses red-black trees to be more efficient.

Question 19

How does CFS choose its time slice?

Answer 19

It does this dynamically, based upon how many processes want to run. However, there is a minimum value for the time slice, which it is never set below.

Question 20

How does CFS deal with IO and sleeping processes?

Answer 20

If a process has slept for a long time, its vruntime will be well below the other processes, so it will hog the scheduler. To prevent this, we set this process’s vruntime to the lowest value present in the vruntime tree. (so it is not completely fair haha)

Question 21

When is shortest-time-to-completion first optimal?

Answer 21

When we know the total execution time of each job.

Question 22

What is the difference between a soft and a hard real time system?

Answer 22

In a hard system, all deadlines MUST be met, and in a soft system deadlines can be missed but the application must be notified and be able to take action.

Question 23

What are two strategies we could use for hard real time scheduling?

Answer 23

Rate Monotonic Scheduling, and Earliest Deadline First