Skip to main content

Non-Contiguous Memory Allocation

Why is non-contiguous memory allocation necessary?​

Although dynamic contiguous memory allocation works well, it suffers from external fragmentation, and its solution—compaction—adds overhead to the operating system. A more efficient approach is to store a process in chunks or non-contiguous parts.

Non-contiguous memory allocation allows a process's memory to be allocated in multiple non-adjacent blocks, solving fragmentation issues and making more efficient use of memory.

Paging​

Paging
Paging

Paging is a memory management technique that eliminates the need for contiguous memory allocation by dividing the process's logical address space into fixed-size blocks called pages and the physical memory into blocks of the same size called frames. During execution, a process's pages can be loaded into any available frames in physical memory.

Page Table​

How Does the MMU Translate Logical Addresses to Physical Addresses?​

Since a process's pages can occupy different frames, a mapping is needed to track this. Each process has its own page table that maps pages to frames. The page table is stored in the Process Control Block (PCB).

Example of a Page Table:

Page No.Frame No.
02
13
25
30

  • In this table, each page of a process is mapped to a corresponding frame in physical memory.

  • Example: Logical address 25 (in binary 011001) is in page 1 with an offset of 9. Page 1 is mapped to frame 3, with a base address of 64. The physical address is 64 + 9 = 73.

Page Table Base Register (PTBR)​

How Does the System Know Which Page Table to Use?​

Each process has its own page table, and the system uses the Page Table Base Register (PTBR) to keep track of the page table for the currently running process. When a context switch occurs (switching from one process to another), the PTBR is updated to point to the new process's page table.

Is Paging Slow?​

Paging adds overhead because it requires finding a reference to the page table, using it to identify the frame, and then translating the logical address to a physical address. This multi-step process can be slower than direct address translation.

Can We Overcome the Slowness?​

Translation Lookahead Buffer (TLB)​

TLB
Translation Lookahead Buffer

A TLB is a hardware cache that stores recent translations of logical addresses to physical addresses, significantly speeding up memory access.

How the Translation Works with TLB:

  1. The CPU generates a logical address for the process.

  2. The address requires the page number and offset to access memory.

  3. The TLB is checked first:

    • TLB Hit: If the address is found, the frame number is quickly retrieved, and the logical address is translated to a physical address.

    • TLB Miss: If the address is not found, the page table is accessed to find the frame number, and the translation is stored in the TLB for future reference.

Is Normal TLB Enough?​

Imagine P1 is running, and its page 1 maps to frame 4. Now P2 starts running, and its page 1 maps to frame 2. If the TLB stores only the page-frame mapping without distinguishing processes, the TLB could incorrectly map P2's page 1 to frame 4 from P1's mapping. This scenario threatens process isolation.

Solution: Use Address Space Identifiers (ASID). Each process is assigned a unique ASID, so TLB entries include the ASID, page number, and frame number.

ASIDPage No.Frame No.
102
114
125
213

By including the ASID, TLB can distinguish between entries for different processes, maintaining accurate mappings.

Segmentation​

When processes have logical groups like functions or data structures, each group is stored in variable-sized segments rather than fixed-size pages. Segmentation is useful when internal fragmentation (wasted space within fixed-size pages) needs to be minimized.

Segmentation
Segmentation
Note

Each process has a segment table that stores the base address and limit for each segment, ensuring memory protection and efficient use.

How Address Translation Happens in Segmentation​

  1. The CPU generates a logical address containing a segment number and offset.

  2. The segment table is consulted to find the base address for the segment.

  3. A check ensures that the offset is within the segment's limit to prevent out-of-bounds access.

  4. If valid, the physical address is calculated by adding the base address to the offset.

Advantages of Segmentation​

  • No Internal Fragmentation: Segments can be sized to fit the logical blocks, reducing wasted space.

  • Logical Grouping: Segments represent logical units like functions or arrays, making memory management intuitive.

Disadvantages of Segmentation​

External Fragmentation: Since segments are variable-sized, they can lead to fragmentation over time as segments are allocated and deallocated.