Basic Terminology
Here are a few terms that we'll be using throughout the tutorial.
- [accordion]
- What is a Process
- While a program is getting executed by the CPU, it's referred to as a process. A program is a piece of code that instructs the CPU to perform a specific task. It contains instructions for the CPU that are followed one after the other.
- What is a Ready Queue
- A process isn't directly sent to the processor for running. First, it's loaded into the main memory. In main memory, they reside in the ready-queue that holds all processes that are ready to run, as its name suggests.
CPU Scheduling
Single-processor systems are able to execute only one process at a time. It arises a question that how multi-programming systems deal with multiple processes using one processor.
This is where the concept of CPU scheduling, AKA process scheduling, comes in.
Imagine a scenario in which a process, let's call it p1 — contains instructions to print a document — is waiting because the printer is busy. It has occupied the CPU but won't use it until the printer becomes available. Is it an efficient use of the CPU? Absolutely not!
It would be OK if it was the only process that needed CPU but in case of multi-programming, dozens of processes are held in the memory. All of them have to be executed one by one.
How about we save the state of p1, terminate it temporarily, take another process from the ready queue and give it control of CPU and let it execute. When the printer becomes free, give CPU back to the process p1 and start its execution from where it was stopped.
On the other hand, while the process is not waiting but running, this state is called CPU burst. So, it turns out that a process throughout its completion goes through CPU and I/O bursts.
Imagine a scenario in which a process, let's call it p1 — contains instructions to print a document — is waiting because the printer is busy. It has occupied the CPU but won't use it until the printer becomes available. Is it an efficient use of the CPU? Absolutely not!
It would be OK if it was the only process that needed CPU but in case of multi-programming, dozens of processes are held in the memory. All of them have to be executed one by one.
How about we save the state of p1, terminate it temporarily, take another process from the ready queue and give it control of CPU and let it execute. When the printer becomes free, give CPU back to the process p1 and start its execution from where it was stopped.
I/O and CPU Bursts
The purpose of the previous example was to introduce the concept of Input/Output (I/O) and CPU bursts. A process is not always executing. It may need to take breaks for completion of some input or output requests. In the given example, it was a request for the printer. These breaks are also called waiting-time or I/O bursts.On the other hand, while the process is not waiting but running, this state is called CPU burst. So, it turns out that a process throughout its completion goes through CPU and I/O bursts.
The goal is to not let the CPU sit idle. So, when the CPU is in waiting-state, i.e. waiting for some input/output, CPU scheduler selects a process from the memory and allocate the CPU to it. Making the CPU as productive as possible.
For this purpose, It may use one of the algorithms that we'll study throughout the tutorial.
For this purpose, It may use one of the algorithms that we'll study throughout the tutorial.
For instance, five processes — call them p1, p2, p3, p4, p5 — arrive in the queue. The job is to decide in what order should they be run to make the efficient use of the CPU.
Different algorithms will pick them up in different sequences.
Each algorithm may adopt one of the following two schemes of scheduling.
Different algorithms will pick them up in different sequences.
Each algorithm may adopt one of the following two schemes of scheduling.
Non-Preemptive Scheduling
If one process has started running, it will release the CPU only if it has completed OR switched to waiting-state. This scheme of scheduling is known as non-preemptive scheduling. This method was used in Windows versions prior to Windows 95.
Preemptive Scheduling
In preemptive scheduling, a process can be terminated even while it's running if a process with high priority needs the CPU. This method was used in versions that came after Windows 95.
Now there, you have some basic understanding of how CPU scheduling works, you are ready to move forward to some prominent scheduling algorithms.
Scheduling Criteria
All algorithms are not the same. An appropriate algorithm must be selected for a particular situation. There are some properties that help us differentiate one algorithm from the other.
CPU Utilization
As mentioned earlier, more the CPU remains busy, the better. CPU utilization, measured in percents, spans from 0 to 100. Less percentage shows CPU is getting wasted.Throughput
Throughput is the measure of work being done by the CPU. It indicates the number of processes that are getting completed in a given unit of time.
Waiting Time
A process may spend a lot of time waiting in the ready queue. An efficient algorithm tends to reduce waiting time. It's the total amount of time a process wasted being in the ready state.
Turnaround Time
From a process request to its completion, the total interval spent is referred to as Turnaround time. A process spends time in waiting-state, ready state, and running state. The sum of all those intervening periods outputs the Turnaround time.
Response Time
It's the interval between the process request and the first response.
Now there, you have some basic understanding of how CPU scheduling works, you are ready to move forward to some prominent scheduling algorithms.
