Introduction to Operating Systems

Operating systems provide abstraction and arbitration services. Abstraction hides hardware details, allowing applications to run on various devices, while arbitration manages shared hardware resources for multiple applications. Key resources managed include the CPU, memory, I/O devices, and power management. Examples illustrate how OS functions support different processors and enable multi-application use without conflict. Unix-like systems and Windows are the two main categories of operating systems, with Unix derivatives dominating mobile and server markets, and Windows prevalent on desktops. Early systems like Multics influenced modern OS concepts such as cloud computing and multi-user environments. Unix, developed at Bell Labs, focused on performance and led to modern Linux and BSD systems.

A computer system is layered, with applications at the top, supported by libraries, utilities, and the operating system as an intermediary to the hardware. The core of the OS, the kernel, manages essential hardware sharing. Hardware components include the CPU for instruction execution, memory hierarchy (registers, cache, RAM, persistent storage) for data and instructions, and various I/O devices. Form factors like ATX, Micro ATX, Mini ITX, and rack-mount systems standardize hardware sizes. Workstations, often ATX or Micro ATX, typically support one user at a time. Rack-mount systems are space-efficient for servers. Internally, a computer consists of a power supply, motherboard (with CPU, RAM, expansion slots, onboard devices), and persistent storage like hard disks, solid-state drives, and optical drives.

The CPU executes instructions, using registers for direct computation and cache for immediate data/instructions. RAM stores programs and data during execution, faster than disk but volatile. Persistent storage (hard drives, SSDs) is the slowest but non-volatile and cheapest per unit. Hard drives are mechanical (platters, heads) and suffer from seek time and rotational delay, making them prone to eventual failure. SSDs use solid-state chips, offer higher performance without mechanical delays, but have finite write cycles and tend to fail over time due to wear. Backup strategies are crucial, with media stored off-site for disaster recovery. Optical discs, flash drives, tape drives, and cloud storage are common backup mediums, each with pros and cons regarding cost, speed, reliability, and security.

Disk input/output involves disk attachment mechanisms, magnetic disk properties, disk addressing, partitioning, and solid-state drives. Historically, PATA (IDE) and SCSI were common buses, replaced by SATA and SAS for serial interfaces, enabling higher speeds. Magnetic disks store information on platters accessed by heads, suffering from seek time and rotational delay. Disk addressing evolved from Cylinder-Head-Sector (CHS) geometry to Logical Block Addressing (LBA), where disk firmware handles physical mapping. Modern LBA supports huge disk sizes. Disk partitioning divides a disk into sections, useful for isolating data and optimizing performance. Master Boot Record (MBR) and GUID Partition Table (GPT) are common partitioning schemes, with GPT supporting larger disks for modern systems.

SSDs offer high performance due to no moving parts, using NAND flash memory. Flash cells have finite write cycles, leading to wear over time. Wear leveling dynamically reallocates blocks to extend SSD life. The ATA TRIM command is crucial for efficient wear leveling and reducing write amplification. However, SSDs pose challenges for forensic data recovery and secure erasure. Disk scheduling arbitrates disk access among programs and historically aimed to improve performance by reducing mechanical seek times. First-Come-First-Serve (FCFS), SCAN (elevator algorithm), and Shortest Seek Time First (SSTF) are classical scheduling algorithms. Modern SATA drives use Native Command Queuing (NCQ) to manage requests, rendering many OS-level seek-optimization algorithms obsolete. Linux schedulers like Deadline and Completely Fair Queuing (CFQ) manage I/O for responsiveness and fairness, with simpler schedulers like noop or Deadline being preferred for SSDs.

Software development involves planning, requirements analysis, design, coding, testing, and maintenance. Conceptualizing, analyzing requirements, designing, implementing, and testing are key steps. Maintenance includes bug fixes, requiring replication, verification, and testing of solutions. Process management and development models are crucial, especially for large teams. The code-and-fix model is simple but inefficient. The waterfall model is sequential, moving from concept to implementation, but often fails in practice due to evolving requirements. Iterative and incremental models like Rapid Application Development (RAD), Agile, and Extreme Programming (XP) are popular, emphasizing prototypes and customer feedback. The Spiral model includes risk analysis. Formal methods, like clean room software engineering, ensure rigorous verification for life and safety-critical systems. The level of formalism needed depends on team size, financial risk, and safety criticality.

