Unit 1: Introduction to Operating System

1. Operating System Fundamentals & Core Services

An Operating System (OS) is system software that acts as an intermediary between the computer hardware and the user applications. From an architectural perspective, the operating system fulfills two foundational mandates:

1. Resource Manager: Coordinates and allocates physical computing resources—including CPU execution cycles, primary memory (RAM), disk storage space, and peripheral I/O devices—among competing processes to ensure fair, conflict-free, and efficient utilization.
2. Control Program: Governs the execution of user programs to prevent system-wide crashes, security compromises, and unauthorized access to hardware resources.

CODECopy Code
                      Computer System Architecture
   ┌──────────────────────────────────────────────────────────────┐
   │       User Applications (Browsers, Compilers, DBMS)          │
   └──────────────────────────────┬───────────────────────────────┘
                                  │ System Calls
   ┌──────────────────────────────▼───────────────────────────────┐
   │                     Operating System                         │
   │  ┌────────────────────────────────────────────────────────┐  │
   │  │ Process Manager  │ Memory Manager   │ File Subsystem   │  │
   │  ├──────────────────┼──────────────────┼──────────────────┤  │
   │  │ Device Drivers   │ Security & Auth  │ Network / IPC    │  │
   │  └────────────────────────────────────────────────────────┘  │
   └──────────────────────────────┬───────────────────────────────┘
                                  │ Privileged Hardware Instructions
   ┌──────────────────────────────▼───────────────────────────────┐
   │          Computer Hardware (CPU, RAM, Disks, NICs)           │
   └──────────────────────────────────────────────────────────────┘

1.1 Core Subsystems of Modern Operating Systems

• Process Management: Handles process creation, scheduling, synchronization, inter-process communication (IPC), and deadlock detection.
• Main Memory Management: Allocates dynamic memory segments, manages virtual memory address spaces via paging or segmentation, and tracks free/occupied memory blocks.
• File System Management: Abstracts physical disk sectors into logical files and hierarchical directories, managing metadata, access control lists (ACLs), and persistent indexing.
• I/O Subsystem: Decouples application code from peripheral hardware using device drivers, interrupt handlers, and buffering/caching layers.
• Protection & Security: Enforces access boundaries between separate user processes and defends system assets against internal tampering and external threats.

2. Hardware Support & Dual-Mode Execution

To maintain system integrity and prevent user applications from causing catastrophic hardware failure or monopolizing CPU resources, modern computer hardware enforces Dual-Mode Operation.

2.1 User Mode vs. Kernel Mode

The CPU architecture incorporates a dedicated hardware register containing a Mode Bit:

• User Mode (Mode Bit = 1): The execution mode used when running standard user application code. The CPU operates under restricted execution capabilities; direct memory access to kernel address spaces and execution of privileged machine instructions are strictly prohibited by hardware logic.
• Kernel Mode (Mode Bit = 0) (also designated as Supervisor Mode, System Mode, or Privileged Mode): The execution mode used when running operating system kernel routines. The CPU possesses complete, unrestricted access to the entire physical memory map and can execute all low-level hardware instructions.

CODECopy Code
                       Dual-Mode State Transitions
    User Mode                                         Kernel Mode
  (Mode Bit = 1)                                    (Mode Bit = 0)
┌─────────────────┐                               ┌─────────────────┐
│ User Application│ ─── Trap / System Call ────►  │ System Call     │
│ Executes        │                               │ Handler (Kernel)│
│                 │ ◄── Return from Trap / Syscall │ Executes Task   │
└─────────────────┘                               └─────────────────┘

2.2 Privileged Instructions

Privileged instructions are machine instructions that can alter the system's operational state or bypass security mechanisms. If a process running in User Mode attempts to execute a privileged instruction, the CPU hardware generates a Trap (software interrupt), immediately transferring execution to the kernel's fault handler, which terminates the offending process with an illegal operation exception.

Examples of Privileged Instructions:

• Disabling or re-enabling hardware CPU interrupts (CLI, STI).
• Loading or modifying memory management registers (Base/Limit registers, Page Table Base Register CR3).
• Initiating direct I/O port commands (IN, OUT on x86).
• Altering the CPU Mode Bit.
• Halting the central processing unit (HLT).

2.3 Hardware Protection Mechanisms

1. Memory Protection: The Memory Management Unit (MMU) uses Base and Limit Registers (or Paging Table Protection Bits). The Base Register holds the smallest physical memory address the process may access, while the Limit Register specifies the range size. Every memory reference generated by a user process is verified by hardware: if $\text{Address} < \text{Base}$ or $\text{Address} \ge \text{Base} + \text{Limit}$, a hardware trap occurs.
2. CPU Protection (Programmable Interval Timer): Prevents a user program from entering an infinite loop and permanently seizing the CPU. The OS loads an integer value into a hardware timer before dispatching a user process. With every clock tick, the timer decrements. When the timer reaches zero, a hardware Timer Interrupt is generated, forcibly transferring control back to the OS scheduler.

