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