Agenda:

• External Fragmentation in Dynamic Partitioning
  • Paging
    • Frames
    • Pages
    • Address translation
    • Page table
    • Optimization in paging
• Segmentation
  • Components 
  • Hardware
  • Comparison with paging
  • Hybrid approach

Addressing External Fragmentation in Dynamic Partitioning

Dynamic partitioning was initially used to divide memory into partitions of varying sizes for process allocation. However, it faces a significant disadvantage: external fragmentation. When memory is dynamically allocated, the memory space becomes fragmented into small chunks over time, preventing efficient allocation of contiguous memory for new processes.

• Compaction as a Solution:
  • Compaction is a process of rearranging the memory contents to combine all free spaces into a single contiguous block, which can then accommodate larger processes.
  • Overhead: This process is resource-intensive, involving substantial processing time to move memory contents, which creates overhead.

This leads us to seek more dynamic and optimal methods of memory allocation, where processes don’t require contiguous space in memory—paging addresses this challenge.

In dynamic partitioning, if a large process is needed but only small, non-contiguous memory blocks are available, external fragmentation prevents memory allocation.

Paging

Paging is a memory management technique that divides both physical and logical memory into fixed-sized blocks. This setup allows processes to be stored non-contiguously in physical memory, increasing flexibility and reducing fragmentation. 

Physical Memory Blocks (Frames)

Physical memory, or main memory, is divided into equal-sized sections known as frames.

• Frames:
  • Frames are fixed-sized blocks within physical memory. Each frame is large enough to hold a single page of a process’s logical memory.
  • Frames are uniform in size across all processes, making it easy to manage and allocate memory.
  • By breaking physical memory into frames, we can allocate memory to processes in a way that does not require contiguous memory blocks.
  • This approach contrasts with older memory management methods that required a contiguous block of free memory, which could lead to external fragmentation when small gaps formed between allocated memory blocks.
• Loading Pages into Frames:
  • Since each frame can hold exactly one page, any page from a process’s logical memory can be loaded into any free frame in physical memory.
  • This flexibility allows the OS to fill in memory gaps with individual pages, thus avoiding external fragmentation.

Logical Memory Blocks (Pages)

Logical memory, or the memory seen by a process, is divided similarly into equal-sized blocks called pages.

• Pages:
  • A page is a fixed-size block of a process’s logical memory.
  • The size of each page matches the size of each frame in physical memory exactly, enabling seamless mapping from logical memory to physical memory.
  • Dividing logical memory into pages enables the OS to map these pages to any available frames in physical memory.
  • This design allows processes to occupy non-contiguous memory in physical memory, even if the logical memory they see appears contiguous.
• Mapping Pages to Frames:
  • When a process is loaded into memory, each of its pages is mapped to a frame. Since the page and frame sizes are the same, the mapping from logical to physical memory is straightforward and efficient.
  • If a process requires more memory than is available contiguously in physical memory, its pages can be placed in separate frames throughout memory, wherever free frames are available.

Flexibility of Non-Contiguous Allocation

Paging’s structure of non-contiguous allocation allows for more efficient memory usage, as it eliminates the need for contiguous space.

• Non-Contiguous Loading:
  • A process does not need its pages to be stored sequentially in physical memory. Pages can be loaded into any available frames, regardless of their locations.
  • This allows memory to be utilized more effectively, as small gaps in memory can be filled with individual pages rather than left empty.
• External Fragmentation Prevention:
  • Traditional memory management methods required contiguous blocks, often leading to external fragmentation (small gaps of unusable memory between allocated blocks).
  • Paging avoids external fragmentation since it can place pages into any available frames, filling in gaps as needed.

Benefits of Paging

Paging provides several benefits over traditional contiguous memory allocation methods:

Avoids External Fragmentation:

Paging allows non-contiguous allocation by filling free frames randomly with pages from a process.

• Since each page is independent, it can be placed into any available frame. Even if the frames are scattered throughout physical memory, the OS and page table will manage the organization.
• By allowing pages to be loaded into any available frames, paging eliminates external fragmentation issues, as memory does not need to be in a continuous block for any single process.

