Dispatching and scheduling
Tasks of multitasking OS are among others:
– Dispatching: Assign the CPU to another process (process switching)
Ready to Running state
– Scheduling: Determine the order of process execution and the exact
point in time when the process switch occurs
• The dispatcher carries out the state transitions of the processes
• The scheduler determines when these transitions happen
Performance consideration
The scheduler may run …
– periodically (e.g., on Linux)
– for every interrupt (e.g., on RIOT)
Should be efficient since scheduler is called very frequently
Every call to scheduler triggers the dispatcher to run
The Dispatcher
Tip
During process switching, dispatcher removes CPU from running
process -> assign to the process (first one in queue)
For transitions btw ready and blocked, -> dispatcher remove the
corresponding PCB from status list -> then insert a new process
Transition from or to a running state always imply a switch of the
process, which is currently executed by the CPU
If a process switches into running state or from the state running to other
state, the dispatcher job is to :
store the context (register contents) of the executed process in
the process control block (PCB)
assign the CPU to another process
restore the context (register contents) of the process, which will be
executed next, from its process control block (PCB)
If no process in a queue -> IDLE PROCESS
Idle Process
Many OS have an idle process
If no process is in the state ready an idle process gets the CPU
assigned
The idle process is always ready to run and has the lowest priority
Many modern CPU provide power-saving modes → most OS will enter a
power-saving mode when the idle process is running
For each CPU core (in hyperthreading systems for each logical CPU) a
system idle process exists
--> This idle process only be executed only when no other process is
ready to run
Scheduling
Scheduling Criteria and Scheduling Policies
• The scheduler of an OS specifies the order in which the dispatcher puts
the processes in the state ready
• The best scheduling policy (or scheduling algorithm) depends on the use
case
– No scheduling policy…
∗ is optimally suited for every system and
∗ can take all scheduling criteria optimal into account.
• The scheduling policy is always a trade-off between different scheduling
criteria
Scheduling criteria
Scheduling criteria are among others CPU load, response time
(latency), turnaround time, throughput, efficiency, real-time
behavior (compliance with deadlines), waiting time, overhead,
fairness, consideration of priorities, even resource utilization…
Non-preemptive and preemptive Scheduling
Two types of scheduling policies exist
– Non-preemptive scheduling or cooperative scheduling ==
∗ Any running process will either run until completion or voluntarily
yields
∗ Problematic: A process may occupy the CPU for as long as it wants
– Examples: Windows 3.x, MacOS 8/9, Windows 95/98/Me (for 16-Bit
processes)
**– Preemptive scheduling==**
∗ The CPU may be removed from a process before its execution is
completed
∗ Drawback: Higher overhead compared with non-preemptive scheduling
– Examples: Linux, MacOS X, Windows 95/98/Me (for 32-Bit processes),
Windows NT (incl. XP/Visa/7/8/10/11), FreeBSD, RIOT
Performance Metrics
Waiting Time
The time a process has to wait before getting the CPU assigned
CPU Time
The time that the process needs to access the CPU to complete its
execution
Runtime = ”lifetime” = time period between the creation and the
termination of a process = (CPU time + Waiting time)
Impact on Overall Performance of a Computer
-> Impact of Scheduling method -> on overall performance
Tip
Short running process runs before long-running process
-> runtime and waiting time -> slightly worse
Long-running process runs before short running process
-> Runtime and waiting time -> significantly worse
Scheduling Representation
Gantt chart -> represent order of process according to scheduling strategy
Scheduling Policies - Algorithm
– Each policy tries to comply with the well-known scheduling criteria and
principles in varying degrees
Priority Driven - Algorithm
Process runs according to their priority
The highest priority process in state ready get the CPU assigned
can be preemptive and non-preemptive
Priority value can be static or Dynamic
Static remain unchanged throughout lifetime -> realtime system
Dynamic priorities are adjusted during a process lifetime
Multilevel feedback scheduling
Risk of (static) priority driven -> process with low priority will be starving -
> NOT FAIR
Example
All processes are started at time point 0 in state ready
Runtime A = Runtime of (B + C + D + A) = 8 + 4+ 13 + 7 = 32
Similar to other Process
-> Then we have this table
First Come First Served (FCFS)
Works according to FIFO
Running process is not interrupted
It is non-preemptive scheduling
FCFS is fair -> process will eventually got scheduled
Average waiting time is high under some certain circumstances
Execution of short-lived process may have to wait for a long time if
processes with long execution time arrived before
FCFS/FIFO -> can be used for => Batch Processing
FIFO is used in LINUX for non-preemptive real-time process
Example ->
Last Come First Served (LCFS)
Works according to LIFO
-> Stack data structure
Running is not interrupted -> non-preemptive
CPU get assigned to process until process termination
NOT FAIR
-> continuous new process get created -> old process get ignored ,
starve
It can be used for batch processing -> Is seldom used in pure form
Examples -> slides
Last Come First Served – Preemptive Variant
(LCFS-PR)
A new process state ready replaces the currently executed process from the
CPU
+ Preempted processes are enqueued at the end
+ -> OS can interrupt and give CPU to this process
+ In case of non-new process -> the current process run till termination
Prefers processes with a short execution time
– The execution of a process with a short execution time may be
completed before new process are created
+ Processes with a long execution time may get the CPU resigned
several times and thus significantly delayed
NOT FAIR
long execution time may starve
Is seldom used in pure form
Earliest Deadline First (EDF)
Used in Real Time OS (RTOS)
Process would comply with their deadlines when possible
Process in state ready get assigned according to their deadline
Process with the closet deadline get CPU assigned next
The queue is reviewed and reorganized whenever
a new process switches into state ready
or an active process terminates
-> this mean it will assess the deadline of new process and reorganized
the waiting queue
• Can be implemented as preemptive and non-preemptive scheduling
– Preemptive EDF can be used in RTOS
– Non-preemptive EDF can be used for batch processing
• EDF is used in Linux for preemptive real-time processes
Round Robin (RR) - Operating Principle
Use time slice with a fixed duration (or even infinity time)
Processed are queued in a cyclic queue according to FIFO
Flow -> first process will be assigned CPU for a period
-> then it will resigned and is preempted -> queued at the end
Finish -> remove process -> new process will be inserted at the end
The CPU time is distributed fair among the processes
• RR with time slice size ∞ behaves like ⟶ FCFS
Shortest Job First (SJF) / Shortest Process Next
(SPN)
Shortest Execution Time -> get CPU assigned
Non-premptive scheduling
-> NOT FAIR
Prefer process which has shorter execution time
Longer execution time process will starving
The runtime of each process needs to be known in advance
Execution time is estimated by analyzing its behavior in the past
Shortest Remaining Time First (SRTF)
Preemptive SJF => is called shortest remaining time first
On process creation the remaining execution time of the running process is
compared with each process in state ready in the queue
if current -> has shortest -> CPU remain unchanged
if 1 or more in READY state -> shorter time -> process has shortest time
get assigned
Estimation of time is required
Processes with a long execution time may starve (⟹ not fair)
Longest Job First (LJF)
The process with the longest execution time get the CPU assigned first
Non-preemptive scheduling policy -> NOT FAIR
Prefer longer execution time
Short execution process will starving
Longest Remaining Time First (LRTF)
Preemptive LJF is called Longest Remaining Time First (LRTF)
The concept is similar to shortest remaining time first but now it targets the
longest time in the queue
Highest Response Ratio Next (HRRN)
Fair variant of SJF/SRTF/LJF/LRTF
– Takes the age of the process into account in order to avoid
starvation
Formular for response ratio
Response ratio value of a process after creation: 1.0
The value rises fast for short processes
since the execution time is small
-> it ratio value increase gonna be fast -> execute first
Objective: Response ratio should be as small as possible for each
process
After termination | a process is blocked -> CPU is assigned to the
process -> highest response ratio
• It is impossible that processes starve ⟹ HRRN is fair
Mutilevel Scheduling
Each scheduling policy require compromises wrt scheduling criteria
-> often we have multiple scheduling algorithm combines with each other
Procedure in practice: Several scheduling strategies are combined
⟹ Static or dynamic multilevel scheduling
Static Multilevel Scheduling
The list of process -> in ready state -> split into multiple sublists
each sublist -> different scheduling policy will be used
Sublist -> different priorities or time multiplexes (e.g., 80%:20% or
60%:30%:10%)
Which generally bad: since CPU cannot optimized to run which process
first
--> Impossible to separate time-critical or non-time-critical process
Note
When process turns to state ready -> it then get assigned to one of a
queue (class 1 or 2 or 3)
Each of the class will have it owns policy (scheduling) - RR, FCFS,
etc.
The mentioned process cannot go between classes
Each of the process will get assigned its priority level, and it is fixed
-> The CPU will execute sequentially from high to low priority
Lower priority process will have to wait
Multilevel Feedback Scheduling
It is impossible to predict the execution time precisely in advance
-> solution : Process which utilized much time in the past -> get accepted
Multilevel feedback scheduling works with multiple queues
Each queue has a different priority or time multiplex (e.g.,
70%:15%:10%:5%)
New process is added to top of queue -> highest priority
Each queue use round robin RR
Multilevel feedback scheduling is preemptive scheduling
-> prefer new process than older.
• Processes with many I/O operations are preferred because they
typically yield when waiting for I/O
• Older, longer-running processes are delayed
Note
A bit contrast to Static
Process get inserted into 1 queue
But in can be moved up or down according to the policy
Feedback :
It learns from how a process behave
It uses multiple queues. A new process starts at a highest queues, each
queue will use a RR with different time slice. If a process uses its entire time
slice, it moves to a lower priority queue. Higher priority processes might
preempt lower one.
Earliest Eligible Virtual Deadline First (EEVDF)
The goal of CFS and its successor, the EEVDF is to distribute the CPU
equally among all processes on the run queue
Scheduler -> take consider -> nice value : static process priority
vruntime -> weighted differently depending on nice value
Virtual clock can run at different speed
A process -> receive less time than deserved -> it has a positive lag value
– Only processes with a lag value >= 0 are eligible
– Only eligible processes are taken into account for being scheduled
Processes get assigned a virtual deadline
– This deadline is calculated by adding its latency nice value to its eligible
time
– The latency nice value represents the lengths of the processes time
slices
∗ I.e., the shorter the time slices of a process the earlier its deadline the
earlier it gets scheduled
In contrast to the EDF scheduling algorithm, EEVDF is designed for general
purpose desktop systems and not for hard real-time systems.
Note
The EEVDF work like this
Firstly, those process which receives CPU time less than deserved
Will be marked as eligible (positive lag value)
Then, the "nice value" decides the weight for each process
Nice value (negative) -> High weight -> Will be run first
Positive -> Low weight -> Delay run
The Scheduler will select the process with earliest deadline, based
on higher weight
Classic and modern scheduling methods
A scheduling policy is fair when each process gets the CPU assigned at
some point
Linux Scheduling Policies
In Linux e.g., each process is assigned to a specific scheduling policy
• For real-time processes…
– SCHED_FIFO (priority-driven scheduling, non-preemptive)
– SCHED_RR (preemptive)
– SCHED_DEADLINE (EDF scheduling, preemptive)
• For non real-time processes…
– SCHED_OTHER (default Linux time-sharing scheduling) implemented
as…
∗ Multilevel Feedback Scheduling (until Kernel 2.4)
∗ O(1) scheduler (Kernel 2.6.0 until 2.6.22)
∗ Completely Fair Scheduler (Kernel 2.6.23 until 6.5.13)
∗ Earliest Eligible Virtual Deadline First (since Kernel 6.6)
Exercise 7
When we compile with -c flag -> tell the shell compiler that just compile
do not invoke the linker -> so the file will not try to link the function with the
machine code
--> it will return a .o (e.g file1.o) file