P3L1 Scheduling - Preemptive, Priority, Round Robin

Question 1

Interrupting a task running on the CPU is called _____________ scheduling

Answer 1

preemptive

Question 2

With reference to the diagram, assuming SJF and preemptive scheduling describe a possible order for the tasks to run. Given:

• Task T2 arrives first, takes 10 seconds
• Tasks T1, T3, arrive at time 2 seconds, take 1 second each

Answer 2

1. T2 runs first because it’s the only task in the system at time=0
2. T2 runs for 2 seconds and is preempted by short tasks
3. T1 runs for 1 second to completion
4. T3 then runs for 1 second to completion
5. T2 is run to completion

Question 3

With reference to the diagram, assuming SJF and preemptive scheduling and given priorities, describe a possible order for the tasks to run. Given:

• Task T2 arrives first, takes 10 seconds
• Tasks T1, T3, arrive at time 2 seconds, take 1 second each
• P1 < P2 < P3 meaning: T1 has lowest priority, T2 has medium, T3 has highest priority

Answer 3

1. T2 runs first because it’s the only task in the system at time=0
   * T2 runs for 2 seconds and is preempted by T3 who has highest priority!
2. T3 preempts T2 and runs for 1 second to completion
3. T2 then runs to completion as it has 2nd highest priority
4. T1 runs to completion

Question 4

What is an effective way (data structure and algorithm) for the OS scheduler to run tasks by priority?

Answer 4

An effective way to be able to quickly tell a task’s priority is to maintain a separate runqueue for each priority level. As a result, the scheduler can just empty queues by priority level.

Question 5

One dangerous situation that can occur with priority scheduling is _______, in which a low priority tasks is essentially never scheduled because ______ priority tasks continually enter the system and take precedence.

One mechanism to protect against starvation is _______ _______ . In _______ _______, the priority of a task is not just the numerical priority, but rather a function of the actual priority and the amount of _____ the task has spent in the _________. This way, older tasks are effectively promoted to higher priority to ensure that they are scheduled in a reasonable amount of time.

Answer 5

One dangerous situation that can occur with priority scheduling is starvation, in which a low priority tasks is essentially never scheduled because higher priority tasks continually enter the system and take precedence.

One mechanism to protect against starvation is priority aging. In priority aging, the priority of a task is not just the numerical priority, but rather a function of the actual priority and the amount of time the task has spent in the runqueue. This way, older tasks are effectively promoted to higher priority to ensure that they are scheduled in a reasonable amount of time.

Question 6

1. Name and describe a possible problem with scheduling tasks only by priority.
2. Name and describe a solution to this problem

Answer 6

1. Starvation - high priority tasks keep coming in and so lower priority tasks never get a turn
2. Solution: Priority aging -‘priority’ is a function of priority level AND amount of time in the runqueue.

• Tasks grow in priority with age.
• This promotes older tasks even if they have lower priority.
• f(actual priority, time spent in runqueue).

Question 7

Assuming priority based, preemptive scheduling, compute finishing times of each task given:

• T1 highest priority (P3 < P2< P1)
• T3 arrives at t=0; time to complete = 4 seconds
• T2 arrives at t=3; time to complete = 4 seconds
• T1 arrives at t=5; time to complete = 3 seconds

Answer 7

1. T3 only task in system so runs for 3 seconds.
2. T2 preempts, runs for 2 seconds
3. T1 preempts, runs for 3 seconds to completion (finish time t=8)
4. T2 runs 2 more seconds to completion (t=10)
5. T3 runs 1 more second to completion (t=11)

Note - question asked finishing times - not ‘time to complete’ so count time from first task

Question 8

When a lower priority task acquires a mutex lock before a higher priority thread enters the runqueue, this can lead to a problem called __________ ___________.

The solution is to temporarily raise the priority of the task which owns the mutex. This mechanism is called _________ _________.

Answer 8

priority inversion

priority boosting

Question 9

Give an example to describe priority inversion

Describe the solution to priority inversion

Answer 9

See diagram …

T1 which has the highest priority has to wait on T3 (for its lock) even though T3 has the lowest priority.

The order of execution should have been T1, T2, T3, but instead was T2, T3, T1.

A solution to this problem would have been to temporarily boost the priority of the mutex owner. When T1 needs to acquire the lock owned by the T3, T3 should have its priority boosted to P1, so it would be scheduled on the CPU. Once T3 releases its mutex, T3 should have its priority dropped back to P3, so T1 can now execute, as T1 is the task with the actual highest priority.

Then lower the priority back of T3 as soon as possible (after unlock)

Question 10

1. When it comes to running jobs with the same priority there are alternatives to FCFS and SJF. A popular option is ___________________ scheduling.
2. If Task T1 has a lower priority than tasks T2 and T3, task T1 will run until task ___ or ___ comes in.
3. When will task T1 continue running?

Answer 10

1. round robin
2. T2 or T3
3. after both T2 and T3 complete

Question 11

1. A further modification that makes sense with round robin is not to wait until the tasks explicitly yield, but instead to _______ them in order to mix in all the tasks in the system at the same time.
2. For example, we would give each task a _______ of one time unit before interrupting it to schedule a new task.
3. We call this mechanism __________.

Answer 11

1. interrupt
2. window
3. timeslicing