No Compaction Needed:

• Because each page can occupy any available frame, memory allocation is more flexible, and processes do not need to occupy consecutive memory locations.
• This flexibility removes the need for compaction, a process that reorganizes memory to make space for large, contiguous blocks, which is both time-consuming and resource-intensive.

Address Translation in Paging

Paging is a memory management method where the operating system breaks down both logical memory (the address space of a program) and physical memory (RAM) into fixed-sized blocks. These blocks are called pages in logical memory and frames in physical memory. When a process is running, it generates logical (or virtual) addresses, which need to be translated into physical addresses.

Structure of a Logical Address

Every logical address that the CPU generates is structured into two distinct parts:

• Page Number (p):
  • The high-order (most significant) bits of the logical address form the page number.
  • The page number represents an index into the page table, which is a table that keeps track of where each page of a process is stored in main memory.
  • If the logical address space size is 2m2m (meaning there are 2m2m possible addresses), and the page size is 2n2n (each page has 2n2n addressable units like bytes or words), then the high-order m−nm−n bits of the logical address are allocated for the page number.
• Page Offset (d):
  • The lower-order (least significant) bits of the logical address form the page offset.
  • This offset indicates the exact location within a page where the desired data or instruction is located.
  • The page offset allows the CPU to locate a specific byte or word within the frame that holds the page in physical memory.
  • The offset size, represented by nn bits, determines how many addressing units (like bytes) a single page can contain (i.e., 2n2n units).

The Page Table

In modern operating systems, different structures of page tables are used to manage the translation between virtual (logical) addresses and physical addresses efficiently. Each page table structure has its own design to balance memory usage and access speed, particularly as address spaces grow larger. 

Hierarchical (or Multilevel) Page Table

The Hierarchical Page Table approach is used when the size of the page table itself becomes very large, typically when a process has a large address space. This structure uses multiple levels of page tables to reduce the memory needed for page tables.

• Multilevel Paging: The page table is split into smaller tables to create multiple levels. For example, in a two-level page table, the logical address is split into three parts:
  1. Outer page number (p1): Indexes into the outer page table.
  2. Inner page number (p2): Indexes into a page within the outer table.
  3. Offset (d): Refers to the location within the selected page in memory.

• Address Translation: The address translation for a two-level page table follows these steps:
  1. Step 1: Use p1 to index into the outer page table to locate the inner page table.
  2. Step 2: Use p2 to index into this inner page table, where the physical frame number for the page resides.
  3. Step 3: Combine this frame number with the offset d to generate the full physical address.

Benefits

• Memory Efficiency: Only portions of the page table are created and stored as needed, so this reduces the overall memory overhead.
• Flexibility: This structure works well for large address spaces without requiring a single massive page table.

Drawbacks

• Access Time: Requires multiple memory accesses (one per level), which can be slower than a single-level page table.

Hashed Page Tables

The Hashed Page Table structure is used for very large address spaces, typically in systems with 64-bit virtual addresses. In this scheme, a hash function is used to manage the page table entries in a way that speeds up lookups.

• Hash Function: A hash function maps the virtual page number to a hashed index in the page table.
• Hash Chain: Each entry in the hashed page table points to a linked list (chain) of pages that hash to the same index.
• Address Translation:
  1. The virtual page number is hashed to obtain the index in the hashed page table.
  2. The system then traverses the chain at that index, comparing each virtual page number with the requested virtual page number.
  3. When a match is found, the system retrieves the corresponding physical frame number.

Benefits

• Efficient Lookups for Large Address Spaces: This structure allows page tables to handle large address spaces efficiently because the hash table structure supports fast, direct access.

Drawbacks

• Complexity with Collisions: Multiple pages may hash to the same table index, resulting in hash collisions. This requires traversing chains, which may slightly slow down lookups.

Inverted Page Table

The Inverted Page Table structure aims to reduce the memory footprint of the page table by using a single entry per frame in physical memory rather than per page in virtual memory.

