Processes, threads and CPU scheduling notes — Unit 2

A program is a passive entity (a file on a disk). A Process is an active entity: a program currently in execution.

A process is more than just the program code. It includes the current activity, represented by:

• Text Section: The compiled program code.
• Program Counter (PC): Indicates the next instruction to execute.
• CPU Registers: Contents of all registers.
• Stack: Temporary data like function parameters, return addresses, and local variables.
• Data Section: Global and static variables.
• Heap: Memory dynamically allocated during runtime.

As a process executes, it changes state. A process can only be in one state at a time.

⇒2.1 The 5-State Model

• New: The process is being created.
• Ready: The process is loaded into main memory and is waiting for the CPU to be assigned to it.
• Running: Instructions are currently being executed on the CPU. (On a single-core machine, only ONE process can be running at a time).
• Waiting (Blocked): The process cannot continue until an event occurs (like waiting for the user to type something, or waiting for the hard drive to return a file).
• Terminated: The process has finished execution.

When a process is in the Running state, if it requests I/O, it moves to Waiting. If the OS timer expires (time slice finished), it is forcibly moved back to Ready.

To manage all these processes, the OS creates a data structure for every single process called the PCB (or Task Control Block). It serves as the repository for any information that varies from process to process.

⇒3.1 Contents of a PCB

• Process State: (Ready, Running, Waiting).
• Program Counter: Address of the next instruction.
• CPU Registers: So the OS can pause a process, save its registers here, and resume it later exactly as it was.
• CPU Scheduling Information: Priority pointers.
• Memory Management Info: Page tables and limits.
• Accounting Info: Amount of CPU time used, time limits.
• I/O Status Info: List of files opened by the process.

When the OS switches the CPU from Process A to Process B, it performs a Context Switch. It saves the state of A into A's PCB, and loads the state of B from B's PCB. Context switching is pure overhead; no useful work is done while switching.

In Unix/Linux, a process can create a new process using the `fork()` system call.

The creating process is the Parent, and the new process is the Child.

⇒4.1 How `fork()` works

When `fork()` is called, the OS creates an exact, identical clone of the parent process. The child gets a copy of the parent's address space, code, and variables.

Both processes continue executing from the exact line of code immediately following the `fork()` call.

How do they know who is who? By checking the return value of `fork()`:

• In the Child, `fork()` returns `0`.
• In the Parent, `fork()` returns the Process ID (PID) of the new child.
• If it returns a negative number, the creation failed.

Usually, the child immediately calls `exec()` to replace its cloned memory space with a brand new program to run.

A Process is heavyweight. Creating a process requires allocating a new memory space and a new PCB. Context switching between processes is slow.

A Thread is a lightweight process. It is a basic unit of CPU utilization.

⇒5.1 What Threads Share

Multiple threads belonging to the same process share:

• The Code section.
• The Data section (global variables).
• OS resources (like open files).

⇒5.2 What Threads Keep Private

Each thread must have its own:

• Thread ID.
• Program Counter (they might be executing different parts of the code).
• Register set.
• Stack (they have their own local variables).

Benefit: Switching between threads of the same process is blazing fast because memory doesn't need to be swapped.

Threads exist in two realms: User threads (managed by a library without the OS knowing) and Kernel threads (managed directly by the OS). How they map to each other defines the multithreading model.

⇒6.1 Many-to-One Model

Many user threads are mapped to a single kernel thread.
Flaw: If one user thread makes a blocking system call (like reading a file), the OS blocks the entire kernel thread, causing all other user threads to freeze, even if they could have done useful work.

⇒6.2 One-to-One Model

Every user thread gets its own dedicated kernel thread.
Pros: Allows true parallel execution on multi-core CPUs. If one blocks, others continue.
Flaw: Creating a kernel thread is expensive. Too many threads will crash the system. (Used by Windows and Linux).

⇒6.3 Many-to-Many Model

Multiplexes many user threads to a smaller or equal number of kernel threads. Highly flexible, but complex to implement.

In a multiprogrammed system, multiple processes are in the Ready queue. Which one gets the CPU next? The Short-Term Scheduler (CPU Scheduler) makes this decision.

⇒7.1 Preemptive vs. Non-Preemptive

• Non-Preemptive: Once the CPU is given to a process, it keeps the CPU until it voluntarily releases it (by terminating or requesting I/O). The OS cannot force it off.
• Preemptive: The OS can forcefully pause a running process at any time (e.g., when a higher priority process arrives, or a timer expires) and give the CPU to someone else. Essential for modern interactive systems.

⇒7.2 Scheduling Criteria

How do we judge if an algorithm is "good"?

• Turnaround Time: Total time from submission to completion.
• Waiting Time: Total time a process spent waiting in the Ready queue.
• Response Time: Time from submission until the first response is produced (crucial for UI).
• Throughput: Number of processes completed per unit time.

