Process Scheduling in Operating System

Process scheduling is an important part of multiprogramming operating systems. It is the process of removing the running task from the processor and selecting another task for processing. It schedules a process into different states like ready, waiting, and running.

Categories of Scheduling in OS

There are two categories of scheduling:

1. Non-preemptive: In non-preemptive, 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.

2. Preemptive: In preemptive scheduling, 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

There are multiple states a process has to go through during execution. The OS maintains a separate queue for each state along with the process control blocks (PCB) of all processes. The PCB moves to a new state queue, after being unlinked from its current queue, when the state of a process changes.

These process scheduling queues are:

1. Job queue: Makes sure that processes stay in the system.

2. Ready queue: This stores a set of all processes in main memory, ready and waiting for execution. The ready queue stores any new process.

3. Device queue: This queue consists of the processes blocked due to the unavailability of an I/O device.

There are different policies that the OS uses to manage each queue and the OS scheduler decides how to move processes between the ready and run queue which allows only one entry per processor core on the system.

The stages a process goes through are:

• A new process first goes in the Ready queue, where it waits for execution or to be dispatched.
• The CPU gets allocated to one of the processes for execution.
• The process issues an I/O request, after which an OS places it in the I/O queue.
• The process then creates a new subprocess and waits for its termination.
• If removed forcefully, the process creates an interrupt. Thus, once this interrupt completes, the process goes back to the ready queue.

Objectives of Process Scheduling in OS

Following are the objectives of process scheduling:

1. It maximizes the number of interactive users within acceptable response times.
2. It achieves a balance between response and utilization.
3. It makes sure that there is no postponement for an unknown time and enforces priorities.
4. It gives reference to the processes holding the key resources.

Two-State Process Model

There are two states in the two-state process model, namely, running state and non-running state.

1. Running: A new process enters into the system in running state, after creation.

2. Not Running: The not running processes are stored in a queue until their turn to get executed arrives and each entry in the queue points to a particular process. The queue can be implemented using a linked list.

If a process has been completed or aborted, the OS discards it and if it is interrupted, then the OS transfers it to the waiting queue. Irrespective of either case, the dispatcher then selects a process from the queue to execute.

Schedulers in OS

A scheduler is a special type of system software that handles process scheduling in numerous ways. It mainly selects the jobs that are to be submitted into the system and decides whether the currently running process should keep running or not. If not then which process should be the next one to run. A scheduler makes a decision:

• When the state of the current process changes from running to waiting due to an I/O request or some unsatisfied OS.
• If the current process terminates.
• When the scheduler needs to move a process from running to ready state as it has already run for its allotted interval of time.
• When the requested I/O operation is completed, a process moves from the waiting state to the ready state. So, the scheduler can decide to replace the currently-running process with a newly-ready one.

Types of Schedulers in operating System

There are three types of schedulers:

1. Long Term Scheduler:

A long-term scheduler also known as a job scheduler determines which program should be admitted to the system for processing. It selects and loads the processes into the memory for execution with the help of CPU scheduling. It provides a balanced combo of jobs, such as I/O bound and processor bound and controls the degree of multiprogramming.

A stable degree of multiprogramming means that the average rate of process creation and the average departure rate of processes leaving the system is equal. Many systems like time-sharing OS, do not have a long term scheduler as it is only required when a process changes its state from new to ready.

2. Short Term Scheduler:

A short-term scheduler also known as a CPU scheduler increases system performance as per the chosen set of criteria. This is the change of ready state to running state of the process.

It selects a process from the multiple processes that are in ready state in order to execute it and also allocates the CPU to one of them. It is faster than long-term schedulers and is also called a dispatcher as it makes the decision on which process will be executed next.

3. Medium Term Scheduler:

Medium-term scheduling removes processes from the memory and is a part of swapping. It reduces the degree of multiprogramming and is in-charge of handling the swapped out processes. Swapping is necessary to improve the process mix.

When a running process makes an I/O request it becomes suspended i.e., it cannot be completed. Thus, in order to remove the process from the memory and make space for others, the suspended process is sent to the secondary storage. This is known as swapping, and the process that goes through swapping is said to be swapped out or rolled out.

Comparison of OS Schedulers

Context Switch in OS

A context switch is an important feature of multitasking OS that can be used to store and restore the state or context of a CPU in a PCB, so that the execution of a process can be resumed from that very point at a later time. A context switch allows multiple processes to share a single CPU. Some hardware systems even employ two or more sets of processor registers, in order to avoid context switching time.

When the scheduler switches the CPU from one process to another, the state of the current running process is stored into the PCB and the state for the next process is loaded from its own PCB. This is then used to set the PC, registers, etc. Since the register and memory state is saved and restored in context switches, they are computationally intensive. Following information is stored during switching:

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

Context switch occurs when:

• A process with a higher priority than the running process enters the ready state.
• An Interrupt happens
• The user mode and kernel-mode switch. Though context switching doesn’t usually happen in this situation.
• We use preemptive CPU scheduling.

Mode Switch in OS

Mode switching happens usually when a system call is made or a fault occurs i.e., it happens when the processor privilege level is changed. A mode switch is necessary if a user process needs to access things exclusively accessible to the kernel. The executing process does not change during a mode switch. We can say that a mode switch occurs so that a process context switch can take place as only the kernel can cause a context switch.

Summary

Process scheduling schedules a process into ready, waiting, and running states. There are two categories of process scheduling: preemptive and non-preemptive scheduling. Job queue, ready queue, and device queue are the three queues of process scheduling.

There are two states in the two-state model, namely, running and not running. A scheduler handles the task of process scheduling and has three types, short-term, long-term, and middle-term. A context switch is used to store and restore the context in a PCB.