Unit 1: Introduction to Operating System and Process Management

1. Operating System Fundamentals & Evolution

An Operating System (OS) is system software that acts as an intermediary between computer hardware and the application programs/users. It fulfills two overarching philosophical goals:

Extended Machine (Top-Down View / Abstract Machine): Presents programmers and users with a clean, unified, high-level abstraction of hardware resources, hiding the grueling complexity of manipulating hardware registers, interrupt controllers, and disk sectors.
Resource Manager (Bottom-Up View): Orderly and fairly allocates physical processors, memory blocks, storage devices, and I/O channels among multiple competing programs and users, maximizing hardware utilization while enforcing isolation and security.

CODE
+-----------------------------------------------------------------------------+
|                           THE COMPUTER SYSTEM STACK                         |
+-----------------------------------------------------------------------------+
|                                  Users                                      |
+-----------------------------------------------------------------------------+
|                  Application Programs (Compilers, DBs, Browsers)            |
+-----------------------------------------------------------------------------+
|               Operating System (Kernel, Device Drivers, System Calls)        |
+-----------------------------------------------------------------------------+
|          Computer Hardware (CPU, Memory, Storage Controllers, I/O Devices)  |
+-----------------------------------------------------------------------------+

1.1 Historical Evolution of Operating Systems

The architectural evolution of operating systems has been driven by the need to eliminate idle processor time and improve human-computer interaction:

First Generation: Serial Processing (1940s – mid-1950s):
- Programmers interacted directly with the bare machine using mechanical switches, plugboards, and paper punch tape.
- No operating system existed.
- Inefficient: Substantial machine time was wasted on manual setup time (loading compiler punch cards, mounting tape reels, clearing memory registers).
Second Generation: Simple Batch Systems (mid-1950s – mid-1960s):
- Operators collected jobs with similar needs into batches.
- Introduced the Resident Monitor: A primitive software program permanently residing in memory that automatically loaded and transferred execution from one job to the next using a Job Control Language (JCL).
- Primary Drawback: The CPU was severely underutilized during I/O operations because mechanical card readers and line printers were thousands of times slower than electronic CPU arithmetic units.
Third Generation: Multiprogrammed Batch Systems (mid-1960s – 1970s):
- Multiple jobs are held in main memory simultaneously.
- When the currently executing job requires I/O, the operating system switches the CPU to another job waiting in memory.
- Relies on SPOOLING (Simultaneous Peripheral Operations On-Line), using fast magnetic disks as high-capacity intermediate buffers between slow card readers/printers and main memory.
- Controls the Degree of Multiprogramming (the number of active processes kept concurrently in main memory).
Fourth Generation: Time-Sharing Systems / Multitasking (1970s – Present):
- Extends multiprogramming by employing high-frequency CPU scheduling and time slicing (quantums).
- Switches the processor so rapidly (typically every 10 to 100 milliseconds) that multiple users interacting via terminals experience immediate, concurrent execution (response time < 1 second).
Multiprocessor Systems (Tightly Coupled Systems):
- Multiple CPUs share a common physical memory bus, system clock, and peripheral devices.
- Symmetric Multiprocessing (SMP): All processors run identical copies of the operating system; any processor can execute user code or kernel routines concurrently without a master bottleneck.
- Asymmetric Multiprocessing (ASMP): A master processor allocates tasks and schedules code for dedicated slave processors.
- Memory Architecture: UMA (Uniform Memory Access) where memory access latency is identical across all CPUs vs NUMA (Non-Uniform Memory Access) where access to local node memory is significantly faster than remote node memory.
Real-Time Operating Systems (RTOS):
- Designed for environments where correctness depends not only on logical results but also on the strict temporal deadlines within which results are produced.
- Hard Real-Time Systems: Missing a deadline constitutes catastrophic system failure (e.g., flight control systems, pacemaker telemetry, automotive ABS braking, nuclear reactor control). Virtual memory swapping is strictly prohibited; processes are locked into RAM.
- Soft Real-Time Systems: Missing a deadline degrades Quality of Service (QoS) but does not cause system collapse (e.g., video streaming, audio playback, online gaming).

