CPU scheduling is the basis of multi-programmed operating systems. By switching the CPU among processes, the operating system can make the computer more productive. CPU Scheduling is a process of determining which process will own CPU for execution while another process is on hold. The main task of CPU scheduling is to make sure that whenever the CPU remains idle, the OS at least selects one of the processes available in the ready queue for execution. The selection process will be carried out by the CPU scheduler. It selects one of the processes in memory that are ready for execution.
Types of CPU Scheduling
Here are two kinds of Scheduling methods:
1. Preemptive Scheduling
In Preemptive Scheduling, the tasks are mostly assigned with their priorities. Sometimes it is important to run a task with a higher priority before another lower-priority task, even if the lower-priority task is still running. The lower priority task holds for some time and resumes when the higher priority task finishes its execution.
2. Non-Preemptive Scheduling
In this type of scheduling method, the CPU has been allocated to a specific process. The process that keeps the CPU busy will release the CPU either by switching context or terminating. It is the only method that can be used for various hardware platforms. That’s because it doesn’t need special hardware (for example, a timer) like preemptive scheduling.
All other scheduling is preemptive.
Important CPU scheduling Terminologies
- Burst Time/Execution Time: It is the time required by the process to complete execution. It is also called running time.
- Arrival Time: when a process enters a ready state
- Finish Time: when the process is complete and exits from a system
- Multiprogramming: A number of programs that can be present in memory at the same time.
- Jobs: It is a type of program without any kind of user interaction.
- User: It is a kind of program having user interaction.
- Process: It is the reference that is used for both the job and the user.
- CPU/IO burst cycle Characterizes process execution, which alternates between CPU and I/O activity. CPU times are usually shorter than the time of I/O.
CPU Scheduling Criteria
- CPU utilization: We want to keep the CPU as busy as possible. 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 loaded system).
- Throughput: If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput. For long processes, this rate may be one process per hour; for short transactions, it may be ten processes per second.
- Turnaround time: From the point of view of a particular process, the important criterion is how long it takes to execute that process. The interval from the time of submission of a process to the time of completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
- Waiting time: The CPU-scheduling algorithm does not affect the amount of time during which a process executes or does I/O. It affects only the amount of time that a process spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.
- Response time: In an interactive system, turnaround time may not be the best criterion. Often, a process can produce some output fairly early and can continue computing new results while previous results are 266. CPU Scheduling output to the user. Thus, another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response.
What is Dispatcher?
It is a module that provides control of the CPU to the process. The Dispatcher should be fast so that it can run on every context switch. Dispatch latency is the amount of time needed by the CPU scheduler to stop one process and start another.
Functions performed by Dispatcher:
- Context Switching
- Switching to user mode
- Moving to the correct location in the newly loaded program.
Types of CPU scheduling Algorithm
There are mainly six types of process scheduling algorithms
- First Come First served (FCFS)
- Shortest-Job-First (SJF) Scheduling
- Priority Scheduling
- Round Robin Scheduling
- Shortest Remaining Time
- Multilevel Queue Scheduling
1. First Come First Serve
First Come First Serve is the full form of FCFS. It is the easiest and most simple CPU scheduling algorithm. In this type of algorithm, the process which requests the CPU gets the CPU allocation first. This scheduling method can be managed with a FIFO queue.
As the process enters the ready queue, its PCB (Process Control Block) is linked with the tail of the queue. So, when the CPU becomes free, it should be assigned to the process at the beginning of the queue.
2. Shortest Remaining Time
The full form of SRT is Shortest remaining time. It is also known as SJF preemptive scheduling. In this method, the process will be allocated to the task, which is closest to its completion. This method prevents a newer ready-state process from holding the completion of an older process.
3. Priority Based Scheduling
Priority scheduling is a method of scheduling processes based on priority. In this method, the scheduler selects the tasks to work as per priority.
Priority scheduling also helps OS to involve priority assignments. The processes with higher priority should be carried out first, whereas jobs with equal priorities are carried out on a round-robin or FCFS basis. Priority can be decided based on memory requirements, time requirements, etc.
4. Round-Robin Scheduling
Round robin is the oldest, simplest scheduling algorithm. The name of this algorithm comes from the round-robin principle, where each person gets an equal share of something in turn. It is mostly used for scheduling algorithms in multitasking. This algorithm method helps for starvation-free execution of processes.
5. Shortest Job First
SJF is a full form of (Shortest job first) is a scheduling algorithm in which the process with the shortest execution time should be selected for execution next. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average waiting time for other processes awaiting execution.
6. Multiple-Level Queues Scheduling
This algorithm separates the ready queue into various separate queues. In this method, processes are assigned to a queue based on a specific property of the process, like the process priority, size of the memory, etc.
However, this is not an independent scheduling OS algorithm as it needs to use other types of algorithms in order to schedule the jobs.
The Purpose of a Scheduling algorithm
Here are the reasons for using a scheduling algorithm:
- The CPU uses scheduling to improve its efficiency.
- It helps you to allocate resources among competing processes.
- The maximum utilization of the CPU can be obtained with multi-programming.
- The processes which are to be executed are in the ready queue.