CS703 — Final Term Summary (Lectures 23–45)

📘 Lecture 23 — Overview of today’s lecture

📖 Overview: This lecture introduces the fundamental goals and mechanisms of OS memory management. It explores how memory is allocated among competing processes, the historical evolution from simple techniques like fixed and variable partitioning to modern virtual memory, and the critical issues of protection, relocation, and fragmentation.

🗂️ Topics Covered

The lecture covers the goals of OS memory management, the core questions regarding memory management, the concept of multiprogramming with linker-loaders and swapping, the use of virtual addresses for multiprogramming, the memory hierarchy, and the two old techniques of fixed partitioning and variable partitioning, including their mechanics and the problem of fragmentation.

📝 Lecture Summary

Goals of OS memory management

The primary goals are to allocate scarce memory resources among competing processes to maximize memory utilization and system throughput, and to provide isolation between processes so that one process cannot interfere with another's memory. The tools used to achieve these goals include base and limit registers, swapping, paging (with page tables and TLBs), segmentation (with segment tables), page fault handling (which enables virtual memory), and the policies that govern the use of these mechanisms.

💡 Why this matters: Understanding these goals is foundational; every memory management technique is designed to solve one or more of these core problems.

Our main questions regarding Memory Management

The three central questions that memory management must answer are: How is protection enforced? How are processes relocated? And how is memory partitioned?

Today’s desktop and server systems

The basic abstraction for memory management in modern systems is virtual memory (VM). VM enables programs to execute without requiring their entire address space to be resident in physical memory, allowing a program to run on machines with less RAM than it "needs." This works because many programs don't need all of their code or data at once (e.g., branches they never take). Furthermore, virtual memory isolates processes from each other, as one process cannot name the addresses visible to others; each process has its own isolated address space. Virtual memory requires hardware and OS support, including MMUs, TLBs, page tables, and page fault handling, and is typically accompanied by swapping and at least limited segmentation.

Multiprogramming: Linker-loader

Can multiple programs share physical memory without hardware translation? Yes. When a program is copied into memory, its addresses (for loads, stores, jumps) are changed to use the addresses of where the program lands in memory. This relocation is performed by a linker-loader (e.g., UNIX ld). The compiler generates each .o file with code that starts at location 0. To create an executable, the linker-loader scans each .o, changing addresses to point to where each module goes in the larger program.

• Swapping is a technique where a program's entire state (including its memory image) is saved to disk, allowing another program to run. The first program can be swapped back in later and restarted right where it was.
• With multiple processes/jobs in memory at once (to overlap I/O and computation), memory management requirements include: protection (restrict which addresses processes can use), fast translation (memory lookups must be fast despite the protection scheme), and fast context switching (updating memory hardware must be quick when switching between jobs).

🔑 Definition — Linker-loader: A program that combines multiple object files into a single executable, adjusting addresses (relocation) to reflect where the program will reside in physical memory. 🔑 Definition — Swapping: Saving a process's entire memory image to disk and restoring it later, allowing the CPU to run other processes in the meantime.

Virtual addresses for multiprogramming

To make it easier to manage memory of multiple processes, processes use virtual addresses. These are independent of the location in physical memory (RAM) where the referenced data lives. The OS determines the location in physical memory. Instructions issued by the CPU reference virtual addresses (e.g., pointers, arguments to load/store instructions, the PC). These virtual addresses are translated by hardware into physical addresses (with some setup from the OS). The set of virtual addresses a process can reference is its address space. This is not yet paging or virtual memory—only that the program issues addresses in a virtual address space that must be "adjusted" to reference memory.

🔑 Definition — Virtual Address: An address in a process's logical address space that is independent of the physical memory location where the data is stored.

Memory Hierarchy

The memory hierarchy is based on two principles: the smaller the amount of memory needed, the faster that memory can be accessed; and the larger the amount of memory, the cheaper per byte. This works because programs exploit locality. Temporal locality means a program will reference the same locations as accessed in the recent past. Spatial locality means a program will reference locations near those accessed in the recent past.

🔑 Definition — Temporal Locality: The tendency of a processor to access the same memory locations repeatedly over a short period of time. 🔑 Definition — Spatial Locality: The tendency of a processor to access memory locations that are near previously accessed locations.

Old technique #1: Fixed partitions

In this technique, physical memory is broken up into fixed partitions. Partitions may have different sizes, but the partitioning never changes. The hardware requirement is a base register and a limit register. The physical address is calculated as physical address = virtual address + base register. Base register is loaded by the OS when it switches to a process. Protection is provided by checking if the physical address exceeds the limit register's value. The main advantage is simplicity. However, it suffers from internal fragmentation (the available partition is larger than what was requested) and external fragmentation (two small partitions are left, but one big job cannot fit).

🔑 Definition — Base Register: A hardware register that holds the starting physical address of a process's memory partition. 🔑 Definition — Limit Register: A hardware register that holds the size of a process's memory partition, used for protection. 🔑 Definition — Internal Fragmentation: Wasted memory space within a allocated partition because the partition is larger than the process needs.

Old technique #2: Variable partitions

The next step is to break up physical memory into partitions dynamically, tailoring partitions to programs. The hardware requirements are still a base register and a limit register. The physical address is calculated as physical address = virtual address + base register. Protection is again provided by comparing against the limit register. The advantage is no internal fragmentation, as the partition size is exactly what the process needs. The main problem is external fragmentation: as jobs are loaded and unloaded, holes are left scattered throughout physical memory.

🔑 Definition — External Fragmentation: Wasted memory space between allocated partitions, where the total free memory is sufficient but not contiguous.

Dealing with fragmentation

One method to deal with fragmentation is to swap a program out, then reload it adjacent to another process, and adjust its base register.

⭐ Key Takeaways

The three core questions of memory management are protection, relocation, and partitioning. While modern systems use virtual memory, historical techniques like fixed and variable partitioning illustrate fundamental trade-offs: fixed partitions are simple but cause internal fragmentation, while variable partitions eliminate internal fragmentation but cause external fragmentation. The base and limit registers are a simple hardware mechanism for relocation and protection. Multiprogramming requires memory management to prevent processes from interfering with each other, achieved initially through linker-loaders and swapping. The memory hierarchy exploits locality to balance speed and cost.

🧠 Quick Revision Questions

1. What are the three main questions that memory management must answer?
2. What is the difference between internal fragmentation and external fragmentation?
3. How do base and limit registers provide both relocation and protection in a fixed partition system?
4. What is the role of a linker-loader in a multiprogramming system without hardware address translation?
5. Explain the difference between temporal and spatial locality in the context of the memory hierarchy.

📘 Lecture 24 — Paging

📖 Overview: This lecture introduces paging as a modern memory management technique that solves external fragmentation by using fixed-sized units. It covers address translation mechanics, page table structures, page fault handling, and multi-level page tables, explaining how virtual addresses are mapped to physical memory frames.

🗂️ Topics Covered

The lecture covers paging as a technique to solve external fragmentation, the user's perspective of virtual address space and virtual-to-physical mapping, address translation mechanics including VPN and PFN, page table structures and page table entries with their control bits, paging advantages and disadvantages including internal fragmentation, page faults and their handling via OS exception handlers, and multi-level page tables as a solution to large page table memory requirements.

📝 Lecture Summary

Modern technique: Paging

Paging solves the external fragmentation problem by using fixed sized units in both physical and virtual memory. External fragmentation occurs when free gaps exist between allocated memory chunks, unlike internal fragmentation where free gaps exist because the process doesn't need all of an allocated chunk.

🔑 Definition — Paging: A memory management scheme that divides both virtual and physical memory into fixed-size blocks called pages (virtual) and frames (physical).

User’s perspective

Processes view memory as a contiguous address space from bytes 0 through N, called the virtual address space (VAS). In reality, virtual pages are scattered across physical memory frames — not contiguous. This virtual-to-physical mapping is invisible to the program. Protection is provided because a program cannot reference memory outside of its VAS; the virtual address 0x356AF maps to different physical addresses for different processes. For now, assume all pages of the address space are resident in memory — no "page faults."

Address translation

Translating virtual addresses requires two parts: virtual page number (VPN) and offset. The VPN is an index into a page table, and the page table entry contains a page frame number (PFN). The physical address is PFN concatenated with offset.

🔑 Definition — Page table: A data structure managed by the OS that maps virtual page numbers (VPN) to page frame numbers (PFN). VPN is simply an index into the page table.

📐 Formula: Physical Address = PFN::offset (concatenation of page frame number and offset)

📌 Example: Assume 32-bit addresses with 4KB page size (4096 bytes, 2^12 bytes). VPN is 20 bits long (2^20 VPNs), offset is 12 bits long. Translate virtual address 0x13325328: VPN is 0x13325, offset is 0x328. Assume page table entry 0x13325 contains value 0x03004 (PFN = 0x03004). Physical address = PFN::offset = 0x03004328.

Page Table Entries (PTEs)

PTEs control mapping with specific bits: the valid bit says whether the PTE can be used and checks if a virtual address is valid; the referenced bit says whether the page has been accessed (set when read or written); the modified bit says whether the page is dirty (set when a write occurs); the protection bits control allowed operations (read, write, execute); and the page frame number determines the physical page start address.

🔑 Definition — Valid bit: A bit in PTE indicating whether the virtual address is valid and can be used.

🔑 Definition — Modified bit: A bit in PTE indicating whether the page has been written to (dirty).

💡 Why this matters: These control bits allow the OS to implement virtual memory, enforce protection, and track page usage for swapping decisions.

Paging advantages

Physical memory is easy to allocate from a free list of frames — to allocate a frame, just remove it from the free list. External fragmentation is not a problem because managing variable-sized allocations is complex. Paging leads naturally to virtual memory where the entire program need not be memory resident, using page faults with the "valid" bit. However, paging was originally introduced to deal with external fragmentation, not to allow programs to be partially resident.

Paging disadvantages

Internal fragmentation can still occur — a process may not use memory in exact multiples of pages. There is a memory reference overhead of 2 references per address lookup (page table, then memory). The solution is using a hardware cache called translation lookaside buffer (TLB) to absorb page table lookups. Memory required to hold page tables can be large — need one PTE per page in virtual address space. A 32-bit address space with 4KB pages requires 2^20 PTEs = 1,048,576 PTEs, with 4 bytes/PTE = 4MB per page table. OS typically has separate page tables per process — 25 processes = 100MB of page tables. Solution: page the page tables.

📐 Formula: Page table size = (Address space size / Page size) × PTE size

📌 Example: For 32-bit AS with 4KB pages and 4-byte PTE: (2^32 / 2^12) × 4 = 2^20 × 4 = 4MB per page table.

Page Faults (like “Cache Misses”)

What if an object is on disk rather than in memory? The page table entry indicates the virtual address is not in memory. An OS exception handler is invoked to move data from disk into memory — the current process suspends while others can resume, and the OS has full control over placement.

Servicing a page fault involves:

1. Processor signals controller to read block of length P starting at disk address X, storing at memory address Y
2. Read occurs via Direct Memory Access (DMA) under I/O controller control
3. I/O controller signals completion via interrupt, OS resumes suspended process

🔑 Definition — Page fault: An interrupt that occurs when a program attempts to access a memory page that is not currently in physical memory, requiring the OS to load it from disk.

🔑 Definition — DMA (Direct Memory Access): A method that allows I/O controllers to transfer data directly between disk and memory without CPU intervention.

📌 Example: Suppose page size is 4 bytes. A small page size means lots of space taken up with page table entries (like VAX had 512-byte pages). A large page size wastes unused space inside the page (internal fragmentation).

Multi-Level Page Tables

Given 4KB page size, 32-bit address space, and 4-byte PTE, we would need a 4MB page table (2^20 × 4 bytes). The common solution is multi-level page tables, e.g., a 2-level table. Level 1 table has 1024 entries, each pointing to a Level 2 page table. Level 2 table has 1024 entries, each pointing to a physical page.

🔑 Definition — Multi-level page table: A hierarchical page table structure where the virtual address is divided into multiple indices, with outer levels pointing to inner level tables, reducing memory usage for sparse address spaces.

📌 Example: With 4K pages (12-bit offset), 4 bytes/PTE, and master page table fitting in one page (4K/4 bytes = 1K entries), we have 1K secondary page tables. The virtual address has three parts: Master page number, Secondary page number, and Offset.

Addressing Page Tables

Page tables can be stored in physical memory (easy to address, no translation required, but allocated page tables consume memory for lifetime of VAS) or in virtual memory (OS virtual address space) — cold page table pages can be paged out to disk, but addressing page tables requires translation. To stop recursion, do not page the outer page table (called wiring). If we're going to page the page tables, we might as well page the entire OS address space, but we need to wire special code and data (fault, interrupt handler).

🔑 Definition — Wiring: The process of marking certain pages (like outer page tables and interrupt handlers) as non-pageable, ensuring they remain in physical memory.

💡 Why this matters: Wiring prevents infinite recursion when the OS tries to handle a page fault but the page table itself is paged out.

⭐ Key Takeaways

Paging solves external fragmentation by using fixed-size pages and frames, with the OS maintaining page tables to map virtual page numbers to physical frame numbers. Address translation requires splitting virtual addresses into VPN and offset, with page table entries containing control bits (valid, referenced, modified, protection) for memory management and protection. Page faults occur when accessed pages are not in memory, requiring the OS to load them from disk while suspending the process. Multi-level page tables reduce memory overhead by using hierarchical structures, where outer level tables point to inner tables, and wiring prevents recursive page faults when paging the page tables.

🧠 Quick Revision Questions

1. What are the two main parts of a virtual address in paging, and how is the physical address constructed from them?
2. List and explain the five control bits found in a typical page table entry (PTE).
3. What is internal fragmentation, and why does paging still suffer from it despite solving external fragmentation?
4. Explain the three steps involved in servicing a page fault, including the role of DMA.
5. Why are multi-level page tables needed, and how do they reduce memory overhead compared to a single-level page table?

📘 Lecture 25 — Overview of today’s lecture

📖 Overview: This lecture introduces segmentation as an alternative memory management technique that partitions address spaces into logical units. It then explores the combination of segmentation and paging, the challenges of efficient address translation, and the critical role of the Translation Lookaside Buffer (TLB) in speeding up virtual-to-physical address lookups.

🗂️ Topics Covered

The lecture covers segmentation as a logical partitioning method, contrasts it with paging, and discusses its hardware support, pros, and cons. It then explains the combination of segmentation and paging, including the translation process and its advantages and disadvantages. The lecture concludes with a discussion on efficient translations, caching principles, and the detailed operation of the Translation Lookaside Buffer (TLB), including different mapping schemes.

📝 Lecture Summary

Segmentation

• Paging mitigates various memory allocation complexities (e.g., fragmentation) by viewing an address space as a linear array of bytes, dividing it into pages of equal size (e.g., 4KB), and using a page table to map virtual pages to physical page frames.
• Segmentation partitions an address space into logical units such as stack, code, heap, subroutines. A virtual address is structured as <segment #, offset>.

What’s the point?

• More “logical”: Without segmentation, a linker takes independent modules and organizes them. Segmentation treats them as truly independent.
• Facilitates sharing and reuse: A segment (e.g., a subroutine) is a natural unit for sharing.
• A natural extension of variable-sized partitions: A variable-sized partition is 1 segment per process; segmentation allows many segments per process.

Hardware support

• A segment table holds multiple base/limit pairs, one per segment. Segments are named by a segment number, which is used as an index into the table. The offset of a virtual address is added to the base address of the segment to yield the physical address.

Segmentation pros & cons

• Pros: + Efficient for sparse address spaces. + Easy to share whole segments (e.g., code segment). + Protection modes can be added (e.g., code segment as read-only).
• Cons: 1. Complex memory allocation (still needs first fit, best fit, etc., and reshuffling to coalesce free fragments).
• Linux Example: 1 kernel code segment, 1 kernel data segment, 1 user code segment, 1 user data segment, N task state segments, 1 local descriptor table segment. All of these segments are paged.

Segmentation and Paging

• Can combine segmentation and paging. The x86 supports both.
• Use segments to manage logically related units (module, procedure, stack). Segments vary in size but are usually large (multiple pages).
• Use pages to partition segments into fixed-size chunks. This makes segments easier to manage (“pageable”)—move page portions instead of whole segments. Only need to allocate page table entries for pieces of segments that have been allocated. Tends to be complex.

Segmentation with paging translation

• The translation process involves using the segment table to get a base address for a page directory, then using the page directory and page table to find the physical page frame.

Segmentation with paging translation Pros & Cons

• Pros: + Only need to allocate as many page table entries as needed (sparse address spaces are easy). + Easy memory allocation. + Share at segment or page level.
• Cons: - Pointer per page (typically 4KB-16KB pages today). - Page tables need to be contiguous. - Two lookups per memory reference (plus the segment lookup, making it more).

Efficient Translations

• The original page table scheme already doubles the cost of memory lookups (one lookup into the page table, another to fetch the data).
• Two-level page tables triple the cost (two lookups into page tables, a third to fetch the data), assuming the page table is in memory.
• How to use paging with lookups costing about the same as fetching from memory? 1. Cache translation in hardware. 2. Translation Lookaside Buffer (TLB). 3. TLB managed by Memory Management Unit (MMU).

Integrating VM and Cache

• Most Caches are “Physically Addressed”: Accessed by physical addresses. This allows multiple processes to have blocks in cache at the same time and share pages. The cache does not need to be concerned with protection issues (access rights are checked as part of address translation).
• Perform Address Translation Before Cache Lookup: This could involve a memory access itself (of the PTE). Page table entries can also become cached.

Caching review

• A cache is a copy that can be accessed more quickly than the original. The idea is to make the frequent case efficient. Caching underlies many techniques (translations, memory locations, pages, file blocks, etc.).
• Generic Issues in Caching:
  • Cache hit: Item is in the cache.
  • Cache miss: Item is not in the cache; full operation is needed.
  • Effective access time = P(hit) * cost of hit + P(miss) * cost of miss.
  • Key questions: How to find if an item is in the cache (hit)? How to choose what to replace on a miss (replacement policy)? How to keep the cache copy consistent with the real version (consistency)?

Speeding up Translation with a TLB

• “Translation Lookaside Buffer” (TLB): A small hardware cache in the MMU. It maps virtual page numbers to physical page numbers and contains complete page table entries for a small number of pages.
• The TLB is a hardware table of frequently used translations, avoiding the page table lookup in the common case. Typically on-chip, with an access time of 2-5ns (vs. 30-100ns for main memory).

How do we tell if needed translation is in TLB?

1. Sequential order: Search the table sequentially.
2. Direct mapped: Restrict each virtual page to use a specific slot in the TLB. For example, use upper bits of the virtual page number to index the TLB, then compare against lower bits to check for a match. A problem arises if two pages (e.g., program counter and stack) conflict for the same slot. This requires picking a hash function to minimize conflicts (e.g., using a selection of high-order and low-order bits as the index).
3. Set associativity: Arrange the TLB (or cache) as N separate banks and do a simultaneous lookup in each bank. This is called an "N-way set associative cache". More set associativity reduces the chance of thrashing, as translations can be stored in either bank.
4. Fully associative: A translation can be stored anywhere in the TLB, so all entries are checked in parallel.

