Operating System Tutorial

What is Operating System Evolution of Operating System Types of Operating System Functions of Operating System What is Kernel and Types of Kernel Operating System Properties Operating System Services Components of Operating System Needs of the Operating System Linux Operating System Unix Operating System Ubuntu Operating System What is DOS Operating System Difference Between Multi-programming and Multitasking What is Thread and Types of Thread Process Management Process State What is Process Scheduler and Process Queue What is Context Switching What is CPU Scheduling Scheduling Algorithm FCFS (First-come-First-Serve) Scheduling SJF (Shortest Job First) Scheduling Round-Robin CPU Scheduling Priority Based Scheduling HRRN (Highest Response Ratio Next) Scheduling Process Synchronization Lock Variable Mechanism TSL Mechanism Turn Variable Mechanism Interested Variable Mechanism What is Producer-Consumer Problem What is Semaphore in Operating System Monitors in Operating System What is Deadlock Deadlock Avoidance Strategies for Handling Deadlock Deadlock Prevention Deadlock Detection and Recovery Resource Allocation Graph Banker’s Algorithm in Operating System Fixed Partitioning and Dynamic Partitioning Partitioning Algorithms What is Paging and Segmentation What is Demand Paging What is Virtual Memory Disk Scheduling Algorithms FCFS and SSTF Disk Scheduling Algorithm SCAN and C-SCAN Disk Scheduling Algorithm Look and C-Look Disk Scheduling Algorithm File in Operating System File Access Methods in Operating System File Allocation Method Directory Structure in Operating System Difference between C-LOOK and C-SCAN Difference between Rotational Latency and Disk Assess Time Trap vs Interrupt How to implement Monitors using Semaphores N-Step-SCAN Disk Scheduling Why is it critical for the Scheduler to distinguish between I/O-bound and CPU-bound programs Difference between C-SCAN and SSTF Difference between SCAN and FCFS Difference between Seek Time and Disk Access Time Difference between SSTF and LOOK Feedback Queue in Operating System Contiguous Memory Allocation in Operating System MS-DOS Operating System Real-time Operating System Starvation in Operating System Thrashing in Operating System 5 Goals of Operating System Advantages of Operating System Advantages of UNIX Operating System Batch Operating System Bit Vector in Operating System Booting Process in Operating System Can a Computer Run Without the Operating System Commercial Mobile Operating Systems Difference between Process and Program in the Operating System Difference between Protection and Security in Operating System Dining Philosophers Problem in Operating System Free Space Management in Operating System Inter Process Communication in Operating System Swapping in Operating System Memory Management in Operating System Multiprogramming Operating System Multitasking Operating Systems Multi-user Operating Systems Non-Contiguous Memory Allocation in Operating System Page Table in Operating System Process Scheduling in Operating System Segmentation in Operating System Simple Structure in Operating System Single-User Operating System Two Phase Locking Protocol
CPU Scheduling in OS
2020-03-12 13:03:42

CPU Scheduling in OS

What is Scheduling?

Scheduling is the process that is used to share the computing resources such as memory, processor time, and bandwidth to the different processes, data flows, threads, and applications that need them. Scheduling is used to balance traffic on the system and for appropriate usage or distribution of resources and assign priorities according to the set of rules.

With the help of scheduling, a computer system can serve all requests and also provides some quality of services.

In a system, Scheduling is carried out with the help of an aptly scheduler, which primarily deals with three things:

1. Latency: - It is the turnaround time or, in other words, latency is the time to complete the job from the time of the request to the time of submission of the job, which also consists of waiting time.

2. Response Time: - Response Time is the time required to serve the process or request.

3. Throughput: - Throughput is the time to finish the task from starting to the end per unit of time.

What is CPU Scheduling?

CPU scheduling is defined as a method which permits the process to use the CPU conveniently and an efficient way when another process execution is on hold or in a waiting state because of a lack of resources such as I/O, etc. The purpose of CPU scheduling is used to improve the efficiency of the system and make the system fast and fair.

 The operating system (OS) chooses the process for execution in the ready queue, at the time when the CPU remains ideal. The process is chosen by the use of a short-term scheduler. The task of the scheduler is to choose the processes in the memory which are to be executed and then allocates the CPU to one of the processes.

The decision of CPU scheduling is taken place under the following cases.

  1. When the CPU switches a process from running to waiting state.

