Processes

MCS-041
Block-1
Unit-2(b)
 Process Scheduling

The process scheduling is the activity of the process manager that handles the

removal of the running process from the CPU and the selection of another process on

the basis of a particular strategy.

Process scheduling is an essential part of a Multiprogramming operating system.

Such operating systems allow more than one process to be loaded into the

executable memory at a time and loaded process shares the CPU using time

multiplexing.
 Scheduling Queues
Scheduling queues refers to queues of processes or devices. When the process enters into the
system, then this process is put into a job queue. This queue consists of all processes in the
system. The operating system also maintains other queues such as device queue. Device queue
is a queue for which multiple processes are waiting for a particular I/O device. Each device
has its own device queue.
 Objectives of Scheduling

Maximize
Throughput

Balance Enforce
resource use Priorities

Objectives
of
Scheduling
Avoid
Minimize
indefinite
overhead
postponement

Be predictable
 Objectives of Scheduling
• Minimize Response Time
– Elapsed time to do an operation (job)
– Response time is what the user sees
• Time to echo keystroke in editor
• Time to compile a program
• Real-time Tasks: Must meet deadlines imposed by World
• Maximize Throughput
– Jobs per second
– Throughput related to response time, but not identical
• Minimizing response time will lead to more context switching than if you
maximized only throughput
– Minimize overhead (context switch time) as well as efficient use of resources (CPU,
disk, memory, etc.)
• Fairness
– Share CPU among users in some equitable way
– Not just minimizing average response time
 Types of Schedulers
 LONG TERM SCHEDULER

 Run seldom ( when job comes into memory )

 Controls degree of multiprogramming
 Tries to balance arrival and departure rate through an appropriate job mix.

 SHORT TERM SCHEDULER

Contains three functions:

 Code to remove a process from the processor at the end of its run.
a)Process may go to ready queue or to a wait state.

 Code to put a process on the ready queue –

a)Process must be ready to run.
b)Process placed on queue based on priority.
 Types of Schedulers
SHORT TERM SCHEDULER (cont.)

 Code to take a process off the ready queue and run that process (also called
dispatcher).
a) Always takes the first process on the queue (no intelligence required)
b) Places the process on the processor.

• This code runs frequently and so should be as short as possible.

 MEDIUM TERM SCHEDULER

• Mixture of CPU and memory resource management.

• Swap out/in jobs to improve mix and to get memory.

• Controls change of priority.

Comparison between Schedulers
 Scheduling Criteria
CPU Utilization: CPU utilization is the ratio of busy time of the processor to the total time
passes for processes to finish.
Processor Utilization = (Processor busy time) / (Processor busy time + Processor idle
time)

Throughput: It refers to the amount of work completed in a unit of time.

Throughput = (No. of processes completed) / (Time unit)

Turnaround Time : It may be defined as interval from the time of submission of a process to
the time of its completion.
Turnaround Time = t(Process completed) – t(Process submitted)
 Scheduling Algorithms

Waiting Time: This is the time spent in the ready queue.

Waiting time = Turnaround Time - Processing Time

Response time: It is most frequently considered in time sharing and real time operating
system.
Response time = t(first response) – t(submission of request)
 Scheduling Algorithms
• Non-preemptive scheduling:
– The running process keeps the CPU until it voluntarily
gives up the CPU
• process exits
• switches to blocked state
• Transition 3 is only voluntary
4
Running Terminated
1
• Preemptive scheduling: 3

– The running process can be Ready Blocked

interrupted and must release
the CPU (can be forced
to give up CPU)
 Simple Processor Scheduling
Algorithms
• Batch systems

– First Come First Serve (FCFS)

– Shortest Job First

• Interactive Systems

– Round Robin

– Priority Based scheduling

 First Come First Serve (FCFS)

• Process that requests the CPU FIRST is allocated the CPU FIRST.

• Also called FIFO

• Used in Batch Systems

• FCFS is non-preemptive.

• Implementation
– FIFO queue

– A new process enters the tail of the queue

– The scheduler selects the process at the head of the queue.

FCFS Example
 Problems with FCFS

• Non-preemptive

• Does not minimize AWT

• Cannot utilize resources in parallel:

– Assume 1 process CPU bounded and many I/O bounded

processes

– result: Convoy effect, low CPU and I/O Device utilization

– Why?
 Shortest-Job First (SJF)

This algorithm is assigned to the process that has smallest next CPU processing
time, when the CPU is available. It is Non-preemptive. It is originally implemented in
a batch-processing environment.

Example of SJF:
Shortest-Job First (SJF)
 Round Robin (RR)
• Round Robin (RR) scheduling is a preemptive algorithm that relates the
process that has been waiting the longest.

• One of the oldest, simplest, most commonly used scheduling algorithm

• primarily used in time-sharing and a multi-user system environment where the

primary requirement is to provide reasonably good response times

• Select process/thread from ready queue in a round-robin fashion (take turns)

Problems:

• Does not consider priority

• Context switch overhead

Preemption after
quantum
expiration
Example of Round Robin
 Shortest Remaining Time Next (SRTN)

This is the preemptive version of shortest job first. This permits a process that

enters the ready list to preempt the running process if the time for the new process

(or for its next burst) is less than the remaining time for the running process (or for

its current burst). Example:

Example of SRTN
 Priority Based Scheduling or Event-
Driven (ED) Scheduling
A priority is associated with each process and the scheduler always picks up the highest
priority process for execution from the ready queue. Equal priority processes are scheduled
FCFS. The level of priority may be determined on the basis of resource requirements,
processes characteristics and its run time behavior.
Example of Priority Based Scheduling
 Performance Evaluation of the scheduling
Algorithm

The performance of the algorithms can be evaluated on the basis of two factors.

These are:

 Maximize CPU utilization with the maximum response time.

 Maximize throughput.
THANK
YOU