🔑 Definition — Translation Lookaside Buffer (TLB): A small, fast hardware cache in the MMU that stores recent virtual-to-physical address translations to speed up memory access.

🔑 Definition — Direct Mapped TLB: A TLB structure where each virtual page number can only map to one specific slot in the TLB, determined by a hash of its address bits.

🔑 Definition — N-way Set Associative TLB: A TLB organized into N banks, where a virtual page can be stored in any one of the N banks indexed by a subset of its address bits, allowing simultaneous lookups.

📌 Example: Direct mapped TLB conflict: If the program counter (PC) and stack pointer (SP) access different virtual pages that map to the same TLB slot (due to a simple indexing scheme), accessing them alternately will cause a TLB miss every time, resulting in thrashing. A better hash function (e.g., mixing high and low bits) can reduce this. A 2-way set associative TLB would allow both translations to be stored simultaneously in the two banks.

💡 Why this matters: The TLB is a crucial performance feature in modern operating systems and CPUs. Without it, every memory access would require multiple slow memory references for page table lookups, dramatically reducing performance. The design of the TLB (direct mapped, set associative, fully associative) is a trade-off between hardware complexity, speed, and the likelihood of translation misses (thrashing).

⭐ Key Takeaways

Segmentation provides a more logical view of memory by partitioning it into units like code and stack, facilitating sharing and protection, though it suffers from complex allocation. Combining segmentation with paging leverages the benefits of both, allowing easy management of large logical units while handling them with small, fixed-size pages in physical memory, though this increases translation overhead. To mitigate the performance cost of multi-level address translation, the TLB caches recent page table entries in the MMU. The design of the TLB—whether direct-mapped, set-associative, or fully associative—is a critical trade-off between hardware cost and the likelihood of translation misses, which directly impacts system performance.

🧠 Quick Revision Questions

1. How does a virtual address differ structurally between a pure paging system and a segmentation system?
2. What are two key advantages of combining segmentation with paging?
3. What is the primary purpose of the Translation Lookaside Buffer (TLB)?
4. Explain the difference between a "direct-mapped" TLB and a "fully associative" TLB in terms of where a translation can be stored.
5. What is the main problem with a direct-mapped TLB when two frequently used pages map to the same slot, and how does set associativity solve this?

📘 Lecture 26 — Set Associative and Fully Associative Caches, Demand Paging, Page Replacement Algorithms

📖 Overview: This lecture explores how hardware caches (set associative and fully associative) and software page replacement work together in memory management. It explains the mechanics of demand paging, page fault handling, and various page replacement algorithms, including their trade-offs between performance and complexity. Understanding these concepts is critical for grasping how virtual memory systems balance speed, memory utilization, and fairness.

🗂️ Topics Covered

The lecture begins by contrasting set associative and fully associative caches, discussing TLB design and replacement policies. It then covers TLB consistency with page tables during context switches and page table entry (PTE) fields. The discussion shifts to paged virtual memory, demand paging, page faults, and program loading. Finally, it details page replacement algorithms: Belady's optimal, FIFO, LRU, approximate LRU, and the Clock (NRU) algorithm, including global vs. local replacement strategies.

📝 Lecture Summary

Set associative cache

A set associative cache is a compromise between direct-mapped and fully associative caches. It divides cache into sets, where each set contains multiple "ways" (cache lines). An address maps to a specific set, but can occupy any way within that set, requiring fewer comparators than fully associative designs.

💡 Why this matters: Set associativity reduces conflict misses compared to direct mapping while keeping hardware complexity manageable.

Fully associative TLB

A fully associative cache has one element per bank with one comparator per bank, allowing any memory address to be stored in any cache line. TLBs (Translation Lookaside Buffers) are typically small and fully associative, while larger hardware caches use direct-mapped or low-degree set associative designs.

• For replacement in set associative or fully associative caches, hardware often chooses randomly (simple and fast), while software page replacement uses more sophisticated algorithms.
• Tradeoff: Spend CPU cycles on smarter replacement to improve cache hit rate.

Consistency between TLB and page tables

• On context switch, the entire TLB must be invalidated because the new program will bring in new translations.
• When translation tables change (e.g., page moved between memory and disk), the corresponding TLB entry must be invalidated.
• Basic mechanism using TLB "present" (valid) bit:
  1. If present: pointer to page frame in memory
  2. If not present: use page table in memory
  3. Hardware traps to OS on reference not in TLB
  4. OS loads page table entry into TLB and continues thread
• All of this is transparent to the job.

Reminder: Page Table Entries (PTEs)

• Valid bit: Says whether the PTE can be used; checked each time a virtual address is used
• Referenced bit: Says whether the page has been accessed; set when a page is read or written
• Modified bit (dirty bit): Says whether the page is dirty; set when a write occurs
• Protection bits: Control which operations are allowed (read, write, execute)
• Page Frame Number (PFN): Determines the physical page; physical page start address = PFN

Paged virtual memory

The full (used) address space exists on secondary storage (disk) in page-sized blocks. The OS uses main memory as a (page) cache. When a page is needed, it is transferred to a free page frame. If no free frames exist, a page must be evicted (evicted pages go to disk only if dirty). All of this is transparent to the application, managed by hardware and OS. This is traditionally called paged virtual memory.

Page faults

When a process references a virtual address in a page that has been evicted:

• When the page was evicted, the OS set the PTE as invalid and stored the disk location in a data structure (like a page table but holding disk addresses)
• When the process accesses the page, the invalid PTE causes an exception (page fault/interrupt)
• The OS runs the page fault handler:
  • Uses the "like a page table" data structure to locate the page on disk
  • Reads the page into a physical frame, updates PTE to point to it and sets it valid
  • OS restarts the faulting process

Demand paging

Demand paging means pages are only brought into main memory when they are referenced. Only the code/data that is needed (demanded) by a process needs to be loaded. Few systems try to anticipate future needs (OS "crystal ball module" is notoriously ineffective). However, clustering is common: the OS keeps track of pages that should come and go together, bringing them all in when one is referenced.

How do you "load" a program?

1. Create process descriptor (process control block)
2. Create page table
3. Put address space image on disk in page-sized chunks
4. Build page table (pointed to by process descriptor):
   • All PTE valid bits set to false
   • An analogous data structure indicates the disk location of the corresponding page
5. When process starts executing:
   • Instructions immediately fault on both code and data pages
   • Faults taper off as necessary code/data pages enter memory

Page replacement

When reading in a page:

• If there are free page frames, grab one
• If not, must evict something else (this is page replacement)

Page replacement algorithms:

• Try to pick a page that won't be needed in the near future
• Try to pick a page that hasn't been modified (saving disk write)
• OS typically keeps a pool of free pages to avoid inevitable evictions
• OS also keeps some "clean" pages around so evictions don't require writes (accomplished by pre-writing when idle)

How does it all work? Locality!

• Temporal locality: Locations referenced recently tend to be referenced again soon
• Spatial locality: Locations near recently referenced locations are likely to be referenced soon

Locality means paging can be infrequent — once paged in, something will be used many times. However, this depends on: degree of locality in the application, page replacement policy and reference pattern, and amount of physical memory vs. application "footprint" or "working set".

Evicting the best page

Goal: Reduce fault rate by selecting the best victim page. The best page to evict is one that will never be touched again (impossible to predict). Belady's proof: evicting the page that won't be used for the longest period of time minimizes page fault rate.

#1: Belady's Algorithm

🔑 Definition — Belady's Algorithm (OPT): The optimal page replacement algorithm that evicts the page that will not be used for the longest time in the future.

📐 Formula: Evict page with maximum "next use time" → minimizes page fault rate

• Provably optimal: lowest fault rate
• Problem: Impossible to predict the future
• Why useful: As a yardstick to compare other algorithms against optimal performance
• No best practical algorithm exists — depends on workload
• Random replacement does pretty badly, though some OS situations use near-random effectively

#2: FIFO (First-In, First-Out)

🔑 Definition — FIFO: Page replacement algorithm that evicts the page that was brought in longest ago.

• Simple to implement: when paging in, put on tail of list; evict from head
• Good: Maybe the oldest page is not being used
• Bad: Have absolutely no information either way
• Performance is typically not good
• Belady's Anomaly: There exist reference strings where the fault rate increases when the process is given more physical memory

#3: Least Recently Used (LRU)

🔑 Definition — LRU (Least Recently Used): Page replacement algorithm that evicts the page that hasn't been used for the longest period of time (past experience as predictor of future behavior).

• Works exceedingly well in general
• Difference from FIFO: LRU looks at past usage (recentness), FIFO looks at arrival time

📌 Example with reference string: A B C A B D A D B C B (On replacement decisions, LRU would evict the page whose most recent use was furthest in the past)

Implementing LRU

• With time stamps: On every memory reference, time stamp each page; at eviction, scan for oldest
• With stack: Keep a stack of page numbers; on every reference, move the page to top of stack
• Problems: Large page lists, no hardware support for time stamps

Approximating LRU (using PTE reference bit)

Keep a counter for each page. At regular intervals, for each page:

• If ref bit = 0, increment counter (hasn't been used)
• If ref bit = 1, zero counter (has been used)
• Regardless, zero ref bit

The counter contains the number of intervals since the last reference. Page with largest counter is least recently used.

#4: LRU Clock (Not Recently Used / Second Chance)

🔑 Definition — Clock Algorithm (NRU/Second Chance): A page replacement algorithm that arranges physical page frames in a circular list (clock) and uses a "clock hand" to sweep through pages, evicting those with reference bit off.

• Algorithm:
  1. Sweep through pages in circular order
  2. If ref bit is off → victim (hasn't been used recently)
  3. If ref bit is on → turn it off and go to next page
• Arm moves quickly when pages needed; low overhead with plenty of memory
• With large memory, accuracy degrades (add more hands to fix)

Problem with large memory: Solution is to add another clock hand — leading edge clears ref bits, trailing edge (N pages back) evicts pages with ref bit 0.

• Angle too small? Angle too large?

Nth Chance Algorithm

Don't throw page out until the hand has swept by N times. OS keeps a counter per page (number of sweeps). On page fault:

• Reference bit = 1 → clear reference bit, clear counter, go on
• Reference bit = 0 → increment counter; if < N, go on; else replace page

Choosing N: Larger N gives better approximation to LRU; smaller N is more efficient (otherwise may look a long way for free page)

Dirty pages: Take extra overhead to write back to disk when replaced. Common approach:

• Clean pages: N = 1
• Dirty pages: N = 2 (write-back to disk when N=1)

Page replacement: Global or local?

Global replacement: When a process faults and needs a page, take oldest page from the entire system.

• Good: Adaptable memory sharing (e.g., P1 needs 20%, P2 needs 70%)
• Bad: Too adaptable; little protection (what happens to P1 if P2 sequentially reads an array about the size of memory?)

Local replacement: Each process replaces only its own pages.

⭐ Key Takeaways

• Set associative and fully associative caches involve a tradeoff between hardware complexity and miss rate; TLBs are typically fully associative while larger caches use lower associativity. Page replacement algorithms must balance sophistication (for higher hit rates) against speed and hardware support constraints. Demand paging leverages locality to keep memory usage efficient, transparently loading pages only when needed. LRU and its approximations (particularly the Clock algorithm) are the most practical effective policies, while Belady's optimal algorithm serves as an analytical benchmark. Global replacement provides adaptive memory sharing but risks thrashing, motivating local replacement or working set-based approaches.

🧠 Quick Revision Questions

1. What are the key differences between set associative and fully associative caches, and how does this affect TLB design?
2. How does the TLB maintain consistency with page tables during context switches and when page tables change?
3. What happens step-by-step during a page fault, from the hardware exception to the OS handler restarting the process?
4. Why does FIFO suffer from Belady's Anomaly, and how does LRU avoid this problem?
5. How does the Clock (NRU) algorithm approximate LRU, and what modifications (Nth chance, dirty page handling) improve its performance?

📘 Lecture 27 — Overview of today’s lecture

📖 Overview: This lecture addresses critical problems in virtual memory management, particularly when the system runs out of physical memory. It explores page replacement policies (global vs. local), the devastating problem of thrashing, and two key solutions: the working set model and page fault frequency algorithm. Understanding these concepts is essential for designing efficient multitasking operating systems.

🗂️ Topics Covered

The lecture covers page replacement strategies (global vs. per-process), the phenomenon of thrashing and why it exposes the lie of virtual memory, the working set model of program behavior and its implementation, scheduling details including the balance set concept, page fault frequency as a variable-space algorithm, and fault resumption techniques that allow OS emulation and virtualization.

📝 Lecture Summary

Page replacement: Global or local?

So far, we‘ve implicitly assumed memory comes from a single global pool (―Global replacement‖). When process P faults and needs a page, take the oldest page on the entire system. This is good for adaptable memory sharing — for example, if P1 needs 20% of memory and P2 needs 70%, they will be happy. However, it is bad because it is too adaptable and provides little protection. A critical question arises: what happens to P1 if P2 sequentially reads an array about the size of memory? P2 will steal all of P1's pages, causing P1 to thrash.

Per-process page replacement

With per-process page replacement, each process has a separate pool of pages. A page fault in one process can only replace one of that process‘s frames. This isolates the process and therefore relieves interference from other processes. However, it also isolates the process and therefore prevents the process from using other‘s (comparatively) idle resources. Efficient memory usage requires a mechanism for (slowly) changing the allocations to each pool. Key questions arise: What is ―slowly‖? How big a pool? When to migrate?

Thrashing

Thrashing is when the system spends most of its time servicing page faults, leaving little time for doing useful work. This could be because there is enough memory but a bad replacement algorithm (one incompatible with program behavior). Alternatively, it could be that memory is over-committed — too many active processes.

Thrashing: exposing the lie of VM

Thrashing occurs when processes on the system require more memory than it has. Each time one page is brought in, another page, whose contents will soon be referenced, is thrown out. Processes will spend all of their time blocked, waiting for pages to be fetched from disk. I/O devices are at 100% utilization but the system is not getting much useful work done. What we wanted was virtual memory the size of disk with the access time of physical memory. What we have is memory with access time equal to disk access.

Making the best of a bad situation

For a single process thrashing, if the process does not fit or does not reuse memory, the OS can do nothing except contain the damage. For system thrashing, if thrashing arises because of the sum of several processes, the OS must adapt: figure out how much memory each process needs, change scheduling priorities to run processes in groups whose memory needs can be satisfied (shedding load), and if new processes try to start, refuse them (admission control). A careful consideration: this is an example of technical vs social — the OS is not the only way to solve this problem. The solution could simply be to go and buy more memory.

🔑 Definition — Thrashing: a condition where the system spends most of its time servicing page faults and little time doing useful work, often because memory is over-committed.

The working set model of program behavior

The working set of a process is used to model the dynamic locality of its memory usage. The working set is the set of pages the process currently ―needs‖, formally defined by Peter Denning in the 1960‘s. A page is in the working set (WS) only if it was referenced in the last w references. Obviously, the working set (the particular pages) varies over the life of the program, as does the working set size (the number of pages in the WS).

🔑 Definition — Working Set: the set of pages a process currently needs, defined as those pages referenced in the last w memory references.

Working set size

The working set size changes with program locality. During periods of poor locality, more pages are referenced, and within that period of time, the working set size is larger. Intuitively, the working set must be in memory, otherwise you‘ll experience heavy faulting (thrashing). When people ask ―How much memory does Internet Explorer need?‖, really they‘re asking ―what is IE‘s average (or worst case) working set size?‖

Hypothetical Working Set algorithm

The algorithm estimates memory needs for a process. Allow that process to start only if you can allocate it that many page frames. Use a local replacement algorithm (e.g. LRU Clock) to make sure that ―the right pages‖ (the working set) are occupying the process‘s frames. Track each process‘s working set size, and re-allocate page frames among processes dynamically. A key challenge remains: how do we choose w?

How to implement working set?

Associate an idle time with each page frame. Idle time equals the amount of CPU time received by process since last access to the page. If a page‘s idle time is greater than T, the page is not part of the working set. To calculate: scan all resident pages of a process. If the reference bit is on, clear the page‘s idle time and clear the use bit. If the reference bit is off, add the process CPU time (since last scan) to the idle time. In Unix: the scan happens every few seconds, and T is on the order of a minute or more.

Scheduling details: The balance set

If the sum of working sets of all runnable processes fits in memory, scheduling is the same as before. If they do not fit, then refuse to run some and divide into two groups: active (working set loaded) and inactive (working set intentionally not loaded). The balance set is the sum of working sets of all active processes. The long term scheduler keeps moving processes from active to inactive until the balance set is less than memory size. It must also allow inactive processes to become active (if changes too frequently?). As the working set changes, the balance set must be updated.

🔑 Definition — Balance Set: the sum of working sets of all active (currently running) processes.

Some problems

T is magic — what if T is too small? Too large? How did we pick it? Usually by ―try and see‖. Fortunately, systems aren‘t too sensitive. What processes should be in the balance set? Large ones so that they exit faster? Small ones since more can run at once? How do we compute the working set for shared pages?

Working sets of real programs

Typical programs have phases. The concept is a good perspective on system behavior. As an optimization trick, it‘s less important: early systems thrashed a lot, current systems not so much. Have OS designers gotten smarter? No. It‘s the hardware (Moore‘s law): memory is much larger (more available for processes), and less obviously, CPUs are faster so jobs exit quicker, returning memory to the free-list faster. Some apps can eat as much as you give them, but the percentage of them that have ―enough‖ seems to be increasing. This was a very important OS research topic in the 80s-90s, but less so now.

Page Fault Frequency (PFF)

Page Fault Frequency (PFF) is a variable-space algorithm that uses a more ad hoc approach. It attempts to equalize the fault rate among all processes and to have a ―tolerable‖ system-wide fault rate. It monitors the fault rate for each process. If the fault rate is above a given threshold, give it more memory so that it faults less. If the fault rate is below the threshold, take away memory so it should fault more, allowing someone else to fault less.

Fault resumption: lets us lie about many things

Fault handling enables many powerful OS techniques. To emulate reference bits: set page permissions to ―invalid‖. On any access, a fault will occur and the handler marks the page as referenced. To emulate non-existent instructions: give the instruction an illegal opcode. When executed, it will cause an ―illegal instruction‖ fault. The handler checks the opcode: if it's for a fake instruction, execute it; otherwise, kill the process. To run an OS on top of another OS: make the OS into a normal process. When it does something ―privileged‖, the real OS will get woken up with a fault. If the operation is allowed, do it; otherwise, kill. Examples include User-mode Linux and VMware.

💡 Why this matters: Fault resumption is the fundamental mechanism that enables virtualization — allowing one operating system to run inside another, which is the basis for modern cloud computing and server consolidation.

⭐ Key Takeaways

A student must understand the critical difference between global and local page replacement: global is adaptable but provides no protection (P2 can steal all of P1's pages), while local isolates processes but wastes idle memory. Thrashing occurs when total working sets exceed physical memory, causing the system to spend all time on page faults with I/O at 100% but no useful work. The working set model provides a theoretical framework: a page is in the working set if referenced in the last w references, and the process must have its working set in memory to avoid thrashing. The page fault frequency (PFF) algorithm provides a practical alternative by monitoring fault rates and adjusting memory allocation dynamically. Finally, fault resumption is the mechanism that enables reference bit emulation, instruction emulation, and OS virtualization.

🧠 Quick Revision Questions

1. What is the fundamental problem with global page replacement when two processes have significantly different memory needs?
2. Explain why thrashing is described as "exposing the lie of virtual memory" — what does the system actually deliver instead of promised performance?
3. In the working set model, how is "idle time" calculated for a page, and what condition determines that a page is NOT part of the working set?
4. What is the balance set, and how does the long-term scheduler manage it when the sum of working sets exceeds physical memory?
5. How does the Page Fault Frequency (PFF) algorithm decide whether to give a process more memory or take memory away?

📘 Lecture 28 — Page Fault Frequency (PFF)

📖 Overview: This lecture examines Page Fault Frequency (PFF) as a variable-space memory allocation algorithm that monitors and adjusts page fault rates across processes. It also covers critical virtual memory concepts including fault resumption, copy-on-write, shared memory, memory-mapped files, and the Intel P6 memory system architecture.

🗂️ Topics Covered

The lecture covers Page Fault Frequency as a variable-space algorithm that equalizes fault rates among processes, fault resumption enabling emulation of reference bits and non-existent instructions, sharing through private virtual address spaces and shared memory, copy-on-write to defer large copies, memory-mapped files for file I/O using loads and stores, the P6 memory system with its TLBs and caches, P6 2-level page table structure, and address translation using the P6 TLB.

📝 Lecture Summary

Page Fault Frequency (PFF)

Page Fault Frequency (PFF) is a variable-space algorithm that uses a more ad hoc approach compared to the Working Set Model. It attempts to equalize the fault rate among all processes and maintain a "tolerable" system-wide fault rate. The algorithm monitors the fault rate for each process: if the fault rate is above a given threshold, the system gives the process more memory so that it faults less; if the fault rate is below threshold, the system takes away memory so the process should fault more, allowing someone else to fault less.

💡 Why this matters: PFF dynamically balances memory allocation based on actual process behavior rather than fixed allocations, improving overall system performance.

Fault Resumption

Fault resumption allows the operating system to "lie about many things" by leveraging the processor's fault handling mechanism. It can emulate reference bits by setting page permissions to "invalid" so that on any access a fault occurs, and the handler marks the page as referenced. It can emulate non-existent instructions by giving an instruction an illegal opcode; when executed, it causes an "illegal instruction" fault, and the handler checks the opcode — if it matches the fake instruction, it performs the operation; otherwise, it kills the process. Fault resumption also enables running an OS on top of another OS by making the OS into a normal process; when it does something "privileged," the real OS gets woken up with a fault.

🔑 Definition — Fault Resumption: The ability to handle faults (page faults, illegal instruction faults, privilege faults) by intercepting them in a handler that performs the desired operation and then resumes execution, allowing the system to emulate hardware features or virtualize the OS.

Sharing

Private virtual address spaces protect applications from each other, but this makes it difficult to share data (requiring copying). Shared memory allows processes to share data using direct memory references, avoiding the overhead of copying data between address spaces.

Copy on Write

Operating systems spend a significant amount of time copying data. Copy on Write (CoW) defers large copies as long as possible, hoping to avoid them altogether. In this scheme, shared pages are protected as read-only in the child process. This is how fork() is implemented as Unix vfork() — the parent and child share pages until one writes, at which point a copy is made.

🔑 Definition — Copy on Write (CoW): A memory management technique where shared pages are marked read-only; if either process tries to write, a fault occurs, and the system creates a private copy of the page for the writing process.

Mapped Files

Mapped files enable processes to do file I/O using loads and stores instead of the traditional "open, read into buffer, operate on buffer" sequence. The mmap() system call in Unix binds a file to a virtual memory region. Page Table Entries (PTEs) map virtual addresses to physical frames holding file data, so virtual address base + N refers to offset N in the file. Initially, all the pages mapped to the file are invalid.

🔑 Definition — Memory-Mapped Files: A mechanism that maps a file's contents into a process's virtual address space, allowing file I/O through normal memory access instructions.

P6 Memory System

The Intel P6 (Pentium Pro) processor features a 32-bit address space with a 4 KB page size. It has L1, L2, and TLBs that are 4-way set associative. The instruction TLB has 32 entries across 8 sets. The data TLB has 64 entries across 16 sets. The L1 i-cache and d-cache are each 16 KB with 32 B line size and 128 sets. The L2 cache is unified (holds both instructions and data) and ranges from 128 KB to 2 MB.

P6 2-level Page Table Structure

The page directory contains 1024 4-byte page directory entries (PDEs) that point to page tables. Each page table contains 1024 4-byte page table entries (PTEs) that point to physical pages.

Translating with the P6 TLB

The translation process follows these steps: 1) Partition the Virtual Page Number (VPN) into TLB Tag (TLBT) and TLB Index (TLBI). 2) Check if the PTE for the VPN is cached in set TLBI. 3) Yes: then build the physical address from the cached PTE. 4) No: then read the PTE (and PDE if not cached) from memory and build the physical address.

