Non-Contiguous Allocation Management

Non-Contiguous Allocation

Non-contiguous allocation lets the memory space of a process be scattered across physical memory, which removes the external fragmentation that plagues contiguous allocation.

Paging

Basic Idea

Both the logical address space of a process and the physical memory are divided into fixed-size pages and frames, and a page table maps each logical page to a physical frame.

Address Structure

The translation process:

1. Extract the page number from the logical address
2. Look up the corresponding frame number in the page table
3. Combine the frame number with the page offset to form the physical address

Page Table Structure

typedef struct {
    int frame_number;    // physical frame number
    int valid;          // valid bit: 1-in memory, 0-on disk
    int dirty;          // dirty bit: 1-modified, 0-not modified
    int referenced;      // reference bit: 1-recently accessed, 0-not accessed
    int protection;      // protection bits: read/write/execute permission
} PageTableEntry;

#define PAGE_SIZE 4096
#define MAX_PAGES 1024

PageTableEntry page_table[MAX_PAGES];
int page_table_size;

Address Translation Implementation

int page_address_translation(int logical_addr) {
    int page_number = logical_addr / PAGE_SIZE;
    int page_offset = logical_addr % PAGE_SIZE;

    // Check whether the page number is valid
    if (page_number >= page_table_size) {
        return -1;  // page number out of bounds
    }

    // Check whether the page is in memory
    if (!page_table[page_number].valid) {
        // The page is not in memory and has to be brought in
        if (page_fault_handler(page_number) != 0) {
            return -1;  // failed to bring the page in
        }
    }

    // Update the reference bit
    page_table[page_number].referenced = 1;

    // Compute the physical address
    int frame_number = page_table[page_number].frame_number;
    int physical_addr = frame_number * PAGE_SIZE + page_offset;

    return physical_addr;
}

Page Table Optimizations

1. Multilevel Page Table

// Two-level page table structure
typedef struct {
    int page_directory[1024];  // page directory
    PageTableEntry page_tables[1024][1024];  // page tables
} TwoLevelPageTable;

int two_level_address_translation(int logical_addr, TwoLevelPageTable *pt) {
    int page_directory_index = (logical_addr >> 22) & 0x3FF;
    int page_table_index = (logical_addr >> 12) & 0x3FF;
    int page_offset = logical_addr & 0xFFF;

    // Check the page directory entry
    if (!pt->page_directory[page_directory_index]) {
        return -1;  // the page table does not exist
    }

    // Access the page table
    PageTableEntry *entry = &pt->page_tables[page_directory_index][page_table_index];

    if (!entry->valid) {
        return -1;  // the page is not in memory
    }

    return entry->frame_number * PAGE_SIZE + page_offset;
}

2. Inverted Page Table

typedef struct {
    int process_id;      // process id
    int page_number;     // page number
    int frame_number;    // frame number
} InvertedPageTableEntry;

InvertedPageTableEntry inverted_table[MAX_FRAMES];
int frame_count;

int inverted_address_translation(int logical_addr, int process_id) {
    int page_number = logical_addr / PAGE_SIZE;
    int page_offset = logical_addr % PAGE_SIZE;

    // Search the inverted page table
    for (int i = 0; i < frame_count; i++) {
        if (inverted_table[i].process_id == process_id &&
            inverted_table[i].page_number == page_number) {
            return inverted_table[i].frame_number * PAGE_SIZE + page_offset;
        }
    }

    return -1;  // the page is not in memory
}

3. TLB (Translation Lookaside Buffer)

typedef struct {
    int page_number;     // page number
    int frame_number;    // frame number
    int valid;          // valid bit
    int process_id;     // process id
} TLBEntry;

#define TLB_SIZE 64
TLBEntry tlb[TLB_SIZE];

int tlb_address_translation(int logical_addr, int process_id) {
    int page_number = logical_addr / PAGE_SIZE;
    int page_offset = logical_addr % PAGE_SIZE;

    // Search the TLB
    for (int i = 0; i < TLB_SIZE; i++) {
        if (tlb[i].valid && tlb[i].process_id == process_id &&
            tlb[i].page_number == page_number) {
            // TLB hit
            return tlb[i].frame_number * PAGE_SIZE + page_offset;
        }
    }

    // TLB miss, go to the page table
    int physical_addr = page_address_translation(logical_addr);
    if (physical_addr != -1) {
        // Update the TLB
        update_tlb(page_number, physical_addr / PAGE_SIZE, process_id);
    }

    return physical_addr;
}

