CPU Scheduling

Kernel
Decides what to run
So far we have understood that multiple processes can exist on the system at the same time
But we have an important question
If we only have one CPU Core and 10p to Processes are ready to run
Which one should get the CPU
This is where CPU Scheduling comes into play

Scheduler
There is a part in the Kernel whose job is to decide which Process or Thread to choose to run

We call this part
Scheduler
Very simply

Ready Processes
│
├── Process A
├── Process B
├── Process C
└── Process D
│
▼
Scheduler
│
▼
CPU

Scheduler
Basically, it is finding the answer to this question
What should be run on the CPU now

Ready Queue
Processes that are ready to run but do not currently have the CPU are conceptually considered in something called the Ready Queue

For example:

Ready Queue

┌─
│
▼
Scheduler
│
▼
CPU

Of course, in a real operating system, the story is much more complicated than a simple queue

Scheduler
must consider different things and its internal structures also vary depending on the operating system and scheduling policy

Can a Process take the CPU forever
Suppose we have a program

while (1) {
// do something
}

This program will never finish

If the operating system had no control over the CPU, this Process could occupy the CPU for a very long time and other programs would not have a chance to run

That is why modern operating systems use Preemptive Scheduling

Preemption
means that the operating system can stop the current unit from executing and give the CPU to another unit Give

For example:

Process A
│
│ Running
▼
Scheduler decides
│
▼
Context Switch
│
▼
Process B
│
│ Running
▼

Here Process A is not necessarily finished
It just lost the CPU for now
It can continue its execution from where it stopped later

Timer Interrupt
comes in here
One of the things that helps the operating system regain control of the CPU is Timer
The operating system sets a hardware Timer
After a certain period of time, the Timer can create an Interrupt

Simply

CPU
│
│ Running Process A
│
▼
Timer
│
│ Time is up
▼
Interrupt
│
▼
Kernel
│
▼
Scheduler
│
▼
Process B

So a Process can't simply say
The CPU is mine and I'm not giving it back😁

The Kernel
can finally get involved

What is the role of Context Switch here Yes

Remember we said earlier that Context Switch means saving the state of the current unit and preparing the state of the next unit for execution

Now put these together

Timer Interrupt
↓
Kernel
↓
Scheduler
↓
Selecting a new unit
↓
Context Switch
↓
A new thread or process running

This chain is one of the important foundations for understanding Scheduling

On what basis does the Scheduler choose
Which unit to run can depend on various policies and algorithms

Let's look at some classic examples

FIFO or FCFS

Any process that enters earlier will run earlier

A → B → C → D

It's simple

But it doesn't always lead to the best performance

Shortest Job First
If we know the execution time of the tasks, we can execute the shorter task first

For example:

A = 10ms
B = 2ms
C = 7ms

B → C → A

It's interesting in theory

But the operating system usually doesn't know in advance exactly how much CPU each process or thread is going to consume Do

Round Robin
Here each thread gets CPU for a certain amount of time

For example

A → B → C → A → B → C

Assume each has 10ms of time

A 10ms
B 10ms
C 10ms
A 10ms
B 10ms

This model may be more suitable for interactive systems

Why is Scheduling important for Reverse Engineering?

When you are debugging a program, you may think that the execution of the program should be completely linear

For example

Instruction 1
Instruction 2
Instruction 3
Instruction 4

But the operating system can take the CPU from that thread in the middle of its execution and execute another thread

For example:

Thread A
│
├── Instruction 1
├── Instruction 2