⭐ Key Takeaways

Page Fault Frequency dynamically adjusts per-process memory allocation by monitoring fault rates against thresholds, balancing memory among processes. Fault resumption enables emulation of reference bits and non-existent instructions through careful fault handling. Copy-on-Write defers expensive memory copies by sharing read-only pages until writes occur, which is fundamental to efficient process creation with vfork(). Memory-mapped files allow file I/O through memory loads/stores using mmap(). The Intel P6 uses a 2-level page table (page directory with 1024 entries pointing to page tables, each with 1024 entries) with 4 KB pages, and address translation first checks the set-associative TLBs before walking the page table hierarchy.

🧠 Quick Revision Questions

1. What is the key difference between PFF (variable-space) and the Working Set Model in managing process memory allocation?
2. How does fault resumption enable emulation of non-existent instructions on real hardware?
3. Explain the copy-on-write mechanism: when does the actual copy occur, and how is it triggered?
4. In the P6 2-level page table structure, how many PDEs are in the page directory, and how many PTEs are in each page table?
5. Describe the steps involved in translating a virtual address using the P6 TLB, including what happens on a TLB miss.

📘 Lecture 29 — File Systems

📖 Overview: This lecture covers the implementation of file systems as an abstraction for secondary storage, including file organization, directory structures, and disk layout strategies. It explains how operating systems manage files, directories, and protection mechanisms, and compares different allocation methods like contiguous and linked structures.

🗂️ Topics Covered

The lecture introduces the concept of files and their properties, basic file operations in Unix and NT, file access methods (sequential, direct, record, indexed), multi-level directory hierarchies with path name translation, file protection mechanisms, and disk layout strategies including contiguous allocation, linked structures, and indexed structures. It also covers the DOS file system as a practical example.

📝 Lecture Summary

Files

A file is a collection of data with some properties including contents, size, owner, last read/write time, protection, and others. Files serve as the fundamental unit of storage in operating systems.

Basic operations

The lecture compares basic file operations between Unix and NT (Windows NT) systems:

💡 Why this matters: Understanding the mapping between Unix and NT system calls helps developers write portable code across different operating systems.

File access methods

• Sequential access: read bytes one at a time, in order
• Direct access: random access given a block/byte number
• Record access: file is array of fixed- or variable-sized records
• Indexed access: FS contains an index to a particular field of each record in a file; apps can find a file based on value in that record (similar to DB)

Directories

Most file systems support multi-level directories — naming hierarchies (e.g., /, /usr, /usr/local, /usr/local/bin). Most file systems support the notion of current directory:

• absolute names: fully-qualified starting from root of FS
  • bash$ cd /usr/local
• relative names: specified with respect to current directory
  • bash$ cd /usr/local (absolute)
  • bash$ cd bin (relative, equivalent to cd /usr/local/bin)

Path name translation

When you want to open /one/two/three:

fd = open("/one/two/three", O_RDWR);

File protection

FS must implement some kind of protection system:

• to control who can access a file (user)
• to control how they can access it (e.g., read, write, or exec)

File System Layout

How do file systems use the disk to store files?

• File systems define a block size (e.g., 4kb)
• A "Master Block" determines location of root directory
• A free map determines which blocks are free, allocated

Disk Layout Strategies

1. Contiguous allocation: Like memory — Fast, simplifies directory access, but Inflexible, causes fragmentation, needs compaction
2. Linked structure: Each block points to the next
3. Indexed structure: Uses indirection and hierarchy (e.g., inodes)

Simple mechanism: contiguous allocation

Files are stored as contiguous blocks on disk, similar to how memory is allocated contiguously in early systems.

Linked files

• pro: easy dynamic growth & sequential access, no fragmentation
• con: slow random access (must traverse linked list)
• Examples (sort-of): Alto, TOPS-10, DOS FAT

Example: DOS FS (simplified)

The DOS file system uses a FAT (File Allocation Table) which is essentially a linked allocation scheme stored in a table. The directory entry points to the first block, and the FAT contains pointers to subsequent blocks in the chain.

⭐ Key Takeaways

File systems provide abstractions for secondary storage through files with defined properties and operations. Different operating systems implement similar file operations with different API calls (Unix vs NT). File access methods vary from simple sequential to complex indexed access. Multi-level directories with absolute and relative path names enable hierarchical organization. File protection controls user access and permissions. Disk layout strategies include contiguous allocation (fast but inflexible), linked structures (flexible but poor random access), and indexed structures. The DOS FAT system exemplifies linked allocation with a table-based approach.

🧠 Quick Revision Questions

1. What are the four file access methods described in this lecture?
2. What is the difference between absolute and relative path names?
3. What are the advantages and disadvantages of contiguous allocation?
4. Which file system operations differ between Unix and NT naming conventions?
5. What is the role of the "Master Block" and "free map" in file system layout?

📘 Lecture 30 — Consistency Problem

📖 Overview: This lecture addresses the fundamental challenge of maintaining data persistence in file systems despite system crashes. It explores Unix file system architecture including indexed allocation, i-node structures, and caching strategies, while also covering file linking mechanisms.

🗂️ Topics Covered

The lecture covers the consistency problem in file systems, indexed allocation with Unix's five-part disk structure, i-node format and block pointers (including direct, single, double, and triple indirect pointers), file buffer cache with write-behind and read-ahead techniques, and the creation of hard and soft links for file synonyms.

📝 Lecture Summary

Consistency problem

The Big File System Promise is persistence — it will hold your data until you explicitly delete it, and sometimes even beyond that through backup/restore. What makes this hard is crashes. If your data is in main memory, a crash destroys it. There is a performance tension: we need to cache everything for speed, but if we do, then crash equals lose everything. More fundamentally, interesting operations involve multiple block modifications, but we can only atomically modify a disk a sector at a time.

Indexed Allocation

Indexed allocation requires an index table and supports random access. It brings all pointers together into the index block.

UNIX: All disks are divided into five parts

All Unix disks have five distinct areas:

• Boot block: can boot the system by loading from this block
• Superblock: specifies boundaries of the next three areas, and contains head of freelists of i-nodes and file blocks
• i-node area: contains descriptors (i-nodes) for each file on the disk; all i-nodes are the same size; head of freelist is in the superblock
• File contents area: fixed-size blocks; head of freelist is in the superblock
• Swap area: holds processes that have been swapped out of memory

💡 Why this matters: This five-part structure is foundational to understanding how Unix manages storage and recovers from crashes.

The “block list” portion of the i-node (Unix Version 7)

Each i-node contains 13 block pointers. The first 10 are "direct pointers" (pointers to 512B blocks of file data). Then there are single, double, and triple indirect pointers.

A later version of Bell Labs Unix utilized 12 direct pointers rather than 10. Berkeley Unix went to 1KB block sizes.

🔑 Definition — Maximum file size calculation: For Berkeley Unix with 1KB blocks and 1KB pointers:

• Single indirect: 256 × 1KB = 256KB
• Double indirect: 256 × 256 × 1KB = 64MB
• Triple indirect: 256 × 256 × 256 × 1KB = 17GB

Suppose you went 4KB blocks: 1K × 1K × 1K × 4KB = 4TB

i-node Format

Each i-node contains:

• User number
• Group number
• Protection bits
• Times: file last read, file last written, inode last written
• File code: specifies if the i-node represents a directory, an ordinary user file, or a "special file" (typically an I/O device)
• Size: length of file in bytes
• Block list: locates contents of file (in the file contents area)
• Link count: number of directories referencing this i-node

File Buffer Cache

Applications exhibit significant locality for reading and writing files. The idea is to cache file blocks in memory to capture this locality.

Caching Writes

On a write, some applications assume that data makes it through the buffer cache and onto the disk. Several ways to compensate for this:

• "write-behind"
• Battery backed-up RAM (NVRAM)

Read Ahead

Many file systems implement "read ahead". For sequentially accessed files, this can be a big win — unless blocks for the file are scattered across the disk. File systems try to prevent that during allocation.

Creating synonyms: Hard and soft links

More than one directory entry can refer to a given file. Unix stores a count of pointers ("hard links") to the inode. To make: ln foo bar creates a synonym ('bar') for 'foo'.

Soft links: also point to a file (or directory), but the object can be deleted from underneath it (or never even exist).

⭐ Key Takeaways

The lecture's core message is that file system persistence requires careful handling of crashes through structured storage allocation (the five-part Unix disk layout), while i-nodes with direct and indirect pointers enable efficient random access to files of varying sizes. The file buffer cache with write-behind and read-ahead improves performance but requires NVRAM or other mechanisms to ensure data integrity during crashes. Hard links share the same inode and persist as long as any link exists, while soft links are independent pointers that can become dangling. Understanding the maximum file size calculations (17GB for 1KB blocks, 4TB for 4KB blocks) is critical for system design decisions.

🧠 Quick Revision Questions

1. What are the five parts of a Unix disk and what is the purpose of each?
2. How does the i-node block pointer scheme (10 direct + single/double/triple indirect) allow Unix to support very large files?
3. What is the maximum file size for Berkeley Unix with 1KB block sizes?
4. What is the difference between a hard link and a soft link in Unix file systems?
5. How do write-behind and NVRAM help with the consistency problem when caching writes?

📘 Lecture 31 — Consistency problem

📖 Overview: This lecture addresses the fundamental challenge of maintaining data persistence in file systems despite system crashes. It explores three main approaches to handling crashes, with particular focus on building atomic disk operations from smaller atomic units and the use of state duplication for recovery.

🗂️ Topics Covered

The lecture covers the Big File System Promise of persistence and the problem of crashes, three main approaches to handling consistency (restart, atomic updates, reconstruction), building arbitrary-sized atomic disk operations using the SABRE approach, crash recovery through state duplication, and Unix file system invariants that can be violated by crashes.

📝 Lecture Summary

Consistency problem

The Big File System Promise is persistence — it will hold your data until you explicitly delete it, and sometimes even beyond that through backup/restore. What's hard about this is crashes. If your data is in main memory, a crash destroys it. There's a performance tension: you need to cache everything, but if you do, crash means lose everything. More fundamentally, interesting operations require multiple block modifications, but you can only atomically modify disk a sector at a time.

💡 Why this matters: The basic mismatch between what file systems need to do (update multiple blocks atomically) and what disks provide (single sector atomic writes) creates the core consistency problem.

Three main approaches to handling crashes:

• Solution 1: Throw everything away and start over — Done for most things (e.g., interrupted compiles), but probably not what you want to happen to your email
• Solution 2: Make updates seem indivisible (atomic) — Build arbitrary sized atomic units from smaller atomic ones (e.g., a sector write), similar to how we built critical sections from locks, and locks from atomic instructions
• Solution 3: Reconstruction — Try to fix things after crash (many file systems do this — "fsck"). Usually do changes in stylized way so that if crash happens, can look at entire state and figure out where you left off

Arbitrary-sized atomic disk ops

For disk, construct a pair of operations:

• put(blk, address): writes data in blk on disk at address
• get(address) -> blk: returns blk at given disk address

Such that "put" appears to place data on disk in its entirety or not at all, and "get" returns the latest version. What we have to guard against: a system crash during a call to "put", which results in a partial write.

SABRE atomic disk operations

The SABRE approach uses state duplication — maintaining two copies of state information. The atomic-put operation:

void atomic-put(data)
    version++;         # unique integer
    put(version, V1);
    put(data, D1);
    put(version, V2);
    put(data, D2);

The atomic-get operation:

blk atomic-get()
    V1data := get(V1);
    D1data := get(D1);
    V2data := get(V2);
    D2data := get(D2);
    if(V1 == V2)
        return D1data;
    else
        return D2data;

Does it work?

