Allocation of Frames

Allocation of Frames

Two important tasks in virtual memory management are: a page-replacement strategy and a frame-allocation strategy. 

1. Minimum Number of Frames

The absolute minimum number of frames that a process must be allocated is dependent on system architecture. One reason for allocating at least a minimum number of frames involves performance. As the number of frames allocated decreases, the page fault rate increases results slowing process execution.

Enough frames had to be allocated to hold all the different pages that any single instruction can reference.

The worst case involves indirect addressing, particularly where multiple levels of indirect addressing are allowed. Left unchecked, a pointer to a pointer to a pointer to a pointer to a . . . could theoretically touch every page in the virtual address space in a single machine instruction, requiring every virtual page be loaded into physical memory simultaneously. For this reason architectures place a limit ( say 16 ) on the number of levels of indirection allowed in an instruction, which is enforced with a counter initialized to the limit and decremented with every level of indirection in an instruction - If the counter reaches zero, then an "excessive indirection" trap occurs.

2. Allocation Algorithms

Equal Allocation - If there are m frames available and n processes to share them, each process gets 

m / n frames, and the leftovers are kept in a free-frame buffer pool.

Proportional Allocation - Allocate the frames proportionally to the size of the process, relative to the total size of all processes. 

So if the size of process i is S_i, and S is the sum of all S_i, then the allocation for process P_i is 

a_i = m * S_i / S, where ‘m’ is total number of available frames.

Variations on proportional allocation could consider priority of process rather than just their size.

3. Global versus Local Allocation

Page replacement algorithms can be classified into two broad categories: global replacement and local replacement.

·         With local replacement, the number of pages allocated to a process is fixed, and page replacement occurs only amongst the pages allocated to this process.

·         With global replacement, any page may be a potential victim, whether it currently belongs to the process seeking a free frame or not.

·         Local page replacement allows processes to better control their own page fault rates, and leads to more consistent performance of a given process over different system load levels.

·         Global page replacement is overall more efficient, and is the more commonly used approach.

4. Non-Uniform Memory Access

The assumption is that all main memory is created equal or at least that is accessed equally. On many systems this is not the case like in multiple-processor systems, especially where each CPU is physically located on a separate circuit board which also holds some portion of the overall system memory. The performance differences are caused by how CPU’s and memory are interconnected in the system.

Systems in which memory access times vary significantly are collectively known as non-uniform memory access (NUMA) systems. Memory allocation algorithms have to be modified by considering NUMA into account; similar changes have to be made to scheduling system. The goal of these changes is to have memory frames allocated as close as possible to the CPU on which the processor running.