File systems organize data on persistent storage, ensuring reliable retrieval. They abstract disk space, providing routines for file operations, human-readable names, and organizational structures like directories. They also arbitrate disk space among users and programs, enforcing permissions and quotas. File systems store metadata about each file, including name, size, ownership, permissions, and timestamps. Formatting creates a new file system on a partition, destroying previous data (though recoverable with forensic tools). Fragmentation occurs when file sections become non-contiguous, impacting performance on mechanical drives. Journaling records steps to maintain consistency during crashes. Internal layouts vary, such as File Allocation Table (FAT) and inodes (Unix), and extents support larger file sizes. Mounting makes file systems available to users, with Unix using mount points and Windows using drive letters.

Software development projects range from 'greenfield' (new from scratch) to 're-engineering' (working with existing, undocumented code). Most projects fall in between these extremes. Projects utilize resources such as people (architects, designers, developers, domain experts), money, and infrastructure (equipment, software). Requirements analysis aims to make effective use of these resources by determining what needs to be developed to build the right product. Stakeholders (people or entities with a vested interest) have interests (expectations) that can be technical, financial, or political. Actors (anything with behavior, human or computerized) interact with the system. Primary actors are direct users, while supporting actors are other systems or entities the system relies on. Functional requirements specify what the software does, while non-functional requirements (qualities like usability, reliability, performance, portability, efficiency) specify what the software is, embodied in its architecture.

Multi-programming runs multiple processes concurrently by quickly switching the CPU. This requires hardware support: an interrupt mechanism for preemption, a clock for timing, and CPU protection levels to restrict access. Two CPU protection levels (kernel/supervisor mode and user mode) are sufficient, with kernel mode having full access and user mode being restricted. x86 systems have four protection rings (0-3), with most OSes using 0 and 3. Virtualization extensions (e.g., Intel VTX) add a level below ring 0 (ring -1) for hypervisors. Mode switches, which occur when changing CPU modes, can be computationally expensive. Interrupts are events that stop current execution to handle an event, categorized as involuntary (I/O, clock, page faults) or voluntary (system calls, exceptions). The CPU provides hardware mechanisms to detect and handle interrupts.

The kernel provides abstraction (hardware access, scheduling, IPC) and arbitration (process isolation, security). It's crucial to separate mechanism (software methods for operations) from policy (rules for access or limits). The RC 4000 monitor kernel (1969) was an early example of good mechanism/policy separation, allowing IPC and sub-kernels. The Unix kernel (late 1960s) prioritized performance, embedding device drivers, scheduling, and memory management directly, becoming a monolithic kernel. Monolithic kernels contain the entire OS in kernel space, offering high performance but are less modular and prone to system crashes from single component failures. Microkernels, like the RC 4000, contain minimal code in kernel space, with most OS functions in user space. They are modular but suffer from performance overhead due to inter-process communication. Most modern kernels are hybrids, combining elements of both, with modular monolithic kernels and microkernels incorporating some monolithic features for performance.

UML (Unified Modeling Language) offers a standardized way to diagram software design, similar to blueprints for buildings. It emerged to standardize diverse diagramming formats, developed by Grady Booch, Ivar Jacobson, and Jim Rumbaugh at Rational Software. UML is standardized by the Object Management Group, though tool compliance can vary. It provides diagram types for system structure (class diagrams), behavior (activity and state machine diagrams), and interaction. Limitations include not replacing other design documents (like extensive use cases) and tool incompatibility. Activity diagrams model processes, such as software development or business workflows. They use an initial state (filled circle), final state (filled circle in another circle), action states (single operations), and activity states (longer processes with their own diagrams). Sequential branches (diamonds) allow decisions, while concurrent forks and joins (thick lines) split and merge parallel paths, often annotated with 'swim lanes' to show responsibility.