• Single Entry per Frame: Each entry in the inverted page table corresponds to a frame in physical memory, not a page in virtual memory.
• Stored Information: For each physical memory frame, the inverted page table entry stores:
  1. The virtual address of the page currently stored in that frame.
  2. Process ID (PID): Uniquely identifies the process that owns this page.
• Address Translation:
  1. When a virtual address needs to be translated, the OS searches the inverted page table for the entry that matches the virtual page number and PID.
  2. If a match is found, the corresponding physical frame number is used to generate the full physical address.

Benefits

• Memory Efficiency: Inverted page tables are memory-efficient because they only store entries for physical frames, not virtual pages. This significantly reduces the space required for page tables.

Drawbacks

• Slower Translation: Because there is only one entry per frame and the system must search for a matching virtual page number and PID, address translation takes longer compared to other page table structures.

Comparison 

Page Table Type	Structure	Memory Efficiency	Lookup Speed	Use Case
Hierarchical Page Table	Multilevel, outer and inner tables	Reduces memory needed	Slower, multiple accesses	Large virtual address spaces, typical in 32-bit or 64-bit systems
Hashed Page Table	Hashing based, uses hash chains	Efficient for large spaces	Fast lookup, collisions may slow	Very large virtual address spaces, e.g., 64-bit systems
Inverted Page Table	Single entry per frame in physical memory	Highly memory-efficient	Slower due to searches	Systems where physical memory size limits are more relevant

Page Table Location and Management

To manage memory efficiently, the system needs to quickly access the page table for each process.

• In Main Memory:
  • The page table is typically stored in main memory, allowing the system to access it during address translation.
  • When a process is created, its page table is initialized and loaded into main memory.
• Page Table Base Register (PTBR):
  • A special register called the Page Table Base Register (PTBR) points to the location of the page table in memory.
  • During a context switch (when the CPU switches from one process to another), only the PTBR needs to be updated with the base address of the new process’s page table, simplifying context management.

Translation Process

The address translation from a logical address to a physical address using the page table follows these steps:

1. Extract Page Number and Offset:
   • The logical address generated by the CPU is split into the page number (p) and the page offset (d). For example, if the logical address is a 16-bit address and the page size is 256 bytes, then:
     • The high-order 8 bits could represent the page number (2^8 = 256 pages).
     • The lower 8 bits represent the page offset (since each page can hold 256 bytes).
2. Lookup Page Table:
   • The CPU uses the page number (p) as an index into the page table. It retrieves the base address of the frame where the page is stored in physical memory.
3. Calculate Physical Address:
   • The retrieved base address (from the page table) is then combined with the page offset (d) to form the physical address.
   • The formula for the physical address becomes:Physical Address=(Frame Number×Page Size)+Page Offset (d)Physical Address=(Frame Number×Page Size)+Page Offset (d)
   • The frame number is derived from the page table lookup, while the page offset is directly from the logical address.
4. Access Physical Memory:
   • Using the calculated physical address, the CPU accesses the correct frame in main memory and retrieves the desired data or instruction.

Example of Address Translation in Paging

To understand this translation process better, let’s go through an example with specific numbers.

• Logical Address Space: Assume the logical address space is 24=1624=16 addresses, which allows addresses from 0 to 15.
• Physical Memory Size: Physical memory is 25=3225=32 addresses.
• Page Size: Suppose each page is 4 bytes.

With this configuration, the system would have:

• 4 pages in the logical address space (16 addresses / 4 bytes per page).
• 8 frames in physical memory (32 addresses / 4 bytes per frame).

Example Logical Address: Let’s take a logical address of 13.

1. Divide Logical Address:
   • Convert the logical address into page number and offset.
   • Page size is 4 bytes, so the offset is represented by 2 bits (log₂4 = 2).
   • The page number is represented by the remaining bits. Since we have 4 pages, we use 2 bits for the page number.
2. For address 13:
   • Page Number = 3 (binary 11).
   • Offset = 1 (binary 01).
3. Look Up in Page Table:
   • The page table entry for Page 3 might indicate that this page is stored in Frame 2.
4. Calculate Physical Address:
   • Frame Base Address: 2×4=82×4=8.
   • Physical Address: 8+1=98+1=9.

