A Process Scheduler schedules different processes to be assigned to the CPU based
on particular scheduling algorithms. There are six popular process scheduling
algorithms which we are going to discuss in this chapter −
First-Come, First-Served (FCFS) Scheduling
Shortest-Job-Next (SJN) Scheduling
Priority Scheduling
Shortest Remaining Time
Round Robin(RR) Scheduling
Multiple-Level Queues Scheduling
Scheduling Algorithms
Scheduling algorithms are used for distributing resources among parties
which simultaneously and asynchronously request them. Scheduling
disciplines are used in routers (to handle packet traffic) as well as in
operating systems (to share CPU time among both threads and processes),
disk drives (I/O scheduling), printers (print spooler), most embedded
systems, etc.
The main purposes of scheduling algorithms are to minimize resource
starvation and to ensure fairness amongst the parties utilizing the resources.
Scheduling deals with the problem of deciding which of the outstanding
requests is to be allocated resources. There are many different scheduling
algorithms. In this section, we introduce several of them.
In packet-switched computer networks and other statistical multiplexing, the
notion of a scheduling algorithm is used as an alternative to first-come first-
served queuing of data packets.
The simplest best-effort scheduling algorithms are round-robin, fair queuing
(a max-min fair scheduling algorithm), proportionally fair scheduling and
maximum throughput. If differentiated or guaranteed quality of service is
offered, as opposed to best-effort communication, weighted fair queuing may
be utilized.
In advanced packet radio wireless networks such as HSDPA (High-Speed
Downlink Packet Access) 3.5G cellular system, channel-dependent
scheduling may be used to take advantage of channel state information. If
the channel conditions are favourable, the throughput and system spectral
efficiency may be increased. In even more advanced systems such as LTE,
the scheduling is combined by channel-dependent packet-by-packet dynamic
channel allocation, or by assigning OFDMA multi-carriers or other frequency-
domain equalization components to the users that best can utilize them.
What is CPU Scheduling?
CPU Scheduling is a process of determining which process will own CPU for execution while
another process is on hold. The main task of CPU scheduling is to make sure that whenever the
CPU remains idle, the OS at least select one of the processes available in the ready queue for
execution. The selection process will be carried out by the CPU scheduler. It selects one of the
processes in memory that are ready for execution.
Important CPU scheduling Terminologies
Burst Time/Execution Time: It is a time required by the process
to complete execution. It is also called running time.
Arrival Time: when a process enters in a ready state
Finish Time: when process complete and exit from a system
Multiprogramming: A number of programs which can be
present in memory at the same time.
Jobs: It is a type of program without any kind of user interaction.
User: It is a kind of program having user interaction.
Process: It is the reference that is used for both job and user.
CPU/IO burst cycle: Characterizes process execution, which
alternates between CPU and I/O activity. CPU times are usually
shorter than the time of I/O.
Maximize
CPU utilization:CPU utilization is the main task in which the operating
system needs to make sure that CPU remains as busy as possible. It
can range from 0 to 100 percent. However, for the RTOS, it can be
range from 40 percent for low-level and 90 percent for the high-level
system.
Throughput: The number of processes that finish their execution per
unit time is known Throughput. So, when the CPU is busy executing
the process, at that time, work is being done, and the work completed
per unit time is called Throughput.
Minimize
Waiting time: Waiting time is an amount that specific process needs
to wait in the ready queue.
Response time: It is an amount to time in which the request was
submitted until the first response is produced.
Turnaround Time: Turnaround time is an amount of time to execute a
specific process. It is the calculation of the total time spent waiting to
get into the memory, waiting in the queue and, executing on the CPU.
The period between the time of process submission to the completion
time is the turnaround time.
First Come First Serve (FCFS)
Jobs are executed on first come, first serve basis.
It is a non-preemptive, pre-emptive scheduling algorithm.
Easy to understand and implement.
Its implementation is based on FIFO queue.
Poor in performance as average wait time is high.
Since context switches only occur upon process termination, and no
reorganization of the process queue is required, scheduling overhead
is minimal.
Throughput can be low, because long processes can be holding the
CPU, causing the short processes to wait for a long time (known as the
convoy effect).
No starvation, because each process gets chance to be executed after
a definite time.
Turnaround time, waiting time and response time depend on the order
of their arrival and can be high for the same reasons above.
No prioritization occurs, thus this system has trouble meeting process
deadlines.
The lack of prioritization means that as long as every process
eventually completes, there is no starvation. In an environment where
some processes might not complete, there can be starvation.
It is based on queuing.
Shortest Job Next (SJN)
This is also known as shortest job first, or SJF
This is a non-preemptive, pre-emptive scheduling algorithm.
Best approach to minimize waiting time.
Easy to implement in Batch systems where required CPU time is known in
advance.
Impossible to implement in interactive systems where required CPU time is not
known.
The processer should know in advance how much time process will take.
imilar to shortest job first (SJF). With this strategy the scheduler arranges
processes with the least estimated processing time remaining to be next in
the queue. This requires advanced knowledge or estimations about the time
required for a process to complete.
If a shorter process arrives during another process' execution, the
currently running process is interrupted (known as preemption),
dividing that process into two separate computing blocks. This creates
excess overhead through additional context switching. The scheduler
must also place each incoming process into a specific place in the
queue, creating additional overhead.
This algorithm is designed for maximum throughput in most scenarios.
Waiting time and response time increase as the process's
computational requirements increase. Since turnaround time is based
on waiting time plus processing time, longer processes are significantly
affected by this. Overall waiting time is smaller than FIFO, however
since no process has to wait for the termination of the longest process.
No particular attention is given to deadlines, the programmer can only
attempt to make processes with deadlines as short as possible.
Starvation is possible, especially in a busy system with many small
processes being run.
To use this policy we should have at least two processes of different
priority
Priority Based Scheduling
Priority scheduling is a non-preemptive algorithm and one of the most common
scheduling algorithms in batch systems.
Each process is assigned a priority. Process with highest priority is to be
executed first and so on.
Processes with same priority are executed on first come first served basis.
Priority can be decided based on memory requirements, time requirements or
any other resource requirement.
Shortest Remaining Time
Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
The processor is allocated to the job closest to completion but it can be
preempted by a newer ready job with shorter time to completion.
Impossible to implement in interactive systems where required CPU time is not
known.
It is often used in batch environments where short jobs need to give preference.
Round Robin Scheduling
Round Robin is the preemptive process scheduling algorithm.
Each process is provided a fix time to execute, it is called a quantum.
Once a process is executed for a given time period, it is preempted and other
process executes for a given time period.
Context switching is used to save states of preempted processes.
Time on the CPU is divided into equal parts called “time slices”. Time
slices are allocated to each program equally and cyclically. This
means that if we had a list of three programs running, the CPU would
run:
Program 1 for one time slice
Program 2 for one time slice
Program 3 for one time slice
and would repeat this order until one of the programs finished.
The scheduler assigns a fixed time unit per process, and cycles through
them. If process completes within that time-slice it gets terminated
otherwise it is rescheduled after giving a chance to all other processes.
RR scheduling involves extensive overhead, especially with a small
time unit.
Balanced throughput between FCFS/ FIFO and SJF/SRTF, shorter jobs
are completed faster than in FIFO and longer processes are completed
faster than in SJF.
Good average response time, waiting time is dependent on number of
processes, and not average process length.
Because of high waiting times, deadlines are rarely met in a pure RR
system.
Starvation can never occur, since no priority is given. Order of time
unit allocation is based upon process arrival time, similar to FIFO.
If Time-Slice is large it becomes FCFS /FIFO or if it is short then it
becomes SJF/SRTF.
Multiple-Level Queues Scheduling
Multiple-level queues are not an independent scheduling algorithm. They make use of
other existing algorithms to group and schedule jobs with common characteristics.
Multiple queues are maintained for processes with common characteristics.
Each queue can have its own scheduling algorithms.
Priorities are assigned to each queue.
Summary
CPU scheduling is a process of determining which process will
own CPU for execution while another process is on hold.
In Preemptive Scheduling, the tasks are mostly assigned with
their priorities.
In the Non-preemptive scheduling method, the CPU has been
allocated to a specific process.
The burst time is the time required for the process to complete
execution. It is also called running time.
CPU utilization is the main task in which the operating system
needs to ensure that the CPU remains as busy as possible.
The number of processes that finish their execution per unit time
is known Throughput.
Waiting time is an amount that a specific process needs to wait
in the ready queue.
It is the amount of time in which the request was submitted until
the first response is produced.
Turnaround time is the amount of time to execute a specific
process.
Timer interruption is a method that is closely related to
preemption.
A dispatcher is a module that provides control of the CPU to the
process.
Six types of process scheduling algorithms are: First Come First
Serve (FCFS), 2) Shortest-Job-First (SJF) Scheduling, 3)
Shortest Remaining Time, 4) Priority Scheduling, 5) Round
Robin Scheduling, 6) Multilevel Queue Scheduling.
In the First Come First Serve method, the process which
requests the CPU gets the CPU allocation first.
In the Shortest Remaining time, the process will be allocated to
the task closest to its completion.
In Priority Scheduling, the scheduler selects the tasks to work as
per the priority.
Round robin scheduling works on the principle where each
person gets an equal share of something in turn.
In the Shortest job first, the shortest execution time should be
selected for execution next.
The multilevel scheduling method separates the ready queue
into various separate queues. In this method, processes are
assigned to a queue based on a specific property.
The CPU uses scheduling to improve its efficiency.