Handling hardware events efficiently is crucial. Two main options exist: polling (OS periodically checks devices), which is simple but wastes CPU time and causes high latency, or interrupts (devices signal the CPU when ready), which is more complex but more responsive. Interrupts involve the OS preempting running processes to handle the event. The CPU's fetch-execute cycle includes checking for pending interrupts. If an interrupt occurs, the CPU switches to kernel mode, saves the program counter, and loads an interrupt handler address from the Interrupt Vector Table (IVT). The IVT maps interrupt numbers to handler addresses. The handler executes, then returns control. Two types of interrupt controllers exist: older PICs using dedicated lines (IRQs), leading to conflicts and performance issues when shared, and newer APICs with Message Signaled Interrupts (MSI/MSI-X) over a shared bus, improving efficiency and reducing contention. DMA (Direct Memory Access) helps devices transfer data without CPU involvement.

Use cases are narrative requirements documents describing how a system behaves in scenarios, useful for testing post-implementation. They define system responses to stakeholder interactions, varying in level from high-level business use cases to detailed system use cases. Both black-box (system treated as a mystery) and white-box (detailing internal operations) scopes exist. Use case narratives typically include a trigger, actors (primary actor interacts directly, supporting actors enable tasks), preconditions (assumed true before execution), steps for system behavior, and guarantees (promises about system state, including minimal guarantees for failures). Simple language, active voice, and avoiding UI elements are recommended. UML use case diagrams provide visual indexes but lack detail, making textual narratives essential. Agile methods often prefer user stories—short, informal descriptions of what an actor wants to achieve—over formal use cases for brevity and adaptability.

Every software system has a 'state' (current variable values), and programs change this state. A finite state machine (FSM) models this with a fixed number of states, transitioning based on input and producing output. FSMs can be deterministic (single next state based on input) or non-deterministic (can change state without input). Mealy machines produce output at any time, while Moore machines only on entering a state. Simple FSMs are limited to regular languages. Adding a stack creates a push-down automaton for context-free languages. A linearly bounded automaton with a movable I/O tape can handle context-sensitive languages, closely resembling modern computers. Turing machines, with infinite tape, can handle recursively enumerable languages. UML state diagrams (for deterministic FSMs) model individual object behavior, using filled circles for initial/final states and rounded rectangles for internal states. States have names and activities triggered on entry, exit, or while active. Transitions are arrows with trigger conditions and optional guard expressions and actions. Nested state diagrams are possible but complex; a special symbol can indicate a state modeled by another diagram.

Dynamic memory allocation (DMA) improves multi-programming by allocating memory to processes as needed, rather than fixed-size chunks, leading to greater complexity. Fragmentation is a primary issue: external fragmentation occurs when free space is broken into small, non-contiguous pieces, while internal fragmentation happens when allocated blocks are larger than requested memory. Classic DMA algorithms include Best Fit (smallest chunk, minimizes internal frag, high external frag), Worst Fit (largest chunk, attempts to reduce external frag but often fails), First Fit (first large enough chunk, simple but creates small fragments at start of free list), and Next Fit (starts search from last allocation, avoids accumulation). None of these perfect and are mostly obsolete in modern kernels. Linux uses slob allocator (first fit) for embedded systems and slab allocation for non-embedded systems.

Modern operating systems use more efficient memory allocation, often employing power-of-two methods. These maintain allocated and free blocks in a binary tree structure. Memory is divided into super blocks, which are subdivided into smaller blocks (sub-blocks) as requested, creating a hierarchy of block sizes. This reduces external fragmentation through 'coalescence,' where adjacent free blocks merge into larger ones. The buddy system is a power-of-two strategy where blocks are repeatedly halved, and freed blocks are coalesced with their 'buddies' to form larger blocks. This is efficient for processes but can still cause internal fragmentation. For kernel data structures, 'slab allocation' is used to minimize both internal and external fragmentation. Kernel memory is arranged into fixed-size 'slabs,' each divided for specific kernel objects, pre-allocated into caches. The Linux kernel uses slub allocator (since 2.6.23) for this, being more memory efficient than older slab allocators on large systems.