Thus, the logical address 13 maps to the physical address 9.

How Paging Avoids External Fragmentation

Paging allows non-contiguous allocation by filling free frames randomly with pages from a process.

• Since each page is independent, it can be placed into any available frame. Even if the frames are scattered throughout physical memory, the OS and page table will manage the organization.
• By allowing pages to be loaded into any available frames, paging eliminates external fragmentation issues, as memory does not need to be in a continuous block for any single process.

Why Paging Can Be Slow and How to Optimize It

Although paging solves the problem of fragmentation, it introduces a potential performance issue: multiple memory references are required to access the actual data in physical memory.

Multiple Memory Accesses:

• Every time a logical address is generated, the CPU needs to:
  • First, access the page table entry to find the physical address of the required page.
  • Second, retrieve the actual data from the physical memory location.
• This two-step memory access slows down the system, especially when multiple processes are running and memory accesses become frequent.

Optimization with TLB (Translation Lookaside Buffer):

The Translation Look-aside Buffer (TLB) is a specialized hardware cache that accelerates the paging process by storing recent translations of logical (or virtual) addresses to physical addresses. Let’s break down each component to understand how it works and why it’s crucial for efficient memory management:

• Speeding Up Paging: The TLB serves as a hardware support mechanism specifically designed to make paging faster.
• Caching Mechanism: It is a small, high-speed memory that temporarily holds the most recently accessed page table entries, allowing quick access to frequently used address mappings.

When a process needs access to a memory address, TLB provides a way to bypass repeated, slower memory accesses by storing this information temporarily.

Structure of TLB

• Key-Value Pairs: The TLB is organized as a collection of key-value pairs.
  • Key: The page number of a logical address.
  • Value: The frame number in physical memory where the page is stored.

When the TLB is queried, it matches the key (page number) to retrieve the corresponding value (frame number). This allows for a rapid lookup that skips the page table in main memory.

Problem with Regular Page Tables

• Page Table Storage: Since the page table resides in main memory, accessing it takes significantly longer.
• Slow Translation: Each time a memory address needs to be translated, the CPU must access the main memory to retrieve the frame number from the page table. This results in slower memory access because two memory accesses are required:
  1. First, to get the frame number from the page table.
  2. Second, to retrieve the data from the physical memory.

Using TLB addresses this issue by caching page table entries so they can be quickly retrieved without repeatedly accessing the main memory.

How TLB Works

The TLB works by caching page table entries that have recently been accessed or are likely to be accessed again soon:

1. Translation with TLB:
   • When a logical address is generated, the CPU first checks the TLB to see if the corresponding page number’s frame is already stored there.
   • If found, this is called a TLB hit, and the frame number can be directly retrieved from the TLB, saving time.
2. Updating TLB:
   • When a page number is not found in the TLB (a TLB miss), the CPU must then access the main memory to retrieve the frame number from the page table.
   • After obtaining the frame number, an entry for this page is added to the TLB so that future accesses can bypass the page table and use the faster TLB instead.
3. Replacement Policy:
   • Since the TLB has limited entries, it needs a replacement policy (e.g., Least Recently Used (LRU)) to decide which entries to replace when it’s full.

TLB Hit and TLB Miss

• TLB Hit: This occurs when the TLB contains the mapping for the requested logical address. The CPU can then quickly obtain the frame number without accessing the page table.
• TLB Miss: This occurs when the requested page number is not in the TLB. The CPU must then access the main memory page table to get the frame number, and this new mapping is subsequently added to the TLB.

Address Space Identifier (ASID)

Each TLB entry is associated with an Address Space Identifier (ASID), which uniquely identifies each process:

• Purpose of ASID: ASIDs help ensure that the TLB can store entries for multiple processes while maintaining security and accuracy.
• Process-Specific Access: When the TLB resolves a virtual page number, it checks whether the ASID for the current process matches the ASID stored with the virtual page in the TLB.
  • If they match, the translation proceeds normally (either a TLB hit or miss).
  • If they don’t match, the attempt is treated as a TLB miss because the translation is intended for a different process.

