P3L1 - Scheduling Flashcards
What is the role of the CPU Scheduler?
To decide how and when the processes (and their threads) access the shared CPUs
T/F: Scheduler concerns itself with both user level tasks and kernel level tasks
True!
When do you need to run the scheduler?
Whenever the CPU becomes idle
What is a common amount of time given to a task?
Timeslice
What are the steps that occur when the scheduler selects a task to be scheduled?
- Switch to new task
- Enter user mode
- Set program counter
- Execution begins!
What is the structure of the ready queue known as?
runqueue
_____ scheduling assumes that once a task is assigned to a CPU, it will run on that CPU until its finished
Run to Completion
What are some common metrics for comparing schedulers?
- Throughput
- Average job completion time
- Average job wait time
- CPU utilization
_____ algorithm has tasks scheduled in the order in which they arrive?
First come First serve (FCFS)
What is an alternative to using execution time when choosing tasks to schedule?
Priority levels
When scheduling based on priority levels, which task should run first?
The task with the highest priority level
What is an effective way to be able to quickly tell a task’s priority
Maintain a separate runqueue for each priority level
What is one dangerous situation that can occur with priority scheduling?
Starvation
What is starvation in the context of scheduling?
When low priority tasks are essentially never scheduled because higher priority tasks continually enter the system and take precedence
What is one mechanism to protect against starvation?
Priority aging - The priority of a task is not just the numerical property but a function of the actual priority and the amount of time the task has spent in the runqueue
What is priority inversion?
When the highest priority task that SHOULD run cannot run because the lowest priority task is holding a mutex it needs
What is one way to combat priority inversion?
Temporarily boost the priority of the mutex owner long enough to allow it to complete
Define a timeslice?
The maximum amount of uninterrupted time that can be given to a task
T/F: A task may run for a smaller amount of time than what the timeslice specifies?
True!
What is one use of timeslices?
To allow tasks to be interleaved
What are the downsides of timeslicing?
The overhead - We have to interrupt the running task, execute the scheduler ,and have to context switch to the new task
How long should a timeslice be?
CPU intensive tasks –> Prefer longer timeslice values
I/O intensive tasks –> Prefer shorter timeslice values
T/F: A runqueue data structure is only LOGICALLY a queue?
True! It can be implemented as multiple queues or even a tree
____ is a structure that maintains multiple distinct queues, each differentiated by their timeslice values
Multi queue