Processes need CPU and RAM. RAM is hardware-based, volatile memory, distinct from persistent storage. Memory is addressed byte by byte, with 32-bit systems supporting 4GB and 64-bit systems supporting more. Each process has its own logical view of memory, divided into a stack (for automatic/local variables), heap (for dynamic allocation), global variables, and a text segment (for program code). The stack and heap grow towards each other. Programmers explicitly manage heap space in C/C++ (malloc/free, new/delete) but Java and Python use automatic garbage collection. Heap memory management is challenging for OSes due to dynamic, small, and frequent allocations. The kernel also has its own memory requirements for code and data structures. Memory is divided into kernel and user regions to share resources and maintain performance during interrupts or system calls. Fixed memory partitioning (used in embedded systems) allocates memory in static chunks, limiting multi-programming and leading to wasted space.

Paging shares memory among processes by allocating fixed-size 'pages' of logical memory. Each process gets its own logical address space. The CPU's Memory Management Unit (MMU) translates logical addresses (page number P and offset D) into physical addresses (frame number F and offset D). A 'page' refers to logical memory, while a 'frame' refers to physical memory; they are typically the same size (e.g., 4KB). Paging eliminates external fragmentation as physical frames don't need to be contiguous. The MMU uses a page table (stored in kernel RAM) to map logical page numbers to physical frame numbers. To avoid two memory accesses (one for page table, one for data) per translation, a Translation Lookaside Buffer (TLB) on the CPU caches recent page-to-frame mappings, allowing fast, parallel lookups. A TLB hit speeds up access; a TLB miss requires consulting the page table, incurring a performance cost. Policies determine which mappings are stored in the TLB.

Operating systems ensure memory protection by arbitrating access to RAM, preventing processes from interfering with each other or the kernel. In simpler memory management systems, 'segmentation' divides process memory into logical pieces (text, global variables, stack, heap) with access permissions. A segment table determines legal access; illegal attempts cause a 'segmentation fault' terminating the process. Modern paging systems implement memory protection via permission bits in page table entries (valid/invalid, read/write, execute). An invalid access causes a CPU fault, leading to process termination (again, a 'segmentation fault'). Read-only pages enable shared memory, saving resources by allowing multiple processes to access the same program code (e.g., web browsers). Newer CPUs (AMD 'NX bit', Intel 'XD bit') add a 'no execute' (NX) bit to page table entries, preventing execution of data in memory regions, enhancing security against buffer overflows. Extended Page Tables (EPT) or Rapid Virtualization Indexing (RVI) add another layer of paging for virtualization, allowing multiple guest OSes to manage their memory efficiently without constant hypervisor intervention, crucial for VM performance.

Testing software serves two main purposes: detecting and isolating bugs, and verifying that the application meets its requirements. Unit testing, a focus of Test-Driven Design (TDD), involves testing individual components (e.g., classes) in isolation, using assertions that are either true or false. Tests pass if results match expectations, fail otherwise. Both positive and negative test cases are used. Automated unit testing tools (X-Unit family like JUnit, PyUnit) are common. TDD is an iterative and incremental process: first, create a failing test case (ensuring a new feature is indeed being added and the test itself is valid). Next, write minimal code to make the test pass. Then, refactor the code for readability and cleanliness. Finally, rerun all existing tests to check for regressions. If regressions occur, fix them or revert code. TDD is not a universal solution; it cannot fix incorrect high-level specifications or test GUI elements easily. Maintaining test cases is crucial as software evolves to prevent regressions.