ASIDs ensure that TLB entries for different processes do not interfere with each other, allowing efficient context-switching.

Segmentation (A Non-Contiguous Memory Allocation Technique)

Segmentation is a memory management scheme designed to support the user’s view of memory, allowing for efficient and logical memory usage from a user’s perspective. Unlike paging, which is more closely associated with the operating system's view, segmentation aligns with how a user or programmer conceptualizes memory: as a collection of logically related parts, such as functions, variables, or data structures.

Structure of Segmentation

1. User-Oriented Memory ManagementSegmentation allows for the separation of a user's view of memory from the physical memory itself. This view aligns closely with how a programmer thinks about memory organization. For instance, memory might be viewed as a collection of logical units like functions, methods, objects, and arrays, rather than uniformly sized pages as in paging.
2. Segmented Logical Address Space
   • A logical address space in segmentation is divided into segments, where each segment corresponds to a logical unit of a program.
   • Each segment is defined by:
     • Segment Number (s): Identifies the segment.
     • Offset (d): Points to the specific location within that segment.
   • Thus, a logical address in segmentation is expressed as a two-tuple: ⟨segment-number, offset⟩ (⟨s, d⟩).
   • Unlike pages in paging, segments can vary in size based on the functions or data structures they represent.
3. Physical Memory Allocation for Segments
   • Each segment is allocated a contiguous block of physical memory, making intra-segment access fast and efficient.
   • The Segment Table contains entries for each segment, where each entry has:
     • Base: Starting physical address where the segment is stored.
     • Limit: Length of the segment, specifying the valid range for the offset within the segment.
4. Address Translation in Segmentation
   • The Segment Number is used as an index in the Segment Table.
   • The Offset (d) must be within the segment’s limit; if not, the OS traps the error, preventing access beyond segment bounds.
   • If the offset is valid, it’s added to the base address to produce the exact physical address in memory.

Segmentation Hardware Components

Segmentation hardware components are essential for managing memory in a system that uses segmentation for non-contiguous memory allocation. These components include specialized registers and a Segment Table, which collectively help the operating system keep track of segments and efficiently translate logical addresses into physical addresses. Here’s a detailed look at each component and how they work together to support segmentation.

Segment Table Base Register (STBR)

The Segment Table Base Register (STBR) holds the starting physical address of the segment table in main memory. This register acts as a pointer to where the segment table begins, allowing the operating system and hardware to locate the table efficiently. Key functions of the STBR include:

• Direct Memory Access: By pointing to the start of the segment table, the STBR allows the hardware to access segment details without scanning memory.
• Context Switching: During a context switch between processes, the STBR value changes to point to the new process’s segment table, allowing each process to have its own isolated view of memory.

The STBR thus plays a vital role in ensuring the right segment table is accessed for the currently active process.

Segment Table Length Register (STLR)

The Segment Table Length Register (STLR) specifies the total number of segments used by the current process. This value serves as a boundary for the segment table, ensuring that only valid segment numbers are referenced during memory access. Key functions of the STLR include:

• Bounds Checking: By defining the upper limit of segments, the STLR prevents any memory access to undefined segments, which could lead to errors or security vulnerabilities.
• Dynamic Allocation: Different processes can have varying numbers of segments; the STLR allows each process’s segment table to be sized according to its needs.

With the STLR in place, the hardware knows the exact size of the segment table and can validate whether a segment number in a logical address is within the permitted range for the active process.

Segment Table

The Segment Table is a data structure that contains entries for each segment in a program’s logical address space. Each entry in the segment table has two key values:

• Base Address: The starting physical memory address where the segment resides.
• Limit: The length of the segment, defining its valid range within physical memory.

The Segment Table is critical for address translation in segmentation. Here’s how it functions:

• Using Segment Number as an Index: When a logical address is generated by the CPU, the segment number (s) is used as an index into the segment table to retrieve the segment’s base and limit values.
• Address Validation: The limit value associated with each segment ensures that the offset within the segment (d) is within a permissible range, preventing access beyond the segment’s defined space.
• Calculating Physical Address: Once validated, the physical address is calculated by adding the offset (d) to the base address. This physical address points to the exact location in memory where the desired data resides.

