Process Scheduling in Operating System

What is Process Scheduling in Operating System? Its Importance and objective?

Process scheduling is an essential part of a multiprogramming operating system. such OS allow more than one process to load in executable memory at a time and share CPU using time multiplexing. 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.

In uniprogramming like MS DOC time spent waiting for I/O is wasted and CPU is free during this time.

In multiprogramming one process can use CPU while another is waiting for I/O this is only possible with process scheduling.

Basic Concepts

Bursts of CPU usage alternate with of I/O wait

–a CPU-bound process

–an I/O bound process

CPU and I/O burst Cycle

We observe that processes require alternate use of processor and I/O in a repetitive manner
Each cycle consist of a CPU burst (typically of 5 ms) followed by a (usually longer) I/O burst
A process terminates on a CPU burst
CPU-bound processes have longer CPU bursts than I/O-bound processes

CPU/IO Bursts

Typically large number of short CPU bursts and a small number of long CPU bursts
An I/O-bound program typically has many short CPU bursts.
A CPU-bound program might have a few long CPU bursts.

Motivation

look the program, processing-component and IO-component indicated by upper-case and lower-case letters respectively.

A1 a1 A2 a2 A3

0 30 50 80 120 130 ===> JOB A

B1 b1 B2

0 20 40 60 ====> JOB B

C1 c1 C2 c2 C3 c3 C4 c4 C5

0 10 20 60 80 100 110 130 140 150 =>JOB C

The starting and ending time of each component are indicate the symbolic references (A1, b1 etc.)
Now lets consider three different ways for scheduling: no overlap, round-robin, simple overlap.
Compare utilization U =time CPU busy / total run time

Why scheduling is important

Scheduling is important aspect of multiprogramming . The resources being scheduled are processors and IO

- Max CPU utilization (keep the CPU as busy as possible)
- Max throughput (processes that complete their execution per unit time )
- Min turnaround time (amount of time to execute a particular process)
- Min waiting time (amount of time a process has been waiting in the readyqueue)
- Min response time (time elapse from the submission of a request to the beginning of the response (for time-sharing environment))

Classification of Scheduling Activity

CPU Scheduler

Short-term scheduler selects from among the processes in ready queue, and allocates the CPU to one of them
Queue may be ordered in various ways
CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
Consider access to shared data
Consider preemption while in kernel mode
Consider interrupts occurring during crucial OS activities

Dispatcher

Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
switching context
switching to user mode
jumping to the proper location in the user program to restart that program
Dispatch latency – time it takes for the dispatcher to stop one process and start
another running

Objectives

To introduce CPU scheduling, which is the basis for multiprogrammed operating systems
To describe various CPU-scheduling algorithms
To discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular system
To examine the scheduling algorithms of several operating system

Categories of Scheduling (Preemptive scheduling)

There are two categories of scheduling:

Non-preemptive: Here the resource can’t be taken from a process until the process completes execution. The switching of resources occurs when the running process terminates and moves to a waiting state.
Preemptive: Here the OS allocates the resources to a process for a fixed amount of time. During resource allocation, the process switches from running state to ready state or from waiting state to ready state. This switching occurs as the CPU may give priority to other processes and replace the process with higher priority with the running process.

Process Scheduling Queues

The OS maintains all Process Control Blocks (PCBs) in Process Scheduling Queues. The OS maintains a separate queue for each of the process states and PCBs of all processes in the same execution state are placed in the same queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new state queue.

The Operating System maintains the following important process scheduling queues −

Job queue − This queue keeps all the processes in the system.
Ready queue − This queue keeps a set of all processes residing in main memory, ready and waiting to execute. A new process is always put in this queue.
Device queues − The processes which are blocked due to unavailability of an I/O device constitute this queue.

The OS can use different policies to manage each queue (FIFO, Round Robin, Priority, etc.). The OS scheduler determines how to move processes between the ready and run queues which can only have one entry per processor core on the system; in the above diagram, it has been merged with the CPU.

Two-State Process Model

Two-state process model refers to running and non-running states which are described below −

S.N.	State & Description
1	Running When a new process is created, it enters into the system as in the running state.
2	Not Running Processes that are not running are kept in queue, waiting for their turn to execute. Each entry in the queue is a pointer to a particular process. Queue is implemented by using linked list. Use of dispatcher is as follows. When a process is interrupted, that process is transferred in the waiting queue. If the process has completed or aborted, the process is discarded. In either case, the dispatcher then selects a process from the queue to execute.

