Virtual Memory Management

Virtual Memory Management

Virtual memory management is the core technology of modern operating systems. By extending the secondary storage to serve as an extension of main memory, it gives every process an address space larger than physical memory.

Core Concepts of Virtual Memory

Basic Idea

Virtual memory lets a process use an address space larger than physical memory. A page replacement mechanism swaps out the pages that are not used often to secondary storage and brings them back into memory when they are needed again.

Advantages of Virtual Memory

1. A larger address space

• A process can use an address space bigger than physical memory
• Large programs become runnable
• Memory utilization improves

2. Memory protection

• Every process has its own virtual address space
• Processes cannot interfere with each other
• Access permissions can be enforced on memory

3. Memory sharing

• Several processes can share the same pages
• Physical memory is saved
• Shared libraries become possible

4. Demand paging

• Only the pages that are needed are brought into memory
• Memory consumption goes down
• The concurrency of the system goes up

Implementation Mechanism

Core components:

1. Page table: records the mapping from virtual pages to physical frames
2. Page replacement algorithm: decides which pages get swapped out
3. Paging mechanism: handles page faults
4. Working set management: tracks the active pages of a process

Demand Paging

Basic Concept

Demand paging brings the pages of a process into memory only when they are needed, instead of loading all of them at once.

Page Table Entry 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
    int present;         // present bit: 1-in memory, 0-on disk
    int accessed;        // accessed bit: 1-accessed, 0-not accessed
} PageTableEntry;

Page Fault Handling

void page_fault_handler(int page_number) {
    // 1. Check whether the page is valid
    if (page_number >= page_table_size) {
        raise_segmentation_fault();
        return;
    }

    // 2. Check the page protection
    if (!check_page_protection(page_number, current_access)) {
        raise_protection_fault();
        return;
    }

    // 3. Find a free frame
    int frame_number = find_free_frame();
    if (frame_number == -1) {
        // No free frame, a page has to be replaced
        frame_number = page_replacement();
    }

    // 4. Bring the page in from secondary storage
    if (load_page_from_disk(page_number, frame_number) != 0) {
        raise_io_error();
        return;
    }

    // 5. Update the page table
    page_table[page_number].frame_number = frame_number;
    page_table[page_number].valid = 1;
    page_table[page_number].present = 1;
    page_table[page_number].referenced = 1;

    // 6. Update the TLB
    update_tlb(page_number, frame_number);

    // 7. Restart the instruction
    restart_instruction();
}

Page Replacement Strategies

1. Global Replacement

• The page to be replaced is chosen among the pages of all processes
• The memory usage of the whole system is taken into account
• It may starve a process

2. Local Replacement

• The page to be replaced is chosen only among the pages of the current process
• It guarantees the memory allocation of the process
• It may lead to low memory utilization

Page Replacement Algorithms

1. Optimal Replacement (OPT)

Basic idea: replace the page that will not be accessed for the longest time in the future.

Implementation example:

int optimal_page_replacement() {
    int victim_page = -1;
    int max_future_time = -1;

    for (int i = 0; i < page_table_size; i++) {
        if (page_table[i].valid) {
            int future_time = get_next_access_time(i);
            if (future_time > max_future_time) {
                max_future_time = future_time;
                victim_page = i;
            }
        }
    }

    return victim_page;
}

int get_next_access_time(int page_number) {
    // Find when the page is accessed next
    for (int i = current_time + 1; i < reference_string_length; i++) {
        if (reference_string[i] == page_number) {
            return i;
        }
    }
    return INT_MAX;  // never accessed again
}

Characteristics:

• The theoretically optimal algorithm
• It requires knowing the future reference sequence
• It cannot be implemented in practice

2. First In First Out (FIFO)

Basic idea: replace the page that entered memory earliest.

Implementation example:

typedef struct {
    int page_number;
    int entry_time;
} FIFOEntry;

FIFOEntry fifo_queue[MAX_FRAMES];
int queue_head = 0;
int queue_tail = 0;

int fifo_page_replacement() {
    // Choose the page that entered the queue earliest
    int victim_page = fifo_queue[queue_head].page_number;

    // Update the queue
    queue_head = (queue_head + 1) % MAX_FRAMES;

    return victim_page;
}

void fifo_page_in(int page_number) {
    // Add the new page to the queue
    fifo_queue[queue_tail].page_number = page_number;
    fifo_queue[queue_tail].entry_time = current_time;
    queue_tail = (queue_tail + 1) % MAX_FRAMES;
}

Characteristics:

• Simple to implement
• It ignores how often a page is used
• Poor performance

3. Least Recently Used (LRU)

Basic idea: replace the page that has gone unused for the longest time.

Implementation example:

typedef struct {
    int page_number;
    int last_access_time;
} LRUEntry;

LRUEntry lru_table[MAX_PAGES];

int lru_page_replacement() {
    int victim_page = -1;
    int oldest_time = INT_MAX;

    for (int i = 0; i < page_table_size; i++) {
        if (page_table[i].valid && lru_table[i].last_access_time < oldest_time) {
            oldest_time = lru_table[i].last_access_time;
            victim_page = i;
        }
    }

    return victim_page;
}