Example: - If a process requests for a resource and the resource is held by another process, then in this situation, the process enters into the running state to the waiting state.

  • If a process changes from running to the ready state Example: when an interrupt occurs between processes.
  • If a process changes from waiting to running state. Example: the completion of I/O.
  • If a process is over.

In 1and 4 cases, there is no option for scheduling. A new process should be chosen for execution. But there is an option in cases 2 and 3.

If scheduling is done under 1 and 4 cases, then scheduling scheme is known as Non-Preemptive scheduling. Otherwise, scheduling is called as Preemptive Scheduling.

Types of Scheduling

There are two types of Scheduling:

  1. Preemptive Scheduling.
  2. Non-Preemptive Scheduling

1. Preemptive Scheduling

Preemptive Scheduling is a type of scheduling in which the process changes from running state to the ready state and waiting state to the ready state.

 In Preemptive Scheduling, resources are allocated to the process for some time, and then it is taken back, and if that process still has CPU burst time remaining, then the process is again put back into the ready queue. The process present in the ready queue until the process gets the next turn of executing.

Preemptive scheduling is priority-based scheduling. The process having the highest priority is always processed and utilized the resources like CPU.

Algorithm used in preemptive scheduling are Priority scheduling, Shortest Remaining Time First (SRTF), Round Robin (RR), etc.

2. Non-Preemptive Scheduling

Non-Preemptive Scheduling is a Scheduling which is used if the process is over, or if the process changes from the running state to the waiting state. In Non-Preemptive Scheduling, if the resources are allocated to the process, then the process holds the CPU until the process is terminated or enters into a waiting state. In Non-Preemptive scheduling if the process is running, then no interrupt is allowed in between the execution of the process. Instead, it waits until its CPU burst time is complete, and it can then assign the CPU to another operation.

Non preemptive scheduling is th1e only scheduling which is used on some hardware platforms because it does not need any hardware for preemptive scheduling.  

Difference between Preemptive and Non-Preemptive Scheduling

    Preemptive Scheduling  Non-Preemptive Scheduling
In Preemptive Scheduling, the CPU is assigned for some time In Non-Preemptive Scheduling, CPU is assigned to the process until the process completes the execution.
Interrupt may occur between the execution of the process. Interrupt cannot occur until the process completes its execution.  
Preemptive Scheduling is flexible. Non-Preemptive Scheduling is rigid
In preemptive Scheduling there may be a chance of overhead the scheduling process In Non-Preemptive Scheduling there is no chance of overhead the scheduling the process.
Preemptive scheduling is cost- related. Non-Preemptive Scheduling does not cost-related.
In preemptive scheduling, when the high-priority process reaches into the ready queue, then due to of high-priority process the low-priority process can starve. In Non-Preemptive Scheduling, when in a CPU, the process which has more burst time is running, then due to this, the process which has less burst time can starve.

CPU Scheduling: Dispatcher

The Dispatcher is the element that contains the CPU scheduling function. Dispatcher module is used in CPU scheduling, which provides control to the CPU in the selection of processes using the short-term scheduler.

Dispatcher involves:

  • Context switching
  • Switching to user mode.
  • Skipping to the user program’s correct location to again start the program from where it was last left.

The dispatcher must be as quick as possible, as it is called at every process turn. The time utilized by the dispatcher to halt one process and resume another process is called as Dispatch Latency.

The following figure shows the Dispatch latency.  

CPU Scheduling

CPU Scheduling: Scheduling Criteria

There are various criteria for CPU Scheduling

  1. Throughput
  2. CPU Utilization
  3. Load Average
  4. Turnaround Time
  5. Waiting Time
  6. Response Time

Throughput: - Throughput is defined as the total number of processes that complete its execution per unit time. Depending on the specific processes, this can vary from 10/second to 1/hour.

CPU Utilization: - CPU utilization is an essential job in the operating system. For effective CPU utilization, the operating system must ensure that the CPU stays as active as possible most of the time. It can be between 0 to 100 percent, but in the Real-Time operating system, the range is 40 percent, for low-level, and for the high-level system, it can be 90 percent. for better CPU utilization, CPU must busy at all the time.

Load Average: - load average is the average number of processes which is existing in the ready queue and waiting for a CPU.

Turnaround Time: - Turnaround Time is defined as the total amount of time process consumed from its arrival to its completion. In other words, it is the total amount of time to execute a specific process.

Waiting Time: - Waiting time is the cumulative amount of time for which the process has waited for the allocation of the CPU.

Response Time: - Response Time is defined as the difference between the time of arrival and the time in which the process gets the CPU first.