The simplest scheduling algorithm. The process that requests the CPU first is allocated the CPU first. It is managed with a FIFO queue.

• Type: Non-Preemptive.
• Pros: Extremely simple to write and understand.
• Cons: Very poor performance in terms of average waiting time.

⇒8.1 The Convoy Effect

The major flaw of FCFS. If a massive, CPU-heavy process arrives first, all other short processes must wait behind it in the queue for a long time. It's like one person with a cart full of groceries blocking 10 people holding a single item at the checkout line.

This algorithm associates with each process the length of its next CPU burst. The CPU is assigned to the process that has the smallest next CPU burst.

• Pros: It is mathematically provable that SJF provides the minimum average waiting time for a given set of processes.
• Cons: It's impossible to implement perfectly in reality. The OS cannot accurately predict how long a process's next CPU burst will be. It must use exponential averaging of past bursts to guess the future.

⇒9.1 Preemptive SJF (SRTF)

Shortest Remaining Time First. If a new process arrives with a CPU burst shorter than what is left of the currently executing process, the OS preempts the current process and gives the CPU to the new one.

Designed specifically for time-sharing systems. It is essentially FCFS with preemption added.

⇒10.1 The Time Quantum

The OS defines a small unit of time called a Time Quantum or Time Slice (usually 10 to 100 milliseconds).

The scheduler goes down the Ready queue, allocating the CPU to each process for exactly 1 time quantum.
If the process finishes within the quantum, it releases the CPU.
If it doesn't, the OS timer interrupts it, forces it to the back of the Ready queue, and gives the CPU to the next process.

⇒10.2 Performance Dependency

RR performance depends entirely on the size of the time quantum.

• If quantum is infinitely large, RR becomes FCFS.
• If quantum is too small (e.g., 1 microsecond), the OS spends more time performing Context Switches than actually running user code. (Thrashing).

A priority number (integer) is associated with each process. The CPU is allocated to the process with the highest priority.

(Note: In OS contexts, a smaller integer often means higher priority. e.g., Priority 1 is higher than Priority 10).

Can be Preemptive (preempts current if a higher priority arrives) or Non-Preemptive.

⇒11.1 The Starvation Problem

A major problem with Priority Scheduling is Starvation (Indefinite Blocking). If a low-priority process is in the queue, and high-priority processes keep arriving continuously, the low-priority process will wait forever and never execute.

⇒11.2 The Solution: Aging

To prevent starvation, the OS uses Aging. The system gradually increases the priority of processes that have been waiting in the system for a long time. Eventually, even the lowest priority process will age enough to get the CPU.

Not all processes are equal. System processes are critical, interactive user processes need fast response times, and background batch processes (like antivirus scans) don't need immediate attention.

⇒12.1 The Architecture

The Ready queue is partitioned into several separate queues (e.g., Foreground Queue and Background Queue).

• Each process is permanently assigned to one queue based on its type.
• Each queue has its own scheduling algorithm. (Foreground might use Round Robin for responsiveness, Background might use FCFS).
• There must be scheduling between the queues. Usually, this is fixed-priority preemptive scheduling. (No process in the Background queue can run unless the Foreground queue is completely empty).

This architecture is rigid. A process cannot move between queues.

The most complex and general CPU scheduling algorithm. Used in modern desktop operating systems.

It solves the rigidity of Multilevel Queues by allowing processes to move between queues based on their behavior.

⇒13.1 How it Works

Imagine 3 queues: Q0 (Highest priority, RR quantum 8ms), Q1 (RR quantum 16ms), and Q2 (Lowest priority, FCFS).

• A new process enters Q0. It gets 8ms. If it finishes, great.
• If it uses its entire 8ms without finishing, it is deemed a "CPU-bound" process. The OS demotes it to Q1.
• If it uses its entire 16ms in Q1, it is demoted to Q2 (the batch background queue).
• Conversely, if a process in Q2 suddenly becomes interactive and starts waiting for user input, the OS promotes it back to Q0.

This algorithm perfectly balances quick response times for UI tasks while preventing heavy background tasks from locking up the system.

Unit 2 is heavily focused on numericals. You must be able to draw Gantt charts.

⇒14.1 University Exam Checklist

• Draw and explain the 5-State Process Transition Diagram.
• What is a PCB? List its components.
• Explain the output of a C program that calls `fork()` multiple times.
• Contrast a Thread with a Process. Explain the benefits of Multithreading.
• Solve a numerical problem calculating Average Waiting Time and Turnaround Time using FCFS, SJF (Preemptive and Non-Preemptive), and Round Robin.
• Explain the Convoy Effect in FCFS.
• Explain Starvation in Priority Scheduling and how Aging solves it.
• Explain the working principle of the Multilevel Feedback Queue.