Scheduling algo(by HJ)

What is CPU Scheduling…?
It decides which processes will run when there are
multiple runnable processes.
Why CPU Scheduling is used…?
In General term the aim of CPU Scheduling is to
make the System efficient, fast and fair.
The I/O will take a long time, and we never want to
leave the CPU idle, while waiting for the I/O to finish.

Basic assumption behind the Scheduling Algorithms:-
 There is a pool of runnable processes contending for
the CPU.
The OS is a multitasking, but not a multiprocessor
 The processes are independent and compete for
resources.
 The job of the Scheduler is to distribute the scarce
resource of the CPU to the different processes ‘fairly’.

Long-term scheduler:
admits new processes to
the system;
required because each
process needs a portion of
the available memory for its
code and data.
Short-term scheduler:
determines the assignment
of the CPU to ready
processes;
required because of IO
requests and completions.
Hard Disk RAM CPU

Scheduling Management
Processes are managed through the use of multiple
queues of PCB's.
The job queue contains all jobs submitted to the
system, but not yet in main memory.
The ready queue contains all jobs in main memory
ready to execute.
Each I/O device has a queue of jobs waiting for
various I/O operations.
A process is then dispatched from the ready queue to
the CPU.

Some terms related to Scheduling…
3.Waiting Time:- Waiting time is the sum of the periods spent
waiting in the ready queue.
2.Throughput:- The number of processes that are
completed per time unit, called throughput.
1. CPU Utilization :- Conceptually, CPU utilization can range
from 0 to 100 percent. In a real system, it should range from 40
percent (for a lightly loaded system) to 90 percent (for a heavily
used system).

6.Burst Cycle :- Process cycles between CPU processing
and I/O activity. The cycles are of two types:-
- CPU Burst Cycle
- I/O Burst Cycle
5.Respond Time :- The measure of the time from the
submission of a request until the first response is
produced.
4 .Turn-around Time :- Turnaround time is the sum of
the time spent waiting to get into memory, waiting in the
ready queue, executing on the CPU, and doing I/O.

8.CPU Bound Processes :- Processes that perform lots of
computation and do little IO.
7. IO Bound Processes :- Processes that perform lots of IO
operations.
Ex. Calculator
- Ready
9. Process States :-
- Running
- Waiting

10. PCB :- Process Control Block is a data structure in
the OS containing the information needed to manage a
particular process. The PCB is "the expression of a
process in an operating system.”
11. Pre-emptive & Non Pre-emptive
When a process switches from the
Running waiting
Running ready
Waiting ready
When a process terminates
Non Pre-
emptive
Pre-emptive

FCFS
Shortest Job First
Multi-Level Scheduling
Round Robin
Priority Queue
Multi-level Feedback Queue Scheduling

First Come First Serve
- Jobs are executed on first come, first serve basis.
- Easy to understand and implement.
- Poor in performance as average wait time is high.
Thus, it is rarely used in modern operating systems, but
is sometimes used inside of other scheduling systems.

Ex.:-
Process Process Time (ms)
P1 24
P2 3
P3 3
P1 P2 P3
Time 0 24 27
Average waiting time= (0+24+27)/3 17 ms

Advantage:-
Simple
Easy to implement
Dis-advantage:-
This scheduling method is non-preemptive.
 Because of this non-preemptive scheduling, short
processes which are at the back of the queue have to
wait for the long process at the front to finish

Shortest Job First
 It works, when the CPU is available, it is assigned to the
process that has the smallest next CPU burst.
- If the next CPU bursts of two processes are the same,
FCFS scheduling is used.
- Impossible to implement as we cannot always predict the
future (i.e., we do not know the next burst length)

Shortest Job First
decreases the waiting time of the short process more than it
increases the waiting time of the long process.
 Consequently, the average waiting time decreases.
 SJF scheduling is used frequently in long-term scheduling.
 Moving a short process before a long one………

Ex:-
Process Process Time
P1 6
P2 8
P3 7
P4 3
P4 P1 P3 P2
Time 0 3 9 16 24
Average Waiting Time = (0+3+9+16)/4 7 ms

Ex:-
Process Arrival Time Process Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
P1 P2 P4 P1 P3
Time 0 1 5 10 17
Average Waiting Time = [(10-1)+(1-1)+(17-2)+(5-3)]/4
6.5 ms
SJF is sometimes called shortest-remaining-time-first-
scheduling

Priority Queue
The basic idea is straightforward: each process is assigned a
priority, and highest priority is allowed to run.
 Equal-Priority processes are scheduled in FCFS order.
 The shortest-Job-First (SJF) algorithm is a special case of
