PROCESS
SCHEDULING
IN LINUX
01. PROCESS TYPES
02. THE SCHEDULING ALGORITHM
03. REAL TIME SCHEDULING
04. TIME SHARING
TABLE OF
CONTENT
HISTORY OF THE SCHEDULING ALGORITHMS
EARLIER VERSION OF LINUX: SIMPLE AND STRAIGHTFORWARD
SCAN THE RUNNABLE PROCESSES, COMPUTE THE PRIORITIES, AND
SELECT THE BEST TO RUN
MUCH MORE COMPLEX IN LINUX 2.6
SCALES WELL WITH THE NUMBER OF PROCESSES AND PROCESSORS
CONSTANT TIME SCHEDULING
3 SCHEDULING CLASSES
SCHED_FIFO: FIRST-IN FIRST-OUT REAL-TIME
SCHED_RR: ROUND-ROBIN REAL-TIME
SCHED_NORMAL: CONVENTIONAL TIME-SHARED PROCESSES
ROUND ROBIN APPROACH
Initially, the LINUX kernel used the RR or Round-Robin approach to
schedule the processes.
In the Round-Robin approach, a circular queue was maintained that
held the processes.
The advantage of using a round-robin was its fast behavior and easy
implementation.
PROCESS TYPES
PROCESSs
Real Time Normal
Interactive Batch
01. O(N)
n is the number of runnable processes in the system.
O(n) scheduler divides the processor's time into a unit called
epochs.
Each task is allowed to use at max 1 epoch. If the task is not
completed in the specified epoch, then the scheduler adds half of
the remaining time in the next epoch.
O(n) scheduler was better than the earlier used circular queue
scheduler because O(n) scheduler could schedule N-processes at a
time.
02. O(1)
O(1) scheduler uses two queues.
The active processes are placed in a queue called RUN QUEUE that
stores the priority value of each process.
The other queue is an array of expired processes called expired
queue. When the allotted time of a process expires, it is placed
into the expired queue.
CFS SCHEDULER
CFS tries to model an “ideal, precise multitasking CPU” – one that
could run multiple processes simultaneously, giving each equal
processing power.
CFS SCHEDULER
We may not be able to have one CPU run things simultaneously, but we
can measure how much runtime each task has had and try and ensure
that everyone gets their fair share of time.
CFS SCHEDULER
CFS is quite simple algorithm for the process scheduling and it is
implemented using RED BLACK Trees and not queues.
So all the process which are on main memory are inserted into Red
Black trees and whenever a new process comes it is inserted into
the tree. As we know that Red Black trees are self Balancing binary
Search trees.
The key for each node is the
vruntime of the
corresponding task.
To pick the next task to
run, simply take the
leftmost node.
When the scheduler is invoked to run a new process:
1. The leftmost node of the scheduling tree is chosen (as it will have the lowest spent
execution time), and sent for execution.
2. If the process simply completes execution, it is removed from the system and
scheduling tree.
3. If the process reaches its maximum execution time or is otherwise stopped
(voluntarily or via interrupt) it is reinserted into the scheduling tree based on its
newly spent execution time(virtual time).
4. The new leftmost node will then be selected from the tree, repeating the iteration.
So this way each process gets fair time for the execution as after every context switch
the virtual time of a process increases and thus priority shuffles.
THANK YOU