3. Evolution and Taxonomy of Operating Systems

Operating system architectures evolved across several decades in tandem with advancements in semiconductor hardware:

CODECopy Code
                            Evolution Timeline
  Serial Processing ──► Batch Systems ──► Multiprogramming ──► Time-Sharing ──► Distributed / RTOS
   (Direct hardware      (Card readers,    (Keep multiple jobs   (Interactive CPU    (Deterministic bounds,
    switches, no OS)      resident mon.)    in RAM, overlap I/O)  slicing, multi-user) network scaling)

3.1 Historical Evolution

1. Serial Processing (No OS): In the 1940s–1950s, programmers interacted directly with hardware using patch boards and mechanical switches. System setup time was massive, and CPU idle time was immense.
2. Simple Batch Systems: Introduced Resident Monitors. Programs with similar requirements were grouped into batches on punch cards and processed sequentially without manual operator intervention.
3. SPOOLING (Simultaneous Peripheral Operations On-Line): Utilized high-speed magnetic disks as intermediate buffer storage between slow I/O devices (card readers) and the CPU, allowing I/O operations of one job to overlap with the computation of another.

3.2 Multiprogramming vs. Time-Sharing Systems

3.3 Real-Time Operating Systems (RTOS)

An RTOS is engineered for environments where computing correctness depends not only on the logical output of calculations, but also on the strict temporal predictability of when results are delivered.

• Hard Real-Time Systems: Missing a scheduling deadline results in catastrophic, irreversible failure of the entire system. Virtual memory swapping and unpredictable caching are typically eliminated. Examples: Nuclear reactor control, fly-by-wire avionics, automotive airbag deployment, pacemaker telemetry.
• Soft Real-Time Systems: Missing a deadline degrades service quality but does not lead to physical destruction or total system collapse. Real-time tasks receive priority over non-critical tasks. Examples: Audio/video streaming, telecommunications switches, robotic vacuum navigation.

3.4 Parallel and Distributed Systems

• Tightly-Coupled (Multiprocessor) Systems: Multiple CPU cores share a single physical main memory, system bus, and peripheral subsystem.
  • Symmetric Multiprocessing (SMP): All processors execute identical OS instances and share all resources equally without a master-slave hierarchy.
  • Asymmetric Multiprocessing (ASMP): A dedicated master processor schedules tasks and delegates specific workloads to subordinate processors.
• Loosely-Coupled (Distributed) Systems: A collection of physically separate, independent computer nodes, each with its own local memory and clock, interconnected via a high-speed communication network (LAN/WAN) coordinating through message-passing.

4. Operating System Structures & System Calls

A System Call is the programmatic mechanism by which an application requests a privileged service from the operating system kernel. It represents the formal Application Binary Interface (ABI) between user space and kernel space.

4.1 System Call Invocation Sequence

1. The user program invokes an API wrapper function (e.g., POSIX read() or Win32 ReadFile()).
2. The wrapper places the system call identity number in a specific CPU register (e.g., EAX / RAX on x86).
3. The wrapper executes a dedicated software trap instruction (e.g., syscall, sysenter, or int 0x80).
4. The CPU hardware switches the mode bit from 1 (User) to 0 (Kernel) and jumps to the kernel's System Call Dispatch Table entry.
5. The kernel validates parameters, executes the requested service routine, and places the return value in a register.
6. The kernel executes a return-from-trap instruction (sysret or iret), restoring the mode bit to 1 and returning control to user space.

CODECopy Code
                  System Call Parameter Passing Techniques
  ┌────────────────────────────────────────────────────────────────────────┐
  │ 1. CPU Registers: Fastest mechanism; parameters loaded directly into   │
  │    hardware registers. Limited by available register count.            │
  ├────────────────────────────────────────────────────────────────────────┤
  │ 2. Memory Block / Table: Parameters written into an in-memory block;  │
  │    the base address of the block is passed in a single CPU register.   │
  │    (Standard approach in Linux/UNIX for complex structs).              │
  ├────────────────────────────────────────────────────────────────────────┤
  │ 3. System Stack: Parameters pushed onto the program stack by user code │
  │    and popped off by the kernel trap handler.                          │
  └────────────────────────────────────────────────────────────────────────┘

4.2 Categories of System Calls

1. Process Control: fork() (create process), execve() (load binary), waitpid() (await child exit), exit() (terminate), kill() (send signal).
2. File Management: open(), read(), write(), close(), lseek(), stat().
3. Device Management: ioctl(), read(), write().
4. Information Maintenance: getpid(), alarm(), time(), sysinfo().
5. Communications: pipe(), shmget() (shared memory), socket(), send(), recv().
6. Protection: chmod(), chown(), umask().

