1. Computer System Fundamentals

1.1 Basic Components

• Processor: Central processing unit (CPU), the primary execution engine.
• Main Memory: Volatile storage; contents are lost on power-off.
• I/O Modules: Devices like disks, keyboards, and network interfaces.
• System Bus: Communication backbone linking processor, memory, and I/O.

1.2 CPU Registers

Registers are high-speed storage units within the CPU designed to reduce memory access latency.

• User-Visible Registers: Accessible via machine or assembly instructions; used by system software to optimize performance.
• Control and Status Registers (CSRs): Manage processor operations. Examples include:
  • Program Counter (PC): Holds the address of the next instruction to fetch.
  • Instruction Register (IR): Stores the most recently fetched instruction.
  • Program Status Word (PSW): Contains condition codes set by hardware after operations (e.g., zero, carry flags).
  • Data Registers: General-purpose but may be specialized (e.g., for floating-point math).
  • Address Registers: Store memory addresses of data, instructions, or partial addresses. A stack pointer is a special address register for managing call stacks.

1.3 Instruction Execution Cycle

An instruction cycle consists of fetch and execute phases. During fetch, the PC provides the instruction address; after execution, the PC increments to point to the next instruction.

1.4 Interrupt Handling

Interrupts improve CPU efficiency by allowing asynchronous event handling. Before servicing an interrupt, the CPU saves critical state—typically the PC and PSW. Multiple interrupts are managed via priority-based schemes, supporting either sequential or nested handling.

1.5 I/O Techniques and Caching

• Cache Memory: On-chip buffer storing recently accessed memory blocks. On a cache miss, a block containing the requested byte is loaded from main memory.
• I/O Methods:
  1. Programmed I/O: CPU polls device status registers.
  2. Interrupt-Driven I/O: Device signals completion via interrupt.
  3. DMA (Direct Memory Access): Dedicated controller transfers data directly between I/O devices and memory without CPU involvement.

1.6 Key Terminology

• PC: Program Counter
• IR: Instruction Register
• MAR/MBR: Memory Address/Data Buffer Registers
• I/O AR/BR: I/O Address/Data Buffer Registers
• AC: Accumulator
• PSW: Program Status Word
• ISR: Interrupt Service Routine
• DMA: Direct Memory Access

---

2. Operating System Overview

2.1 Design Goals

• Convenience: Simplify user interaction.
• Efficiency: Maximize resource utilization.
• Evolvability: Support future enhancements.

2.2 Evolution Drivers

• Hardware advancements
• New service requirements
• Bug fixes and security patches

OS services include program execution, I/O/file access, error handling, accounting, and standardized interfaces (ISA, ABI, API).

2.3 Historical OS Models

• Serial Processing: Manual setup per job; inefficient.
• Simple Batch: Jobs queued; automatic loading via monitor program. Requires memory protection, timers, privileged instructions, and interrupts.
• Multiprogramming Batch: CPU switches to another job during I/O waits. Relies on I/O interrupts and DMA.
• Time-Sharing: Rapid context switching enables concurrent user sesssions.

2.4 Key OS Achievements

• Process abstraction
• Memory management
• Security and protection
• Resource scheduling
• Modular system design

2.5 Process vs. Thread

• Process: An executable instance with its own resources (memory, files). The OS allocates resources per process.
• Thread: Lightweight execution unit within a process. Shares process resources. Threads are scheduled independently.
• Multithreading: Decomposing a process into concurrent threads.
• Concurrency: Logical simultaneity on a single CPU.
• Parallelism: Physical simultaneity across multiple CPUs/cores.

---

3. Processes

3.1 Process Attributes

Stored in the Process Control Block (PCB):

• Identifier, state, priority
• Program counter, memory pointers
• Context data, I/O status, accounting info

3.2 Process States

• Two-State Model: Running / Not Running
• Five-State Model: New, Ready, Running, Blockedd, Exit
• Suspended States: Blocked/Suspend and Ready/Suspend (stored on disk to free RAM)

