little life

little life
11 little new born guppies in the house

Tuesday, September 2, 2008

VIRTUAL MEMORY MANAGEMENT






One of the most important aspects of an operating system is the Virtual Memory Management system. Virtual Memory (VM) allows an operating system to perform many of its advanced functions, such as process isolation, file caching, and swapping.

Virtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory, while in fact it is physically fragmented and may even overflow on to disk storage.

Systems which use this technique make programming of large applications easier and use real physical memory (e.g. RAM) more efficiently than those without virtual memory.

Note that "virtual memory" is not just "using disk space to extend physical memory size". Extending memory is a normal consequence of using virtual memory techniques, but can be done by other means such as overlays or swapping programs and their data completely out to disk while they are inactive.














































Windows OS

Operating System

UNIX/Linux OS

Windows NT needs to maintain a lot
of data. First, it needs to maintain whether each address is mapped to
physical RAM or the data is to be brought in from secondary storage when
a request with the address comes. Maintaining this information for each
byte itself takes a lot of space (actually, more space than the address
space for which the information is to be maintained). So Windows NT breaks
the address space into 4KB pages and maintains this information in page
tables.

As we saw earlier, a page table entry (PTE) consists of the address of
the physical page (if the page is mapped to physical RAM) and attributes
of the page. Since the processor heavily depends on PTEs for address translation,
the structure of PTE is processor dependent.

If a page is not mapped onto physical RAM, Windows NT marks the page as
invalid. Any access to this page causes a page fault, and the page fault
handler can bring in the page from the secondary storage.

To be more specific, when the page contains DLL code or executable module
code, the page is brought in from the DLL or executable file. When the
page contains data, it is brought in from the swap file. When the page
represents a memory-mapped file area, it is brought in from the corresponding
file.

Windows NT needs to keep track of free physical RAM so that it can allocate
space for a page brought in from secondary storage in case of a page fault.
This information is maintained in a kernel data structure called the Page
Frame Database (PFD). The PFD also maintains a First-In-First-Out (FIFO)
list of in-memory pages so that it can decide on pages to throw out in
case of a space crunch.

According to FIFO policy, the oldest data (that is, the data that was
brought in the RAM first) is thrown out whenever there is a space crunch.

Virtual memory management

Virtual memory consists of main memory
and swap space.

The Digital UNIX operating system keeps only a set of the recently used
pages of all processes in main memory and keeps the other pages on disk
in swap space. Virtual memory and the unified buffer cache (UBC) share
all physical memory.

Paging and swapping is used to ensure that the active task has the pages
in memory that are needed for it to execute. Paging is controlled by the
page reclamation code. Swapping is controlled by the task swapping daemon.

Much of the movement of addresses and data among the CPU cache, secondary
and tertiary cache, and physical memory is controlled by the hardware
logic and the Privileged Architecture Library (PAL) code, which is transparent
to the Digital UNIX operating system.

The virtual memory subsystem becomes involved when the CPU's translation
buffer is unable to map a requested virtual address to a physical address
and then traps to the PAL's page lookup code, which is responsible for
monitoring and loading addresses from the page table into the CPU's translation
buffer.

If the requested page has been referenced before, the virtual memory subsystem
loads the address of the requested page into the translation buffer and
performs a disk I/O to copy the contents of the page from swap space into
memory. This is known as a page-in page fault.

The Zoned Buddy Allocator interacts directly with the Memory Managemen
Unit (MMU), providing valid pages when the kernel asks for them. It also
manages lists of pages and keeps track of different categories of memory
addresses.

The Slab Allocator is another layer in front of the Buddy Allocator, and
provides the ability to create cache of memory objects in memory. On x86
hardware, pages of memory must be allocated in 4KB blocks, but the Slab
Allocator allows the kernel to store objects that are differently sized,
and will manage and allocate real pages appropriately.

Finally, a few kernel tasks run to manage specific aspects of the VMM.
Bdflush manages block device pages (disk IO), and kswapd handles swapping
pages to disk.

Pages of memory are either Free (available to allocate), Active (in use),
or Inactive. Inactive pages of memory are either dirty or clean, depending
on if it has been selected for removal yet or not. An inactive, dirty
page is no longer in use, but is not yet available for re-use. The operating
system must scan for dirty pages, and decide to deallocate them. After
they have been guaranteed sync’d to disk, an inactive page my be
“clean,” or ready for re-use.


Windows uses structured exception
handling to report page fault-based invalid accesses as access violation
exceptions. It involves the termination of the running task that caused
the error condition, a notification may be shown to user.

Recent versions of Windows often report such problems with less technical
error messages simply stating something along the lines of this program
must close. Additionally, recent Windows versions also write a minidump
(core dump) describing the state of the crashed process for later analysis
alongside such less-technical error messages.

Of course, since there is generally far less physical memory than there
is virtual memory, part of this mechanism defines what the hardware should
do if a virtual page is accessed but there is no translation defined to
a physical page. In Windows terminology, this is defined to be a page
fault.