general priority scheduling algorithm.

Priorities can be defined either internally or externally
Internally defined priorities use some measurable
quantities to compute the priority of a process, such as
 time limits  memory requirements  the number of open files
 the ratio of average I/O burst to average CPU burst
External priorities are set by criteria outside the OS,
such as
 the amount of funds being paid for computer use
 such as the importance of the process
 other, political factors.

 Priority scheduling can suffer from a major problem known
as indefinite blocking, or starvation.
 Priority scheduling can be either preemptive or non-
preemptive.
 In which a low-priority task can wait forever because there
are always some other jobs around that have higher priority.
 A solution to the problem of indefinite blockage of the low-
priority process is Aging.
 Aging is a technique of gradually increasing the priority of
processes that wait in the system for a long period of time.

Ex:-
Process Process Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Time
P2 P5 P1 P3
0 1 6 16
Average Waiting Time = (0+1+6+16+18)/4 8.2 ms
P4
18

Round Robin
It is specially designed for Time-Sharing System
 It is similar to FCFS scheduling, but preemption is
added to switch between processes.
 Each process is provided a fix time to execute called
quantum.
 Once a process is executed for given time period.
Process is preempted and other process executes for
given time period.

sets a timer to interrupt after 1
time quantum
 The CPU scheduler picks the first process
from the ready queue
and dispatches the process.
 Therefore, one of two things will then happen.
 The process may have a CPU burst of less than 1
time quantum.
 Otherwise, a context switch will be executed, and
the process will be put at the tail of the ready
queue.

If there are n process in the ready Queue and the
time quantum is q, then each process must wait no
longer then…
(n-1) x q time units (until its next time quantum)
For Ex.:-
n=4 And q=10ms
Time till second chance
(4-1) x 10 =30 ms

Now, the choice of how big to make the time
quantum(q) is extremely important
If q is very large then,
Round Robin degenerates into FCFS
If q is very small,
the context switch overhead defeats
the benefits, & the RR approach is called
processor sharing.

Example:
Process Process Time
P1 24
P2 3
P3 3
Time
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26
Average Waiting Time = (0+4+7+(10-4))/3 5.6 ms

Multi-level Scheduling
Multiple queues are maintained for processes.
Each queue can have its own scheduling algorithms.
Priorities are assigned to each queue.
The processes are permanently assigned to one queue,
generally based on some property of the process, such as
memory size, process priority, or process type.

Ex. of a Ready queue of multi-queue algorithm:

Scheduling must be done between queues, because:
 fixed priority (may lead to starvation) (e.g.,
foreground jobs have absolute priority over
background jobs)
 time slice per queue

Multi-level Feedback Queue
Scheduling
In this Processor are permanently assigned to a
queue
The Multi-level Feedback Queue Scheduling,
algorithm, in contrast, allow a process to move
between queues.
If a process uses too much CPU time, it will be
moved to a lower-priority queue.

Multi-level Feedback Queue
Scheduling
This Scheme leaves I/O bound and interactive
process in the higher-priority queue.
In addition, a process waits too long in a lower –
priority queue may be moved into a higher-
priority queue.
The idea is to separate processes according to
the characteristics of their CPU bursts.

For example, consider a multilevel feedback-queue
scheduler with three queues, numbered from 0 to 2.
 The scheduler first executes all processes in queue
0.
 Only when queue 0 is empty will it execute
processes in queue 1.
 Similarly, processes in queue 2 will only be
executed if queues 0 and 1 are empty.
 While executing queue 1, if a process arrives in queue
0 – then pre-emption will take place

A process entering the ready Queue is put in queue 0.
A process in queue 0 is given a time quantum of 8
millisecond
If queue 0 is empty the process at the head of queue
1 is given a quantum of 16 millisecond.
Process in queue 2 are run on an FCFS basis but
are run only when queues o and 1 are empty
If it does not finish within this time, it is moved to the tail of queue 1.
If it does not complete, it is preempted and is put into queue 2

This scheduling algorithm gives highest priority to
any process with a CPU burst of 8 millisecond or less
Processes that need more then 8 but less then 24
millisecond are also served quickly, although with lower
priority then shorter processes.
Long processes automatically sink to queue 2 and
served in FCFS order with any CPU cycles left over from
queues 0 and 1.

Scheduling algo(by HJ)

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

Similar to Scheduling algo(by HJ) (20)

Recently uploaded (20)

Scheduling algo(by HJ)