void lru_page_access(int page_number) {
    // Update the last access time of the page
    lru_table[page_number].last_access_time = current_time;
}

Characteristics:

• Good performance
• The access time of every page has to be recorded
• The hardware support is complicated

4. Clock Algorithm

Basic idea: use a circular queue to simulate a clock and replace the page whose reference bit is 0.

Implementation example:

typedef struct {
    int page_number;
    int reference_bit;
} ClockEntry;

ClockEntry clock_queue[MAX_FRAMES];
int clock_hand = 0;

int clock_page_replacement() {
    while (1) {
        if (clock_queue[clock_hand].reference_bit == 0) {
            // Found the page to be replaced
            int victim_page = clock_queue[clock_hand].page_number;
            clock_hand = (clock_hand + 1) % MAX_FRAMES;
            return victim_page;
        } else {
            // Give the page a second chance
            clock_queue[clock_hand].reference_bit = 0;
            clock_hand = (clock_hand + 1) % MAX_FRAMES;
        }
    }
}

void clock_page_access(int page_number) {
    // Set the reference bit of the page
    for (int i = 0; i < MAX_FRAMES; i++) {
        if (clock_queue[i].page_number == page_number) {
            clock_queue[i].reference_bit = 1;
            break;
        }
    }
}

Characteristics:

• Relatively simple to implement
• Performance close to LRU
• It needs little hardware support

5. Enhanced Clock Algorithm

Basic idea: consider the reference bit and the dirty bit together, preferring to replace a page that has neither been referenced nor modified.

Implementation example:

typedef struct {
    int page_number;
    int reference_bit;
    int dirty_bit;
} EnhancedClockEntry;

EnhancedClockEntry enhanced_clock_queue[MAX_FRAMES];
int enhanced_clock_hand = 0;

int enhanced_clock_page_replacement() {
    int first_unreferenced = -1;
    int first_unreferenced_clean = -1;

    // First round: look for a page that is neither referenced nor modified
    for (int i = 0; i < MAX_FRAMES; i++) {
        int index = (enhanced_clock_hand + i) % MAX_FRAMES;
        if (enhanced_clock_queue[index].reference_bit == 0) {
            if (first_unreferenced == -1) {
                first_unreferenced = index;
            }
            if (enhanced_clock_queue[index].dirty_bit == 0) {
                first_unreferenced_clean = index;
                break;
            }
        }
    }

    // Second round: if no clean page was found, take any unreferenced page
    if (first_unreferenced_clean != -1) {
        enhanced_clock_hand = (first_unreferenced_clean + 1) % MAX_FRAMES;
        return enhanced_clock_queue[first_unreferenced_clean].page_number;
    } else if (first_unreferenced != -1) {
        enhanced_clock_hand = (first_unreferenced + 1) % MAX_FRAMES;
        return enhanced_clock_queue[first_unreferenced].page_number;
    }

    // Third round: every page has been referenced, reset the reference bits
    for (int i = 0; i < MAX_FRAMES; i++) {
        enhanced_clock_queue[i].reference_bit = 0;
    }

    return enhanced_clock_page_replacement();
}

Page Allocation Strategies

1. Fixed Allocation

Basic idea: give every process a fixed number of pages.

Implementation example:

typedef struct {
    int process_id;
    int allocated_frames;
    int max_frames;
} ProcessFrameAllocation;

ProcessFrameAllocation frame_allocation[MAX_PROCESSES];

int allocate_frames_fixed(int process_id, int requested_frames) {
    if (frame_allocation[process_id].allocated_frames + requested_frames >
        frame_allocation[process_id].max_frames) {
        return -1;  // beyond the allocation limit
    }

    // Allocate the pages
    int allocated = 0;
    for (int i = 0; i < requested_frames && allocated < requested_frames; i++) {
        int frame = find_free_frame();
        if (frame != -1) {
            allocate_frame_to_process(frame, process_id);
            allocated++;
        }
    }

    frame_allocation[process_id].allocated_frames += allocated;
    return allocated;
}

2. Variable Allocation

Basic idea: adjust the number of pages given to a process dynamically according to its needs.

Implementation example:

typedef struct {
    int process_id;
    int allocated_frames;
    int working_set_size;
    float page_fault_rate;
} VariableAllocation;

VariableAllocation variable_allocation[MAX_PROCESSES];

int adjust_frame_allocation(int process_id) {
    float current_fault_rate = variable_allocation[process_id].page_fault_rate;
    int current_frames = variable_allocation[process_id].allocated_frames;

    if (current_fault_rate > HIGH_FAULT_RATE) {
        // The page fault rate is high, give it more frames
        return increase_frame_allocation(process_id);
    } else if (current_fault_rate < LOW_FAULT_RATE) {
        // The page fault rate is low, give it fewer frames
        return decrease_frame_allocation(process_id);
    }

    return current_frames;
}

The Working Set Model

Basic Concept

The working set is the set of pages a process has accessed during a recent period of time, and it reflects the locality of the process.

Computing the Working Set