How the Segmentation Hardware Components Work Together

When a program generates a logical address, these components work in tandem to translate it into a physical memory address as follows:

1. Segment Table Lookup:
   • The segment number (s) in the logical address is used to access the Segment Table using the Segment Table Base Register (STBR).
2. Bounds Checking:
   • The Segment Table Length Register (STLR) ensures that the segment number (s) is within the allowed range, validating that the address belongs to a defined segment for the active process.
3. Offset Validation:
   • The offset (d) in the logical address is compared to the limit value of the segment. If the offset is within bounds, it’s considered a valid address within the segment.
4. Physical Address Calculation:
   • If all checks pass, the hardware adds the offset (d) to the base address from the segment table to compute the physical address in memory.

Example of Segmentation

Consider a process with five segments numbered from 0 to 4:

• Each segment is stored in physical memory in a contiguous block.
• The Segment Table contains:
  • Segment 2, for example, begins at physical address 4300 and has a length of 400 bytes.
  • A request for byte 53 of segment 2 results in an address translation of:
    • Physical Address = 4300 + 53 = 4353.

Advantages of Segmentation

1. No Internal Fragmentation: Since segments are assigned contiguous memory blocks, there is no internal fragmentation within each segment.
2. Efficiency within Segments: Each segment contains related functions or data, improving efficiency as all elements of a segment are logically grouped and can be processed together.
3. Smaller Segment Table Size: The segment table is typically smaller than a page table since it only stores entries for logical program units, not uniformly sized pages.
4. User-Friendly Memory Organization: Since segmentation is based on the logical structure of a program, it allows for more natural organization of related functions, improving program efficiency.

Disadvantages of Segmentation

1. External Fragmentation: Over time, as segments are allocated and deallocated, free memory spaces become fragmented. This fragmentation can reduce usable memory and potentially require compaction.
2. Complexity with Variable Segment Sizes: Swapping segments in and out of memory becomes more challenging because segments vary in size. This variability complicates memory management, especially as segment sizes may not fit neatly into the available free memory spaces.

Comparison with Paging

• User vs. OS Perspective:
  • Paging: Prioritizes the operating system’s perspective, dividing memory into fixed-sized pages, disregarding logical structure. This approach may fragment functions or logically connected elements across multiple pages.
  • Segmentation: Prioritizes the user’s view of memory, organizing memory by functions, variables, or logical program elements.
• Memory Efficiency:
  • Paging: Eliminates external fragmentation but may introduce internal fragmentation when page frames are not entirely used.
  • Segmentation: Prevents internal fragmentation but can suffer from external fragmentation over time.

Aspect	Paging	Segmentation
Size	Pages and frames are fixed in size, with the page/frame size determined by the hardware.	Segments can vary in size, as they are defined by the system user according to logical units.
Fragmentation	Paging can lead to internal fragmentation if a page isn’t fully utilized (although modern OSs mitigate this).	Segmentation results in external fragmentation due to variable-sized segments scattered across memory.
Tables	Page tables, used by the Memory Management Unit (MMU), locate and manage pages. This process is slower than with segmentation tables, but is sped up by the Translation Lookaside Buffer (TLB).	Segmentation tables contain segment IDs and relevant information. Direct lookup is faster than page tables because each segment is contiguous.
Availability	Paging is widely supported on modern CPUs and MMU chips for effective memory management.	Segmentation is less widely supported. Windows may support it for backward compatibility, while Linux has limited support.

Hybrid Approach: Segmentation and Paging Combined

Modern systems often integrate both segmentation and paging, combining the user-oriented benefits of segmentation with the efficiency of paging. In such hybrid schemes:

• Logical Address: Initially segmented, providing the user’s view of memory.
• Each Segment: Further divided into pages, optimizing memory usage by minimizing both internal and external fragmentation.

This combined approach allows the operating system to manage memory more flexibly, taking advantage of paging’s efficiency and segmentation’s user-oriented view.