4.3 Architectural Kernel Models

CODECopy Code
         Monolithic Kernel                             Microkernel Architecture
  ┌───────────────────────────────┐               ┌─────────────────────────────────┐
  │       User Applications       │               │ User Apps │ File Server │ Net Drv│ (User Space)
  ├───────────────────────────────┤               ├───────────┴─────────────┴────────┤
  │   Monolithic Kernel Space:    │               │ IPC │ Virtual Memory │ Sched     │ (Kernel Space)
  │ - Virtual Memory - Process Mgt│               └─────────────────────────────────┘
  │ - File Systems   - Net Stacks │                     (Hardware Platform)
  │ - Device Drivers - Hardware   │
  └───────────────────────────────┘

• Monolithic Kernels (e.g., Linux, FreeBSD): The entire operating system—including virtual memory management, CPU scheduling, file systems, network stacks, and device drivers—executes in a single, unified kernel address space.
  • Advantage: Superior execution speed because intra-kernel components communicate via direct C function calls without context switching.
  • Disadvantage: Poor fault isolation; a single buggy device driver can corrupt kernel memory and panic the entire operating system.
• Microkernel Architecture (e.g., Mach, QNX, L4): Strips the kernel down to the absolute bare minimum set of mechanisms required to support an operating system: low-level memory addressing, inter-process communication (IPC), and basic thread scheduling. All traditional OS services (file systems, networking, device drivers) run as independent server processes in User Space.
  • Advantage: High modularity, security, and fault tolerance; if a file system server crashes, it can be restarted without taking down the kernel.
  • Disadvantage: Significant performance degradation caused by continuous user-to-kernel context switches and IPC message copying overhead.
• Hybrid Kernels (e.g., Windows NT, macOS XNU): Combine the modular structure of a microkernel with the high-performance execution of a monolithic kernel by running performance-critical servers (like graphics subsystems) inside kernel space.
• Loadable Kernel Modules (LKMs): Modern monolithic kernels (like Linux) dynamically link and unlink compiled object modules (.ko files) into kernel space at runtime without requiring system rebooting or kernel recompilation.

5. Process Architecture, Lifecycle, and Scheduling

A Process is defined fundamentally as a program in execution. While a program is a passive entity stored on disk as an executable binary file (e.g., app.exe), a process is an active, dynamic entity possessing hardware state, memory resources, and execution context.

5.1 Memory Layout of a Process

When an operating system loads an executable binary into main memory, it structures the process virtual address space into distinct functional segments:

CODECopy Code
                  Process Virtual Memory Segments
  High Memory Address 0xFFFFFFFF
    ┌────────────────────────────────────────────────────────┐
    │ Stack Segment (Grows downward towards lower addresses) │
    │   - Local function variables                           │
    │   - Activation frames, parameter passing, return ptrs  │
    ├────────────────────────────────────────────────────────┤
    │                           │                            │
    │                           ▼                            │
    │                                                        │
    │                           ▲                            │
    │                           │                            │
    ├────────────────────────────────────────────────────────┤
    │ Heap Segment (Grows upward towards higher addresses)   │
    │   - Dynamic memory allocated via malloc(), new()       │
    ├────────────────────────────────────────────────────────┤
    │ BSS Segment (Uninitialized global and static data)     │
    ├────────────────────────────────────────────────────────┤
    │ Data Segment (Initialized global and static variables) │
    ├────────────────────────────────────────────────────────┤
    │ Text Segment (Compiled machine bytecode instructions)  │
    └────────────────────────────────────────────────────────┘
  Low Memory Address 0x00000000

5.2 Process State Lifecycle

During its lifespan, a process transitions through several discrete operational states:

1. NEW: The process is in the process of being instantiated and allocated memory structures.
2. READY: The process is loaded in main memory and possesses all required resources, waiting exclusively for CPU timeslice assignment by the scheduler.
3. RUNNING: The instructions of the process are currently being executed on a physical CPU core.
4. WAITING (Blocked): The process cannot execute because it is waiting for an external event (e.g., completion of disk I/O, reception of a network packet, or synchronization lock acquisition).
5. TERMINATED: The process has finished executing its code or was forcibly aborted; its resources are being reclaimed by the kernel.

CODECopy Code
                       Process State Transition Diagram
    
                     ┌──────────┐
                     │   NEW    │
                     └────┬─────┘
                          │ Admitted by Long-Term Scheduler
                          ▼
        ┌──────────► ┌──────────┐   Scheduler Dispatch   ┌───────────┐
        │            │  READY   │ ─────────────────────► │  RUNNING  │ ─── Exit ──► ┌──────────┐
        │            └──────────┘ ◄───────────────────── └─────┬─────┘              │TERMINATED│
        │                         Timer Interrupt / Yield      │                    └──────────┘
        │                                                      │ I/O or Event Wait
        │                  ┌──────────┐                        │
        └───────────────── │ WAITING  │ ◄──────────────────────┘
          I/O or Event Done└──────────┘

