Scheduler
Short-term scheduler
Selects from among the processes in ready queue
Allocates the CPU to one of them
Queue may be ordered in various ways
Decisions may take place when a process
Terminates
Switches from waiting to ready
Switches from running to ready state
Switches from running to waiting state
Dispatcher
Gives control of the CPU to the process selected by the short-term scheduler
Tasks
Switching to user mode
Switching context
Jumping to the proper location in the user program to restart that program
Latency
Time it takes for the dispatcher to stop one process and start another running
Definitions
CPU utilization – keep the CPU as busy as possible
Throughput – # of processes that complete their execution per time unit
Turnaround time – amount of time to execute a particular process
Waiting time – amount of time a process has been waiting in the ready queue
Response time – amount of time it takes from when a request was submitted until the first response is produced, not output
Criteria
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
Scheduling Algorithm
First-Come, First-Served (FCFS)
Shortest Job First (SJF)
Convoy effect: short process behind long process
Associate with each process the length of its next CPU burst
Use these lengths to schedule the process with the shortest time
SJF is optimal – gives minimum average waiting time for a given set of processes
The difficulty is knowing the length of the next CPU request
CPU Burst
Determine length of next CPU burst
Can only estimate the length
Then pick process with shortest predicted next CPU burst
Can be done by using the length of previous CPU bursts
Prioridad
SJF is priority scheduling where priority is the inverse of predicted next CPU burst time
The CPU is allocated to the process with the highest priority
A priority number (integer) is associated with each process
Problem: Starvation
Solution: Aging
Round Robin
Each process gets a small unit of CPU time
Usually 10-100 milliseconds
After the time has elapsed, the process is preempted and added to the end of the ready queue
If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once.
No process waits more than (n-1)q time units
Timer interrupts every quantum to schedule next process
Multilevel Queue
Ready queue is partitioned into separate queues
Foreground
Background
Each queue has its own scheduling algorithm
Foreground – RR
Background – FCFS
Scheduling must be done between the queues
Multilevel Feedback Queue
A process can move between the various queues; aging can be implemented this way
Scheduler defined by parameters
Number of queues
Scheduling algorithms for each queue
Method used to determine when to upgrade a process
Method used to determine when to demote a process
Method used to determine which queue a process will enter when that process needs service
Threads
When threads supported, threads scheduled, not processes
Kernel thread scheduled onto available CPU is system-contention scope
Balance Load
Push migration – periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs
Pull migration – idle processors pulls waiting task from busy processor
Real Time Scheduling
Soft real-time systems – no guarantee as to when critical real-time process will be scheduled
Hard real-time systems – task must be serviced by its deadline
Latencies
Interrupt latency – time from arrival of interrupt to start of routine that services interrupt
Dispatch latency – time for schedule to take current process off CPU and switch to another
Conflicts
Preemption of any process running in kernel mode
Release by low-priority process of resources needed by high-priority processes
Priority-based Scheduling
For real-time scheduling, scheduler must support preemptive, priority-based scheduling
For hard real-time must also provide ability to meet deadlines
Virtualization and Scheduling
Each guest doing its own scheduling
Can effect time-of-day clocks in guests
Can result in poor response time
Not knowing it doesn’t own the CPUs
Virtualization software schedules multiple guests onto CPU(s)
Can undo good scheduling algorithm efforts of guests
Linux Scheduling
Completely Fair Scheduler (CFS)
Scheduling classes
Each has specific priority
Scheduler picks highest priority task in highest scheduling class
Rather than quantum based on fixed time allotments, based on proportion of CPU time
2 scheduling classes included, others can be added
default
real-time