Assume we have correctly written to disk: { #2, "seat 25", #2, "seat 25" } and want to change seat 25 to seat 31. The system crashes during atomic-put("seat 31"). There are 6 cases depending on where failure occurs:

Two assumptions:

1. Once data written, the disk returns it correctly
2. Disk is in a correct state when atomic-put starts

Recovery

The recovery function uses the duplicated state to restore consistency:

void recover(void) {
    V1data = get(V1);    # following 4 ops same as in a-get
    D1data = get(D1);
    V2data = get(V2);
    D2data = get(D2);
    if (V1data == V2data)
        if(D1data != D2data)
            # if we crash & corrupt D2, will get here again.
            put(D1data, D2);
        else
            # if we crash and corrupt D1, will get back here
            put(D2data, D1);
        # if we crash and corrupt V1, will get back here
        put(V2data, V1);

The power of state duplication

Most approaches to tolerating failure have at their core a similar notion of state duplication:

• Want a reliable tire? Have a spare.
• Want a reliable disk? Keep a tape backup (not in same building).
• Want a reliable server? Have two with identical copies; primary fails? Switch.

Fighting failure

In general, coping with failure consists of first defining a failure model composed of:

• Acceptable failures: E.g., earth destroyed by aliens from Mars — loss of file viewed as unavoidable
• Unacceptable failures: E.g., power outage — lost file not ok

Unix file system invariants

These are properties that must hold in a consistent file system:

• File and directory names are unique
• All free objects are on free list, and free list only holds free objects
• Data blocks have exactly one pointer to them
• Inode's ref count = the number of pointers to it
• All objects are initialized (new file should have no data blocks, just allocated block should contain all zeros)

A crash can violate every one of these invariants.

Unused resources marked as "allocated"

Rule: Never persistently record a pointer to any object still on the free list

The dual of allocation is deallocation. The problem happens there as well. With Truncate:

1. Set pointer to block to 0
2. Put block on free list

If the writes for steps 1 and 2 get reversed, can falsely think something is freed.

Dual rule: Never reuse a resource before persistently nullifying all pointers to it.

⭐ Key Takeaways

The fundamental challenge in file system consistency is that interesting operations require multiple block modifications, but disks only provide atomic writes at the sector level. The SABRE approach solves this through state duplication — maintaining two copies of version numbers and data so that atomic-get can always return a consistent previous or new state regardless of when a crash occurs during atomic-put. Crash recovery leverages this same duplication to restore consistency. Unix file system invariants (unique names, correct free lists, proper reference counts) can all be violated by crashes, so rules about never pointing to freed objects and never reusing resources before nullifying pointers are essential for maintaining consistency.

🧠 Quick Revision Questions

1. What are the three main approaches to handling crashes in file systems?
2. In the SABRE atomic disk operations, why is it necessary to store two copies of the version number and data?
3. When a crash occurs during atomic-put, what determines whether atomic-get returns the old data or the new data?
4. What is the dual rule for deallocation that corresponds to "never persistently record a pointer to any object still on the free list"?
5. What five invariants must a consistent Unix file system maintain, and how can a crash violate them?

📘 Lecture 32 — Reactive: reconstruct freelist on crash

📖 Overview: This lecture focuses on crash recovery and consistency mechanisms in file systems. It covers both reactive approaches (like mark-and-sweep garbage collection) and proactive rules for maintaining file system integrity, along with the detailed process of fsck (file system check).

🗂️ Topics Covered

The lecture covers reactive reconstruction of freelists using mark-and-sweep garbage collection, file deletion with reference count management, issues with bogus reference counts, file creation and growth procedures, conservative file moving techniques, the two fixable cases for file system corruption, fsck reconstruction algorithm, and write ordering with dependencies.

📝 Lecture Summary

Reactive: reconstruct freelist on crash

When a crash occurs, the free list may become corrupted. A reactive approach uses mark-and-sweep garbage collection to reconstruct it. Starting from the root directory, the system recursively traverses all live objects and removes them from the free list.

🔑 Definition — Mark and sweep: A garbage collection algorithm that marks all live objects by traversing from known roots, then sweeps by reclaiming unmarked objects.

📌 Example: If the free list incorrectly marks an allocated inode as free, the mark-and-sweep traversal will discover the inode by following pointers from the root directory and remove it from the free list.

💡 Why this matters: This approach fixes the case where allocated objects are mistakenly marked as free, but it's expensive because it requires traversing all live objects, making reboot slow.

Deleting a file

The unlink operation removes a file by name. The system traverses the current working directory looking for the file name; if not found or permissions are wrong, it returns an error. It then clears the directory entry, decrements the inode's reference count, and if the count reaches zero, frees the inode and all blocks it points to.

📐 Formula: Unlink process → (1) traverse directory, (2) clear entry, (3) decrement refcount, (4) if refcount=0, free inode and blocks

📌 Example: Calling unlink("foo") in a directory that contains entry ("foo", inode 41) with refcount 1 will: clear the entry, set refcount to 0, then free inode 41 and all its data blocks.

Bogus reference count

A reference count too high means the inode and its blocks will never be reclaimed (e.g., a 2GB file becomes permanently allocated). A reference count too low is dangerous because blocks will be marked free while still in use, creating a major security hole (e.g., password file stored in "freed" blocks).

🔑 Definition — Reference count: A counter indicating how many directory entries point to a given inode.

📌 Example: If reference count for an open file is 2 but should be 1, the file remains allocated after unlink, wasting space. If count is 0 when it should be 1, blocks may be reallocated while the file still uses them.

The proactive solution: Never decrement reference counter before removing the pointer to an object. Do synchronous writes. The reactive solution: Fix with mark and sweep.

Creating a new file

The golden rule: never (persistently) point to a resource before it has been initialized. This means file creation requires 2 or 3 synchronous writes.

📌 Example: Creating a file requires: Write 1 — write out the modified free list to disk and wait; Write 2 — write out zeros to initialize the inode and wait; Write 3 — write out directory block containing pointer to the inode.

Growing a file

The write(fd, &c, 1) operation translates current file position (byte offset) into location in inode (or indirect block). If the inode already points to a block, modify and write back. Otherwise: allocate a free block, write modified free list to disk and wait, write the newly allocated block to disk and wait, write the pointer (inode) to the new block to disk and wait.

📌 Example: Appending 1 byte to a 4096-byte file (block size 4096) where the file currently has one full block: allocate block #500, write free list (block #500 removed), write byte to block #500, update inode to point to block #500 — each step requiring synchronous write.

Conservatively moving a file

The rule: never reset an old pointer to an object before a new pointer has been set. Moving foo to bar (where foo → inode #41) requires: increment inode 41's reference count and write inode to disk; insert ("bar", inode 41) and write bar's directory block; destroy ("foo", inode 41) and write foo's directory block; decrement inode 41's reference count and write inode to disk.

📌 Example: mv foo bar where foo points to inode 41 with refcount 1: After step 0, refcount=2; after step 2, refcount=2 with two directory entries; after step 3, refcount=1 with only "bar" pointing to inode 41. Cost: 3 synchronous writes.

Summary: the two fixable cases

Case 1: Free list holds pointer to allocated block. Cause: crash during allocation or deallocation. Rule: make free list conservative — free by nullifying pointer before putting on free list; allocate by removing from free list before adding pointer.

Case 2: Wrong reference count. Too high = lost memory (safe); Too low = reuse object still in use (very unsafe). Cause: crash while forming or removing a link. Rule: conservatively set reference count to be high — unlink by nullifying pointer before reference count decrement; link by incrementing reference count before adding pointer.

Alternative: Ignore all rules and fix on reboot using fsck.

FSCK: Reconstructing File System

The fsck algorithm performs mark and sweep and fixes reference counts. It maintains a worklist starting from the root directory, traverses all reachable objects, marks them as allocated, and counts references to each object. After traversal, it compares the actual reference count (seen) with the stored reference count (refs) and fixes any discrepancies.

📐 Algorithm:

worklist := { root directory }
while e := pop(worklist)  # sweep down from roots
    foreach pointer p in e
        if p.type != dataBlock and !seen{p}
            push(worklist, p)
        refs{p} = p.refcnt  # p's notion of pointers to it
        seen{p} += 1  # count references to p
        freelist[p] = ALLOCATED  # mark not free
foreach e in refs  # fix reference counts
    if(seen{e} != refs{e})
        e.refcnt = seen{e}
        e.dirty = true

Write ordering

Synchronous writes are expensive. Solution: have the buffer cache provide ordering support. Whenever block "a" must be written before block "b", insert a dependency. Before writing any block, check for dependencies. To eliminate dependency, synchronously write out each block in chain until done.

📌 Example: If block B and C have no dependencies, they can be written immediately. Block A requires block B to be synchronously written first. This creates a chain: write B, then A, then C.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) File system consistency can be maintained either proactively through careful write ordering and conservative pointer manipulation, or reactively through mark-and-sweep garbage collection and fsck. (2) The two primary fixable corruption cases are incorrect freelist entries and wrong reference counts, each with specific rules to prevent them. (3) Synchronous writes ensure consistency but are expensive, leading to write ordering techniques as an optimization. (4) Reference counts must be incremented before adding pointers and decremented after removing pointers to prevent dangling references or memory leaks. (5) Fsck provides a comprehensive recovery mechanism by traversing the entire file system from roots, fixing both freelist and reference count issues.

🧠 Quick Revision Questions

1. What are the two types of file system corruption cases that are considered "fixable" and what causes each?

2. Why is a reference count that is too low more dangerous than one that is too high?

3. How many synchronous writes are required for creating a new file, and what does each write accomplish?

4. What is the basic algorithm used by fsck to reconstruct a consistent file system state after a crash?

5. How does write ordering with dependencies reduce the cost of maintaining file system consistency compared to synchronous writes?

📘 Lecture 33 — Physical Disk Management

📖 Overview: This lecture covers the physical components and operation of disk drives, disk scheduling algorithms, and the design of the BSD 4.4 Fast File System (FFS). Understanding these topics is essential because disk I/O is a major bottleneck in computer systems, and file system design must account for physical disk characteristics to achieve good performance.

🗂️ Topics Covered

The lecture begins with disk components and how the operating system interacts with disks, including the logical block interface. It then covers important disk operation facts such as sector atomicity and read-modify-write cycles. Disk scheduling algorithms including FCFS, SSTF, SCAN, and C-SCAN are presented. Key trends in disk technology are discussed, followed by a detailed examination of the BSD 4.4 Fast File System (FFS), including cylinder groups, allocation policies, small file representation, clustering, and consistency and recovery mechanisms.

📝 Lecture Summary

Disk Components

A hard disk drive consists of several physical components: platters (rigid circular disks), surfaces (the top and bottom of each platter where data is stored), tracks (concentric circles on each surface), sectors (subdivisions of tracks, the smallest unit of read/write), cylinders (all tracks at the same radial position across all platters), the arm (the mechanical assembly that moves the read/write heads), and heads (the devices that read and write data on the surfaces).

Disk Interaction

Specifying disk requests traditionally required detailed information: cylinder number, surface number, track number, sector number, transfer size, and more. Modern disks, however, use a higher-level interface like SCSI (Small Computer System Interface). In this interface, the disk exports its data as a logical array of blocks numbered [0 ... N]. The disk drive itself handles the mapping from logical block numbers to physical cylinder/surface/track/sector locations.

Some useful facts

Disk drives read and write in units of sectors, not individual bytes. To write a single byte, the disk performs a "read-modify-write" operation: it reads the entire sector containing the byte, modifies that specific byte in memory, then writes the entire sector back to disk. If the sector is already cached in memory, the read step is unnecessary.

The sector is the unit of atomicity for disk writes. A sector write is guaranteed to complete entirely, even if a crash occurs in the middle of the operation (the disk has enough momentum to finish writing the sector). Larger atomic units must be synthesized by the operating system, for example through careful ordering of writes.

💡 Why this matters: These physical characteristics mean that even writing a single byte requires reading and writing an entire sector (typically 512 bytes or 4KB), which has significant performance implications.

Disk Scheduling

Because seeks (moving the disk arm to a different track) are extremely expensive in terms of time (milliseconds), the operating system schedules queued disk requests to minimize seek overhead.

• FCFS (First-Come, First-Served): Processes requests in the order they arrive. This is reasonable when the load is low but leads to long waiting times for long request queues because the arm may move back and forth across the disk randomly.

• SSTF (Shortest Seek Time First): Selects the request with the shortest seek distance from the current arm position. This minimizes arm movement and maximizes request rate, but it can unfairly favor requests for the middle blocks of the disk, potentially causing starvation for outer blocks.

• SCAN (Elevator algorithm): The disk arm moves in one direction, servicing all requests along the way, until it reaches the end of the disk. It then reverses direction and services requests on the way back. This provides fairer service than SSTF.

• C-SCAN (Circular SCAN): Similar to SCAN, but the arm only services requests in one direction (like a typewriter carriage). After reaching one end, it quickly returns to the beginning without servicing requests, then services requests again in the forward direction. This provides more uniform wait times than SCAN.

Some useful trends

Disk bandwidth and cost per bit have been improving exponentially, similar to CPU speed and memory size. However, seek time and rotational delay have been improving very slowly because they require moving physical objects (the disk arm and platters).

Implications of these trends:

• Disk accesses are a huge system bottleneck that is getting worse relative to other components.
• Bandwidth increases allow systems to prefetch large chunks of data for about the same cost as reading a small chunk. Performance improves if related data can be read together.
• Cluster related data together on disk to take advantage of this bandwidth.
• Memory size is increasing faster than typical workload sizes, so more and more of the workload fits in the file cache. This shifts disk traffic toward writes and new data rather than reads of existing data.

BSD 4.4 Fast File system (FFS)

The BSD 4.4 Fast File System (FFS) uses a minimum disk block size of 4096 bytes (4KB). The block size is recorded in the superblock, which is the file system's metadata. Multiple file systems with different block sizes can co-reside on the same disk. FFS improves performance through several mechanisms, and the superblock is replicated across multiple locations to provide fault tolerance.

FFS Cylinder Groups

FFS defines cylinder groups as the unit of disk locality. A typical disk has thousands of cylinders divided into dozens of cylinder groups. The allocation strategy is to place "related" data blocks in the same cylinder group whenever possible, because seek latency is proportional to seek distance.

Specific allocation strategies:

• Large files are "smeared" across multiple cylinder groups, with a run of contiguous blocks placed in each group.
• Inode blocks are reserved in each cylinder group, allowing inodes to be allocated close to their directory entries and close to their data blocks (especially important for small files).

💡 Why this matters: By keeping related data in the same cylinder group, FFS reduces seek distances and improves overall file system performance.

FFS Allocation Policies

1. Allocate file inodes close to their containing directories.

   • For mkdir (creating a directory), select a cylinder group with a more-than-average number of free inodes.
   • For creat (creating a file), place the inode in the same cylinder group as the parent directory.

2. Concentrate related file data blocks in cylinder groups.

   • Most files are read and written sequentially.
   • Place the initial blocks of a file in the same cylinder group as its inode.
   • For directory blocks: place adjacent logical blocks in the same cylinder group.
   • Logical block n+1 goes in the same group as block n.
   • Switch to a different cylinder group for each indirect block (a block that contains pointers to other data blocks).

Representing Small Files

Internal fragmentation (wasted space within a file system block) can waste significant space for small files. FFS solves this problem by allowing blocks to be subdivided into fragments (typically 2, 4, or 8 fragments per block). This reduces wasted space for small files while maintaining the performance benefits of large blocks for large files.

Clustering in FFS

Clustering improves bandwidth utilization for large files that are read and written sequentially. FFS can allocate contiguous runs of blocks "most of the time" on disks that have sufficient free space. By reading these contiguous blocks in a single operation, the system maximizes disk bandwidth.

FFS consistency and recovery

When the system reboots after a crash, FFS reconstructs the free list (list of free blocks) and reference counts (number of directory entries pointing to each inode). The file system enforces two invariants:

1. Directory names always reference valid inodes.
2. No block is claimed by more than one inode.

These invariants are maintained through three ordering rules:

1. Write a newly allocated inode to disk before the entry is added to a directory (otherwise a crash could leave a directory pointing to an invalid inode).
2. Remove the directory name before the inode is deallocated.
3. Write the deallocated inode to disk before its blocks are placed on the free list.

File creation and deletion each require two synchronous writes to disk. The third rule is necessary because otherwise, during inode recovery, a crash could leave the system thinking a deallocated inode still owns blocks that have been placed on the free list.

💡 Why this matters: These ordering rules ensure file system consistency even in the face of crashes, without requiring a full journaling mechanism.

FFS: inode recovery

Files can be lost if the directory containing them is destroyed or if a crash occurs before a directory link can be set. However, FFS can find lost inodes because:

1. FFS pre-allocates inodes in known locations on disk.
2. Free inodes are initialized to all zeros.

Using these facts, the fsck (file system check) utility can:

• Find all inodes (whether or not there are any pointers to them) because they're in known locations.
• Determine that any inode with non-zero contents is probably still in use.
• Place unreferenced inodes (those with no directory entry pointing to them but with non-zero contents) in the lost+found directory, allowing the user to examine and recover them.

⭐ Key Takeaways

The physical disk drive has components including platters, surfaces, tracks, sectors, and cylinders; seeks are the main performance bottleneck. Disk scheduling algorithms like FCFS, SSTF, SCAN, and C-SCAN trade off fairness, throughput, and starvation prevention. Disk bandwidth improves exponentially but seek times improve very slowly, making disks an increasing system bottleneck. The Berkeley Fast File System uses cylinder groups to localize related data, large blocks with fragmentation for small files, clustering for sequential access, and careful ordering rules for crash recovery without journaling. FFS can recover lost files by scanning pre-allocated inode locations and checking for non-zero contents.

🧠 Quick Revision Questions

1. What is the "read-modify-write" operation and why is it necessary for writing a single byte to disk?
2. How does the C-SCAN disk scheduling algorithm differ from the SCAN (elevator) algorithm?
3. What are cylinder groups in FFS, and what is the primary strategy for allocating related data within them?
4. What three ordering rules does FFS use to ensure file system consistency and why is the third rule necessary?
5. How does FFS recover lost inodes after a crash, and where does it place unreferenced inodes with non-zero contents?

📘 Lecture 34 — Log Structured File Systems

📖 Overview: This lecture introduces log-structured (journaling) file systems, which record each update as a transaction to enable fast crash recovery. It covers logging implementation, log management, performance considerations, and then extends the discussion to Linux Virtual File System (VFS) and the Sun Network File System (NFS) architecture.

🗂️ Topics Covered

The lecture begins with log-structured file systems and the concept of logging for crash recovery, including write-ahead logging implementation. It discusses log management through checkpoint operations and the performance issue of two disk writes per change. It then transitions to Linux Virtual File System (VFS) describing its primary objects: superblock, inode, dentry, and file objects. Finally, it covers the Sun Network File System (NFS) architecture and presents a schematic view of NFS.

📝 Lecture Summary

Log Structured File Systems

Log structured (or journaling) file systems record each update to the file system as a transaction. All transactions are written to a log. A transaction is considered committed once it is written to the log. However, the file system may not yet be updated — meaning the log holds the record of pending changes.

💡 Why this matters: This separation allows the system to commit changes quickly to the log (without waiting for the entire file system update) and then apply them later, which improves both performance and reliability during crashes.

🔑 Definition — Write-ahead logging (also called journaling): The practice of always writing changes to the log first, before writing them to the actual file system. All reads go to the file system. If a crash occurs, the system can read the log and correct any inconsistencies in the file system.

Logging

The core idea of logging is: keep track of what operations are in progress and use this for recovery. The system keeps a "log" of all operations. Upon a crash, we can scan through the log and find problem areas that need fixing.

Implementation

Implementation involves adding a log area to disk. The sequence of operations:

1. Always write changes to log first – called write-ahead logging or journaling
2. Then write the changes to the file system
3. All reads go to the file system (not the log)
4. Crash recovery – read log and correct any inconsistencies in the file system

Issue - Log management

Observation: The log is only needed for crash recovery.
Checkpoint operation – make in-memory copy of file system (file cache) consistent with disk. After a checkpoint, can truncate the log and start again. Most logging file systems only log metadata (file descriptors and directories) and not file data to keep log size down.

Issue – Performance

There are two key performance concerns:

• Two disk writes (on different parts of the disk) for every change
• Synchronous writes on every file system change

Observation: Log writes are sequential on disk, so even synchronous writes can be fast. Best performance is achieved if the log is on a separate disk.

Current trend is towards logging FS

Benefits include:

• Fast recovery: recovery time is O(active operations) and not O(disk size)
• Better performance if changes need to be reliable
• Sequential synchronous writes are much faster than non-sequential ones
• Examples: Windows NTFS, Veritas on Sun
• Many competing logging file systems for Linux

Linux Virtual File System

The Linux Virtual File System (VFS) provides a uniform file system interface to user processes. It represents any conceivable file system's general feature and behavior. VFS assumes files are objects that share basic properties regardless of the target file system.

Primary Objects in VFS

The VFS is built around four primary objects:

• Superblock object → Represents a specific mounted file system
• Inode object → Represents a specific file
• Dentry object → Represents a specific directory entry
• File object → Represents an open file associated with a process

The Sun Network File System (NFS)

NFS is an implementation and a specification of a software system for accessing remote files across LANs (or WANs). The implementation is part of the Solaris and SunOS operating systems running on Sun workstations using an unreliable datagram protocol (UDP/IP protocol and Ethernet).

Schematic View of NFS Architecture

The architecture shows how NFS enables remote file access across networks, with clients and servers communicating over a network protocol (UDP/IP over Ethernet).

⭐ Key Takeaways

Log-structured file systems use write-ahead logging to record transactions, allowing fast crash recovery with recovery time proportional to active operations rather than disk size. The log is managed through checkpoint operations that synchronize memory with disk, after which the log can be truncated; most implementations log only metadata to keep log size manageable. Performance benefits come from sequential synchronous writes, especially when the log is on a separate disk, as seen in Windows NTFS and Veritas on Sun. The Linux Virtual File System provides a uniform interface through four object types (superblock, inode, dentry, file) that abstract any file system's features. The Sun NFS extends these concepts to remote file access across networks using UDP/IP over Ethernet.

🧠 Quick Revision Questions

1. What is write-ahead logging and why is it essential for crash recovery in journaling file systems?
2. What is the checkpoint operation and what happens to the log after a checkpoint?
3. Why do most logging file systems only log metadata and not file data?
4. Name the four primary objects in the Linux Virtual File System and state what each represents.
5. What protocol does Sun NFS use for communication across LANs or WANs?

📘 Lecture 35 — Overview of today’s lecture

📖 Overview: This lecture covers the principles and software layers of I/O systems in operating systems. It explains the goals of I/O software, different I/O methods (programmed, interrupt-driven, DMA), and how device controllers work. Understanding these concepts is essential for designing efficient and device-independent operating systems.

🗂️ Topics Covered

The lecture covers the goals of I/O software including device independence, uniform naming, error handling, synchronous vs. asynchronous transfers, and buffering. It then explains device controllers, layers of the I/O system, memory-mapped vs. direct I/O, programmed I/O, interrupt-driven I/O, and direct memory access (DMA). Finally, it demonstrates reading a disk sector step-by-step and printing using DMA.

📝 Lecture Summary

Goals of I/O Software

The goals of I/O software are designed to make I/O operations efficient and easy to use. Device independence means programs can access any I/O device (floppy, hard drive, or CD-ROM) without specifying the device in advance. Uniform naming ensures that the name of a file or device is a string or an integer that does not depend on which machine is used. Error handling should be performed as close to the hardware as possible. Synchronous vs. asynchronous transfers distinguish between blocked transfers and interrupt-driven transfers. Buffering is necessary because data coming off a device cannot be stored in the final destination immediately.

Device Controllers

I/O devices have two main components: a mechanical component and an electronic component. The electronic component is the device controller, which may be able to handle multiple devices. A controller's tasks include converting a serial bit stream to a block of bytes, performing error correction as necessary, and making data available to main memory.

Layers of the I/O system and the main functions of each layer

The I/O system is organized in layers, with each layer having specific functions. The top layer is user-level I/O software, followed by device-independent operating system software, then device drivers, and finally interrupt handlers at the bottom. Each layer provides services to the layer above it and hides implementation details from it.

Memory mapped I/O Vs Direct I/O

Memory mapped I/O means the device controller's registers and internal memory are directly mapped into the processor's address space. In Direct I/O, the device controller's registers and internal memory are accessible via special instructions in the assembly language instruction set. The arguments to these instructions are usually called ports.

Programmed I/O

Programmed I/O (also called polled I/O) involves the CPU directly controlling I/O operations. The CPU continuously checks the device status (polling) until the operation completes. Writing a string to the printer using programmed I/O requires the CPU to output each character one at a time, waiting for the printer to be ready before sending the next character. 📌 Example: Writing a string to the printer using programmed I/O: The CPU loops through each character, writes it to the printer's data register, then waits in a busy loop until the printer signals it is ready for the next character.

Interrupt-Driven I/O

Interrupt-driven I/O improves efficiency over programmed I/O by allowing the CPU to do other work while waiting for I/O operations. When a device completes an operation, it sends an interrupt signal to the CPU. A special interrupt service procedure handles the interrupt and continues the I/O operation. 📌 Example: Writing a string to the printer using interrupt-driven I/O: (a) Code executed when print system call is made initiates the first character transfer and then returns control to the calling program. (b) Interrupt service procedure is called each time the printer finishes printing a character, and this procedure sends the next character.

Reading a Disk Sector: Step 1

The CPU initiates a disk read by writing a command, logical block number, and destination memory address to a port (address) associated with the disk controller.

Reading a Disk Sector: Step 2

The disk controller reads the sector and performs a direct memory access (DMA) transfer into main memory. The DMA controller handles the data transfer directly between the device and memory without CPU intervention.

Reading a Disk Sector: Step 3

When the DMA transfer completes, the disk controller notifies the CPU with an interrupt. The controller asserts a special "interrupt" pin on the CPU to signal completion.

Direct Memory Access (DMA)

Direct Memory Access (DMA) is a hardware mechanism that allows I/O devices to transfer data directly to/from main memory without involving the CPU for each byte. A DMA controller manages the transfer, and the CPU is only involved at the beginning (to set up the transfer) and at the end (to handle the interrupt when transfer completes). 💡 Why this matters: DMA dramatically reduces CPU overhead for large data transfers, allowing the CPU to perform other tasks while data is being moved between devices and memory.

I/O Using DMA

I/O using DMA involves three phases: setup, data transfer, and completion. In the setup phase, the CPU tells the DMA controller the source, destination, and size of the transfer. The DMA controller then performs the data transfer independently. When finished, the DMA controller sends an interrupt to the CPU. 📌 Example: Printing a string using DMA: (a) Code executed when the print system call is made sets up the DMA transfer with the string's memory address and length. (b) Interrupt service procedure is called when the entire string has been printed, notifying the application that the print operation is complete.

⭐ Key Takeaways

The most critical concepts from this lecture are the three main I/O methods (programmed, interrupt-driven, and DMA) and their trade-offs. Programmed I/O is simple but wastes CPU time polling. Interrupt-driven I/O improves efficiency by freeing the CPU during I/O operations. DMA is the most efficient for large transfers as it minimizes CPU involvement. The layers of I/O software provide device independence and uniform naming. Memory-mapped I/O and direct I/O are two different approaches to accessing device controller registers. Error handling should be done as close to the hardware as possible, and buffering is essential when data arrival rate doesn't match consumption rate.

🧠 Quick Revision Questions

1. What are the five goals of I/O software discussed in this lecture?
2. How does programmed I/O (polled I/O) differ from interrupt-driven I/O?
3. What are the three steps involved in reading a disk sector using DMA?
4. What is the difference between memory-mapped I/O and direct I/O (port-mapped I/O)?
5. In the layers of the I/O system, which layer is responsible for handling interrupts from hardware devices?

📘 Lecture 36 — Device Independent I/O, Kernel Subsystem, and I/O Lifecycle

📖 Overview: This lecture examines the layered architecture of operating system I/O, focusing on the device-independent software layer that provides a uniform interface to device drivers. It covers buffering strategies, block versus character versus network devices, the kernel I/O subsystem including scheduling and caching, and walks through the complete lifecycle of I/O and network requests.

🗂️ Topics Covered

The lecture covers device-independent I/O software and its functions including buffering and error reporting; classification of devices into block, character, and network categories; the kernel I/O subsystem components such as scheduling, buffering, caching, spooling, and device reservation; error handling and kernel data structures; performance improvement techniques; and the detailed lifecycle of a typical I/O request and a network I/O request.

📝 Lecture Summary

Device-Independent I/O Software

This layer sits above device drivers and provides a uniform interfacing for all device drivers. It handles buffering, error reporting, allocating and releasing dedicated devices, and providing a device-independent block size.

• Typically interfaces to device drivers through a standard interface
• Offers several buffering options:
  1. Unbuffered input
  2. Buffering in user space
  3. Buffering in the kernel followed by copying to user space
  4. Double buffering in the kernel

💡 Why this matters: The device-independent layer allows programmers to write I/O code that works across many different hardware devices without modification.

Block and Character Devices

Block devices include disk drives:

• Commands include read, write, seek
• Support raw I/O or file-system access
• Memory-mapped file access is possible

Character devices include keyboards, mice, serial ports:

• Commands include get, put
• Libraries layered on top allow line editing

💡 Why this matters: Block devices allow random access to fixed-size data blocks, while character devices deal with streams of bytes; the OS handles them differently.

Network Devices

Network devices are varying enough from block and character to have their own interface. Unix and Windows NT/9i/2000/XP include a socket interface that:

• Separates network protocol from network operation
• Includes select functionality

Approaches vary widely and include pipes, FIFOs, streams, queues, mailboxes.

Clocks and Timers

These provide current time, elapsed time, timer functionality. A programmable interval timer is used for timings and periodic interrupts. The ioctl system call (on UNIX) covers odd aspects of I/O such as clocks and timers.

Blocking and Nonblocking I/O

• Blocking - process suspended until I/O completed, easy to use but insufficient for some needs
• Nonblocking - I/O call returns as much as available, used for user interface and data copy (buffered I/O), implemented via multi-threading inside the kernel, returns quickly with count of bytes read or written
• Asynchronous - process runs while I/O executes, difficult to use, I/O subsystem signals process when I/O completed

Kernel I/O Subsystem

• Scheduling: Some I/O request ordering via per-device queue, some OSs try fairness
• Buffering: Store data in memory while transferring between devices to:
  • Cope with device speed mismatch
  • Cope with device transfer size mismatch
  • Maintain "copy semantics"
• Caching: Fast memory holding copy of data, always just a copy, key to performance
• Spooling: Hold output for a device from multiple sources, used when device can serve only one request at a time (e.g., printing)
• Device reservation: Provides exclusive access to a device, uses system calls for allocation and deallocation, watch out for deadlock

Error Handling

The OS can recover from disk read, device unavailable, and transient write failures. Most return an error number or code when I/O request fails. System error logs hold problem reports.

Kernel Data Structures

The kernel keeps state info for I/O components, including:

• Open file tables
• Network connections
• Character device state

Many complex data structures track buffers, memory allocation, and "dirty" blocks. Some systems use object-oriented methods and message passing to implement I/O.

Unix I/O Kernel Structure

The structure shows a layered architecture: User processes access kernel via system calls, which go through a file system layer, buffer cache, character device layer, device driver, and finally to hardware.

Improving Performance

• Reduce number of context switches
• Reduce data copying
• Reduce interrupts by using large transfers, smart controllers, polling
• Use DMA
• Balance CPU, memory, bus, and I/O performance for highest throughput

Life Cycle of An I/O Request

A typical I/O request goes through:

1. User process makes a system call (e.g., read())
2. Kernel checks parameters, processes request through VFS (Virtual File System)
3. VFS dispatches to appropriate file system or device driver
4. Device driver issues commands to hardware (disk controller, network card, etc.)
5. I/O completes, device generates interrupt
6. Interrupt handler processes completion, wakes waiting process
7. Data transferred (via DMA or programmed I/O) to user buffer
8. System call returns to user process

Inter-computer Communications

This brief section covers how I/O extends to network communications between computers, relying on the socket interface and layered network protocols.

⭐ Key Takeaways

The device-independent I/O software layer provides critical uniformity across different hardware devices by handling buffering, error reporting, and device allocation. Students must understand the distinction between block devices (random access, disks) and character devices (stream-oriented, keyboards/terminals) and how network devices require their own socket-based interface. The kernel I/O subsystem involves scheduling, buffering, caching, spooling, and device reservation—each solving specific performance or correctness problems. Blocking, nonblocking, and asynchronous I/O represent three different models for process-device interaction that affect system design. Finally, the complete lifecycle of an I/O request from system call through VFS, device driver, interrupt handling, and data transfer to the user buffer is essential for understanding how operating systems manage hardware.

🧠 Quick Revision Questions

1. What are the four buffering options provided by the device-independent I/O software layer?
2. Explain the key differences between block devices and character devices, including typical commands for each.
3. What is the difference between blocking, nonblocking, and asynchronous I/O, and when is each appropriate?
4. List the five major components of the kernel I/O subsystem and briefly describe the purpose of each.
5. Trace the lifecycle of a typical disk read request from user system call to data arrival in user space.

📘 Lecture 37 — Overview of today’s lecture

📖 Overview: This lecture examines Linux interrupt handling mechanisms, distinguishing between interrupts and exceptions at the hardware and software levels. It then covers timing and timer devices, including kernel dynamic timers and user-mode interval timers, which are critical for scheduling, timeouts, and system accounting.

🗂️ Topics Covered

The lecture covers interrupt handlers, the distinction between interrupts (maskable/nonmaskable) and exceptions (faults, traps, aborts, programmed exceptions), Linux interrupt handling components (top-half/bottom-half, tasklets), timing hardware (RTC, PIT, TSC, local APIC timer), dynamic kernel timers (timer_list structure), and user-mode interval timers (setitimer() with ITIMER_REAL, VIRT, PROF).

📝 Lecture Summary

Interrupt Handlers

Interrupt handlers are best hidden from normal program flow. The interrupt procedure does its task transparently, allowing the interrupted code to resume unaware of the interruption.

Interrupts vs Exceptions

Terminology varies, but for Intel architecture interrupts and exceptions are distinct. Interrupts are device-generated and come in two types: maskable interrupts associated with IRQs (interrupt request lines) that may be temporarily disabled while remaining pending, and nonmaskable interrupts for some critical hardware failures. Exceptions are processor-detected and include faults (correctable/restartable, e.g., page fault), traps (no reexecution needed, e.g., breakpoint), and aborts (severe error; process usually terminated by signal). Additionally, programmed exceptions (software interrupts) include int (system call), int3 (breakpoint), into (overflow), and bounds (address check).

Interrupts and Exceptions

Hardware support is required for getting the CPU's attention. Interrupts often transfer execution from user mode to kernel mode. Asynchronous interrupts are device or timer generated, while synchronous interrupts are the immediate result of the last instruction executed. Intel terminology and hardware includes: IRQs, vectors, IDT (Interrupt Descriptor Table), gates, PIC (Programmable Interrupt Controller), and APIC (Advanced Programmable Interrupt Controller).

Interrupt Handling

Interrupt handling is more complex than exception handling because it requires registry, deferred processing, and other steps. One key issue is that IRQs are often shared; all handlers (ISRs) are executed, so they must query the device to determine if it generated the interrupt. Three types of actions exist: Critical actions (top-half, interrupts disabled briefly), Non-critical actions (top-half, interrupts enabled), and Non-critical deferrable actions (done "later" with interrupts enabled).

💡 Why this matters: This three-tier separation ensures minimal interrupt latency while allowing non-urgent work to be postponed, which is fundamental to Linux's real-time and throughput performance.

Timing and Timers

Accurate timing is crucial for many OS aspects: Device-related timeouts, file timestamps (created, accessed, written), time-of-day (gettimeofday()), high-precision timers (for code profiling), and scheduling/cpu usage accounting. Intel timer hardware includes: RTC (Real Time Clock), PIT (Programmable Interrupt Timer), TSC (TimeStamp Counter, a cycle counter), and Local APIC Timer (per-CPU alarms). Timer implementations are of two types: kernel timers (dynamic timers) and user "interval" timers (alarm(), setitimer()).

🔑 Definition — Dynamic timers: Timers that may be dynamically created and destroyed with no limit on the number of currently active dynamic timers.

A dynamic timer is stored in the timer_list structure:

struct timer_list {
    struct list_head list;
    unsigned long expires;
    unsigned long data;
    void (*function)(unsigned long);
};

Software timers in Linux

Each timer contains a field indicating how far in the future the timer should expire. This field is initially calculated by adding the right number of ticks to the current value of jiffies. The field does not change after initialization. Every time the kernel checks a timer, it compares the expiration field to the value of jiffies at the current moment, and the timer expires when jiffies is greater than or equal to the stored value.

📐 Formula: expires = jiffies + number_of_ticks → The timer will fire when jiffies >= expires.

📌 Example: If jiffies is currently 1000 and you want a timer to expire in 50 ticks, you set expires = 1000 + 50 = 1050. The kernel checks this field periodically; when jiffies reaches 1050 or greater, the timer's function is called.

User Mode Interval Timers

The setitimer() system call provides 3 distinct user-mode interval timers that can be set for one-time or periodic alarms, sending signals on timer expiry. The three timers are: ITIMER_REAL (elapsed real time, sends SIGALRM), ITIMER_VIRT (user CPU time, sends SIGVTALRM), and ITIMER_PROF (user + kernel CPU time, sends SIGPROF). Implementations differ: VIRT and PROF are updated by PIT or APIC interrupts. REAL requires a kernel timer and may need to deliver to a blocked process, using current->real_timer. The REAL timer is shared by the alarm() API, so you cannot use both simultaneously.

💡 Why this matters: Understanding these timers is essential for writing user programs that need precise timeouts, profiling, or periodic signal delivery, and for understanding how the OS manages time-sharing and resource accounting.

⭐ Key Takeaways

You must remember the fundamental distinction between interrupts (device-generated, asynchronous) and exceptions (processor-detected, synchronous) including their subtypes: maskable/nonmaskable interrupts and faults/traps/aborts. For interrupt handling, recall the three-tier architecture (critical, non-critical, deferrable) and that shared IRQs require all handlers to query devices. For timers, know the four Intel timer hardware types (RTC, PIT, TSC, Local APIC) and that dynamic kernel timers use the timer_list structure with expires, data, and function fields compared against jiffies. Finally, remember the three user-mode interval timers (ITIMER_REAL, ITIMER_VIRT, ITIMER_PROF) and their associated signals, with the key implementation detail that ITIMER_REAL uses current->real_timer shared with alarm().

🧠 Quick Revision Questions

1. What is the difference between a maskable interrupt and a nonmaskable interrupt?
2. Name the three types of processor-detected exceptions and give one example for each.
3. Why must all interrupt handlers in a shared IRQ line execute and query the device?
4. What are the three fields in the timer_list structure, and how does the kernel determine when a dynamic timer expires?
5. Explain the difference between ITIMER_REAL, ITIMER_VIRT, and ITIMER_PROF — which one cannot be used simultaneously with alarm() and why?

📘 Lecture 38 — Loadable Kernel modules and device drivers; Signals and asynchronous event notification

📖 Overview: This lecture covers two major topics. First, it explains the Linux and Solaris loadable kernel module system, including module management, driver registration, and conflict resolution. Second, it provides a comprehensive introduction to signals as an asynchronous event notification mechanism in Unix/Linux, covering their APIs, semantics, and the evolution from old unreliable signals to modern reliable and real-time signals.

🗂️ Topics Covered

The lecture begins with an overview of Loadable Kernel Modules in Linux and Solaris, explaining their purpose and the three core components: module management, driver registration, and conflict resolution. It then transitions to a detailed discussion of Signals, covering them as an early minimal IPC mechanism, their three distinct APIs, basic properties like names and numbers, generation sources, pending signals, system calls, default actions, and a specific comparison between old unreliable signals and modern reliable signals via the sigaction() call.

📝 Lecture Summary

Loadable Kernel Modules (Linux & Solaris)

These are sections of kernel code that can be compiled, loaded, and unloaded independent of the rest of the kernel. A kernel module may typically implement a device driver, a file system, or a networking protocol. The module interface allows third parties to write and distribute device drivers or file systems on their own terms, even if they could not be distributed under the GPL. Kernel modules allow a Linux system to be set up with a standard, minimal kernel, without any extra device drivers built in. There are three components to Linux module support: module management, driver registration, and conflict resolution.

Module Management

This component supports loading modules into memory and letting them talk to the rest of the kernel. Module loading is split into two separate sections: managing sections of module code in kernel memory, and handling symbols that modules are allowed to reference. The module requestor manages loading of requested but currently unloaded modules; it also regularly queries the kernel to see whether a dynamically loaded module is still in use and will unload it when it is no longer actively needed.

Driver Registration

This component allows modules to tell the rest of the kernel that a new driver has become available. The kernel maintains dynamic tables of all known drivers and provides a set of routines to allow drivers to be added to or removed from these tables at any time. Registration tables include the following items: device drivers, file systems, network protocols, and binary format.

Conflict Resolution

This is a mechanism that allows different device drivers to reserve hardware resources and to protect those resources from accidental use by another driver. The conflict resolution module aims to prevent modules from clashing over access to hardware resources, prevent autoprobes from interfering with existing device drivers, and resolve conflicts with multiple drivers trying to access the same hardware.

Signals

Signals are an early minimal IPC (no information) mechanism that functions as an asynchronous event notification system and a software analog of hardware interrupts. There are three distinct APIs: the original (buggy, unreliable) signals with slightly differing semantics between Sys V and BSD, reliable (Posix) signals, and real-time (Posix) signals. Things you can do with signals include: generate (send, raise) using kill(), deliver (receive, handle) during kernel to user transition, block/mask to temporarily disable delivery (but not generation), ignore to throw away on delivery, and catch (handle) to execute a user-supplied handler on delivery.

Signals: Basics

Signals have names (macros) and numbers. Examples include SIGINT (2), SIGKILL (9), and SIGPWR (30). The kill –l command lists platform assignments. Some signals are architecture and processor dependent, such as SIGSTKFLT for coprocessor stack error on Intel. Signals can be generated by users via special shell characters (control-c) or user-level commands (kill -9 1234), by programs via system calls (kill(pid, sig)), or by the kernel (e.g., in response to exceptions). In Linux, regular signals are numbers 1-31 (assigned specific functions), and real-time signals are numbers 32-64 (user assignable).

Pending signals are generated but not delivered, and they may be blocked or not-blocked. Regular signals "can't count" — generation of an already pending signal is not recorded; think of it as a single bit that is "set" on generation. In contrast, realtime signals "queue" as a linked list of generated signals (up to some maximum).

Basic system calls include: kill() and rt_sigqueueinfo() for generation; sigprocmask() and rt_sigprocmask() for blocking and unblocking; sigpending() and rt_sigpending() to check pending signals; sigaction(), signal(), and rt_sigaction() to establish a handler; and sigsuspend() and rt_sigsuspend() to wait for a signal. Calls often operate on signal sets, which are two-element arrays of ints (64-bit bitmask).

Regarding blocking, pending, and delivery: blocked signals have delivery delayed until unblocked, and it is possible for a signal to be blocked with no signal pending. A generated signal is pending for a short while even if unblocked. Unblocked pending signals are delivered on kernel to user transition, with delivery opportunities every timer interrupt (but only for current). When masking signals, current signal delivery is masked during handler execution (like interrupt masking), so handlers need not be re-entrant. Old, buggy semantics did not mask the current signal.

All signals have a default action: terminate, dump (terminate and dump core), ignore (throw away on delivery), stop (control-z), or continue. It is possible to catch most signals by establishing a user-specified handler. However, SIGKILL and SIGSTOP cannot be caught, blocked, or ignored.

Signals: Old Unreliable Signals

The old call signal() was unreliable and buggy because further signal delivery was not masked during the handler, and the default action was restored on delivery. The common programming idiom was to re-establish the handler inside the handler:

myhandler() {
    // window of vulnerability here!
    signal(SIGWHATEVER, myhandler) // reestablish
    // do something to handle signal
}

The consequence is that a new delivery can occur during the window of vulnerability, making it impossible to reliably catch all signals. The new call sigaction() is reliable: it avoids the problem because signals are masked and there is no reset. It is parameterized to make old semantics still available, and signal() just calls sigaction() with appropriate parameters.

Signals: System Calls

The key system calls are:

• kill(pid, sig)
• sigaction(sig, act, oact) (which replaces signal())
• sigpending()
• sigprocmask()
• sigsuspend()

⭐ Key Takeaways

Loadable kernel modules are sections of kernel code that can be dynamically loaded and unloaded, independent of the rest of the kernel, and they rely on three components: module management, driver registration, and conflict resolution. Conflict resolution is essential for preventing multiple drivers from clashing over hardware resources. Signals are an asynchronous notification mechanism, like software interrupts, with three API generations: old unreliable, reliable Posix, and real-time Posix. The critical difference between old and reliable signals is that sigaction() masks further delivery during handler execution and does not reset the default action, solving the window of vulnerability problem in signal(). SIGKILL and SIGSTOP are the two signals that cannot be caught, blocked, or ignored.

🧠 Quick Revision Questions

1. What are the three components to Linux module support?
2. What is the purpose of the conflict resolution module?
3. What are the three distinct APIs for signals?
4. What is the fundamental difference between how regular signals and real-time signals handle multiple pending generations?
5. Why is the old signal() call considered "unreliable," and how does sigaction() fix this?

📘 Lecture 39 — Overview of today’s lecture

📖 Overview: This lecture introduces fundamental concepts of security and protection in operating systems, covering security issues, the distinction between policy and mechanism, design principles for security, and basic terminology. It also provides an introduction to user authentication methods. Understanding these concepts is critical for designing systems that can resist both accidental misuse and malicious attacks.

🗂️ Topics Covered

The lecture covers the introduction to security and protection, including security issues such as isolation, authentication, access control, and protection problems. It then discusses policy versus mechanism, the reality that no perfect protection system exists, design principles for security, how to determine security requirements, key terminology (principals, objects, rights), and activities (authentication, authorization, auditing), concluding with an introduction to user authentication.

📝 Lecture Summary

Security & Protection

The purpose of a protection system is to prevent accidental or intentional misuse of a system. Accidental misuse, such as a program mistakenly deleting the root directory, is relatively easy to solve by making the likelihood small. Malicious abuse, such as a hacker breaking a password and transferring money, is very hard to completely eliminate because loopholes cannot be fully sealed and probability-based solutions are insufficient.

💡 Why this matters: Understanding the difference between accidental and malicious threats helps engineers design appropriate defense mechanisms for each type.

Security issues

Isolation ensures separate processes execute in separate memory space, so a process can only manipulate allocated pages. Authentication determines who can access the system by proving identities. Access control governs when a process can create or access a file, create or read/write to a socket, or make a specific system call. The protection problem is to ensure that each object is accessed correctly and only by those processes that are allowed to do so. Comparison between different operating systems involves evaluating which protection models support least privilege most effectively and which system best enforces its protection model.

Policy versus mechanism

A good way to approach security is to separate policy (what) from mechanism (how). A protection system is the mechanism to enforce a security policy, with roughly the same set of choices regardless of the specific policy. A security policy delineates what is acceptable and unacceptable behavior. Example security policies include: each user can only allocate 40MB of disk, no one but root can write to the password file, and you cannot read my mail.

There is no perfect protection system

A very simple but easily missed point: protection can only increase the work factor—the effort needed to do something bad—but it cannot prevent it entirely. Even assuming a technically perfect system, there are always the four Bs:

1. Burglary: if you cannot break into the system, you can always steal it (physical security)
2. Bribery: find whoever has access to what you want and bribe them
3. Blackmail
4. Bludgeoning: beat someone until they tell you

Design Principles for Security

1. System design should be public
2. Default should be no access
3. Check for current authority
4. Give each process least privilege possible
5. Protection mechanism should be simple, uniform, and in lowest layers of system
6. Scheme should be psychologically acceptable

First: What are Your Security Requirements?

To determine security requirements, first assess your security environment: what threats exist and how severe are they, who is not trusted, what assumptions are made, what platforms and network environment exist, what organizational policies apply, and what assets need protection. Then identify your product's security objectives:

• Confidentiality ("can't read")
• Integrity ("can't change")
• Availability ("works continuously")
• Other: Privacy ("doesn't reveal"), Audit, etc.

Finally, determine what functions and assurance measures are needed, using the Common Criteria as a useful checklist of requirements.

Terminology I: the entities

• Principals – who is acting? (user/process creator, code author)
• Objects – what is that principal acting on? (file, network connection)
• Rights – what actions might you take? (read, write)

Familiar UNIX file system example: owner/group/world with read/write/execute permissions.

Terminology II: the activities

• Authentication – who are you? Identifying principals (users/programs)
• Authorization – what are you allowed to do? Determining what access users and programs have to specific objects
• Auditing – what happened? Recording what users and programs are doing for later analysis/prosecution

User Authentication

User authentication must identify the user through one of three basic principles:

1. Something the user knows (e.g., password)
2. Something the user has (e.g., security token)
3. Something the user is (e.g., biometric characteristic)

This is done before the user can use the system.

⭐ Key Takeaways

The most critical point is that no protection system is perfect—it can only increase the work factor required to breach security, and attackers may bypass technical controls through physical means (the four Bs). Students must understand the crucial distinction between policy (what behavior is allowed) and mechanism (how to enforce it), and that a protection system is just the mechanism implementing a policy. The six design principles, especially "default no access" and "least privilege," are foundational for building secure systems. Finally, security requirements must be evaluated before design, considering confidentiality, integrity, availability, and privacy, and the three authentication factors (something you know, have, or are) must be clearly distinguished.

🧠 Quick Revision Questions

1. What is the fundamental difference between accidental misuse and malicious abuse in terms of difficulty of prevention?
2. What are the four Bs that can defeat even a technically perfect protection system?
3. List all six design principles for security as presented in the lecture.
4. What are the three security objectives (confidentiality, integrity, availability) and how do they differ from privacy?
5. What three categories of information are used for user authentication, and provide an example of each?

📘 Lecture 40 — Overview of today’s lecture

📖 Overview: This lecture covers the fundamental concepts of user authentication and access control in operating systems. It examines various authentication methods ranging from password-based schemes to biometrics, and introduces the access control matrix model along with its practical implementations (ACLs and capabilities). Understanding these mechanisms is crucial for designing secure systems that correctly identify users and control their access to resources.

🗂️ Topics Covered

This lecture covers user authentication, password-based authentication, the UNIX password scheme, one-time password schemes (including Lamport’s scheme), challenge-response authentication (used in PPP), biometrics and other authentication alternatives like badges/keys, access control and authorization, and the access control matrix model with its two implementation concepts: access control lists (ACLs) and capabilities.

📝 Lecture Summary

Overview of today’s lecture

The lecture begins with an outline of topics including user authentication, password based authentication, the UNIX password scheme, one-time password schemes, challenge response authentication, biometrics and other authentication schemes, and access control and authorization culminating in the access control matrix.

Authentication

Authentication is usually done with passwords, which is considered a relatively weak form because it relies on something people must remember. Empirically, passwords are often based on easily guessed personal information like a spouse's or child's name or a favorite movie name.

Passwords should not be stored in a directly-readable form. Instead, use some sort of one-way-transformation (a secure hash) and store that hash. For example, if you look in /etc/passwords, you will see a bunch of gibberish associated with each name — that is the hashed password.

A key problem is preventing dictionary attacks: passwords should be long and obscure to prevent guessing, but unfortunately, such passwords are easily forgotten and are usually written down.

🔑 Definition — Dictionary attack: An attack where an adversary tries a list of common passwords or dictionary words against a hashed password database. 📌 Example: A user chooses "password123" as their password. An attacker runs a program that hashes thousands of common passwords (e.g., "password", "123456", "qwerty", "letmein") and compares the resulting hashes to the stored hash in /etc/passwords. If any match, the password is cracked.

💡 Why this matters: Dictionary attacks are the most common method for breaking password-based systems; understanding this motivates the need for strong, random passwords and hashing with salt.

UNIX password security: Uses encryption of passwords.

One time passwords: A clever scheme was developed by Lamport (read Tanenbaum for details).

Challenge-Response based authentication: Used in PPP (Point-to-Point Protocol) and many other applications.

Authentication alternatives

An alternative to passwords is a badge or key. This does not have to be kept secret and is usually some sort of picture ID worn on a jacket (e.g., at military bases). It should not be forgeable or copy-able. It can be stolen, but the owner should know if it is.

🔑 Definition — Capability: In this context, a badge or key is similar to the notion of a "capability" that will be seen later — a token that grants access to a resource.

Biometrics

Biometrics refers to authentication of a person based on a physiological or behavioral characteristic. Example features include face, fingerprints, hand geometry, handwriting, iris, retinal, vein, and voice. This provides strong authentication but still requires a trusted path.

🔑 Definition — Trusted Path: A mechanism that ensures a user is communicating directly with the trusted operating system, not with a malicious program (e.g., a fake login screen) that might intercept credentials.

Access control

The context for access control is that the system knows who the user is (e.g., user has entered a name and password, or other info). Access requests pass through a gatekeeper, and the OS must be designed so that the monitor cannot be bypassed.

Access control matrix [Lampson]

The access control matrix is a conceptual model where:

• Rows represent subjects (users or processes)
• Columns represent objects (resources like files, devices)
• Cells contain the access rights (e.g., read, write, execute) that a subject has to an object

📐 Formula: AccessControlMatrix[Subject, Object] = {set of access rights} → Plain-English meaning: For each user and each resource, the matrix specifies exactly what operations that user is allowed to perform.

Two implementation concepts

Two main implementations of the access control matrix exist:

1. Access control list (ACL): Store the column of the matrix with the resource. Each resource (object) maintains a list of users and their access rights. 📌 Example: A file "report.txt" has an ACL specifying: "Alice: read, write; Bob: read; Charlie: no access".

2. Capability: The user holds a ticket for each resource. Each user (subject) possesses a list of tickets that grant access to specific objects. 📌 Example: Alice holds a capability token that allows her to open "report.txt" with read and write access; Bob holds a different capability token for the same file giving only read access.

Access control lists are widely used, often with groups. Some aspects of the capability concept are used in Kerberos.

💡 Why this matters: ACLs and capabilities represent the two fundamental approaches to implementing authorization — one stores permissions with the object (easier for revocation), the other with the user (easier for delegation). Choosing between them affects system performance and security properties.

⭐ Key Takeaways

• Passwords should never be stored in plain text; always use one-way transformations (secure hashes) to prevent direct exposure, and long obscure passwords are needed to resist dictionary attacks despite being hard to remember. Biometrics (face, fingerprints, iris, etc.) offer stronger authentication but still require a trusted path to prevent interception. The access control matrix is the foundational model for authorization, where rows represent subjects, columns represent objects, and cells define access rights. This matrix is implemented in two main ways: access control lists (ACLs) store permissions with the resource (column-oriented), while capabilities store them with the user (row-oriented). ACLs are the more widely used approach, often with groups, while capability concepts appear in systems like Kerberos.

🧠 Quick Revision Questions

1. What is the main weakness of password-based authentication as described in this lecture, and what attack does it enable?
2. How does the UNIX password scheme store passwords securely, and what should you find in /etc/passwords?
3. What is Lamport's scheme used for, and what is the main advantage of one-time passwords?
4. List four different biometric features that can be used for authentication.
5. Explain the difference between an access control list (ACL) and a capability in terms of where the access permissions are stored.

📘 Lecture 41 — Overview of today’s lecture

📖 Overview: This lecture contrasts Access Control Lists (ACLs) and capabilities as two fundamental access control mechanisms, covering delegation, revocation, and operations on capabilities. It then explores advanced access control models including roles, groups, confidentiality (Bell-LaPadula), integrity (Biba), and other policy concepts like separation of duty and the Chinese Wall policy, which are crucial for designing secure operating systems.

🗂️ Topics Covered

The lecture begins with a comparison of ACLs versus capabilities, focusing on delegation and revocation. It then details operations on capabilities (copy, copy object, remove, destroy), discusses sandboxing mobile code, and introduces roles and groups for organizing permissions. Finally, it covers Multi-Level Security (MLS) concepts, the Confidentiality Model (Bell-LaPadula), the Integrity Model (Biba), and other policy concepts like separation of duty and the Chinese Wall policy.

📝 Lecture Summary

ACL vs Capabilities

Access Control Lists (ACLs) associate a list with each object and check the user/group against that list. This relies on authentication because the system needs to know the user's identity. In contrast, capabilities are unforgeable tickets—either a random bit sequence or managed by the OS—that can be passed from one process to another. A reference monitor checks the ticket and does not need to know the identity of the user or process.

For delegation, with capabilities, a process can pass a capability to another at run time. With ACLs, you must try to get the owner to add the permission to the list. For revocation, ACLs simply remove the user or group from the list. With capabilities, revocation is harder because you have to try to get the capability back from the process. Revocation is possible in some systems only if the OS performs appropriate bookkeeping and knows what data is a capability. If a capability is used for multiple resources, you have to revoke all or none.

Operations on Capabilities

Four operations are defined on capabilities:

• Copy: create a new capability for the same object
• Copy object: create a duplicate object with a new capability
• Remove capability: delete an entry from the capability list; the object remains unaffected
• Destroy object: permanently remove an object and its capability

Sandboxing mobile code involves starting a foreign program in a process and giving that process a specific set of capabilities, such as read and write on the monitor and read and write a scratch directory. This follows the principle of least privilege.

💡 Why this matters: Capabilities have been described as an operating system concept "of the future (and always will be?)" but are implemented in systems like Hydra, StarOS, Intel iAPX 432, Eros, and Amoeba (distributed, unforgeable tickets).

🔑 Definition — Capability: An unforgeable ticket that grants a process access rights to an object, managed either as a random bit sequence or by the operating system.

Roles (also called Groups)

A role is a set of users, such as Administrator, PowerUser, User, and Guest. Permissions are assigned to roles, and each user gets the permissions of their assigned role. A role hierarchy is a partial order of roles where each role automatically inherits the permissions of roles below it. You only need to list new permissions given to each role.

Groups for resources, rights

A permission is defined as a pair ⟨right, resource⟩. Permission hierarchies allow that if a user has right r and r > s, then the user also has right s. Similarly, if a user has read access to a directory, the user has read access to every file in that directory. The big problem in access control is that complex mechanisms require complex input, making them difficult to configure and maintain. Roles and other organizing ideas try to simplify this problem.

Multi-Level Security (MLS) Concepts

MLS originates from military security policy where classification involves sensitivity levels and compartments. The goal is to prevent classified information from leaking to unclassified files. Grouping individuals and resources uses some form of hierarchy to organize policy. Other policy concepts include separation of duty and the "Chinese Wall" Policy.

Confidentiality Model

The Confidentiality Model (Bell-LaPadula) answers: When is it OK to release information? It has two properties:

1. Simple security property: A subject S may read object O only if C(O) ≤ C(S)
2. *-Property (star property): A subject S with read access to object O may write object P only if C(O) ≤ C(P)

In words: You may only read below your classification and only write above your classification.

🔑 Definition — Simple security property: A subject may read an object only if the object's classification is less than or equal to the subject's classification (no read-up). 🔑 Definition — *-Property (star property): A subject that has read access to an object may write to another object only if the first object's classification is less than or equal to the second object's classification (no write-down).

Integrity Model

The Integrity Model (Biba) preserves the integrity of information. It also has two properties:

1. Simple integrity property: A subject S may write object O only if C(S) ≥ C(O). Only trust S to modify O if S has higher rank.
2. *-Property (star property): A subject S with read access to O may write object P only if C(O) ≥ C(P). Only move info from O to P if O is more trusted than P.

In words: You may only write below your classification and only read above your classification.

The problem is that these models appear contradictory. Confidentiality says "read down, write up," while integrity says "read up, write down." To have both confidentiality and integrity, this contradiction is partly an illusion. You may use confidentiality for one classification of personnel/data and integrity for another. Otherwise, the only way to satisfy both models is to allow read and write only at the same classification. In practice, confidentiality is used more than the integrity model (e.g., in Common Criteria).

🔑 Definition — Simple integrity property: A subject may write an object only if the subject's classification is greater than or equal to the object's classification (no write-up). 🔑 Definition — *-Property (integrity): A subject with read access to an object may write another object only if the first object's classification is greater than or equal to the second's (no read-down).

Other policy concepts

Separation of duty: If an amount is over $10,000, a check is only valid if signed by two authorized people. The two people must be different. Policy involves role membership and inequality.

Chinese Wall Policy: Lawyers L1 and L2 in Firm F are experts in banking. If bank B1 sues bank B2, L1 and L2 can each work for either B1 or B2, but no lawyer can work for opposite sides in any case. Permission depends on the use of other permissions.

⭐ Key Takeaways

The critical lesson is the fundamental contrast between ACLs (which require identity) and capabilities (which rely on unforgeable tickets and support run-time delegation but complicate revocation). You must know the two pairs of properties: for confidentiality (Bell-LaPadula) — Simple security property (read down) and *-Property (write up) — and for integrity (Biba) — Simple integrity property (write down) and *-Property (read up). Remember that these models are contradictory if applied to the same data, but can be used for different classifications. Finally, be able to define capabilities, roles, role hierarchies, separation of duty, and the Chinese Wall policy.

🧠 Quick Revision Questions

1. How does delegation differ between ACL-based and capability-based systems?
2. What are the two properties of the Confidentiality (Bell-LaPadula) model, and what do they prevent (in terms of reading up/down and writing up/down)?
3. What are the two properties of the Integrity (Biba) model, and how do they differ from the Confidentiality model's rules?
4. Explain the revocation problem with capabilities and what OS bookkeeping is needed to make it possible.
5. Describe the Chinese Wall policy and explain why it differs from standard access control models.

📘 Lecture 42 — Overview of today’s lecture

📖 Overview: This lecture introduces several common types of malicious software attacks, including Trojan horses, login spoofing, logic bombs, and trap doors. It then focuses extensively on buffer and stack overflow attacks—one of the most prevalent and dangerous security vulnerabilities—explaining how they work and how they can be exploited using unsafe C library functions.

🗂️ Topics Covered

The lecture covers Trojan horses as deceptive programs containing hidden harmful code, login spoofing attacks that trick users into revealing credentials, logic bombs that activate upon specific conditions, and trap doors providing unauthorized access. The main focus is on buffer and stack overflow attacks, including their history, mechanics using stack diagrams, and the role of unsafe C library functions (strcpy, strcat, gets, scanf, printf) in enabling these exploits.

📝 Lecture Summary

Trojan Horses (from Tanenbaum’s book)

A Trojan horse is a free program made available to an unsuspecting user that actually contains code to do harm. The attacker places an altered version of a utility program on the victim's computer, tricking the user into running that program. This is similar to the ancient Greek story where a seemingly harmless gift concealed enemy soldiers.

Login Spoofing

Login spoofing involves displaying a phony login screen that looks identical to the correct one. The user types their username and password, which are captured by the attacker. The fake screen might then show an error message and present the real login screen, making the user believe they mistyped their credentials.

🔑 Definition — Login spoofing: A technique where a fake login interface is presented to trick users into entering their credentials, which are then stolen by the attacker.

Logic Bombs

A logic bomb is malicious code written by a company programmer that has the potential to do harm. It remains harmless as long as the programmer enters a password daily. If the programmer is fired and stops entering the password, the bomb "explodes" and executes the harmful payload.

🔑 Definition — Logic bomb: Malicious code inserted into a system that activates upon a specific logical condition (e.g., missing a daily password entry).

Trap Doors

A trap door (also called a backdoor) is secret entry point inserted into code that bypasses normal authentication. The lecture shows normal code and code with a trapdoor inserted, allowing the attacker to gain unauthorized access to the system.

🔑 Definition — Trap door: A hidden mechanism in software that grants unauthorized access to a system, bypassing normal security controls.

Buffer overflows

Buffer overflows are an extremely common bug. The first major exploit was the 1988 Internet Worm targeting the fingerd service. Ten years later, over 50% of all CERT advisories involved buffer overflows: 1997 had 16 out of 28 (57%), 1998 had 9 out of 13 (69%), and 1999 had 6 out of 12 (50%). Buffer overflows often lead to total compromise of the host. Fortunately, exploiting them requires expertise and patience, involving two steps: locating a buffer overflow within an application, and designing an exploit.

The lecture shows stack diagrams: (a) situation when main program is running, (b) after program A is called, and (c) buffer overflow shown in gray, illustrating how the overflow overwrites adjacent memory.

💡 Why this matters: Buffer overflows remain one of the most critical security vulnerabilities despite being known for decades. They allow attackers to execute arbitrary code and take complete control of systems.

What are buffer overflows?

Suppose a web server contains a function:

void func(char *str) {
    char buf[128];
    strcpy(buf, str);
    do-something(buf);
}

When the function is invoked, the stack looks like a structure containing local variables (buf with 128 bytes), the saved frame pointer, and the return address. If *str is 136 bytes long, after strcpy() the extra 8 bytes overwrite the return address and potentially the saved frame pointer, corrupting the stack.

🔑 Definition — Buffer overflow: Occurs when a program writes more data to a buffer than it can hold, overwriting adjacent memory and potentially causing crashes or enabling code execution.

Basic stack exploit

The main problem is no range checking in strcpy(). Suppose *str is crafted so that after strcpy, the stack contains the attacker's shellcode in the buffer area, and the overwritten return address points to that shellcode. When func() exits, the return address is used to transfer control—and instead of returning normally, the user will be given a shell. Note that attack code runs in the stack. To determine the correct return address, the attacker guesses the position of the stack when func() is called and uses a stream of NOPs (no-operation instructions) to create a "NOP sled" that increases the chance of landing in the exploit code.

🔑 Definition — NOP sled: A sequence of NOP (no-operation) instructions placed before shellcode to increase the probability that the overwritten return address lands somewhere in the sled, sliding execution into the actual exploit code.

📐 Formula: Buffer overflow exploit formula: Overflow buffer + overwrite return address + NOP sled + shellcode = arbitrary code execution

📌 Example: A 128-byte buffer receives 136 bytes via strcpy. The first 128 bytes fill the buffer (possibly containing NOP sled and shellcode), bytes 129-132 overwrite the saved frame pointer, and bytes 133-136 overwrite the return address to point to the shellcode in the buffer.

Some unsafe C lib functions

The following C library functions are unsafe because they do not perform bounds checking:

• strcpy (char *dest, const char *src) — copies string without size limit
• strcat (char *dest, const char *src) — appends string without size limit
• gets (char *s) — reads input without size limit
• scanf ( const char *format, ... ) — may overflow if format doesn't limit input
• printf (const char *format, ... ) — can be exploited via format string vulnerabilities

🔑 Definition — Unsafe C library functions: Standard C functions that do not check buffer boundaries, making them vulnerable to buffer overflow attacks when used with untrusted input.

How does an attacker actually launch this attack

An attacker launches a buffer overflow attack through inspection of source code (if available), help of debuggers to examine memory layout and stack positions, and cramming a lot of data into a program to trigger the overflow.

Exploiting buffer overflows

Suppose a web server calls func() with a given URL. The attacker can create a 200-byte URL to obtain a shell on the web server. Some complications arise: the program should not contain the '\0' character (which would terminate string operations early), and the overflow should not crash the program before func() exits. Sample buffer overflows of this type include: overflow in MIME type field in MS Outlook, and overflow in ISAPI in IIS.

📌 Example: A web server processes a URL parameter and passes it to a function with a 128-byte buffer. The attacker crafts a 200-byte URL containing NOP sled + shellcode + overwritten return address. When processed, the function returns to the shellcode, giving the attacker a command shell with the server's privileges.

⭐ Key Takeaways

The lecture identifies five major attack types: Trojan horses, login spoofing, logic bombs, trap doors, and buffer/stack overflows. Buffer overflows are historically the most dangerous, responsible for over 50% of security advisories for years. The core mechanism involves overwriting a fixed-size buffer using unsafe C functions like strcpy, which lack bounds checking, allowing attackers to corrupt the return address on the stack and redirect execution to malicious shellcode. The classic exploit uses a NOP sled to increase reliability and is launched by sending input data (like a crafted URL) longer than the expected buffer size. Understanding these vulnerabilities requires knowledge of memory layout, stack organization, and the specific functions that enable these attacks.

🧠 Quick Revision Questions

1. What is the difference between a Trojan horse and a logic bomb in terms of how they are activated?
2. How does a login spoofing attack work, and what makes it effective against users?
3. When a buffer is 128 bytes and the input is 136 bytes, what specific memory locations are overwritten on the stack?
4. Why is the strcpy() function considered unsafe in the context of buffer overflow attacks?
5. What is the purpose of using a NOP sled in a buffer overflow exploit, and how does it increase the attacker's success rate?

📘 Lecture 43 — Overview of today’s lecture

📖 Overview: This lecture covers buffer overflow attacks and their prevention mechanisms, then transitions to broader security topics including viruses, worms, and mobile code security. Understanding these concepts is critical for building secure systems and defending against common exploits.

🗂️ Topics Covered

The lecture covers types of buffer overflow attacks including stack smashing, function pointer and longjmp buffer attacks, followed by methods for finding buffer overflows. Prevention techniques are discussed including marking stack as non-execute, StackGuard with canary types, PointGuard, Libsafe, and address obfuscation. The lecture then covers viruses and worms, their operation and spread, antivirus techniques, and concludes with mobile code security including sandboxing and Java security mechanisms.

📝 Lecture Summary

Types of buffer overflow attacks

Buffer overflow attacks exploit programs that use unsafe string functions without bounds checking. The stack smashing attack overrides the return address in a stack activation record by overflowing a local buffer variable, redirecting execution to attacker-controlled code. Attackers can also target function pointers — overflowing a buffer can override a function pointer to redirect execution, as was used in the attack on Linux superprobe. Similarly, longjmp buffers — overflowing a buffer next to the jump position overrides the value of pos, as used in the attack on Perl 5.003.

Causing program to exec attack code

The core goal of buffer overflow attacks is to cause the program to execute attack code. The stack smashing attack overrides the return address in the stack activation record by overflowing a local buffer variable. Function pointers can be targeted — overflowing a buffer will override a function pointer to point to malicious code. Longjmp buffers like longjmp(pos) — overflowing a buffer next to the jump position overrides the value of pos, redirecting control flow.

Finding buffer overflows

Hackers find buffer overflows through systematic testing. One method involves running the web server on a local machine and issuing requests with long tags, where all long tags end with "$$$$$". If the web server crashes, the attacker searches the core dump for "$$$$$" to find the overflow location. Some automated tools exist for finding buffer overflows, including eEye Retina and ISIC.

Preventing buf overflow attacks

The main problem is that unsafe C functions like strcpy(), strcat(), and sprintf() have no range checking. The "safe" versions strncpy() and strncat() are misleading because strncpy() may leave the buffer unterminated. Defenses include using type safe languages like Java or ML (but legacy code remains problematic), marking the stack as non-execute, static source code analysis, run time checking using tools like StackGuard, Libsafe, SafeC, or Purify, and black box testing using tools like eEye Retina or ISIC.

Marking stack as non-execute

The basic stack exploit can be prevented by marking the stack segment as non-executable or randomizing the stack location. Code patches exist for Linux and Solaris. However, this approach has significant problems: it does not block more general overflow exploits like heap overflows where the buffer next to a function pointer is overflowed. Some applications need an executable stack, such as LISP interpreters. The patch is not shipped by default for Linux and Solaris.

Run time checking: StackGuard

Many run-time checking techniques exist. StackGuard (by WireX) performs run time tests for stack integrity. It embeds canaries in stack frames and verifies their integrity prior to function return. Two types of canaries exist: Random canary — a random string is chosen at program startup, inserted into every stack frame, and verified before returning from a function. To corrupt a random canary, the attacker must learn the current random string. Terminator canary — the canary consists of characters like 0, newline, linefeed, and EOF. String functions will not copy beyond these terminators, so the attacker cannot use string functions to corrupt the stack. StackGuard is implemented as a GCC patch, requiring the program to be recompiled, with minimal performance effects (8% for Apache). The newer version PointGuard protects function pointers and setjmp buffers by placing canaries next to them, with more noticeable performance effects. However, canaries don't offer full protection — some stack smashing attacks can leave canaries untouched.

🔑 Definition — Canary: A random or terminator value placed in a stack frame to detect buffer overflows by verifying its integrity before function return.

📌 Example: With a terminator canary containing 0, newline, linefeed, and EOF characters, if an attacker attempts to overwrite the stack using strcpy() to copy a string containing these characters, the copy will stop at the first terminator character, preventing corruption of the return address.

Run time checking: Libsafe

Libsafe (by Avaya Labs) is a dynamically loaded library that intercepts calls to strcpy(dest, src). It validates sufficient space in the current stack frame by checking |frame-pointer – dest| > strlen(src). If there is enough space, it performs the strcpy operation; otherwise, it terminates the application.

More methods

Address obfuscation (Stony Brook, 2003) encrypts the return address on the stack by XORing it with a random string, then decrypts just before returning from the function. The attacker needs the decryption key to set the return address to a desired value. Another method is to randomize the location of functions in libc, so the attacker cannot jump directly to an exec function.

💡 Why this matters: Run-time checking and obfuscation techniques provide defense-in-depth, even if system-level protections fail, but no single method is foolproof.

Viruses and worms

An external threat involves code transmitted to a target machine where it is executed, causing damage. The goals of a virus writer include creating a quickly spreading virus, making it difficult to detect, and making it hard to get rid of. A virus is a program that can reproduce itself by attaching its code to another program and additionally causes harm.

How Viruses Work (1)

A virus is typically written in assembly language and inserted into another program using a tool called a dropper. The virus remains dormant until the program is executed, at which point it infects other programs and eventually executes its payload. A virus can be placed at the front of an executable program, at the end, or spread over free space within the program.

How Viruses Spread

Viruses are placed where they are likely to be copied. When copied, they infect programs on the hard drive or floppy disks and may try to spread over a LAN. They can attach to innocent-looking emails — when the email attachment runs, the virus uses the mailing list to replicate itself.

Antivirus and Anti-Antivirus Techniques

Antivirus techniques include signature-based detection, integrity checkers, and behavioral checkers. Virus avoidance strategies include using a good operating system, installing only shrink-wrapped software, using antivirus software, not clicking on attachments to email, and performing frequent backups. Recovery from a virus attack involves halting the computer, rebooting from a safe disk, and running antivirus software.

Mobile Code (1) Sandboxing

Sandboxing divides memory into 1-MB sandboxes. Instructions are checked for validity by verifying that each memory access stays within its allocated sandbox. For example, an OR instruction that computes the effective address is checked with a guard to ensure it falls within the sandbox boundaries.

Mobile Code (2) and (3)

In mobile code execution, applets can be interpreted by a Web browser. Code signing is a security mechanism where a developer signs the code with a digital signature. The signature verifies the code's origin and integrity. If the signature is valid, the code is given more privileges (e.g., full access); if not, it runs with restricted privileges in the sandbox.

🔑 Definition — Sandboxing: A security mechanism that restricts mobile code to a limited set of resources and memory regions, preventing it from accessing system resources without permission.

Java Security (1)

Java is a type safe language — the compiler rejects attempts to misuse variables. Security checks in Java include: attempts to forge pointers, violation of access restrictions on private class members, misuse of variables by type, generation of stack over/underflows, and illegal conversion of variables to another type. These compile-time checks prevent many buffer overflow and memory corruption attacks.

⭐ Key Takeaways

Buffer overflow attacks exploit the lack of bounds checking in C functions like strcpy() to overwrite return addresses, function pointers, or longjmp buffers. Multiple defense layers exist: marking the stack as non-executable prevents basic exploits but not heap overflows; StackGuard uses canaries to detect stack corruption at runtime with minimal performance overhead; and Libsafe intercepts unsafe function calls to validate buffer sizes. Viruses and worms are self-replicating programs that spread and execute payloads, countered by signature-based, integrity, and behavioral detection methods. Mobile code security relies on sandboxing to restrict untrusted applets and code signing to grant privileges based on verified origins.

🧠 Quick Revision Questions

1. What are the three types of buffer overflow attack targets discussed, and what do they each overwrite?
2. How does StackGuard's random canary differ from its terminator canary in implementation and defense mechanism?
3. Why does marking the stack as non-executable fail to prevent all buffer overflow attacks?
4. What are the three main categories of antivirus detection techniques, and what does each monitor?
5. How does Java's type safety prevent buffer overflow attacks, and what specific violations does the compiler check?

📘 Lecture 44 — Overview of today’s lecture

📖 Overview: This lecture provides a comprehensive overview of security mechanisms across several major operating systems, including Java, UNIX, and Windows, and introduces SELinux. It covers critical concepts like setuid programs, access control lists (ACLs), tokens, security descriptors, and the reference monitor, culminating in a summary of what constitutes a secure OS, including the distinction between Discretionary Access Control (DAC) and Mandatory Access Control (MAC) and the Orange Book criteria.

🗂️ Topics Covered

The lecture covers Java security examples, UNIX file security including permissions, setuid, setgid, and sticky bits, and process IDs (RUID, EUID, SUID). It then details Windows (NTFS) access control with tokens, SIDs, permission inheritance, security descriptors, and the reference monitor. SELinux is introduced with its security abstractions and kernelized design. Finally, the lecture summarizes features of a secure OS including DAC vs. MAC, assurance methods, and the Orange Book security evaluation criteria (Levels D through A1).

📝 Lecture Summary

Java Security (2)

Examples of specified protection with JDK 1.2 are an extension of previously discussed Java security concepts.

Unix file security

• Each file has an owner and a group.
• Permissions are set by the owner for read, write, and execute access, categorized by owner, group, and other.
• Permissions are represented by a vector of four octal values.
• Only the owner or root can change permissions; this privilege cannot be delegated or shared.
• Setid bits are discussed later.

🔑 Definition — Owner privilege resolution: When an owner has fewer privileges than "other", the system uses a prioritized resolution: if the user is the owner, owner permissions apply; else if the user is in the group, group permissions apply; else, other permissions apply.

Setid bits on executable Unix file

There are three setid bits:

• Setuid: Sets the Effective User ID (EUID) of the process to the ID of the file owner.
• Setgid: Sets the Effective Group ID (EGID) of the process to the GID of the file.
• Sticky bit:
  • Off: If a user has write permission on a directory, they can rename or remove files, even if they are not the owner.
  • On: Only the file owner, directory owner, and root can rename or remove a file in the directory.

Effective user id (EUID)

Each process has three IDs (plus more under Linux):

• Real user ID (RUID): Same as the user ID of the parent process (unless changed); it determines which user started the process.
• Effective user ID (EUID): Comes from the set user ID bit on the file being executed or a system call; it determines the permissions for the process (file access and port binding).
• Saved user ID (SUID): Stores the previous EUID so it can be restored.
• Real group ID and effective group ID are used similarly.

Process Operations and IDs

• Root: Has an ID=0 for the superuser and can access any file.
• Fork and Exec: Inherit the three IDs, except when executing a file with the setuid bit set.
• Setuid system calls: seteuid(newid) can set the EUID to the Real ID or Saved ID (regardless of current EUID), or to any ID if the current EUID is 0.
• Details are actually more complicated, with several different calls: setuid, seteuid, setreuid.

📌 Example: The lecture text implies an example exists but does not explicitly state it. The caution is that setuid programs can do anything the file owner is allowed to do, so they must ensure they do not take action for an untrusted user or return secret data to an untrusted user. Anything is possible if root; there is no middle ground between user and root.

Unix summary

• Good things: Provides some protection from most users and is flexible enough to make things possible.
• Main bad thing: It is too tempting to use root privileges, and there is no way to assume some root privileges without all root privileges.

Access control in Windows (NTFS)

• Some basic functionality is similar to Unix, specifying access for groups and users (read, modify, change owner, delete).
• Additional concepts include Tokens and Security attributes.
• Generally, it offers more flexibility than Unix, allowing the definition of new permissions and the ability to give some, but not all, administrator privileges.

Security ID (SID)

• A Security ID (SID) is an identity that replaces the UID.
• It consists of a SID revision number, a 48-bit authority value, and a variable number of Relative Identifiers (RIDs) for uniqueness.
• Users, groups, computers, domains, and domain members all have SIDs.

Permission Inheritance

• Static permission inheritance (Win NT): Subfolders initially inherit permissions of the folder. The folder and subfolder are changed independently. The "Replace Permissions on Subdirectories" command eliminates any differences.
• Dynamic permission inheritance (Win 2000): Children inherit parent permissions and remain linked. Parent changes are inherited, except for explicit settings. Inherited and explicitly-set permissions may conflict, with resolution rules that positive permissions are additive and negative permissions (deny access) take priority.

Tokens

• The Security Reference Monitor uses tokens to identify the security context of a process or thread, which consists of the privileges and groups associated with it.
• An impersonation token is used temporarily by a thread to adopt a different security context, usually of another user.

🔑 Definition — Impersonation Tokens: A process uses the security attributes of another. The client passes an impersonation token to the server. The client specifies an impersonation level:

• Anonymous: Token has no information about the client.
• Identification: Server obtains the SIDs of the client and its privileges, but cannot impersonate.
• Impersonation: Server identifies and impersonates the client.
• Delegation: Lets server impersonate client on local and remote systems.

Security Descriptor

• Information associated with an object that defines who can perform what actions on the object.
• Fields include a Header (revision number, control flags, memory layout), the SID of the object's owner, the SID of the primary group, and two optional lists: Discretionary Access Control List (DACL) (users, groups) and System Access Control List (SACL) (system logs).

📌 Example access request: The lecture text mentions an example but does not provide a specific scenario in the provided text.

SELinux

• Security-enhanced Linux system (NSA) enforces separation of information based on confidentiality and integrity requirements.
• Mandatory Access Control (MAC) is incorporated into the major subsystems of the kernel to limit tampering, bypassing of application security mechanisms, and confine damage from malicious applications.
• Why Linux? It is open source, already subject to public review, and the NSA could review, modify, and extend its source code.

SELinux Security Policy Abstractions

• Type enforcement: Each process has an associated domain, and each object has an associated type. Configuration files specify how domains are allowed to access types and allowable interactions between domains.
• Role-based access control: Each process has an associated role (separating system and user processes). Configuration files specify the set of domains that may be entered by each role.

Kernelized Design

• Trusted Computing Base (TCB): The hardware and software for enforcing security rules.
• Reference monitor: Part of the TCB; all system calls go through it for security checking. Most OS are not designed this way.

What makes a “secure” OS?

• Extra security features: Stronger authentication (e.g., token + password), more security policy options (e.g., only let users read a file for a specific purpose), and logging.
• More secure implementation: Apply secure design and coding principles, assurance and certification (code audit or formal verification), and maintenance procedures (applying patches).

Sample Features of “Trusted OS”

• Mandatory access control (MAC): Not under user control, with precedence over DAC.
• Object reuse protection: Write over old data when file space is allocated.
• Complete mediation: Prevent any access that circumvents the monitor.
• Audit: Log security-related events and check logs.
• Intrusion detection: Anomaly detection (learn normal activity, report abnormal actions) and attack detection (recognize patterns associated with known attacks).

DAC and MAC

• Discretionary Access Control (DAC): Restricts a subject's access to an object (e.g., limit a user's access to a file). The owner of the file controls other users' accesses.
• Mandatory Access Control (MAC): Needed when security policy dictates that protection decisions must not be left to the object owner, and the system enforces a security policy over the wishes or intentions of the object owner.

🔑 Definition — DAC vs. MAC:

• DAC: Object owner has full power; complete trust in users; decisions are based only on user id and object ownerships; impossible to control information flow.
• MAC: Object owner CAN have some power; only trust in administrators; objects and tasks themselves can have ids; makes information flow control possible.

Audit

• Log security-related events.
• Protect audit log by writing to a write-once non-volatile medium.
• Audit logs can become huge, so manage size by following a policy (e.g., audit only first/last access by a process to a file, do not record routine, expected events). This makes storage and analysis more feasible.

Assurance methods

• Testing: Can demonstrate existence of a flaw, not absence.
• Formal verification: Time-consuming, painstaking process.
• “Validation”: Requirements checking, design and code reviews, module and system testing.

Orange Book Criteria

• Level D: No security requirements.
• Level C: For environments with cooperating users.
  • C1: Protected mode OS, authenticated login, DAC, security testing and documentation (e.g., Unix).
  • C2: DAC to the level of individual user, object initialization, auditing (e.g., Windows NT 4.0).
• Level B, A: All users and objects must be assigned a security label (classified, unclassified, etc.). System must enforce the Bell-LaPadula confidentiality model.

🔑 Definition — Levels B, A:

• Level B1: Classification and Bell-LaPadula.
• Level B2: System designed in a top-down modular way; must be possible to verify security of modules.
• Level B3: ACLs with users and groups; formal TCB must be presented; adequate security auditing; secure crash recovery.
• Level A1: Formal proof of the protection system, formal proof that the model is correct, and demonstration that the implementation conforms to the model.

⭐ Key Takeaways

The most critical aspects of OS security from this lecture include the fundamental difference between DAC (where the object owner controls access) and MAC (where the system enforces policy independent of the owner). Understanding the setuid/setgid mechanism in Unix is crucial for recognizing a common privilege escalation vector. Windows' security model relies on tokens (especially for impersonation) and Security Descriptors (with DACL and SACL) for fine-grained access control. The Orange Book criteria provide a historic framework for evaluating system security, from Level D (no security) to Level A1 (formally proven security). Finally, a secure OS requires features like complete mediation (reference monitor), audit logs, and intrusion detection, beyond just basic access control.

🧠 Quick Revision Questions

1. In Unix file security, if the file owner has fewer permissions than "other", what happens when the owner tries to access the file?
2. What is the purpose of the Effective User ID (EUID) in a Unix process, and how does the setuid bit affect it?
3. In Windows, what is the difference between an Impersonation Level of "Identification" and one of "Impersonation"?
4. What are the two main security policy abstractions used by SELinux to enforce Mandatory Access Control?
5. According to the Orange Book criteria, what are the minimum requirements for a system to be classified at Level C1, and what additional requirement is added for Level C2?

📘 Lecture 45 — Overview of today's lectures

📖 Overview: This lecture surveys advanced operating system research directions and emerging technologies, with a focus on reliability challenges in commodity OSes, mobile security risks, and the Symbian OS architecture. It also introduces Virtual Machine Monitors (VMMs) and provides a comprehensive review of memory management and I/O topics covered throughout the course.

🗂️ Topics Covered

This lecture begins with OS research directions, followed by the Nooks approach to improving reliability of commodity OSes. It then covers mobile phone risks including toll fraud, theft, availability threats, and attack vectors. The Symbian OS for mobile devices is examined in detail, including its architecture, security features, and limitations. Virtual Machine Monitors are introduced with concepts of virtualization, privileged instruction handling, and virtualization conditions. The lecture concludes with a quick review of memory management topics (paging, segmentation, TLB, page replacement, thrashing), file systems (allocation methods, FFS, journaling), and I/O subsystems (DMA, interrupt handling, device drivers).

📝 Lecture Summary

OS research directions

The lecture outlines multiple research directions in operating systems. A major direction is improving reliability of commodity OSes like Windows and Linux. Other directions include addressing mobile phone risks and security issues, studying embedded operating systems like Symbian OS, and exploring Virtual Machine Monitors (VMMs). The lecture also covers asynchronous I/O interfaces in the Linux kernel. Finally, it provides a quick review of all memory management and I/O topics.

Reliability in commodity OSes (e.g. Nooks)

The Nooks approach addresses the problem that device drivers are a major source of OS crashes. Drivers are run in protection domains defined by hardware and software, similar to how processes are isolated. This requires kernel modification to implement the isolation mechanism. The solution is good not only for drivers but also for other kernel extensions, such as in-kernel file systems.

Mobile phone risks

Mobile phones face multiple categories of risk:

Toll fraud includes:

• Auto dialers that secretly call premium numbers
• High cost SMS/MMS messages
• Phone Proxy that uses the device for unauthorized calls

Loss or theft risks include:

• Data loss
• Data compromise
• Loss of Identity (caller ID being misused)

Availability threats include:

• SPAM messages
• Destruction of the device (flash memory)
• Destruction of data

Risks induced by usage include:

• Mobile banking vulnerabilities
• Confidential e-mail and documents
• Device present at confidential meetings enabling snooping

Attack vectors are numerous and include: Executables, Bluetooth, GPRS/GSM, OTA (Over-The-Air), IrDa (Infrared), Browser, SMS/MMS, SD card, WAP, E-mail — "too many entry points to list all."

💡 Why this matters: The proliferation of mobile devices with multiple connectivity options creates an enormous attack surface, making mobile security a critical research area.

Symbian OS for mobile devices

Symbian Ltd. was formed in 1998 by Ericsson, Nokia, Motorola, and Psion. The EPOC operating system was renamed to Symbian OS. Currently there are approximately 30 phones with Symbian and 15 licensees.

Current ownership (at the time of this lecture):

• Nokia: 47.5%
• Panasonic: 10.5%
• Ericsson: 15.6%
• Siemens: 8.4%
• SonyEricsson: 13.1%
• Samsung: 4.5%

Architecture features:

• Multitasking, preemptive kernel
• MMU protection of kernel and process spaces
• Strong Client-Server architecture
• Plug-in patterns
• Filesystem can reside in ROM, Flash, RAM, and on SD-card

Symbian security features include:

Crypto:

• Algorithms
• Certificate framework
• Protocols: HTTPS, WTLS, etc.

Symbian signed:

• Public key signatures on applications
• Root CAs (Certificate Authorities) in ROM

Separation:

• Kernel vs. user space
• Process space
• Secured 'wallet' storage

Access controls:

• SIM PIN, device security code
• Bluetooth pairing

Artificial Limitations/patches:

• Prevent loading device drivers in the kernel (Nokia)
• Disallow overriding of ROM based plug-ins

Limitations:

• No concept of roles or users
• No access controls in the file system
• No user confirmation needed for access by applications
• User view on device is limited: partial filesystem, selected processes
• Majority of interesting applications are unsigned

Are attacks prevented?

• Fraud: user should not accept unsigned apps
• Loss/theft: In practice, little protection
• Availability: any application can render phone unusable (skulls trojan)

Virtual Machine Monitors

A Virtual Machine Monitor (VMM) exports a virtual machine to user programs that resembles real hardware. A virtual machine consists of all hardware features including user/kernel modes, I/O, interrupts, and "pretty much everything a real machine has." A virtual machine may run any OS.

Examples: JVM, VmWare, User-Mode Linux (UML).

Advantage: portability Disadvantage: slow speed

What Is It? A VMM virtualizes system resources. It runs directly on hardware and provides an interface that gives each program running on it the illusion that it is the only process on the system and is running directly on hardware. It provides the illusion of contiguous memory beginning at address 0, a CPU, and secondary storage to each program.

Privileged Instructions — The VMM handles privileged operations through a series of traps:

1. VMM is running operating system o, which is running process p
   • p tries to read — a privileged operation — this traps to hardware
2. VMM is invoked, determines the trap occurred in o
   • VMM updates state of o to make it look like hardware invoked o directly, so o tries to read, causing a trap
3. VMM does the actual read
   • Updates o to make it seem like o did the read
   • Transfers control to o
4. o tries to switch context to p, causing another trap
5. VMM updates virtual machine of o to make it appear o did context switch successfully
   • Transfers control to o, which (as o apparently did a context switch to p) has the effect of returning control to p

When Is VM Possible? An architecture can be virtualized when:

1. All sensitive instructions cause traps when executed by processes at lower levels of privilege
2. All references to sensitive data structures cause traps when executed by processes at lower levels of privilege

Asynchronous kernel interfaces

Asynchronous kernel interfaces and their implementation in the Linux kernel may require major changes to several parts and sub-systems of the kernel. These changes may result in enhanced kernel and application performance.

Quick review of memory management and I/O topics

Memory Management:

• Goals of OS memory management
• Questions regarding memory management
• Multiprogramming
• Virtual addresses
• Fixed partitioning and Variable partitioning
• Fragmentation
• Paging
• Address translation
• Page tables and Page table entries
• Multi-level address translation
• Page faults and their handling
• Segmentation
• Combined Segmentation and paging
• Efficient translations and caching
• Translation Lookaside Buffer (TLB)
• Set associative and fully associative caches
• Demand Paging
• Page replacement algorithms
• Thrashing
• Working set model
• Page fault frequency
• Copy on write
• Sharing
• Memory mapped files
• Allocation: Linked allocation, FAT, Indexed allocation, i-nodes
• File buffer cache
• Read ahead
• Consistency problem and its solutions
• SABRE airline example
• UNIX file system invariants
• Consistency ensuring techniques and rules: Write ordering, etc.
• Disks structure and internals: Platters, Cylinders, heads, tracks, sectors, etc.
• Fast File system (FFS): Cylinder groups, Fragments for small files
• Log structured (or journaling) file systems: Each update to the file system is recorded as a transaction. All transactions are written to a log. A transaction is considered committed once it is written to the log. The file system may not yet be updated. The transactions in the log are asynchronously written to the file system. When the file system is modified, the transaction is removed from the log. If the file system crashes, all remaining transactions in the log must still be performed.
• Uniform file system interface to user processes
• Represents any conceivable file system's general feature and behavior
• Assumes files are objects that share basic properties regardless of the target file system

I/O Topics:

• Goals of I/O software
• Layers of I/O software
• Direct Vs memory mapped I/O
• Interrupt driven I/O
• Polled I/O
• Direct Memory Access (DMA)
• Device independent I/O software layer
• Buffered and un-buffered I/O
• Block and character devices
• Network devices
• Kernel I/O subsystem and data structures
• Life cycle of a typical I/O request
• Life cycle of a typical network I/O request
• Interrupt handlers
• Interrupts and exceptions
• Linux interrupt handling
• Top halfs, bottom halfs and tasklets
• Timings and timer devices
• Linux kernel timers and interval timers
• Loadable Kernel modules and device drivers
• Linux module management
• Linux module conflict resolution
• Linux module registration
• Signals and asynchronous event notification

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) The Nooks approach improves OS reliability by running drivers in isolated protection domains requiring kernel modification. (2) Mobile phones face diverse risks including toll fraud, data loss from theft, and multiple attack vectors (Bluetooth, SMS, browser, etc.). (3) Symbian OS provides multitasking with MMU protection and client-server architecture but has significant security limitations including no user roles, no filesystem access controls, and most apps being unsigned. (4) A VMM virtualizes system resources by running directly on hardware and providing the illusion of a complete machine; virtualization is only possible when all sensitive instructions and data structure references cause traps at lower privilege levels. (5) The quick review section comprehensively lists all memory management concepts (paging, segmentation, TLB, page replacement, thrashing) and I/O topics (DMA, interrupt handling, device drivers, journaling file systems) covered in the course.

🧠 Quick Revision Questions

1. What are the three main categories of mobile phone risks, and give one example attack vector for each category?
2. In the Nooks approach, how are device drivers isolated from the rest of the kernel, and what type of modification is required?
3. What are the two conditions that must be met for an architecture to be virtualizable by a VMM?
4. List three security limitations of the Symbian OS mentioned in this lecture.
5. What is the key difference between how a VMM handles a privileged instruction from an operating system versus how it handles one from a user process?