2. Hardware Support & Dual-Mode Operation

To prevent malfunctioning user programs or malicious adversaries from crashing the entire system, seizing exclusive control of hardware, or snooping on private memory spaces, modern microprocessors enforce Hardware-Enforced Protection.

CODE
+-----------------------------------------------------------------------------+
|                           DUAL-MODE OPERATION                               |
+-----------------------------------------------------------------------------+
|  User Mode (Mode Bit = 1)               Kernel / Supervisor Mode (Mode Bit = 0)
|  - Executes user application code       - Executes core operating system kernel
|  - Restricted instruction set           - Full access to all machine instructions
|  - Cannot execute privileged instructions- Direct manipulation of hardware registers
|  - Isolated virtual memory address space- Access to entire physical memory space
+-----------------------------------------+-----------------------------------+
       |                                                 ^
       | --- 1. Trap / System Call / Hardware Interrupt -|  (Mode Bit -> 0)
       |                                                 |
       |<--- 2. Return from Interrupt / Syscall (IRET) --|  (Mode Bit -> 1)

2.1 Privileged vs Non-Privileged Instructions

Privileged Instructions: Machine instructions that can alter machine state, modify memory translation tables, or communicate directly with external peripherals. They can execute only in Kernel Mode. If executed in User Mode, the CPU hardware generates a Trap/Exception, halting the offending program.
- Examples: HLT (halt CPU), IN/OUT or memory-mapped I/O operations, loading the Page Table Base Register (CR3 in x86), clearing the interrupt flag (CLI), programming the system interval timer.
Non-Privileged Instructions: Safe computational operations permitted in User Mode.
- Examples: Arithmetic operations (ADD, SUB, MUL), reading system clock, branching (JMP, CALL), reading user registers.

2.2 Mechanism of Mode Switching

Transition from User Mode to Kernel Mode occurs via three hardware-controlled mechanisms:

System Call: A software-initiated request by an application to execute an OS service.
Trap / Exception: A synchronous condition generated internally by the CPU when an instruction faults (e.g., division by zero, page fault, illegal memory access).
Hardware Interrupt: An asynchronous electrical signal sent by an external hardware controller (e.g., timer chip expiring, disk controller signaling I/O completion, keystroke on keyboard).

2.3 Hardware Protection Systems

Dual-Mode Operation: Controlled by a physical Mode Bit inside the Program Status Word (PSW) register (0 = Kernel Mode, 1 = User Mode).
I/O Protection: All I/O instructions are strictly privileged. User programs must invoke system calls; the kernel checks parameters and performs I/O on the application's behalf.
Memory Protection: Hardware registers—specifically the Base Register (holds smallest legal physical memory address) and Limit Register (specifies the size of the range)—are compared against every memory reference generated by a user process. If $\text{Address} < \text{Base}$ or $\text{Address} \ge \text{Base} + \text{Limit}$ , a hardware trap occurs.
Timer Protection: A programmable hardware interval timer is decremented by every physical clock tick. When the counter reaches zero, a hardware interrupt is generated, returning control to the kernel scheduler. This prevents any user program from monopolizing the CPU in an infinite loop.

3. Operating System Architecture & System Calls

3.1 The System Call Interface

A System Call provides the programmatic interface between an application running in User Mode and the privileged services supplied by the Operating System Kernel.

