Scheduling - Chapter 5

Basic

CPU burst - when the cpu executes the process

IO burst - when waiting on IO

Preemptive - when the process is forced to stop running with out its content (Interrupt), can also mean that the process can be stopped

Non-Preemptive - when the process willingly stops processing (terminates, waiting), can also mean that the process cannot be stopped

Dispatcher

Dispatcher - is what does the context switch, points to the next command, switches to user-mode

Dispatch latency - time from the end of one process to the start of the next

Voluntary - non-preemptive

Involuntary - preemptive

Goals

CPU utilisation - make it work as hard as possible

Though-put - number of processes that complete per n time

Turn around time - time it takes for a process to finish execution

Waiting time - time it takes for the process to start execution since joining the ready queue

Response time - turn around time + waiting time

FCFS

first come first serve

• avg wait time can be anything

• it is non-preemptive

SJF

shortest job first:

• not really possible since how do you know the length of the next job

• so job length is determined by the duration of the last cpu-burst

• non-preemptive

SRJF

shortest remaining job first:

• the same as SJF but will switch context if there is a new shorter job

• preemptive

RR

round robin:

• time quantum is specified (10ms)

• if job exceeded time quantum on cpu burst then it is swapped, and sent to the back of the ready queue

• time quantum should not be too low since too many context switches

Priority scheduling

• levels of priority are made, only tasks with the highest priority are executed

• this may cause starvation, so ageing increases priority

• SJF is an example

Multi level queues

• multiple queues, each queue has a priority level

• each queue will have another scheduling mechanism within i.e. RR

• Typically foreground processes have higher priority over batch processes

• Ageing can allow a process to move up levels

• Processes can also be demoted, for example if they take too long

level 0, if the task takes longer than 8, it will be demoted to level 1

level 1, if the taks takes longer than 16, it will be demaoted to level 2

level 2, first come first serve

Thread scheduling

process-concentration scope - the order in which threads within a kernel thread are executed

system-concentration scope - the order in which all kernel threads are executed

Asymmetric Multiprocessing and Symmetric Multiprocessing

Asymmetric Multiprocessing - once core is a master, and does the scheduling to the slaves

Symmetric Multiprocessing - all cores do their own scheduling (better cos its faster + more energy efficient); note this comes in two varients

• one common ready queue

• each core has its own ready queue

Multiprocessor Scheduling

Multithreading/ hyperthreading - in a memory stall, a new processes starts execution

If each core has its own queue, then please note the following definitions:

• load balancing - evenly distribute the workload

• push migration - if too much work push a process to another core’s queue

• pull migration - if too little work pull a process from another core’s queue

Processor affinity - processes want to stay on the same core, since it is quicker

soft affinity - don’t want to stay that much

hard affinity - HAS TO STAY