Segmentation

Basic Idea

The address space of a process is divided into segments along the logical structure of the program, and each segment corresponds to a logical module such as the code segment, the data segment, or the stack segment.

Address Structure

Segment Table Structure

typedef struct {
    int base;           // segment base address
    int limit;          // segment length
    int valid;          // valid bit
    int protection;     // protection bits
    int accessed;       // accessed bit
    int modified;       // modified bit
} SegmentTableEntry;

#define MAX_SEGMENTS 16
SegmentTableEntry segment_table[MAX_SEGMENTS];
int segment_count;

Address Translation Implementation

int segment_address_translation(int logical_addr, int segment_number) {
    // Check whether the segment number is valid
    if (segment_number >= segment_count) {
        return -1;  // segment number out of bounds
    }

    SegmentTableEntry *entry = &segment_table[segment_number];

    // Check whether the segment is in memory
    if (!entry->valid) {
        return -1;  // the segment is not in memory
    }

    // Check whether the offset inside the segment is out of bounds
    int segment_offset = logical_addr;
    if (segment_offset >= entry->limit) {
        return -1;  // segment offset out of bounds
    }

    // Update the accessed bit
    entry->accessed = 1;

    // Compute the physical address
    int physical_addr = entry->base + segment_offset;

    return physical_addr;
}

Comparing Segmentation and Paging

Segmented Paging

Basic Idea

Segmented paging combines the advantages of segmentation and paging: the address space is first split by logical structure, and then every segment is divided into fixed-size pages.

Address Structure

Address Translation Process

1. Segment table lookup: use the segment number to find the segment table and obtain the segment base and the segment length
2. Offset check: check whether the offset inside the segment is out of bounds
3. Page table lookup: use the page number inside the segment to find the page table and obtain the frame number
4. Physical address computation: combine the frame number with the page offset

Segmented Paging Address Translation

typedef struct {
    int base;           // segment base address
    int limit;          // segment length
    int valid;          // valid bit
    int page_table_base; // page table base address
} SegmentTableEntry;

typedef struct {
    int frame_number;    // frame number
    int valid;          // valid bit
    int protection;     // protection bits
} PageTableEntry;

int segment_page_address_translation(int logical_addr, int segment_number) {
    // Step 1: segment table lookup
    if (segment_number >= segment_count) {
        return -1;  // segment number out of bounds
    }

    SegmentTableEntry *seg_entry = &segment_table[segment_number];
    if (!seg_entry->valid) {
        return -1;  // the segment is not in memory
    }

    // Step 2: check the offset inside the segment
    int segment_offset = logical_addr;
    if (segment_offset >= seg_entry->limit) {
        return -1;  // segment offset out of bounds
    }

    // Step 3: page table lookup
    int page_number = segment_offset / PAGE_SIZE;
    int page_offset = segment_offset % PAGE_SIZE;

    PageTableEntry *page_entry = &page_tables[seg_entry->page_table_base][page_number];
    if (!page_entry->valid) {
        return -1;  // the page is not in memory
    }

    // Step 4: compute the physical address
    int physical_addr = page_entry->frame_number * PAGE_SIZE + page_offset;

    return physical_addr;
}

Memory Sharing

Sharing in Paging Systems

// Implementation of shared pages
typedef struct {
    int frame_number;    // frame number
    int reference_count; // reference count
    int shared;          // shared flag
} SharedPageInfo;

SharedPageInfo shared_pages[MAX_FRAMES];

int share_page(int process_id, int page_number, int frame_number) {
    // Check whether the page has already been shared
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (shared_pages[i].frame_number == frame_number) {
            shared_pages[i].reference_count++;
            return i;
        }
    }

    // Create a new shared page
    int index = find_free_shared_slot();
    shared_pages[index].frame_number = frame_number;
    shared_pages[index].reference_count = 1;
    shared_pages[index].shared = 1;

    return index;
}

void unshare_page(int process_id, int page_number) {
    // Decrease the reference count
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (shared_pages[i].frame_number == get_frame_number(process_id, page_number)) {
            shared_pages[i].reference_count--;
            if (shared_pages[i].reference_count == 0) {
                // Free the page
                free_frame(shared_pages[i].frame_number);
                shared_pages[i].shared = 0;
            }
            break;
        }
    }
}

