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 Si,
and S is the sum of all Si, then the allocation for process Pi
is
ai = m * Si / 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.
No comments:
Post a Comment