CODE
USER SPACE                                    KERNEL SPACE
+---------------------------+                 +-------------------------------+
| User Application          |                 | System Call Dispatch Table    |
|   printf("Hello");        |                 |   [1] -> sys_exit()           |
|         |                 |                 |   [2] -> sys_fork()           |
|         v                 |                 |   [3] -> sys_read()           |
| C Standard Library (glibc)|                 |   [4] -> sys_write() -------->|
|   write(1, "Hello", 5)    |                 +---------------+---------------+
|         |                 |                                 |
|         v                 |                                 v
| Assembly Stub:            |                 | Execute sys_write() Handler:  |
|   MOV RAX, 1 (syscall #)  |                 | - Validate memory buffers     |
|   MOV RDI, 1 (stdout fd)  |                 | - Copy data to kernel buffer  |
|   MOV RSI, ptr            |                 | - Invoke TTY device driver    |
|   MOV RDX, 5              |                 +---------------+---------------+
|   SYSCALL / INT 0x80      |                                 |
+---------+-----------------+                                 |
          |                                                   |
          +============== Hardware Mode Switch ==============>+
                          (Mode Bit 1 -> 0)

Parameter Passing Mechanisms

When an application invokes a system call, parameters must be transferred from user space into kernel space:

Processor Registers: Fast and direct; parameters are loaded into specific registers (e.g., RDI, RSI, RDX, R10, R8, R9 in Linux x86_64). Limited by the number of general-purpose registers.
Memory Block / Table: Parameters are stored in an allocated memory block or structure in user space; the starting physical/virtual memory address of the block is passed in a single register.
System Stack: Parameters are pushed onto the program stack by the caller and popped off by the operating system kernel upon mode switch.

Common Categories of System Calls

Process Control: fork(), execve(), wait(), exit(), abort(), getpid().
File Manipulation: open(), read(), write(), close(), lseek(), unlink().
Device Manipulation: ioctl(), read(), write().
Information Maintenance: time(), alarm(), getrusage().
Communication & IPC: pipe(), shmget(), mmap(), socket(), send(), recv().

3.2 Operating System Structural Models

CODE
+-----------------------------------------------------------------------------+
|                      MONOLITHIC KERNEL vs MICROKERNEL                       |
+-----------------------------------------------------------------------------+
| Monolithic (e.g., Linux, Traditional Unix) | Microkernel (e.g., Mach, QNX)  |
| - All OS components (scheduler, VFS, IPC,  | - Only indispensable functions |
|   network stack, device drivers) reside in |   reside in kernel space (IPC, |
|   a single huge binary in KERNEL SPACE.    |   virtual memory, scheduler).  |
| - Extremely high execution speed (direct   | - Drivers, filesystems, and net|
|   function calls without IPC overhead).    |   stacks run in USER SPACE.    |
| - Low fault tolerance: A bug in a single   | - High fault tolerance: Driver |
|   third-party driver crashes entire system |   crash does not crash kernel. |
| - Difficult to maintain and extend.        | - Slower: Heavy IPC context    |
|                                            |   switching and message passing|
+-----------------------------------------------------------------------------+

Layered Architecture (Dijkstra's THE System):
- The OS is decomposed into $N$ hierarchical layers ( $0$ to $N$ ). Layer 0 is the hardware; Layer $N$ is the user interface.
- Each layer $i$ is implemented using only the operations provided by lower layer $i-1$ .
- Advantage: Clean modularity, simplified verification and debugging.
- Disadvantage: Inefficient execution due to multiple function abstraction boundaries; difficult to cleanly partition low-level dependencies.
Hybrid Kernels (Windows NT, macOS XNU):
- Combines the performance advantages of monolithic kernels with the modular structure and abstractions of microkernels.

4. The Process Concept & Process Control Block (PCB)

4.1 Process vs Program

A Program is a passive entity stored on non-volatile disk as an executable file (a sequence of binary instructions in ELF or PE format).
A Process is an active entity representing a program in execution, possessing an instruction pointer (Program Counter), CPU registers, memory segments, and allocated system resources.

4.2 Anatomy of a Process in Memory

CODE
High Memory (0xFFFFFFFF / 0x7FFFFFFFFFFF)
+---------------------------------------------------+
|                   Kernel Space                    | (Protected from User Access)
+---------------------------------------------------+
|               Environment & Arguments             |
+---------------------------------------------------+
|                       STACK                       | (Grows DOWNWARD)
| - Local variables, function parameters, returns   |
|                         |                         |
|                         v                         |
|                                                   |
|                         ^                         |
|                         |                         |
|                       HEAP                        | (Grows UPWARD)
| - Dynamically allocated memory (malloc, new, brk) |
+---------------------------------------------------+
|                   BSS Segment                     |
| - Uninitialized global and static variables       |
+---------------------------------------------------+
|              Initialized Data Segment             |
| - Global and static variables initialized by code |
+---------------------------------------------------+
|                   Text Segment                    |
| - Read-only compiled binary machine instructions  |
+---------------------------------------------------+
Low Memory (0x00000000)

4.3 Process States & Transitions

CODE
                +-------------------< Admitted <-------------------+
                |                                                  |
                v                                                  |
           +---------+        Scheduler Dispatch       +---------+ |
           |  READY  | ------------------------------> | RUNNING | |
           +---------+ <------------------------------ +---------+ |
                ^              Interrupt / Time Slice       |      |
                |                                           |      |
         I/O or Event                                  I/O or Event|
          Completion                                       Wait    |
                |                                           v      |
                +----------------- +---------+ <------------+      |
                                   | WAITING |                     |
                                   +---------+                     |
                                                                   |
          +-----+                                            +------------+
          | NEW | -----------------------------------------> | TERMINATED |
          +-----+                                            +------------+

The 5-state lifecycle:

New: The process is currently being created and its data structures allocated.
Ready: The process is loaded in main memory, possesses all required resources, and is awaiting CPU assignment.
Running: The process's instructions are currently being executed by a physical CPU core.
Waiting / Blocked: The process cannot execute because it is waiting for an external event (e.g., disk I/O completion, keyboard input, timer signal, child termination).
Terminated: The process has finished execution; its resources are deallocated, awaiting parent cleanup.

4.4 The Process Control Block (PCB / `task_struct`)

The PCB is the definitive data structure maintained by the operating system kernel for every active process:

Process Identification (PID): Unique positive integer identifier.
Process State: Current state (Ready, Running, Blocked, etc.).
Program Counter (PC): Address of the next machine instruction to be fetched and executed.
CPU Registers: Values of accumulators, index registers, stack pointers, and condition codes that must be saved when an interrupt occurs.
CPU Scheduling Information: Priority value, scheduling queue pointers, CPU time metrics.
Memory Management Information: Value of base/limit registers or pointers to Page Tables / Segment Tables.
Accounting Information: Total CPU time utilized, time limits, elapsed clock time.
I/O Status Information: List of allocated I/O devices, file descriptor table pointing to open files.

5. Context Switching & Process Scheduling Queues

5.1 Context Switching Mechanics

A Context Switch is the computational mechanism of stopping the currently executing process, saving its complete execution context into its PCB, and loading the saved execution context of another ready process from its PCB into the CPU hardware registers.

CODE
Process P_0                           Operating System                           Process P_1
    |                                        |                                        |
    | Executing                              |                                        |
    | --- Interrupt / System Call ---------> |                                        |
    |                                        | Save state into PCB_0                  |
    |                                        | Reload state from PCB_1                |
    |                                        |<---------------------------------------|
    |                                        |                                        | Executing
    |                                        | <--- Interrupt / System Call ----------|
    |                                        | Save state into PCB_1                  |
    |                                        | Reload state from PCB_0                |
    | <--------------------------------------|                                        |
    | Executing                              |                                        |

Context Switch Overhead

Context switching represents pure computational overhead; while the CPU is executing the context switch, no useful application work is accomplished. Factors influencing context switch duration:

Number of physical CPU registers to push and pop.
Flushing or invalidating the hardware Translation Lookaside Buffer (TLB) when switching virtual memory address spaces.
Cache pollution (the newly scheduled process experiences hardware CPU cache misses until its working set is reloaded into L1/L2 caches).

5.2 Process Scheduling Queues

As processes enter the system, they are placed into various kernel scheduling queues:

Job Queue: Holds all processes submitted to the system (typically on secondary storage spool).
Ready Queue: A linked list of PCBs of all processes that reside in main memory and are ready to execute.
Device / Wait Queues: Dedicated FIFO queues for each physical I/O device (e.g., Disk wait queue, Network socket wait queue).

5.3 Types of Schedulers

CODE
+-----------------------------------------------------------------------------+
| SCHEDULER             | INVOCATION FREQUENCY | PRIMARY RESPONSIBILITY       |
+-----------------------+----------------------+------------------------------+
| Long-Term Scheduler   | Infrequent (seconds, | Selects jobs from disk spool |
| (Job Scheduler)       | minutes)             | and loads them into memory.  |
|                       |                      | Controls Degree of Multipro- |
|                       |                      | gramming and process mix.    |
+-----------------------+----------------------+------------------------------+
| Short-Term Scheduler  | Extremely Frequent   | Selects which ready process  |
| (CPU Scheduler)       | (10 to 100 ms)       | in memory gets the CPU core. |
|                       |                      | Must be blazing fast.        |
+-----------------------+----------------------+------------------------------+
| Medium-Term Scheduler | Intermediate         | Swaps processes out to disk  |
| (Swapper)             | (seconds)            | when memory is overcommitted;|
|                       |                      | swaps them back in later.    |
+-----------------------+----------------------+------------------------------+

Process Mix: I/O-Bound vs CPU-Bound

I/O-Bound Process: Spends the vast majority of its time performing I/O operations; generates short CPU bursts before blocking (e.g., text editors, web browsers, database queries).
CPU-Bound Process: Spends the vast majority of its time performing heavy arithmetic and logical computations; generates long CPU bursts with infrequent I/O (e.g., scientific simulations, video encoding, matrix multiplication).
A well-balanced long-term scheduler maintains an optimal mix of both to ensure that neither the CPU nor the I/O channels sit idle.

6. Process Operations: Creation, Termination & States

6.1 Process Creation via `fork()`

In Unix-like systems, new processes are created exclusively by existing processes using the fork() system call, establishing a strict parent-child tree hierarchy rooted at PID 1 (init or systemd).

CODE
Parent Process (PID 100)
    |
    | --- fork() returns Child PID (e.g. 101) to Parent
    |
    +--------------------------------+
    |                                |
    v                                v
Parent Execution                 Child Process (PID 101)
  wait(NULL);                      fork() returns 0 to Child!
                                   execve("/bin/ls", ...);

Characteristics of `fork()`

Dual Return Values:
- To the parent process: Returns the newly created child's positive PID.
- To the child process: Returns 0.
- On failure: Returns a negative value (-1), and no child is created.
Address Space Cloning & Copy-on-Write (COW):
- Naive fork() historically duplicated the entire physical memory space of the parent.
- Modern operating systems employ Copy-on-Write (COW): Parent and child initially share the exact same physical memory pages marked as read-only. Only when either process attempts to write to a page does the hardware trigger a page fault, prompting the OS to allocate and copy a fresh physical page for the modifying process.
The exec() Family: Overwrites the calling process's text, data, heap, and stack segments with a completely new executable binary loaded from disk, keeping the same PID.

6.2 Process Termination: Zombie vs Orphan Processes

When a process executes its final instruction, it calls the exit() system call, passing an integer status code (e.g., exit(0)). The OS frees its physical memory, open file descriptors, and allocated resources. However, the process's entry in the Process Table must remain retained until the parent process reads its exit status via wait() or waitpid().

CODE
+-----------------------------------------------------------------------------+
|                           ZOMBIE vs ORPHAN PROCESS                          |
+-----------------------------------------------------------------------------+
| ZOMBIE PROCESS                                                              |
| - A child process that has TERMINATED, but whose parent has NOT YET called   |
|   wait() to read its termination exit status.                               |
| - Consumes no CPU or memory, but holds a slot in the kernel Process Table.  |
| - Defeated when parent finally invokes wait(), or when parent terminates.   |
+-----------------------------------------------------------------------------+
| ORPHAN PROCESS                                                              |
| - A process whose PARENT has TERMINATED while the child continues running.  |
| - Automatically adopted by the system root process (PID 1: init / systemd). |
| - init periodically invokes wait(), reaping orphans when they terminate.    |
+-----------------------------------------------------------------------------+

Operating Systems