CPU Scheduling

A computer runs many programs at once — the browser, the music player, the compiler, dozens of background services — yet it usually has only one (or a few) CPUs. Process scheduling is the activity of the operating system that decides which process owns the CPU at any given moment, and for how long. The part of the OS that makes this decision is called the scheduler, and the code that performs the actual switch is the dispatcher.

Good scheduling has three goals: keep the CPU busy (high utilisation), finish many jobs quickly (high throughput), and keep users happy by responding fast (low response time) and not making any single job wait too long (low turnaround time). These goals often conflict — favouring short jobs raises throughput but can starve a long job — so every scheduling algorithm is a different trade-off.

Operating systems mainly use three types of schedulers to manage process execution and memory efficiently. Each one moves a process from one queue to another:

1. Long Term Scheduler (Job Scheduler)

The long term scheduler is responsible for selecting processes from the job pool (stored on disk) and loading them into the main memory (RAM). Once loaded, these processes move into the ready state.

• Multiprogramming: Controls how many processes are present in memory at a time (degree of multiprogramming).
• Selection criteria: Selects processes based on factors like priority, resource needs, or execution time.
• Frequency: Invoked less frequently (every few seconds or minutes).
• Speed: Slowest scheduler because it involves heavy disk operations.

2. Short Term Scheduler (CPU Scheduler)

The short term scheduler chooses a process from the ready queue and assigns it to the CPU for execution.

• Algorithms: Works with scheduling algorithms like FCFS, SJF, and Round Robin.
• Frequency: Runs very frequently (every few milliseconds).
• Speed: Fastest scheduler because decisions must be made extremely quickly.
• Dispatcher: Uses a dispatcher to physically switch the CPU between processes (saving state, loading state, transferring control). The time taken for this switch is called dispatch latency.

3. Medium Term Scheduler (Swapper)

The medium term scheduler manages memory by temporarily removing processes from RAM and storing them on disk. This process is called swapping.

• Memory load: Reduces memory load by suspending some processes.
• Performance: Helps improve overall system performance during heavy load.
• Frequency: Invoked occasionally when memory is limited.
• Speed: Speed is between long term and short term schedulers.

Together, the long-term scheduler controls entry into the system, the short-term scheduler controls entry into the CPU, and the medium-term scheduler can pull a process out to disk (suspend) and re-introduce it later.

   [Pool of jobs]            [Ready queue]            [CPU]
   on disk                  in memory                (Running)
      │                        ▲                        │
      │  long-term             │  short-term             │  time slice
      └─────── admit ──────────┘  schedule ─────────────┘  expires / block
                                    │                        │
                                    │      medium-term        │
                                    │   suspend ◀────────────┤
                                    │   resume  ──────▶      │
                                 [Suspended / swapped out]   │
                                      (on disk)              ▼
                                          [Terminated]

Every process the OS knows about sits in one of several queues. The two queues you will keep meeting are the job queue (every process in the system) and the ready queue (processes in memory, waiting only for the CPU). Processes that are blocked on an I/O operation sit in the device queue for that device. The OS keeps a queue for each device, so I/O-bound and CPU-bound processes naturally separate.

When the short-term scheduler picks a new process, the dispatcher performs a context switch: it saves the running process's register values and program counter into its PCB, loads the next process's saved state from its PCB, and hands control to the next process. This switch is pure overhead — no useful work happens during it — so a good scheduler tries not to switch more often than necessary.