typedef struct {
    int page_number;
    int last_access_time;
} WorkingSetEntry;

WorkingSetEntry working_set[MAX_PAGES];
int working_set_size = 0;

int calculate_working_set(int process_id, int window_size) {
    int current_time = get_current_time();
    int ws_size = 0;

    for (int i = 0; i < page_table_size; i++) {
        if (page_table[i].valid &&
            current_time - working_set[i].last_access_time <= window_size) {
            ws_size++;
        }
    }

    return ws_size;
}

void update_working_set(int page_number) {
    working_set[page_number].last_access_time = get_current_time();
    working_set[page_number].page_number = page_number;
}

Working Set Replacement Algorithm

int working_set_page_replacement(int window_size) {
    int current_time = get_current_time();
    int victim_page = -1;
    int oldest_time = INT_MAX;

    for (int i = 0; i < page_table_size; i++) {
        if (page_table[i].valid) {
            int time_since_access = current_time - working_set[i].last_access_time;
            if (time_since_access > window_size &&
                working_set[i].last_access_time < oldest_time) {
                oldest_time = working_set[i].last_access_time;
                victim_page = i;
            }
        }
    }

    return victim_page;
}

The Thrashing Problem

The Thrashing Phenomenon

Thrashing is the phenomenon in which the system swaps pages so frequently that the CPU utilization collapses.

Causes of Thrashing

1. Too few pages allocated: a process is given fewer pages than its working set needs
2. An unsuitable replacement algorithm: the chosen algorithm does not fit the current access pattern
3. Heavy contention for memory: several processes compete for the same limited memory at the same time

Detecting Thrashing

typedef struct {
    int process_id;
    int page_fault_count;
    int cpu_utilization;
    float fault_rate;
} ThrashingMonitor;

ThrashingMonitor thrashing_monitor[MAX_PROCESSES];

int detect_thrashing() {
    int thrashing_processes = 0;

    for (int i = 0; i < process_count; i++) {
        if (thrashing_monitor[i].fault_rate > THRESHOLD_FAULT_RATE &&
            thrashing_monitor[i].cpu_utilization < THRESHOLD_CPU_UTIL) {
            thrashing_processes++;
        }
    }

    return thrashing_processes > 0;
}

Preventing Thrashing

void prevent_thrashing() {
    if (detect_thrashing()) {
        // 1. Increase the page allocation
        increase_frame_allocation_for_all();

        // 2. Adjust the page replacement algorithm
        adjust_replacement_algorithm();

        // 3. Limit the number of processes
        limit_process_count();

        // 4. Use the working set model
        use_working_set_model();
    }
}

Performance Optimization

1. Prepaging

void prepaging(int process_id) {
    // Predict the pages that will be needed from the historical access pattern
    int predicted_pages[MAX_PAGES];
    int predicted_count = predict_pages(process_id, predicted_pages);

    for (int i = 0; i < predicted_count; i++) {
        if (!page_table[predicted_pages[i]].valid) {
            load_page_from_disk(predicted_pages[i], find_free_frame());
        }
    }
}

2. Page Buffering

typedef struct {
    int page_number;
    int frame_number;
    int dirty;
} PageBuffer;

PageBuffer page_buffer[MAX_BUFFER_SIZE];
int buffer_head = 0;
int buffer_tail = 0;

void buffer_page(int page_number, int frame_number) {
    page_buffer[buffer_tail].page_number = page_number;
    page_buffer[buffer_tail].frame_number = frame_number;
    page_buffer[buffer_tail].dirty = 0;
    buffer_tail = (buffer_tail + 1) % MAX_BUFFER_SIZE;
}

3. Copy-on-Write

int copy_on_write(int page_number) {
    if (page_table[page_number].reference_count > 1) {
        // Create a copy of the page
        int new_frame = allocate_new_frame();
        copy_page_content(page_table[page_number].frame_number, new_frame);

        // Update the page table
        page_table[page_number].frame_number = new_frame;
        page_table[page_number].reference_count = 1;

        return new_frame;
    }

    return page_table[page_number].frame_number;
}

Practical Applications

Virtual Memory in Linux

// Virtual memory management in the Linux kernel
struct vm_area_struct {
    unsigned long vm_start;      // start address
    unsigned long vm_end;        // end address
    unsigned long vm_flags;      // flags
    struct file *vm_file;        // mapped file
    unsigned long vm_pgoff;      // file offset
    struct vm_operations_struct *vm_ops; // operation functions
};

Virtual Memory in Windows

// Windows virtual memory API
LPVOID VirtualAlloc(
    LPVOID lpAddress,
    SIZE_T dwSize,
    DWORD flAllocationType,
    DWORD flProtect
);

BOOL VirtualFree(
    LPVOID lpAddress,
    SIZE_T dwSize,
    DWORD dwFreeType
);

Summary

Virtual memory management is the core technology of modern operating systems. Through page replacement, working set management, and performance optimization, it gives a process an address space larger than physical memory. Choosing the right page replacement algorithm and allocation strategy is essential for system performance, and modern operating systems usually combine several of these techniques to manage memory efficiently.

---

Glossary