3.3 Process Creation/Termination

• Creation Triggers: Batch jobs, logins, service requests, fork().
• Termination Causes: Normal exit, timeout, memory exhaustion, errors, parent termination.

3.4 Process Image and Tables

A process image includes:

• User program and data
• System stack (LIFO)
• PCB

The OS maintains four key tables:

1. Memory Tables: Track allocation and permissions.
2. I/O Tables: Manage device status and transfers.
3. File Tables: Record file metadata and locations.
4. Process Tables: Describe all active processes.

3.5 Execution Modes

• User Mode: Restricted; non-privileged instructions only.
• Kernel Mode: Full hardware access; handles system calls, interrupts, and traps.

---

4. Threads

4.1 Thread Advantages

Faster creation, termination, context switching, and inter-thread communication (due to shared address space).

4.2 Thread States

Same as processes: Running, Ready, Blocked. Operations include spawn, block, unblock, finish.

4.3 Thread Implementations

• User-Level Threads: Managed by application runtime. Fast switching but cannot leverage multiple cores.
• Kernel-Level Threads: Managed by OS. Supports true parallelism but incurs kernel overhead.
• Hybrid Models: Combine benefits of both approaches.

---

5. Concurrency: Mutual Exclusion and Synchronization

5.1 Key Terms

• Critical Section: Code accessing shared resources.
• Race Condition: Unpredictable behavior due to unsynchronized access.
• Deadlock: Circular waiting among processes.
• Livelock: Continuous state changes without progress.
• Starvation: A ready process never scheduled.

5.2 Mutual Exclusion Requirements

1. Only one process in critical section at a time.
2. No interference from blocked processes.
3. Bounded waiting (no starvation/deadlock).
4. Progress when critical section is free.
5. Independence from CPU speed or count.

5.3 Hardware-Based Solutions

Use atomic instructions like compare_and_swap:

int lock = 0;
void enter_critical() {
    while (compare_and_swap(&lock, 0, 1) != 0);
}
void leave_critical() {
    lock = 0;
}

Drawbacks: Busy-waiting wastes CPU cycles.

5.4 Semaphores

Integer variable with atomic wait() (P) and signal() (V) operations:

semaphore mutex = 1;
void task() {
    semWait(mutex);
    // critical section
    semSignal(mutex);
}

• Binary Semaphore: Values 0 or 1.
• Mutex: Must be released by the same thread that acquired it.

5.5 Monitors

High-level construct ensuring only one process executes inside at a time. Uses condition variables with cwait() and csignal():

monitor BoundedBuffer {
    char buffer[N];
    int count = 0, in = 0, out = 0;
    condition notfull, notempty;

    void append(char item) {
        if (count == N) cwait(notfull);
        buffer[in] = item;
        in = (in + 1) % N;
        count++;
        csignal(notempty);
    }
}

5.6 Message Passing

Processes coordinate via send() and receive():

// Mutual exclusion using a token message
void process() {
    message token;
    receive(mailbox, token);
    // critical section
    send(mailbox, token);
}

• Direct Addressing: Specify sender/receiver explicitly.
• Indirect (Mailbox): Use shared queues for flexible communication patterns.

5.7 Classic Problems

• Producer-Consumer: Shared buffer with synchronization for empty/full states.
• Reader-Writer: Multiple readers allowed; writers require exclusive access.

Note: Producer-consumer is distinct—it requires bidirectional coordination (producers check buffer space, consumers check data availability).

---

6. Deadlock and Starvation

6.1 Deadlock Conditions

Four necessary conditions:

1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait

6.2 Prevention Strategies

• Hold-and-Wait: Require all resources upfront.
• No Preemption: Allow OS to forcibly reclaim resources.
• Circular Wait: Impose global resource ordering.

6.3 Avoidance (Banker’s Algorithm)