S.N.

State & Description

Running

When a new process is created, it enters into the system as in the running state.

Not Running

Processes that are not running are kept in queue, waiting for their turn to execute. Each entry in the queue is a pointer to a particular process. Queue is implemented by using linked list. Use of dispatcher is as follows. When a process is interrupted, that process is transferred in the waiting queue. If the process has completed or aborted, the process is discarded. In either case, the dispatcher then selects a process from the queue to execute.

Schedulers

Schedulers are special system software which handle process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run. Schedulers are of three types −

Long-Term Scheduler
Short-Term Scheduler
Medium-Term Scheduler

Long Term Scheduler

It is also called a job scheduler. A long-term scheduler determines which programs are admitted to the system for processing. It selects processes from the queue and loads them into memory for execution. Process loads into the memory for CPU scheduling.

The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and processor bound. It also controls the degree of multiprogramming. If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system.

On some systems, the long-term scheduler may not be available or minimal. Time-sharing operating systems have no long term scheduler. When a process changes the state from new to ready, then there is use of long-term scheduler.

Short Term Scheduler

It is also called as CPU scheduler. Its main objective is to increase system performance in accordance with the chosen set of criteria. It is the change of ready state to running state of the process. CPU scheduler selects a process among the processes that are ready to execute and allocates CPU to one of them.

Short-term schedulers, also known as dispatchers, make the decision of which process to execute next. Short-term schedulers are faster than long-term schedulers.

Medium Term Scheduler

Medium-term scheduling is a part of swapping. It removes the processes from the memory. It reduces the degree of multiprogramming. The medium-term scheduler is in-charge of handling the swapped out-processes.

A running process may become suspended if it makes an I/O request. A suspended processes cannot make any progress towards completion. In this condition, to remove the process from memory and make space for other processes, the suspended process is moved to the secondary storage. This process is called swapping, and the process is said to be swapped out or rolled out. Swapping may be necessary to improve the process mix.

Comparison among Scheduler

S.N.	Long-Term Scheduler	Short-Term Scheduler	Medium-Term Scheduler
1	It is a job scheduler	It is a CPU scheduler	It is a process swapping scheduler.
2	Speed is lesser than short term scheduler	Speed is fastest among other two	Speed is in between both short and long term scheduler.
3	It controls the degree of multiprogramming	It provides lesser control over degree of multiprogramming	It reduces the degree of multiprogramming.
4	It is almost absent or minimal in time sharing system	It is also minimal in time sharing system	It is a part of Time sharing systems.
5	It selects processes from pool and loads them into memory for execution	It selects those processes which are ready to execute	It can re-introduce the process into memory and execution can be continued.

Context Switching

A context switching is the mechanism to store and restore the state or context of a CPU in Process Control block so that a process execution can be resumed from the same point at a later time. Using this technique, a context switcher enables multiple processes to share a single CPU. Context switching is an essential part of a multitasking operating system features.

When the scheduler switches the CPU from executing one process to execute another, the state from the current running process is stored into the process control block. After this, the state for the process to run next is loaded from its own PCB and used to set the PC, registers, etc. At that point, the second process can start executing.

Context switches are computationally intensive since register and memory state must be saved and restored. To avoid the amount of context switching time, some hardware systems employ two or more sets of processor registers. When the process is switched, the following information is stored for later use.

Program Counter
Scheduling information
Base and limit register value
Currently used register
Changed State
I/O State information
Accounting information

Related Links to Operating System topics

Operating system Course content

Lab Practice Task

#Operating System complete course #Operating System past paper #Operating System-project #Computer Science all courses #operating system Problem with source code#University Past Paper #Programming language #Question paper #old paper #Operating System-Functions and History #Generations of Operating System #Functions of an Operating System #Components of Operating System #Types of Operating System #Services of Operating System #Properties of Operating System #Processes in Operating System #Process Scheduling in Operating System #Introduction to Linux Ubunto #Installation with virtual Box #Writing Linux Commands #Navigation in File System and Directory Management in Ubunto using CLI #File Handling and I/O Redirection In Ubunto #File Access Permission in Linux #Text Processing Tools and Basic System Configuration Tools in Linux #Package Management in Linux #How to manage processes in Linux #Compiling and Executing C++ programs in Linux #System Calls #Introduction To Shell Programming