P3L1 Scheduling - Timeslices Flashcards
A ________ is the maximum amount of uninterrupted time that can be given to a task.
A task may run for a ________ amount of time than what the timeslice specifies.
The use of timeslices allows for the tasks to be ____________ . That is, they will be timesharing the CPU.
For _____ bound tasks, this is not super critical, as these tasks will often be placed on wait queues. However, for _____ bound tasks, timeslices are the only way that we can achieve timesharing.
A timeslice is the maximum amount of uninterrupted time that can be given to a task.
A task may run for a shorter amount of time than what the timeslice specifies.
The use of timeslices allows for the tasks to be interleaved. That is, they will be timesharing the CPU.
For I/O bound tasks, this is not super critical, as these tasks will often be placed on wait queues. However, for CPU bound tasks, timeslices are the only way that we can achieve timesharing.
Define ‘timeslice’
A timeslice is the maximum amount of uninterrupted time that can be given to a task.
Specify 2 ways a task may run for a shorter amount of time than specified.
- Task has to wait on I/O
- Another higher priority task becomes runnable and preempts
Use of timeslicing is more important for CPU bound tasks or I/O bound tasks?
CPU bound tasks because I/O tasks get stopped anyway. CPU bound tasks would just hog the CPU if nothing stops them.
For these tasks that all arrive at the same time, same priority:
- T1 , exec time 1 sec
- T2, exec time 10 sec
- T3, exec time 1 sec
Using timeslice (1 sec) scheduling, calculate
- throughput
- average wait time
- average completion time
- throughput = 3/(1 + 2 + 1+8) = 3/12 sec 0.25 tasks/sec
- average wait time - (0 + 1 + 2)/3 = 1 sec
- average completion time = (1 + 12 + 3)/3 = 5.33 sec
What’s the advantage of timeslicing scheduling algorithm over SJF?
Don’t need prior knowledge of execution times.
Even though according to previous metric question, our throughput stays the same, and our average wait and average completion time are on par with SJF.
But a priori knowledge of execution times, is not feasible in real systems.
List 3 advantages of Timeslicing algorithm in general
- Short tasks finish sooner
- More responsive
- Lengthy I/O tasks initiated sooner
- List one disadvantage of Timeslice scheduling
- How can this disadvantage be mitigated?
-
Overhead of context switch.
* Depends on length of timeslice in comparison to context switching overhead - Choose the length of timeslice ‘enough’ longer than the overhead.
How long should a timeslice be?
Timeslices provide benefits to the system, but also come with certain ________. The ________ of the _______ and the overheads will inform the length of the timeslice.
The answer is different for _____ bound tasks vs. ______bound tasks.
Timeslices provide benefits to the system, but also come with certain overheads. The balance of the benefits and the overheads will inform the length of the timeslice.
The answer is different for I/O bound tasks vs. CPU bound tasks.
Two tasks that are only CPU bound, exec. time of each is 10 seconds, context switch time is 0.1 seconds
Calculate for timeslice = 1 sec
- Throughput
- Average Wait Time
- Average Completion Time
Calculate for timeslice = 1 sec
- Throughput = 2/(10 + 10 + 19*0.1) = 0.091 tasks/second
- Average Wait Time = (0 + 0.1 + 1.0) /2 = 0.55 seconds. Note that wait time for the 2nd task includes context switch time.
- Average Completion Time = (19 + 18*0.1 + 20 + 19*0.1)/2 = 42.7/2 = 21.35 sec
Note the short wait time
Note the long completion time
Two tasks that are only CPU bound, exec. time of each is 10 seconds, context switch time is 0.1 seconds
Calculate for timeslice = 5 sec
- Throughput
- Average Wait Time
- Average Completion Time
Calculate for timeslice = 5 sec
- Throughput = 2/(10 + 10 + 3*0.1) = 0.098 tasks/second
- Average Wait Time =(0 + (5+0.1)) / 2 = 2.55 seconds
- Average Completion Time = (15 + 2*0.1 + 20 + 3*0.1)/2 = 17.75
Two tasks that are only CPU bound, exec. time of each is 10 seconds, context switch time is 0.1 seconds
Calculate for timeslice = = infinite (run to completion)
- Throughput
- Average Wait Time
- Average Completion Time
Calculate for timeslice = infinity - NO PREEMPTION
- Throughput = 2/(10 + 10) = 0.1 tasks/second
- Average Wait Time =(0 + 10) / 2 = 5 seconds
- Average Completion Time = (10 + 20)/2 = 15 seconds
(Note no context switch overhead!)
With a smaller timeslice value, we have to pay the time cost of context switching more frequently.
With smaller timeslices is
- throughput higher or lower?
- completion time shorter or longer?
- average wait time shorter or longer?
With a smaller timeslice value, we have to pay the time cost of context switching more frequently.
With smaller timeslices is
- throughput lower
- completion longer
- average wait time shorter
Smaller timeslices mean that tasks are started ________, so our average wait time is _______ when we have smaller timeslices.
Average wait time for CPU bound tasks is important for the user. True or False?
Smaller timeslices mean that tasks are started sooner, so our average wait time is better when we have smaller timeslices.
False. The user cannot really perceive when a CPU bound task starts, so average wait time is not super important for CPU bound tasks. The user cares when a CPU bound task completes.
For CPU bound tasks, we are better off choosing a _________ timeslice.
If our timeslice value was infinite - that is to say we never ________ tasks - our metrics would be _____.
For CPU bound tasks, we are better off choosing a larger timeslice.
In fact, if our timeslice value was infinite - that is to say we never preempt tasks - our metrics would be best.