Maintain a safe state where all processes can eventually complete. Before granting a request, simulate allocation to ensure safety.

6.4 Detection and Recovery

• Detection: Use resource-allocation graphs or matrix-based algorithms to identify cycles.
• Recovery:
  • Terminate deadlocked processes.
  • Roll back to checkpoints.
  • Preempt resources incrementally.

---

7. Memory Management

7.1 Requirements

• Relocation: Map logical to physical addresses.
• Protection: Prevent unauthorized access.
• Sharing: Allow controlled access to common regions.
• Logical/Physical Organization: Support modular programs and efficient storage.

7.2 Partitioning Schemes

• Fixed Partitions: Equal/unequal sizes; suffer internal fragmentation.
• Dynamic Partitions: Allocate exact needed space; suffer external fragmentation.
  • Placement Policies: First-fit, best-fit, next-fit.
• Buddy System: Binary-splitting allocator balancing internal/external fragmentation.

7.3 Paging

Divide memory and processes into fixed-size pages (process) and frames (memory). A page table maps pages to frames. Causes minor internal fragmentation.

7.4 Segmentation

Divide programs into variable-sized segments (e.g., code, data, stack). Causes external fragmentation but supports logical modularity.

---

8. Virtual Memory

8.1 Paging Enhancements

• Two-Level Page Tables: Hierarchical structure to reduce memory overhead.
• Inverted Page Tables: One entry per frame; uses hashing for lookup.
• TLB (Translation Lookaside Buffer): Cache for recent page-table entries.

8.2 Page Replacement Algorithms

• OPT: Theoretical optimum (replace farthest-used page).
• LRU: Replace least recently used.
• FIFO: Replace oldest page.
• Clock: Approximate LRU using a circular buffer and use bits.

8.3 Working Set and Thrashing

• Resident Set: Pages currently in physical memory.
• Thrashing: Excessive paging due to undersized resident sets.
• Load Control: Adjust number of concurrent processes to balance CPU and I/O utilization.

---

9. CPU Scheduling

9.1 Scheduler Types

• Long-Term: Admits jobs to the ready queue.
• Medium-Term: Swaps processes in/out of memory.
• Short-Term: Selects next process to run (dispatcher).

9.2 Scheduling Algorithms

• FCFS: Simple but penalizes short jobs.
• Round Robin: Time-sliced; fair but overhead-heavy.
• SPN/SRT: Shortest job/remaining time first; optimal but requires prediction.
• HRRN: Highest response ratio ((wait + service) / service).
• Feedback: Multilevel queues with aging.

---

11. I/O and Disk Management

11.1 I/O Techniques

• Programmed I/O: CPU polls device status.
• Interrupt-Driven: Device notifies CPU on completion.
• DMA: Transfers blocks directly between device and memory.

11.2 Disk Scheduling

Minimize seek time and rotational latency:

• FIFO: Fair but inefficient.
• SSTF: Shortest seek time first; may starve distant requests.
• SCAN/C-SCAN: Elevator algorithm; balances fairness and performance.
• N-Step SCAN/FSCAN: Batch requests to prevent starvation.

11.3 RAID Levels

Redundant arrays improve performance and reliability:

• RAID 0: Striping (no redundancy).
• RAID 1: Mirroring.
• RAID 5: Striping with distributed parity.

---

12. File Systems

12.1 File Organization

• Heap: Unordered records.
• Sequential: Sorted by key field.
• Indexed Sequential: Adds index and overflow areas.
• Hashed: Direct access via hash function.

12.2 Directory Structures

• Tree-Based: Hierarchical paths (e.g., /home/user/file.txt).
• Working Directory: Current context for relative paths.

12.3 File Allocation

• Contiguous: Fast access but external fragmentation.
• Linked: No fragmentation but poor locality.
• Indexed: FAT or inode-based; supports direct/sequential access.

12.4 Access Control

Permissions form a hierarchy: none → know → execute → read → append → update → change protection → delete.