Research Exercise
The key to using memory efficiently is virtual memory management. Consider both Windows and a UNIX/Linux operating system. Compare and contrast how each implements virtual memory. Describe how each one handles page faults, page sizes and how it reconciles thrashing issues. Cite your sources.
|
Windows OS |
UNIX/Linux
OS |
Similarity |
Hardware Abstraction Layer: All OSes have a layer
called the hardware abstraction layer (HAL) which does the system-dependent
work, and thus enables the rest of the kernel to be coded in platform
independent fashion. This eases porting it to other platforms.
Copy-on-write: When a page is to be shared, the system
uses only one page with both processes sharing that same copy of the page.
However, when one of the process does a write onto the page, a private copy
is made for that process, which it can then manipulate individually. This
gives a lot better efficiency.
Shadow paging: A shadow object is created for an
original object such that the shadow object has some of its pages modified
from the original object, but shares the rest of the pages with the original
object. They are formed as a result
of Copy-On-Write action.
A Background daemon: There exists a background daemon
which is invoked periodically and performs tasks like page flushing, freeing
unused memory, etc.
Memory mapped Files: A file can be mapped onto memory,
which then can be used with simple memory read/write instructions.
Inter-Process Communication: The memory mapped files
are allowed to be then shared between processes forming a method for
interprocess
communication.
|
Differences |
In UNIX/Linux, one can use a swap file, both perform
better with a swap partition. The reason for this is that the swap is
performed outside of the file system. That is, the partition is used in raw
mode and the OS keeps track of where it stores swapped data by cylinder and
sector, significantly faster than going through the fs to swap to a file, as
in the case of MS. On Unix/Linux systems running a large database, one of
the methods of speeding database access is to run the databease in raw mode
outside of the normal fs.
The capability of handling virtual memory is built into
the microprocessor. UNIX/Linux tends to utilize this capability with the
minimum of extra logic. Whereas MS tends to wrap this basic capability in a
large amount of system code to have it perform to their idea of what VM
should be.
|
Page Faults Handling |
Windows uses
structured exception handling to report
page fault-based invalid accesses as
access violation exceptions
Windows versions
also write a
minidump (similar in principle to a
core dump) describing the state of the
crashed process for later analysis alongside such less-technical error
messages
|
UNIX (and
UNIX-like) systems typically use
signals, such as
SIGSEGV, to report these error
conditions to programs
UNIX and
UNIX-like operating systems typically
report these conditions to the user with error messages such as
"segmentation violation", or "bus error".
|
Page Sizes Handling |
Windows NT and its variants employ a dynamically
allocated pagefile for memory management. A pagefile is allocated on disk,
for less frequently accessed objects in memory, leaving more RAM available
to actively used objects. This scheme suffers from slow-downs due to disk
fragmentation, which hampers the speed at which the objects can be brought
back into memory when they are needed. Windows can be configured to place
the pagefile on a separate partition; doing this negates the
disk-fragmentation issues, but introduces an I/O slowdown due to the seek
time involved in switching back and forth between the two partitions.
However, the main reason this is not done by default is that, if the
pagefile is on a separate partition, then Windows cannot create a memory
dump in the event of a Stop Error. The ideal solution performance-wise is to
have the pagefile on a separate hard drive to the primary one, which
eliminates both defragmentation and I/O issues.
|
Most hard drive installations of Linux utilize a "swap
partition", where the disk space allocated for paging is separate from
general data, and is used strictly for paging operations. This reduces
slowdown due to disk fragmentation from general use. As with Windows, for
best performance the swap partition should be placed on a separate hard
drive to the primary one.
|
Thrash Issues Reconcile
|
In NT-based versions of Windows (such as
Windows XP and
Windows Vista), the file used for
paging is named
pagefile.sys. The
default location of the page file is in the root directory of the partition
where Windows is installed. Windows can be configured to use free space on
any available drives for pagefiles. It is required, however, for the boot
partition (i.e. the drive containing the Windows directory) to have a
pagefile on it if the system is configured to write either kernel or full
memory dumps after a
crash. Windows uses the paging file as
temporary storage for the memory dump. When the system is rebooted, Windows
copies the memory dump from the pagefile to a separate file and frees the
space that was used in the pagefile.
|
The old UNIX scheduler is priority based. The Linux process-scheduling
algorithm is based on the old UNIX scheduler. More details about
the Linux scheduler can be found for example in and in many
other books and websites.
The virtual memory capabilities along with the paging mechanism
give Linux the ability to handle many processes, even when the
real memory needs are larger than those of the available physical
memory. However, the virtual memory mechanism cannot handle
every situation. If the memory pages demand is too high over a
short period, the swapping mechanism cannot satisfy the memory
needs reasonably. Pages are frequently swapped in and out and a
little progress is made.
Linux only kills processes when
thrashing
occurs and the system is out of swap space. In some sense
there is nothing else that the kernel could do in this case,
since memory is needed but there is no more physical or swap
memory to allocate. When such a case occurs, Linux kernel kills the most
memory-consuming processes. This feature is very drastic; hence
its implications might be severe. For example, if a server runs
several applications with mutual dependencies, killing one of the
applications may yield unexpected results.
The recent Linux 2.6 version has adopted the token-ordered LRU
policy. The basic concept of this policy is eliminating page
swapping at some cases called by the authors ‘false LRU pages’.
Occasionally, a page of a sleeping process is swapped out,
although it would have not been swapped out if the process were
not sleeping. The idea of the token-ordered LRU policy is setting
one or multiple tokens in the system. The token is taken by one
process when a page fault occurs. The system eliminates the false
LRU pages for the process holding the token and allows the
process a quick establishing of its working set. By giving this
privilege to a process, the total number of false LRU pages is
reduced and an order is put in the pool of the competing pages.
However, this policy can be helpful only if the memory needs
slightly exceed those of the physical memory. A large memory
excess by many processes will be treated by this method as FIFO,
while the other processes still vie for memory allocations and
thrash; hence, the authors of suggest to keep the traditional
killing approach of Linux for severe cases. We suggest another
approach that can also handle these severe cases.
In addition, the process selection algorithm of Linux can mistakenly
select a process that executes an endless loop. Such a selection
will worsen the
thrashing. Even selecting a very long process
that is executed for some hours will be harmful. The selection
algorithm can just guess which the shortest process is, but this
guess may be wrong.
|
Implementation of Virtual Memory
|
The data structures used by Windows NT are as shown in
Figure 3.
Instead of a linked list, the Windows NT System keeps
it in a tree form. Each node of the tree is called Virtual Address
Descriptors(VAD). Each VAD denotes a range of address which has the same
protection parameters and commit state information. The
tree is also a balanced, which means that depth of the
tree is kept at a minimum. This then implies that the search time, say when
finding the node containing a location, will be relatively low. The VAD
marks each node as either committed, free, or reserved. Committed are the
ones which have been used i.e. code or
data has been mapped onto it. Nodes that are marked
free are yet unused, and those marked reserved are the ones which are not
available for being mapped until the reservation is explicitly removed.
Reservation are used in special cases, for example, a node can be reserved
for a thread’s stack when a thread is created. The link to the root of the
tree is kept in the Process Control Block.
|
Linux implements the virtual memory data structure in a
similar manner to UNIX. It maintains a linked list of vm area structs. These
are structures which represent
continuous memory areas which have the same protection parameters etc.
This list is searched whenever a page is to be found that consists a
particular location. The structure also records the range of address it is
mapping onto, protection mode, whether it is pinned in memory(not
page-able), and the direction (up/down) it will grow in. It also records
whether the area is public or private. If the number of entries grows
greater than a particular number, usually 32, then the linked list is
converted into a tree. This is a quite good approach which uses the best
structure in the best situations. |
References:
http://discussions.virtualdr.com/archive/index.php/t-73511.html
www.weblearn.hs-bremen.de/risse/RST/docs/Memory/comparison.pdf
www.gaurang.org/academics/csci555/termpaper.ps
http://en.wikipedia.org/wiki/Page_fault
No comments:
Post a Comment