Process Scheduling Fundamentals

TL;DR

Process scheduling ensures your computer's CPU is always busy by carefully managing "processes," which are programs in execution. The operating system uses various queues and schedulers to move processes through different states, like waiting or running, to efficiently share the CPU. Understanding these fundamentals helps you grasp how multiple applications can run seemingly simultaneously.

1. The Mental Model

Think of your computer's CPU as a single chef in a busy kitchen. Many orders (processes) come in, but only one can be cooked (executed) at a time. Process scheduling is the system that helps the chef decide which order to work on next, ensuring no time is wasted and all orders eventually get prepared.

2. The Core Material

A process is essentially a program in execution. When you launch an application, it becomes a process. Each process needs to progress in a sequential fashion. To identify and manage each process, the operating system uses a Process Control Block (PCB), which holds all the critical information about that process.

Components of a Process Control Block (PCB)

The PCB is like a passport for a process, containing vital details:
* Process state: Shows whether the process is new, running, waiting, ready, or terminated.
* Program counter: Points to the exact memory address of the next instruction to be executed by that process.
* CPU registers: Stores the contents of the CPU's internal registers specific to the process.
* CPU scheduling information: Includes details like the process's priority and pointers to scheduling queues.
* Memory-management information: Tracks the memory allocated to the process.
* Accounting information: Records how much CPU time the process has used, how long it's been running, and any time limits.
* I/O status information: Lists any I/O devices assigned to the process and its open files.

Process States

As a process executes, it moves through different states:
* new: The process is being created.
* running: The process's instructions are currently being executed by the CPU.
* waiting: The process is paused, waiting for some event (like an I/O operation to complete).
* ready: The process is in main memory and waiting for the CPU to become available so it can run.
* terminated: The process has finished its execution.

graph TD
    subgraph Process States
        New --> Ready;
        Ready --> Running;
        Running --> Waiting;
        Running --> Terminated;
        Waiting --> Ready;
    end

Process Scheduling Goals

The main goal of process scheduling is to maximize CPU use, ensuring there's always a running process if one is available. To do this, the operating system maintains different types of queues:

• Job queue: This queue holds all processes currently in the system.
• Ready queue: This contains all processes that are residing in main memory, ready, and waiting for the CPU.
• Device queues: These are queues of processes waiting for a specific I/O device. Processes can move (or "migrate") between these queues.

Schedulers

Schedulers are special OS components that decide which processes run when.

• Short-term scheduler (or CPU scheduler): This scheduler is very fast and frequently invoked (in milliseconds). It selects a process from the ready queue and allocates the CPU to it.
• Long-term scheduler (or job scheduler): This scheduler is invoked less frequently (seconds, minutes). It selects processes from mass storage and brings them into the ready queue. This scheduler also controls the degree of multiprogramming (how many processes are trying to use the CPU at once).

CPU Switch and Context Switch

When the CPU needs to stop executing one process and start another, it performs a context switch. This involves:
1. Saving the complete state of the currently running process (all its PCB information).
2. Loading the saved state of the new process it's about to run.

This process allows the CPU to efficiently switch between multiple processes, making it seem like they are all running simultaneously.

Processes can be categorized by how they use the CPU:
* I/O-bound process: Spends more time doing input/output operations than computations, characterized by many short CPU bursts.
* CPU-bound process: Spends more time doing computations, often having a few very long CPU bursts.

3. Worked Example

Imagine you have two programs running:
1. A word processor (Process A)
2. A video rendering application (Process B)

Initially, Process A is running on the CPU. It's an I/O-bound process, so it frequently performs disk saves.

1. Process A uses the CPU for a short burst to process some text.
2. Then, Process A needs to save your document to disk. It changes its state from running to waiting (for the disk I/O to complete) and is moved to a device queue specifically for the disk.
3. The short-term scheduler immediately sees that the CPU is now free. It looks at the ready queue. Let's say Process B (the video renderer) was ready and waiting there.
4. A context switch occurs:
   • The OS saves all information from Process A's PCB.
   • The OS loads all information from Process B's PCB.
5. Process B now moves from ready to running on the CPU, using a long CPU burst to render video frames.
6. Later, Process A's disk save completes. Process A moves from waiting back to the ready queue.
7. If Process B is still running and hasn't finished its CPU burst or needs to wait for something, Process A will just wait in the ready queue until the CPU becomes available again through another context switch.

This constant saving and loading allows your computer to smoothly handle multiple tasks.

4. Key Takeaways

• A process is a program in execution, managed by its own information in a Process Control Block (PCB).
• Processes move through distinct states: new, ready, running, waiting, and terminated.
• Schedulers (short-term and long-term) manage the movement of processes through various queues to optimize CPU usage.
• The short-term scheduler quickly picks the next process for the CPU from the ready queue.
• A context switch efficiently saves one process's state and loads another's, enabling multiple programs to share the CPU.
• Processes can be I/O-bound (many short CPU bursts) or CPU-bound (few long CPU bursts).

Common mistakes to avoid:
- Confusing a program (an inactive file) with a process (an active instance of that program).
- Thinking that multiple programs truly run simultaneously on a single-core CPU; they appear to through rapid switching.
- Underestimating the importance of ready queue in CPU scheduling – it's the primary source for the short-term scheduler.
- Mixing up the roles of short-term (CPU allocation) and long-term (multi-programming degree) schedulers.

5. Now Try It

List the current processes running on your computer using a system utility (like Task Manager on Windows or Activity Monitor on macOS, or ps -aux on Linux). For any three processes, imagine what "state" they might be in (running, waiting, ready, etc.) and provide a plausible reason why (e.g., "Web browser is waiting because it's loading an image from the internet").