Sharing in Segmentation Systems

// Implementation of shared segments
typedef struct {
    int segment_number;  // segment number
    int base;           // segment base address
    int limit;          // segment length
    int reference_count; // reference count
    int shared;         // shared flag
} SharedSegmentInfo;

SharedSegmentInfo shared_segments[MAX_SEGMENTS];

int share_segment(int process_id, int segment_number) {
    // Look for an existing shared segment with the same properties
    for (int i = 0; i < MAX_SEGMENTS; i++) {
        if (shared_segments[i].shared &&
            shared_segments[i].limit == get_segment_limit(process_id, segment_number)) {
            shared_segments[i].reference_count++;
            return i;
        }
    }

    // Create a new shared segment
    int index = find_free_shared_slot();
    shared_segments[index].segment_number = segment_number;
    shared_segments[index].base = get_segment_base(process_id, segment_number);
    shared_segments[index].limit = get_segment_limit(process_id, segment_number);
    shared_segments[index].reference_count = 1;
    shared_segments[index].shared = 1;

    return index;
}

Memory Protection

Protection in Paging Systems

// Page-level protection
typedef struct {
    int frame_number;    // frame number
    int read;           // read permission
    int write;          // write permission
    int execute;        // execute permission
    int user;           // user permission
} PageProtection;

int check_page_protection(int logical_addr, int access_type, int user_mode) {
    int page_number = logical_addr / PAGE_SIZE;
    PageProtection *prot = &page_protection[page_number];

    switch (access_type) {
        case READ_ACCESS:
            if (!prot->read) return -1;
            break;
        case WRITE_ACCESS:
            if (!prot->write) return -1;
            break;
        case EXECUTE_ACCESS:
            if (!prot->execute) return -1;
            break;
    }

    // Check the user permission
    if (user_mode && !prot->user) {
        return -1;
    }

    return 0;
}

Protection in Segmentation Systems

// Segment-level protection
typedef struct {
    int base;           // segment base address
    int limit;          // segment length
    int read;           // read permission
    int write;          // write permission
    int execute;        // execute permission
    int user;           // user permission
} SegmentProtection;

int check_segment_protection(int logical_addr, int segment_number,
                           int access_type, int user_mode) {
    SegmentProtection *prot = &segment_protection[segment_number];

    // Check the offset inside the segment
    int offset = logical_addr;
    if (offset >= prot->limit) {
        return -1;  // segment offset out of bounds
    }

    // Check the access permissions
    switch (access_type) {
        case READ_ACCESS:
            if (!prot->read) return -1;
            break;
        case WRITE_ACCESS:
            if (!prot->write) return -1;
            break;
        case EXECUTE_ACCESS:
            if (!prot->execute) return -1;
            break;
    }

    // Check the user permission
    if (user_mode && !prot->user) {
        return -1;
    }

    return 0;
}

Practical Applications

Memory Management in Linux

Linux uses segmented paging, but it relies mainly on paging:

// Memory management in the Linux kernel
struct mm_struct {
    struct vm_area_struct *mmap;        // list of memory regions
    struct rb_root mm_rb;               // red-black tree
    unsigned long start_code, end_code; // code segment
    unsigned long start_data, end_data; // data segment
    unsigned long start_brk, brk;       // heap
    unsigned long start_stack;          // stack
    unsigned long arg_start, arg_end;   // arguments
    unsigned long env_start, env_end;   // environment variables
};

Memory Management in Windows

Windows uses paging:

// Windows memory management API
HANDLE CreateFileMapping(
    HANDLE hFile,
    LPSECURITY_ATTRIBUTES lpAttributes,
    DWORD flProtect,
    DWORD dwMaximumSizeHigh,
    DWORD dwMaximumSizeLow,
    LPCTSTR lpName
);

LPVOID MapViewOfFile(
    HANDLE hFileMappingObject,
    DWORD dwDesiredAccess,
    DWORD dwFileOffsetHigh,
    DWORD dwFileOffsetLow,
    SIZE_T dwNumberOfBytesToMap
);

Summary

Non-contiguous allocation, through paging, segmentation, and segmented paging, removes the fragmentation problems of contiguous allocation and raises memory utilization. Modern operating systems mainly use segmented paging, which keeps the logical structure of the program while offering a flexible memory management mechanism.

---

Glossary