Page tables store mappings between logical pages and physical frames. When a TLB miss occurs, the page table is consulted. Most modern CPUs (x86-64, ARM) manage page table searches in hardware, increasing memory access time but avoiding context switches. Some architectures (MIPS) require the OS to manage page tables, leading to context switches and slower performance. Hierarchical page tables (tree structure) reduce search time by dividing page tables into pages, with logical addresses having multiple offset components. Hashed page tables use a hash function to find page table entries, optimizing for sparse address spaces in 64-bit systems. Inverted page tables store one entry per frame, efficient for storage but not performance. Extended Page Tables (EPT, or AMD's RVI) provide hardware support for virtualization, adding a layer of paging where the CPU translates guest virtual addresses to guest physical addresses, then to host physical addresses, without costly hypervisor mode switches, greatly benefiting virtual machine performance.

Object-Oriented Design (OOD) aims to increase software modularity by breaking systems into smaller, reusable components, thereby improving maintainability. Objects combine data (properties/fields) and behavior (methods) into logical units, modeled after real-world processes (e.g., a 'song player' object). OOD is theoretically independent of implementation language; procedural languages like C can implement OOD if programmers are disciplined, though OO languages (Java, C++) make it easier. Objects are instances of classes, which serve as templates. Granularity—the level of division into objects—is critical; too many small objects lead to complexity and performance issues, while too few large objects lose modularity. Key OOD objectives include: encapsulation (data and methods grouped in objects), information hiding (internal workings concealed), polymorphism (different objects expose compatible interfaces), and reuse (well-designed objects can be used in other applications). Downsides include potential for over-engineering, difficulty in reusing objects tied to specific business processes, and slower execution compared to procedural solutions due to dynamic memory allocation.

This section demonstrates implementing an object-oriented 'Horror' class (with a 'message' field and 'screen' method) in Java, C++, C, and Python. Java, an OO language, handles constructors/destructors and memory automatically (garbage collection). C++ requires manual memory management (new/delete, constructors/destructors), and its class definitions can break information hiding. C, a procedural language, can implement OOD using structs for data encapsulation, function pointers for methods, and factory functions for object creation, but requires manual memory management and explicit object passing to methods. Python offers a very compact and readable implementation due to its duck typing (objects with same interface are interchangeable) and automatic memory management, making it highly polymorphic and easy to reuse, but generally slower. The example also shows how to write procedural code in Java by using static methods and avoiding new object instantiation, illustrating that language choice doesn't strictly dictate design paradigm.

When memory demand exceeds physical RAM, the OS must decide which pages to keep and which to swap out to disk. This involves finding an unused page, ideally one not needed soon, to minimize page swaps. Page table entries gain 'referenced' and 'dirty' bits for OS to track usage and modifications. Page replacement can be global (any page swapped out) or local (only a process's pages swapped out). Local replacement is more complex due to Belady's anomaly (more frames don't always mean fewer faults) and aims for an 'optimal working set.' Classical algorithms include Random (ineffective), Oldest Page (ineffective if frequently accessed), Least Frequently Used (ineffective), Most Frequently Used (stupid idea), and Least Recently Used (LRU - theoretically best, but impractical to implement directly due to tracking overhead). The optimal algorithm (OPT) is impossible to implement as it requires future knowledge. Real-world systems use LRU approximations like Not Used Recently (NUR) that track reference/dirty bits and age counters for reasonable performance.

A process is an instance of a computer program in execution. Modern systems feature multi-threaded processes and provide private resource allocations (CPU, memory, data). Processes are segmented into text (code), data (global variables), stack (local variables), and heap (dynamic data), which grow towards each other. The OS tracks process information including memory usage, program counter, open files, network connections, and scheduling data (Process ID, owner, CPU time). Processes transition through states: New (creation), Ready (waiting for CPU), Running (executing), Waiting (for I/O), and Terminated (cleanup). Unix-like systems create processes via 'forking,' where a parent process copies itself. The child process can then run independently or load a different program using the 'exec' system call. Processes can be independent or cooperating (sharing information). This part covers the basics; Part 2 will delve into fork/exec details.

Each process has a 'process context' – minimal state needed for stopping and restarting (CPU registers, program counter, RAM contents). Switching between processes ('process switch') involves 'context switches' (saving/restoring context) which are expensive operations for the OS, requiring entry into kernel mode. The kernel saves the old process's state into its Process Control Block (PCB), marking it 'ready', then restores the new process's state from its PCB, marking it 'running', before switching back to user mode. PCBs, containing process state, ID, program counter, register contents, memory limits, and file descriptors, are stored in linked lists (job queue, ready list, device queues). Scheduling is categorized as: job/long-term (selecting processes for ready state), midterm (swapping active/inactive processes), and CPU/short-term (selecting processes from ready list to run). The 'dispatcher' performs the final context switch to start a process on a CPU core. I/O requests cause blocking operations, moving processes to a waiting state. CPU-bound processes are preempted by the scheduler to ensure system responsiveness.