When a page fault occurs, the hardware cannot do anything else with the
instruction that caused the page fault and thus it must transfer control
to an operating system routine (this is the page fault handler). The page
fault handler must then decide how to handle the page fault.

Only those parts of the program and data that are currently in active
use need to be held in physical RAM. Other parts are then held in a swap
file or page file. When a program tries to access some address that is
not currently in physical RAM, it generates an interrupt, called a Page
Fault. This asks the system to retrieve the 4 KB page containing the address
from the page file invisibly. Sometimes, through program or hardware error,
the page is not there either. The system then has an ‘Invalid Page
Fault’ error. This will be a fatal error if detected in a program:
if it is seen within the system itself (perhaps because a program sent
it a bad request to do something), it may manifest itself as a ‘blue
screen’ failure with a STOP code.

If there is pressure on space in RAM, then parts of code and data that
are not currently needed can be ‘paged out’ in order to make
room — the page file can thus be seen as an overflow area to make
the RAM behave as if it were larger than it is.


How it handles page faults

UNIX systems typically use signals,
such as SIGSEGV, to report these error conditions to programs. It involves
the termination of the running process that caused the error condition,
and a notification to the user that the program has malfunctioned. The
operating systems typically report these conditions to the user with error
messages such as "segmentation violation" or "bus error".

If the faulting virtual address is invalid this means that the process
has attempted to access a virtual address that it should not have. Maybe
the application has gone wrong in some way, for example writing to random
addresses in memory. In this case the operating system will terminate
it, protecting the other processes in the system from this rogue process.


If the faulting virtual address was valid but the page that it refers
to is not currently in memory, the operating system must bring the appropriate
page into memory from the image on disk. Disk access takes a long time,
relatively speaking, and so the process must wait quite a while until
the page has been fetched.

If there are other processes that could run, then the operating system
will select one of them to run. The fetched page is written into a free
physical page frame and an entry for the virtual page frame number is
added to the process' page table. The process is then restarted at the
machine instruction where the memory fault occurred. This time the virtual
memory access is made, the processor can make the virtual to physical
address translation and so the process continues to run.

Linux uses demand paging to load executable images into a process's virtual
memory. Whenever a command is executed, the file containing it is opened
and its contents are mapped into the process's virtual memory. This is
done by modifying the data structures describing this process' memory
map and is known as memory mapping. However, only the first part of the
image is actually brought into physical memory. The rest of the image
is left on disk. As the image executes, it generates page faults and Linux
uses the process's memory map in order to determine which parts of the
image to bring into memory for execution.


The page file is a hidden file in
the file type of pagefile.sys.

Windows divides up all the physical memory in the system into a series
of pages (on the x86 architecture this is normally 4kb but driver writers
should use the manifest constant PAGE_SIZE).

It also divides up the virtual address space into a series of comparably
sized pages as well. Finally, Windows and the underlying hardware platform
agree upon a means to tell the hardware how to translate the address of
a virtual page into a corresponding physical page.

It is regenerated at each boot, which is no need to be included in backup.


Page File

OS divides its main memory into pages
to allow better utilization of memory.

A page is a fixed length block of main memory, which is contiguous in
physical and also virtual memory addressing.The blocks of pages are examined
in a cyclical manner; a different block of pages is examined each time
an attempt is made to shrink the memory map.


If the amount of real memory installed
is less than the required amount of memory for the task at hand, a phenomenon
called "thrashing" can occur.

This is exhibited when the machine spends most of its time moving pages
to and from disk versus doing real work.

In our current working environment, the amount of memory required to use
the standard applications is less than 2MB.

To prevent thrashing, a process must be provided with as many frames as
it needs. The number of frames it needs can be determined with several
techniques, including the working-set strategy. This approach defines
the locality model process execution

Paging supervisor creates and manages the page tables. If the dynamic
address translation hardware raises a page fault interrupt, the paging
supervisor searches the page file for the page containing the required
virtual address, reads it into real physical memory, updates the page
tables to reflect the new location of the virtual address and finally
tells the dynamic address translation mechanism to start the search again.


Thrashing issues reconciliation

In the case of thrashing, pages are
constantly being written to and read back from disk. This causes the operating
system to be too busy to perform enough real work.

If, for example, physical page frame number 1 is being regularly accessed
then it is not a good candidate for swapping to hard disk. The set of
pages that a process is currently using is called the working set. An
efficient swap scheme would make sure that all processes have their working
set in physical memory.

The page fault handler then determines what must be done to resolve this
page fault. It can find where the desired page resides on disk and read
it in (this is normally the case if the page fault is for a page of code);
determine that the desired page is already in RAM (but not allocated to
the current process) and direct the MMU to point to it; point to a special
page containing nothing but zeros and later allocate a page only if the
page is ever written to (this is called a copy on write page, and is often
used for pages containing zero-initialized data)

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)