5.3 Process Control Block (PCB)

The Process Control Block (represented as struct task_struct in the Linux kernel) is the operating system's internal data structure representing an individual process. It encapsulates:

• Process Identifier (PID): Unique numerical identifier assigned to the process.
• Process State: Current state (READY, RUNNING, WAITING, etc.).
• Program Counter (PC): Memory address of the next machine instruction to execute.
• CPU Registers: Accumulators, index registers, stack pointer (SP), and condition code flags.
• CPU Scheduling Information: Process priority, scheduling queue pointers, CPU burst accounting.
• Memory Management Information: Page tables, segment tables, and base/limit registers.
• Accounting Information: Total CPU time consumed, execution limits, process start time.
• I/O Status Information: List of allocated I/O devices and array of open file descriptors.

5.4 Context Switching Mechanics & Overhead

A Context Switch is the low-level kernel procedure of saving the hardware execution context of the currently executing process and loading the saved execution context of a newly scheduled process.

Step-by-Step Context Switch Sequence:

1. An interrupt occurs (e.g., timer interrupt) or a process issues a blocking system call.
2. The hardware switches to Kernel Mode and saves the Program Counter and basic registers onto the kernel stack.
3. The kernel's context switch handler saves the remainder of the CPU register file into the outgoing process's PCB.
4. The scheduler algorithm selects the next process from the Ready Queue.
5. The kernel updates memory management hardware by loading the incoming process's page directory address into the CPU register (e.g., CR3 on x86).
6. The register state of the incoming process is loaded from its PCB into the CPU hardware registers.
7. The kernel executes a return-from-interrupt instruction, switching back to User Mode (Mode Bit = 1) and resuming the new process at its saved Program Counter.

Performance Costs of Context Switching:

• Direct Overhead: CPU cycles spent saving/restoring register state, executing scheduler code, and managing stack frames (pure unproductive overhead).
• Indirect Overhead (Cache Invalidation): Switching page directories invalidates the CPU's Translation Lookaside Buffer (TLB) and disrupts L1/L2 hardware CPU caches. The newly scheduled process suffers severe cache misses until its memory working set is reloaded ("cache warming").

5.5 Schedulers: Long-Term, Short-Term, and Medium-Term

1. Long-Term Scheduler (Job Scheduler):
   • Controls the Degree of Multiprogramming (the total number of processes residing simultaneously in memory).
   • Selects jobs from disk spool storage and admits them into main memory.
   • Executes infrequently (seconds or minutes). Strives to maintain a balanced mix of CPU-bound and I/O-bound processes.
2. Short-Term Scheduler (CPU Scheduler):
   • Selects which process from the in-memory Ready Queue receives CPU execution time.
   • Executes with extreme frequency (every 10 to 100 milliseconds). Must be exceptionally fast to minimize scheduling latency.
3. Medium-Term Scheduler (Swapper):
   • Manages memory overcommit by temporarily removing processes from main memory and writing them to swap space on disk (Swapping Out), placing them in the Suspended-Ready or Suspended-Blocked state.
   • When memory pressure eases, it reintroduces suspended processes back into RAM (Swapping In).

5.6 Process Operations: Creation, Termination, Zombies, and Orphans

• Process Creation (fork() in UNIX):
  • Creates an exact duplicate child process inheriting the parent's environment, credentials, and open file descriptors.
  • Returns 0 to the child process and returns the child's positive PID to the parent process.
  • Copy-On-Write (COW): Modern kernels do not duplicate physical memory pages immediately upon fork(). Instead, parent and child share read-only virtual memory pages until one process writes to a page, at which point the kernel duplicates only that modified page.
  • The child typically executes execve() to overwrite its memory image with a new executable program.
• Process Termination (exit()):
  • The process voluntarily terminates by calling exit(int status) or is aborted by a signal.
  • The kernel reclaims the process's physical memory, open files, and I/O allocations, but retains its exit status code and PID entry in the kernel process table.
• Zombie Process: A process that has terminated its execution via exit(), but whose parent process has not yet read its exit status via wait() or waitpid(). A zombie process consumes no CPU or RAM, but continues to occupy a slot in the operating system's finite Process Table.
• Orphan Process: A child process whose parent process terminates before the child completes. In POSIX systems, orphan processes are immediately adopted by the root ancestor process (systemd or init with PID 1), which periodically invokes wait() to reap their exit codes and prevent permanent zombies.