Algorithm for allocating memory pages and page tables

Question

I want to design an algorithm for allocating and freeing memory pages and page tables. What data structures would allow best performance and simplest implementation?

Answer 1

The most common algorithm and data structure is called, unsurprisingly, the page table. At its most basic, it consists of a single array mapping blocks of virtual address space to blocks of physical address space; unallocated pages are set to null. When a process tries to access unmapped memory, the system takes a previously unused block of physical memory and maps it in the page table.

Since most virtual memory spaces are too big for a single level page table (a 32 bit machine with 4k pages would require 32 bits * (2^32 bytes / 4 kilobytes) = 4 megabytes per virtual address space, while a 64 bit one would require exponentially more), multi-level pagetables are used: The top level consists of pointers to second level pagetables, which point to actual regions of phyiscal memory (possibly with more levels of indirection). This allows the system to save memory on the pagetable when large areas of address space remain unused.

Answer 2

Even though OS normally implement page tables, the simpler solution could be something like this.

Have a large contiguous memory as an array. When you allocate some memory, maintain that information in a linked list storing the index of the array and the length in the data part.

When you are building the linked list, make sure that it is sorted on the index.

When you want to allocate memory, scan the linked list and this will take O(N). where N is the allocations already done.

Deletion will be scanning the array for the particular index and removing the node in linked list.

Once the node is removed, have a separate linked list containing these free allocations.

Insertion will look like this. 1. Check in free list if there is an element in the list of size requested. 2. If not, allocate memory after the last element of linked list

Deletion will work like this, 1. Move the node to the free list.

Make sure free list and linked list are sorted on the index.

This approach doesn't address the fragmentation issue in memory allocators.One easy approach is to use compaction. Regularly, scan the free node linked list and for each element move the elements in the array and update the index of the node in linked list appropriately.